Search code examples
cmathcryptographyopenbsdtype-bounds

Modulus Operator vs Zero (re: arc4random_uniform source)

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

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

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

Now, I'm no mathematics genius, but surely -N%N will always equal zero. So why not just write 

min=0
Solution

  • It's important to note that we're dealing with unsigned ints (uint32_t) here, so -upper_bound doesn't do what you think it does. It's actually 2**32 - upper_bound, due to modulo wrap-around, and the purpose of this is explained in the comment above (i.e. obtaining 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