decompress.asm

decompress.asm

.cpu cortex-m3
.syntax unified @ this is important, you won't get most of thumb-2 otherwise

.text
@ this file contains a assembly version of a lz decoder for cpse1 at the hogeschool utrecht
@ it's done in 15 instructions / 40 bytes, 20% less then what the best compiler did :)

@ compiler benchmarks
@ clang (trunk)
@ -O0 124 bytes
@ -O1  72 bytes
@ -O2 268 bytes
@ -O3 280 bytes
@ -Os  54 bytes
@ -Oz  50 bytes

@ gcc (trunk)
@ -O0 132 bytes
@ -O1  74 bytes
@ -O2  82 bytes
@ -O3 192 bytes
@ -Os  58 bytes

@ r0 = read head of compressed string
@ r1 = write head of decompressed string
@ r2 = value of compressed string head
@ r3 = length of match
@ r12 = offset of match

.global decompress
decompress:
.Lloop:                                 @ main loop for each character in the compressed string
        ldrb    r2, [r0], #1            @ get a char from compressed string
        cmp     r2, #'@'                @ check if char is '@' (the match marker)
        beq .Lmatch_found               @ then start decompression routine
        cbnz    r2, .Lstore_byte        @ if don't get a null byte (EOS) we store it in the decompressed string
        bx      lr                      @ else we exit
.Lmatch_found:
        ldrb    r3, [r0, #1]            @ read the length after the '@'
        ldrb    r2, [r0], #2            @ read the offset after the '@' and advance the pointer by 2
        rsb     r12, r2, #'0' - 1       @ reverse subtract a '0'-1 so we can use r12 as a "negative" offset to our regular decompressed write head
        subs    r3, #'0' - 1            @ subtract a '0'-1 because Wouter; -1 because we also sub one on the next instruction
.Lwrite_to_buffer:
        subs    r3, #1                  @ subtract one from the length (sets flags)
        itte    ne                      @ if the length was not equal to one, store it, else branch back to main loop 
        ldrbne  r2, [r1, r12]           @ load the byte by adding r12 to r1 so it overflows and points back into the decompressed buffer
.Lstore_byte:                           @ if we jump to this label; skipping the itte instruction, we will execute both the store and the branch even though they have opposite conditionals
        strbne  r2, [r1], #1            @ store a byte into our decompressed string and advance the pointer after
        beq .Lloop                      @ if the length became one we jump back to the main loop
        b   .Lwrite_to_buffer           @ otherwise we decompress the next character

main.cpp

#include "hwlib.hpp"

extern "C" void decompress(const char * comp, char * decomp);
void decompress_cc(const char *comp,  char *decomp);

extern "C" void put_char(char c) {
    hwlib::cout << c << hwlib::flush;
}

extern "C" char decompressed_string;
extern "C" char compressed_string;

const char *comp = &compressed_string;
char *decomp = &decompressed_string;

int main() {
    // wait for the terminal emulator to start up
    hwlib::wait_ms(100);
    decompress(comp, decomp);
    hwlib::cout << decomp << hwlib::flush;
}

// a C++ implementation to benchmark compilers
void decompress_cc(const char *comp,  char *decomp ) {
    while (true) {
        char c = *comp++;
        if (c == 0) {
            return;
        }
        if (c != '@') {
            *decomp++ = c;
        } else {
            int offset = *comp++ - '0' + 1;
            int length = *comp++ - '0';

            char * alt_head = decomp - offset;
            while (length--) {
                *decomp++ = *alt_head++;
            }
        }
    }
}

text.asm

.syntax unified
.global compressed_string, decompressed_string

.data
compressed_string:
.asciz "Wilhelmus van Nassouwe \n Ben ick@F5Duytsch@A3Bloedt,@O3D@O3Vaderland ghetrouwe@I3Blijf ick tot inden doet;@K3E@;3Prince van Orangi@O3\n B@U3ick vry onverveert.@I3D@O3Conin@M4an Hispangi@F3\n Heb i@H3altijt gheeert.\n\nIn Godes vre@53te leven \n Heb ick altijt betracht,@J3Daerom@B3n@Q5verdrev@=3\n Om Land, @O3Luyd ghebracht:@M3Maer Godt sal my regeren@J3Als e@93goet Instrument,@J3Dat ick sal wederkeeren@I3In mijn@;3Regiment.\n\nLijdt U,@J5 Ondersaten, \n Die oprecht z@N4van aert@L4Godt sal u niet verlaten@J3Al zijt ghy nu beswaert:@J3Die vroom@E3ghe@E3 te leven,@N3Bidt Go@43nacht ende d@:3.@L3Dat Hy my cr@M5wil gheven@M7ick u help@B3m@S3.\n\nLijf ende goed al te sam@Q3\n Heb ick u niet verschoont,@L3Mijn Broed@F3, @G3ch van Namen@Q4Hebbent u @K3k vertoont:@J3Graef Adolff is ghebleven,@L3In Vrieslandt in den Slach@M4Sijn siel@I3t eewich lev@S3\n Verw@W3t d@>3jonghst@H3d@C3.\n\nEdel @W3Hooch ghebor@W3\n Van Keyserlick@Q3stam:@H3E@N3Vorst des Rijcks vercoren,@P3Als e@T3vroom Christen-ma@M5Voor Godes W@:3t ghepreese@N5Heb ick vrij onversaecht@K4Als een helt zonder@W3ees@C3\n Mijn edel bloet gewaecht.\n\n@J5schilt ende betrouwen \n Zijt ghy, O Godt, mijn Heer.@N3Op U soo wil ick bouwen,@J3Verlaet my nimmermeer;@H3Dat ick doch vroom mag blijven@P3U dienaer t'all@73stond@I3Die tyranny verdrijven,@I7my mijn hert doorwondt.\n\nVal @23d@S6beswaren, \n End mijn vervolghers z@@3@L4M@H4Godt wilt doch bewaren@M3D@53trouw@=3dienaer@73jn:@K4at sy my niet verasschen@K3In haer@;3boos@B3moet,@H3H@E3@J3nd@V3niet @R3wassch@T3\n In mijn on@A3uldich bloet.\n\nAls David moeste vluchten \n Voor Saul d@?3tyran:@F3Soo heb ick moet@K3such@74\n Met menich edelman:@E4aer Godt heef@54m verheven,@O3Verlost uit alder noot@I4Een Coninckrijck ghe@23v@F3\n In Israel, seer groot.\n\nNa tsu@@3sal ick ontfanghen \n Van Godt, mijn Heer, dat soe@D3\n Daer na@?3 d@B3 verlanghen@L3Mijn vorstelick @F3m@T3,@J3Dat is, d@74@J3mag @V3rven@M3Met eeren, in@S5velt,@I3E@O3eeuwich rijk@H3rwerv@F3\n Als@L3n ghetrouwe helt.\n\nNiets doet my meer erbarmen \n In mijn@;3wedersp@W3,@G3Dan dat @U4siet verar@=4@K3es Conincks land@S3goet,@K4at ud de Spaengiaerts crencken@R4O edel Neerlandt soet@H4Als ick daeraen ghedencke@L4Mijn @?3l hert@S3t bloet.\n\nAls een Prins opgheset@@3\n Met mijnes heyr@63cracht,@K3Van d@U3tyr@93vermet@>3\n Heb ick@L5slach@L4w@73t,@M3Die, by Maestri@E3 begraven@N4Bevreesde mijn ghewelt;@I3M@?4ruyters sach men drav@63\n Seer moedi@I3door dat velt.\n\nSoo het den wil@73s Heer@>3\n Op die tijt had gheweest,@K3H@?3ick geern willen k@<3@63\n Van u dit swaer tempeest:@K3M@@4de He@H3van hi@Q3boven@M3Die alle dinck reg@V3t,@I7m@S3altijt moet loven@L4En heeft@C3ni@H3begeert.\n\nS@73 christlick was ghedreven \n Mijn prince@O5@K3moet,@J3Stantvastich is@J4bleven@K3Mijn hert in te@J3nspoet,@K3D@Q3Heer@O3b ick @M3bed@E3\n Van mijnes@M3rt@C3gront,@J3Dat Hy@M5 saeck wil reden@N4M@G4onschult doe@=3ircont.\n\nOorlof m@S4arme @V3apen, \n Die zijt in grooten n@63.@K3U Herder sal niet slapen,@K3Al zijt ghy nu verstroit:@K3Tot Godt wilt u begheven,@K3Sijn heylsaem woort neemt a@P6Als vrome Christen lev@K6Tsal hier haest zijn ghedaen.\n\nVoor Godt wil ick belijden \n End sijner groot@73macht,@K3Dat ick tot gheenen tijd@63@L3@<3Conin@P3heb veracht:@J4an dat i@J3Godt den Heere,@M4er hoochst@93Maje@83yt@J4Heb moeten obedieren@G4In der gh@@3chticheyt.\n"

.bss
decompressed_string:
.skip 4096 @ reserve 4k for decompressed string