scrambler.cpp

// based on https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
static uint32_t permute(uint32_t x, uint32_t prime) {
    if (x >= prime)
        return x;
    uint32_t residue = ((uint64_t) x * x) % prime;
    return (x <= prime / 2) ? residue : prime - residue;
}

static uint64_t scramble(uint64_t x) {
    // find msb
    int bits = -1;
    for (int i = 64; i-- > 0;) {
        if (x & (1ull << i)) {
            bits = i;
            break;
        }
    }
    if (bits < 1) return x;
    // scramble up to first 32 bits
    bits = std::min(32,bits);
    uint64_t mask = (1ull << bits) - 1ull;
    uint64_t top = x & ~mask;
    x = x & mask;
    if (bits >= 8) {
        uint32_t delta = 0;
        // from https://primes.utm.edu/lists/2small/0bit.html
        switch(bits) {
        case  8: delta = 5; break; case  9: delta = 3; break; case 10: delta = 3; break; case 11: delta = 9; break;
        case 12: delta = 3; break; case 13: delta = 1; break; case 14: delta = 3; break; case 15: delta = 19; break;
        case 16: delta = 15; break; case 17: delta = 1; break; case 18: delta = 5; break; case 19: delta = 1; break;
        case 20: delta = 3; break; case 21: delta = 9; break; case 22: delta = 3; break; case 23: delta = 15; break;
        case 24: delta = 3; break; case 25: delta = 39; break; case 26: delta = 5; break; case 27: delta = 39; break;
        case 28: delta = 57; break; case 29: delta = 3; break; case 30: delta = 35; break; case 31: delta = 1; break;
        case 32: delta = 5; break; default: assert(false); break;
        }
        uint32_t prime = (1u << bits) - delta;
        uint32_t m = 0x5bf03635 & mask;
        x = permute(x, prime);
        x = permute(x ^ m, prime);        
    }
    return x | top;
}