www.nosreme.org

Cunning division

Posted on December 07, 2008 at 22:13:09 by chris

I recently needed to go from a pointer to an element in an array of one type, to the corresponding element in an array of a different size. The function I wrote was something like:

struct A *b_to_a(struct B *b)
{
    int offset = b - array_b;
    return array_a + offset;
}

which looks simple, but does have a hidden division (by the size of struct B, in this case something like 240, ie not a power of 2, to get the offset as an array index). Division isn't ideal on the particular platform I'm using; there's a fast integer multiply but slow (function call) division. However the compiler was more cunning than I was, and produced something like:

uint32_t temp = (uint32_t)b - (uint32_t)array_b;
temp = temp * 0xeeeeeeef;
offset = temp >> 3;

It turns out that multiplying by 0xeeeeeeefhas the effect of dividing by 15. Ok, I thought - think of it as -0x11111111, so multiplying it by 15 (0xf) gives -0xffffffff, or just 1, and being linear that means that multiplying by 15*N will give N. So it's a neat trick that works for factors of 0xffffffff.

After further thought it turns out the trick works for any odd divisor, ie which is coprime with 2³² - and the rest can be handled with an extra shift. The magic number is just the multiplicative inverse, mod 2³², of the divisor. The only catch is that if the input isn't guaranteed to be an exact multiple of the divisor, the result is gibberish.

I thought it was cute.