	.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
