Consider the following expression from a Pascal program:

	B := ((X=Y) and (A <= C)) or ((Z-A) <> 5);

B is a boolean variable and the remaining variables are all integers.

How do we represent boolean variables in assembly language? Although it takes only a single bit to represent a boolean value most assembly language programmers allocate a whole byte or word for this purpose. With a byte there are 256 possible values we can use to represent the two values true and false. So which two values (or which two sets of values) do we use to represent these boolean values? Because of the machine's architecture it's much easier to test for conditions like zero or not zero and positive or negative rather than to test for one of two particular boolean values. Most programmers (and indeed some programming languages like "C") choose zero to represent false and anything else to represent true. Some people prefer to represent true and false with one and zero (respectively) and not allow any other values. Others select 0FFFFh for true and 0 for false. You could also use a positive value for true and a negative value for false. All these mechanisms have their own advantages and drawbacks.

Using only zero and one to represent false and true offers one very big advantage: the 80x86 logical instructions (and or xor and to a lesser extent not) operate on these values exactly as you would expect. That is if you have two boolean variables A and B then the following instructions perform the basic logical operations on these two variables:

                mov     ax
A
and     ax
B
mov     C
ax           ;C := A and B;

mov     ax
A
or      ax
B
mov     C
ax           ;C := A or B;

mov     ax
A
xor     ax
B
mov     C
ax           ;C := A xor B;

mov     ax
A           ;Note that the NOT instruction does not
not     ax              ; properly compute B := not A by itself.
and     ax
1           ; I.e.
(NOT 0)does not equal one.
mov     B
ax           ;B := not A;

mov     ax
A           ;Another way to do B := NOT A;
xor     ax
1
mov     B
ax           ;B := not A;

Note as pointed out above that the not instruction will not properly compute logical negation. The bitwise not of zero is 0FFh and the bitwise not of one is 0FEh. Neither result is zero or one. However by anding the result with one you get the proper result. Note that you can implement the not operation more efficiently using the xor ax 1 instruction since it only affects the L.O. bit.

As it turns out using zero for false and anything else for true has a lot of subtle advantages. Specifically the test for true or false is often implicit in the execution of any logical instruction. However this mechanism suffers from a very big disadvantage: you cannot use the 80x86 and or xor and not instructions to implement the boolean operations of the same name. Consider the two values 55h and 0AAh. They're both non-zero so they both represent the value true. However if you logically and 55h and 0AAh together using the 80x86 and instruction the result is zero. (True and true) should produce true not false. A system that uses non-zero values to represent true and zero to represent false is an arithmetic logical system. A system that uses the two distinct values like zero and one to represent false and true is called a boolean logical system or simply a boolean system. You can use either system as convenient. Consider again the boolean expression:

	B := ((X=Y) and (A <= D)) or ((Z-A) <> 5);

The simple expressions resulting from this expression might be:

        Temp2 := X = Y
Temp := A <= D
Temp := Temp and Temp2
Temp2 := Z-A
Temp2 := Temp2 <> 5
B := Temp or Temp2

The assembly language code for these expressions could be:

                mov     ax
x           ;See if X = Y and load zero or
cmp     ax
y           ; one into AX to denote the result
jnz     L1              ; of this comparison.
mov     al
1           ;X = Y
jmp     L2
L1:             mov     al
0           ;X <> Y
L2:
mov     bx
A           ;See if A <= D and load zero or one
cmp     bx
D           ; into BX to denote the result of
jle     ST1             ; this comparison.
mov     bl
0
jmp     L3
ST1:            mov     bl
1
L3:
and     bl
al          ;Temp := Temp and Temp2

mov     ax
Z           ;See if (Z-A) <> 5.
sub     ax
A           ;Temp2 := Z-A;
cmp     ax
5           ;Temp2 := Temp2 <> 5;
jnz     ST2
mov     al
0
jmp     short L4
ST2:            mov     al
1
L4:
or      al
bl          ;Temp := Temp or Temp2;
mov     B
al           ;B := Temp;

As you can see this is a rather unwieldy sequence of statements. One slight optimization you can use is to assume a result is going to be true or false and initialize the corresponding boolean result ahead of time:

                mov     bl
0           ;Assume X <> Y
mov     ax
x
cmp     ax
Y
jne     L1
mov     bl
1           ;X is equal to Y
so make this true.
L1:
mov     bh
0           ;Assume not (A <= D)
mov     ax
A
cmp     ax
D
jnle    L2
mov     bh
1           ;A <= D so make this true
L2:
and     bl
bh          ;Compute logical AND of results.

mov     bh
0           ;Assume (Z-A) = 5
mov     ax
Z
sub     ax
A
cmp     ax
5
je      L3:
mov     bh
1           ;(Z-A) <> 5
L3:
or      bl
bh          ;Logical OR of results.
mov     B
bl           ;Save boolean result.

Of course if you have an 80386 or later processor you can use the setcc instructions to simplify this a bit:

                mov     ax
x
cmp     ax
y
sete    al              ;TEMP2 := X = Y

mov     bx
A
cmp     bx
D
setle   bl              ;TEMP := A <= D
and     bl
al          ;Temp := Temp and Temp2
mov     ax
Z
sub     ax
A           ;Temp2 := Z-A;
cmp     ax
5           ;Temp2 := Temp2 <> 5;
setne   al
or      bl
al          ;Temp := Temp or Temp2;
mov     B
bl           ;B := Temp;

This code sequence is obviously much better than the previous one but it will only execute on 80386 and later processors.

Another way to handle boolean expressions is to represent boolean values by states within your code. The basic idea is to forget maintaining a boolean variable throughout the execution of a code sequence and use the position within the code to determine the boolean result. Consider the following implementation of the above expression. First let's rearrange the expression to be

        B := ((Z-A) <> 5) or ((X=Y) and (A <= D));

This is perfectly legal since the or operation is commutative. Now consider the following implementation:

                mov     B
1            ;Assume the result is true.
mov     ax
Z           ;See if (Z-A) <> 5
sub     ax
A           ;If this condition is true
the
cmp     ax
5           ; result is always true so there
jne     Done            ; is no need to check the rest.

mov     ax
X           ;If X <> Y
the result is false

cmp     ax
Y           ; no matter what A and D contain
jne     SetBtoFalse

mov     ax
A           ;Now see if A <= D.
cmp     ax
D
jle     Done            ;If so
quit.
SetBtoFalse:            mov     B
0            ;If B is false
handle that here.
Done:

Notice that this section of code is a lot shorter than the first version above (and it runs on all processors). The previous translations did everything computationally. This version uses program flow logic to improve the code. It begins by assuming a true result and sets the B variable to true. It then checks to see if (Z-A) <> 5. If this is true the code branches to the done table because B is true no matter what else happens. If the program falls through to the mov ax X instruction we know that the result of the previous comparison is false. There is no need to save this result in a temporary since we implicitly know its value by the fact that we're executing the mov ax X instruction. Likewise the second group of statements above checks to see if X is equal to Y. If it is not we already know the result is false so this code jumps to the SetBtoFalse label. If the program begins executing the third set of statements above we know that the first result was false and the second result was true; the position of the code guarantees this. Therefore there is no need to maintain temporary boolean variables that keep track of the state of this computation.

Consider another example:

	B := ((A = E) or (F <> D)) and ((A<>B) or (F = D));

Computationally this expression would yield a considerable amount of code. However by using flow control you can reduce it to the following:

                mov     b
0            ;Assume result is false.
mov     ax
a           ;See if A = E.
cmp     ax
e
je      test2           ;If so
1st subexpression is true.

mov     ax
f           ;If not
check 2nd subexpression
cmp     ax
d           ; to see if F <> D.
je      Done            ;If so
we're done
else fall
; through to next tests.
Test2:          mov     ax
a           ;Does A <> B?
cmp     ax
b
jne     SetBto1         ;If so
we're done.

mov     ax
f           ;If not
see if F = D.
cmp     ax
d
jne     Done

SetBto1:        mov     b
1
Done:

There is one other difference between using control flow vs. computation logic: when using control flow methods you may skip the majority of the instructions that implement the boolean formula. This is known as short-circuit evaluation. When using the computation model even with the setcc instruction you wind up executing most of the statements. Keep in mind that this is not necessarily a disadvantage. On pipelined processors it may be much faster to execute several additional instructions rather than flush the pipeline and prefetch queue. You may need to experiment with your code to determine the best solution.

When working with boolean expressions don't forget the that you might be able to optimize your code by simplifying those boolean expressions (See Chapter Two). You can use algebraic transformations (especially DeMorgan's theorems) and the mapping method to help reduce the complexity of an expression.

Chapter Nine: Arithmetic And Logical Operations (Part 2)
27 SEP 1996