Loading patent…
AssigneeInternational Business Machines Corporation
InventorsJohn L. Carter, George Markowsky, Mark N. Wegman
Estimating the term…
The invention comprises a method and apparatus for performing a hashing operation on an N bit number under control of a prespecified N bit hashing constant which comprises performing N/K finite field partial multiplications of the object to be hashed by the hashing constant, utilizing K logic and combinatorial circuits all of which operate in parallel to completely evaluate the number in N/K operations. Another feature of the present invention is that the hashing constant loaded into the system may be changed at will with a resultant changing of the hashing characteristics to suit a particular class of objects to be hashed. This is done by a "select" operation. In the "select" operation, the hashing constant is sequentially loaded into said K logic and combinatorial circuits, each of which comprises a feedback shift register (FSR), said feedback shift registers being so configured that at the end of K operational sequences each of said feedback shift registers contains said hashing constant shifted and permuted in accordance with the particular feedback configuration of said register, a number of bits proportional to its location in the sequence of feedback shift registers, such that the hashing constant in the shift register FSR.sub.i will be shifted in a predetermined direction (i-1) N/K bit positions. Each of the operational sequences referred to above comprises a hashing sequence which includes N/K shifts of the feedback shift registers.
A hashing generator for performing a hashing operation on an N bit operand as a function of a predetermined N bit hashing constant, said generator comprising a shift register for receiving the operand to be hashed, a register for receiving and storing the hashing constant, K feedback shift registers wherein K is an integer factor of N, means for loading each of said K feedback shift registers with said hasing constant shifted from the low to the high order direction N/K-bit positions with respect to each of its adjacent feedback shift registers, means including a result register and combinatorial circuit means for accumulating the contents of each of said K feedback shift registers as a function of the binary state of an associated bit in said operand shift register together with the results of the immediately preceding accumulation and means for sequentially shifting all of said K feedback shift registers and said operand shift register and successively accumulating the interim results in said result register a total of N/K times to perform a complete hashing operation.
A hashing generator for performing a hashing operation on an N bit operand as a function of a predetermined N bit hashing constant, said generator comprising a shift register for receiving the operand to be hashed, a register for receiving and storing the hashing constant, K feedback shift registers wherein K is not an integer factor of N, means for loading each of said K feedback shift registers with said hashing constant shifted from the low to the higher order direction L bit positions with respect to each of its adjacent feecback shift registers where L is the greatest integer less than N/K, means for loading a zero into the high order bit position of the operand shift register each time a shift is performed, means including a result register and combinatorial circuit means for accumulating the contents of each of said K feedback shift registers as a function of the binary state of an associated bit in said operand shift register together with the results of the immediately preceding accumulation and means for sequentially shifting all of said K feedback shift registers and said operand shift register and successively accumulating the interim results in said result register a total of L times to perform a complete hashing operation.
Dependencies are inferred from the claim text.