Method and system for performing permutations with bit permutation instructions

• US 20050149590A1
• Filed: 02/16/2005
• Published: 07/07/2005
• Est. Priority Date: 05/05/2000
• Status: Active Grant

• Current Assignee: Ruby B. Lee, Zhijie Shi
• Original Assignee: Ruby B. Lee, Zhijie Shi
• Inventors: Lee, Ruby B., Shi, Zhijie
• Granted Patent: US 7,519,795 B2
• Time in Patent Office: Days
• US Class Current: 708/200
• CPC Class Codes: G06F 7/762 having at least two separately controlled rearrangement levels, e.g. multistage interconnection networks G06F7/764 - G06F7/768 take precedence
• CPC Class Codes: G06F 9/30018 Bit or string instructions
• CPC Class Codes: G06F 9/30025 Format conversion instructions, e.g. Floating-Point to Integer, decimal conversion
• CPC Class Codes: G06F 9/30032 Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations

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. PPERM and PPERM3R instructions are defined to perform permutations by a sequence of instructions with each sequence specifying the position in the source for each bit in the destination. In the PPERM instruction bits in the destination register that change are updated and bits in the destination register that do not change are set to zero. In the PPERM3R instruction bits in the destination register that change are updated and bits in the destination register that do not change are copied from intermediate result of previous PPERM3R instructions. Both PPERM and PPERM3R instruction can individually do permutation with bit repetition. Both PPERM and PPERM3R instruction can individually do permutation of bits stored in more than one register. In an alternate embodiment, a GRP instruction is defined to perform permutations. The GRP instruction divides the initial sequence in the source register into two groups depending on control bits. The first group is combined with the second group to form an intermediate sequence toward the desired final permutation. The total number of GRP instructions for a bit level permutation of n bits is not greater than 1gn. The GRP instruction can be used to permute k-bit subwords packed into an n bits word, where k can be 1, 2, . . . , or n bits, and k*r=n. At most 1gr permutation instructions are used in the permutation instruction sequence, where r is the number of k-bit subwords to be permuted. The GRP instruction can also be used to permute 2n bits stored in two n-bit registers. The total number of instructions for bit permutation of 2n bits is 21gn+4, and two of those instructions are SHIFT PAIR instruction.

Claims

1-57. -57. (canceled)

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

a source register;

a configuration register;

a destination register;

in response to a GRP instruction dividing an arrangement of a source sequence of bits into a first group and a second group and combining said first group and said second group based on control bits of a configuration register.

59. The system of claim 58 wherein at most 1gn said GRP instructions are included in said permutation instruction sequence, wherein n is the number of subwords in said sequence of bits, each said subword comprising one or more bits.

60. 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 using a GRP instruction by dividing an arrangement of a source sequence of bits into a first group and a second group and combining said first group and said second group based on control bits of a configuration register.

61. The computer readable medium of claim 60 wherein at most 1gn said permutation instructions are included in said permutation instruction sequence, wherein n is the number of subwords in said sequence of bits, each said subword comprising one or more bits.

62. 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 using a GRP instruction by dividing an arrangement of a source sequence of bits into a first group and a second group and combining said first group and said second group based on control bits of a configuration register.

63. The cryptographic system of claim 62 wherein at most 1gn said permutation instructions are included in said permutation instruction sequence, wherein n is the number of subwords in said sequence of bits, each said subword comprising one or more bits.

64. A circuit for implementing a permutation instruction comprising:

a first matrix of a plurality of operation units, each of said operation units comprising a first input connected to a second input, a first output and a second output and a control input, said control input controls a connection between said first input and said second input to said first output or said second output for each of said basic units; and

a second matrix comprising an inversion of said first matrix;

said first matrix being selectively connected to said second matrix.

65. The circuit of claim 64 wherein said permutation instruction is for an n bit operation and control bits are encoded by one-hot code for combining results of two n bit operations into a 2n bit operation.

66-77. -77. (canceled)