1. Technical Field
The present invention relates in general to a method and system for manipulating a long bit pattern, and in particular to a method and system of transforming a long bit pattern into a matrix having rows and columns of bits. Still more particularly, the present invention relates to transforming a long bit pattern into a matrix having rows and columns of bits, and manipulating such a matrix to perform the equivalent of a rotate operation on such a long bit pattern.
2. Description of the Related Art
Many software algorithms and hardware products utilize conceptual linear or circular shift registers or stacks of bits. Examples of such algorithms include non repeating and/or pseudo random sequence generation utilizing shift registers with feedback. Such sequence generation is used in applications such as calculating CRCs, cipher and signature generation, real-time signal processing, spread spectrum communications, and Monte Carlo modeling. Another use for linear or circular shift registers is for calculating history bit patterns in sliding window data compression. Still other applications for linear or circular shift registers include modeling hardware which incorporates long shift registers, and in pattern recognition applications.
In current software practice, it is taken for granted that multiword bit shift registers are represented in a computer as a linear array of addressable units (words). When the multiword bit patterns are interpreted as integers, this is the order which is convenient for performing multiple precision integer arithmetic. Many modern CPU construction sets include instructions to facilitate the shift or rotation of multi-word bit patterns consisting of a linear array of machine words. One example of such a CPU is the CPU sold under the trademark "RS6000" by IBM Corporation. By repeating machine word shift instructions, a long shift operation or long rotate operation may be synthesized. For example, on a left long shift, all bits but the leftmost bit of a minimum addressable unit or word are moved one position to the left, except that the leftmost bit of a given word is placed into the rightmost bit of the next word. And for a right long shift, the operation described above is reversed. To operate such a linear array of machine words as a linear queue, or FIFO (First-in, First-Out), new bits may be put into the rightmost bit for a left long shift and removed from the leftmost bit. For a right long shift, new bits are entered on the left and removed on the right. When data is entered and removed from the same end of the data structure, such a data structure is usually referred to as a "stack." In a circular operation, the leftmost bit of the leftmost word is considered to be adjacent to the rightmost bit of the rightmost word. In the case of circular operations, the long shift operations described above become long rotate operations.
FIG. 1 illustrates a rotate left operation which is performed on a 16-bit bit pattern that is stored in four 4-bit words. To simplify this example, a CPU that can perform a 4-bit rotate operation is utilized. That is, the CPU has a shift operand length of 4 bits. Thus, to perform a rotate left operation on four 4-bit words, the CPU must perform a series of shift operations on the 4-bit operands in order to make the bit pattern 20 of FIG. 1 into bit pattern 22. Such a series of shift operations is illustrated in the steps of FIG. 2.
In some figures in this disclosure, bit locations, in either a word or a register, are illustrated by a box. These bit locations are utilized to store either a "1" or a "0." Numerals within the boxes, however, indicate a reference numeral assigned to a particular bit in a bit pattern. Such numerals are not stored in the bit locations. Reference numerals are used in the examples to illustrate what happens to a particular bit in the bit pattern from one step in the process to another.
FIG. 2 illustrates the conventional steps for executing a 1-bit left rotate of a 16-bit bit pattern composed of four 4-bit words. Such a process is illustrated here as five steps. However, those persons skilled in the art should recognize that several machine instructions may be necessary to manipulate the bits in one step to resemble the bits in a subsequent step.
In step 1, the leftmost bit of WORD 3, bit-15, is copied to the CARRY bit location. In step 2, WORD 0 has been shifted left, with the CARRY bit placed in the rightmost bit of WORD 0, and the leftmost bit of WORD 0 placed into the CARRY bit. In step 3, WORD 1 has been shifted left, with the CARRY bit placed in the rightmost bit of WORD 1, and the leftmost bit of WORD 1 placed into the CARRY bit. In step 4, WORD 2 has been shifted left, with the CARRY bit placed in the rightmost bit of WORD 2, and the leftmost bit of WORD 2 placed in the CARRY bit. And finally, in step 5, WORD 3 has been shifted left, with the CARRY bit placed in the rightmost bit of WORD 3.
Those persons skilled in the art will appreciate that as more bits are added to the bit pattern, the number of steps to perform a rotate on such a bit pattern increases proportionately.
In FIG. 3, there is a sequence of C-language instructions to perform the 1-bit left rotate as illustrated in FIGS. 1 and 2. In this code, there is a "DO-loop" which is executed a number of times proportional to the number of words or pattern groups that comprise the bit pattern. Thus, the number of instructions to accomplish the one-bit rotate is proportional to the number of bits to be rotated divided by the shift operand length, which is usually the word length of the shift registers in the CPU.