Module operator against zero (re: arc4random_uniform source)

Question

Found myself looking at the source arc4random_uniform ( http://bxr.su/o/lib/libc/crypt/arc4random_uniform.c )

My question relates to the following line (comment is their original comment):

/* 2**32 % x == (2**32 - x) % x */ min = -upper_bound % upper_bound; 

Now I'm not a genius in mathematics, but, of course, -N% N will always be zero. So why just write

 min=0 

Answer 1

It is important to note that here we are dealing with unsigned ints ( uint32_t ), so -upper_bound does not do what you think. This is actually 2**32 - upper_bound , due to the modular wrapper, and the purpose of this is explained in the comment above (i.e. 2**32 % upper_bound without overflow).

Example:

 #include <stdio.h> #include <stdint.h> int main() { uint32_t upper_bound = 42; uint32_t min = -upper_bound % upper_bound; printf("%u -> %u\n", upper_bound, min); return 0; } 

gives:

 42 -> 4 

Live code

Answer 2

First, it is worth mentioning that the variables are uint32_t , therefore unsigned. Then let's take a close look: -upper_bound % upper_bound = (-upper_bound) % upper_bound; . This means that -upper_bound is actually 2 additions to upper_bound . Suppose upper_bound=10 , then -upper_bound is 0xFFFFFFF6=246 . Then -upper_bound % upper_bound = 246%10 = 6 . And you can check it out.