Method for reversing the bits of a computer data structure
AssigneeHewlett-Packard Company
InventorsMatthew Fischer, Raghuram Kota, Thavatchai Makphaibulchoke, Subramanian Ramesh
Life of this patent
Estimating the term…
Abstract
The bits comprising a computer data structure are reversed rapidly and efficiently using a combination of data partitioning and table look ups. In an exemplary embodiment, the invention is employed in the pre-processing of Advanced Configuration and Power Interface (ACPI) tables stored in little-endian format for use by a big-endian operating system.
Claims12
A method for reversing the order of bits in a bit group comprising a first bit sub-group and a second bit sub-group, the first bit sub-group and the second bit sub-group each comprising at least two bits, the method comprising the steps of:
- (a) isolating the first bit sub-group;
- (b) obtaining a bit-reversed first bit sub-group by addressing a look-up table using the isolated first bit sub-group;
- (c) isolating the second bit sub-group;
- (d) obtaining a bit-reversed second bit sub-group by addressing the look-up table using the isolated second bit sub-group;
- and
- (e) combining the bit-reversed first bit sub-group and the bit-reversed second bit sub-group to generate a bit-reversed bit group.
A method for reversing the order of bits in a computer word comprising an even number of bytes, each byte comprising a first nibble and a second nibble, the first nibble and the second nibble each comprising four bits, the method comprising the steps of:
- (a) selecting from the word a first byte and a second byte that have not yet been bit reversed;
- (b) isolating the first nibble of the first byte;
- (c) obtaining a bit-reversed first nibble of the first byte by addressing a look-up table using the isolated first nibble of the first byte;
- (d) isolating the second nibble of the first byte;
- (e) obtaining a bit-reversed second nibble of the first byte by addressing a look-up table using the isolated second nibble of the first byte;
- (f) combining the bit-reversed first nibble of the first byte and the bit-reversed second nibble of the first byte to generate a bit-reversed first byte;
- (g) isolating the first nibble of the second byte;
- (h) obtaining a bit-reversed first nibble of the second byte by addressing a look-up table using the isolated first nibble of the second byte;
- (i) isolating the second nibble of the second byte;
- (j) obtaining a bit-reversed second nibble of the second byte by addressing a look-up table using the isolated second nibble of the second byte;
- (k) combining the bit-reversed first nibble of the second byte and the bit-reversed second nibble of the second byte to generate a bit-reversed second byte;
- and
- (l) repeating steps (a)-(k) until all bytes of the word have been bit reversed.
A computer-readable storage medium containing program code for reversing the order of bits in a bit group comprising a first bit sub-group and a second bit sub-group, the first bit sub-group and the second bit sub-group each comprising at least two bits, the computer readable storage medium comprising:
- a first program segment configured to isolate the first bit sub-group;
- a second program segment configured to generate a bit-reversed first bit sub-group by addressing a look-up table using the isolated first bit sub-group;
- a third program segment configured to isolate the second bit sub-group;
- a fourth program segment configured to generate a bit-reversed second bit sub-group by addressing the look-up table using the isolated second bit sub-group;
- and
- a fifth program segment configured to combine the bit-reversed first bit sub-group and the bit-reversed second bit sub-group to generate a bit-reversed bit group.
Dependencies are inferred from the claim text.