Clever Code Puzzle

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

User avatar
Infernalis
Posts: 68
Joined: Mon Nov 10, 2008 10:13 pm UTC
Location: Cube farm

Clever Code Puzzle

Postby Infernalis » Tue Sep 20, 2011 5:37 pm UTC

I don't know if anyone has ever seen this before but my proffessor mentioned it in class and I thought it was clever so I thought I'd share. I'll post what it does later on, spoilers are no fun and I'm curious what people will think. So without any further ado, follow the bahavior of the loop (assuming the implementation is in C).

Code: Select all

int a[10], i;

for (i = 0; i <= 10; i++)
{
     a[i] = 0;
}


*edit* Fixed commas, whoops!
Last edited by Infernalis on Wed Sep 21, 2011 1:30 pm UTC, edited 1 time in total.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Clever Code Puzzle

Postby EvanED » Tue Sep 20, 2011 5:41 pm UTC

Invokes undefined behavior? :-)

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Clever Code Puzzle

Postby Xanthir » Tue Sep 20, 2011 5:42 pm UTC

I assume that it relies on undefined behavior, specially the placement of i directly after the last element of a in memory. It then infinite loops, as the last round (when i=10) resets i to 0.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
Quyzi
Posts: 1
Joined: Wed Jun 29, 2011 4:03 pm UTC

Re: Clever Code Puzzle

Postby Quyzi » Tue Sep 20, 2011 5:46 pm UTC

Wouldn't it crash when it tried to access a[10]?

Laguana
Posts: 49
Joined: Sat Jan 19, 2008 10:13 pm UTC

Re: Clever Code Puzzle

Postby Laguana » Tue Sep 20, 2011 11:14 pm UTC

Alternate answer: It doesn't compile, since commas rather than semicolons were used in the for loop.

[edit] I should probably say, I thought there was going to be some cute trick relying on that that I wasn't aware of; like the loop never executes or something and just does the initialisation step. But no, it just doesn't compile as-stated.

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Clever Code Puzzle

Postby Dason » Wed Sep 21, 2011 12:31 am UTC

Ignoring the comma instead of semi-colon issue I think what the OP was trying to get at is what Xanthir mentioned. It becomes an infinite loop since a only goes up to a[9] so when you access a[10] on the last run of the loop you're actually accessing i (possibly... it's undefined).
double epsilon = -.0000001;

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Clever Code Puzzle

Postby letterX » Wed Sep 21, 2011 12:54 am UTC

Yeah. Try compiling with -O3 (for gcc anyways), and it goes back to doing absolutely nothing, with no infinite loop.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Clever Code Puzzle

Postby You, sir, name? » Wed Sep 21, 2011 12:14 pm UTC

Several distinct possibilities:

a and i are placed sequentially in memory: Infinite loop.
a and i are not placed sequentially in memory: goto Possible Stack Smash
i is optimized into a register variable: goto Possible Stack Smash
the loop gets unrolled: goto Possible Stack Smash

Possible Stack Smash: The program either crashes, or nothing visible happens, depending on whether the system detects the stack smash and in which direction the stack grows.
Last edited by You, sir, name? on Wed Sep 21, 2011 2:12 pm UTC, edited 1 time in total.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
Infernalis
Posts: 68
Joined: Mon Nov 10, 2008 10:13 pm UTC
Location: Cube farm

Re: Clever Code Puzzle

Postby Infernalis » Wed Sep 21, 2011 1:32 pm UTC

Xanthir wrote:I assume that it relies on undefined behavior, specially the placement of i directly after the last element of a in memory. It then infinite loops, as the last round (when i=10) resets i to 0.


+1 internets for you, sir.

It goes without question that using anything like this in pracice would be suicide, but I can't help but wonder how reliable this undefined behavior can be. It sems intuitive that in the vast majority of cases i will be stored immediately after a[9]...

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Clever Code Puzzle

Postby EvanED » Wed Sep 21, 2011 2:23 pm UTC

Infernalis wrote:
Xanthir wrote:I assume that it relies on undefined behavior, specially the placement of i directly after the last element of a in memory. It then infinite loops, as the last round (when i=10) resets i to 0.


+1 internets for you, sir.

It goes without question that using anything like this in pracice would be suicide, but I can't help but wonder how reliable this undefined behavior can be. It sems intuitive that in the vast majority of cases i will be stored immediately after a[9]...

Depends on how the rest of the code goes. As letterX says, with -O2, GCC optimizes away the entire loop:

Code: Select all

.globl main
        .type   main, @function
main:
.LFB2:
        xorl    %eax, %eax
        ret


If I add some additional code to prevent that degree of optimization:

Code: Select all

int main()
{
    int a[10], i, sum;

    for (i = 0; i <= 10; i++){
         a[i] = 0;
    }

    for (i = 0; i<=9; i++) {
        sum += a[i];
    }
    return sum;
}

then it still puts i in a register. In other words, i doesn't have a memory address for the out-of-bounds array access to overwrite:

Code: Select all

.globl main
        .type   main, @function
main:
.LFB2:
        leaq    -56(%rsp), %rcx
        xorl    %eax, %eax
        .p2align 4,,7
.L2:
        movl    $0, (%rcx,%rax,4)
        addq    $1, %rax
        cmpq    $11, %rax
        jne     .L2
        xorl    %edx, %edx
        .p2align 4,,7
.L4:
        addl    (%rcx,%rdx,4), %eax
        addq    $1, %rdx
        cmpq    $10, %rdx
        jne     .L4
        rep ; ret

(Note that rax is holding i in both loops. Edit: No. rax has it during the first loop, and rdx in the second.)

So in other words it's very realistic that that behavior is not reliable.

User avatar
cemper93
Posts: 209
Joined: Sun Feb 20, 2011 2:35 pm UTC
Location: `pwd`

Re: Clever Code Puzzle

Postby cemper93 » Wed Sep 21, 2011 7:58 pm UTC

But what would happen if you used volatile? (I have no compiler here for testing.) It should at least always execute the loop, as it would expect weird stuff to happen to i. OTOH, it does still not ensure that &(a[10]) == &i.

Divinas
Posts: 57
Joined: Wed Aug 26, 2009 7:04 am UTC

Re: Clever Code Puzzle

Postby Divinas » Thu Sep 22, 2011 9:13 am UTC

If for some reason you really want that to work reliably, put i and a in a struct as members, and you'll get the behavior you're looking for.
ps. Don't do that, really.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Clever Code Puzzle

Postby jaap » Thu Sep 22, 2011 9:56 am UTC

Divinas wrote:If for some reason you really want that to work reliably, put i and a in a struct as members, and you'll get the behavior you're looking for.
ps. Don't do that, really.

Not necessarily as there may be padding between struct members.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Clever Code Puzzle

Postby PM 2Ring » Thu Sep 22, 2011 12:24 pm UTC

Relying on undefined behaviour in code is evil; by comparison, the use of goto is positively benign.

The only (sane) reason for learning about tricks like this one is so that you learn to never ever do it in real code, and if it accidentally happens due to an indexing error you'll be aware of the symptoms of this kind of bug.

Goplat
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: Clever Code Puzzle

Postby Goplat » Thu Sep 22, 2011 8:16 pm UTC

jaap wrote:
Divinas wrote:If for some reason you really want that to work reliably, put i and a in a struct as members, and you'll get the behavior you're looking for.
ps. Don't do that, really.

Not necessarily as there may be padding between struct members.

Fun fact: with a struct { int a[10], i } variable, even though no compiler in the world would ever put padding between a and i, it's still undefined behavior to access a[10] (pointer arithmetic is only defined for moving between elements of an array, not members of a struct), and if the struct is a local variable then the gcc optimizer assumes that assignment to a[10] does not modify i. So much for common sense.

Turtlewing
Posts: 236
Joined: Tue Nov 03, 2009 5:22 pm UTC

Re: Clever Code Puzzle

Postby Turtlewing » Thu Sep 22, 2011 8:49 pm UTC

You could probably get it to relyably access i, if i were deffined differently (pointers would do the trick), but that would probably ruin the obfuscation.

forgive the syntax, it's been forever since I did anything with C so I probably borked a de-reference or something at least once, but something like this should reliably begin an infinite loop.

Code: Select all

int a[11];
int *i = &a[10]; // this is the annoying line because it gives away the surprise
for(*i=0; *i<=10; *i++)
{
   a[*i]=0;
}

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Clever Code Puzzle

Postby EvanED » Thu Sep 22, 2011 9:29 pm UTC

Turtlewing wrote:You could probably get it to relyably access i, if i were deffined differently (pointers would do the trick), but that would probably ruin the obfuscation.

forgive the syntax, it's been forever since I did anything with C so I probably borked a de-reference or something at least once, but something like this should reliably begin an infinite loop.

Code: Select all

int a[11];
int *i = &a[10]; // this is the annoying line because it gives away the surprise
for(*i=0; *i<=10; *i++)
{
   a[*i]=0;
}

Yes, that works. If you have C++ you can make it slightly more obscure:

Code: Select all

int a[11];
int &i = a[10]; // this is the annoying line because it gives away the surprise
for(i=0; i<=10; i++)
{
   a[i]=0;
}


You still have the "surprise" line but at least all the *is are gone.

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Clever Code Puzzle

Postby Carnildo » Fri Sep 23, 2011 3:06 am UTC

Infernalis wrote:It goes without question that using anything like this in pracice would be suicide, but I can't help but wonder how reliable this undefined behavior can be. It sems intuitive that in the vast majority of cases i will be stored immediately after a[9]...

See "Nasal Demons": it's perfectly legal for the compiler, upon encountering that construct, to drain your bank account and run off to Bermuda.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 10 guests