Here the highest bit of each byte is masked out to avoid a possible carry from each byte into the next one when adding. The code is using XOR rather than ADD to put back the high bit again, in order to avoid carry. If the second addend may have the high bit set as well, it must be masked too. No masking is needed if none of the two addends have the high bit set.

The next example finds the length of a zero-terminated string by searching for the first byte of zero. It is faster than using REPNE SCASB if the string is long or the branch misprediction penalty is not severe:

The string should of course be aligned by 4. The code may read past the end of the string, so the string should not be placed at the end of a segment. Handling 4 bytes simultaneously can be quite difficult. The code in example 17.4 uses a formula which generates a nonzero value for a byte if, and only if, the byte is zero. This makes it possible to test all four bytes in one operation. This algorithm involves the subtraction of 1 from all bytes (in the LEA instruction). I have not masked out the highest bit of each byte before subtracting, as I did in example 17.3, so the subtraction may generate a borrow to the next byte, but only if it is zero, and this is exactly the situation where we don't care what the next byte is, because we are searching forwards for the first zero. If you want to search for a byte value other than zero, then you may XOR all four bytes with the value you are searching for, and then use the method above to search for zero.

18 Problematic Instructions

18.1 XCHG (all processors)

The XCHG register,[memory] instruction is dangerous. This instruction always has an implicit LOCK prefix which prevents it from using the cache. This instruction is therefore very time consuming, and should always be avoided.

18.2 Shifts and rotates (P4)

Shifts and rotates on general purpose registers are slow on the P4. You may consider using MMX or XMM registers instead or replacing left shifts by additions.

constant with a combination of other instructions such as SHL, ADD, SUB, and LEA. For example IMUL EAX,5 can be replaced by LEA EAX,[EAX+4*EAX]. On the P4, SHL and LEA with a scale factor are also relatively slow, so the fastest way on this processor is to use additions.

Multiplying a register with a constant can be done with the following macro, which uses only additions:

;This macro multiplies an integer by a constant, using only

;additions. Parameters:

;REG1: an 8-bit, 16-bit or 32-bit register containing the number

;to multiply. The result will be returned in REG1.

;REG2: a spare register of the same size. (will not be used if

;FACTOR is a power of 2).

;FACTOR: a positive integer constant to multiply by.

MULTIPLY MACRO REG1, REG2, FACTOR

For example, IMUL EAX,100 can be replaced by

MULTIPLY EAX, EBX, 100 which will be expanded to:

This method is considerably faster than using MUL or IMUL on the P4, unless the factor is very big. However, since this method uses many instructions, it should only be used if latency is critical and throughput is not critical. If you have opportunities for handling data in parallel, or if your code contains many integer multiply and shift operations, then it may be faster to use MMX or XMM registers.

18.7 Division (all processors)

Both integer division and floating-point division are quite time consuming on all processors. Various methods for reducing the number of divisions are explained on page 10. Several methods to improve code that contains division are discussed below.

Integer division by a power of 2 (all processors)

Integer division by a power of two can be done by shifting right. Dividing an unsigned integer by 2N:

Dividing a signed integer by 2N:

Obviously, you should prefer the unsigned version if the dividend is certain to be nonnegative.

Integer division by a constant (all processors)

Dividing by a constant can be done by multiplying with the reciprocal. A useful algorithm for integer division by a constant is as follows:

To calculate the unsigned integer division q = x / d, you first calculate the reciprocal of the divisor, f = 2r / d, where r defines the position of the binary decimal point (radix point). Then multiply x with f and shift right r positions. The maximum value of r is 32+b, where b is the number of binary digits in d minus 1. (b is the highest integer for which 2b ≤ d). Use r = 32+b to cover the maximum range for the value of the dividend x.

This method needs some refinement in order to compensate for rounding errors. The following algorithm will give you the correct result for unsigned integer division with truncation, i.e. the same result as the DIV instruction gives (Thanks to Terje Mathisen who invented this method):

b = (the number of significant bits in d) - 1

r = 32 + b f = 2r / d

If f is an integer then d is a power of 2: goto case A.

If f is not an integer, then check if the fractional part of f is < 0.5 If the fractional part of f < 0.5: goto case B.

If the fractional part of f > 0.5: goto case C.

case A (d = 2b): result = x SHR b

case B (fractional part of f < 0.5): round f down to nearest integer result = ((x+1) * f) SHR r

case C (fractional part of f > 0.5): round f up to nearest integer result = (x * f) SHR r

Example:

Assume that you want to divide by 5.

5 = 101B.

b = (number of significant binary digits) - 1 = 2 r = 32+2 = 34

f = 234 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(hexadecimal)

The fractional part is greater than a half: use case C.

Round f up to 0CCCCCCCDH.

The following code divides EAX by 5 and returns the result in EDX:

After the multiplication, EDX contains the product shifted right 32 places. Since r = 34 you have to shift 2 more places to get the result. To divide by 10, just change the last line to SHR EDX,3.

In case B we would have:

This code works for all values of x except 0FFFFFFFFH which gives zero because of overflow in the ADD EAX,1 instruction. If x = 0FFFFFFFFH is possible, then change the code to:

If the value of x is limited, then you may use a lower value of r, i.e. fewer digits. There can be several reasons for using a lower value of r:

• you may set r = 32 to avoid the SHR EDX,b in the end.

•you may set r = 16+b and use a multiplication instruction that gives a 32-bit result rather than 64 bits. This will free the EDX register:

IMUL EAX,0CCCDh / SHR EAX,18

•you may choose a value of r that gives case C rather than case B in order to avoid the ADD EAX,1 instruction

The maximum value for x in these cases is at least 2r-b, sometimes higher. You have to do a systematic test if you want to know the exact maximum value of x for which the code works correctly.

You may want to replace the slow multiplication instruction with faster instructions as explained on page 114.

The following example divides EAX by 10 and returns the result in EAX. I have chosen r=17 rather than 19 because it happens to give a code that is easier to optimize, and covers the same range for x. f = 217 / 10 = 3333h, case B: q = (x+1)*3333h:

LEA EBX,[EAX+2*EAX+3]

LEA ECX,[EAX+2*EAX+3]

SHL EBX,4

MOV EAX,ECX

SHL ECX,8

ADD EAX,EBX

SHL EBX,8

ADD EAX,ECX

ADD EAX,EBX

SHR EAX,17

A systematic test shows that this code works correctly for all x < 10004H.

Repeated integer division by the same value (all processors)

If the divisor is not known at assembly time, but you are dividing repeatedly with the same divisor, then you may use the same method as above. The code has to distinguish between case A, B and C and calculate f before doing the divisions.

The code that follows shows how to do multiple divisions with the same divisor (unsigned division with truncation). First call SET_DIVISOR to specify the divisor and calculate the reciprocal, then call DIVIDE_FIXED for each value to divide by the same divisor.

Example 18.1, repeated integer division with same divisor

.DATA