.title r$hash ;+ ; this routine hashes the character string passed in r0 into ; an 7-character EOS-terminated string returned in the buffer ; passed in r1. All registers remain constant across the call. ; ; The hashing algorithm is a little wierd, but seems to be quite ; effective. A 32-bit integer is generated from the input string in ; the following manner: ; ; for (i=1; in(i) != EOS; i=i+1) ; { ; circularly rotate integer left by `limit' bits ; exclusive or character into integer ; } ; ; the output string is generated from the integer by taking 5-bit ; chunks of the integer (with the first character from the high 2 bits) ; and indexing into an array of the 26 upper-case characters and 0-5 ; ; this routine was tested on the 42000+ word dictionary `smalldict' ; with only 10 collisions found. ;- limit=5 .psect $r.rod,con,ro,rel,lcl,d table: .ascii "ABCDEFGHIJKLMNOPQRSTUVWXYZ012345" .even .psect $r.roi,con,ro,rel,lcl,i .enabl lsb r$hash:: call r$savr ; save all registers mov r1,-(sp) ; save output buffer address clr r3 ; initialize 32-bit integer clr r4 ; ... 10$: movb (r0)+,r1 ; fetch next character beq 20$ ; done mov #limit,r2 ; do rol limit times 2$: clc ; do 32 bit left rol rol r4 ; ... rol r3 ; ... adc r4 ; ... sob r2,2$ ; do again xor r1,r4 ; exclusive or character br 10$ ; do next character 20$: mov (sp)+,r0 ; address of output buffer mov #2,-(sp) ; do shifts twice ashc #2,r2 ; fetch high order 2 bits bic #177774,r2 ; mask to 2 bits movb table(r2),(r0)+ ; output first character asl r4 ; get 16th bit bcc 30$ ; c clear => high bit not set bis #2,r3 ; set the bit 30$: mov #3,r1 ; 3 shifts per word 40$: ashc #5,r2 ; fetch five bits from r3 bic #177740,r2 ; mask to five bits movb table(r2),(r0)+ ; copy character sob r1,40$ ; do again mov r4,r3 ; get second half dec (sp) ; are we done? bgt 30$ ; YES tst (sp)+ ; pop word off stack clrb (r0) ; terminate with EOS return .end