Method and system for performing permutations using permutation instructions based on butterfly networks

Abstract

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. The permute instructions are based on a Benes network comprising two butterfly networks of the same size connected back-to-back. Intermediate sequences of bits are defined that an initial sequence of bits from a source register are transformed into. Each intermediate sequence of bits is used as input to a subsequent permutation instruction. Permutation instructions are determined for permitting the initial source sequence of bits into one or more intermediate sequence of bits until a desired sequence is obtained. The intermediate sequences of bits are determined by configuration bits. The permutation instructions form a permutation instruction sequence of at least one instruction. At most 21gr/m permutation instructions are used in the permutation instruction sequence, where r is the number of k-bit subwords to be permuted, and m is the number of network stages executed in one instruction. The permutation instructions can be used to permute k-bit subwords packed into an n-bit word, where k can be 1, 2, . . . , or n bits, and k*r=n.

1 - 65 . (canceled)  
   
   
       66 . A system of performing an arbitrary permutation of a source sequence of bits in a programmable processor comprising: 
 means for defining an intermediate sequence of bits that said source sequence of bits is transformed into using butterfly network stages and inverse butterfly network stages;    means for determining a permutation instruction for transforming said source sequence of bits into one or more intermediate sequence of bits until a desired sequence of bits is obtained,    wherein each intermediate sequence of bits is used as input to the subsequent permutation instruction and the determined permutation instructions form a permutation instruction sequence and configuration bits are used in said permutation instruction for determining movement of said source sequence of bits in said source register to said intermediate sequence of bits or movement of said intermediate sequence of bits into a destination register or a source register; and    means for storing said configuration bits and means for retrieving said stored configuration bits for use in said permutation instruction.    
   
   
       67 . A system of performing an arbitrary permutation of a source sequence of bits in a programmable processor comprising: 
 means for defining an intermediate sequence of bits that said source sequence of bits is transformed into using Benes network stages and inverse butterfly network stages;    means for determining a permutation instruction for transforming said source sequence of bits into one or more intermediate sequence of bits until a desired sequence of bits is obtained,    wherein each intermediate sequence of bits is used as input to the subsequent permutation instruction and the determined permutation instructions form a permutation instruction sequence and configuration bits are used in said permutation instruction for determining movement of said source sequence of bits in said source register to said intermediate sequence of bits or movement of said intermediate sequence of bits into a destination register or a source register; and    means for storing said configuration bits and means for retrieving said stored configuration bits for use in said permutation instruction.    
   
   
       68 . A method of performing an arbitrary permutation of a source sequence of bits in a programmable processor comprising the steps of: 
 a. defining an intermediate sequence of bits that said source sequence of bits is transformed into using one or more network stages selected from the group consisting of Benes network stages, butterfly network stages, and inverse network stages; and    b. determining one or more permutation instructions for transforming said source sequence of bits into said intermediate sequence of bits, wherein configuration bits are used in said one or more permutation instructions for determining movement of said source sequence of bits in a source register to said intermediate sequence of bits or movement of said intermediate sequence of bits into a destination register or a second intermediate sequence of bits.    
   
   
       69 . The method of  claim 68  further comprising the steps of: 
 repeating steps a. and b. using said determined intermediate sequence of bits from step b. as said source sequence of bits in step a. until a desired sequence of bits is obtained, the determined permutation instructions form a permutation instruction sequence.    
   
   
       70 . The method of  claim 69  wherein said one or more permutation instructions can perform more than two said Benes stages.  
   
   
       71 . The method of  claim 68  further comprising the steps of: 
 c. storing said configuration bits; and    d. retrieving said stored configuration bits.    
   
   
       72 . The method of  claim 71  further comprising the steps of: 
 determining a subsequent permutation instruction using said retrieved configuration of bits.    
   
   
       73 . The method of  claim 70  further comprising the steps of: 
 d. storing a portion of said configuration bits; and    e. retrieving said stored portions of said configuration bits.    
   
   
       74 . The method of  claim 73  further comprising the steps of: 
 determining a subsequent permutation instruction using said retrieved configuration portion of said configuration bits.    
   
   
       75 . The method of  claim 69  wherein said method performs 1g(n) of said network stages in one instruction.  
   
   
       76 . The method of  claim 69  wherein said method performs 21g(n) network stages in one instruction.  
   
   
       77 . The method of  claim 69  wherein said configuration bits are obtained from a register file.