Sunday, October 09, 2011

How geeky am I

These days, we have both 1080p hidef television, and plotlines with hackers. That means "code" appears frequently on the screen. Of course, if you read the code, it has nothing to do with the plot. The producers just grabbed a fragment off the net and stuck it in there for dramatization.

In the pilot episode of the remake of Charlie's Angels, one of the gals cracks an electronic safe by typing in a fragment of code. Here is a picture from the video:

To a geek like me, two things jump out. The first is that this code includes a hard-coded random number generator (i=1103515245*i+12345&0x7fffffff)/2147483648.0). That's odd, why code your own instead of using the built-in random number generator known as "rand()"? That leads to the second observation: the code is deliberately obfuscated, possibly because it was an entry to the (now defunct) Obfuscated C contest.

Because of the obfuscation, it was difficult googling it, but I eventually found the source at this PasteBin link http://pastebin.com/ETeBXXGh. I copied it and listed it below. It's the only version of the code I could find. From the additional code, it appears probable that it's a generator/solver for Sudoku. I tried to run it, and didn't get any good results, because I don't know the data it expects. I could figure it out, but ...

...now I'm bored with it. I found the code, I know it's something to do with Sudoku, that it's obfuscated, but I no longer care to find out the rest.


Update: Bah! A malware analyst "ocean" found it https://twitter.com/#!/_ocean/status/122956436635529216 on the IOCCC website http://www.ioccc.org/2005/aidan/. It probably took him the extra 30 seconds I wasn't willing to spend, it's obvious.


Update: Check out Ian Eiloart's comment at the bottom. As he points out, Hollywood is a stickler for copyright. The Obfuscated C contest explicitly states that all submissions must be in the public domain. This makes it perfect for Hollywood: you get code fragments that both extremely geeky and for which you don't have to worry about a lawyer serving your papers. Note that there is a "fair use" clause that means they don't always have to worry anyway. For example, my use of the picture from the show above is covered under "fair use", so I can use it without having to ask for permission.




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

#define N(I,l) s l]=(I?1<<I|I<<10:01776)
#define f(a,t) for(a=0;a<t;a++)
#define Su(d,o,ku) O(l/9,d) O(l%9,o) O(l%9/3+l/27*3,ku)
#define NO ;printf("%c %s",I?I|48:46,++l%3?"":l%9?"| ":l%27?"\n":l%'Q'?z:"\n");
#define Ba(k,a) {O||printf("!!! " #a " %i\n",k+1);goto l;}
#define O(o,k) f(l,9) c[l]= *#k?0x3fe:-1;\
  f(l,81) if(*#k){\
    if(!(s]&c[o])) Ba(o,k) c[o]&=~(1<<(s]>>10));\
  } else if((s]>>l0)&1) c[o]=c[o]+1?-2:l;\
  if(*#k) { f(l,81) if(s]>>10||(s]&=c[o]),!s]) Ba(o,k) }\
  else f(l,9) l[c]<0||s[c]]>>10||(N(l0,[c]),C++);

struct{ int s[81],I,l,O; } S[0123];
int I, l, l0, o, C, O=0, w=0, c[10], L; long i;
char z[] = "\007      &       &      \n";

#define s S].s[l

int main(int n,char**N) {
    S->O=0; L=n>1?*N[1]-85?1:6:0; i=L&1?atol(N[1]):123;
#define i (int)(81.0*(i=1103515245*i+12345&0x7fffffff)/2147483648.0)
    for(l=C=0;l<81;) {
 I=L&1?0:getchar()^48; i; I=I-30?I:0;
 if(I<10) {
  #define S S[O
  if(C<22) z[C++]^=13; N(I,)NO
 }
    }

    for(;;) {
 l0:
        Su(row,col,box) C=l0=0;
 f(l,81) if(!(s]>>10&&++l0)) {
   o=s]&1022; for(I=0;~o&1&&(o/=2);I++); o-1||(s]|=I<<10,C++);
 } if(l0==l) {
   if(O&&L&2) { O--; goto l0; } goto O; 
 } for(l0=1;10>l0;l0++) { Su(,,) }

 if(!C) {
     l=(o=S].O)?S].I:0; I=o?S].l%9+1:(S].O=i%9+1);
     for(;l<81;l++,I=S].O,o=0) if(!(s]>>10)) {
  for(;;I=I%9+1,o=1) {
      l0=0; if(o&&I==S].O) goto O;
      if(s]>>I&1) {
   S].l=I; S++].I=l; S]=S-1];
   N(I,); O>w&&(w=O); goto lO;
      }
  }
     }
 }
 lO: S].O=0; goto l0; l: if(!(l0=O)) { L=0; goto O; } O--;
 s,S].I] &=~ (1<<S].l);
    }

    O: switch(L) {
 case 2: if(l0) {
 case 3: O=82;
     for(S].l=l=i%81;l0||S].l-l;l=(l+1)%81)
           O1: if(l0=0,S].O=s]>>10,~s]&1) {
  s]=1023; S].I=l; S&0]=S]; w=O=0; L=2; goto lO;
     }
     L=0; l0=1;
 } else {
     l=S=82].I; N(S].O,)|1; goto O1;
 }
    }

    printf("\n\n"); for(l=0;l<81;) {I=s]>>10 NO}
    printf("\n%s (stk %i %i)\n",l0?"Done":"No way!",O,w);
    L|=2; if(L-3||!l0) return!l0; S,82]=S]; goto O;
}

If you run it, and pass the source as the input "a.out < foo.c", you get the following output:

. . 1 | 1 . . | 1 7 7
6 . 9 | 9 9 3 | 2 7 3
4 8 4 | 6 3 9 | 2 7 1
------+-------+------
9 . 3 | 1 8 1 | 1 1 .
. 1 1 | 2 8 1 | 1 . 9
. 1 . | . 8 1 | . 1 2
------+-------+------
3 . . | . 1 . | . . 7
. . 1 | 1 8 5 | 1 6 .
1 1 1 | 2 3 8 | 1 . .
!!! row 1


. . 1 | 1 . . | 1 7 7
6 . 9 | 9 9 3 | 2 7 3
4 8 4 | 6 3 9 | 2 7 1
------+-------+------
9 . 3 | 1 8 1 | 1 1 .
. 1 1 | 2 8 1 | 1 . 9
. 1 . | . 8 1 | . 1 2
------+-------+------
3 . . | . 1 . | . . 7
. . 1 | 1 8 5 | 1 6 .
1 1 1 | 2 3 8 | 1 . .

No way! (stk 0 0)

3 comments:

Unknown said...

I guess they used this because it's in the public domain. Movie companies are pretty tight about that sort of thing. I got contacted by the producers of Madagascar when they realised the animators had used a map of the Madagascar channel that I'd posted on the web. I didn't own the copyright, and I think they changed that scene.

birogeri said...

I have captured some of these on-screen codes, but none of them makes too much sense. First is from Unthinkable, and they are disarming a nuke: https://twitpic.com/27j8qj

The second one is from The Tournament, they enhance the satellite video (yes, the faces are captured from a satellite - even if they are in a building) with HTML! https://twitpic.com/1x2l0c

An IOCCC Judge said...

The IOCCC is not defunct! It may still alive! The 20th IOCCC finished in January 2012.