Nogle børn ønsker sig så mange gaver, at nisserne nogle gange må være kreative og lave to stykker legetøj i ét! Det kræver snedighed og nogle gange beskidte tricks.

Hvad det har at gøre med denne opgave, det ved vi ikke, men det var vigtigt at fortælle!

Til denne opgave er vi givet en 5,6 mb stor C fil med 132.631 linjer i. Åbner man filen vil man spotte at næsten alle de første 132.630 er #defines og den sidste linje kalder nogle af disse makroer. Til den slags er det altid et godt første skridt at køre en C præprocessor over filen og se om det giver noget:

$ gcc -E christmas_even.c
# 0 "christmas_even.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "christmas_even.c"
# 132631 "christmas_even.c"
int puts ( const char * ) ; int main ( ) { puts ( " " " " " " " " "*" "\n" " " " " " " " " "A" "\n" " " " " " " "/" "." "\\" "\n" " " " " "/" "." "." "." "\\" "\n" " " " " "/" "." "." "." "\\" "\n" " " "/" "." "." "." "." "." "\\" "\n" " " "/" "." "." "." "." "." "\\" "\n" "/" "." "." "." "." "." "." "." "\\" "\n" "^" "^" "^" "[" "_" "]" "^" "^" "^" ) ; return 0 ; }

Rydder man lidt op i dette program så er det bare:

int puts(const char *);

int main() {
    puts("    *\n"
         "    A\n"
         "   /.\\\n"
         "  /...\\\n"
         "  /...\\\n"
         " /.....\\\n"
         " /.....\\\n"
         "/.......\\\n"
         "^^^[_]^^^");
    return 0;
}

Altså er det bare et simpelt print af et juletræ og så slutter programmet. Compiler og kører vi programmet så kan vi bekræfte dette:

$ gcc christmas_even.c -o christmas_even && ./christmas_even
    *
    A
   /.\
  /...\
  /...\
 /.....\
 /.....\
/.......\
^^^[_]^^^

Så selve programmet får vi ikke meget sjov ud af, så lad os kigge på makro kaldene.

Makro kald

I bunden af C finder vi den ene linje

O11I1Il1(olIII1l1(o1I1lI1l)) O11I1Il1(olIII1l1(O1lI11Il)) O11I1Il1(olIII1l1(o1ll1Il1)) O11I1Il1(olIII1l1(O1llllI1)) O11I1Il1(olIII1l1(Ol1IIlIl)) O11I1Il1(olIII1l1(ol11lIll)) O11I1Il1(olIII1l1(oI111lI1)) O11I1Il1(olIII1l1(o11I1I11)) O11I1Il1(olIII1l1(OlIIIIlI)) O11I1Il1(olIII1l1(O1I1Il11)) O11I1Il1(olIII1l1(oIIIl111)) O11I1Il1(olIII1l1(o11111I1)) O11I1Il1(olIII1l1(OlIIIlIl)) O11I1Il1(olIII1l1(oIl111l1)) O11I1Il1(olIII1l1(OI1ll1lI)) O11I1Il1(olIII1l1(oII1I1I1)) O11I1Il1(olIII1l1(oI1IlI11)) O11I1Il1(olIII1l1(oll1II1l)) O11I1Il1(olIII1l1(ol1II1lI)) O11I1Il1(olIII1l1(oIIll111)) O11I1Il1(olIII1l1(O111IlI1)) O11I1Il1(olIII1l1(ollIIl11)) O11I1Il1(olIII1l1(OlI11lI1)) O11I1Il1(olIII1l1(Oll1lIll)) O11I1Il1(olIII1l1(OI1lll1l)) O11I1Il1(olIII1l1(ol1I1111)) O11I1Il1(olIII1l1(o1IIlIl1)) O11I1Il1(olIII1l1(oIII11lI)) O11I1Il1(olIII1l1(OllI1l11)) O11I1Il1(olIII1l1(OI1lIII1)) O11I1Il1(olIII1l1(o111I1Il)) O11I1Il1(olIII1l1(olII1IIl)) O11I1Il1(olIII1l1(OlIIII11)) O11I1Il1(olIII1l1(oIIIl1I1)) O11I1Il1(olIII1l1(oI1IIlIl)) O11I1Il1(olIII1l1(OIl11Il1)) O11I1Il1(olIII1l1(Oll111ll)) O11I1Il1(olIII1l1(OIIIll1I)) O11I1Il1(olIII1l1(OIllIIII)) O11I1Il1(olIII1l1(OI11lIlI)) O11I1Il1(olIII1l1(OI11lI11)) O11I1Il1(olIII1l1(olIIlII1)) O11I1Il1(olIII1l1(Ol11Illl)) O11I1Il1(olIII1l1(o1Il1I1I)) O11I1Il1(olIII1l1(O11II11l)) O11I1Il1(olIII1l1(OlIll1I1)) O11I1Il1(olIII1l1(ol11lIII)) O11I1Il1(olIII1l1(o11ll11l)) O11I1Il1(olIII1l1(oI1Il11I)) O11I1Il1(olIII1l1(OIllII1I)) O11I1Il1(olIII1l1(OIIIIlIl)) O11I1Il1(olIII1l1(OI1lllII)) O11I1Il1(olIII1l1(O1IlIIl1)) O11I1Il1(olIII1l1(o11llIII)) O11I1Il1(olIII1l1(oI1lIII1)) O11I1Il1(olIII1l1(o1Il1IlI)) O11I1Il1(olIII1l1(O1l11111)) O11I1Il1(olIII1l1(oll1IlIl)) O11I1Il1(olIII1l1(oI1IIll1)) O11I1Il1(olIII1l1(Olllllll)) O11I1Il1(olIII1l1(OIIIlIl1)) O11I1Il1(olIII1l1(o1IIIII1)) O11I1Il1(olIII1l1(o1I1l1Il)) O11I1Il1(olIII1l1(O1Il1II1)) O11I1Il1(olIII1l1(o1lll11I)) O11I1Il1(olIII1l1(OIIIlIlI)) O11I1Il1(olIII1l1(O1I1lllI)) O11I1Il1(olIII1l1(olI11lIl)) O11I1Il1(olIII1l1(OlIllIIl)) O11I1Il1(olIII1l1(o11III11)) O11I1Il1(olIII1l1(o1lI1Il1)) O11I1Il1(olIII1l1(Ol1lIlIl)) O11I1Il1(olIII1l1(O11lllI1)) O11I1Il1(olIII1l1(oIIIlI11)) O11I1Il1(olIII1l1(oI11I1ll)) O11I1Il1(olIII1l1(OIl1IIIl)) O11I1Il1(olIII1l1(OIll1lII)) O11I1Il1(olIII1l1(olI11IIl)) O11I1Il1(olIII1l1(O11Il1l1)) O11I1Il1(olIII1l1(o1l1IIIl)) O11I1Il1(olIII1l1(o111Illl)) O11I1Il1(olIII1l1(O1l1Il11)) O11I1Il1(olIII1l1(o11lI1ll)) O11I1Il1(olIII1l1(OlIl1Ill)) O11I1Il1(olIII1l1(o11IIII1)) O11I1Il1(olIII1l1(O1l1I1Il)) O11I1Il1(olIII1l1(OI11llII)) O11I1Il1(olIII1l1(oIIIll1I)) O11I1Il1(olIII1l1(oll1l1ll)) O11I1Il1(olIII1l1(O1IlI11I)) O11I1Il1(olIII1l1(OI11l1ll)) O11I1Il1(olIII1l1(Ol1l1I1l)) O11I1Il1(olIII1l1(OIlI1l1l))

Givet at alt andet i filen er enten blanke linjer eller #defines må dette være linjen der faktisk samler programmet til sidst. Hvis vi fordeler alle disse kald ud på hver deres linje, så kan vi måske få en idé om, hvad disse gør:

O11I1Il1(olIII1l1(o1I1lI1l))
O11I1Il1(olIII1l1(O1lI11Il))
O11I1Il1(olIII1l1(o1ll1Il1))
O11I1Il1(olIII1l1(O1llllI1))
O11I1Il1(olIII1l1(Ol1IIlIl))
O11I1Il1(olIII1l1(ol11lIll))
...
O11I1Il1(olIII1l1(OIlI1l1l))

Hvilket giver:

$ gcc -E christmas_even-with-nl.c
# 0 "christmas_even-with-nl.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "christmas_even-with-nl.c"
# 132631 "christmas_even-with-nl.c"
int
puts
(
const
char
*
...
}

Det er rimeligt klart her, at hvert kald til makroerne resulterer i en enkelt C token. En mere subtil detalje, der også kan opdages her er, at forskellige kald til makroerne godt kan resultere i samme token. F.eks giver begge de to følgende makro kald ; som resultat

O11I1Il1(olIII1l1(oll1l1ll))
O11I1Il1(olIII1l1(Ol1l1I1l))

Tæller man antallet af tokens der bliver genereret, så får man 93:

$ gcc -E christmas_even-with-nl.c | grep -v '^#' | wc -l
93

En sidste ting, der er værd at spotte er, at alle tokens bliver genereret med de samme to nestede makroer og så blot en forskellig parameter inderst. Så det næste vi kan gøre er at pille disse makroer fra hinanden, startende yderst.

O11I1Il1 makroen

Leder vi efter O11I1Il1 så finder vi følgende:

$ grep '#define O11I1Il1' christmas_even.c
#define O11I1Il1(OII) OII1l11I(OII)

Altså er dette blot en wrapper rundt om en anden makro. Lad os gå videre til den:

$ grep '#define OII1l11I' christmas_even.c
#define OII1l11I(ol1) o1Il1III##ol1

Denne giver os lidt mere at gå efter. ## er C præprocessorens “token pasting” operator, dvs. den tager to tokens og sætter dem sammen til en, så f.eks. ab ## cd bliver én token abcd. Den nestede konstruktion, altså det at man får en makro til at kalde en anden makro, der så udfører pasting, er en typisk C konstruktion til at lade præprocessoren evaluere både argumenterne og resultatet af pasting operatoren.

Her ser vi konkret, at hvad end der gives som argument til O11I1Il1 bliver pasted sammen med o1Il1III og resultatet bliver så makro udvidet selv. Så et næste naturligt skridt er at se, hvilke makroer der eksisterer som starter med o1Il1III. Dem viser det sig der, er et par stykker af:

$ grep '#define o1Il1III' christmas_even.c | wc -l
257

Kigger vi lidt på disse, så optræder der et par typer af dem.

Type 1: De simple

To af makroerne er helt simple:

#define o1Il1IIIO1IIII11
#define o1Il1IIIO1l1l1lI " "

Det er blot en blank token og et quoted space.

Type 2: Enkelte tokens

Dernæst er der en gruppe af makroer som blot udvider til en anden makro:

#define o1Il1IIIO1II11l1 O1I1I1lI
#define o1Il1IIIo1l11I1l O1ll1lll
#define o1Il1IIIO1IIl111 o1I111lI
#define o1Il1IIIol1I1I1l OlllI1lI
#define o1Il1IIIolI11lIl O1IlllII
#define o1Il1IIIO1llll1l O1ll1lll
#define o1Il1IIIoIIIlI11 oI1l1lll
#define o1Il1IIIo1lI1Il1 oI1lIIll
#define o1Il1IIIol11I1lI O1I1I1lI
#define o1Il1IIIollIl1Il OlllI1lI
#define o1Il1IIIO1llIll1 o1Il1lII
#define o1Il1IIIollIlI1I oI1l1lll
#define o1Il1IIIoII1ll1l OlllI1lI

Følger man disse makroer finder man at disse blot er enkelte symboler:

#define o1I111lI ;
#define oI1l1lll 0
#define o1Il1lII {
#define OlllI1lI *
#define O1IlllII )
#define oI1lIIll ,
#define O1I1I1lI }
#define O1ll1lll (

Dette ligner mistænkeligt meget de symboler, der er brugt som tokens i det præprocesserede program, men det fører os til den første reduktion vi kan lave, og bare sige, denne anden gruppe af makroer er:

#define o1Il1IIIO1II11l1 }
#define o1Il1IIIo1l11I1l (
#define o1Il1IIIO1IIl111 ;
#define o1Il1IIIol1I1I1l *
#define o1Il1IIIolI11lIl )
#define o1Il1IIIO1llll1l (
#define o1Il1IIIoIIIlI11 0
#define o1Il1IIIo1lI1Il1 ,
#define o1Il1IIIol11I1lI }
#define o1Il1IIIollIl1Il *
#define o1Il1IIIO1llIll1 {
#define o1Il1IIIollIlI1I 0
#define o1Il1IIIoII1ll1l *

Type 3: Quoted tokens

Den næste gruppe af o1Il1III makroer er så

#define o1Il1IIIO1I111I1 OIl1Il1l(O11lIlll)
#define o1Il1IIIOlllllll OIl1Il1l(OI11IlIl)
#define o1Il1IIIol11111I OIl1Il1l(OlI1Il1l)
#define o1Il1IIIo11lIlII OIl1Il1l(oIll1l1I)
...
#define o1Il1IIIolIlllIl OIl1Il1l(OI11lIII)

Disse er kendetegnet ved at de alle kalder OIl1Il1l makroen:

#define OIl1Il1l(oII) O1lIIll1(oII)
#define O1lIIll1(OIl) #OIl

Igen ser vi denne nestede makro struktur til at tvinge evaluering af makroerne, denne gange bare med # operatoren, som er “Stringizing” operatoren. Den tager essentielt hvad end den er givet af parameter og sætter " omkring dem. Kigger vi på hvad det er der bliver sat " omkring, så ser vi:

#define O11lIlll o
#define OI11IlIl w
#define OlI1Il1l d
#define oIll1l1I e
...
#define OI11lIII 3

Altså er det enkelte symboler der bliver sat i ". Dette passer meget godt hvis vi tænker tilbage til juletræsprogrammet, hvor strengen til puts ikke var en samlet streng, men bestod af enkelte tegn i ". Noget interessant her er, at vi ser tegn, som ikke indgår i juletræsprogrammet, men som potentielt kan genereres af makroerne. Vi kan igen reducere disse makroer:

#define o1Il1IIIO1I111I1 "o"
#define o1Il1IIIOlllllll "w"
#define o1Il1IIIol11111I "d"
#define o1Il1IIIo11lIlII "e"
...
#define o1Il1IIIolIlllIl "3"

Type 4: Sammensatte tokens

Den sidste gruppe af disse makroer er så:

#define o1Il1IIIollllIIl O1lII11l(O1lII11l(Ol1I1lII,oIllII1I),O1lII11l(o11lIl1I,o11I111I))
#define o1Il1IIIOll111ll O1lII11l(O1lII11l(O1lII11l(Ol1I1lII,O1lII11l(O11lIlll,o11II1I1)),O1ll1IIl),o11lI111)
#define o1Il1IIIOI1lll1I O1lII11l(Ol1ll1l1,O1lII11l(o11II1I1,o11lI111))
#define o1Il1IIIOI1111I1 O1lII11l(O1lII11l(OI11lllI,oII1llI1),O1lII11l(o11lI111,O1ll1IIl))
....
#define o1Il1IIIolIllI1l O1lII11l(Ol1ll1l1,O1lII11l(o11II1I1,o11lI111))

Her ser vi en gruppe af makroer der laver nestede kald til O1lII11l makroen. Så den er naturligvis værd at kigge på:

#define O1lII11l(oI1,oII) OI1l1I1l(oI1,oII)
#define OI1l1I1l(Ol1,oll) Ol1##oll

Igen samme nestede struktur og her et gensyn med joining operatoren. Denne gang er det de to argumenter, der pastes. Disse argumenter er (igen) enkelte tegn:

#define Ol1I1lII c
#define oIllII1I h
#define o11lIl1I a
#define o11I111I r
...
#define o11lI111 t

Disse bliver så gennem de nestede kald til O1lII11l kombineret til større tokens, og vi kan igen reducere vores makroer:

#define o1Il1IIIollllIIl char
#define o1Il1IIIOll111ll const
#define o1Il1IIIOI1lll1I int
#define o1Il1IIIOI1111I1 puts
....
#define o1Il1IIIolIllI1l int

Kigger vi så tilbage på hvad dette betyder for O11I1Il1 makroen, som vi begyndte at kigge på tidligere, så kan vi se at O11I1Il1 kan kaldes med én af 257 forskellige argumenter, som hver resultere i én C-token. Vi ved også at der er argumenter, der kan resulterer i en token, som ikke er i det oprindelige juletræsprogram. Det kan på dette tidspunkt godt betale sig at lave lidt søg og erstat ned igennem filen. Først kan vi omdøbe O1lII11l makroen til f.eks. token_paste. Vi kan også omdøbe O11I1Il1 til token_lookup, og sidst kan vi tage o1Il1III præfixet og lave til token_table. Her er også første gang vi støder på denne tabelstruktur, hvor vi har en lang række makroer. der starter med samme præfix og så et skiftende suffix, så i f.eks. o1Il1IIIOI1111I1 er o1Il1III det fælles præfix og OI1111I1 suffixet, der indikerer, hvad der skal slåes op.

olIII1l1 makroen

Med token_lookup makroen klaret, så kan vi kigge på den anden makro i token genereringen; olIII1l1:

#define olIII1l1(o11) oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oIIIll1l(o11),o11111Il(o11)),ollIIl1l(o11)),oI1l11l1(oI1l11l1(oI1l11l1(O1IllI1I(o11),O1llI1Il(o11)),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(OI1II111(o11),oIIII1lI(o11)),oI1l11l1(oI1l11l1(oIlI1lIl(o11),oI1l11l1(Ol1l1I11(o11),o1l1lIIl(o11))),oI1l11l1(oI1l11l1(O1IlIIll(o11),oI1l11l1(oIIlIIl1(o11),oI1l1111(o11))),oIll1II1(o11)))),oI1l11l1(oI1l11l1(oI1l11l1(o1I11l1l(o11),o1lI1II1(o11)),O11III1l(o11)),Ol1I11lI(o11))),oI1l11l1(oI1l11l1(ol1II11I(o11),O1l1IlII(o11)),oI1l11l1(Ol1IIIll(o11),O1l11l11(o11))))),oI1l11l1(oI1l11l1(oI1l11l1(Oll11111(o11),OIIlll1I(o11)),oI1l11l1(Ol1Il1lI(o11),OII1IIl1(o11))),oI1l11l1(oI1l11l1(OI1lI1ll(o11),oI1I111l(o11)),oI1l11l1(OIlII1lI(o11),O11I1lI1(o11)))))),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(Oll1l1lI(o11),olIllll1(o11)),oI1l11l1(oI1l11l1(oI111Ill(o11),oI1l11l1(o11IllI1(o11),oI1l11l1(oI1l11l1(Ol1Il1II(o11),O1lI1lII(o11)),ol11IIlI(o11)))),o1ll1lI1(o11))),oI1l11l1(oI1l11l1(oI1l11l1(O1lIIlI1(o11),oI1l11l1(oI1l11l1(OIlI1Ill(o11),o1IlIIll(o11)),oIl11Ill(o11))),oI1l11l1(OlI11llI(o11),oll1l1Il(o11))),oI1Illll(o11))),oI1l11l1(oI1l11l1(oI1l11l1(OI11lIl1(o11),oI1l11l1(O1llI1l1(o11),o111Il1l(o11))),oI1l11l1(oI1l11l1(o1l1I11I(o11),ol11l1l1(o11)),olllI1II(o11))),oI1l11l1(oI1l11l1(o1IIlIIl(o11),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(OIIlllI1(o11),OI1Il1Il(o11)),ol1Il1ll(o11)),Ol11l1II(o11)),oI1l11l1(o1II1l1l(o11),olIIIIlI(o11)))),ol1Ill11(o11)))),oI1l11l1(OlIlIII1(o11),oI1l11l1(oI1l11l1(oI11lll1(o11),olIIllII(o11)),oI1l11l1(Ol1l1II1(o11),o11l111I(o11))))),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(Ollllll1(o11),O1lIlIl1(o11)),ol1111ll(o11)),oI1l11l1(oI1l11l1(oI1l11l1(OI11lll1(o11),oI1l11l1(O11lIlII(o11),Olll1lII(o11))),oI1l11l1(ollI1IIl(o11),oI1l11l1(OlII11II(o11),OIlI1I1l(o11)))),oI1l11l1(oI1l11l1(O1IIlI11(o11),OI11lI1l(o11)),o1I11l11(o11)))),oI1lI111(o11)),oI1l11l1(oI1l11l1(Olll11II(o11),O11Il111(o11)),oI1l11l1(oI1l11l1(O11lIIl1(o11),oI1l11l1(OI1l111I(o11),O1I1ll1l(o11))),oI1l11l1(oI1l11l1(o11I11l1(o11),oIl1lIlI(o11)),olI1l11l(o11))))),oI1l11l1(oI1l11l1(oI1l11l1(ollI111I(o11),oI1l11l1(oI1l11l1(OlI1lll1(o11),OlllIIlI(o11)),oI1l11l1(oI1l11l1(oI1l11l1(OIl1lI1I(o11),oI1l11l1(olI1II1I(o11),oII1llII(o11))),oll1ll1l(o11)),oI1l11l1(Ol1IIIl1(o11),olllI11I(o11))))),oI1l11l1(oI1l11l1(oIl1I1l1(o11),oI1l11l1(oI1l11l1(oII1IlI1(o11),OIIlI1Il(o11)),oI1l11l1(oI11111l(o11),oll11I1I(o11)))),oI1l11l1(oI1l11l1(ollIl111(o11),OIlIIl1l(o11)),OlIIl1ll(o11)))),oI1l11l1(oI1l11l1(oIIIl11l(o11),oI1l11l1(O1lIIl1I(o11),oI11l11I(o11))),o111I1ll(o11))))),oI1l11l1(oI1l11l1(olIII1ll(o11),o1llllll(o11)),ol1IIIlI(o11))),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(OllIIIIl(o11),oI1l11l1(oI1l11l1(o1I11I11(o11),o1lll111(o11)),OllIIlIl(o11))),oI1l11l1(oI1l11l1(oI1l11l1(oIlI1l11(o11),oII11l1I(o11)),oI1l11l1(OllllII1(o11),O111IIll(o11))),oI1l11l1(Ol1lI1I1(o11),oI1l11l1(O111III1(o11),oI1l11l1(oI1l11l1(oI1l11l1(OI1IlIll(o11),oIIlI11I(o11)),Ol11IIl1(o11)),o1l11III(o11)))))),oI1l11l1(Ol111I1l(o11),Oll11Ill(o11))),oI1l11l1(oI1l11l1(oI1l11l1(oI11lI1I(o11),oI1l11l1(olIl1Ill(o11),oI1l11l1(oI1l11l1(oIlI1111(o11),OI1llIII(o11)),oI1l11l1(o11I1I1I(o11),o1II1lll(o11))))),oIIll1ll(o11)),oI1l11l1(oI1l11l1(OI1II1lI(o11),oI1l11l1(ol1I1II1(o11),o1IIlllI(o11))),olI1lIIl(o11)))))),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(o1Il1II1(o11),oI1l11l1(oI1l11l1(OIIl11l1(o11),oI1l11l1(OIllIlII(o11),oI1l11l1(ol111l11(o11),Ol11llI1(o11)))),oI1l11l1(oI1l11l1(oI1l1ll1(o11),O111IIl1(o11)),ol1llll1(o11)))),olIl1IIl(o11)),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(ollII1Il(o11),oI1l11l1(oIlII11l(o11),O1III1Il(o11))),oI1l11l1(oI1l11l1(olIlIIII(o11),oI1l11l1(oIIIIlIl(o11),olI1Il1I(o11))),OII1l11l(o11))),oI1l11l1(oI1l11l1(oI1l11l1(OIIIIl1l(o11),oI1l11l1(oI1l11l1(oII1IlIl(o11),oI1llIlI(o11)),ol1I11ll(o11))),o1ll1lIl(o11)),olI1II1l(o11))),OlIl1I1l(o11))),oI1l11l1(oI1l11l1(OlI1lI1I(o11),oII1IIII(o11)),OII1IlII(o11))),oI1l11l1(oI1l11l1(oI1l11l1(oI1l11l1(O1ll111l(o11),O1llIllI(o11)),oI1l11l1(oI1l11Il(o11),Ol11IIIl(o11))),oI1l11l1(oI1l11l1(o11Il1I1(o11),OIIlIlIl(o11)),oI1l11l1(oI1l11l1(o1ll1IlI(o11),OI1l1l1I(o11)),oI1l11l1(oI1l11l1(o1IlllII(o11),O1lI11ll(o11)),oI1l11l1(oI1l11l1(OllIIl1I(o11),oI11llI1(o11)),oI1l11l1(oI1l11l1(OIIIIlll(o11),oII1l11I(o11)),OIlI1I11(o11))))))),oI1l11l1(oI1l11l1(oI1l11l1(OI1l1lIl(o11),oI1l11l1(oI1l11l1(OlIlII1I(o11),o1l11I11(o11)),OIIlI11l(o11))),ollIll11(o11)),oI1l11l1(oIllll1I(o11),oI1l11l1(o1llII11(o11),oI1l11l1(o1llllI1(o11),olIl11ll(o11))))))))

oI1l11l1 makroen

Dette er noget af en makro, men hvis vi bare tager den første makro heri, oI1l11l1 og kigger på den:

#define oI1l11l1(Oll,O1l) token_paste(token_paste(oIlIII11,Oll),O1l)

Så får vi et kært gensyn med vores token_paste makro, som vi lige har omdøbt. Så her bliver de to argumenter pasted sammen med oIlIII11 foran og evalueret. Igen kan det være interessant at kigge på alle de makroer der starter sådan:

#define oIlIII11Ol1llI1lOlIIII11 oI11I1ll
#define oIlIII11Oll1IlIlOlI1Il11 O1Ill1l1
#define oIlIII11olI1II11O1llIIlI O11II11l
#define oIlIII11O1I1Il11o1II1lII olIIl11l
...
#define oIlIII11OI1I11IIo1IIlll1 o111IIll

Dem er der mange af, rigtigt mange af. Faktisk er der 66049 af dem, og måske synes man, det var et pudsigt tal, for det er et kvadrattal, specifikt 257², altså kvadratet på antallet af værdier, der er i vores token_lookup makro. Det kunne tyde på, at denne her oI1l11l1 makro tager to tokenrepræsentationer ind og, baseret på de eksempler overfor, giver en token repræsentation tilbage ud. Også strukturen af tabelens navne tyder på dette. F.eks. kan oIlIII11O1I1Il11o1II1lII deles i tre dele, på samme måde som vores token_table kunne deles i to. Der er delene så oIlIII11, der er præfixet, samt O1I1Il11 og o1II1lII som så er de to suffixer. Kigger man på alle resultaterne af oI1l11l1 makroen, så er de ikke bare valide inputs til token_lookup makroen, men også til oI1l11l1 makroen selv. De valide inputs til oI1l11l1 er også præcist de samme tokenrepræsentationer som token_lookup tager. Dvs. tokenrepræsentationerne er lukket under oI1l11l1 makroen. Hvis man er lidt matematisk anlagt, så kunne det være nærliggende at overveje, hvilke andre egenskaber oI1l11l1 potentielt har. Har den f.eks. et identitetselement, et nulelement, er den kommutativ, er den associativ?

#define oIlIII11OlIII1I1O111111l O111111l
#define oIlIII11OlIII1I1oI111lI1 oI111lI1
#define oIlIII11OlIII1I1OI11lIlI OI11lIlI
#define oIlIII11OlIII1I1O1l1I1Il O1l1I1Il
...
#define oIlIII11OlIII1I1OlIIIIlI OlIIIIlI

OlIII1I1 er et identitetselement for oI1l11l1, dvs. oI1l11l1(OlIII1I1, x) = x.

#define oIlIII11o11IIII1oll1l1ll O11II11l
#define oIlIII11oll1l1llo11IIII1 O11II11l

oI1l11l1 er også kommutativ, dvs. oI1l11l1(x, y) = oI1l11l1(y, x).

#define oIlIII11o1Il1I1IoIlIlIIl O1I1Il11
#define oIlIII11O1I1Il11OI1lll1l OlIl1II1
#define oIlIII11oIlIlIIlOI1lll1l O111Il11
#define oIlIII11o1Il1I1IO111Il11 OlIl1II1

Sidst er oI1l11l1 også associativ, dvs. oI1l11l1(x, oI1l11l1(y, z)) = oI1l11l1(oI1l11l1(x, y), z). Hvis man arbejder alle 257 muligheder igennem, så har oI1l11l1 ikke noget nul element, dvs. der findes ikke nogen værdi O således at oI1l11l1(O, x) = O for alle x. For at holde styr på dette, så kan vi, for nu, omdøbe oI1l11l1 til op1 og oIlIII11 til op1_table.

Tager vi et skridt tilbage til den oprindelige olIII1l1 makro, så ved vi nu, at op1 makroen er både kommutativ og associativ, så vi kan betragte alle de næstede kald til op1 som bare værende mellem de andre allerinderste argumenter. Disse argumenter er så:

oIIIll1l(o11)
o11111Il(o11)
ollIIl1l(o11)
O1IllI1I(o11)
...
olIl11ll(o11)

Begynder vi ved den første her, er den bare en konstant:

#define oIIIll1l(OII) oIIIlI11

Det er der ikke synderligt meget at hive ud af, men lad os kigge på de næste 3 stykker:

#define o11111Il(oII) O1I1lIlI(oI1llll1,oII)
#define ollIIl1l(OI1) O1I1lIlI(O1I1lIlI(oIl111lI,OI1),OI1)
#define O1IllI1I(O11) O1I1lIlI(O1I1lIlI(O1I1lIlI(OI11lI11,O11),O11),O11)

De bliver gradvist større og større, og kigger man på resten af de indre makroer, så fortsætter dette mønster med at hver makro tilføjer et ekstra kald til O1I1lIlI makroen.

O1I1lIlI makroen

Så er det jo nærliggende at undersøge denne O1I1lIlI makroen:

#define O1I1lIlI(o1l,o11) token_paste(token_paste(olIll111,o1l),o11)

Dette minder jo uhyggeligt meget om op1 makroen bare med et nyt præfix, olIll111. Laver vi de samme analyser som vi gjorde for op1, så finder vi at også O1I1lIlI er lukket, kommutativ, associativ og har et identitetselement o1I1lI1l, ydermere har O1I1lIlI også et nul element:

#define olIll111OlIII1I1ol11111I OlIII1I1
#define olIll111OlIII1I1oI1IIll1 OlIII1I1

Navneligt OlIII1I1, dvs. O1I1lIlI(OlIII1I1, x) = OlIII1I1 Nævneværdigt her er, at O1I1lIlIs nul-element, OlIII1I1, også er op1s identitetselement.

Lad os lynhurtigt kalde O1I1lIlI for op2 og olIll111 for op2_table

Tager vi et skridt tilbage, så har vi nu to binære operationer op1 og op2. Begge er kommutative og associative, begge har et identitetselement, og op1s identitetselement er også op2s nul-element. Samtidigt har vi olIII1l1 makroen, som kombinerer forskellige under-makroer med op1, hver af disse under-makroer bruger så op2 startende fra 0 gange af og gradvist flere og flere.

Sammenligner man disse egenskaber med normale matematiske operatorer, så passer alle disse egenskaber med at op1 er plus og op2 er gange. Både plus og gange er lukkede, kommutative og associative. Plus har identitetselement 0, som samtidigt er ganges nul-element. Gange har identitetselement 1. Kigger vi på olIII1l1 makroen, så ville det blive et polynomial med den antagelse. Så alt i alt virker det ikke som en urimelig antagelse at arbejde videre med.

Så kan vi, på forsøgsbase, omdøbe op1 og op2 makroerne. Samtidigt kan vi omdøbe olIII1l1 til f.eks. poly. Sidst har vi en idé om at OlIII1I1 er 0 og o1I1lI1l er 1, så de to kan vi også begynde at omdøbe.

Alle tallene

Med en idé om at vi har fundet 0 og 1, og med vores plus operator, så er det trivielt at regne de resterende tal op til 256 ved først at regne 1 + 1, så 2 + 1, 3 + 1, osv. Vi ved, der kun er op til 256, da vi tidligere konstaterede, at der var 257 forskellige tokenreferencer, og det jo er disse, der bliver lagt sammen.

#define op1_table_001_001 OlI111II
#define op1_tableOlI111II_001 O1lI11Il
#define op1_tableO1lI11Il_001 O1llIl1I
...
#define op1_tableOlIIIl1I_001 O111Illl

Således får vi en måde at konvertere alle tokenreferencerne til tal, og hvis vi så laver en søg og erstat ned i vores fil, så alle disse token referencer bliver til tal, så ser vores sidste linje i filen således ud:

token_lookup(poly(_001)) token_lookup(poly(_003)) token_lookup(poly(_005)) token_lookup(poly(_007)) token_lookup(poly(_009)) token_lookup(poly(_011)) token_lookup(poly(_013)) token_lookup(poly(_015)) token_lookup(poly(_017)) token_lookup(poly(_019)) token_lookup(poly(_021)) token_lookup(poly(_023)) token_lookup(poly(_025)) token_lookup(poly(_027)) token_lookup(poly(_029)) token_lookup(poly(_031)) token_lookup(poly(_033)) token_lookup(poly(_035)) token_lookup(poly(_037)) token_lookup(poly(_039)) token_lookup(poly(_041)) token_lookup(poly(_043)) token_lookup(poly(_045)) token_lookup(poly(_047)) token_lookup(poly(_049)) token_lookup(poly(_051)) token_lookup(poly(_053)) token_lookup(poly(_055)) token_lookup(poly(_057)) token_lookup(poly(_059)) token_lookup(poly(_061)) token_lookup(poly(_063)) token_lookup(poly(_065)) token_lookup(poly(_067)) token_lookup(poly(_069)) token_lookup(poly(_071)) token_lookup(poly(_073)) token_lookup(poly(_075)) token_lookup(poly(_077)) token_lookup(poly(_079)) token_lookup(poly(_081)) token_lookup(poly(_083)) token_lookup(poly(_085)) token_lookup(poly(_087)) token_lookup(poly(_089)) token_lookup(poly(_091)) token_lookup(poly(_093)) token_lookup(poly(_095)) token_lookup(poly(_097)) token_lookup(poly(_099)) token_lookup(poly(_101)) token_lookup(poly(_103)) token_lookup(poly(_105)) token_lookup(poly(_107)) token_lookup(poly(_109)) token_lookup(poly(_111)) token_lookup(poly(_113)) token_lookup(poly(_115)) token_lookup(poly(_117)) token_lookup(poly(_119)) token_lookup(poly(_121)) token_lookup(poly(_123)) token_lookup(poly(_125)) token_lookup(poly(_127)) token_lookup(poly(_129)) token_lookup(poly(_131)) token_lookup(poly(_133)) token_lookup(poly(_135)) token_lookup(poly(_137)) token_lookup(poly(_139)) token_lookup(poly(_141)) token_lookup(poly(_143)) token_lookup(poly(_145)) token_lookup(poly(_147)) token_lookup(poly(_149)) token_lookup(poly(_151)) token_lookup(poly(_153)) token_lookup(poly(_155)) token_lookup(poly(_157)) token_lookup(poly(_159)) token_lookup(poly(_161)) token_lookup(poly(_163)) token_lookup(poly(_165)) token_lookup(poly(_167)) token_lookup(poly(_169)) token_lookup(poly(_171)) token_lookup(poly(_173)) token_lookup(poly(_175)) token_lookup(poly(_177)) token_lookup(poly(_179)) token_lookup(poly(_181)) token_lookup(poly(_183)) token_lookup(poly(_185))

Og her er det jo pudsigt, at polynomiet bliver brugt udelukkende på ulige tal, så kunne man jo være fristet til at overveje hvad der sker, hvis man skifter den til lige tal, specielt når opgaven hedder Christmas Even. Så ændrer vi den sidste linje til:

token_lookup(poly(_002)) token_lookup(poly(_004)) token_lookup(poly(_006)) token_lookup(poly(_008)) token_lookup(poly(_010)) token_lookup(poly(_012)) token_lookup(poly(_014)) token_lookup(poly(_016)) token_lookup(poly(_018)) token_lookup(poly(_020)) token_lookup(poly(_022)) token_lookup(poly(_024)) token_lookup(poly(_026)) token_lookup(poly(_028)) token_lookup(poly(_030)) token_lookup(poly(_032)) token_lookup(poly(_034)) token_lookup(poly(_036)) token_lookup(poly(_038)) token_lookup(poly(_040)) token_lookup(poly(_042)) token_lookup(poly(_044)) token_lookup(poly(_046)) token_lookup(poly(_048)) token_lookup(poly(_050)) token_lookup(poly(_052)) token_lookup(poly(_054)) token_lookup(poly(_056)) token_lookup(poly(_058)) token_lookup(poly(_060)) token_lookup(poly(_062)) token_lookup(poly(_064)) token_lookup(poly(_066)) token_lookup(poly(_068)) token_lookup(poly(_070)) token_lookup(poly(_072)) token_lookup(poly(_074)) token_lookup(poly(_076)) token_lookup(poly(_078)) token_lookup(poly(_080)) token_lookup(poly(_082)) token_lookup(poly(_084)) token_lookup(poly(_086)) token_lookup(poly(_088)) token_lookup(poly(_090)) token_lookup(poly(_092)) token_lookup(poly(_094)) token_lookup(poly(_096)) token_lookup(poly(_098)) token_lookup(poly(_100)) token_lookup(poly(_102)) token_lookup(poly(_104)) token_lookup(poly(_106)) token_lookup(poly(_108)) token_lookup(poly(_110)) token_lookup(poly(_112)) token_lookup(poly(_114)) token_lookup(poly(_116)) token_lookup(poly(_118)) token_lookup(poly(_120)) token_lookup(poly(_122)) token_lookup(poly(_124)) token_lookup(poly(_126)) token_lookup(poly(_128)) token_lookup(poly(_130)) token_lookup(poly(_132)) token_lookup(poly(_134)) token_lookup(poly(_136)) token_lookup(poly(_138)) token_lookup(poly(_140)) token_lookup(poly(_142)) token_lookup(poly(_144)) token_lookup(poly(_146)) token_lookup(poly(_148)) token_lookup(poly(_150)) token_lookup(poly(_152)) token_lookup(poly(_154)) token_lookup(poly(_156)) token_lookup(poly(_158)) token_lookup(poly(_160)) token_lookup(poly(_162)) token_lookup(poly(_164)) token_lookup(poly(_166)) token_lookup(poly(_168)) token_lookup(poly(_170)) token_lookup(poly(_172)) token_lookup(poly(_174)) token_lookup(poly(_176)) token_lookup(poly(_178)) token_lookup(poly(_180)) token_lookup(poly(_182)) token_lookup(poly(_184)) token_lookup(poly(_186))

Så kan vi køre præprocessoren igen og får:

$ gcc -E christmas_even-renamed.c
# 0 "christmas_even-renamed.c"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 0 "<command-line>" 2
# 1 "christmas_even-renamed.c"
# 132631 "christmas_even-renamed.c"
int puts ( const char * ) ; int main ( int , char * * ) { puts ( "N" "C" "3" "{" "W" "h" "3" "N" "_" "1" "5" "_" "C" "h" "R" "1" "5" "7" "M" "a" "S" "_" "3" "v" "3" "_" "e" "V" "3" "n" "}" ) ; return 0 ; }

Compiler man og kører programmet, så får man:

$ gcc christmas_even-renamed.c -o christmas_even
$ ./christmas_even
NC3{Wh3N_15_ChR157MaS_3v3_eV3n}

Og det er jo et flag!