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

• US 5,781,903 A
• Filed: 12/31/1996
• Issued: 07/14/1998
• 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 L
• Application Number:
  US08/775,795
• Time in Patent Office: 560 Days
• Field of Search: 707/1, 707/100, 707/101, 707/102, 707/103, 707/104, 707/200, 382/232, 382/244, 382/248, 382/254, 382/115, 395/500, 345/422
• US Class Current: 707/742
• 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

Abstract

A computer-based system and method for efficiently identifying inverted bits in an address, utilizing a single technique to rearrange any size table, generating new index bit sequences based upon inverted index bits without utilizing a significant amount of memory resources, and rearranging table entries only once. The present invention utilizes a mask that defines the address bits that are inverted for a new table. The present invention then rearranges the table entries in the old table to form a new table. Once generated the new table can be used in place of the old table thereby requiring no more memory than the old table. Accordingly, the present invention provides a system and method for identifying the index bits to be inverted after the lookup table and computer program have been generated while utilizing significantly less memory than conventional systems and methods.

Claims

1. A computer based method for generating signals representing data in a new data structure in response to an inversion of one or more input signals, 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 bits including one or more active mask bits representing the inverted input signals, the method comprising the steps of:

(a) setting the value of the first index to the value of the reordering mask;

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

(c) 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;

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

(i) selecting a first bit in said first index as a selected bit;

(ii) inverting said selected bit;

(iii) selecting another bit in said first index as a selected bit and repeating steps (ii)-(iii) if the value of said selected bit is equal to the value of a mask bit in the reordering mask corresponding to the selected bit;

(e) modifying the value of the second index if the value of said selected bit is not equal to the value of a mask bit in the reordering mask corresponding to the selected bit;

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

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

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

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

5. The computer based method of claim 1, wherein each bit in the reordering mask corresponds to one bit in each of the first and second indicies, and identifies bits in the second index that are inverted.

6. A computer based method for generating signals representing data in a new data structure in response to an inversion of one or more input signals, 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 bits including one or more active mask bits representing the inverted input signals, the method comprising the steps of:

(a) setting the value of the second index to the value of the reordering mask;

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

(c) 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;

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

(i) selecting a first bit in said second index as a selected bit;

(ii) inverting said selected bit;

(iii) selecting another bit in said first index as a selected bit and repeating steps (ii)-(iii) if the value of said selected bit is equal to the value of a mask bit in the reordering mask corresponding to the selected bit; and

(e) modifying the value of the first index if the value of said selected bit is not equal to the value of a mask bit in the reordering mask corresponding to the selected bit;

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

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

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

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

10. A computer system for generating signals representing data in a new data structure in response to an inversion of one or more input signals, 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, and

a reordering mask having a plurality of bits including one or more active mask bits representing the inverted input signals;

first setting means, adapted to receive signals from said memory module, for setting the value of said first index to the value of said reordering mask;

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

third 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 selecting means, adapted to receive signals from said memory module, for selecting a first bit in said first index as a selected bit,

inverting means, adapted to receive signals from said memory module, for inverting said selected bit,

second determining means, adapted to receive signals from said memory module, for determining if the value of said selected bit is equal to the value of a mask bit in the reordering mask corresponding to the selected bit, and

second selecting means, adapted to receive signals from said determining means, for selecting another bit in said first index as a selected bit; and

modifying means, adapted to receive signals from said determining means, for modifying the value of the second index if the value of said selected bit.

11. The computer system of claim 10, wherein said modifying means sequentially modifies said second index.

12. The computer system of claim 10, wherein said modifying means sequentially increases said second index.

13. The computer system of claim 10, wherein said modifying means sequentially decreases said second index.

14. The computer system of claim 10, wherein each bit in the reordering mask corresponds to one bit in each of the first and second indicies, and identifies bits in the second index that are inverted.