Prefix comparator
AssigneeLSI Logic Corporation
InventorsAlexander E. Andreev, Ranko Scepanovic
Life of this patent
Estimating the term…
Abstract
A longest common subprefix of two binary words p1 and p2 is identified based on bit strings ip1 and ip2 which are extensions of p1 and p2, and binary words n1 and n2 that define the length of p1 and p2. The bit strings and words are processed to set a “greater” output if p1>p2 and to set an “equal” output if p1=p2. A mask having a consecutive string of most significant bits having a first logical value is constructed to identify the matching subprefixes of p1 and p2.
Claims20
Apparatus for identifying a longest common subprefix of two binary prefixes p1 and p2 comprising:
- means defining p1 as binary word ip1, n1 and p2 as binary word ip2, n2, where ip1 and ip2 are of equal length and each is an extension of the respective p1 and p2, and n1 and n2 represent the length of p1 and p2, respectively;
- a comparator for responsive to ip1 and ip2 to provide a first bit string identifying bits of ip1 and ip2 that match in value;
- a decoder responsive to n1 and n2 to form a second bit string identifying the length of the shortest of p1 and p2;
- and
- a processor responsive to the first and second bit strings to derive a mask having a consecutive string of most significant bits representing the matching subprefixes of p1 and p2.
A process for identifying a longest common subprefix of two binary prefixes p1 and p2 comprising steps of:
- a) defining p1 as ip1, n1 and p2 as ip2, n2, where ip1 and ip2 are of equal length and each is an extension of the respective p1 and p2, and n1 and n2 represent the length of p1 and p2;
- b) processing ip1 and ip2 to form a first bit string having a first logical bit value corresponding to bits of ip1 and ip2 that match in value;
- c) decoding n1 and n2 to form a second bit string having the first logical value matching the length of the shortest of p1 and p2;
- and
- d) processing the bit strings produced by steps (b) and (c) to derive a mask having a consecutive string of most significant bits representing the matching subprefixes of ip1 and ip2.
A computer usable medium having a computer readable program embedded therein for addressing data to identify common subprefixes of two binary prefixes p1 and p2 by a computer, the computer readable program in the computer readable medium comprising:
- first computer readable program code for causing the computer to define p1 as binary word ip1 , n1 and p2 as binary word ip2, n2, where ip1 and ip2 are of equal length and each is an extension of the respective p1 and p2, and n1 and n2 represent the length of p1 and p2, respectively;
- second computer readable program code for causing the computer to process ip1 and ip2 to form a first bit string identifying bits of ip1 and ip2 that match in value;
- third computer readable program code for causing the computer to decode n1 and n2 to form a second bit string identifying the length of the shortest of p1 and p2;
- and
- fourth computer readable program code for causing the computer to process the first and second bit strings to derive a mask having a consecutive string of most significant bits representing the matching subprefixes of ip1 and ip2.
Dependencies are inferred from the claim text.