Method and system for performing permutations using permutation instructions based on modified omega and flip stages
First Claim
1. 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;
b. determining a permutation instruction for transforming said source sequence of bits into said intermediate sequence of bits; and
c. 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, wherein the determined permutation instructions form a permutation instruction sequence.
1 Assignment
0 Petitions
Accused Products
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 an omegaflip network comprising at least two stages in which each stage can perform the function of either an omega network stage or a flip network stage. 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 permuting 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 21 gr/m permutation instructions are used in the permutation instruction sequence, where r is the number of kbit subwords to be permuted, and m is the number of network stages executed in one instruction. The permutation instructions can be used to permute kbit subwords packed into an nbit word, where k can be 1, 2, . . . , or n bits, and k*r=n.
39 Citations
70 Claims

1. 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;
b. determining a permutation instruction for transforming said source sequence of bits into said intermediate sequence of bits; and
c. 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, wherein the determined permutation instructions form a permutation instruction sequence.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 23)


21. A method of performing an arbitrary permutation of a source sequence of bits in a programmable processor said source sequence of bits is packed into a plurality of source registers comprising the steps of:

a. dividing bits of a first of said source registers to be placed in a first destination register into a first group and bits of said first of said source registers to be placed in a second destination register into a second group with a first permutation instruction sequence;
b. dividing bits of a second of said source registers to be placed in said first destination register into a first group and bits of said second of said source registers to be placed in a second destination register into a second group with a second permutation instruction sequence;
c. placing bits of said first group of said first of said source registers and said bits of said first group of said second of said source registers into said first destination register;
d. placing bits of said second group of said first of said source registers and said second group of said second of said registers into said second destination register;
e. defining a sequence of bits of said first destination register as a first source sequence of bits and a sequence of bits of said second destination register as a second source sequence of bits;
f. defining an intermediate sequence of bits that each of said first source sequence of bits and said second source sequence of bits is transformed into;
g. determining a permutation instruction for transforming said first source sequence of bits and said second source sequence of bits into respective said intermediate sequence of bits; and
repeating steps f. and g. using said determined intermediate sequence of bits from step g. as said source sequence of bits in step f. until a respective desired sequence of bits is obtained for said first source sequence of bits and said second source sequence of bits, wherein the determined permutation instructions form a permutation instruction sequence.  View Dependent Claims (22, 25, 26, 29, 30)


24. 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 with a configuration of an omegaflip network, said omegaflip network comprising at least two stages, each said stage is either an omega network stage or a flip network stage;
b. determining a permutation instruction for transforming said source sequence of bits into said intermediate sequence of bits;
c. storing said determined intermediate sequence of bits; and
d. determining a subsequent permutation instruction using said stored intermediate sequence of bits.


27. A method for performing a permutation of a source sequence of bits in a programmable processor comprising the steps of:

defining an intermediate sequence of bits that said source sequence of bits is transferred into using an interconnection network; and
determining a sequence of one or more permutation instructions for transferring said source sequence of bits into said intermediate sequence of bits and optionally one or more subsequent intermediate sequences of bits until a desired sequence of bits is obtained.


28. A method for performing a permutation of a source sequence of bits in a programmable processor comprising the steps of:

defining an intermediate sequence of bits that said source sequence of bits is transferred into using an omegaflip network; and
determining a sequence of one or more permutation instructions for transferring said source sequence of bits into said intermediate sequence of bits and optionally one or more subsequent intermediate sequences of bits until a desired sequence of bits is obtained.


31. 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 omega network stages and flip network stages; and
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.  View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49)


50. A system of performing an arbitrary permutation of a source sequence of bits in a programmable processor said source sequence of bits is packed into a plurality of source registers comprising:

means for dividing bits of a first of said source registers to be placed in a first destination register into a first group and bits of said first of said source registers to be placed in a second destination register into a second group with one said permutation instruction sequence;
means for dividing bits of a second of said source registers going to said first destination register into a first group and bits of a second of said source registers going to a second destination register into a second group with one said permutation instruction sequence;
means for placing bits of said first group of said first of said source registers and said bits of said first group of said second of said source registers into said first destination register;
means for placing bits of said second group of said first of said source registers and said second group of said second of said source registers into said second destination register;
means for defining a sequence of bits of said first destination register, as a first source sequence of bits and a sequence of bits of said second destination register as a second source sequence of bits;
means for defining an intermediate sequence of bits that each of said first source sequence of bits and said second source sequence of bits is transformed into; and
means for determining a permutation instruction for transforming said first source sequence of bits and said second source sequence of bits into one or more respective said intermediate sequence of bits until a respective desired sequence of bits is obtained for said first source sequence of bits and said second source sequence of bits, 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.  View Dependent Claims (51)


52. A system for performing an arbitrary permutation of a source sequence of bits in a programmable processor comprising:

a. means for defining an intermediate sequence of bits that said source sequence of bits is transformed into with a configuration of an omegaflip network, said omegaflip network comprising at least two stages, each said stage is either an omega network stage or a flip network stage;
b. means for determining a permutation instruction for transforming said source sequence of bits into said intermediate sequence of bits;
c. means for storing said determined intermediate sequence of bits; and
d. means for determining a subsequent permutation instruction using said stored intermediate sequence of bits.  View Dependent Claims (53, 54)


55. A system for performing a 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 an interconnection network, and means for determining a sequence of permutation operations for transforming said source sequence of bits into one or more intermediate sequence of bits until a desired sequence of bits is obtained.  View Dependent Claims (57, 58, 60)


56. A system for performing a 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 omega and flip network stages; and
means for determining a sequence of permutation operations for transforming said source sequence of bits into one or more intermediate sequence of bits until a desired sequence of bits is obtained.


59. A computer implemented method for performing an arbitrary permutation of a sequence of bits comprising the steps of:

inputting said sequence of bits into a source register;
connecting said source register to an omegaflip network;
in response to an omegaflip instruction selecting a configuration of said omegaflip network; and
moving each of said bits in said source register to a position in a sequence of bits of a destination register based on configuration bits of a configuration register.


61. A computer system for performing an arbitrary permutation comprising:

a source register;
a configuration register;
a destination register;
an omegaflip network coupled to said first source register, said configuration register and said destination register, in response to an omegaflip instruction selecting a configuration of said omegaflip network, placing each bit in said sequence of bits from said source register to a position in a sequence of bits in said destination register based on a configuration of bits of said configuration register.  View Dependent Claims (62)


63. A computer readable medium having stored thereon data representing a sequence of permutation instructions, the sequence of permutation instructions which when executed by a processor, cause the processor to permute a source sequence of subwords into one or more intermediate sequences of subwords, each intermediate sequence of subwords using input from said source sequence of subwords or a previous said intermediate sequence of subwords until a desired sequence of subwords is obtained, wherein each subword is one or more bits, said intermediate sequence being determined using a multistage interconnection network.
 64. A computer readable medium having stored thereon data representing a sequence of permutation instructions, the sequence of permutation instructions which when executed by a processor, cause the processor to permute a source sequence of subwords into one or more intermediate sequences of subwords, each intermediate sequence of subwords using input from said source sequence of subwords or a previous said intermediate sequence of subwords until a desired sequence of subwords is obtained, wherein each subword is one or more bits, said intermediate sequence being determined using an omega and flip network stages.

67. A cryptographic system, having stored thereon data representing a sequence of permutation instructions, the sequence of permutation instructions which when executed by a processor, cause the processor to permute a source sequence of subwords into one or more intermediate sequences of subwords, each intermediate sequence of subwords using input from said source sequence of subwords or a previous said intermediate sequence of subwords until a desired sequence of subwords is obtained, wherein each subword is one or more bits, said intermediate sequence being determined using a multistage interconnection network.

68. A cryptographic system, having stored thereon data representing a sequence of permutation instructions, the sequence of permutation instructions which when executed by a processor, cause the processor to permute a source sequence of subwords into one or more intermediate sequences of subwords, each intermediate sequence of subwords using input from said source sequence of subwords or a previous said intermediate sequence of subwords until a desired sequence of subwords is obtained, wherein each subword is one or more bits, said intermediate sequence being determined using an omega and flip network stages.
Specification