Re: [PATCH RFC] random: Account for entropy loss due to overwrites

["Theodore Ts'o" <tytso@mit.edu>]

On Mon, Oct 15, 2012 at 09:45:23PM -0700, H. Peter Anvin wrote:
> 
> Or we could compute poolwords (and poolbits, and poolbytes) from it,
> since shifts generally are cheap.  I don't strongly care, whatever your
> preference is.

We are already calculating poolbits from poolwords:

#define POOLBITS	poolwords*32
#define POOLBYTES	poolwords*4

So you'd basically be suggesting that we define

#define POOLWORDS	(1 << (poolshift - 5))
#define POOLBYTES	(1 << (poolshift - 3))
#define POOLBITS	(1 << poolshift)

Yeah, that works; we don't use poolwords in that many places, and a
data dependent shift is cheap at least on x86 and arm (so probably all
modern platforms).

There was one aesthetic reason for using POOLWORDS, which was that
first term of the generating polynomial was the same as poolwords,
i.e:

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ 128,	103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ 32,	26,	20,	14,	7,	1 },

If we change it to be:

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ 12,	103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ 10,	26,	20,	14,	7,	1 },

It's a wee bit less obvious where the "12" and "10" is coming form.  I
don't see an easy way to fix this, though, other than perhaps making
sure it's clear in the comments.  Unfortunately we can't count on gcc
doing a built-in optimization for a log2 of a constant as far as I
know.... or can we?

Hmm, this does get optimized correctly at least with gcc 4.7:

#define shiftbits(words) ((int) __builtin_log2((double) (words)) + 5)

... and it looks like include/linux/log2.h already has a definition
for ilog2() which should definitely work for all versions of gcc, so
we could do this instead:

#define shiftbits(w)	(ilog2((w)) + 5)

	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
	{ shiftbits(128), 103,	76,	51,	25,	1 },
	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
	{ shiftbits(32),  26,	20,	14,	7,	1 },

						- Ted