Modulus Operator vs Zero (re: arc4random_uniform source)

Question

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

Patriapatriarch

Related: #8027194 – Plenish

Answer 1

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

Cythera

Answer 2

First it's worth mentioning that the variables are uint32_t, thus unsigned. Then lets look closely: -upper_bound % upper_bound = (-upper_bound) % upper_bound;. It means that -upper_bound is actually 2's complement of upper_bound. Assume that upper_bound=10, then -upper_bound is 0xFFFFFFF6=246. Then -upper_bound % upper_bound = 246%10 = 6. And you can test it.

Purlin