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