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.