Browse Prior Art Database

Fast Bit Addressing Algorithm

IP.com Disclosure Number: IPCOM000109478D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 1 page(s) / 44K

Publishing Venue

IBM

Related People

Linzer, E: AUTHOR

Abstract

Most of today's computers allow for the addressing of individual bytes but not individual bits. The following algorithm can be used to address bits in software.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 85% of the total text.

Fast Bit Addressing Algorithm

      Most of today's computers allow for the addressing of
individual bytes but not individual bits.  The following algorithm
can be used to address bits in software.

      The algorithm that we describe assumes a machine capability to
load and store an eight-byte data type quickly.  The algorithm
consists of three stages.
1.   In the first stage, a lookup table of size 256 X 8 bytes long
is created.  (We assume a row-major representation of 2-D arrays; if
a column-major representation is used, an 8 X 256 table would be
used.)  The 8-bytes of the kth row are the binary representation of
k.  Thus the jth byte of the kth row has value 1 if the jth
bit of the 8-bit representation of k is equal to 1 and zero
otherwise.  For example, the first five rows of the table are
      o    0 0 0 0 0 0 0 0
      o    0 0 0 0 0 0 0 1
      o    0 0 0 0 0 0 1 0
      o    0 0 0 0 0 0 1 1
      o    0 0 0 0 0 1 0 0
      We will call this table T.  The table T is created once and can
be used to process a bit stream of arbitrary length.
2.   Let A be an array of length N bytes that contains the original
bit stream, and let B be a scratch array of length 8N bytes.  For
0<=i<N-1, row A(i) of table T is loaded as an 8-byte data type (e.g.,
a double precision floating point word) and stored as an 8-byte data
type beginning at byte 8*i of the array B.  The result is that the
ith byte of the array B is...