151

I've found C code that prints from 1 to 1000 without loops or conditionals : But I don't understand how it works. Can anyone go through the code and explain each line?

#include <stdio.h>
#include <stdlib.h>

void main(int j) {
  printf("%d\n", j);
  (&main + (&exit - &main)*(j/1000))(j+1);
}
Community
  • 1
  • 1
ob_dev
  • 2,808
  • 1
  • 20
  • 26
  • 1
    Are you compiling as C or as C++? What errors do you see? You cannot call `main` in C++. – ninjalj Oct 29 '11 at 10:05
  • @ninjalj I have created a C++ project and copy/past the code the error are : illegal, left operand has type 'void (__cdecl *)(int)' and expression must be a pointer to a complete object type – ob_dev Oct 29 '11 at 10:15
  • 1
    @ninjalj These code is working on ideone.org but not in visual studio http://ideone.com/MtJ1M – ob_dev Oct 29 '11 at 10:27
  • @oussama Similar, but slightly _more_ difficult to understand: http://ideone.com/2ItXm You're welcome. :) – Mark Oct 29 '11 at 12:30
  • @Mark good one ,but i don't get the use of # in the first define – ob_dev Oct 29 '11 at 12:59
  • `##` tells the preprocessor to join the things on either side. If I had used `#define MACRONAME blah` and then wrote `somethingMACRONAME`, the preprocessor wouldn't substitute `blah` for `MACRONAME`. However, `something##MACRONAME` would become `somethingblah`. It's explained in more detail under _Advanced Macro Tricks_ at http://www.cprogramming.com/tutorial/cpreprocessor.html – Mark Oct 29 '11 at 13:51
  • The mark of any good recursive function is how shallow it stays, and this is as far from good as you can get. – CyberSkull Oct 29 '11 at 14:23
  • 2
    i have removed all '&' characters from these line (&main + (&exit - &main)*(j/1000))(j+1); and this code still works. – ob_dev Oct 30 '11 at 16:57
  • Do `./prog 2` to have it start with 2 ;-) – Déjà vu Jan 10 '13 at 14:48
  • @obounaim if you haven't already figured this out that is because `&`'s are optional in function pointers – aaronman Jun 08 '13 at 14:58
  • `main + (exit - main)` works because function name is also a function pointer itself. You can even add any number of `*`s to the pointer and it still works: `*main + (*exit - *main)`, `**main + (**exit - **main)`... – phuclv Jul 21 '15 at 10:07

3 Answers3

267

Don't ever write code like that.

For j<1000, j/1000 is zero (integer division). So:

(&main + (&exit - &main)*(j/1000))(j+1);

is equivalent to:

(&main + (&exit - &main)*0)(j+1);

Which is:

(&main)(j+1);

Which calls main with j+1.

If j == 1000, then the same lines comes out as:

(&main + (&exit - &main)*1)(j+1);

Which boils down to

(&exit)(j+1);

Which is exit(j+1) and leaves the program.

(&exit)(j+1) and exit(j+1) are essentially the same thing - quoting C99 §6.3.2.1/4:

A function designator is an expression that has function type. Except when it is the operand of the sizeof operator or the unary & operator, a function designator with type "function returning type" is converted to an expression that has type "pointer to function returning type".

exit is a function designator. Even without the unary & address-of operator, it is treated as a pointer to function. (The & just makes it explicit.)

And function calls are described in §6.5.2.2/1 and following:

The expression that denotes the called function shall have type pointer to function returning void or returning an object type other than an array type.

So exit(j+1) works because of the automatic conversion of the function type to a pointer-to-function type, and (&exit)(j+1) works as well with an explicit conversion to a pointer-to-function type.

That being said, the above code is not conforming (main takes either two arguments or none at all), and &exit - &main is, I believe, undefined according to §6.5.6/9:

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; ...

The addition (&main + ...) would be valid in itself, and could be used, if the quantity added was zero, since §6.5.6/7 says:

For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

So adding zero to &main would be ok (but not much use).

Mat
  • 202,337
  • 40
  • 393
  • 406
  • @Mat i don't get it how to call a function with & – ob_dev Oct 29 '11 at 08:53
  • 4
    `foo(arg)` and `(&foo)(arg)` are equivalent, they call foo with argument arg. http://www.newty.de/fpt/fpt.html is an interesting page about function pointers. – Mat Oct 29 '11 at 08:57
  • @Krishnabhadra: it's documented in the standards, and it doesn't happen always. For C, it doesn't happen when used in `sizeof` or unary `&`, and for arrays it also doesn't happen when the array is a string literal used to initialize an array (e.g: `char foo[] = "foo"`). – ninjalj Oct 29 '11 at 10:03
  • @ninjalj sorry but char foo[] = "foo" is string literal? What about char *foo = "foo" – Krishnabhadra Oct 29 '11 at 10:07
  • @Krishnabhadra: `"foo"` is a string literal of type array of char. `char *foo="foo"` has a string literal of type array that gets converted to a pointer to initialize a `char *` variable. – ninjalj Oct 29 '11 at 10:14
  • Anyway I wrote a program like this #include int main(){ char *foo = "foo"; printf("%u \n%u \n",foo, &foo); } then I got different result as output.. – Krishnabhadra Oct 29 '11 at 10:15
  • But when I wrote #include int main(){ char foo[] = "foo"; printf("%u \n%u \n",foo, &foo); } I got both values equal... – Krishnabhadra Oct 29 '11 at 10:16
  • 1
    @Krishnabhadra: in the first case, `foo` is a pointer, `&foo` is the address of that pointer. In the second case, `foo` is an array, and `&foo` is equivalent to foo. – Mat Oct 29 '11 at 10:20
  • 9
    Unnecessarily complex, at least for C99: `((void(*[])()){main, exit})[j / 1000](j + 1);` – Per Johansson Oct 29 '11 at 10:22
  • hmm got that part, but why you said *and for arrays it also doesn't happen when the array is a string literal used to initialize an array (e.g: char foo[] = "foo").*? – Krishnabhadra Oct 29 '11 at 10:23
  • 1
    `&foo` is not the same as `foo` when it comes to an array. `&foo` is a pointer to the array, `foo` is a pointer to the first element. They do have the same value though. For functions, `fun` and `&fun` are both pointers to the function. – Per Johansson Oct 29 '11 at 10:31
  • @Krishnabhadra: in the `char foo[] = "foo"` case, `foo` gets initialized with _the array_. – ninjalj Oct 29 '11 at 10:31
  • Got that, but what I didn't understand is why you said in this case array name **does not** give array base address? When I print printf("%u",foo); returning the starting address of array..When I print with %s specifier it prints the entire array..So I think you can use array name to get array base address..Thats why I am able to say **char *ptr = foo;** so that pointer will be initialized with the address of the array.. – Krishnabhadra Oct 29 '11 at 10:42
  • @Krishnabhadra: err, `char *foo="1234567890"` is a pointer-sized variable that points to an array that is probably in the `.rodata` section. `char foo[] = "1234567890"` is a 11-byte-sized variable. I see where your confusion comes from. `"1234567890"` is also an array. – ninjalj Oct 29 '11 at 10:49
  • *char *foo="1234567890" is a pointer-sized variable that points to an array that is probably in the .rodata section* 100 percent agree...I have nothing to say about this one.. – Krishnabhadra Oct 29 '11 at 10:57
  • *"1234567890" is also an array* hmm..you are right..this part is what confusing me...Ok leave it..This has been going on for too long, on a thread which has its own question and answers...Thanks for your time...I have to read that part of my C book again... – Krishnabhadra Oct 29 '11 at 10:59
  • 1
    FYI, if you look at [the relevant answer to the other question cited above](http://stackoverflow.com/questions/4568645/printing-1-to-1000-without-loop-or-conditionals/4583502#4583502), you'll see there's a variation that is in fact comformant C99. Scary, but true. – Daniel Pryden Oct 30 '11 at 06:01
  • My mind needs clarification - what if I have args? J will start as not 0 and so this will run for less then 1000 iterations, right? – Mikle Nov 01 '11 at 21:32
  • @Mikle: yes, if you pass in arguments, it won't start at 1. (Note: without args, it would start at 1, not 0, on most implementations - the name of the program itself is passed as the first (zero'eth) element of argv.) But since the `main` declaration, as it is, is not standard (an implementation could make if valid though), YMMV. – Mat Nov 01 '11 at 21:40
  • @PerJohansson casting a function pointer to a different type, then calling through that pointer, causes undefined behaviour – M.M Jun 17 '15 at 13:53
  • @MattMcNabb the types are compatible. But I agree, it would have been more correct to use `(void(*[])(int))`. – Per Johansson Jun 18 '15 at 08:30
41

It uses recursion, pointer arithmetic, and exploits the rounding behavior of integer division.

The j/1000 term rounds down to 0 for all j < 1000; once j reaches 1000, it evaluates to 1.

Now if you have a + (b - a) * n, where n is either 0 or 1, you end up with a if n == 0, and b if n == 1. Using &main (the address of main()) and &exit for a and b, the term (&main + (&exit - &main) * (j/1000)) returns &main when j is below 1000, &exit otherwise. The resulting function pointer is then fed the argument j+1.

This whole construct results in recursive behavior: while j is below 1000, main calls itself recursively; when j reaches 1000, it calls exit instead, making the program exit with exit code 1001 (which is kind of dirty, but works).

r0estir0bbe
  • 699
  • 2
  • 7
  • 23
tdammers
  • 20,353
  • 1
  • 39
  • 56
  • 1
    Good answer, but one doubt..How main exit with exit code 1001? Main is not returning anything..Any default return value? – Krishnabhadra Oct 29 '11 at 09:30
  • 2
    When j reaches 1000, main doesn't recurse into itself anymore; instead, it calls the libc function `exit`, which takes the exit code as its argument and, well, exits the current process. At that point, j is 1000, so j+1 equals 1001, which becomes the exit code. – tdammers Oct 29 '11 at 09:33
  • Actually the exit code will be 233 (1001 % 256 or 1001 & 255). – U. Windl May 27 '21 at 12:20
0

https://stackoverflow.com/a/7937813/6607497 explains it all, but for the impatient here is the equivalent (readable) code:

#include <stdio.h>
#include <stdlib.h>
    
void main(int j) {
    printf("%d\n", j);
    if (i/1000 == 0)
        main(j+1);
    else
        exit(j+1);
}

So i guess its obvious how it works. The only real trick being used is the "computed goto" (&main + (&exit - &main)*(j/1000)), evaluating to either main while j/1000 is zero, or exit otherwise (actually if it's 1).

Maybe also note that the program is misusing argc as j, so it will count differently when you pass arguments to the program, and it will most likely crash when you add more than 2000 parameters...

U. Windl
  • 3,480
  • 26
  • 54