[Next] [Art of Assembly][Randall Hyde]

Art of Assembly Language: Chapter Nine


Chapter Nine - Arithmetic and Logical Operations
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:
Hello Again Professor Hyde,

Dallas gave me permission to take orders for the Computer Science 13 Manuals. We would need to take charge card orders. The only cards we take are: Master Card, Visa, and Discover. They would need to send the name, numbers, expiration date, type of card, and authorization to charge $95.00 for the manual and shipping, also we should have their phone number in case the company has any trouble delivery. They can use my e-mail address for the orders and I will process them as soon as possible. I would assume that two weeks would be sufficient for printing, packages and delivery time.

I am open to suggestions if you can think of any to make this as easy as possible.

Thank You for your business,

Kathy Chapman, Assistant
Printing and Reprographics
University of California
Riverside
(909) 787-4443/4444
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.

Art of Assembly Bug Report Submissions

Did you find an error in The Art of Assembly Language Programming? You can let me know by using the form below to report the error to me so that I can correct the error for the next beta version. Thank you.

The Submission Form

Please provide your name and e-mail address so I can contact you if I have any questions regarding your submission.

What is your name?
What is your e-mail address?

In the space provided below, please describe the nature of the problem. To help me find the problem quicker, please also provide the chapter and section number containing the problem. If you are reporting a problem with a hardcopy version of the textbook, please provide the page number as well.


Chapter Nine Arithmetic and Logical Operations

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.

9.0 Chapter Overview

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.
* Arithmetic expressions

* Simple assignments

* Simple expressions

* Complex expressions

* Commutative operators

* Logical expressions

* Multiprecision operations

* Multiprecision addition operations

* Multiprecision subtraction operations

* Extended precision comparisons

o Extended precision multiplication

o Extended precision division

o Extended precision negation

* Extended precision AND, OR, XOR, and NOT

o Extended precision shift and rotate operations

o Operating on different sized operands

* Multiplying without MUL and IMUL

o Division without DIV and IDIV

o Using AND to compute remainders

o Modulo-n Counters with AND

o Testing for 0FFFFF...FFFh

* Test operations

o Testing signs with the XOR instructions

o Masking operations

o Masking with the AND instructions

o Masking with the OR instruction

o Packing and unpacking data types

o Table lookups 

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.






9.1 Arithmetic Expressions


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.






9.1.1 Simple Assignments


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.







9.1.2 Simple Expressions


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.






9.1.3 Complex Expressions


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.






9.1.4 Commutative Operators


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:




Some Common Commutative Binary Operators

PascalC/C++Description

++Addition

**Multiplication

AND&& or &Logical or bitwise AND

OR|| or |Logical or bitwise OR

XOR^(Logical or) Bitwise exclusive-OR

===Equality

<>!=Inequality





Some Common Noncommutative Binary Operators

PascalC/C++Description

--Subtraction

/ or DIV/Division

MOD%Modulo or remainder

<<Less than

<=<=Less than or equal

>>Greater than

>=>=Greater than or equal




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 



Art of Assembly: Chapter Nine - 27 SEP 1996



[Next] [Art of Assembly][Randall
Hyde]