; HHash.asm

;	Last modified May 26, 1979  6:39 PM by Taft

.ent HHash

	.srel

HHash:	.HHash

	.nrel

; HHash(logTableSize,key,lvProbe) - Generate a hash probe.
; Multiplicative Hash, Knuth vol3 p 509.
; Stores the initial probe in @lvProbe and returns the second hash
; (increment) as its value.  Both results are in the range
; [0..2↑logTableSize), and the second hash is relatively prime
; to 2↑logTableSize.  logTableSize must be le 8.

; let p ← (M*key) mod 2↑16, where M is a carefully-chosen prime.
; stores the high logTableSize bits of p right-justified in
; @lvProbe.  then returns the next logTableSize bits of p,
; right-justified, with 1 added if necessary to make it odd.

.HHash:
	sta 3 1 2		; save return
	sta 0 2 2		; store logRTSize for later
	sub 0 0
	mov 2 3			; save stack ptr
	lda 2 M
	mul			; ac1 ← (M*key) mod 2↑16
	mov 3 2			; restore stack ptr
	mov 1 0			; ac0 ← product
	lda 1 2 2		; get logTableSize
	cycle 0			; ac0 ← ac0 lcy ac1
	mov 0 3			; high bits now right-justified
	mkone 0 0		; compute 2↑logTableSize
	lda 1 2 2		; get logTableSize again
	cycle 0
	neg 0 0			; subtract 1 to make mask
	com 0 0
	lda 1 2 2		; get logTableSize again
	sta 0 2 2		; save mask
	and 3 0			; mask high logTableSize bits
	sta 0 @3 2		; @lvProbe ← initial probe
	mov 3 0			; unmasked product to ac0
	cycle 0			; ac0 ← ac0 lcy ac1
	lda 3 2 2		; mask next logTableSize bits
	and 3 0
	movr# 0 0 snc		; ensure the result is odd
	 inc 0 0
	lda 3 1 2		; return second hash
	jmp 1 3

M:	40501.		; 2↑16/golden ratio

	.end