TableLookups.pdf

Calculation Via Table Lookups

Calculation

Via Table Lookups

Chapter Twelve

12.1

Chapter Overview

This chapter discusses arithmetic computation via table lookup. By the conclusion of this chapter you

should be able to use table lookups to quickly compute comple

x functions.

ou will also learn ho

w to con

struct these tables programmatically

12.2

Tables

The term “table” has dif

ferent meanings to dif

ferent programmers.

o most assembly language pro

grammers, a table is nothing more than an array that is initialized with some data.

The assembly language

programmer often uses tables to compute comple

x or otherwise slo

w functions. Man

y v

ery high le

el lan

guages (e.g., SNOBOL4 and Icon) directly support a table data type.

ables in these languages are essen

tially arrays whose elements you can access with a non-inte

ger inde

x (e.g., ﬂ

oating point, string, or an

y other

data type). HLA pro

vides a table module that lets you inde

x an array using a string. Ho

, in this chapter

we will adopt the assembly language programmer’

s vie

w of tables.

A table is an array containing preinitialized v

alues that do not change during the e

ecution of the pro

gram.

A table can be compared to an array in the same w

ay an inte

ger constant can be compared to an inte

ger

ariable. In assembly language, you can use tables for a v

ariety of purposes: computing functions, control

ling program ﬂ

, or simply “looking things up”. In general, tables pro

vide a f

ast mechanism for performing

some operation at the e

xpense of some space in your program (the e

xtra space holds the tab

ular data). In the

follo

wing sections we’

ll e

xplore some of the man

y possible uses of tables in an assembly language program.

Note: since tables typically contain preinitialized data that does not change during program e

ecution,

the READONL

Y section is a good place to declare your table objects.

12.2.1

Function Computation via Table Look-up

ables can do all kinds of things in assembly language. In HLLs, lik

e P

ascal, it’

s real easy to create a

formula which computes some v

alue.

A simple looking arithmetic e

xpression can be equi

alent to a consid

erable amount of 80x86 assembly language code.

Assembly language programmers tend to compute man

alues via table look up rather than through the e

ecution of some function.

This has the adv

antage of being

easier

, and often more ef

ﬁ

cient as well. Consider the follo

wing P

ascal statement:

if (character >= ‘a’) and (character <= ‘z’) then character := chr(ord(character) - 32);

This P

ascal

statement con

erts the character v

ariable character from lo

wer case to upper case if char

acter is in the range ‘a’..

’z’.

The HLA code that does the same thing is

mov( character, al );

if( al in ‘a’..’z’ ) then

and( $5f, al );

// Same as SUB( 32, al ) in this code.

endif;

mov( al, character );

’s high level IF statement translates into four machine instructions in this particular example.

Hence, this code requires a total of seven machine instructions.

Beta Draft - Do not distribute

Page

647

Note that HLA

Chapter Twelve

Volume Three

Had you b

uried this code in a nested loop, you’

d be hard pressed to impro

e the speed of this code with

out using a table look up. Using a table look up, ho

, allo

ws you to reduce this sequence of instructions

to just four instructions:

mov( character, al );

lea( ebx, CnvrtLower );

xlat

mov( al, character );

ou’

re probab

ly w

onder

ing ho

w this code w

ks and what is this ne

w instr

uction, XLA

The

XLA

, or

anslate

, instr

uction does the f

ollo

wing:

mov( [ebx+al*1], al );

alue of the AL register as an index into the array whose base address is contained

in EBX. It fetches the byte at that index in the array and copies that byte into the AL register. Intel calls this

the translate instruction because programmers typically use it to translate characters from one form to

another using a lookup table. That’s exactly how we are using it here.

In the pre

vious e

xample

tLo

is a 256-byte table which contains the v

alues 0..$60 at indices

0..$60, $41..$5A at indices $61..$7A, and $7B..$FF at indices $7Bh..0FF

Therefore, if

AL contains a v

alue

in the range $0..$60, the XLA

T instruction returns the v

alue $0..$60, ef

fecti

ely lea

ving

AL unchanged.

AL contains a value in the range $61..$7A (the ASCII codes for ‘a’..’z’) then the XLAT instruc-

tion replaces the value in AL with a value in the range $41..$5A. $41..$5A just happen to be the ASCII

codes for ‘A’..’Z’. Therefore, if AL originally contains an lower case character ($61..$7A), the XLAT

instruction replaces the value in AL with a corresponding value in the range $61..$7A, effectively converting

the original lower case character ($61..$7A) to an upper case character ($41..$5A). The remaining entries in

the table, like entries $0..$60, simply contain the index into the table of their particular element. Therefore,

if AL originally contains a value in the range $7A..$FF, the XLAT instruction will return the corresponding

table entry that also contains $7A..$FF.

As the complexity of the function increases, the performance beneﬁts of the table look up method

increase dramatically. While you would almost never use a look up table to convert lower case to upper case,

consider what happens if you want to swap cases:

, if

Via computation:

mov( character, al );

if( al in ‘a’..’z’ ) then

and( $5f, al );

elseif( al in ‘A’..’Z’ ) then

or( $20, al );

endif;

mov( al, character ):

The IF and ELSEIF statements generate four and ﬁve actual machine instructions, respectively, so this code

is equivalent to 13 actual machine instructions.

The table look up code to compute this same function is:

mov( character, al );

lea( ebx, SwapUL );

xlat();

mov( al, character );

As you can see, when using a table look up to compute a function only the table changes, the code

remains the same.

Page

648

Beta Draft - Do not distribute

That is, it uses the current v

Calculation Via Table Lookups

Table look ups suffer from one major problem – functions computed via table look up have a limited

domain. The domain of a function is the set of possible input values (parameters) it will accept. For example,

the upper/lower case conversion functions above have the 256-character ASCII character set as their domain.

A function such as SIN or COS accepts the set of real numbers as possible input values. Clearly the

domain for SIN and COS is much larger than for the upper/lower case conversion function. If you are going

to do computations via table look up, you must limit the domain of a function to a small set. This is because

each element in the domain of a function requires an entry in the look up table. You won’t ﬁnd it very practi-

cal to implement a function via table look up whose domain the set of real numbers.

Most look up tables are quite small, usually 10 to 128 entries. Rarely do look up tables grow beyond

1,000 entries. Most programmers don’t have the patience to create (and verify the correctness) of a 1,000

entry table.

Another limitation of functions based on look up tables is that the elements in the domain of the func-

tion must be fairly contiguous. Table look ups take the input value for a function, use this input value as an

index into the table, and return the value at that entry in the table. If you do not pass a function any values

other than 0, 100, 1,000, and 10,000 it would seem an ideal candidate for implementation via table look up,

its domain consists of only four items. However, the table would actually require 10,001 different elements

due to the range of the input values. Therefore, you cannot efﬁciently create such a function via a table look

up. Throughout this section on tables, we’ll assume that the domain of the function is a fairly contiguous set

of values.

The best functions you can implement via table look ups are those whose domain and range is always

0..255 (or some subset of this range). You can efﬁciently implement such functions on the 80x86 via the

XLAT instruction. The upper/lower case conversion routines presented earlier are good examples of such a

function. Any function in this class (those whose domain and range take on the values 0..255) can be com-

puted using the same two instructions: “ lea( table, ebx );” and “xlat( );” The only thing that ever changes is the

look up table.

You cannot (conveniently) use the XLAT instruction to compute a function value once the range or

domain of the function takes on values outside 0..255. There are three situations to consider:

• The domain is outside 0..255 but the range is within 0..255,

• The domain is inside 0..255 but the range is outside 0..255, and

• Both the domain and range of the function take on values outside 0..255.

We will consider each of these cases separately.

If the domain of a function is outside 0..255 but the range of the function falls within this set of values,

our look up table will require more than 256 entries but we can represent each entry with a single byte.

Therefore, the look up table can be an array of bytes. Next to look ups involving the XLAT instruction, func-

tions falling into this class are the most efﬁcient. The following Pascal function invocation,

B := Func(X);

where Func is

function Func(X:dword):byte;

consists of the following HLA code:

mov( X, ebx );

mov( FuncTable[ ebx ], al );

mov( al, B );

This code loads the function parameter into EBX , uses this value (in the range 0..??) as an index into the

FuncTable table, fetches the byte at that location, and stores the result into B . Obviously, the table must con-

tain a valid entry for each possible value of X . For example, suppose you wanted to map a cursor position on

the video screen in the range 0..1999 (there are 2,000 character positions on an 80x25 video display) to its X

or Y coordinate on the screen. You could easily compute the X coordinate via the function:

X:=Posn mod 80

Beta Draft - Do not distribute

Page 649

Chapter Twelve

Volume Three

and the Y coordinate with the formula

Y:=Posn div 80

(where Posn is the cursor position on the screen). This can be easily computed using the 80x86 code:

mov( Posn, ax );

div( 80, ax );

// X is now in AH, Y is now in AL

However, the DIV instruction on the 80x86 is very slow. If you need to do this computation for every

character you write to the screen, you will seriously degrade the speed of your video display code. The fol-

lowing code, which realizes these two functions via table look up, would improve the performance of your

code considerably:

movzx( Posn, ebx ); // Use a plain MOV instr if Posn is uns32

mov( YCoord[ebx], al ); // rather than an uns16 value.

mov( XCoord[ebx], ah );

If the domain of a function is within 0..255 but the range is outside this set, the look up table will con-

tain 256 or fewer entries but each entry will require two or more bytes. If both the range and domains of the

function are outside 0..255, each entry will require two or more bytes and the table will contain more than

256 entries.

Recall from the chapter on arrays that the formula for indexing into a single dimensional array (of

which a table is a special case) is

Address := Base + index * size

If elements in the range of the function require two bytes, then the index must be multiplied by two

before indexing into the table. Likewise, if each entry requires three, four, or more bytes, the index must be

multiplied by the size of each table entry before being used as an index into the table. For example, suppose

you have a function, F(x), deﬁned by the following (pseudo) Pascal declaration:

function F(x:dword):word;

You can easily create this function using the following 80x86 code (and, of course, the appropriate table

named F ):

mov( X, ebx );

mov( F[ebx*2], ax );

Any function whose domain is small and mostly contiguous is a good candidate for computation via

table look up. In some cases, non-contiguous domains are acceptable as well, as long as the domain can be

coerced into an appropriate set of values. Such operations are called conditioning and are the subject of the

next section.

12.2.2 Domain Conditioning

Domain conditioning is taking a set of values in the domain of a function and massaging them so that

they are more acceptable as inputs to that function. Consider the following function:

sin

sin x

[

–

]

As we all know, sine is a circular function which will accept any real valued input. The formula used to

compute sine, however, only accept a small set of these values.

Page 650

Beta Draft - Do not distribute

This says that the (computer) function SIN(x) is equivalent to the (mathematical) function sin x where

-2

Calculation Via Table Lookups

This range limitation doesn’t present any real problems, by simply computing SIN(X mod (2*pi)) we can

compute the sine of any input value. Modifying an input value so that we can easily compute a function is

called conditioning the input. In the example above we computed “ X mod 2*pi” and used the result as the

input to the sin function. This truncates X to the domain sin needs without affecting the result. We can apply

input conditioning to table look ups as well. In fact, scaling the index to handle word entries is a form of

input conditioning. Consider the following Pascal function:

function val(x:word):word; begin

case x of

0: val := 1;

1: val := 1;

2: val := 4;

3: val := 27;

4: val := 256;

otherwise val := 0;

end;

This function computes some value for x in the range 0..4 and it returns zero if x is outside this range.

Since x can take on 65,536 different values (being a 16 bit word), creating a table containing 65,536 words

where only the ﬁrst ﬁve entries are non-zero seems to be quite wasteful. However, we can still compute this

function using a table look up if we use input conditioning. The following assembly language code presents

this principle:

mov( 0, ax ); // AX = 0, assume X > 4.

movzx( x, ebx ); // Note that H.O. bits of EBX must be zero!

if( bx <= 4 ) then

mov( val[ ebx*2 ], ax );

endif;

This code checks to see if x is outside the range 0..4. If so, it manually sets AX to zero, otherwise it looks

up the function value through the val table. With input conditioning, you can implement several functions

that would otherwise be impractical to do via table look up.

12.2.3 Generating Tables

One big problem with using table look ups is creating the table in the ﬁrst place. This is particularly true

if there are a large number of entries in the table. Figuring out the data to place in the table, then laboriously

entering the data, and, ﬁnally, checking that data to make sure it is valid, is a very time-staking and boring

process. For many tables, there is no way around this process. For other tables there is a better way – use the

computer to generate the table for you. An example is probably the best way to describe this. Consider the

following modiﬁcation to the sine function:

(

sin

)

---------------------------------------------- x

r 1000

(

sin

)

[

0359

]

1000

This states that x is an integer in the range 0..359 and r must be an integer. The computer can easily

compute this with the following code:

movzx( x, ebx );

mov( Sines[ ebx*2], eax ); // Get SIN(X) * 1000

imul( r, eax );

// Note that this extends EAX into EDX.

idiv( 1000, edx:eax );

// Compute (R*(SIN(X)*1000)) / 1000

Note that integer multiplication and division are not associative. You cannot remove the multiplication

by 1000 and the division by 1000 because they seem to cancel one another out. Furthermore, this code must

Beta Draft - Do not distribute

Page 651

(

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: