Why does this code break when -O2 or higher is enabled?

Question

I tried to fit an implementation of NSA's SPECK in a 8-bit PIC microcontroller. The free version of their compiler (based on CLANG) won't enable optimizations so I ran out of memory. I tried the "trial" version that enables -O2, -O3 and -Os (optimize for size). With -Os It managed to fit my code in the 2K program memory space.

Here's the code:

#include <stdint.h>
#include <string.h>

#define ROR(x, r) ((x >> r) | (x << (32 - r)))
#define ROL(x, r) ((x << r) | (x >> (32 - r)))
#define R(x, y, k) (x = ROR(x, 8), x += y, x ^= k, y = ROL(y, 3), y ^= x)
#define ROUNDS 27

void encrypt_block(uint32_t ct[2],
        uint32_t const pt[2],
        uint32_t const K[4]) {
    uint32_t x = pt[0], y = pt[1];
    uint32_t a = K[0], b = K[1], c = K[2], d = K[3];

    R(y, x, a);
    for (int i = 0; i < ROUNDS - 3; i += 3) {
        R(b, a, i);
        R(y, x, a);
        R(c, a, i + 1);
        R(y, x, a);
        R(d, a, i + 2);
        R(y, x, a);
    }
    R(b, a, ROUNDS - 3);
    R(y, x, a);
    R(c, a, ROUNDS - 2);
    R(y, x, a);

    ct[0] = x;
    ct[1] = y;
}

Unfortunately, when debugging it line by line, comparing it to the test vectors in the implementation guide, from page 32, "15 SPECK64/128 Test Vectors", the results difer from the expected results.

Here's a way to call this function:

uint32_t out[2];
uint32_t in[] = { 0x7475432d, 0x3b726574 };
uint32_t key[] = { 0x3020100, 0xb0a0908, 0x13121110, 0x1b1a1918 };

encrypt_block(out, in, key);

assert(out[0] == 0x454e028b);
assert(out[1] == 0x8c6fa548);

The expected value for "out", according to the guide, should be 0x454e028b, 0x8c6fa548. The result I'm getting with -O2 is 0x8FA3FED7 0x53D8CEA8. With -O1, I get 0x454e028b, 0x8c6fa548, which is the correct result.

Step Debugging

The implentation guide includes all the intermediate key schedule other values, so I stepped through the code line by line, comparing the results to the guide.

The expected results for "x" are: 03020100, 131d0309, bbd80d53, 0d334df3. I start step debugging, but when reaching the 4th result, 0d334df3, the debugger window shows 0d334df0 instead. By the next round, the expected 7fa43565 value is 7FA43578 and only gets worse with every iteration.

This only happens when -O2 or greater is enabled. With no optimizations, or with -O1, the code works as expected.

Answer 1

It was a bug in the compiler.

I posted the question in the manufacturer's forum. Other people have indeed reproduced the issue, which happens when compiling for certain parts. Other parts are unaffected.

As a workaround, I changed the macros into real functions, and split the operation in two lines:

uint32_t ROL(uint32_t x, uint8_t r) {
    uint32_t intermedio;
    intermedio = x << r;
    intermedio |= x >> (32 - r);
    return intermedio;
}

This gives the correct result.

Answer 2

Posting compilable test code as a reference.

#include <stdint.h>
#include <string.h>
//#include "speck.h"

#define ROR(x, r) ((x >> r) | (x << (32 - r)))
#define ROL(x, r) ((x << r) | (x >> (32 - r)))
#define R(x, y, k) (x = ROR(x, 8), x += y, x ^= k, y = ROL(y, 3), y ^= x)
#define ROUNDS 27

void encrypt_block(uint32_t ct[2], uint32_t const pt[2], uint32_t const K[4]) {
  uint32_t x = pt[0], y = pt[1];
  uint32_t a = K[0], b = K[1], c = K[2], d = K[3];

  R(y, x, a);
  // for (int i = 0; i < ROUNDS - 3; i += 3) {
  for (uint32_t i = 0; i < ROUNDS - 3; i += 3) {
    R(b, a, i);
    R(y, x, a);
    R(c, a, i + 1);
    R(y, x, a);
    R(d, a, i + 2);
    R(y, x, a);
  }
  R(b, a, ROUNDS - 3);
  R(y, x, a);
  R(c, a, ROUNDS - 2);
  R(y, x, a);

  ct[0] = x;
  ct[1] = y;
}

int main(void) {
  uint32_t out[2];
  uint32_t in[] = {0x7475432d, 0x3b726574};
  uint32_t key[] = {0x03020100, 0x0b0a0908, 0x13121110, 0x1b1a1918};
  encrypt_block(out, in, key);

  printf("%8lx %8lx\n", (unsigned long) out[0], 0x454e028bLU);
  printf("%8lx %8lx\n", (unsigned long) out[1], 0x8c6fa548LU);
}

Output

454e028b 454e028b
8c6fa548 8c6fa548

Unexpected output

0x8FA3FED7
0x53D8CEA8

Answer 3

I don't see any indication of undefined behavior in your code, unless it's in some aspect of the setup/call point that you haven't shown. As such, it should be impossible for behavior to differ according to optimization level. Normally I would not be quick to blame compiler bugs for something like this, but forks of FOSS compilers for embedded stuff, and especially forks that redefine int to 16-bit in a compiler that wasn't designed to target 16-bit int, and especially proprietary forks where their code is so bad that they don't even want to let you see it, a compiler bug is very very likely.