What Every C Programmer Should Know About Undefined Behavior #1/3

Hint: the problem arises from the different order of operations rearranging the predefined sequence of "random" numbers.

That reminds me, the random number generator was pretty awesome in its own right. It's the kind of random number generator that both XKCD and Dilbert can weigh in on, even without meaning to!

unsigned char rndtable[256] = {
    0,   8, 109, 220, 222, 241, 149, 107,  75, 248, 254, 140,  16,  66 ,
    74,  21, 211,  47,  80, 242, 154,  27, 205, 128, 161,  89,  77,  36 ,
    95, 110,  85,  48, 212, 140, 211, 249,  22,  79, 200,  50,  28, 188 ,
    52, 140, 202, 120,  68, 145,  62,  70, 184, 190,  91, 197, 152, 224 ,
    149, 104,  25, 178, 252, 182, 202, 182, 141, 197,   4,  81, 181, 242 ,
    145,  42,  39, 227, 156, 198, 225, 193, 219,  93, 122, 175, 249,   0 ,
    175, 143,  70, 239,  46, 246, 163,  53, 163, 109, 168, 135,   2, 235 ,
    25,  92,  20, 145, 138,  77,  69, 166,  78, 176, 173, 212, 166, 113 ,
    94, 161,  41,  50, 239,  49, 111, 164,  70,  60,   2,  37, 171,  75 ,
    136, 156,  11,  56,  42, 146, 138, 229,  73, 146,  77,  61,  98, 196 ,
    135, 106,  63, 197, 195,  86,  96, 203, 113, 101, 170, 247, 181, 113 ,
    80, 250, 108,   7, 255, 237, 129, 226,  79, 107, 112, 166, 103, 241 ,
    24, 223, 239, 120, 198,  58,  60,  82, 128,   3, 184,  66, 143, 224 ,
    145, 224,  81, 206, 163,  45,  63,  90, 168, 114,  59,  33, 159,  95 ,
    28, 139, 123,  98, 125, 196,  15,  70, 194, 253,  54,  14, 109, 226 ,
    71,  17, 161,  93, 186,  87, 244, 138,  20,  52, 123, 251,  26,  36 ,
    17,  46,  52, 231, 232,  76,  31, 221,  84,  37, 216, 165, 212, 106 ,
    197, 242,  98,  43,  39, 175, 254, 145, 190,  84, 118, 222, 187, 136 ,
    120, 163, 236, 249
};

int rndindex = 0;
int prndindex = 0;

// Which one is deterministic?
int P_Random (void)
{
    prndindex = (prndindex+1)&0xff;
    return rndtable[prndindex];
}

int M_Random (void)
{
    rndindex = (rndindex+1)&0xff;
    return rndtable[rndindex];
}

void M_ClearRandom (void)
{
    rndindex = prndindex = 0;
}

Indeed. Java's stack-based interpreter model might not benefit from such optimizations, but a real register-based machines can benefit from evaluating expressions inside-out, for example, since it minimizes the number of temporary values you need to keep around.

In the worst case, left-to-right evaluation requires generating a temporary for every subexpression. Consider this pathological case:

 foo = (a() - (b() - (c() - (d() - (e() - f())))));

You need to compute a(), b(), c(), d(), e() and f() before you can do the first subtract in a language that guarantees left-to-right evaluation. In C, the compiler is free to evaluate e() or f() ahead of the rest.

Before someone points out the commutativity and associativity of addition and subtraction, let me remind you that even C can't re-order the order of floating point operations. So if 'a' through 'f' return floats, you must do e() - f() first.

So, the C rules give the compiler some needed (and obviously useful in this contrived example) flexibility in this case.