One way to provide entropy to the LUT is to connect the entropy source to the block's input. The quality does not need to be great but the effect is slow.

Now if you have a block of external data (a network packet, a keystroke, the usual deal), you may want to hit the LUT directly. It should be faster, right ?

512 bytes is also 128× 32-bit words but you can't write them like that in the LUT. You have to respect the balance between 1s and 0s. Thus given an entropy word, you must XOR two locations : if you flip two bits, the overall bitcount is preserved.

Well, no, it doesn't work like that.

XORing is the easy bit of course. But keeping the bit balance is something else : one could use popcnt (__builtin_popcountl(x) if you want it to work with GCC) twice (once before and once after the XOR) but this would be slow, so let's turn the difficulty into an opportunity.

Let's have our entropy word E that XORs a value L in the LUT. This gives the new word N=E^L. Fine.

• Some bits from E will be cleared : they are given by R=E&L.

• Some bits from E will be set : they are given by S=E&(~L) = E&N.

The trick is to not bother with how many bits do this or that, keeping a count would be cumbersome, and another beautiful thing is : we don't care how many words it will take to scan to find a location where a corresponding bit can be toggled.

So we will be scanning the word located after the place we just XORed, and try to see if each one fits a mask that even partially matches what has just been done.

For each new word N, we try the masks S and R:

• S shows which bits were set so now they indicate which ones must be reset : S2 = S & N.
• R indicates cleared bits so now they set it : R2 = R & ~N

Now get X = R2 | S2 and you can get N2 = X^N which can be rewritten back to the LUT.

And don't forget to update the masks:

R &= ~R2

S &= ~S2

If R | S is not 0 then move on to the next word.

Of course this assumes that the LUT is already "properly initialised" with enough entropy. The word or the mask could be rotated once in a while ( to increase the chances of a match).

This also promotes the use of very long words, like 64 bits, to amortize the costs.

Oh and checking the actual number of bits of the LUT is a safety measure that must not be forgotten.

--------------------------------------------------------------

Actual code : it works well !

when feeding the "entropy" 0x123456789ABCDEF 256 times, I get this result:

⢾⢓⡿⣣⣿⡣⣪⠗⠚⠐⠅⠃⠍⠀⢀⠃⠚⢐⠭⠣⠿⠀⢈⠇⡿⡿⣶⣿⣿⣿⣿⣿
⡥⡯⢺⣔⣉⢯⡷⡸⡯⡬⢾⢴⣊⣘⣿⠽⢈⢙⡛⠯⣟⣶⡦⣖⢹⡨⡃⣑⣸⡈⡁⣑
⢻⡨⠉⣭⣻⣐⣇⣱⡖⢟⢦⠦⠤⢧⡘⣏⡝⣿⣏⣓⠜⠯⡑⠆⢪⢈⠲⠬⢀⣐⣗⡩
⡜⡧⣕⣓⣾⠯⣭⢞⢨⠝⡀⠂⢈⠄⡡⣕⣅⠔⡂⠨⠂⣺⣌⠤⠺⣟⢥⣷⡿⢅⠑⣙
⣄⡻⢾⢑⡉⠫⠂⡊⠑⢡⠒⠌⢵⡋⠻⢗⣬⣞⣕⣻⢘⠱⡆⠮⢯⠺⢁⣃⠉⠬⡈⢐
⡩⡁⡈⠐⠶⠓⠰⡛⠵⠆⢄⢁⢙⢮⠃⠋⣈⠻⡂⡒⢯⠩⡺⣖⠹⡀⠰⢀⠦⠆⠉⠈
⢅⣏⢵⢛⢘⠿⡀⠘⡠⠸⡼⡐⣇⠐⡆⠗⣥⢕⠁⢂⠂⠂⠀⠜⡀⠦⡀⠁⠉⠍⠀⠂
⠙⡠⡌⠣⠉⠭⠉⠂⣼⢟⢡⣐⢔⠂⡰⡉⣜⡸⡦⠐⢀⠠⡱⣋⢡⣜⢄⣂⢞⠆⡊⢀
⡬⣫⡄⢑⢡⠨⡈⠊⣅⣿⠔⡂⢌⠙⡬⠒⣀⣷⠄⡂⠮⠉⠐⣃⣍⣾⠒⡊⠝⠘⡞⠂
⠰⠀⣙⢙⡒⡦⢁⡈⢕⠂⠢⢪⠸⠄⡍⣘⠘⡩⡝⠕⠆⢠⠱⡈⣧⢞⢀⣮⡘⠏⣀⠢
⠠⡭⡅⠕⣆⢢⠠⢈⡗⣷⣟⣻⣮⠛⣍⡕⢸⠁⠢⠊⠡⡤⢋⢾⢱⠀⠒⢨⣶⠳⢕⣗
⡟⣿⣱⣿⣚⣜⡷⢸⢀⠀⠤⠈⠀⡢⣈⠢⡏⣿⣵⣿⢺⢜⣷⠝⣹⡷⣷⡿⡖⣻⣮⣸
⢕⣕⢱⠖⠕⡧⠈⠊⡸⠢⡚⣭⣪⣘⢲⣵⣿⣷⠧⣮⡻⣡⢯⣏⠀⠩⣐⠙⢄⢒⣄⠢
⣂⠉⠹⠼⡂⣐⢆⢠⠧⣶⣚⣫⡏⣽⢆⠪⡍⢯⡤⢏⣼⣇⡰⣗⠳⢨⡄⣾⠔⣣⣨⠸
⣞⡖⠻⡭⡫⣜⢞⣣⠙⠔⠾⢎⣠⣀⢻⣉⠑⠝⠲⣞⣻⡐⢿⣽⣆⡲⣳⠯⢦⣽⢟⣧
⡗⣫⣑⠏⣎⢿⢯⡖⣸⣯⡺⣬⣷⣛⢕⡩⣲⡳⡚⣬⡦⣋⣿⣽⠟⠈⢿⠾⡪⢴⣿⣷

And the starting point was the "worst case" so in practice fewer than 256 words would be necessary. I played with a few other initial bit patterns and it seems to work too.

Anyway, at least input some LFSR, congruential thing, or varying numbers, because the constant input creates extra clusters & patterns that sometimes can't be broken, so in the very worst case, the function returns -1 (lacking any fallback method).

code here : AddEntropy.tgz