Hello folks!

Consider the expression (x % d) == c where d and c are constants.

For simplicity let us assume that x is unsigned and 0 <= c < d.

Let us further assume that d = a * (1 << b) and a is odd.

Then our expression can be transformed to

rotate_right(x-c, b) * inverse_mul(a) <= (high_value(x) - c) / d .

Example [(x % 250) == 3]:

sub eax,3

ror eax,1

imul eax,eax,0x26e978d5 // multiplicative inverse of 125

cmp eax,17179869 // 0xffffffff / 250

jbe OK

A range check for x can be embedded as well with no additional code.

For signed values a similar transformation is possible.

For more details see my comment on Hacker's Delight (Hackersdelight.org) and/or our paper about hashing (http://programming.sirrida.de/hashsuper.pdf).

The current version of Clang / LLVM (clang -O3 -S) translates it to the following (GCC produces similar code):

movl %edi, %eax

imulq $274877907, %rax, %rax # imm = 0x10624DD3

shrq $36, %rax

imull $250, %eax, %eax

movl %edi, %ecx

subl %eax, %ecx

cmpl $3, %ecx

je OK

Please note that there are 2 multiply operations and one of them produces a double width result (multiply high).

Best regards

Jasper