Methods and apparatus for a bit rake instruction

Abstract

Techniques for performing a bit rake instruction in a programmable processor. The bit rake instruction extracts an arbitrary pattern of bits from a source register, based on a mask provided in another register, and packs and right justifies the bits into a target register. The bit rake instruction allows any set of bits from the source register to be packed together.

We claim:  
     
         1 . A programmable apparatus for executing a bit rake instruction comprising: 
 means for receiving the bit rake instruction;    means for decoding the bit rake instruction defining a source register, a mask register and a target register; and    processing means for extracting a pattern from the source register based on a mask provided from the mask register, and packing and justifying the pattern into the target register.    
     
     
         2 . The programmable apparatus of  claim 1  wherein the processing means comprises an adder tree, a mask path and a data path.  
     
     
         3 . The programmable apparatus of  claim 2  wherein the adder tree, mask path and data path each comprise a plurality of stages.  
     
     
         4 . The programmable apparatus of  claim 3  wherein the mask comprises a number of groups of bits, each group size being a power of two, and wherein the adder tree computes the sum of the number of mask bits in each of the groups.  
     
     
         5 . The programmable apparatus of  claim 4  wherein the plurality of stages of the adder tree comprise adders.  
     
     
         6 . The programmable apparatus of  claim 5  wherein each of the stage's adders includes a sum output and a carry output, the sum output and the carry output controlling corresponding mask path and data path stage groups.  
     
     
         7 . The programmable apparatus of  claim 6  wherein the mask path provides group masks at each stage for controlling selection of corresponding group data in the data path.  
     
     
         8 . The programmable apparatus of  claim 4  wherein the mask path stages and the data path stages comprise a binary shifter and at least one multiplexer.  
     
     
         9 . The programmable apparatus of  claim 8  wherein the depth of the binary shifter increases by one multiplexer with each stage advance.  
     
     
         10 . The programmable apparatus of  claim 9  wherein shifting amounts and group sizes are restricted to powers of two.  
     
     
         11 . The programmable apparatus of  claim 10  wherein the output of each adder has a maximum value which is a power of two.  
     
     
         12 . The programmable apparatus of  claim 8  wherein the at least one multiplexer is controlled by an adder carry bit.  
     
     
         13 . The programmable apparatus of  claim 3  wherein the pattern is packed into the least significant bit positions of the target register.  
     
     
         14 . The programmable apparatus of  claim 13  wherein the unextracted bit positions in the target register are filled by a replication of the most significant extracted bit.  
     
     
         15 . The programmable apparatus of  claim 14  wherein the most significant extracted bit value is determined from the input values by determining a first asserted mask bit and selecting a corresponding data value.  
     
     
         16 . The programmable apparatus of  claim 1  wherein the unextracted bit positions in the target register are filled by sorted unmasked bits.  
     
     
         17 . A method for executing a bit rake instruction comprising: 
 receiving the bit rake instruction;    decoding the bit rake instruction defining a source register, a mask register and a target register;    extracting a pattern from the source register based on a mask provided from the mask register by a processor apparatus; and    packing and justifying the pattern into the target register by a processor apparatus.    
     
     
         18 . The method of  claim 17  wherein the processor apparatus comprises an adder tree, a mask path and a data path.  
     
     
         19 . The method of  claim 18  wherein the adder tree, mask path and data path each comprise a plurality of stages.  
     
     
         20 . The method of  claim 19  wherein the mask comprises a number of groups of bits, each group size being a power of two, the method further comprising the step of: 
 computing the sum of the number of mask bits in each of the groups.  
 
     
     
         21 . The method of  claim 20  wherein the plurality of stages of the adder tree comprise adders.  
     
     
         22 . The method of  claim 21  wherein each of the stage's adders includes a sum output and a carry output, the method further comprising the step of: 
 controlling the corresponding mask path and data path stage groups utilizing the sum output and the carry output.  
 
     
     
         23 . The method of  claim 22  further comprising the step of: 
 providing group masks at each stage of the mask path for controlling selection of corresponding group data in the data path.  
 
     
     
         24 . The method of  claim 20  wherein the mask path stages and the data path stages comprise a binary shifter and at least one multiplexer.  
     
     
         25 . The method of  claim 24  wherein the depth of the binary shifter increases by one multiplexer with each stage advance.  
     
     
         26 . The method of  claim 25  wherein shifting amounts and group sizes are restricted to powers of two.  
     
     
         27 . The method of  claim 26  wherein the output of each adder has a maximum value which is a power of two.  
     
     
         28 . The method of  claim 24  further comprising the step of: 
 controlling the at least one multiplexer by an adder carry bit.  
 
     
     
         29 . The method of  claim 19  further comprising the step of: 
 packing the pattern into the least significant bit positions of the target register.  
 
     
     
         30 . The method of  claim 29  further comprising the step of: 
 filling the unextracted bit positions in the target register with a replication of the most significant extracted bit.  
 
     
     
         31 . The method of  claim 30  wherein the most significant extracted bit value is determined from the input values by determining a first asserted mask bit and selecting the corresponding data value.  32 . The method of  claim 17  wherein the unextracted bit positions in the target register are filled by sorted unmasked bits.