Pearson Hash in 6502 Assembly. Written in asm6 dialect.

README.md

Try it on Visual6502

pearson.asm

;; Defines

; Writes to this address are written as ASCII characters
; in the Visual6502 console.
OUTPUT  .equ    $000F       
; Number of strings
NUM_STR .equ    4

; Define some zero-page storage.
        .enum   $0010
; Generic string pointer.
strptr: .dsw 1      ; Generic string pointer
        .ende


;; PC starts at $0000; Jump to main subroutine, then halt.
        .base $0000
_start:
        sei         ; Disable interupts...
        cld         ; And disable BCD mode.
        ldx #$ff    ; Reset the stack pointer.
        txs
        jsr main
        .db $02     ; KILL opcode.


        .base $0200
; Hashes the string pointed to by strptr
; Hash is returned in A
; Destroys A,X,Y
Pearson: 
        ldy #$00            ; i = 0
        lda (strptr),Y      ; Return if str[0] == 0
        beq @done

        ldx #$00            ; hash = 0

@loop:  txa                 ; hash (=X) -> A
        eor (strptr),Y      ; hash (=A) ^ input (=M[strptr+Y]) -> A

        tax                 ; calculated index -> X
        lda PearsonLUT,X    ; new hash -> A

        tax                 ; hash (=A) -> X
        iny                 ; strptr++
        beq @done           ; Finish on overflow
        lda (strptr),Y
        bne @loop           ; loop if *strptr != 0

@done:  txa
        rts

; Calculate and print the hash of each string.
main:
        ldy #$00            ; i = 0

        
@loop   lda (Strings),Y     ; strptr = Strings[Y]
        sta strptr
        lda (Strings+1),Y
        sta strptr+1

        ; Save Y
        tya
        pha

        ; Calculate hash; returned in A.
        jsr Pearson

        ; Print a line in the form "%02X\t%s\n" % (hash, strptr)
        jsr PrintHex
        lda #$09
        sta OUTPUT
        jsr PutStr
        lda #$0A
        sta OUTPUT

        ; Restore Y and increment...
        pla
        tay
        iny
        iny
        cpy # 2*NUM_STR ; Y is i*2 so compare *2.
        bne @loop

        rts

; Prints A as two hex digits
; Destroys A,X,Y
PrintHex:
        tay                 ; Back up argument in Y

        lsr
        lsr
        lsr
        lsr
        tax                 ; Use the digit as an index in HexDigits
        lda HexDigits,X
        sta OUTPUT

        tya                 ; Restore A
        and #$0F            ; Keep first nimble
        tax                 ; Repeat printing process
        lda HexDigits,X
        sta OUTPUT

        rts

; Prints the zero-terminated string pointed by strptr.
; Destroys A,Y
PutStr
        ldy #$00
        lda (strptr),Y
        beq @done

@loop   sta OUTPUT
        iny
        beq @done           ; Finish on overflow
        lda (strptr),Y
        bne @loop

@done   rts


;; Data

        .base $E000
; A randomly generated look-up table for hashing.
PearsonLUT:
        .hex a44b50e89a8bb46226beb27edb05acc5
        .hex 2829b6e07bcd5b08988e54588487f4c2
        .hex d5fc739db7bf078814e2da567fb91d25
        .hex 761eb806bd5df6dd92ca3803fd43d0eb
        .hex ccd81f4d6d69ec80998f1a5979c69f40
        .hex 2df039eeb1a0279c01aa6a860446fb0a
        .hex 0d7d191bc936204815616b17116096d2
        .hex e17867cfc4bc4ce9516333de65d3d4dc
        .hex 3c16496f123a53cb18ba89f92f5f820c
        .hex d93b9497ad47a62a212bef3574d69be3
        .hex 34e48c0f8de5316c0e3f3d712c5ea122
        .hex a7b0d1a2a8e6c8a94a422e32af10f166
        .hex 4ec11cfaae8aea934509c7f3ed446ebb
        .hex 247c00abf2f75c9195812372c3705752
        .hex 0bf85a02a5687a37e7d7df3013b34fb5
        .hex 55857577a390f59e643e83c041cefe01

; An array of test strings.
Strings:
        .dw @s1, @s2, @s3, @s4
        ; hashes to 0x23
@s1     .db "antidisestablishmentarianism",0
        ; hashes to 0x5E
@s2     .db "supercalifragilisticexpialidocious",0
        ; hashes to 0xA1
@s3     .db "pneumonoultramicroscopicsilicovolcanoconiosis",0
        ; hashes to 0x37
@s4     .db "Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch",0

        .align 16,$00
HexDigits:
        .db "0123456789ABCDEF"