Dette indlæg er alene udtryk for skribentens egen holdning.

Elegant kode

Af Poul-Henning Kamp30. december 2016 kl. 22:1325
Artiklen er ældre end 30 dage

En af mine juletraditioner er at lave et juleprojekt "bare fordi".

I år er det noget gammel kode der er blevet disassembleret og undervejs fandt jeg en utrolig elegant funktion.

Det er ikke alle der kan assemblerkode nu om dags, så jeg har skrevet funktionen i python:

  1. def at214c(d0):
  2. d2 = 0x11111111
  3. d2 &= d0
  4. d0 <<= 1
  5. d0 <<= 1
  6. d0 <<= 1
  7. d0 &= 0x77777777
  8. d0 += d2
  9. d2 <<= 2
  10. d0 += d2
  11. return d0

Her er udfordringen: Kan du gennemskue hvad funktionen gør, uden at bruge en computer ?

Artiklen fortsætter efter annoncen

phk

25 kommentarer.  Hop til debatten
Denne artikel er gratis...

...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.

Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.

Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.

Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.

Debatten
Log ind eller opret en bruger for at deltage i debatten.
settingsDebatindstillinger
24
2. januar 2017 kl. 23:18

Ud over BCDMUL5 er der også en BCDMUL2, samt forskellige kombinationer af disse og addition (MUL3, MUL4, MUL6, MUL7...) men bortset fra BCDMUL2 er de alle ubrugte så vidt min kodeanalyse.

Hmm. Mit bud ville være at du har BCDMUL2, BCDMUL4 og BCDMUL5 der er de "nemme" at realisere effektivt. De kan så kombineres til at lave en generel X * Y multiplicator med lidt ekstra kode hvor disse funktioner er byggesten, uden at skulle lave mere end et par additioner undervejs.

Det er muligt at ALGOL-compileren bare lader det komme med i en runtime men fordi koden aldrig har haft brug for X*Y hvor X ikke er en konstant, så har den aldrig lavet kald til BCDMUL5. Eller også foregår der noget beregning af en adresse der så hoppes til, således at det direkte kald ikke er at finde i koden. Det ville være fyfy på en moderne kasse, men det er smart på en gammel dims :)

21
2. januar 2017 kl. 09:47

Hvis du savner at prøve det i virkeligheden har vi et par HP21xx ude i datamuseum.dk der godt kunne trænge til en kærlig hånd :-)

20
2. januar 2017 kl. 07:44

Min perle fra HP assembler:

        CLA,INA,SZA,RSS

Kan andre huske den?

19
1. januar 2017 kl. 20:22

Pudsigt, der er helt klart forskel på hvad man mener med "elegant kode". For mig er elegant kode hverken svært at læse eller forstå.

Jeg tror vi bliver nødt til at skelne imellem maskinkode og højniveausprog på dette punkt.

I højniveausprog har du et generelt og typisk veldesignet arsenal af virkemidler til rådighed og du skal ikke kære dig om "calling-conventions", register-allokering osv.

I maskinkode har du et endeligt og ofte af hardwareimplementeringen degeneraliserede instruktioner, et berænset antal registre, ofte med specielle egenskaber og du skal selve holde styr på hvilke registre du bruger ind/ud og rydde op på stakken efter din kode.

I maskinkode verdenen er ovenstående elegant kode, for det bruger slet ikke stakken og får gjort en pokkers masse arbejde med kun 9 instruktioner.

18
1. januar 2017 kl. 20:14

Baldur: Ang. hvorfor ikke d0 <<= 3, så skyldes det nok at den maskinarkitektur der er oversat fra, ikke understøtter shifts med mere end én.

Jeg vil kalde det en porteringsfejl.

Den første model, HP8568A brugte HP's egen 16 bit microprocessor, kaldet "The Hybrid Processor" (mere her: http://www.hp9845.net/9845/hardware/processors/)

Den havde såvidt jeg ved kun instruktioner til enkelt-skift.

Efterfølgeren HP8568B fik en Motorola 68000 CPU og den har faktisk shift-#N instruktioner, men det overså den person der porterede BCD-biblioteket - Formodentlig Wheelwright selv.

17
1. januar 2017 kl. 20:10

Jeg mistænker derfor funktionen for at være en "opgave til læserne" mere end en funktion der fundet "in the wild".

Opgaven er bestemt ikke konstrueret. Den kommer fra firmwaren på en HP8568 spektrum analysator der har givet mig lidt problemer hen over julen.

I bunden af firmware ligger håndkodede biblioteksrutiner til to størrelse floating point og 16-ciffer BCD aritmetik.

Ud over BCDMUL5 er der også en BCDMUL2, samt forskellige kombinationer af disse og addition (MUL3, MUL4, MUL6, MUL7...) men bortset fra BCDMUL2 er de alle ubrugte så vidt min kodeanalyse.

Det meste af firmwaren er skrevet i "WHEELGOL", hvilket var det interne HP kælenavn for Lynn M. Wheelwrights ALGOL compiler. Compileren spytter kald til de forskellige BCD rutiner ud, men som sagt har jeg ikke fundet nogen til MUL5 funktionen.

14
1. januar 2017 kl. 17:40

Casper Bang: Man skal nok se den med elektroingeniør-briller på for at finde den elegant. Pointen er, som vist i diagrammet i Anders Søndergaards link, at opgaven kan løses uden digital logik. Det er ren ledningsføring.

Baldur: Ang. hvorfor ikke d0 <<= 3, så skyldes det nok at den maskinarkitektur der er oversat fra, ikke understøtter shifts med mere end én. Det gælder for eksempel oprindeligt x86, der havde shl reg, 1 og shl reg, cl (cl er navnet på et register), men ikke en generel shl reg, imm. Først senere kom denne til. Og iøvrigt var der masser af denne type tricks i ældre kode fordi multiplikationer og divisioner var dyre. Der var fx en gut, der fandt ud af at sætte et VGA-kort i "Mode Q" (256x256 pixels i 256 farver), fordi et skærmkoordinat da kunne repræsenteres ved 8+8 bits = ingen multiplikationer og ingen shifts (da høj/lav byte på 16-bit x86 kan addresseres direkte).

13
1. januar 2017 kl. 16:54

@Casper Bang, Tak - det er vidst den bemærkning som burde siges.

12
1. januar 2017 kl. 16:17

Pudsigt, der er helt klart forskel på hvad man mener med "elegant kode". For mig er elegant kode hverken svært at læse eller forstå.

11
1. januar 2017 kl. 12:29

En aimbot til counterstrike?

Ej altså, tror bare det bliver skisport i dag :)

10
31. december 2016 kl. 17:29

Din funktion ganger et binært tal med 5. PHKs funktion ganger et "packed BCD" tal med 5. To forskellige ting.

Der er ikke nogen generisk måde at udføre multiplikation på "packed BCD" uden at konvertere til et andet format først.

Jeg sværger på at jeg har set denne opgave før men kan ikke lige finde ud af hvor. Det virker lidt søgt at man har brug for en funktion der kan gange med 5 men tilsyneladende ikke har brug for at udføre multiplikation generisk. Hvis man har den generiske funktion tilgængelig, så vil de fleste bare kalde den. Jeg mistænker derfor funktionen for at være en "opgave til læserne" mere end en funktion der fundet "in the wild".

9
31. december 2016 kl. 16:58

Er den kode så så meget mere elegant end den klassiske måde:

def at214c(d0): d2 = d0 d2 <<= 2 d0 += d2 return d0

8
31. december 2016 kl. 16:32

Hvis jeg havde kunnet regne så havde jeg nok indset noget før at 0x7 ikke er 1000. Det ændrer jo lidt på regnestykket.

7
31. december 2016 kl. 14:09

Der er ingen overflow eller mente fra nibble til nibble.

Jo det er præcis det der er.

Hvis du tager mindst betydende nibble, så er resultatet altid 0000 eller 0101 (5). Du ser at d0 bliver shiftet 3 til venstre (= ganget med 8). Herefter bliver den udsat for en AND operation med 0111 (7) og resultatet af det er altid 0000 for den første nibble. d2 husker den nederste bit, dvs. om tallet var ulige. Hvis mindst betydende nibble er lige, så sker der ikke mere og resultatet er 0000. Hvis den er ulige bliver der added 0101 og resultatet er 0101 (5). Det sker ved operationen d0 = d0 + d2 + 4*d2.

For den næst mindst betydende nibble er resultatet det samme. Det giver 0000 eller 0101. PLUS mente fra forrige nibble.

For at udregne menten ganger du hvert ciffer med 5 og dividerer med 10. Det er det samme som at dividere hvert ciffer med 2.

Der shiftes 3 bits til venstre. Havde det været 4 bits, så var hvert ciffer blevet flyttet helt over til næste nibble. En shift for lidt er dermed det samme som at flytte hvert ciffer over til næste nibble og dividere med 2. Den mindst betydende bit, som bliver til overs som fjerde bit i den oprindelige nibble, slipper vi af med ved at udføre AND operationen med 0111.

Det vil sige at efter shift og AND indeholder d0 menten for hvert ciffer. Og i d2 har man gemt oplysning om hvorvidt der skal tillægges 5 eller ej for hvert ciffer.

Er der nogen der ved hvorfor de ikke bare skriver d0 <<= 3 ?

6
31. december 2016 kl. 12:47

Funktionen arbejder med nibbles. Der bruges kun mindst betydende bit i hver nibble. Der er ingen overflow eller mente fra nibble til nibble. Til gengæld arbejdes der på 8 nibbles ad gangen (32 bit registre) hvilket er effektivt :-)

For hver nibble er funktionen: input -> output xxx0 -> 0000 xxx1 -> 1101 altså lige nibbles bliver til 0, ulige til 0xD.

Det havde været hulens rart at vide hvilken datatype der arbejdes med. Jeg har ikke gennemskuet om der ligger et hint i funktionens navn.

5
31. december 2016 kl. 01:06

  1. # Her er min forklaring til koden:
  2. def at214c(d0):
  3. d2 = 0x11111111
  4. d2 &= d0 # d2 = 1 for hver BCD ciffer hvis cifferet er ulige
  5. d0 <<= 1
  6. d0 <<= 1
  7. d0 <<= 1
  8. d0 &= 0x77777777# d0 = d0 skifter et BCD ciffer og hvert BCD ciffer divideres med 2 (heltalsdivision)
  9. d0 += d2 # d0 = d0 med hvert BCD ciffer forøget med 1 hvis det oprindelige BCD ciffer var ulige
  10. d2 <<= 2 # d2 = 4 for hver BCD ciffer hvis det oprindelige BCD ciffer var ulige
  11. d0 += d2 # d0 = d0 med hvert BCD ciffer forøget med 4 hvis det oprindelige BCD ciffer var ulige.
  12. # Det vil sige at der i de sidste 3 linjer lægges 5 til hvert BCD ciffer der oprindelig var ulige
  13. return d0

3
31. december 2016 kl. 00:35

Jeg tror det funktionen gør er, at den ganger en BCD værdi med 5.

P.S. Jeg har testet det førend jeg skrev dette indlæg ved at køre python koden og det se sådan ud, så det er måske at snyde.

2
31. december 2016 kl. 00:17

Rettelse: der sker spring ned til 5x ved x = 1, 16, 256 osv. Funktionen at214c(x) - 8*x springer kraftigere og kraftigere ved x mod 1, 16, 256, 4096, .. 2^(4n) = 0 for stigende n.

1
31. december 2016 kl. 00:04

Til første orden ganger funktionen d0 med 8 via de 3 enkelte bitskift. Det er i hvert fald tilfældet så længe den mindst betydende bit i hver nibble (= halve byte) er 0, da det er den der bliver gemt i d2, og det er de eneste bits der bliver frasorteret d0*8 med &= 0x77777777.

I de tilfælde hvor den mindst betydende bit i mindst en nibble er 1 bliver de trukket fra d0 og lagt tilbage med et offset på 0 og 2 (dvs ganget med 5) efter at "resten" af d0 er blevet ganget med 8.

at214c(x) antager således værdier mellem 5x og 8x, med spring ned til 5*x hver gang x mod 1, 16, 256, 4096, .. 2^(4n) = 0

Jeg har snydt lidt og plottet funktionen atc214c(x) og det ligner en slags fraktal firkantfunktion.