System and method for reordering lookup table entries when table address bits are reordered

• US 5,864,838 A
• Filed: 12/31/1996
• Issued: 01/26/1999
• Est. Priority Date: 12/31/1996
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Rusterholz, John T.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Ho, Ruay Lian
• Application Number:
  US08/777,596
• Time in Patent Office: 756 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 356/124, 382/232, 345/422, 395/500, 395/386
• US Class Current: 1/1
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 7/76 Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer-based system and method for efficiently identifying a new index bit sequence, utilizing a single technique to rearrange any size table, generating new index bit sequences without utilizing a significant amount of memory resources, and rearranging table entries only once. A mask array defines the new index bit sequence for a new table. The mask array has N entries of N bits each where N is equal to the number of bits in the old table index. The table entries in the old table to form a new table by initializing an old table index (OI) and a new table index (NI) and setting the new table entry associated with the NI equal to the old table entry associated with the OI. Then the new index that is associated with the next old index value by using the mask array to sequentially mask bits in the NI corresponding to mask bits in the mask array is dynamically generated. Then the new table entry associated with the generated new table index value is assigned with the old table entry associated with the sequentially increased old table index. The process repeats for all values of the old index. The new table, once completed, is used in place of the old table. Accordingly, the system utilizes significantly less memory and operates more efficiently than conventional systems and methods.

Claims

1. A computer based method for generating signals representing data in a new data structure, the data in the new data structure associated with signals representing a first index, the data in the new data structure being equal to data in an old data structure associated with signals representing a second index, a reordering mask having a plurality of entries, each entry having only one active mask bit and a plurality of non-active mask bits, the computer having a processor and a memory module, the new data structure, the old data structure, the first and second indicies, and the reordering mask stored in the memory module, the method comprising the steps of:

(a) setting the value of the first index and the value of the second index equal to a first value;

(b) setting an element of the new array associated with the value of the first index equal to an element of the old array associated with the value of the second index;

(c) determining a new value for the first index, having the steps of;

(i) identifying a first entry in said reordering mask as the current entry;

(ii) identifying a first bit in the first index that corresponds to the active mask bit in the current entry;

(iii) inverting said first bit;

(iv) identifying the next entry in said reordering mask as the current entry and repeating steps (ii)-(iv) if said first bit is equal to a second value; and

(d) modifying the value of the second index if said first bit is not equal to said second value; and

(e) repeating steps (b) through (e) for each second index signal.

2. The computer based method of claim 1, wherein said second index is modified sequentially in step (d).

3. The computer based method of claim 1, wherein said second index is increased sequentially in step (d).

4. The computer based method of claim 1, wherein said second index is decreased sequentially in step (d).

5. The computer based method of claim 1, wherein said one active mask bit in each mask entry corresponds to a location in the first index that is associated with the first entry.

6. A computer based method for generating signals representing data in a new data structure, the data in the new data structure associated with signals representing a first index, the data in the new data structure being equal to data in an old data structure associated with signals representing a second index, a reordering mask having a plurality of entries, each entry having only one active mask bit and a plurality of non-active mask bits, the computer having a processor and a memory module, the new data structure, the old data structure, the first and second indicies, and the reordering mask stored in the memory module, the method comprising the steps of:

(a) setting the value of the second index and the value of the first index equal to a first value;

(b) setting an element of the new array associated with the value of the first index equal to an element of the old array associated with the value of the second index;

(c) determining a new value for the second index, having the steps of;

(i) identifying a first entry in said reordering mask as the current entry;

(ii) identifying a first bit in the second index that corresponds to the active mask bit in the current entry;

(iii) inverting said first bit;

(iv) identifying the next entry in said reordering mask as the current entry and repeating steps (ii)-(iv) if said first bit is equal to a second value; and

(d) modifying the value of the first index if said first bit is not equal to said second value; and

(e) repeating steps (b) through (e) for each first index signal.

7. The computer based method of claim 6, wherein said first index is modified sequentially in step (d).

8. The computer based method of claim 6, wherein said first index is increased sequentially in step (d).

9. The computer based method of claim 6, wherein said first index is decreased sequentially in step (d).

10. A computer based method for generating signals representing data in a new data structure, the data in the new data structure associated with signals representing a new index, the data in the new data structure being equal to data in an old data structure associated with an old index, said data in the old data structure having a data sequence different from a data sequence of the new data structure corresponding to differences in the new index and the old index, a reordering mask having one entry for every bit representing the old index, each entry having only one active mask bit and a plurality of non-active mask bits, the computer having a processor and a memory module, the new data structure, the old data structure, the new index, the old index, and the reordering mask stored in the memory module, the method comprising the steps of:

(a) setting the value of the new index and the value of the old index equal to zero;

(b) setting an element of the new array associated with the value of the new index equal to an element of the old array associated with the value of the old index;

(c) determining a new value for the new index, having the steps of;

(i) identifying a first entry in said reordering mask as the current entry;

(ii) identifying a first bit in the new index that corresponds to the active mask bit in the current entry;

(iii) inverting said first bit;

(iv) identifying the next entry in said reordering mask as the current entry and repeating steps (ii)-(iv) if said first bit is equal to a first value; and

(d) incrementing the value of the old index if said first bit is not equal to said first value; and

(e) repeating steps (b) through (e) for each old index value.

11. The computer based method of claim 10, wherein said second index is modified sequentially in step (d).

12. The computer based method of claim 10, wherein said second index is increased sequentially in step (d).

13. The computer based method of claim 10, wherein said second index is decreased sequentially in step (d).

14. The computer based method of claim 10, wherein said one active mask bit in each mask entry corresponds to a location in the first index that is associated with the first entry.

15. A computer system for generating signals representing data in a new data structure, comprising:

a processor;

a memory module adapted to receive signals from said processor, including;

a first index associated with data in the new data structure;

a second index associated with data in an old data structure;

a reordering mask having a plurality of entries, each entry having only one active mask bit and a plurality of nonactive mask bits;

first setting means, adapted to receive signals from said memory module, for setting the value of the first index and the value of the second index equal to a first value;

second setting means, adapted to receive signals from said memory module, for setting an element of the new array associated with the value of the first index equal to an element of the old array associated with the value of the second index;

first determining means, adapted to receive signals from said memory module, for determining a new value for the first index, including;

first identifying means, adapted to receive signals from said memory module, for identifying a first entry in said reordering mask as the current entry;

second identifying means, adapted to receive signals from said memory module, for identifying a first bit in the first index that corresponds to the active mask bit in the current entry;

inverting means, adapted to receive signals from said second identifying means, for inverting said first bit;

second determining means, adapted to receive signals from said memory module, for determining if said first bit is not equal to a second value; and

third identifying means, adapted to receive signals from said memory module, for identifying the next entry in said reordering mask as the current entry; and

modifying means, adapted to receive signals from said memory module, for modifying the value of the second index if said first bit is not equal to said second value.

16. The computer system of claim 15, wherein said modifying means modifies said second index sequentially.

17. The computer system of claim 15, wherein said modifying means sequentially increases the value of said second index.

18. The computer system of claim 15, wherein said modifying means sequentially decreases the value of said second index.

19. The computer system of claim 15, wherein said one active mask bit in each mask entry corresponds to a location in the first index that is associated with said first entry.