United States Patent 19
`Turkowski
`
`||||IIII
`US005524256A
`11
`Patent Number:
`5,524.256
`45) Date of Patent:
`Jun. 4, 1996
`
`9.
`
`9
`
`9
`
`54 METHOD AND SYSTEM FOR REORDERING
`BYTES IN ADATA STREAM
`
`5,398,328 3/1995 Weber et al. ........................... 395/500
`5,423,010 6/1995 Mizukami ............................... 395/375
`
`(75
`
`Inventor: Kenneth E. Turkowski, Palo Alto,
`Calif.
`73 Assignee: Apple Computer, Inc., Cupertino,
`Calif.
`
`Appl. No.: 58,429
`(21
`1 -.
`22 Filed:
`May 7, 1993
`(51) Int. Cl. ....................... G06F 7/00
`52 U.S. Cl. .................... 395/800; 395/500; 364/DIG. 1;
`364/259; 364/2604; 364/239.5
`58 Field of Search .................................... 395/800, 500,
`395/775, 250, 200, 425, 821, 700, 325
`'
`'
`' ' ' '
`2
`References Cited
`U.S. PATENT DOCUMENTS
`5/1974 Batcher ................................... asso
`3,812,467
`-- a
`395/775
`4,931,925 6/1990 Utsumi et al.
`a
`395/600
`4,956,809 9/1990 George et al. ...
`395/800
`5,107,415 4/1992 Sato et al. .........
`5,132,898 7/1992 Sakamura et al. ......
`395/425
`5, 191581 3/1993 Woodbury et al. .................... 370/85.9
`5,265,237 11/1993 Tobias et al. ........................... 395/500
`5,313,231
`5/1994 Yin et al. ................................ 345/199
`
`56
`
`2
`
`Primary Examiner- Mehmet Gecki
`Attorney, Agent, or Firm-Carr, DeFilippo & Ferrell
`57
`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 com
`bining 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 per
`mutation signals, and outputs which propagate destination
`sequences.
`
`2 Claims, 10 Drawing Sheets
`
`ENDIAN CODES
`
`
`
`
`
`BIG E LITTLE E (HEX)
`O
`O1
`
`
`
`
`
`ORDERING WITHIN
`BYTE
`WORD 16
`WORD 16 WORD 32
`WORD 32 WORD 64
`WORD 64 128 BITS
`128 BITS 256 BITS
`256 BITS 512 BITS
`512 BITS 1024. BITS
`1 O24 BITS 2048 BITS
`
`
`
`
`
`
`
`
`
`Oracle-1022 p. 1
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 1 of 10
`
`5,524.256
`
`DEFINE ENDIAN CODES
`ES & ED
`
`COMPUTE PERMUTATION
`CODE EP
`
`DETERMINE REORDERING
`INDICES
`
`REARRANGE UNITS TO
`PRODUCE DESTINATION
`SEQUENCE
`
`FIG. 1
`
`ENDIAN CODES
`
`BIG E LITTLE E (HEX)
`O
`O1
`O2
`
`ORDERING WITHIN
`BYTE
`WORD 16
`WORD 16 WORD 32
`WORD 32 WORD 64
`WORD 64 128 BITS
`128 BITS 256 BITS
`256 BITS 512 BITS
`512 BITS 1024. BITS
`1 O24. BITS 2048 BITS
`
`
`
`FIG 2
`
`Oracle-1022 p. 2
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 2 of 10
`
`5,524.256
`
`ENDIAN CODES FOR
`POPULAR PROCESSORS
`PROCESSORS
`MOTOROLA 68OXO,
`MIPS, SPARC
`
`TYPE
`BIG
`ENDIAN
`
`CODE (HEX)
`
`
`
`
`
`LITTLE
`ENDIAN
`
`INTEL 8OX86
`
`FF
`
`FIG. 3
`
`
`
`Oracle-1022 p. 3
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 3 of 10
`
`5,524.256
`
`BIG-ENDIAN
`
`4 || 5 || 6 || 7
`
`Es=0
`
`D-O
`
`1
`
`LTTLE-ENDIAN
`
`2
`
`3
`
`7 || 6 || 5 || 4
`(LSB)
`(MSB)
`FIG. 5b
`
`Es=FF
`
`
`
`DATA SIZE
`(NUMBER OF BYTES)
`
`Oracle-1022 p. 4
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 4 of 10
`
`5,524.256
`
`O v-
`
`v-
`
`ly
`
`CN
`
`QQ
`
`ny
`
`in
`
`P2
`
`11
`IO
`C SWAP
`YO Y1
`
`P1
`
`33 JE US CU
`--- st
`
`11
`IO
`C SWAP
`YO Y1
`
`11
`IO
`C SWAP
`YO Y1
`
`11
`|O
`C SWAP
`YO Y1
`
`33
`
`| 1
`IO
`C SWAP
`YO Y1
`
`3.
`
`11
`IO
`C SWAP
`YO Y1
`
`11
`IO
`C SWAP
`YO Y1
`
`| 1
`IO
`C SWAP
`YO Y1
`
`C SWAP
`YO Y1
`
`C SWAP
`YO Y1
`
`C SWAP
`YO Y1
`
`1
`C SWAP
`YO Y1
`
`
`
`FIG. 7
`
`Oracle-1022 p. 5
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 5 of 10
`
`5,524.256
`
`
`
`Oracle-1022 p. 6
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`
`
`US. Patent
`
`Jun. 4, 1996
`
`Sheet 6 of 10
`
`5,524.256
`5,524,256
`
`11a
`
`
`
`
`-_.-i|
`1""il-_.11
`
`E H HE
`
`
`Hall
` liiiiiifiJ"
`
`
`..._ 'lll
`
`
`
`
`
`
`11b
`
`FIG 11 (MAP)
`FIG.
`11 (MAP)
`
`Oracle-1022 p. 7
`Oracle v. Teleputers
`|PR2021-00078
`
`Oracle-1022 p. 7
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 7 of 10
`
`5,524.256
`
`Q YN CNN) w
`(f)
`(/)
`(/)
`(/)
`(/)
`
`() Co. n.
`(/)
`(/)
`(/)
`
`On YN Q.
`QQ Q
`
`
`
`H. Do
`H6 H7
`|
`|
`1995
`|
`|
`2
`9
`H3 D
`H4 H5 H6 -7
`H
`
`1926 H2 H3 | | |
`E Y
`
`|
`
`|
`
`
`
`
`
`
`
`CD2 D
`
`FIG 11a
`
`Oracle-1022 p. 8
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 8 of 10
`
`5,524.256
`
`A
`
`Y
`
`C D3 D
`
`
`
`99.
`
`|||— 99.
`
`H.
`
`-5 H6 H7 || H.
`H 4 - O H; Y H5 H6 H7 ||
`2 F3 H4 H5 H6 H H
`
`-
`
`
`
`
`
`
`
`FIG. filb
`
`Oracle-1022 p. 9
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 9 of 10
`
`5,524,256
`
`we l) Co. N.
`
`wn
`vs.
`S. CS
`
`al
`
`1 = D1=6
`D = 6
`
`77
`
`FIG. 12
`
`Oracle-1022 p. 10
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`U.S. Patent
`
`Jun. 4, 1996
`
`Sheet 10 of 10
`
`5,524,256
`
`9 || ||
`
`
`
`
`
`Oracle-1022 p. 11
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`1
`METHOD AND SYSTEM FOR REORDERING
`BYTES IN ADATA STREAM
`
`5,524.256
`
`2
`Little-endian: 7 6 5 4 3 2 10
`The number 7 represents the most significant byte of the an
`eight byte word, and 0 represents the least significant byte.
`A single byte is alternatively defined as a "Words', a 16-bit
`quantity as a “Word 6', a 32-bit word as a “Word32', and
`so on, to simplify the forthcoming discussion. The PDP-11
`(formerly manufactured by Digital Equipment Corporation
`of Maynard, Mass.) using the same representations of most
`and least significant bytes (Words's), is represented as:
`PDP-11 little-endian: 10 3 2 5 47 6.
`The VAX computer line of computers, also manufactured by
`Digital Equipment Corporation, is represented as:
`VAX little-endian: 3 2 10 7 6 5 4.
`A pure big-endian packing mechanism packs Words's into
`Word 16's in a big-endian manner, that is the most significant
`Words is packed first, then the least significant Words is
`packed. Likewise, Word16's are packed into Word32's in a
`big-endian manner, Word32's into Word64's, in a big endian
`manner, etc. A pure little-endian packing mechanism packs
`Words's into Word 16's in a little-endian manner, starting
`with the least significant Words and followed by the most
`significant Words. Similarly, Word 16's are packed into
`Word32's, Word32's into WordG4's, and so on, in a little
`endian manner. The PDP-11 structure shown above, packs
`Words's into Word16's in a little-endian manner, but packs
`Word 16's into Words2's and WordS2's into Word64's in a
`big-endian manner. The VAX, which succeeded the PDP-11,
`packs Words's into Word16's and Word 16's into Word32's
`in a little-endian manner, but packs Word32's into Word64's
`in a big-endian manner. The motivation for this change in
`structure between the PDP-11 and the VAX, is that at the
`time of the PDP-11, 32-bit data types were not supported by
`the hardware, and during the time of the VAX, 64-bit data
`types were not supported by the hardware. Currently, 64-bits
`is the largest primitive data type supported on most com
`puters, although this will likely change in the future.
`The major problem associated with the various arrange
`ments of data strings used by different computers, is that
`communication between these computers is extremely cum
`bersome at best, and impossible in the normal course of
`network communication. What is needed is a method and
`system for efficiently translating data from a known-endian
`arrangement to an alternative-endian scheme.
`
`SUMMARY OF THE INVENTION
`In accordance with the present invention, a method and
`system are disclosed for efficiently translating data from one
`known endian arrangement to an alternative-endian scheme.
`The first step of the method involves defining a source
`sequence code and a destination sequence code which
`contains information relating to the ordering of units within
`the source and destination sequences. Once the endian codes
`are defined for the source and the destination sequences, a
`permutation code is defined which describes the relationship
`between the source sequence and the destination sequence.
`Using this permutation code, the units in the source
`sequence are reordered to the desired destination sequenc
`ing.
`A reordering circuit is used to rearrange the source
`sequence units into the target destination sequence units
`utilizing the permutation signals defined above. The reor
`dering circuit consists of an array of ordered swap units
`which contain inputs for source sequence units and permu
`tation codes and outputs which propagate destination
`Sequences.
`
`15
`
`20
`
`25
`
`30
`
`40
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates to the organization of computer
`data and more particularly to a method and system for
`translating between data structures used in different com
`puter architectures. The present invention enables one con
`10
`puter to read and reorder data bytes which are generated by
`another computer system using a differing byte ordering
`scheme.
`2. Description of the Background Art
`One of the most ubiquitous problems in data interchange
`between heterogeneous computer systems is breaking up
`larger quanta of data into smaller quanta of data, and
`conversely, assembling larger quanta of data from smaller
`quanta. Data contained in a data stream is generally arranged
`as either big-endian, little-endian, or some hybrid of the two.
`In a "big-endian' (from the description "big end”) arrange
`ment, the most significant unit of a data word is transmitted
`first, followed by units of descending radix value until the
`least significant unit is transmitted. It should be noted that a
`unit is commonly defined as some number of bits or a byte
`(where a byte is eight bits) and that a word is some number
`of bytes. Big-endian sequencing is motivated in part by the
`western tradition of reading written text from left to right.
`Since the most significant unit of a number read from left to
`right is encountered first, transmission of numbers from left
`to right as they might appear on a display terminal or a
`printed page is a natural sequencing. A second motivation
`for the big-endian sequencing scheme arises from the effi
`ciency associated with transmitting the most significant unit
`35
`first. From the standpoint of transmitting the most amount of
`information in the shortest amount of time, it makes sense to
`transmit the most significant data first, since gross decisions
`can be made based on order-of-magnitude information con
`tained in the high-order bytes. Certainly in many mathemati
`cal operations, some processing can occur on the most
`significant components of a data stream even as the proces
`sor is waiting for the lower end bytes of the data components
`to arrive. The line of Macintosh computers (manufacture by
`Apple Computer Company of Cupertino, Calif.) uses the
`big-endian data structure.
`Little-endian data packing, derived from "little end', is
`the converse of the big-endian scheme. The least significant
`unit is transmitted first, followed by units representing
`values of increasing numerical significance. A motivation
`for the use of the little-endian scheme is that the data is
`organized conveniently and logically as a function of
`increasing radix. The first value transmitted is 20*n, the
`second value is 21*n, and so on, where n represents the
`number of bits per unit (n=8 when the unit is a byte). This
`sequencing is particularly useful since all addition functions
`require a carry calculation on the least significant bits before
`higher-order bits can be processed.
`Other organization systems commonly combine features
`of the big-endian and little-endian conventions to produce
`hybrid data packing schemes. For purposes of comparing
`various hybrid structures, it is useful to define the big-endian
`scheme as a sequence of bytes arranged as:
`Big-endian: 0 12345 67
`where 0 represents the most significant byte of an eight byte
`word, and 7 represents the least significant byte. Similarly
`the little-endian structure would be represented as:
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Oracle-1022 p. 12
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`5,524.256
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a flow chart showing the method of translating
`the ordering of unit bytes from a source sequencing scheme
`to a destination sequencing scheme in a computer data
`Stream,
`FIG. 2 is a table showing the big- and little-endian codes
`used to define the source and destination sequences in the
`method of FIG.
`FIG. 3 is a table identifying endian codes for popular
`processors using the table of FIG. 2;
`FIG. 4 is a flow chart showing the details of the step of
`determining reordering indices for the method of FIG. 1;
`FIG. 5A and 5B are diagram showing an example reor
`dering from a big-endian source sequence of the bytes
`containing the number 4567 to a corresponding little-endian
`destination sequence, using the method of FIG. 1;
`FIG. 6 is a signal flow diagram showing an overview of
`the translation of a source sequence into a destination
`Sequence responsive to a permutation signal, Ep;
`FIG. 7 is a schematic diagram showing the preferred
`circuit embodiment for implementing the reordering method
`of FIG. 1 using multi-layered combinational logic;
`FIG. 8 is a schematic diagram showing details of the
`SWAP block used in the preferred embodiment of FIG. 7;
`FIG. 9 a schematic diagram showing details of the sixteen
`bit input, eight output multiplexer used in the SWAP block
`of FIG. 7;
`FIG. 10 is a schematic diagram showing the preferred
`embodiment for implementing the reordering of four bytes
`using combinational logic,
`FIG. 11 FIG. 11 (a) and FIG. 11 (b) comprise a schematic
`diagram showing an alternative embodiment for implement
`ing the reordering of eight bytes using combinational logic;
`FIG. 12 is a schematic diagram showing an alternative
`embodiment for implementing the reordering of four bytes
`using combinational logic, and FIG. 13 is a block diagram
`of a computer system for translating source sequences of
`ordered data units into destination sequences having differ
`ent orderings in accordance with the present invention.
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`Referring now to FIG. 1, a method is shown for translat
`ing the ordering of data units from a source sequencing
`scheme to a destination sequencing scheme in a computer
`data stream. The method begins with step 11 by defining
`endian codes for source (ES) and destination (ED)
`sequences. The source and destination sequences are strings
`of data that are either being used, transmitted or stored by a
`processor in a computing environment. As a generalization,
`sequences consist of groups of bits referred to as data units.
`A unit can contain a single bit or any number of bits; in the
`preferred embodiment, the data are grouped in strings of
`eight bits, defined as bytes. Groups of bytes are defined by
`their conventional terms to include Word 16 (a double-byte
`word, also called a short word), Word32 (a string of two
`double byte words, often referred to as along word), Word64
`(a string of two quad-byte words, also referred to as a double
`word), etc.
`Referring now to FIG. 2, a coding scheme of the present
`invention is shown in which hexadecimal (hex) weights are
`assigned to orderings of bytes contained within data streams.
`The first line of the data table in FIG. 2 shows that the
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`ordering of a byte within a Word16 is represented by a zero
`when Word16 is arranged in big endian form (i.e., the most
`significant byte is transmitted first), and the Word 16 is
`represented by hexadecimal 01 (01 hex) when represented in
`little-endian form (where the most significant byte is trans
`mitted first). Similarly from the second line of the table of
`FIG. 2, a Word32 containing two ordered Word16's is
`represented by a zero when Word32 is composed of two
`Word16's arranged in big-endian form and Word32 is rep
`resented as a hexadecimal 02 when Word32 is composed of
`two Word 16's arranged in little-endian form. It should be
`noted that in FIG. 2 all of the orderings which are in big
`endian form are assigned a value of zero. The value of a
`little-endian representation, however, changes for each
`ordering depending on the size of the word in which the
`reorderings are required. The table of FIG. 2 can be easily
`extrapolated to include larger orderings than those shown.
`Referring now to FIG. 3, the code for ES and ED for
`popular processors are shown. The Motorola 680XO
`(Motorola Inc., Schaumburg, Ill.), the MIPS (Silicon Graph
`ics, Inc., Mountain View, Calif.), and the Sparc (Sun Micro
`systems, Inc., Mountain View, Calif.) processors, all use
`big-endian data arrangements and are assigned a code of 00
`hex. As described above, the DEC PDP-11 is a hybrid
`processor and is assigned a code of 01 hex. The DEC VAX
`is also a hybrid and is assigned a code of 03 hex.
`In step 13, a permutation code Ep is computed from the
`equation:
`
`Ep-tes xor Ep) AND (n-1)
`and represents the endian-ordering relationship between the
`endian ordering Es of the source sequence and the endian
`ordering E of the destination sequence. In the above
`equation for Ep, in represents the number of bytes in the
`desired data set, and the symbol XOR represents a logical
`exclusive OR operation.
`Following the computation of the permutation code Ep in
`step 13, reordering indices are determined in step 15.
`Reordering indices are numerical pointers which identify the
`rearrangement of bytes. Each source sequence position has
`an index pointer identifying the byte's location in the
`sequence. The first byte is indexed as 0. The next byte is 1,
`and the index number increases through the sequence. A
`similar indexing exists for the destination sequence, and the
`object of step 15 is to translate the byte from its indexed
`position in the source sequence to an appropriate position in
`the destination sequence, as identified by the reordering
`index. The method for determining the reordering indices is
`shown in FIG. 4. The first step of FIG. 4 is to establish an
`index counteri which is set to zero in step 21. Index counter
`i is a positive integer ranging from zero to n-1, where n is
`equal to the number of bytes in the source sequence for
`which translation to a destination sequence is desired. In step
`23 a determination occurs as to whether i is less than n. If
`i is not less 12 than n, then all indices have been determined
`and the process ends in step 25 and returns to step 17 for
`reordering of the bytes to the destination sequence. If i is less
`than n, then the destination reordering index is calculated for
`byte i of the source sequence. The destination reordering
`index is calculated by logically combining the index counter
`i with the permutation code Ep using an exclusive OR
`function. The equation for determining reordering indices
`shown in step 27 is:
`
`Di)=Si XOR Ee
`Following the determination of the reordering value Di)
`for i in step 27, the index counteri is incremented in step 29
`
`Oracle-1022 p. 13
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`5,524.256
`
`6
`
`Therefore, the number “6” moves from the S=2 position in
`FIG.5(a) to the D=1 position in the little-endian, destination
`sequence of FIG. 5(b). Continuing through the method of
`FIG. 4, where i-2,
`
`0
`
`The number "5" in the S=l position of the big-endian source
`sequence representation of FIG. 5(a) moves to the D =2
`position in the little-endian destination representation of
`FIG. 5(b). Finally, for i =3,
`
`5
`and the method of FIG. 4 proceeds back to step 23 where the
`value for i is retested against the total number of bytes n. The
`process of step 15 continues until a reordering value Di has
`been calculated for each byte of the source data sequence
`represented by index counter i. In step 17 of FIG. 1, the
`source sequence bytes are then rearranged to produce the
`desired destination sequence using the reordering indices
`calculated in step 15.
`Referring now to FIG. 5, 50a) and FIG. 5 (b) an example
`is shown in which the method steps of FIG. 1 are utilized to
`convert a source sequence "4567” from the big-endian
`representation shown in FIG. 5(a) to a little-endian repre
`sentation as shown in FIG. 5(b). The data representation of
`FIG. 5(a) in big-endian format shows the number “4567”
`contained in four bytes indexed as i=0 for the most signifi
`cant byte, 4, through i=3 for the least significant byte, 7.
`Referring also to the method steps of FIG. 1, in step 11 the
`endian codes are defined for the source sequence (Es) and
`the destination sequence (E) using the table of FIG. 2.
`Since the source sequence is in big-endian format, Es is
`equal to Zero (EO). The target destination sequencing in
`this example is little-endian for a WORD32 comprised of
`four bytes. Reading from FIG. 2, two adjacent bytes in a
`WORD16 which are arranged in little-endian format are
`assigned the code of 01 hex. Two adjacent WORD16's in a
`WORD32 in little-endian form are assigned the code of 02
`hex. In order to arrive at E, the individual codes are added
`together. In the case of the present example,
`hex 01-hex O2=hex 03
`which is represented in binary as 11. The value for the
`destination endian code could also easily have been deter
`mined by reference to FIG. 3, in which it is shown that all
`pure little-endian codes are represented by FF hex for
`practical sequence lengths. Since the unit of data to be
`swapped is 4 bytes in length in the present example, only the
`first two least significant units (112) of the binary represen
`tation of FF hex are required to implement the reordering.
`Referring now to step 13 of FIG. 1, the permutation code
`Ep is computed from the equation:
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`The number “4” moves from the S =0 position in the
`big-endian source representation of FIG. 5(a) to the D =3
`position in the little-endian destination sequence of FIG.
`5(b).
`Continuing with the method, in step 29, i is incremented
`to 4 and in step 23, i=4 is no longer less than n-4 and
`therefore the method steps of FIG. 4 end, and control is
`returned to step 17 of FIG. 1. Subsequently, in step 17, the
`bytes are rearranged from the big-endian representation to
`the little-endian representation of FIG. 5(b).
`Although the present example demonstrates the method of
`FIG. 1 for data sequences having 4 bytes, this same method
`is applicable to data sequences of any length. The present
`method is particularly useful for sequences having n-values
`equal to an exponent of 2, i.e., 2, 4, 8, 16, 32, etc.; however,
`other-length sequences can also be reordered using this
`method, although additional steps will be required to cor
`rectly orient the data within the sequence.
`Referring now to FIG. 6, a signal flow diagram is shown
`illustrating an overview of the translation of a source
`sequence 46 into a destination sequence 50 responsive to a
`permutation signal 44. In the preferred embodiment, a
`source sequence signal 40 is produced by a computing
`system using a look-up table or equivalent, implementing
`the techniques described above. Likewise, a destination
`sequence signal 42 is also generated which describes the
`ordering of a desired destination sequence 50. The signals 40
`and 42 comprise a string of binary data which identify the
`endian coding of the source and destination sequences
`46.50. The data size (n) 43 represents the sequence sizes of
`both the source sequence 46 and the destination sequence
`50. Using the logical relationship
`
`E=(Es XORE) AND (n-1)
`a permutation signal 44 is generated which is used to instruct
`the computing system as to the translation of the source
`sequence 46 into the destination sequence 50 in reorder unit
`48. As implemented in a computing system, the source
`sequence 46 and the destination sequence 50 are preferably
`memory units which contain the sequencing data. Source
`sequence signal 40 and destination sequence signal 42 are
`calculated results produced from the logical combination of
`data stored in a look-up table. Permutation signal 44 results
`from the logical combination of source sequence signal 40,
`data size (n) 43, and destination sequence signal 42 as
`described above. Reorder unit 48 may be implemented as
`either a hardware implementation as discussed below or as
`a software implementation, comprising a sequence of com
`puter program steps implementing the methods discussed
`above.
`Referring now to FIG.7, a schematic diagram is shown of
`a hardware circuit for reordering bytes from a source
`
`E=(Es XORE) AND (n-1).
`where n is equal to the number of units (bytes) in the
`sequence. The number of bytes in the present example is 4,
`and therefore n=4. Plugging the known values into the
`equation of step 13:
`EP = (OXORFF) AND (4-1)
`- FFAND3 =3.
`
`From step 15, the reordering indices are determined using
`the flow chart of FIG. 4. In step 21, i is set equal to zero.
`In step 23, since i =0 and is therefore less than 4, the method
`proceeds to step 27, where the indexed reordering calcula
`tion proceeds, solving:
`
`D(i)=S(iXOR Ee
`For i=0,
`
`DO-S FOXOR3-S
`From this first pass through the flow chart of FIG. 4, it has
`been determined that the number "7" occupying the last
`byte, S=3, of the source sequence in FIG. 5(a) moves to the
`D =0 position in the destination sequence shown in FIG.
`5(b). Iterating again through the flow chart of FIG. 4, for i
`=l,
`
`Oracle-1022 p. 14
`Oracle v. Teleputers
`IPR2021-00078
`
`

`

`7
`sequence to a destination sequence given a known permu
`tation code, Ep. Sequence translator 31 implements steps 15
`and 17 of FIG. 1, in which the ordering indices are deter
`mined and the bytes are rearranged to the destination pack
`ing sequence. Sequence translator 31 converts eight source
`bytes So-S7 into eight translated or resequenced destination
`bytes Do-D, using the permutation code Ep having code
`bits Po-P. The circuit consists of twelve swap cells 33
`arranged in an ordered sequence and combination. It should
`be noted that the eight-bit embodiment of the sequence
`translator 31, is exemplary only and can be easily scaled to
`handle orderings of higher or lower bytes. The general
`structure of the sequence translator 31 of FIG. 7 consists of
`three rows of swap cells 33 each row controlled by a
`permutation code Po, P, or P. The top row, controlled by
`P, contains four swap cells 33, and each swap cell contains
`inputs for two source bytes: So, S.; S, S5, S2, S, and SS7.
`The P. row of swap cells 33 functions to swap long words
`(WORD32) in an eight-byte source sequence. That is, when
`P has a logical value of 1, each of the two long words in the
`eight-byte source sequence effectively switch positions.
`Similarly, in the second row of swap cells 33 controlled by
`permutation code P, short words (WORD16's) are swapped
`when permutation code P is set to 1 (i.e., P1 is logically
`true). Finally, the bottom row of swap cells 33, controlled by
`permutation code P0, swap individual adjacent bytes when
`P1. The net effect is to translate a sequence of source bytes
`into a sequence of translated destination bytes according to
`the permutation codes Po, P, and P.
`Referring now to FIG. 8, the implementation of a swap
`cell 33 is shown, in which the state of a permutation code
`input P determines whether two-inputsource bytes will swap
`positions at the output of the cell. Swap cell 33 consists of
`a pair of multiplexers 35.36 in which each of the two
`multiplexers receive as inputs the bytes from the source
`sequence So and S. The inputs So and S are identical, but
`in the opposite order, for each of the two multiplexers 35,36.
`So is connected to the 0 input of multiplexer 35 and S is
`connected to the 1 input of multiplexer 35. When permuta
`tion code P=0, So is propagated through multiplexer 35 and
`40
`appears at output Do When permutation code P=1, Swhich
`is present at the 1 input of multiplexer 35 appears as the
`output Do. Similarly, multiplexer 36 has as its 0 input S,
`and as its 1 input So When P=0, S (appearing at the 0 input
`of multiplexer 36) is transmitted through the multiplexer 36
`to output D. When permutation code P is equal to 1, So
`which is present at the 1 input of multiplexer 36 is trans
`mitted through to output D. The consequence then of
`permutation code P being 0, is that outputs Do and D have
`as outputs, So and S respectively. When P=1, Do and D are
`equal to S, So respectively. The effect of Po switching from
`a 0 state to a 1 state is that the inputs So and S are switched
`at the outputs DO and D.
`Referring now to FIG.9, a detailed schematic diagram of
`multiplexer 35 is shown as an array of parallel two-bit
`multiplexers having 16 inputs X-X, and Yo-Y7, and
`having eight outputs Zo-Z. The multiplexers 39 are con
`trolled by permutation code P. Implementation of multiplex
`ers 39 is conventional and is well known in the electronics
`atS.
`Referring now to FIG. 10, a schematic diagram is shown
`for implementing the translation example of FIG.5. (a) and
`FIG. (b) The source sequence of FIG. 5(a) and FIG. 5(b) is
`in big-endian format and consists of the sequence of bytes
`4567. The permutation code was determined to be 11 binary
`using the method discussed above. As an example of use of
`the present circuit, four swap cells, 61, 63, 65, and 67, are
`
`30
`
`8
`shown in the ordered arrangement discussed with respect to
`FIG. 7 above. Swap cells 61 and 63 are controlled by
`permutation signal P1, and the outputs from swap cells 61
`and 63 feed into swap cells 65 and 67, which are controlled
`by permutation signal Po. Swap cells 61 and 63 receive
`inputs So, S2 and S1, S3, respectively, and swap cells 65 and
`67 generate outputs Do D and D2, D3, respectively. Refer
`ring to the example then in FIG. 5(a) and FIG. 5(b) swap cell
`61 receives source sequence bytes 4 and 6, while swap cell
`63 receives source sequence bytes 5 and 7. The permutation
`signal was determined above to be 11 binary; that is, P-1
`and Po 1. With P 1, So 4 appearing at the Io input of swap
`cell 61 is transmitted to the Y output; and the S-6 input
`appearing at the I input of Swap cell 61, appears at the Yo
`output. Similarly, the S5 input, appearing at the Io input of
`swap cell 63, is output at the Youtput; while the S. 7 signal
`appearing at the I input, is transmitted through to the Yo
`output. The outputs from the P level are then input into
`swap cells 65 and 67 at the Po level, where the S 6 input
`now appears at the Io input of swap cell 65, and with Pol
`is output as D. The S 7 input to swap cell 63 now appears
`as the I input to swap cell 65, and when P1, S7 is output
`as Do D-5 results from the propagation of the I input of
`swap cell 67, which is produced by the S5 input of swap
`cell 63. The D4 output of swap cell 67 results from the Io
`input of swap cell 67, which in turn is generated from the So
`input of swap cell 61.
`An alternative embodiment to the hardware circuit of
`FIG. 7 for reordering bytes from a source sequence to a
`destination sequence given a known permutation code, is
`shown in FIG. 11 (including details FIG. 11 (a) and FIG. 11
`(b)). This circuit implements the equation:
`
`for an eight byte circuit. The circuit of FIG. 11 can also be
`expanded to generally include any number of bytes as
`discussed above. In general, the circuit consists of an array
`of multiplexers having a number of inputs equal to the
`number of bytes or units being reordered, and a number of
`control lines equal to the number of bits in the permutation
`code Ep. For an eight byte source code as shown in FIG. 11,
`the multiplexers used are eight to one multiplexers, each
`having three control signal inputs. The advantage to the
`embodiment of FIG. 11 over that of FIG. 7, is that only a
`single layer of logic is used