[ Pobierz całość w formacie PDF ]
It is not uncommon to see the following puzzling instruction in a 80x86
program:
xor eax, eax ; eax = 0
A number XOR ed with itself always results in zero. This instruction is used
because its machine code is smaller than the correspondingMOVinstruction.
3.3 Avoiding Conditional Branches
Modern processors use very sophisticated techniques to execute code as
quickly as possible. One common technique is known as speculative execu-
tion. This technique uses the parallel processing capabilities of the CPU to
execute multiple instructions at once. Conditional branches present a prob-
lem with this idea. The processor, in general, does not know whether the
branch will be taken or not. If it is taken, a different set of instructions will
be executed than if it is not taken. Processors try to predict whether the
branch will be taken. If the prediciton is wrong, the processor has wasted
its time executing the wrong code.
54 CHAPTER 3. BIT OPERATIONS
One way to avoid this problem is to avoid using conditional branches
when possible. The sample code in 3.1.5 provides a simple example of where
one could do this. In the previous example, the on bits of the EAX register
are counted. It uses a branch to skip theINCinstruction. Figure 3.3 shows
how the branch can be removed by using theADCinstruction to add the
carry flag directly.
TheSETxx instructions provide a way to remove branches in certain
cases. These instructions set the value of a byte register or memory location
to zero or one based on the state of the FLAGS register. The characters
afterSETare the same characters used for conditional branches. If the
corresponding condition of theSETxx is true, the result stored is a one, if
false a zero is stored. For example,
setz al ; AL = 1 if Z flag is set, else 0
Using these instructions, one can develop some clever techniques that cal-
cuate values without branches.
For example, consider the problem of finding the maximum of two values.
The standard approach to solving this problem would be to use aCMPand use
a conditional branch to act on which value was larger. The example program
below shows how the maximum can be found without any branches.
1 ; file: max.asm
2 %include "asm_io.inc"
3 segment .data
4
5 message1 db "Enter a number: ",0
6 message2 db "Enter another number: ", 0
7 message3 db "The larger number is: ", 0
8
9 segment .bss
10
11 input1 resd 1 ; first number entered
12
13 segment .text
14 global _asm_main
15 _asm_main:
16 enter 0,0 ; setup routine
17 pusha
18
19 mov eax, message1 ; print out first message
20 call print_string
21 call read_int ; input first number
3.3. AVOIDING CONDITIONAL BRANCHES 55
22 mov [input1], eax
23
24 mov eax, message2 ; print out second message
25 call print_string
26 call read_int ; input second number (in eax)
27
28 xor ebx, ebx ; ebx = 0
29 cmp eax, [input1] ; compare second and first number
30 setg bl ; ebx = (input2 > input1) ? 1 : 0
31 neg ebx ; ebx = (input2 > input1) ? 0xFFFFFFFF : 0
32 mov ecx, ebx ; ecx = (input2 > input1) ? 0xFFFFFFFF : 0
33 and ecx, eax ; ecx = (input2 > input1) ? input2 : 0
34 not ebx ; ebx = (input2 > input1) ? 0 : 0xFFFFFFFF
35 and ebx, [input1] ; ebx = (input2 > input1) ? 0 : input1
36 or ecx, ebx ; ecx = (input2 > input1) ? input2 : input1
37
38 mov eax, message3 ; print out result
39 call print_string
40 mov eax, ecx
41 call print_int
42 call print_nl
43
44 popa
45 mov eax, 0 ; return back to C
46 leave
47 ret
The trick is to create a bit mask that can be used to select the correct
value for the maximum. TheSETGinstruction in line 30 sets BL to 1 if the
second input is the maximum or 0 otherwise. This is not quite the bit mask
desired. To create the required bit mask, line 31 uses theNEGinstruction
on the entire EBX register. (Note that EBX was zeroed out earlier.) If
EBX is 0, this does nothing; however, if EBX is 1, the result is the two s
complement representation of -1 or 0xFFFFFFFF. This is just the bit mask
required. The remaining code uses this bit mask to select the correct input
as the maximum.
An alternative trick is to use theDECstatement. In the above code, if the
NEGis replaced with aDEC, again the result will either be 0 or 0xFFFFFFFF.
However, the values are reversed than when using theNEGinstruction.
56 CHAPTER 3. BIT OPERATIONS
3.4 Manipulating bits in C
3.4.1 The bitwise operators of C
Unlike some high-level languages, C does provide operators for bitwise
[ Pobierz całość w formacie PDF ]