Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Permutation of Bits in a Bit String

IP.com Disclosure Number: IPCOM000080011D
Original Publication Date: 1973-Oct-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 60K

Publishing Venue

IBM

Related People

Davis, RA: AUTHOR

Abstract

Programmers occasionally require a method for permuting, or reordering, the bits in a bit string. The method usually chosen to accomplish this involves a loop of repeated instructions, which operate on the bit string bit-by-bit. The method described here does not require a loop of repeated instructions, and will execute appreciably faster than other methods for bit strings of nontrivial length. Using the IBM System/360 instruction set, the method is implemented as six instructions with no loops or branches. In this representation, the method is limited to handling bit strings of 256 bits or less, but this limitation applies only to the number of bits produced in the result. Due to the addressing capabilities of S/360, these result bits can be selected from a source field of up to 2048 bits (256 bytes) in length.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Permutation of Bits in a Bit String

Programmers occasionally require a method for permuting, or reordering, the bits in a bit string. The method usually chosen to accomplish this involves a loop of repeated instructions, which operate on the bit string bit-by-bit. The method described here does not require a loop of repeated instructions, and will execute appreciably faster than other methods for bit strings of nontrivial length. Using the IBM System/360 instruction set, the method is implemented as six instructions with no loops or branches. In this representation, the method is limited to handling bit strings of 256 bits or less, but this limitation applies only to the number of bits produced in the result. Due to the addressing capabilities of S/360, these result bits can be selected from a source field of up to 2048 bits (256 bytes) in length.

The method uses, in addition to the six instructions, a permutation vector, two mask fields, a work field, and a translate table. The operation performed is equivalent to the APL operation:

(Image Omitted)

The bits in the input bit string B are selected according to the vector of permutation indices P: R is the result of selecting from the vector B those components whose indices are P. Description of Data Fields: DATA: Contains the bit string to be permuted, left justified. If there are N bits in the string, DATA will be bytes long. For convenience in operation the number of bits is rounded up to the next multiple of eight, since the S/360 instruction set is oriented to eight-bit bytes. WORK: This field is used to contain intermediate results. At the completion of operation, the final result is contained in the low-order B bytes of this field. The WORK field contains one byte for each of the bits in the result, or 8XB bytes total. Except for the final operation, there is a constant one-to-one correspondence between each byte of WORK and a bit of the final result. This correspondence is as follows: The first B bytes of WORK correspond, respectively, to bit 0 of each of the B bytes of the result. The second B bytes correspond, respectively, to bit 1 of each of the B result bytes, and so on. In general, the nth set of B bytes in WORK (0</-n</-7) correspond, respectively, to bit n of each of the B result bytes. P: A vector of one byte numbers. P is equal in length to WORK. Each number in P is used as a byte index to DATA to select a single-data byte. Each number in P must then be in the range

(Image Omitted)

since DATA contains B bytes. P is used to fill WORK with the DATA bytes, so that the ith WORK byte contains the DATA byte...