Reciprocal generator using piece-wise-linear segments of varying width with floating-point format

• US 6,260,054 B1
• Filed: 10/29/1998
• Issued: 07/10/2001
• Est. Priority Date: 10/29/1998
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Neomagic Corporation
• Inventors: Lin, Tao, Rosman, Andrew
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US09/182,349
• Time in Patent Office: 985 Days
• Field of Search: 708/270, 708/272, 708/274, 708/510, 708/504, 708/502, 708/606, 708/653, 708/654
• US Class Current: 708/502
• CPC Class Codes: G06F 1/035 Reduction of table size G06F1/0314 takes precedence
• CPC Class Codes: G06F 2101/12 Reciprocal functions
• CPC Class Codes: G06F 7/49936 Normalisation mentioned as feature only
• CPC Class Codes: G06F 7/74 Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders with shifting G06F5/01

Abstract

A reciprocal generator is useful for perspective correction for 3D graphics. The input range is divided into many sections. A lookup table contains reciprocal outputs for only two of the sections, the smallest-inputs section and the largest-inputs section. Entries in the table for the smallest section contain a base and a scale factor to indicate the reciprocal value. One entry is provided for each possible input value in the smallest section. This provides high precision where the outputs have the largest values, reducing visible distortions caused by relatively small changes in the large output values. Each section is divided into intervals, with one table entry for each interval. For the largest section, each table entry has an initial reciprocal and a slope of a line approximating the reciprocal curve in that interval. Reciprocals for inputs within the interval are calculated by multiplying an offset into the interval by the slope, and then adding to the initial reciprocal for that interval. Each section is twice as wide as the previous section, but has the same number of intervals. A scale factor is generated by counting a number of leading zeros in the input. Then the input is shifted by the number of leading zeros and input of the table. Thus the inputs are scaled to points within the largest section, so intermediate sections do not have to be stored in the table.

Claims

1. A reciprocal generator comprising:

an input bus;

a leading-zero detector, coupled to the input bus, for generating a scale factor indicating a number of leading zeros of an input value on the input bus;

wherein the leading-zero detector is coupled to only upper bits of the input bus and not connected to lower bits of the input bus;

a shifter, responsive to the leading-zero detector, for shifting the input bus by a number of bit-positions indicated by the leading-zero detector to produce a shifted input;

a lookup table, coupled to the shifter, having a plurality of entries, each entry having an initial reciprocal field and a slope field, the lookup table for outputting an initial reciprocal and a slope for an entry selected by a portion of the shifted input; and

an interpolator, coupled to the lookup table, for generating a reciprocal base from the initial reciprocal and the slope output by the lookup table,

wherein the reciprocal of the input bus is the reciprocal base from the interpolator scaled by the scale factor from the leading-zero detector,

wherein the input bus has an input range, the input range being divided into a plurality of sections;

wherein the lookup table does not have separate entries for each of the plurality of sections, the lookup table having entries for a last section, the last section having largest input values,

whereby the reciprocal is generated from the lookup table and the scale factor from the leading-zero detector and entries for the last section but not all sections are stored in the lookup table and the leading-zero detector detects a limited number of leading zeros.

2. The reciprocal generator of claim 1 wherein each successive section has twice an input range of a previous section,

whereby successive sections are doubled in input-width.

3. The reciprocal generator of claim 2 wherein each section has a same number of intervals, wherein a number of interval is equal to a number of entries for the last section.

4. The reciprocal generator of claim 3 wherein the interpolator further comprises:

a multiplier, coupled to the lookup table and coupled to the shifter, for forming a product of lower bits of the shifted input and the slope from the lookup table;

an adder, coupled to the multiplier and coupled to the lookup table, for forming a sum of the product from the multiplier and the initial reciprocal from the lookup table,

wherein the sum from the adder is output as the reciprocal base.

5. The reciprocal generator of claim 1 wherein the lookup table further stores entries for a first section, the first section having smallest input values, the smallest input values being less than input values from all other sections in the plurality of sections,

wherein the lookup table contains entries for only the first section and the last section, but not for intermediate sections,

whereby the lookup table has a reduced number of entries than a table having separate entries for all sections.

6. The reciprocal generator of claim 5 further comprising:

a scale mux, coupled to the leading-zero detector, for outputting the scale factor from the leading-zero detector for all sections except the first section, but for outputting a scale factor from the lookup table when the input value on the input bus is in the first section;

wherein the lookup table stores entries for the first section and the last section, wherein entries for the first section contain the initial reciprocal and a stored scale factor, the stored scale factor being output by the scale mux as the scale factor for the initial reciprocal,

whereby scale factors for the first section are stored in the lookup table, but scale factors for other sections are generated by the leading-zero detector.

7. The reciprocal generator of claim 6 wherein the initial reciprocal from entries for the first section in the lookup table is output by the interpolator as the reciprocal base,

whereby the first section is not interpolated.

8. The reciprocal generator of claim 6 wherein the scale mux is controlled by a most-significant bit of the shifted input form the shifter.

9. The reciprocal generator of claim 8 wherein the shifter shifts zeros into the least-significant bits of the input bus to generate the shifted input.

10. A method for generating a reciprocal from an input, the method comprising:

reading leading bits of the input to detect a bit-position of a leading one;

outputting a scale factor that indicates the bit-position of the leading one;

shifting the input to generate a shifted input that has the leading one in a most-significant-bit position;

addressing a lookup table and selecting a selected entry with an upper group of most-significant bits of the shifted input;

outputting an initial field and a secondary field from the selected entry from the lookup table;

when the shifted input falls within an interval between two adjacent entries in the lookup table;

sending lower bits of the shifted input to a multiplier, the lower bits not including the upper group that addressed the lookup table;

sending the secondary field from the selected entry to the multiplier;

forming a product in the multiplier of the lower bits of the shifted input and secondary field; and

adding the product from the multiplier to the initial field to generate a reciprocal base;

when the shifted input does not fall within an interval;

outputting the initial field of the selected entry as the reciprocal base;

outputting the reciprocal base and the scale factor as the reciprocal of the input, whereby the scale factor of the reciprocal is generated by detecting the leading one of the input, but the reciprocal base is read from the lookup table and whereby inputs not within the interval are not interpolated by the multiplier.

11. The method of claim 10 further comprising:

limiting the input shift to a maximum shift;

when the bit-position of the leading one exceeds the maximum shift;

outputting the secondary field of the selected entry from the lookup table as the scale factor;

outputting the initial field of the selected entry as the reciprocal base,

whereby the secondary field supplies the scale factor when the bit-position of the leading one exceeds the maximum shift.

12. The method of claim 11 wherein the selected entry is read from a first section of the lookup table when the bit-position of the leading one exceeds the maximum shift;

wherein the selected entry is read from a second section of the lookup table when the bit-position of the leading one does not exceeds the maximum shift;

wherein one of two sections of the lookup table is selected.

13. The method of claim further comprising:

using a most-significant bit of the shifted input to select either the first section or the second section of the lookup table.

14. A variable-precision reciprocal generator comprising:

an input bus for carrying a binary input value, the binary input value having an input range divided into a plurality of sections, wherein a last section has a leading one in a most-significant bit-position of the input bus, a next-to-last section has the leading one in a second most-significant bit-position of the input bus, a third to-last section has the leading one in a third most-significant bit-position of the input bus, a second section has the leading one in a limit bit-position of the input bus, and a first section has the leading one in one of several bit positions that are less significant than the limit bit-position,

wherein each successive section contains double a width of binary input values as a previous section;

priority encode means, coupled to the input bus, for determining a number of leading zeros before the leading one of the binary input value, the priority encode means outputting a scale factor;

shift means, responsive to the priority encode means, for shifting the input bus to generate a shifted input;

table means, coupled to the shift means, for outputting a selected entry, the selected entry located by upper bits of the shifted input, the table means having last section entries selected when a most-significant bit of the upper bits from the shifted input is high, but first-section entries selected when the most-significant bit of the upper bits from the shifted input is low, the table means outputting an initial field and a secondary field for the selected entry;

adjust means, coupled to the table means, for generating a reciprocal base by adjusting the initial field by an adjust amount, the adjust amount being generated from lower bits of the shifted input and from the secondary field of the selected entry;

wherein a reciprocal of the binary input value is output as the reciprocal base from the adjust means scaled by the scale factor from the priority encode means when a last-section entry in the table means is selected.

15. The variable-precision reciprocal generator of claim 14 wherein the priority encode means includes limiting means that limits the shift means to shift by a limited shift, the limited shift being a shift amount sufficient to shift the leading one in the limit bit-position to the most-significant bit-position;

wherein when the binary input value is in the first section, the limiting means limits the shift means so that the shift means shifts one of the leading zeros into the most-significant bit-position of the shifted input;

wherein the most-significant bit of the upper bits from the shifted input is a zero when the binary input value is in the first section.

16. The variable-precision reciprocal generator of claim 15 further comprising:

mux means, coupled to receive the scale factor from the priority encode means, for outputting the scale factor from the priority encode means when the binary input value is not in the first section, but for outputting the secondary field of the selected entry from the table means when the binary input value is in the first section,

whereby the scale factor is output by the table means for the first section, but generated by the priority encode means for other sections.

17. The variable-precision reciprocal generator of claim 16 wherein the table means contains 64 first-section entries and 64 last-section entries, but no entries for the next-to-last section, the third-to-last section, or the second section,

whereby a size of the table means is reduced.