CVE-2011-3441
CVE-2011-3246
A series of regex-writing challenges.
A series of XSS challenges: here's some unsafe code; exploit it! Shortest code wins.

My CSS-fu is weak; please use a recent browser.

Some rights reserved.

Random, semi-related image by ~fb~.

Bit Tricks, Part I: Exact Division

GCC has some clever tricks up its sleeve for compiling the humble division operator.

This is part 1 of a series of posts on bit-twiddling tricks and micro-optimizations. This one looks at ways to try to optimize the following function:

"Constant"
int exactDiv3(int x) { // given that x is a multiple of 3 return x/3; }

Recap: Two's complement

Integer arithmetic (in binary) is usually done in two's complement(W), meaning that negative numbers are stored as an infinite string of ones:

...00000000010 =  2
...00000000001 =  1
...00000000000 =  0
...11111111111 = -1
...11111111110 = -2
...11111111101 = -3

This works rather nicely; if you have -1 in a register and you add one, the carry goes all the way to the left and eventually "falls off the end", and you end up with zero (as you should).

To flip the sign of a number, you invert all the bits, and add one:

...00000001100 = 12
...11111110011 = ~12 = -11
...11111110100 = ~12 + 1 = -12

2-adic numbers

Now consider this infinitely long string of bits, where only half the bits are 1s:

...010101010101 = ?
If we multiply it by three, we get
   ...010101010101 * 11 =

...010101010101 + ...10101010101
= ...111111111111 = -1 ?

... so apparently the mystery number ...010101 behaves like -⅓. If it really is -⅓, we should be able to do this:

...010101010101 = -⅓
...101010101010 = ~(-⅓)
...101010101011 = ~(-⅓) + 1 = -(-⅓) = ⅓

Let's try multiplying 9 by our "⅓":


...101010101011 * 1001 =
...101010101011 + ...010101011000
= ...000000000011 = 3

It actually works!

int exactDiv3(int x) {
  return x * 0xaaaaaaab;
}

This works in decimal as well: The next time you need to divide a number by 13, just multiply by ...23076923076923076923077 instead. It's that simple!

91 * 23076923076923076923077 = 2100000000000000000000007
... and so, ignoring the high-order digits:
91 * ...076923076923077 = ...000000000000007 = 7

Wikipedia has a nice article about 2-adic numbers1. If you don't like infinite bit strings, you can pretend we're just using inverses in the group formed by the odd integers under multiplication mod 2W. In fact, Java even has a library method for finding such inverses:

BigInteger a = BigInteger.valueOf(3);
BigInteger m = BigInteger.ONE.shiftLeft(64);
out.println(a.modInverse(m).toString(16));
// prints "aaaaaaaaaaaaaaab"

In the real world

Since this trick only works when there is no remainder, GCC will (as far as I know) only use it one situation.

When subtracting two pointers to the same array, it needs to divide the raw pointer difference by the element size. This difference will always be an exact multiple of the element size (this is guaranteed by one of the "nasal demon(W) clauses" in the C standard).

You can force it to accept arbitrary integers by doing something like this (no, I'm not suggesting you use this anywhere):

"Exact"
template<int i> class dummy { char x[i]; }; template<int i> int divideby(int x) { return ((dummy<i>*)x) - (dummy<i>*)0; } int main() { printf("%d %d\n", divideby<5>(210), divideby<5>(7)); } // output: 42 -1717986917

There's one additional snag, though: If the divisor is an even number, there is no direct multiplicative inverse. However, since we're still assuming there is no remainder, it is safe the use a bit shift to handle the 2n factor2. The following function...

	int test(int n) {
	  return divide<20>(n);
	}

... can be compiled as (to see this, just run g++ -S foo.cpp and inspect the resulting .S file)

	;; essentially   return (x>>2) * -858993459;

        sarl    $2, %eax
        imull   $-858993459, %eax, %eax
        ret

Microbenchmark

This graph shows the runtime for each of the three division implementations: division by a variable using IDIV, division by a constant as optimized by GCC into a multiplication followed by fixups, and the exact division method.

Note how powers of 2 are most efficient (requiring a bitshift only), with odd numbers (multiplication but no shift) as a close second.

Remainder testing

Another common operation is checking if the remainder is zero:

if (x % 7 == 0) { 
  ...

This can be simplified to...3

if (x * inverse(7) <= floor(2**32/7)) {
  ...

... that is, checking that the result of the inverse multiplication can be multiplied by 7 without overflowing again. As far as I can tell, no compilers actually use this trick.

Comments

If your input has limited range, it's possible to compute some constant divisions using a small constant multiply (implemented by the compiler as shifts & adds) and a constant division by a power of 2. I.e. 5*n/16. This is sometimes faster than an exact multiply solution, but this probably depends on the architecture and function computed.
— Eric 2010-01-09

Footnotes:

  1. For all prime values of 2
  2. It's unsafe in general, since negative numbers will round the wrong way. (-5/2) is -2, but (-5>>1) is -3.
  3. Assuming x is unsigned; signed integers may require more instructions