Nynaeve

One relatively common compiler optimization that can be handy to quickly recognize relates to conditional assignment (where a variable is conditionally assigned either one value or an alternate value). This optimization typically happens when the ternary operator in C (“?:”) is used, although it can also be used in code like so:

// var = condition ? value1 : value2;
if (condition)
  var = value1;
else
  var = value2;

The primary optimization that the compiler would try to make here is the elimination of explicit branch instructions.

Although conditional move operations were added to the x86 instruction set around the time of the Pentium II, the Microsoft C compiler still does not use them by default when targeting x86 platforms (in contrast, x64 compiler uses them extensively). However, there are still some tricks that the compiler has at its disposal to perform such conditional assignments without branch instructions.

This is possible through clever use of the “conditional set (setcc)” family of instructions (e.g. setz), which store either a zero or a one into a register without requiring a branch. For example, here’s an example that I came across recently:

xor     ecx, ecx
cmp     al, 30h
mov     eax, [ebp+PacketLeader]
setnz   cl
dec     ecx
and     ecx, 0C6C6C6C7h
add     ecx, 69696969h
mov     [eax], ecx

Broken up into the individual relevant steps, this code is something along the lines of the following in pseudo-code:

if (eax == 0x30)
  ecx = 0;
else
  ecx = 1;

ecx--; // after, ecx is either 0 or 0xFFFFFFFF (-1)
ecx &= 0x30303030 - 0x69696969; // 0xC6C6C6C7
ecx += 0x69696969;

The key trick here is the use of a setcc instruction, followed by a dec instruction and an and instruction. If one takes a minute to look at the code, the meaning of these three instructions in sequence becomes apparent. Specifically, a setcc followed by a dec sets a register to either 0 or 0xFFFFFFFF (-1) based on a particular condition flag. Following which the register is ANDed with a constant, which depending on whether the register is 0 or -1 will result in the register being set to the constant or being left at zero (since anything AND zero is zero, while ANDing any particular value with 0xFFFFFFFF yields the input value). After this sequence, a second constant is summed with the current value of the register, yielding the desired result of the operation.

(The initial constant is chosen such that adding the second constant to it results in one of the values of the conditional assignment, where the second constant is the other possible value in the conditional assignment.)

Cleaned up a bit, this code might look more like so:

*PacketLeader = (eax == 0x30 ? 0x30303030 : 0x69696969);

This sort of trick is also often used where something is conditionally set to either zero or some other value, in which case the “add” trick can be omitted and the non-zero conditonal assignment value is used in the AND step.

A similar construct with the sbb instruction and the carry flag can also be constructed (as opposed to setcc, if sbb is more convenient for the particular case at hand). For example, the sbb approach tends to be preferred by the compiler when setting a value to zero or -1 as a further optimization on this theme as it avoids the need to decrement, assuming that the input value was already zero initially and the condition is specified via the carry flag.

This entry was posted on Thursday, October 18th, 2007 at 10:14 am and is filed under Reverse Engineering. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.