Chapter Nine (Part 6)
|Table of Content||
Chapter Nine (Part 8)
ARITHMETIC AND LOGICAL OPERATIONS (Part 7)
9.6.1 - Masking Operations with the AND Instruction
9.6.2 - Masking Operations with the OR Instruction
9.7 - Packing and Unpacking Data Types
9.8.1 - Function Computation via Table Look Up
9.8.2 - Domain Conditioning
9.8.3 - Generating Tables
|9.6 Masking Operations|
A mask is a value used to force certain bits to zero or one within some other value. A mask typically affects certain bits in an operand (forcing them to zero or one) and leaves other bits unaffected. The appropriate use of masks allows you to extract bits from a value insert bits into a value and pack or unpacked a packed data type. The following sections describe these operations in detail.
9.6.1 Masking Operations with the AND Instruction
If you'll take a look at the truth table for the and
operation back in Chapter One
you'll note that if you fix either operand at zero the
result is always zero. If you set that operand to one
the result is always the value of
the other operand. We can use this property of the
and instruction to
selectively force certain bits to zero in a value without affecting other bits. This is
called masking out bits.
As an example
consider the ASCII codes for the digits
"0".."9". Their codes fall in the range 30h..39h respectively. To
convert an ASCII digit to its corresponding numeric value
you must subtract 30h from the
ASCII code. This is easily accomplished by logically anding the value with 0Fh. This
strips (sets to zero) all but the L.O. four bits producing the numeric value. You could
have used the subtract instruction
but most people use the
for this purpose.
9.6.2 Masking Operations with the OR Instruction
Much as you can use the
and instruction to
force selected bits to zero
you can use the
or instruction to force selected
bits to one. This operation is called masking in bits.
Remember the masking out operation described earlier with
and instruction? In that example we wanted to convert an ASCII code for a
digit to its numeric equivalent. You can use the
or instruction to reverse
this process. That is
convert a numeric value in the range 0..9 to the ASCII code for the
'0'..'9'. To do this
logically or the specified numeric value
One of the primary uses of the shift and rotate instructions is packing and unpacking data. Byte and word data types are chosen more often than any other since the 80x86 supports these two data sizes with hardware. If you don't need exactly eight or 16 bits using a byte or word to hold your data might be wasteful. By packing data you may be able to reduce memory requirements for your data by inserting two or more values into a single byte or word. The cost for this reduction in memory use is lower performance. It takes time to pack and unpack the data. Nevertheless for applications that aren't speed critical (or for those portions of the application that aren't speed critical) the memory savings might justify the use of packed data.
The data type that offers the most savings when using packing techniques is the boolean data type. To represent true or false requires a single bit. Therefore up to eight different boolean values can be packed into a single byte. This represents an 8:1 compression ratio therefore a packed array of boolean values requires only one-eighth the space of an equivalent unpacked array (where each boolean variable consumes one byte). For example the Pascal array
B:packed array[0..31] of boolean;
requires only four bytes when packed one value per bit. When packed one value per byte this array requires 32 bytes.
Dealing with a packed boolean array requires two operations. You'll need to insert a value into a packed variable (often called a packed field) and you'll need to extract a value from a packed field.
To insert a value into a packed boolean array
align the source bit with its position in the destination operand and then store that bit
into the destination operand. You can do this with a sequence of
and shift instructions. The first step is to mask out the corresponding bit in the
destination operand. Use an
and instruction for this. Then the source operand
is shifted so that it is aligned with the destination position
finally the source operand
is or'd into the destination operand. For example
if you want to insert bit zero of the
register into bit five of the
the following code could be
and cl 0DFh ;Clear bit five (the destination bit) and al 1 ;Clear all AL bits except the src bit. ror al 1 ;Move to bit 7 shr al 1 ;Move to bit 6 shr al 1 ;move to bit 5 or cl al
This code is somewhat tricky. It rotates the data to the right rather than shifting it to the left since this requires fewer shifts and rotate instructions.
To extract a boolean value
you simply reverse this
you move the desired bit into bit zero and then mask out all the other
bits. For example
to extract the data in bit five of the
cx register leaving
the single boolean value in bit zero of the
you'd use the
mov al cl shl al 1 ;Bit 5 to bit 6 shl al 1 ;Bit 6 to bit 7 rol al 1 ;Bit 7 to bit 0 and ax 1 ;Clear all bits except 0
To test a boolean variable in a packed array you needn't extract the bit and then test it you can test it in place. For example to test the value in bit five to see if it is zero or one the following code could be used:
test cl 00100000b jnz BitIsSet
Other types of packed data can be handled in a similar fashion except you need to work with two or more bits. For example suppose you've packed five different three bit fields into a sixteen bit value as shown below:
ax register contains the data to pack
you could use the following code to insert this data into field
mov ah al ;Do a shl by 8 shr ax 1 ;Reposition down to bits 6..8 shr ax 1 and ax 11100000b ;Strip undesired bits and DATA 0FE3Fh ;Set destination field to zero. or DATA ax ;Merge new data into field.
Extraction is handled in a similar fashion. First you strip the unneeded bits and then you justify the result:
mov ax DATA and ax 1Ch shr ax 1 shr ax 1 shr ax 1 shr ax 1 shr ax 1 shr ax 1
This code can be improved by using the following code sequence:
mov ax DATA shl ax 1 shl ax 1 mov al ah and ax 07h
Additional uses for packed data will be explored throughout this book.
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 (e.g. SNOBOL4 and Icon) directly support a table data type. Tables in these languages are essentially arrays whose elements you can access with an non-integer value (e.g. floating point string or any other data type). In this section we will adopt the assembly language programmer's view of tables.
A Table is an array containing preinitialized values that do not change during the execution of the program. A table can be compared to an array in the same way an integer constant can be compared to an integer variable. 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.
9.8.1 Function Computation via Table Look Up
Tables can do all kinds of things in assembly language. In HLLs like Pascal it's real easy to create a formula which computes some value. A simple looking arithmetic expression is equivalent to a considerable amount of 80x86 assembly language code. Assembly language programmers tend to compute many values via table look up rather than through the execution of some function. This has the advantage of being easier and often more efficient as well. Consider the following Pascal statement:
if (character >= 'a') and (character <= 'z') then character := chr(ord(character) - 32);
if statement converts the
character variable character from lower case to upper case if character is in the range
'a'..'z'. The 80x86 assembly language code that does the same thing is
mov al character cmp al 'a' jb NotLower cmp al 'z' ja NotLower and al 05fh ;Same operation as SUB AL 32 NotLower: mov character al
Had you buried this code in a nested loop you'd be hard pressed to improve the speed of this code without using a table look up. Using a table look up however allows you to reduce this sequence of instructions to just four instructions:
mov al character lea bx CnvrtLower xlat mov character al
CnvrtLower is a 256-byte table which contains the values 0..60h at indices 0..60h 41h..5Ah at indices 61h..7Ah and 7Bh..0FFh at indices 7Bh..0FFh. Often using this table look up facility will increase the speed of your code.
As the complexity of the function increases the performance benefits 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:
Via computation: mov al character cmp al 'a' jb NotLower cmp al 'z' ja NotLower and al 05fh jmp ConvertDone NotLower: cmp al 'A' jb ConvertDone cmp al 'Z' ja ConvertDone or al 20h ConvertDone: mov character al The table look up code to compute this same function is: mov al character lea bx SwapUL xlat mov character al
As you can see when computing a function via table look up no matter what the function is only the table changes not the code doing the look up.
Table look ups suffer from one major problem - functions computed via table look ups 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 find it very practical 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 function 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 efficiently 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 that can be implemented via table look
ups are those whose domain and range is always 0..255 (or some subset of this range). Such
functions are efficiently implemented 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 computed using the same two instructions (
table / xlat)
above. The only thing that ever changes is the look up table.
xlat instruction cannot be (conveniently)
used 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:
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
functions falling into this class are the most efficient. The following
Pascal function invocation
B := Func(X);
where Func is
consists of the following 80x86 code:
mov bx X mov al FuncTable [bx] mov B al
This code loads the function parameter into
uses this value (in the range 0..??) as an index into the
fetches the byte at that location
and stores the result into
the table must contain a valid entry for each possible value of
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
mod 80 and the Y coordinate with the formula
Y:=Posn div 80 (where
is the cursor position on the screen). This can be easily computed using the 80x86 code:
mov bl 80 mov ax Posn div bx ; 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 following code which realizes these two functions via table look up would improve the performance of your code considerably:
mov bx Posn mov al YCoord[bx] mov ah XCoord[bx]
If the domain of a function is within 0..255 but the range is outside this set the look up table will contain 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 Chapter Four the formula for indexing into a single dimensional array (of which a table is a special case):
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) defined by the following (pseudo) Pascal declaration:
You can easily create this function using the following 80x86 code (and of course the appropriate table):
mov bx X ;Get function input value and shl bx 1 ; convert to a word index into F. mov ax F[bx]
shl instruction multiplies the index by
providing the proper index into a table whose elements are words.
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.
9.8.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:
This says that the (computer) function SIN(x) is equivalent to the (mathematical) function sin x where
-2pi <= x <= 2pi
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.
This range limitation doesn't present any real problems
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
mod 2*pi and
used the result as the input to the
sin function. This truncates
to the domain
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 zero if
x is outside this range. Since
can take on 65
536 different values (being a 16 bit word)
creating a table containing
536 words where only the first five entries are non-zero seems to be quite wasteful.
we can still compute this function using a table look up if we use input
conditioning. The following assembly language code presents this principle:
xor ax ax ;AX := 0 assume X > 4. mov bx x cmp bx 4 ja ItsZero shl bx 1 mov ax val[bx] ItsZero:
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.
9.8.3 Generating Tables
One big problem with using table look ups is creating the table in the first 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 finally 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 modification to the sine function:
This states that x is an integer in the range
r is an integer. The computer can easily compute this with the
mov bx X shl bx 1 mov ax Sines [bx] ;Get SIN(X)*1000 mov bx R ;Compute R*(SIN(X)*1000) mul bx mov bx 1000 ;Compute (R*(SIN(X)*1000))/1000 div bx
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 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 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 following Turbo Pascal program:
program maketable; var i:integer; r:integer; f:text; begin assign(f 'sines.asm'); rewrite(f); for i := 0 to 359 do begin r := round(sin(I * 2.0 * pi / 360.0) * 1000.0); if (i mod 8) = 0 then begin writeln(f); write(f ' dw ' r); end else write(f ' ' r); end; close(f); end.
This program produces the following output:
dw 0 17 35 52 70 87 105 122 dw 139 156 174 191 208 225 242 259 dw 276 292 309 326 342 358 375 391 dw 407 423 438 454 469 485 500 515 dw 530 545 559 574 588 602 616 629 dw 643 656 669 682 695 707 719 731 dw 743 755 766 777 788 799 809 819 dw 829 839 848 857 866 875 883 891 dw 899 906 914 921 927 934 940 946 dw 951 956 961 966 970 974 978 982 dw 985 988 990 993 995 996 998 999 dw 999 1000 1000 1000 999 999 998 996 dw 995 993 990 988 985 982 978 974 dw 970 966 961 956 951 946 940 934 dw 927 921 914 906 899 891 883 875 dw 866 857 848 839 829 819 809 799 dw 788 777 766 755 743 731 719 707 dw 695 682 669 656 643 629 616 602 dw 588 574 559 545 530 515 500 485 dw 469 454 438 423 407 391 375 358 dw 342 326 309 292 276 259 242 225 dw 208 191 174 156 139 122 105 87 dw 70 52 35 17 0 -17 -35 -52 dw -70 -87 -105 -122 -139 -156 -174 -191 dw -208 -225 -242 -259 -276 -292 -309 -326 dw -342 -358 -375 -391 -407 -423 -438 -454 dw -469 -485 -500 -515 -530 -545 -559 -574 dw -588 -602 -616 -629 -643 -656 -669 -682 dw -695 -707 -719 -731 -743 -755 -766 -777 dw -788 -799 -809 -819 -829 -839 -848 -857 dw -866 -875 -883 -891 -899 -906 -914 -921 dw -927 -934 -940 -946 -951 -956 -961 -966 dw -970 -974 -978 -982 -985 -988 -990 -993 dw -995 -996 -998 -999 -999 -1000 -1000 -1000 dw -999 -999 -998 -996 -995 -993 -990 -988 dw -985 -982 -978 -974 -970 -966 -961 -956 dw -951 -946 -940 -934 -927 -921 -914 -906 dw -899 -891 -883 -875 -866 -857 -848 -839 dw -829 -819 -809 -799 -788 -777 -766 -755 dw -743 -731 -719 -707 -695 -682 -669 -656 dw -643 -629 -616 -602 -588 -574 -559 -545 dw -530 -515 -500 -485 -469 -454 -438 -423 dw -407 -391 -375 -358 -342 -326 -309 -292 dw -276 -259 -242 -225 -208 -191 -174 -156 dw -139 -122 -105 -87 -70 -52 -35 -17
Obviously it's much easier to write the Turbo Pascal program that generated this data than to enter (and verify) this data by hand. This little example shows how useful Pascal can be to the assembly language programmer!
Chapter Nine: Arithmetic And Logical
Operations (Part 7)
27 SEP 1996