Christmas Even
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:
Rydder man lidt op i dette program så er det bare:
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:
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
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:
Hvilket giver:
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
Tæller man antallet af tokens der bliver genereret, så får man 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:
Altså er dette blot en wrapper rundt om en anden makro. Lad os gå videre til den:
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:
Kigger vi lidt på disse, så optræder der et par typer af dem.
Type 1: De simple
To af makroerne er helt simple:
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:
Følger man disse makroer finder man at disse blot er enkelte symboler:
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:
Type 3: Quoted tokens
Den næste gruppe af o1Il1III makroer er så
Disse er kendetegnet ved at de alle kalder OIl1Il1l makroen:
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:
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:
Type 4: Sammensatte tokens
Den sidste gruppe af disse makroer er så:
Her ser vi en gruppe af makroer der laver nestede kald til O1lII11l makroen. Så den er naturligvis værd at kigge på:
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:
Disse bliver så gennem de nestede kald til O1lII11l kombineret til større tokens, og vi kan igen reducere vores makroer:
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:
oI1l11l1 makroen
Dette er noget af en makro, men hvis vi bare tager den første makro heri, oI1l11l1 og kigger på den:
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:
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?
OlIII1I1 er et identitetselement for oI1l11l1, dvs. oI1l11l1(OlIII1I1, x) = x.
oI1l11l1 er også kommutativ, dvs. oI1l11l1(x, y) = oI1l11l1(y, x).
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å:
Begynder vi ved den første her, er den bare en konstant:
Det er der ikke synderligt meget at hive ud af, men lad os kigge på de næste 3 stykker:
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:
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:
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.
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:
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:
Så kan vi køre præprocessoren igen og får:
Compiler man og kører programmet, så får man:
Og det er jo et flag!