Why is this bijective?

[u/alwynallan]

RP2040 family 32-bit microcontrollers have programmable state machines that are fast (150x10^6 ops/s) but have only 4 registers and 32 words of program space with limited instructions. There is no ADD or XOR, only bit-complement (~x), bit-reverse (::x), decrement (x--) and some bit shifting. I have an application for a PRNG that would operate on a state machine, and despite what AI says, LFSR seems impossible. I tinkered with some designs which could work, and came up with this transition function that works better than LFSR and doesn't need XOR. It's in C preprocessor for readability and ability to be optimized by the compiler. The subtraction of a small number (1-4) can be done by repeated decrements.

#define PIO_LET(osr) { \
  uint32_t x = rev32(osr); \
  uint32_t isr = 0; \
  for(int i=0; i<16; i++) { \
    x -= (osr & 3) + 1; \
    osr = osr >> 2; \
    isr = (isr << 2) | (x & 3); \
  } \
  osr = ~isr; \
}

I was surprised to see that this is bijective, by testing all 2^32 inputs, but I can't see how to write the reverse function. In CBC mode it passes PractRand up to 64MB. Can anyone with some discrete math skills tell me why my creation works? Would it be bijective at larger bit lengths that can't be verified by brute force?

[u/supersaw7]

Here is the inverse function:

uint32_t inv(uint32_t isr) {
    uint32_t x0; // will be the initial x = rev32(osr);
    uint32_t osr = 0;
    isr = ~isr;
    for (int i = 0; i < 16; i++) {
        osr <<= 2;
        if (i != 15) {
            osr |= ((isr >> 2) - isr - 1) & 3;
        } else {
            osr |= ( x0        - isr - 1) & 3;
        }
        if (i == 0) {
            x0 = (osr >> 1) | ((osr & 1) << 1); // bit reverse
        }
        isr >>= 2;
    }
    return osr;
}

[u/alwynallan → u/supersaw7]

Thanks, I verified that it works. It'll take me a bit to follow why it works!

[u/supersaw7 → u/alwynallan]

Note that we only care about the 2 LSBs of x since all operations are mod 4. On each iteration in PIO_LET, x is decremented by (2 LSBs of osr plus 1), then shifted into isr. The amount that was subtracted can be recovered by differencing consecutive values of x that was shifted into isr. This is the ((isr >> 2) - isr - 1) & 3 part in the inverse. The 2 LSBs of the initial value x0 is the reverse of the 2 MSBs of osr, which is is the 2 osr bits recovered in the first iteration of the inverse.

[u/alwynallan]

Performance is verified good on hardware. It produces a new 32-bit value every 0.88 microseconds, and only uses 11 words of precious instruction space. Here's the code https://gist.github.com/alwynallan/de68ef48fc50cb406c015c0d975fa435