一套保證唯一的整數組合的LUT

Question

說我有16個值8個表：

uint32_t lut[8][16]; 

我想，以填補這些表值，使得合併（添加，EOR，等等）從每個進入這八個表將產生一個唯一的32位值 - 與任何其他條目組合的結果不同。

也就是說，隨機變量i，j，k，l，m，n，o和p，我想從lut[0][i] + lut[1][j] + lut[2][k] + lut[3][l] + lut[4][m] + lut[5][n] + lut[6][o] + lut[7][p]所有這些變量可以有不同的價值觀的獨特成果。雖然組合操作不一定是加號。

總共有16**8（40億）個輸入組合，並且每個輸入的結果必須是不同的。

此外 - 這是很難的部分 - 我希望這些條目出現隨機。

明顯的答案是：

uint32_t lut[8][16] = { 
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, 
    { 0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60 /* ... */ }, 
    { 0x000, 0x100, 0x2000 /* ... */ }, 
    /* ... */ 
}; 

而且我們可以證明它與：

for (uint64_t x = 0; x < 0x100000000; x++) { 
    uint32_t y = 0; 
    for (int i = 0; i < 8; i++) { 
    y += lut[i][(x >> (i * 4)) & 15]; 
    } 
    assert(x == y); 
} 

但是，這不是隨機的一切！

我可以這樣做：

for (int i = 0; i < 8; i++) { 
    shuffle(lut[i], 16); 
} 

這有助於一點，但不多。

我最終做的是上面的例子中的一堆轉換。任何1：1 線性我可以對組合值執行變換以使其「更隨機」，可以在表格元素上提前執行，如果我得到的結果與之後完成的結果相同那麼我已經證明，每個可能的組合仍然會產生一個唯一的值（因爲它在變換之前）。但是，這種方法有一些侷限性。所以我想知道;是否有另一種方法來使這些表與給定的約束隨機化？

Answer 1

這是我所做的。

任何1：1類似哈希的轉換，我可以對組合結果做一些預處理，只要這些轉換是線性的。

所以，如果我能做到這一點：

uint32_t y = 0; 
for (int i = 0; i < 8; i++) { 
    y += lut[i][(x >> (i * 4)) & 15]; 
} 
y = transform(y); 

然後，只要transform()是線性的，我能做到這一點，而不是：

for (int i = 0; i < 8; i++) { 
    for (int j = 0; j < 16; j++) { 
    lut[i][j] = transform([i][j]); 
    } 
} 

而且我可以在功能上非常激進因爲我只需要做一次來設置表格。

作爲初始操作，我可以重新排序位，因爲沒有任何位重疊意味着沒有攜帶行爲擔心：

uint32_t bitpermute(uint32_t x) { 
    int s = 1; 
    uint32_t y = 0; 
    for (int i = 0; i < 32; i++) { 
    if ((x & 1) != 0) { 
     y |= 1 << (a & 31); 
    } 
    a = a * 1103515245 + 12345; 
    x >>= 1; 
    } 
    return y; 
} 

uint32_t transform(uint32_t x) { 
    return bitpermute(x); 
} 

我可以被奇數乘以（任意奇數共與uint32_t隱式模-prime，所以它總是具有1：1映射）：

uint32_t transform(uint32_t x) { 
    return bitpermute(x) * 0x39597a05; 
} 

這裏的問題是，低位比特不能以高序位的影響，因此改變到導致高位變化的輸入（在之後高）不會對低位產生任何影響。我們不能右移，因爲這不是線性的。在組合操作之前右移不同的進位傳播在其之後的右移。

那些攜帶毀了一切！

爲了得到方程中的進位，我們可以改變域。讓我們加一個加模2（異或）：

uint32_t y = 0; 
for (int i = 0; i < 8; i++) { 
    y ^= lut[i][(x >> (i * 4)) & 15]; 
} 

現在我們的乘法已經將與一些類似替代：

uint32_t bitmix(uint32_t x, uint32_t p, int s) { 
    uint32_t y = 0; 
    while (p > 0) { 
    if ((p & 1) != 0) { 
     y ^= x; 
    } 
    x = (s > 0) ? (x >> -s) : (x << s); 
    p >>= 1; 
    } 
    return y; 
} 

uint32_t transform(uint32_t x) { 
    x = bitpermute(x); 
    x = bitmixup(x, 0x39597a05, 1); 
    x = bitmixdn(x, 0x1b0bb8ad, -1); 
    x = bitmixup(x, 0x09bb8825, 1); 
    return x; 
} 

在那裏，我固定它。

不幸的是，這犧牲了進位的好處，即相鄰比特的組合可能會影響其他比特......但是如果它們都遵循相同的模式，我可以從任何比特混合到任何其他比特。

不是模2運算（代替+使用^），我可以把它MOD-4使用這個成語做：r = x + y - (x & y & 0xaaaaaaaa)，然後我不得不把所有班次限制爲是偶數。儘管如此，我還沒有調查過，因爲我不確定它會向有用的方向發展。