Elegant kode

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:

def at214c(d0):
        d2 = 0x11111111
        d2 &= d0
        d0 <<= 1
        d0 <<= 1
        d0 <<= 1
        d0 &= 0x77777777
        d0 += d2
        d2 <<= 2
        d0 += d2
        return d0

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

phk

Poul-Henning Kamps billede
Poul-Henning er selvstændig systemprogrammør, kernekoder, Varnish-forfatter, data-arkæolog og brokkehoved uden særlig portefølje.

Kommentarer (25)

Anders Søndergaard

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.

Finn Glamhøj

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.

Finn Glamhøj

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

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.

Baldur Norddahl

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 ?

Baldur Norddahl

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".

Lars Skovlund

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).

Poul-Henning Kamp Blogger

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.

Poul-Henning Kamp Blogger

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.

Poul-Henning Kamp Blogger

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.

Jesper Louis Andersen

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 :)

Log ind eller opret en konto for at skrive kommentarer