Optimising pointer subtraction with 2-adic integers.

blog.sigfpe.com
7 min read
easy
Here is a simple C type and a function definition: struct A { char x[7]; }; int diff(struct A *a, struct A *b) { return a-b; } ...
struct A

{

char x[7];

};

int diff(struct A *a, struct A *b)

{

return a-b;

}

A

movl 4(%esp), %eax

subl 8(%esp), %eax

imull $-1227133513, %eax, %eax

ret

1

2

n

n

n

n

n

n

n

...11111111

...00000001

-----------

...00000000

...11111111

...1111111

...111111

...11111

...

-----------

...00000001

n

n

n+1

n+1

n

n

n

n+1

n

n

1

-5

-185

-239945

-403015701065

-1136951587135200126341705

00000000000000000000000000000000000000000000000000000000000000000000000000000000001

11111111111111111111111111111111111111111111111111111111111111111111111111111111011

11111111111111111111111111111111111111111111111111111111111111111111111111101000111

11111111111111111111111111111111111111111111111111111111111111111000101011010110111

11111111111111111111111111111111111111111111010001000101010011001000110110110110111

11100001111001111011011101100100000010000000011011010110110110110110110110110110111

10110110110110110110110110110111

10100000000000000000000000000000001

00000000000000000000000000000001.

#include

#include

typedef unsigned int uint;

uint inverse(uint x)

{

uint y = 2-x;

y = y*(2-x*y);

y = y*(2-x*y);

y = y*(2-x*y);

y = y*(2-x*y);

return y;

}

int main()

{

uint i;

for (i = 1; i<0xfffffffe; i += 2)

{

assert (i*inverse(i) == 1);

}

}

Here is a simple C type and a function definition:It doesn't seem like there could be much to say about that. Thestructure is 7 bytes long so the subtraction implicitly divides by 7. That's about it. But take a look at the assembly language generated when it's compiled with gcc:Where is the division by 7? Instead we see multiplication by -1227133513. A good first guess is that maybe this strange constant is an approximate fixed point representation of 1/7. But this is a single multiplication with no shifting or bit field selection tricks. So how does this work? And what is -1227133513? Answering that question will lead us on a trip through some suprising and abstract mathematics. Among…
Read full article