Method and system for reordering bytes in a data stream

• US 5,594,919 A
• Filed: 06/02/1995
• Issued: 01/14/1997
• Est. Priority Date: 05/07/1993
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Turkowski, Kenneth E.
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US08/458,496
• Time in Patent Office: 592 Days
• Field of Search: 395/700, 395/800, 395/500
• US Class Current: 712/300
• 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 7/768 Data position reversal, e.g. bit reversal, byte swapping
• 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

Abstract

A method and system are disclosed for efficiently translating data from one known data sequencing arrangement to an alternative sequencing arrangement. The method consists of the steps of generating a source sequence signal which identifies the ordering of units within the source sequence, generating a destination sequence signal which identifies the ordering of units within the destination sequence, and combining the source signal and destination signal to produce a permutation signal which defines the relationship between the source sequence and the destination sequence. Once the permutation signal has been defined, this permutation signal is applied to the source sequence to allow the reordering of the source sequence into the desired destination sequence. A reordering circuit is used to rearrange the source sequence units into the desired destination sequence units utilizing the permutation signal generated in the present invention. The reordering circuit consists of an array of ordered swap units which contain inputs for source sequence signals and permutation signals, and outputs which propagate destination sequences.

Claims

1. A computer implemented method for translating a source sequence of ordered data units into a destination sequence having a different ordering of said data units, the method comprising the computer implemented steps of:

using machine-specific data unit packing parameters to generate a source sequence signal, E_S, which identifies the ordering of units within the source sequence;

using machine-specific data unit packing parameters to generate a destination sequence signal, E_D, which identifies the ordering of units within the destination sequence;

combining the source sequence signal and the destination sequence signal to produce a permutation signal, E_P, according to the formula;

space="preserve" listing-type="equation">E.sub.P =(E.sub.S XOR E.sub.D)AND(n-1)

where n is equal to the number of data units to be translated and is greater than two; and

reordering the units from the source sequence in response to the permutation signal to produce a translated destination sequence.

2. The method for translating according to claim 1, wherein the data unit is an eight-bit byte.

3. The method for translating according to claim 1, wherein the data unit is a single bit.

4. The method for translating according to claim 1, wherein n is equal to 2 raised to an integer power.

5. The method for translating according to claim 1, wherein the step of reordering the data units of the source sequence comprises:

determining a destination ordering index D(i) for each data unit of the source sequence based on a source ordering index S(i) of the unit'"'"'s order in the source sequence, using the permutation signal, E_P, according to the formula;

space="preserve" listing-type="equation">D(i)=S(i XOR E.sub.P).

6. A computer system for translating a source sequence of n ordered data units into a desired destination sequence having a different ordering, the computer system comprising:

means for using machine-specific data unit packing parameters to generate a source sequence signal, E_S, which identifies the ordering of units within the source sequence;

means for using machine-specific data unit packing parameters to generate a destination sequence signal, E_D, which identifies the ordering of units within the destination sequence;

means for combining the source sequence signal and destination sequence signal to produce a permutation signal, E_P defined by the formula;

E_P =(E_S XOR E_D)AND(n-1) where n is greater than two; and

means for reordering the units from the source sequence in response to the permutation signal to produce a translated destination sequence of data units.

7. The system for translating according to claim 6, wherein the data unit is an eight-bit byte.

8. The system for translating according to claim 6, wherein the data unit is a single bit.

9. The system for translating according to claim 6, wherein the means for reordering the data units of the source sequence comprises:

means for determining a destination ordering index D(i) for each data unit of the source sequence using a source ordering index S(i) corresponding to each unit'"'"'s location in the source sequence, and the permutation signal, E_P, in the formula;

space="preserve" listing-type="equation">D(i)=S(i XOR E.sub.P).

10. The system for translating according to claim 6, wherein n is equal to 2 raised to an integer power.