A Nim implementation of Cyclic Polynomial Hash, aka BuzHash
A Cyclic Polynomial hash is a type of Rolling hash which avoids multiplication by using circular shifts and xoring. For more information regarding Cyclic Polynomial hasing please refer to wiki's article on Rolling Hash
Types
CyclicHash[H; C] = object hashValue*: H n: int wordSize: int hasher: CharacterHash[H, C] maskOne: H myR: int maskN: H
Procs
proc newCyclicHash[H, C](myN: int; myWordSize: int): CyclicHash[H, C] {...}{.inline.}
-
Creates a new Cyclic Hash with a quasi-random[*]_ initial has value of size myWordSize in bits.
Asserts that the bitsize of the required hash value is not smaller than the bitsize of myWordSzie
proc newCyclicHash[H, C](myN: int; seedOne, seedTwo: int; myWordSize: int): CyclicHash[H, C] {...}{.inline.}
-
Creates a new Cyclic Hash with a random[*]_ initial has value of size myWordSize in bits.
Asserts that the bitsize of the required hash value is not smaller than the bitsize of myWordSzie
proc trueHash[H, C](y: CyclicHash[H, C]; c: seq[char]): H {...}{.inline.}
- Hash complete sequence of char without the need to update. This is a helper proceedure to test whether the update proceedure below yeilds correct results in unit testing
proc update[H, C](y: var CyclicHash[H, C]; outChar, inChar: char) {...}{.inline.}
- Updates the rolling hash after shifting left and xoring hash value of outChar add inChar
proc reverseUpdate[H, C](y: var CyclicHash[H, C]; outChar, inChar: char) {...}{.inline.}
proc eat[H, C](y: var CyclicHash[H, C]; inChar: char) {...}{.inline.}
- Move rolling hash forward by shifting left and xoring the hash value of the new inChar
proc hashPrepend[H, C](y: var CyclicHash[H, C]; x: char): H {...}{.inline.}
- Prepends a rolling hash by adding a hashed x into the front of the rolling hash sequence
proc hashExtend[H, C](y: CyclicHash[H, C]; x: char): H {...}{.inline.}
- Extends a rolling hash by adding a hashed x into the end of the rolling hash sequence
proc reset[H, C](y: var CyclicHash[H, C]) {...}{.inline.}
- Reset the hash values of rolling hash to 0