Code: Select all
#define PROBELIMIT 1000
#define UNKNOWN -1
type KNOW
mask as ulongint
table(any) as ulongint
bvalues(any) as ubyte
hkey as ulongint
hindex as ulongint
hprobe as ulongint
declare constructor(size as ulongint)
declare function getByteAfterIndex(x as ubyte ptr,index as ulongint) as long
declare sub setByteAfterIndex(x as ubyte ptr,index as ulongint,byteAfter as ubyte)
declare function find() as longint
declare sub resethash()
declare sub nexthash(x as ubyte)
end type
'size must be a power of 2 (eg. 2,4,8,16,...)
constructor KNOW(size as ulongint)
this.mask=size-1
if (size and mask)<>0 then error(1)
redim this.table(mask) as ulongint
redim this.bvalues(mask) as ubyte
end constructor
function KNOW.find() as longint
dim as ulongint idx=hindex,probe=hprobe or 1,key=iif(hkey=0,1,hkey)
for i as ulong =1 to PROBELIMIT
dim as ulongint j=idx and mask
dim as ulongint t=table(j)
if t=0 or t=key then return j
idx+=probe
next
return UNKNOWN
end function
'returns UNKNOWN if it can't find anything suitable
function KNOW.getByteAfterIndex(x as ubyte ptr,index as ulongint) as long
resethash()
nexthash(x[index])
dim as longint idx=find()
if idx=UNKNOWN then return UNKNOWN
if table(idx)=0 then return UNKNOWN
dim as ubyte res=bvalues(idx)
while index<>0
index-=1
nexthash(x[index])
idx=find()
if idx=UNKNOWN then exit while
if table(idx)=0 then exit while
res=bvalues(idx)
wend
return res
end function
sub KNOW.setByteAfterIndex(x as ubyte ptr,index as ulongint,byteAfter as ubyte)
dim as long res=getByteAfterIndex(x,index)
if res=byteAfter then return
dim as longint idx=find()
if idx=UNKNOWN then return
if table(idx)=0 then
table(idx)=iif(hkey=0,1,hkey)
bvalues(idx)=byteAfter
end if
end sub
sub KNOW.resethash()
hkey=0
hindex=0
hprobe=0
end sub
sub KNOW.nexthash(x as ubyte)
hkey+=x+&he8e92631f2614fe1ULL
hindex+=x+&h18373fe1619628abULL
hprobe+=x+&h57eba727a2c23d17ULL
hkey*=2862933555777941757ull
hindex*=3202034522624059733ull
hprobe*=3935559000370003845ull
hkey xor=hkey shr 31
hindex xor=hindex shr 31
hprobe xor=hprobe shr 31
end sub
dim as string s="I am a bronze maiden and I stand on Midas' tomb, For as long as water flows and tall trees bloom, Remaining right here on his much-lamented tomb, I will announce to passersby that Midas is buried in this place."
s+=s
dim as KNOW k=KNOW(512)
for i as long=0 to len(s)-2
k.setByteAfterIndex(strptr(s),i,asc(s,i+2))
print chr(asc(s,i+2));
next
print
print
s="b"
for i as long=0 to 200
dim as long b=k.getByteAfterIndex(strptr(s),i)
if b=UNKNOWN then b=32
print chr(b);
s=s+chr(b)
next