Electrical computers and digital processing systems: processing – Byte-word rearranging – bit-field insertion or extraction,...
Reexamination Certificate
2000-04-07
2003-09-16
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Byte-word rearranging, bit-field insertion or extraction,...
C712S221000, C708S209000
Reexamination Certificate
active
06622242
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computers and more specifically to functional units for processing predetermined types of instructions. The invention particularly provides a circuit or functional unit for use in connection with execution of various types of instructions for rearranging bits of a data word.
BACKGROUND OF THE INVENTION
Computers process data in accordance with instructions. A number of types of instructions rearrange bits of data words in predetermined patterns by, for example, shifting them, rotating them and the like. Typically, such instructions have two operands, with one operand comprising the data word and the other operand providing control information indicating in part how the bits of the data word are to be rearranged. In some cases, all of the bits of the data word are used in the rearranged data word. In other cases, some or all of the bits of the data word are discarded and replaced with bits having predetermined values, such as “zero” or “one.”
Typical examples of such instructions are “unsigned shift left,” “unsigned shift right,” “arithmetic shift right,” “rotate left,” and “rotate right.” If the operand data word consists of “N” bits D
0
D
1
D
2
. . . DN−1 (generally Dn) and “m” is a control operand having a value 0≦m<N, an unsigned shift left instruction results in a shift of the bits of the operand data word to the left by “m” places, with the bits in the “m” bit positions at the right end of the rearranged data word being provided with bits having the value “zero.” That is, the rearranged data word would be Dm Dm+1 . . . DN−1
0
. . .
0
, where the “m” bit positions at the right are provided with bits having the value “zero,” and the bits D
0
. . . Dm−1 of the operand data word are “shifted out” of the left end of the rearranged data word. Essentially, the bit in bit position “k” of the rearranged data word receives the bit in bit position k+m of the operand data word for k+m<N, and otherwise the bit in the rearranged data word receives the value “zero.” Similarly, an unsigned shift right instruction results in a shift of the bits of the operand data word to the right by “m” places, with the bits in the “m” bit positions at the left end of the rearranged data word being provided with bits having the value “zero.” That is, the rearranged data word would be
0
. . .
0
D
0
D
1
. . . DN−1−m, where the “m” bit positions to the left are provided with bits having the value “zero” and the bits DN−m . . . DN−1 of the operand data word are “shifted out” of the right end of rearranged data word. Essentially, the bit in bit position “k” of the rearranged data word receives the bit in bit position k−m of the operand data word, for k−m≧0, and otherwise the bit in the rearranged data word receives the value “zero.” It will be appreciated that, if “m” has the value “zero,” the rearranged data word is the same as the input data word for both types of instructions.
An arithmetic shift right instruction provides a result similar to the unsigned shift right, except that, instead of providing the “m” bit positions at the left end of the rearranged data word with the value “zero,” they are provided with bits having the value in bit position D
0
of the operand data word. That is, the rearranged data word is D
0
. . . D
0
D
0
D
1
. . . DN−1−m, where there are “m” bits D
0
. . . D
0
to the left of bits D
0
D
1
. . . DN−1−m. The arithmetic shift right instruction is typically used with an operand data word which is a signed number, with the D
0
data bit comprising the sign, that is, indicating whether the number is positive or negative, and the remaining bits D
1
. . . DN−1 indicating the absolute value of the number. The arithmetic shift right instruction results in the bits D
1
. . . DN−1 comprising the absolute value being shifted to the right by “m” bit positions, with the bits DN−m . . . DN−1 being shifted out of the rearranged data word, and the sign bit D
0
being extended through the first m+1 bit positions of the rearranged data word.
The rotate left and rotate right instructions are also similar to the unsighted shift left and unsigned shift right instructions, except that, instead of providing bits having the value “zero” in the “in” bit positions of the left and right end of the rearranged data word, respectively, the bits that are “shifted out” of the right and left ends respectively are “shifted into” those “m” bit positions. That is, the rearranged data word provided in response to the rotate left and rotate right instructions would be Dm Dm+1 . . . DN−1 D
0
. . . Dm−1 and DN−m . . . DN−1 D
0
D
1
. . . DN−1−m, respectively. Essentially, for a rotate left instruction, the bit in bit position “k” of the rearranged data word receives the value of the bit in bit position k+m of the operand data word for k+m<N, and otherwise bit “k” of the rearranged data word receives the bit in bit position k+m−N of the operand data word. Similarly, for a rotate right instruction, the bit in bit position “k” of the rearranged data word receives the bit in bit position k−m of the operand data word for k−m>0, and otherwise bit “k” of the rearranged data word receives the bit in bit position k−m+N of the operand data word.
Several other types of bit manipulation instructions have also been proposed, such as, for example, a generalized bit reverse instruction and a generalized shuffle/unshuffle instruction. For a generalized bit reverse instruction bit “k” in the rearranged data word receives the bit in bit position k XOR m of the operand data word. For example, if “m” equals “one,” the rearranged data word is D
1
D
0
D
3
D
2
D
5
D
4
. . . DN−1 DN−2, with successive pairs of bits in bit positions Dn Dn+1 of the operand data word being reversed Dn+1 Dn in the rearranged data word. On the other hand, if “m” equals “two,” the rearranged data word is D
2
D
3
D
0
D
1
D
6
D
7
D
4
D
5
. . . . DN−2 DN−1 DN−4 D−3, with successive pairs of pairs of bits in bit positions Dn Dn+1 Dn+2 Dn+3 of the operand data word being reversed Dn+2 Dn+3 Dn Dn+1 in the rearranged data word. Generally, if “m” is equal to “p−q,” where “p” and “q” are both powers of two, the generalized bit reverse instruction results in a division of the operand data word into sections of size “p” and each section being divided into chunks of size “q”, with the sections in the rearranged data word being in the same order as in the operand data word, but the chunks in each section being in reversed order in the rearranged data word. This is illustrated in the above examples, since for m=1=2−1 (=
2
1
−2
0
), the size of each section was two and the size of each chunk was one, and successive pairs of bits in bit positions Dn Dn+1 of the operand data word were reversed Dn+1 Dn in the rearranged data word. Similarly, for m=2=4−2 (=
2
2
−2
1
), the size of each section was four and the size of each chunk was two, and successive pairs of pairs of bits in bit positions Dn Dn+1 Dn+2 Dn+3 of the operand data word were reversed Dn+2 Dn+3 Dn Dn+1 in the rearranged data word. If, for example, m=7=8−1 (=2
3
−2
0
), the generalized bit reverse instruction results in a rearranged data word in which the bit positions of the bits in each of the operand data word are in reversed order. On the other hand, if m=N−8 (=2
LogN
−2
3
) (where, it will be assumed, Log
2
N is an integer), the generalized bit reverse instruction results in a rearranged data word in which the order of bytes in the operand data word is reversed in the rearranged data word. If m=0, the rearranged data word correspo
Cesari and McKenna LLP
Sun Microsystems Inc.
Tsai Henry W. H.
LandOfFree
System and method for performing generalized operations in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing generalized operations in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing generalized operations in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065877