Table of Content | Chapter Nine (Part 2) |
CHAPTER
NINE: ARITHMETIC AND LOGICAL OPERATIONS (Part 1) |
||
9.0 -
Chapter Overview 9.1 - Arithmetic Expressions 9.1.1 - Simple Assignments 9.1.2 - Simple Expressions 9.1.3 - Complex Expressions 9.1.4 - Commutative Operators 9.2 - Logical (Boolean) Expressions 9.3 - Multiprecision Operations 9.3.1 - Multiprecision Addition Operations 9.3.2 - Multiprecision Subtraction Operations 9.3.3 - Extended Precision Comparisons 9.3.4 - Extended Precision Multiplication 9.3.5 - Extended Precision Division 9.3.6 - Extended Precision NEG Operations 9.3.7 - Extended Precision AND Operations 9.3.8 - Extended Precision OR Operations 9.3.9 - Extended Precision XOR Operations 9.3.10 - Extended Precision NOT Operations 9.3.11 - Extended Precision Shift Operations 9.3.12 - Extended Precision Rotate Operations 9.4 - Operating on Different Sized Operands 9.5 - Machine and Arithmetic Idioms 9.5.1 - Multiplying Without MUL and IMUL 9.5.2 - Division Without DIV and IDIV 9.5.3 - Using AND to Compute Remainders 9.5.4 - Implementing Modulo-n Counters with AND 9.5.5 - Testing an Extended Precision Value for 0FFFF..FFh 9.5.6 - TEST Operations 9.5.7 - Testing Signs with the XOR Instruction 9.6 - Masking Operations 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 - Tables 9.8.1 - Function Computation via Table Look Up 9.8.2 - Domain Conditioning 9.8.3 - Generating Tables 9.9 - Sample Programs 9.9.1 - Converting Arithmetic Expressions to Assembly Language 9.9.2 - Boolean Operations Example 9.9.3 - 64-bit Integer I/O 9.9.4 - Packing and Unpacking Date Data Types |
Copyright 1996 by Randall Hyde
All rights reserved. Duplication other than for immediate display through a browser is prohibited by U.S. Copyright Law. This material is provided on-line as a beta-test of this text. It is for the personal use of the reader only. If you are interested in using this material as part of a course please contact rhyde@cs.ucr.edu Supporting software and other materials are available via anonymous ftp from ftp.cs.ucr.edu. See the "/pub/pc/ibmpcdir" directory for details. You may also download the material from "Randall Hyde's Assembly Language Page" at URL: http://webster.ucr.edu Notes: This document does not contain the laboratory exercises programming assignments exercises or chapter summary. These portions were omitted for several reasons: either they wouldn't format properly they contained hyperlinks that were too much work to resolve they were under constant revision or they were not included for security reasons. Such omission should have very little impact on the reader interested in learning this material or evaluating this document. This document was prepared using Harlequin's Web Maker 2.2 and Quadralay's Webworks Publisher. Since HTML does not support the rich formatting options available in Framemaker this document is only an approximation of the actual chapter from the textbook. If you are absolutely dying to get your hands on a version other than HTML you might consider having the UCR Printing a Reprographics Department run you off a copy on their Xerox machines. For details please read the following EMAIL message I received from the Printing and Reprographics Department:
We are currently working on ways to publish this text in a form other than HTML (e.g. Postscript PDF Frameviewer hard copy etc.). This however is a low-priority project. Please do not contact Randall Hyde concerning this effort. When something happens an announcement will appear on "Randall Hyde's Assembly Language Page." Please visit this WEB site at http://webster.ucr.edu for the latest scoop. Redesigned 10/2000 with "MS FrontPage 98" using
17" monitor 1024x768 |
There is a lot more to assembly language than knowing the operations of a handful of machine instructions. You've got to know how to use them and what they can do. Many instructions are useful for operations that have little to do with their mathematical or obvious functions. This chapter discusses how to convert expressions from a high level language into assembly language. It also discusses advanced arithmetic and logical operations including multiprecision operations and tricks you can play with various instructions.
This chapter discusses six main subjects: converting HLL arithmetic expressions into assembly language logical expressions extended precision arithmetic and logical operations operating on different sized operands machine and arithmetic idioms and masking operations. Like the preceding chapters this chapter contains considerable material that you may need to learn immediately if you're a beginning assembly language programmer. The sections below that have a "*" prefix are essential. Those sections with a "o" discuss advanced topics that you may want to put off for a while.
None of this material is particularly difficult to understand. However there are a lot of new topics here and taking them a few at a time will certain help you absorb the material better. Those topics with the "*" prefix are ones you will frequently use; hence it is a good idea to study these first.
Probably the biggest shock to beginners facing assembly language for the very first time is the lack of familiar arithmetic expressions. Arithmetic expressions in most high level languages look similar to their algebraic equivalents:
X:=Y*Z;
In assembly language you'll need several statements to accomplish this same task e.g.
mov ax y imul z mov x ax
Obviously the HLL version is much easier to type read and understand. This point more than any other is responsible for scaring people away from assembly language.
Although there is a lot of typing involved converting an arithmetic expression into assembly language isn't difficult at all. By attacking the problem in steps the same way you would solve the problem by hand you can easily break down any arithmetic expression into an equivalent sequence of assembly language statements. By learning how to convert such expressions to assembly language in three steps you'll discover there is little difficulty to this task.
The easiest expressions to convert to assembly language are the simple assignments. Simple assignments copy a single value into a variable and take one of two forms:
variable := constant
or
variable := variable
If variable appears in the current data segment (e.g.
DSEG
)
converting the first form to assembly language is easy
just use the assembly language
statement:
mov variable constant
This move immediate instruction copies the constant into the variable.
The second assignment above is somewhat complicated since
the 80x86 doesn't provide a memory-to-memory mov
instruction. Therefore
to
copy one memory variable into another
you must move the data through a register. If
you'll look at the encoding for the mov
instruction in the appendix
you'll
notice that the mov ax
memory
and mov memory
ax
instructions
are shorter than moves involving other registers. Therefore
if the ax
register is available
you should use it for this operation. For example
var1 := var2;
becomes
mov ax var2 mov var1 ax
Of course
if you're using the ax
register for
something else
one of the other registers will suffice. Regardless
you must use a
register to transfer one memory location to another.
This discussion of course assumes that both variables are in memory. If possible you should try to use a register to hold the value of a variable.
The next level of complexity up from a simple assignment is a simple expression. A simple expression takes the form:
var := term1 op term2;
Var
is a variable
term1
and
term2
are variables or constants
and op
is some arithmetic operator
(addition
subtraction
multiplication
etc.).
As simple as this expression appears most expressions take this form. It should come as no surprise then that the 80x86 architecture was optimized for just this type of expression.
A typical conversion for this type of expression takes the following form:
mov ax term1 op ax term2 mov var ax
Op
is the mnemonic that corresponds to the
specified operation (e.g.
"+" = add
"-" = sub
etc.).
There are a few inconsistencies you need to be aware of.
First
the 80x86's {i}mul
instructions do not allow immediate operands on
processors earlier than the 80286. Further
none of the processors allow immediate
operands with {i}div
. Therefore
if the operation is multiplication or
division and one of the terms is a constant value
you may need to load this constant into
a register or memory location and then multiply or divide ax
by that value.
Of course
when dealing with the multiply and divide instructions on the 8086/8088
you
must use the ax
and dx
registers. You cannot use arbitrary
registers as you can with other operations. Also
don't forget the sign extension
instructions if you're performing a division operation and you're dividing one 16/32 bit
number by another. Finally
don't forget that some instructions may cause overflow. You
may want to check for an overflow (or underflow) condition after an arithmetic operation.
Examples of common simple expressions:
X := Y + Z; mov ax y add ax z mov x ax X := Y - Z; mov ax y sub ax z mov x ax X := Y * Z; {unsigned} mov ax y mul z ;Use IMUL for signed arithmetic. mov x ax ;Don't forget this wipes out DX. X := Y div Z; {unsigned div} mov ax y mov dx 0 ;Zero extend AX into DX div z mov x ax X := Y div Z; {signed div} mov ax y cwd ;Sign extend AX into DX idiv z mov x ax X := Y mod Z; {unsigned remainder} mov ax y mov dx 0 ;Zero extend AX into DX div z mov x dx ;Remainder is in DX X := Y mod Z; {signed remainder} mov ax y cwd ;Sign extend AX into DX idiv z mov x dx ;Remainder is in DX
Since it is possible for an arithmetic error to occur
you
should generally test the result of each expression for an error before or after
completing the operation. For example
unsigned addition
subtraction
and multiplication
set the carry flag if an overflow occurs. You can use the jc
or jnc
instructions immediately after the corresponding instruction sequence to test for
overflow. Likewise
you can use the jo
or jno
instructions after
these sequences to test for signed arithmetic overflow. The next two examples demonstrate
how to do this for the add
instruction:
X := Y + Z; {unsigned} mov ax y add ax z mov x ax jc uOverflow X := Y + Z; {signed} mov ax y add ax z mov x ax jo sOverflow
Certain unary operations also qualify as simple expressions. A good example of a unary operation is negation. In a high level language negation takes one of two possible forms:
var := -var or var1 := -var2
Note that var := -constant
is really a simple
assignment
not a simple expression. You can specify a negative constant as an operand to
the mov
instruction:
mov var -14
To handle the first form of the negation operation above use the single assembly language statement:
neg var
If two different variables are involved then use the following:
mov ax var2 neg ax mov var1 ax
Overflow only occurs if you attempt to negate the most
negative value (-128 for eight bit values
-32768 for sixteen bit values
etc.). In this
instance the 80x86 sets the overflow flag
so you can test for arithmetic overflow using
the jo
or jno
instructions. In all other cases the80x86 clears
the overflow flag. The carry flag has no meaning after executing the neg
instruction since neg
(obviously) does not apply to unsigned operands.
A complex expression is any arithmetic expression involving more than two terms and one operator. Such expressions are commonly found in programs written in a high level language. Complex expressions may include parentheses to override operator precedence function calls array accesses etc. While the conversion of some complex expressions to assembly language is fairly straight-forward others require some effort. This section outlines the rules you use to convert such expressions.
A complex function that is easy to convert to assembly language is one that involves three terms and two operators for example:
W := W - Y - Z;
Clearly the straight-forward assembly language conversion
of this statement will require two sub
instructions. However
even with an
expression as simple as this one
the conversion is not trivial. There are actually two
ways to convert this from the statement above into assembly language:
mov ax w sub ax y sub ax z mov w ax
and
mov ax y sub ax z sub w ax
The second conversion since it is shorter looks better. However it produces an incorrect result (assuming Pascal-like semantics for the original statement). Associativity is the problem. The second sequence above computes W := W - (Y - Z) which is not the same as W := (W - Y) - Z. How we place the parentheses around the subexpressions can affect the result. Note that if you are interested in a shorter form you can use the following sequence:
mov ax y add ax z sub w ax
This computes W:=W-(Y+Z). This is equivalent to W := (W - Y) - Z.
Precedence is another issue. Consider the Pascal expression:
X := W * Y + Z;
Once again there are two ways we can evaluate this expression:
X := (W * Y) + Z; or X := W * (Y + Z);
By now you're probably thinking that this text is crazy. Everyone knows the correct way to evaluate these expressions is the second form provided in these two examples. However you're wrong to think that way. The APL programming language for example evaluates expressions solely from right to left and does not give one operator precedence over another.
Most high level languages use a fixed set of precedence rules to describe the order of evaluation in an expression involving two or more different operators. Most programming languages for example compute multiplication and division before addition and subtraction. Those that support exponentiation (e.g. FORTRAN and BASIC) usually compute that before multiplication and division. These rules are intuitive since almost everyone learns them before high school. Consider the expression:
X op1 Y op2 Z
If op1 takes precedence over op2 then this evaluates to (X op1 Y) op2 Z otherwise if op2 takes precedence over op1 then this evaluates to X op1 (Y op2 Z ). Depending upon the operators and operands involved these two computations could produce different results.
When converting an expression of this form into assembly language you must be sure to compute the subexpression with the highest precedence first. The following example demonstrates this technique:
; W := X + Y * Z; mov bx x mov ax y ;Must compute Y * Z first since mul z ; "*" has the highest precedence. add bx ax ;Now add product with X's value. mov w bx ;Save away result.
Since addition is a commutative operation we could optimize the above code to produce:
; W := X + Y * Z; mov ax y ;Must compute Y * Z first since mul z ; "*" has the highest precedence. add ax x ;Now add product with X's value. mov w ax ;Save away result.
If two operators appearing within an expression have the same precedence then you determine the order of evaluation using associativity rules. Most operators are left associative meaning that they evaluate from left to right. Addition subtraction multiplication and division are all left associative. A right associative operator evaluates from right to left. The exponentiation operator in FORTRAN and BASIC is a good example of a right associative operator:
2^2^3 is equal to 2^(2^3) not (2^2)^3
The precedence and associativity rules determine the order of evaluation. Indirectly these rules tell you where to place parentheses in an expression to determine the order of evaluation. Of course you can always use parentheses to override the default precedence and associativity. However the ultimate point is that your assembly code must complete certain operations before others to correctly compute the value of a given expression. The following examples demonstrate this principle:
; W := X - Y - Z mov ax x ;All the same operator so we need sub ax y ; to evaluate from left to right sub ax z ; because they all have the same mov w ax ; precedence. ; W := X + Y * Z mov ax y ;Must compute Y * Z first since imul z ; multiplication has a higher add ax x ; precedence than addition. mov w ax ; W := X / Y - Z mov ax x ;Here we need to compute division cwd ; first since it has the highest idiv y ; precedence. sub ax z mov w ax ; W := X * Y * Z mov ax y ;Addition and multiplication are imul z ; commutative therefore the order imul x ; of evaluation does not matter mov w ax
There is one exception to the associativity rule. If an expression involves multiplication and division it is always better to perform the multiplication first. For example given an expression of the form:
W := X/Y * Z
It is better to compute X*Z
and then divide
the result by Y
rather than divide X
by Y
and
multiply the quotient by Z
. There are two reasons this approach is better.
First
remember that the imul
instruction always produces a 32 bit result
(assuming 16 bit operands). By doing the multiplication first
you automatically sign
extend the product into the dx
register so you do not have to sign extend ax
prior to the division. This saves the execution of the cwd
instruction. A
second reason for doing the multiplication first is to increase the accuracy of the
computation. Remember
(integer) division often produces an inexact result. For example
if you compute 5/2 you will get the value two
not 2.5. Computing (5/2)*3 produces six.
However
if you compute (5*3)/2 you get the value seven which is a little closer to the
real quotient (7.5). Therefore
if you encounter an expression of the form:
W := X/Y*Z;
You can usually convert this to assembly code:
mov ax x imul z idiv z mov w ax
Of course if the algorithm you're encoding depends on the truncation effect of the division operation you cannot use this trick to improve the algorithm. Moral of the story: always make sure you fully understand any expression you are converting to assembly language. Obviously if the semantics dictate that you must perform the division first do so.
Consider the following Pascal statement:
W := X - Y * Z;
This is similar to a previous example except it uses subtraction rather than addition. Since subtraction is not commutative you cannot compute Y * Z and then subtract X from this result. This tends to complicate the conversion a tiny amount. Rather than a straight forward multiply and addition sequence you'll have to load X into a register multiply Y and Z leaving their product in a different register and then subtract this product from X e.g.
mov bx x mov ax y imul z sub bx ax mov w bx
This is a trivial example that demonstrates the need for
temporary variables in an expression. The code uses the bx
register to
temporarily hold a copy of X
until it computes the product of Y
and Z
. As your expression increase in complexity
the need for temporaries
grows. Consider the following Pascal statement:
W := (A + B) * (Y + Z);
Following the normal rules of algebraic evaluation you compute the subexpressions inside the parentheses (i.e. the two subexpressions with the highest precedence) first and set their values aside. When you computed the values for both subexpressions you can compute their sum. One way to deal with complex expressions like this one is to reduce it to a sequence of simple expressions whose results wind up in temporary variables. For example we can convert the single expression above into the following sequence:
Temp1 := A + B; Temp2 := Y + Z; W := Temp1 * Temp2;
Since converting simple expressions to assembly language is quite easy it's now a snap to compute the former complex expression in assembly. The code is
mov ax a add ax b mov Temp1 ax mov ax y add ax z mov temp2 ax mov ax temp1 imul temp2 mov w ax
Of course this code is grossly inefficient and it requires that you declare a couple of temporary variables in your data segment. However it is very easy to optimize this code by keeping temporary variables as much as possible in 80x86 registers. By using 80x86 registers to hold the temporary results this code becomes:
mov ax a add ax b mov bx y add bx z imul bx mov w ax
Yet another example:
X := (Y+Z) * (A-B) / 10;
This can be converted to a set of four simple expressions:
Temp1 := (Y+Z) Temp2 := (A-B) Temp1 := Temp1 * Temp2 X := Temp1 / 10
You can convert these four simple expressions into the assembly language statements:
mov ax y ;Compute AX := Y+Z add ax z mov bx a ;Compute BX := A-B sub bx b mul bx ;Compute AX := AX * BX this also sign mov bx 10 ; extends AX into DX for idiv. idiv bx ;Compute AX := AX / 10 mov x ax ;Store result into X
The most important thing to keep in mind is that temporary values if possible should be kept in registers. Remember accessing an 80x86 register is much more efficient than accessing a memory location. Use memory locations to hold temporaries only if you've run out of registers to use.
Ultimately converting a complex expression to assembly language is little different than solving the expression by hand. Instead of actually computing the result at each stage of the computation you simply write the assembly code that computes the results. Since you were probably taught to compute only one operation at a time this means that manual computation works on "simple expressions" that exist in a complex expression. Of course converting those simple expressions to assembly is fairly trivial. Therefore anyone who can solve a complex expression by hand can convert it to assembly language following the rules for simple expressions.
If "@" represents some operator that operator is commutative if the following relationship is always true:
(A @ B) = (B @ A)
As you saw in the previous section commutative operators are nice because the order of their operands is immaterial and this lets you rearrange a computation often making that computation easier or more efficient. Often rearranging a computation allows you to use fewer temporary variables. Whenever you encounter a commutative operator in an expression you should always check to see if there is a better sequence you can use to improve the size or speed of your code. The following tables list the commutative and non-commutative operators you typically find in high level languages:
Pascal | C/C++ | Description |
---|---|---|
+ | + | Addition |
* | * | Multiplication |
AND | && or & | Logical or bitwise AND |
OR | || or | | Logical or bitwise OR |
XOR | ^ | (Logical or) Bitwise exclusive-OR |
= | == | Equality |
<> | != | Inequality |
Pascal | C/C++ | Description |
---|---|---|
- | - | Subtraction |
/ or DIV | / | Division |
MOD | % | Modulo or remainder |
< | < | Less than |
<= | <= | Less than or equal |
> | > | Greater than |
>= | >= | Greater than or equal |
Table of Content | Chapter Nine (Part 2) |
Chapter Nine: Arithmetic And Logical
Operations (Part 1)
27 SEP 1996