The term table has different meanings to different programmers. To most assembly language programmers, a table is nothing more than an array that is initialized with some data. The assembly language programmer often uses tables to compute complex or otherwise slow functions. Many very-high-level languages (for example, SNOBOL4 and Icon) directly support a table data type. Tables in these languages are essentially associative arrays whose elements you can access with a noninteger index (for example, floating point, string, or any other data type). HLA provides a table module that lets you index an array using a string. However, in this chapter we will adopt the assembly language programmer's view of tables.
A table is an array containing initialized values that do not change during the execution of the program. In assembly language, you can use tables for a variety of purposes: computing functions, controlling program flow, or simply looking things up. In general, tables provide a fast mechanism for performing some operation at the expense of some space in your program (the extra space holds the tabular data). In the following sections we'll explore some of the many possible uses of tables in an assembly language program.
Note that because tables typically contain initialized data that does not change during program execution, the readonly section is a good place to put your table objects.
Tables can do all kinds of things in assembly language. In high-level languages like Pascal, it's easy to create a formula that computes some value. A simple-looking high-level-language arithmetic expression can be equivalent to a considerable amount of 80x86 assembly language code and, therefore, could be expensive to compute. Assembly language programmers often precompute many values and use a table lookup of those values to speed up their programs. This has the advantage of being easier, and it's often more efficient as well. Consider the following Pascal statement:
if (character>= 'a') and (character<= 'z') thencharacter:= chr(ord(character) - 32);
This Pascal if statement converts the character variable's value from lowercase to uppercase if character is in the range a..z. The HLA code that does the same thing follows:
mov(character, al ); if( al in 'a'..'z' ) then and( $5f, al ); // Same as sub( 32, al ) in this code. endif; mov( al,character);
Note that HLA's high-level if statement translates into four machine instructions in this particular example. Hence, this code requires a total of seven machine instructions.
Had you buried this code in a nested loop, you'd be hard pressed to reduce the size of this code without using a table lookup. Using a table lookup, however, allows you to reduce this sequence of instructions to just four instructions:
mov(character, al ); lea( ebx, CnvrtLower ); xlat mov( al,character);
You're probably wondering how this code works and asking, "What is this new instruction, xlat?" The xlat, or translate, instruction does the following:
mov( [ebx+al*1], al );
That is, it uses the current value of the AL register as an index into the array whose base address is found in EBX. It fetches the byte at that index in the array and copies that byte into the AL register. Intel calls this instruction translate 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 previous example, CnvrtLower is a 256-byte table that contains the values 0..$60 at indices 0..$60, $41..$5A at indices $61..$7A, and $7B..$FF at indices $7Bh..0FF. Therefore, if AL contains a value in the range $0..$60, the xlat instruction returns the value $0..$60, effectively leaving AL unchanged. However, if AL contains a value in the range $61..$7A (the ASCII codes for a..z), then the xlat instruction replaces the value in AL with a value in the range $41..$5A. The values $41..$5A just happen to be the ASCII codes for A..Z. Therefore, if AL originally contains a lowercase character ($61..$7A), the xlat instruction replaces the value in AL with a corresponding value in the range $61..$7A, effectively converting the original lowercase character ($61..$7A) to an uppercase 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 benefits of the table lookup method increase dramatically. While you would almost never use a lookup table to convert lowercase to uppercase, consider what happens if you want to swap cases, for example, 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 4 and 5 actual machine instructions, respectively, so this code is equivalent to 13 actual machine instructions.
The table lookup 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 lookup to compute a function, only the table changes; the code remains the same.
Table lookups suffer from one major problem—functions computed via table lookup have a limited domain. The domain of a function is the set of possible input values (parameters) it will accept. For example, the uppercase/lowercase 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/lowercase conversion function. If you are going to do computations via table lookup, 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 lookup table. You won't find it very practical to implement a function via table lookup whose domain is the set of real numbers.
Most lookup tables are quite small, usually 10 to 256 entries. Rarely do lookup 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 lookup tables is that the elements in the domain of the function must be fairly contiguous. Table lookups 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 lookup; 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 efficiently create such a function via a table lookup. 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 lookups are those whose domain and range are always 0..255 (or some subset of this range). You can efficiently implement such functions on the 80x86 via the xlat instruction. The uppercase/lowercase 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 computed using the same two instructions: lea( table, ebx ); and xlat();. The only thing that ever changes is the lookup 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.
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 lookup table will require more than 256 entries, but we can represent each entry with a single byte. Therefore, the lookup table can be an array of bytes. Other than those lookups that can use the xlat instruction, functions falling into this class are the most efficient. The following Pascal function invocation
B := Func(X);
where Func is
function Func(X:dword):byte;
is easily converted to 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 contain 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..1,999 (there are 2,000 character positions on an 80×25 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
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 alHowever, 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 following code, which realizes these two functions via table lookup, may improve the performance of your code considerably:
movzx( Posn, ebx ); // Use a plain mov instr if Posn is
mov( YCoord[ebx], al ); // uns32 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 lookup table will contain 256 or fewer entries, but each entry will require 2 or more bytes. If both the range and domains of the function are outside 0..255, each entry will require 2 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 2 bytes, then you must multiply the index by 2 before indexing into the table. Likewise, if each entry requires 3, 4, 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), defined 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 lookup. In some cases, noncontiguous 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.
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:
This says that the (computer) function sin(x) is equivalent to the (mathematical) function sin x where
As we all know, sine is a circular function, which will accept any real valued input. The formula used to compute sine, however, accepts only a small set of these values.
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 lookups 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;
end;This function computes some value for x in the range 0..4 and it returns 0 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 first five entries are nonzero seems to be quite wasteful. However, we can still compute this function using a table lookup 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 0!
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 0; 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 lookup.
One big problem with using table lookups is creating the table in the first place. This is particularly true if there is a large number of entries in the table. Figuring out the data to place in the table, then laboriously entering the data, and, finally, checking that data to make sure it is valid is a very time-consuming and boring process. For many tables, there is no way around this process. For other tables, there is a better way—using the computer to generate the table for you. An example is probably the best way to describe this. Consider the following modification to the sine function:
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)) / 1000Note that integer multiplication and division are not associative. You cannot remove the multiplication by 1,000 and the division by 1,000 because they appear to cancel one another out. Furthermore, this code must compute this function in exactly this order. All that we need to complete this function is a table containing 360 different values corresponding to the sine of the angle (in degrees) times 1,000. Entering such a table into an assembly language program containing such values is extremely boring and you'd probably make several mistakes entering and verifying this data. However, you can have the program generate this table for you. Consider the HLA program in Example 8-8.
Example 8-8. An HLA program that generates a table of sines
program GenerateSines;
#include( "stdlib.hhf" );
var
outFile: dword;
angle: int32;
r: int32;
readonly
RoundMode: uns16 := $23f;
begin GenerateSines;
// Open the file:
mov( fileio.openNew( "sines.hla" ), outFile );
// Emit the initial part of the declaration to the output file:
fileio.put
(
outFile,
stdio.tab,
"sines: int32[360] := " nl,
stdio.tab, stdio.tab, stdio.tab, "[" nl );
// Enable rounding control (round to the nearest integer).
fldcw( RoundMode );
// Emit the sines table:
for( mov( 0, angle); angle < 359; inc( angle )) do
// Convert angle in degrees to an angle in radians using
// radians := angle * 2.0 * pi / 360.0;
fild( angle );
fld( 2.0 );
fmulp();
fldpi();
fmulp();
fld( 360.0 );
fdivp();
// Okay, compute the sine of st0.
fsin();
// Multiply by 1000 and store the rounded result into
// the integer variable r.
fld( 1000.0 );
fmulp();
fistp( r );
// Write out the integers eight per line to the source file.
// Note: If (angle AND %111) is 0, then angle is evenly
// divisible by 8 and we should output a newline first.
test( %111, angle );
if( @z ) then
fileio.put
(
outFile,
nl,
stdio.tab,
stdio.tab,
stdio.tab,
stdio.tab,
r:5,
','
);
else
fileio.put( outFile, r:5, ',' );
endif;
endfor;
// Output sine(359) as a special case (no comma following it).
// Note: This value was computed manually with a calculator.
fileio.put
(
outFile,
" −17",
nl,
stdio.tab,
stdio.tab,
stdio.tab,
"];",
nl
);
fileio.close( outFile );
end GenerateSines;The program above produces the following output (truncated for brevity):
sines: int32[360] :=
[
0, 17, 35, 52, 70, 87, 105, 122,
139, 156, 174, 191, 208, 225, 242, 259,
276, 292, 309, 326, 342, 358, 375, 391,
407, 423, 438, 454, 469, 485, 500, 515,
530, 545, 559, 574, 588, 602, 616, 629,
643, 656, 669, 682, 695, 707, 719, 731,
.
.
.
−643, −629, −616, −602, −588, −574, −559, −545,
−530, −515, −500, −485, −469, −454, −438, −423,
−407, −391, −375, −358, −342, −326, −309, −292,
−276, −259, −242, −225, −208, −191, −174, −156,
−139, −122, −105, −87, −70, −52, −35, −17
];Obviously it's much easier to write the HLA program that generated this data than to enter (and verify) this data by hand. Of course, you don't even have to write the table-generation program in HLA. If you prefer, you might find it easier to write the program in Pascal/Delphi, C/C++, or some other high-level language. Because the program will only execute once, the performance of the table-generation program is not an issue. If it's easier to write the table-generation program in a high-level language, by all means do so. Note also that HLA has a built-in interpreter that allows you to easily create tables without having to use an external program. For more details, see Chapter 9.
Once you run your table-generation program, all that remains to be done is to cut and paste the table from the file (sines.hla in this example) into the program that will actually use the table.
In the early days of PCs, table lookups were a preferred way to do high-performance computations. However, as the speed of new CPUs vastly outpaces the speed of memory, the advantages of lookup tables have been waning. Today, it is not uncommon for a CPU to be 10 to 100 times faster than main memory. As a result, using a table lookup may not be faster than doing the same calculation with machine instructions. So it's worthwhile to briefly discuss when table lookups offer a big advantage.
Although the CPU is much faster than main memory, the on-chip CPU cache memory subsystems operate at near CPU speeds. Therefore, table lookups can be cost effective if your table resides in cache memory on the CPU. This means that the way to get good performance using table lookups is to use small tables (because there's only so much room on the cache) and use tables whose entries you reference frequently (so the tables stay in the cache). See Write Great Code, Volume 1 (No Starch Press) or the electronic version of The Art of Assembly Language at http://webster.cs.ucr.edu/ or http://www.artofasm.com/ for details concerning the operation of cache memory and how you can optimize your use of cache memory.