Efficient bit scan mechanism

Details Efficient bit scan mechanism Efficient bit scan mechanism

1999-03-22

2001-01-09

Young, Brian (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from run length limited codes

C345S501000, C712S300000

Reexamination Certificate

active

06172623

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates in general to enhance efficiency in data processing systems, and in particular to enhance efficiency in performing data bits processing functions. Still more particularly, the present invention relates to a method and an apparatus of enhancing processing efficiency in a data processing system for locating the most, or least, significant bit in a bit string comprising plurality of data bits.
In some computer operations or instructions, the most or least significant set bit on a data word or an array is requested by either an assembly instruction or other component in a microprocessor system. A set bit is defined conventionally as a bit set to “1”. For example, in some matrix calculations, leading zeros of a bit-string is preferably to be eliminated in order to conserve memory space. Therefore, the first most significant set bit is needed to be located in order to truncate all the leading zeros. In another example such as floating point processing, leading zeros are generally detected and eliminated. Therefore, a method of efficiently detecting the first most., or least, significant set bit of a group of data bits is desired.
In the Intel (TM) x86 instruction set, there is an instruction Bit Scan Forward (“B SF”) for searching an operand for the least significant set bit (“1 ” bit). According to the Intel (TM) x86 instruction set, if a least significant 1 bit is found, its bit index is stored in the destination location. The bit index is an unsigned offset from bit
0
of the source operand. If the contents source operand does not contain any set bit, the contents of the destination operand is undefined. For example, in a 32-bit bit-string, the destination operand will be 5 bits long (i.e. S
4
,S
3
,S
2
,S
1
,S
0
).
The following algorithm is used to illustrate the detailed operation of the BSF in a conventional processor:
IF SRC = 0
* No set bit?
THEN
ZF <−− 1;
* Set zero bit
DEST is undefined;
* Result undefined
ELSE
ZF <−− 0;
* Reset zero bit
temp <−− 0;
* Initialize temp reg
WHILE Bit(SRC, temp) = 0
* Bit set?
DO
temp <−− temp + 1;
* Increment temp
DEST <−− temp;
* Update result
OD;
* Loop exit
FI;
* Finish
As shown in the algorithm, the processor tests each bit at a time and then proceeds to the next bit if the condition is not met. As it can be instantly recognized, extensive time delay will occur if the first least significant set bit is in the higher bits range.
Another example is the Intel (TM) instruction BSR where the most significant set bit is detected. The algorithm is similar to the BSF as shown above, with the replacing of the least significant bit with the most significant bit. However, the same timing penalty will be incurred when the set bit is located in some undesirable positions.
Therefore, a more efficient method of locating the most or least significant set bit is desired.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to disclose a bit scan method and apparatus capable of locating the first most/least significant set bit in a bit-string.
It is another object of the present invention to disclose a bit scan mechanism capable of preforming the bit scan in a few clock cycles.
It is yet another object of the present invention to disclose a bit scan mechanism being able to scale to any number of data bits in the bit-string.
It is a further object of the present invention to disclose a bit scan mechanism using minimum number of components.
The present invention discloses a method and apparatus to locate the first most/least significant set bit in a bit-string by breaking down the bit-string into a plurality of shorter sub-strings. After dividing the bit-string into shorter sub-strings, boolean operations can be performed directly to the sub-strings for determining the location of the most, or least, significant set bit. Furthermore, this method can be repeatedly performed to reduce the length of the shorter sub-string when the most/least significant sub-string is located. This method of repeatedly dividing the bit-string greatly reduces the speed of locating the set bit.
These and other objects and features of the invention will be better understood by reference to the detailed description which follows taken together with the drawings in which like elements are referred to by like designations throughout the several views.


REFERENCES:
patent: 5177482 (1993-01-01), Cideciyan et al.
patent: 5335332 (1994-08-01), Christopher, Jr. et al.
patent: 5778074 (1998-07-01), Garcken et al.
patent: 6100905 (2000-08-01), Sidwell
Intel,Intel Architecture Software Developer's Manual, “Instruction Set Reference,” vol. 2, Order No. 243191, (1997) pp. 3-25 to 3-28.

Affiliated with

Also associated with

Rating

Efficient bit scan mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient bit scan mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient bit scan mechanism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2513186