18 ms·
C implementation of Tic-Tac-Toe in a single call to printf
- f2f 6y agothanks. now i have nightmares.
- yokohummer7 6y ago> %n takes a pointer and writes (!!) the number of bytes printed so far. > Okay, everyone probably knows this. Let's get a bit more advanced. Ok, but I didn't know about that. What's the use?
- zlynx 6y agoI seem to recall using it to auto-adjust column widths. And we did something with it involving string translations. Since we didn't control the translated format string we couldn't just count the characters in the source code. But it's been a really long time and I don't recall the details.
- deleted 6y ago[deleted]
- Someone 6y agoOne use is aligning outputs: char *prefix = "example"; char *line1 = "line 1"; char *line2 = "line 2"; printf("%s: %n%s\n", prefix, &n, line1); printf("%*s%s\n", n, "", line2); will output example: line 1 line 2 That’s a bit more robust than using strlen(s)+2, where you have to keep that magic constant 2 in sync with ": ". Moving ": " to a variable and using strlen(s)+strlen(separator) would fix that, though (at the price of speed, unless you’ve a compiler that optimizes that away)
- tgv 6y agoI'd never heard of %n, but I use printf's return value (the number of bytes written) for this kind of purpose, so n = printf("%s: ", prefix); printf("%s\n", line1); printf("%*s%s\n", n, " ", line2);
- MertsA 6y agoYeah but the difference is that you can use %n wherever you need it in the format string. Depending on what arguments come after it figuring out the length of the printed arguments might not be trivial whereas with printf, it already has to keep a count of it during execution in order to return it at the end so it's easy to add support for it.
- quietbritishjim 6y ago> That’s a bit more robust than using strlen(s)+2 strlen wouldn't even be an option if you were formatting something that's not a string e.g. int n; int prefix_num = 23; char *line1 = "line 1"; char *line2 = "line 2"; printf("example %d: %n%s\n", prefix_num, &n, line1); printf("%*s%s\n", n, "", line2);
- JoshTriplett 6y agoThis only works if you're not dealing with Unicode, where the number of bytes, the number of characters, and the width of those characters can all vary.
- JanisL 6y agoThis makes me wonder if there's some sort of Unicode equivalent for this?
- Someone 6y agoYou don’t need Unicode for that. It also requires you use a monospaced font. I think the feature predates that and Unicode, though. But even then, it fails if you underline text the way it was done at the time, either by using backspace and underline characters or by using termcap (https://en.wikipedia.org/wiki/Termcap https://en.wikipedia.org/wiki/Termcap)
- MertsA 6y agoWell the fun use is using it to exploit printf format string vulnerabilities. Microcorruption has a fun level involving that IIRC.
- CamperBob2 6y agoNormally you'd use %n with input functions like scanf(), not printf().
- bawolff 6y agoTo support format string vulnerabilities! /s
- mariomatos 6y agoSome advanced clickbait we have here.
- encom 6y agoNah. Dennis Ritchie HATES him. Program like a pro with this one weird trick! You won't believe what happens! That's proper bait.
- qllp100 6y agoHence advanced bait. printf() is called in a while loop, so it is hardly a single call.
- taspeotis 6y agoI don’t want to jump on the title hate bandwagon - what the author has done is definitely creative and clever and this discussion detracts from it - but it also uses scanf.
- quietbritishjim 6y agoWhere? int main() { while(*d) printf(fmt, arg); }
- shawnz 6y agoOn line 57: https://github.com/carlini/printf-tac-toe/blob/master/printtt.c#L57 https://github.com/carlini/printf-tac-toe/blob/master/printt...
- quietbritishjim 6y agoAh, well spotted, thanks. I didn't think it was fair to call the title click bait just because it used a while loop to drive the calls to printf, but also including a scanf call is definitely not in the same spirit.
- tikej 6y agoLooks a bit like scientific codes from 3 decades ago :)
- mci 6y agoI am afraid that the author has disqualified himself by publishing the source code before the judging of IOCCC 2020 is over. See catch 22 in the rules: "The judges STRONGLY prefer to not know who is submitting entries to the IOCCC."[1] Even the winners are asked not to publish the code until it is available on the IOCCC web site.[2] [1] https://ioccc.org/2020/rules.txt https://ioccc.org/2020/rules.txt [2] Personal communication
- Luc 6y ago‘Strongly prefer‘ != disqualification
- andi999 6y ago'Strongly prefer'== banned for life
- lifthrasiir 6y agoIt is true that publishing the source code this early is risky, but submitting the code that has been already published is not prohibited by its own. My winning entry (2012/kang [1]) was in fact published independently and was even on HN [2]. I'm pretty sure that this is not the only occurrence, having seen some winning entries trending on Twitter before the public announcement. [1] https://www.ioccc.org/2012/kang/ https://www.ioccc.org/2012/kang/ [2] https://news.ycombinator.com/item?id=2748402 https://news.ycombinator.com/item?id=2748402
- mjburgess 6y agoRelevant talk on the motivation for printf-programming: https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/carlini#:~:text=Control%2DFlow%20Bending%3A%20On%20the%20Effectiveness%20of%20Control%2DFlow%20Integrity,-Authors%3A&text=Control%2DFlow%20Integrity%20(CFI),is%20believed%20to%20be%20secure https://www.usenix.org/conference/usenixsecurity15/technical.... Very interesting. Roughly, that the existence of Turing-complete functions within programs creates a fundamental vulnerability that even rigid control over the control flow of a program cannot avoid.
- blunte 6y agoTitle correction: Tic Tac Toe written almost entirely in #defines.
- lukaszdk 6y agoThis is just crazy and I love it <3 From a description on the author's website[1] of a Doom clone written in 13k of JavaScript. > Until recently all content on this website was research, and while writing papers can be fun, sometimes you just need to blow off a little steam. I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis. [1] https://nicholas.carlini.com/ https://nicholas.carlini.com/
- learnstats2 6y ago>I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis. Maybe we could call this additional 'holiday pay' or a longer 'weekend' and mandate it through law so that everyone benefits.
- LoSboccacc 6y agoa law would be government overreach, but the idea is solid and the results tangibles; should be within the realm of a union regulations, if we ever manage to get one going.
- commandlinefan 6y agoHa, if I had a longer weekend my wife would demand I use it taking her out.
- learnstats2 6y agoDo you not like spending time with your wife? That seems a shame.
- DaiPlusPlus 6y ago> I think more companies should allow for their employees to have some plain old fun with no strings attached on a regular basis. Nicholas Carlini's resume is crazy-insane and he's highly desirable, so of course Google Brain is going to lend him far more flexibility than Google Analytics would have with a recent college-hire, or at the other end of the supply/demand distribution: the working flexibility Amazon would afford a warehouse employee (if they aren't a contractor...).
- yitchelle 6y agoLove the attempt the blindside the reader with funky formatting showing "%N".
- TapamN 6y agoThat's not too unusual for IOCCC entries. Of the top of my head, there's a flight simulator shaped like an airplane, and an addition routine shaped like a full-adder. A more subtle touch is that the #defines spell out NOUGHTs AnD CRoSSES.
- codegladiator 6y ago> in a single call to printf > while(*d) printf(fmt, arg) How's that a single call ?
- usr1106 6y ago> How's that a single call syntactically it is. But it's not a very clear description. So how would you describe that single call location getting executed in a loop so everybody understands what is really meant? A single line of code is worse.
- RoutinePlayer 6y ago"a call to printf in a while loop"
- lelf 6y agoprintf once in a while
- zeroimpl 6y agoIt also turns out “arg” is a macro which calls scanf. Would be better if they described it more realistically.
- yenwodyah 6y agoIt isn't really a "single call" to printf if it's in a while loop, is it?
- phire 6y agoThat's what you are getting hung up over? There is a call to scanf in the middle of the arg #define
- eternauta3k 6y agoI was expecting the tic-tac-toe to be written in machine code in an array, and printf would smash the stack to jump to it.
- simias 6y agoOddly enough I find that the #define macro soup detracts from the performance here. I was rather unimpressed at first because obfuscating C code by just #define'ing a bunch of code is a trivial and rather uninteresting way to write unreadable code. Of course you can make any arbitrary code look like a printf call with enough macros! But it's actually a lot more clever than that. I feel like this would be a lot more impressive if it was written in simple and clear C since then you'd see that there really isn't any tic-tac-toe logic being explicitly implemented the way you'd expect.
- russfink 6y agoOne time, I had to maintain C code That somebody had #define'd to look like FORTRAN. It was impressive.
- simias 6y agoI've had to deal with code like that, only poorly mimicking Lisp instead: `#define unless(_x) if (!(_x))` etc... One of my favourite accidental features in Rust is that macros are so annoying and cryptic to write that people think twice before abusing them.
- Gene_Parmesan 6y agoWouldn't be surprised if that was intentional, actually. The idea of making syntax a little unwieldy for things that you should really think twice before using is not a new one.
- TeMPOraL 6y agoI understand the temptation. I keep catching myself on writing `unless( ... )` in C++ every couple days, and I've considered adding a macro for it, but ultimately decided against it, as the rest of the team would not understand why I need it.
- codezero 6y agoOne time, I had to maintain FORTRAN code. Much of it was still in FORTRAN 66.
- techbio 6y agoI’m impressed with the aesthetics, and humor: formatted ‘fmt’, “printf oriented programming”... Suggests in my mind, somehow, thought I’d share: “CTRL-F oriented programming” :)
- phkahler 6y agoI thought the program was going to consist of only the call to printf(). But alas, that is inside a while loop.
- williesleg 6y agoMeh.
- rosstex 6y agoIf you're reading these Nicholas, thanks for your super help in CS 161 Spring 2016!
- staycoolboy 6y agoExcellent obfuscation. It ticks all the boxes: - esoteric modes of operation of a common function - truly novel use of macros - visibly beautiful
- anta40 6y agottt.c(25): fatal error C1091: compiler limit: string exceeds 65535 bytes in length Aaargghhh MSVC 2019 doesn't like this :(
- haberman 6y agoIn case you're wondering (like me) how you'd get input from printf(): > We ab^H^Huse [the Turing-completeness of printf()] to implement a the logic of tic-tac-toe entirely within this one printf call (and a call to scanf() to read user input). So it should be "one printf() and one scanf()."
- sfoley 6y agoShould be "an infinite number of printf()s and scanf()s".
- identity0 6y agoWould you say that an infinite loop has infinite lines of code?
- yjftsjthsd-h 6y agoIt has infinite instructions, yes. (Well, "unbounded" or "endless", if we're being picky.)
- identity0 6y agoNo it doesn’t. It has finite instructions for the loop body, and then one jump instruction for the loop.
- selimnairb 6y agoI am jealous of people who have time to do things like this.
- thr0w__4w4y 6y agoI hear you on that. But for me, the jealousy dissipates quickly once I realize that even if I had /lots/ of time, I don't think I would come up with this.
- hebetude 6y agofake news, single call to while
- peter_d_sherman 6y agoHoly Crap Batman! Never in a million years would I have thought that printf() was Turing-Complete -- and yet, here's the proof that it is... And then there's this related paper: https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-carlini.pdf https://www.usenix.org/system/files/conference/usenixsecurit... Page 175: "Printf is Turing-complete"