US 6,715,066 B1Granted

System and method for arranging bits of a data word in accordance with a mask

AssigneeSun Microsystems, Inc.

InventorGuy L. Steele, Jr.

Life of this patent

Estimating the term…

Abstract

A system is described for rearranging data units of a data word in accordance with a mask word, the mask word having a plurality of mask bits each associated with a data unit, each mask bit having one of a set condition or a clear condition. The system includes a control module and a shifter module. The control module is configured to generate, for each mask bit, values identifying the number of mask bits to the left of the respective mask bit which have one of the set condition or the clear condition and the number of mask bits to the right of the respective mask bit which have the other of the set condition or the clear condition. The shifter module is configured to shift data units of the data word in accordance with the values generated by the control module.

Claims43

Dependent claims

For producing from input signals representing an input data word and a mask word an output signal representing an output data word, the input and output data words comprising N data units Dn, and Zn, respectively, where n=0, 1, 2, . . . , N−1, the mask word comprising, for each data unit Dn in the input word and thereby for the corresponding data unit Zn in the output word, a separate mask bit Mn associated therewith that assumes one of a right-indicating value and a left-indicating value, a centrifuge circuit comprising a control module configured to generate, for each mask bit Mn such that n<N−1, a right-sum output representing the number Rn of mask bits Mk such that k>n that have the left-indicating value and further comprising a shifter module, responsive to the mask word and the right-sum outputs, to provide, for each n such that mask bit Mn that has the right-indicating value, the input word's data unit Dn as the output word's data unit Zd, where d=n+Rn, wherein:

A) the shifter module comprises, for each data unit Zn in the output data word, a respective shift column Cn associated therewith and thereby with the respective mask bit Mn and the respective data unit Dn in the input data word, each shift column Cn generating the respective data unit Zn and including a right series of J shift elements Sj, where 1≦j≦J, each shift element Sj being connected to receive a respective pass input, providing a respective shift-element output, and being associated with a respective shift value sj such that, for j < J , s j + 1 > ∑ k = 1 J ⁢ s k ;
B) in the right series of each shift column Cn:
i) shift element S1 receives Dn as its pass input if mask bit Mn has the right-indicating value;
ii) each other shift element Sj receives as its pass input the output of shift element Sj−1 in the same series;
C) in the right series of each shift column Cn of at least a plurality of the shift columns, each shift element Sj of a plurality of the shift elements includes a multiplexer that:
i) receives as its shift input:
a) if j=1, the input word's data unit Dd if mask bit Md has the right-indicating value, where d=n−sj;
and
b) if j>1, the shift-element output of the shift element Sj−1 in the right series of column Cd, where d=n−sj;
ii) makes a choice between its inputs in accordance with the value of Rd, where d=n−sj;
and
iii) forwards its input thus chosen as shift element Sj's output;
D) for each n, the sum of the shift values sj associated with the multiplexers that choose their shift inputs in response to Rn is Rn;
and
E) for each n such that n≧N−RT, where RT is the total number of bits in the mask word having the right-indicating value, the shift module provides as Zn the output of the shift module SJ in the right series of shift column Cn.

12 more elements

For producing an output data word comprising data units Zn by rearranging data units Dn of an input data word, where n=1, 2, . . . , N−1 and Dn and Zn are respectively considered to be to the left of Dn+1 and Zn+1, in accordance with a mask word, the mask word including N mask bits Mn, each mask bit Mn being associated with respective data unit Dn, and having a respective one of two possible mask-bit values, namely, a left-indicating mask-bit value and a right-indicating mask-bit value, a data-unit-rearrangement circuit comprising:

A) a control module configured to generate, for at least each mask bit Mn other than mask bit MN−1, a right-sum output representing the number Rn of mask bits to the right of the respective mask bit that have the left-indicating mask-bit value, wherein:
i) the control module includes an array of adders that are organized in a series of layers and generate the right-sum outputs associated with at least a plurality of the mask bits;
ii) each of at least a plurality of the adders in the first layer of the series of layers receives a respective series of consecutive ones of the mask bits as its adder inputs and generates therefrom a respective adder output identifying the number of the mask bits in that series of mask bits that have the left-indicating value;
and
iii) each adder in each subsequent layer receives as at least one of its adder inputs the adder output generated by an adder in the previous layer, and each of at least a plurality of the adders in each subsequent layer generates therefrom a respective adder output identifying the number of mask bits in a respective series of consecutive ones of the mask bits that have the left-indicating value, the length of the series of mask bits associated with each such adder being greater than that associated with any adder from which it draws one of its inputs;
and
B) a shifter module configured to shift data units of the input data word in accordance with the right-sum outputs.

4 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

A) the shifter module comprises, for each data unit Zn in the output data word, a respective shift column Cn associated therewith and thereby with the respective mask bit Mn and the respective data unit Dn in the input data word, each shift column Cn generating the respective data unit Zn and including a right series of J shift elements Sj, where 1≦j≦J, each shift element Sj being connected to receive a respective pass input, providing a respective shift-element output, and being associated with a respective shift value sj such that, for j < J , s j + 1 > ∑ k = 1 J ⁢ s k ;
B) in the right series of each shift column Cn:
i) shift element S1 receives Dn as its pass input if mask bit Mn has the right-indicating value;
ii) each other shift element Sj receives as its pass input the output of shift element Sj−1 in the same series;
C) in the right series of each shift column Cn of at least a plurality of the shift columns, each shift element Sj of a plurality of the shift elements includes a multiplexer that:
i) receives as its shift input:
a) if j=1, the input word's data unit Dd if mask bit Md has the right-indicating value, where d=n−sj;
and
b) if j>1, the shift-element output of the shift element Sj−1 in the right series of column Cd, where d=n−sj;
ii) makes a choice between its inputs in accordance with the value of Rd, where d=n−sj;
and
iii) forwards its input thus chosen as shift element Sj's output;
D) for each n, the sum of the shift values sj associated with the multiplexers that choose their shift inputs in response to Rn is Rn;
and
E) for each n such that n≧N−RT, where RT is the total number of bits in the mask word having the right-indicating value, the shift module provides as Zn the output of the shift module SJ in the right series of shift column Cn.

12 more elements