A common operation in many C programs is a division by a constant quantity. This sort of operation occurs all over the place; in explicit mathematical calculations, and in other, more innocuous situations such as where the programmer does something like take a size in bytes and convert it into a count of structures.<\/p>\n
This fundamental operation (division by a constant) is also one that the compiler will tend to optimize in ways that may seem a bit strange until you know what is going on.<\/p>\n
Consider this simple C program:<\/p>\n
\r\nint\r\n__cdecl\r\nwmain(\r\n\tint ac,\r\n\twchar_t** av)\r\n{\r\n\tunsigned long x = rand();\r\n\r\n\treturn x \/ 1518;\r\n}\r\n<\/pre>\nIn assembly, one would expect to see the following operations emitted by the compiler:<\/p>\n
\n- A call to rand<\/em>, to populate the ‘x’ variable.<\/li>\n
- A div<\/em> instruction to perform the requested division of ‘x’ by 1518.<\/li>\n<\/ol>\n
However, if optimizations are turned on and the compiler is not configured to prioritize small code over performance exclusively, then the result is not what we might expect:<\/p>\n
\r\n; int __cdecl main(int argc,\r\n const char **argv,\r\n const char *envp)\r\n_main proc near\r\ncall ds:__imp__rand\r\nmov ecx, eax\r\nmov eax, 596179C3h\r\nmul ecx\r\nmov eax, ecx\r\nsub eax, edx\r\nshr eax, 1\r\nadd eax, edx\r\nshr eax, 0Ah ; return value in eax\r\nretn\r\n<\/pre>\nThe first time you encounter something like this, you’ll probably be wondering something along the lines of “what was the compiler thinking when it did that, and how does that set of instructions end up dividing out ‘x’ by 1518?”.<\/p>\n
What has happened here is that the compiler has used a trick sometimes known as magic number division<\/em> to improve performance. In x86 (and in most processor architectures, actually), it is typically much more expensive to perform a division than a multiplication (or most any other basic mathematical primative, for that matter). While ordinarily, it is typically not possible to make division any faster than what the ‘div’ instruction gives you performance-wise, under special circumstances it is possible to do a bit better. Specifically, if the compiler knows that one of the operands to the division operation is a constant (specifically, the divisor), then it can engage some clever tricks in order to eliminate the expensive ‘div’ instruction and turn it into a sequence of other instructions that, while initially longer and more complicated on the surface, are actually faster to execute.<\/p>\nIn this instance, the compiler has taken one ‘div’ instruction and converted it into a multiply, subtract, add, and two right shift operations. The basic idea behind how the code the compiler produced actually gives the correct result is that it typically involves a multiplication with a large constant, where the low 32-bits are then discarded and then remaining high 32-bits (recall that the ‘mul’ instruction returns the result in edx:eax, so the high 32-bits of the result are stored in edx) have some transform applied, typically one that includes fast division by a power of 2 via a right shift.<\/p>\n
Sure enough, we can demonstrate that the above code works by manually comparing the result to a known value, and then manually performing each of the individual operations. For example, assume that in the above program, the call to rand returns 10626 (otherwise known as 7 * 1518, for simplicity, although the optimized code above works equally well for non-multiples of 1518).<\/p>\n
Taking the above set of instructions, we perform the following operations:<\/p>\n
\n- Multiply 10626 by the magic constant 0x596179C3. This yields 0x00000E7E00001006.<\/li>\n
- Discard the low 32-bits (eax), saving only the high 32-bits of the multiplication (edx; 0xE7E, or 3710 in decimal).<\/li>\n
- Subtract 3710 from the original input value, 10626, yielding 6916.<\/li>\n
- Divide 6916 by 2^1 (bit shift right by 1), yielding 3458.<\/li>\n
- Add 3710 to 3458, yielding 7168.<\/li>\n
- Divide 7168 by 2^10 (bit shift right by 10), yielding 7, our final answer. (10626 \/ 1518 == 7)<\/li>\n<\/ol>\n
Depending on the values being divided, it is possible that there may only be a right shift after the large multiply. For instance, if we change the above program to divide by 1517 instead of 1518, then we might see the following code generated instead:<\/p>\n
\r\nmov eax, 5666F0A5h\r\nmul ecx\r\nshr edx, 9\r\n<\/pre>\n