Skip to content

Instantly share code, notes, and snippets.

@adiee5

adiee5/fnv.asm

Last active December 14, 2025 22:40
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save adiee5/2fe93449167d6670cf5b38f34c12a729 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save adiee5/2fe93449167d6670cf5b38f34c12a729 to your computer and use it in GitHub Desktop.
Download ZIP
6502 implementation of FNV-1a hashing algorithm, ca65 assembler
Raw
fnv.asm
; 6502 implementation of the FNV-1a hash algorithm. It calculates a 32 bit hash and also casts the hash into a 16 bit value stored in CPU regs upon returning
.export fnv
; CONFIGURATION:
; feel free to modify bellow symbols on a way that suit your needs
; ----------------------------------------------------------------------
; two 32 bit variables, preferably in Zero Page in order to improve execution speed
hash=2
temp=hash+2*2
; set this to 1 in order to read data from a pointer variable
; set this to 0 in order to read data from a statically allocated buffer
PTRACCESS=0
.if PTRACCESS
; a Zero Page variable that stores an address of the buffer
fnvptr=temp+2*2
.else
; a statically allocated buffer that contains data to be hashed.
; with the way it's currently defined in this code snippet, user needs to create a buffer in the user code, call it `fnvbuff`
; and then export it using the .export directive. The bellow .import directive can be replaced with a normal symbol definition
; if that's more intuitive than the actions explained above
.import fnvbuff
.endif
; CODE:
; -------------------------------------------------------------------------
; macros that implement PHY and PLY instructions that are absent on older CPUs (most 6502 CPUs actually)
.if .not .ismnemonic(ply)
.macro ply
pla
tay
.endmacro
.endif
.if .not .ismnemonic(phy)
.macro phy
tya
pha
.endmacro
.endif
OFFSET=2166136261
; FNV-1a hashing function
; Input: buffer that contains a zero-terminated string of bytes.
; Its address is either provided in the pointer variable defined above as `fnvptr` or it's statically assigned to a symbol `fnvbuff`,
; depending on the configuration above
; Output: A 32 bit hash can be read from the 32 variable defined in the configuration as `hash`.
; The function also outputs a 16 bit hash in registers A and X - X stores a low byte and A stores high byte.
fnv:
lda #OFFSET>>24
sta hash+3
lda #^OFFSET
sta hash+2
lda #>OFFSET
sta hash+1
lda #<OFFSET
sta hash
ldy #0
mainloop:
.if PTRACCESS
lda (fnvptr), Y
.else
lda fnvbuff, Y
.endif
bne work
; XA = (hash>>16) eor (hash & $FFFF)
lda hash
eor hash+2
tax
lda hash+1
eor hash+3
rts
work:
eor hash
sta hash ; hash=hash^fnvbuff[x]
phy
ldx #3
@cp:
lda hash, X
sta temp, X
dex
bpl @cp
; hash+(temp<<24)
clc
lda temp
adc hash+3
sta hash+3
; hash+(temp<<8)
clc
.repeat 3, G
lda temp+G
adc hash+1+G
sta hash+1+G
.endrepeat
asl temp ; <<1
.repeat 3, G
rol temp+1+G
.endrepeat
clc
.repeat 4, G
lda temp+G
adc hash+G
sta hash+G
.endrepeat
ldy #1
@bigloop:
ldx #3 ; <<4, <<7
@l1:
asl temp
.repeat 3, G
rol temp+1+G
.endrepeat
dex
bne @l1
clc
.repeat 4, G
lda temp+G
adc hash+G
sta hash+G
.endrepeat
dey
beq @bigloop
ply
iny
jmp mainloop
Raw
fnv816.asm
; 65c816 implementation of the FNV-1a hash algorithm. It calculates a 32 bit hash and also casts the hash into a 16 bit value stored in CPU regs upon returning
.export fnv816
; CONFIGURATION:
; feel free to modify bellow symbols on a way that suit your needs
; ----------------------------------------------------------------------
.p816
; two 32 bit variables, preferably in Zero Page in order to improve execution speed
hash=2
temp=hash+2*2
; set this to 1 in order to read data from a (24-bit) pointer variable
; set this to 0 in order to read data from a statically allocated buffer
; set this to 2 in order to read data from a place Y points to
PTRACCESS=0
.if PTRACCESS=1
; a Zero Page variable that stores an address of the buffer
fnvptr=temp+2*2
.elseif PTRACCESS=0
; a statically allocated buffer that contains data to be hashed.
; with the way it's currently defined in this code snippet, user needs to create a buffer in the user code, call it `fnvbuff`
; and then export it using the .export directive. The bellow .import directive can be replaced with a normal symbol definition
; if that's more intuitive than the actions explained above
.import fnvbuff
.elseif PTRACCESS!=2
.error "Incorrect PTRACCESS value"
.endif
; CODE:
; -------------------------------------------------------------------------
; helpers for setting accumulator and index registers width
.macro _a8
sep #%00100000 ; 8-bit accumulator
.a8
.endmacro
.macro _a16
rep #%00100000 ; 16-bit accumulator
.a16
.endmacro
.macro _i8
sep #%00010000 ; 8-bit index
.i8
.endmacro
.macro _i16
rep #%00010000 ; 16-bit index
.i16
.endmacro
.macro _ai8
sep #%00110000 ; 8-bit accumulator and index
.a8
.i8
.endmacro
.macro _ai16
rep #%00110000 ; 16-bit accumulator and index
.a16
.i16
.endmacro
OFFSET=2166136261
; FNV-1a hashing function
; Input: buffer that contains a zero-terminated string of bytes.
; Its address is either provided in the pointer variable defined above as `fnvptr` or it's statically assigned to a symbol `fnvbuff`,
; depending on the configuration above
; Output: A 32 bit hash can be read from the 32 variable defined in the configuration as `hash`.
; The function also outputs a 16 bit hash in the A register
fnv816:
_ai16
lda #.hiword(OFFSET)
sta hash+2
lda #.loword(OFFSET)
sta hash
.if PTRACCESS=0
ldx #0
.elseif PTRACCESS!=2
ldy #0
.endif
mainloop:
_a8
.if PTRACCESS=1
lda [fnvptr], Y
.elseif PTRACCESS=2
lda 0, Y
.else
lda f:fnvbuff, X
.endif
bne work
; A = (hash>>16) eor (hash & $FFFF)
_a16
lda hash
eor hash+2
rts
work:
eor hash
sta hash ; hash=hash^fnvbuff[x]
.if PTRACCESS=0
phx
.else
phy
.endif
_a16
lda hash+2
sta temp+2
lda hash
sta temp
; hash+(temp<<24)
_ai8
clc
adc hash+3
sta hash+3
; hash+(temp<<8)
clc
lda temp
adc hash+1
sta hash+1
_a16
lda temp+1
adc hash+2
sta hash+2
asl temp ; <<1
rol temp+2
clc
.repeat 2, G
lda temp+G*2
adc hash+G*2
sta hash+G*2
.endrepeat
ldy #1
@bigloop:
ldx #3 ; <<4, <<7
@l1:
asl temp
rol temp+2
dex
bne @l1
clc
.repeat 2, G
lda temp+G*2
adc hash+G*2
sta hash+G*2
.endrepeat
dey
beq @bigloop
_i16
.if PTRACCESS=0
plx
inx
.else
ply
iny
.endif
jmp mainloop
Raw
testhash.asm
.import fnv
.export fnvbuff
cout :=$FFD2
r0=2
.data
tmp: .res 1
.code
jsr fnv
jsr PrHex
txa
jsr PrHex
lda #' '
jsr cout
ldx #3
:
lda r0, x
stx tmp
jsr PrHex
ldx tmp
dex
bpl :-
rts
; This is taken from https://www.beebwiki.mdfs.net/Number_output_in_6502_machine_code
; I honestly have no idea whether am I allowed to use this code, but it's here solely for debugging purposes
PrHex:
PHA ; Save A
LSR
LSR
LSR
LSR ; Move top nybble to bottom nybble
JSR PrNybble
PLA
AND #15 ; Mask out original bottom nybble
PrNybble:
SED
CLC
ADC #$90 ; Produce &90-&99 or &00-&05
ADC #$40 ; Produce &30-&39 or &41-&46
CLD
jmp cout ; Print it
.rodata
fnvbuff: .byte "toki", 0
Raw
‌LICENSE
Copyright 2025 Adiee5
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment