random.c

powerpc内核mpc8241linux系统下char驱动程序

 * 0 and 4095 only.  This allows a few shortcuts.
 */
#if 0	/* Slow but clear version */
static inline __u32 int_ln_12bits(__u32 word)
{
	__u32 nbits = 0;
	
	while (word >>= 1)
		nbits++;
	return nbits;
}
#else	/* Faster (more clever) version, courtesy Colin Plumb */
static inline __u32 int_ln_12bits(__u32 word)
{
	/* Smear msbit right to make an n-bit mask */
	word |= word >> 8;
	word |= word >> 4;
	word |= word >> 2;
	word |= word >> 1;
	/* Remove one bit to make this a logarithm */
	word >>= 1;
	/* Count the bits set in the word */
	word -= (word >> 1) & 0x555;
	word = (word & 0x333) + ((word >> 2) & 0x333);
	word += (word >> 4);
	word += (word >> 8);
	return word & 15;
}
#endif

	
/*
 * Initialize the random pool with standard stuff.
 *
 * NOTE: This is an OS-dependent function.
 */
static void init_std_data(struct random_bucket *r)
{
	__u32 words[2], *p;
	int i;
	struct timeval 	tv;

	do_gettimeofday(&tv);
	add_entropy_words(r, tv.tv_sec, tv.tv_usec);

	/*
	 *	This doesnt lock system.utsname. Howeve we are generating
	 *	entropy so a race with a name set here is fine.
	 */
	p = (__u32 *)&system_utsname;
	for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
		memcpy(words, p, sizeof(words));
		add_entropy_words(r, words[0], words[1]);
		p += sizeof(words)/sizeof(*words);
	}
	
}

/* Clear the entropy pool and associated counters. */
static void rand_clear_pool(void)
{
	memset(&random_state, 0, sizeof(random_state));
	init_std_data(&random_state);
}

__initfunc(void rand_initialize(void))
{
	int i;

	rand_clear_pool();
	for (i = 0; i < NR_IRQS; i++)
		irq_timer_state[i] = NULL;
	for (i = 0; i < MAX_BLKDEV; i++)
		blkdev_timer_state[i] = NULL;
	memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state));
	memset(&mouse_timer_state, 0, sizeof(struct timer_rand_state));
	memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
#ifdef RANDOM_BENCHMARK
	initialize_benchmark(&timer_benchmark, "timer", 0);
#endif
	extract_timer_state.dont_count_entropy = 1;
	random_read_wait = NULL;
	random_write_wait = NULL;
}

void rand_initialize_irq(int irq)
{
	struct timer_rand_state *state;
	
	if (irq >= NR_IRQS || irq_timer_state[irq])
		return;

	/*
	 * If kmalloc returns null, we just won't use that entropy
	 * source.
	 */
	state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
	if (state) {
		irq_timer_state[irq] = state;
		memset(state, 0, sizeof(struct timer_rand_state));
	}
}

void rand_initialize_blkdev(int major, int mode)
{
	struct timer_rand_state *state;
	
	if (major >= MAX_BLKDEV || blkdev_timer_state[major])
		return;

	/*
	 * If kmalloc returns null, we just won't use that entropy
	 * source.
	 */
	state = kmalloc(sizeof(struct timer_rand_state), mode);
	if (state) {
		blkdev_timer_state[major] = state;
		memset(state, 0, sizeof(struct timer_rand_state));
	}
}

/*
 * This function adds a byte into the entropy "pool".  It does not
 * update the entropy estimate.  The caller must do this if appropriate.
 *
 * This function is tuned for speed above most other considerations.
 *
 * The pool is stirred with a primitive polynomial of the appropriate degree,
 * and then twisted.  We twist by three bits at a time because it's
 * cheap to do so and helps slightly in the expected case where the
 * entropy is concentrated in the low-order bits.
 */
#define MASK(x) ((x) & (POOLWORDS-1))	/* Convenient abreviation */
static inline void fast_add_entropy_words(struct random_bucket *r,
					 __u32 x, __u32 y)
{
	static __u32 const twist_table[8] = {
		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
	unsigned i, j;

	i = MASK(r->add_ptr - 2);	/* i is always even */
	r->add_ptr = i;

#ifdef ROTATE_PARANOIA
	j = r->input_rotate + 14;
	if (i)
		j -= 7;
	r->input_rotate = j & 31;

	x = rotate_left(r->input_rotate, x);
	y = rotate_left(r->input_rotate, y);
#endif

	/*
	 * XOR in the various taps.  Even though logically, we compute
	 * x and then compute y, we read in y then x order because most
	 * caches work slightly better with increasing read addresses.
	 * If a tap is even then we can use the fact that i is even to
	 * avoid a masking operation.  Every polynomial has at least one
	 * even tap, so j is always used.
	 * (Is there a nicer way to arrange this code?)
	 */
#if TAP1 & 1
	y ^= r->pool[MASK(i+TAP1)];	x ^= r->pool[MASK(i+TAP1+1)];
#else
	j = MASK(i+TAP1);	y ^= r->pool[j];	x ^= r->pool[j+1];
#endif
#if TAP2 & 1
	y ^= r->pool[MASK(i+TAP2)];	x ^= r->pool[MASK(i+TAP2+1)];
#else
	j = MASK(i+TAP2);	y ^= r->pool[j];	x ^= r->pool[j+1];
#endif
#if TAP3 & 1
	y ^= r->pool[MASK(i+TAP3)];	x ^= r->pool[MASK(i+TAP3+1)];
#else
	j = MASK(i+TAP3);	y ^= r->pool[j];	x ^= r->pool[j+1];
#endif
#if TAP4 & 1
	y ^= r->pool[MASK(i+TAP4)];	x ^= r->pool[MASK(i+TAP4+1)];
#else
	j = MASK(i+TAP4);	y ^= r->pool[j];	x ^= r->pool[j+1];
#endif
#if TAP5 == 1
	/* We need to pretend to write pool[i+1] before computing y */
	y ^= r->pool[i];
	x ^= r->pool[i+1];
	x ^= r->pool[MASK(i+TAP5+1)];
	y ^= r->pool[i+1] = x = (x >> 3) ^ twist_table[x & 7];
	r->pool[i] = (y >> 3) ^ twist_table[y & 7];
#else
# if TAP5 & 1
	y ^= r->pool[MASK(i+TAP5)];	x ^= r->pool[MASK(i+TAP5+1)];
# else
	j = MASK(i+TAP5);	y ^= r->pool[j];	x ^= r->pool[j+1];
# endif
	y ^= r->pool[i];
	x ^= r->pool[i+1];
	r->pool[i] = (y >> 3) ^ twist_table[y & 7];
	r->pool[i+1] = (x >> 3) ^ twist_table[x & 7];
#endif
}

/*
 * For places where we don't need the inlined version
 */
static void add_entropy_words(struct random_bucket *r, __u32 x, __u32 y)
{
	fast_add_entropy_words(r, x, y);
}

/*
 * This function adds entropy to the entropy "pool" by using timing
 * delays.  It uses the timer_rand_state structure to make an estimate
 * of how many bits of entropy this call has added to the pool.
 *
 * The number "num" is also added to the pool - it should somehow describe
 * the type of event which just happened.  This is currently 0-255 for
 * keyboard scan codes, and 256 upwards for interrupts.
 * On the i386, this is assumed to be at most 16 bits, and the high bits
 * are used for a high-resolution timer.
 *
 */
static void add_timer_randomness(struct random_bucket *r,
				 struct timer_rand_state *state, unsigned num)
{
	__u32		time;
	__s32		delta, delta2, delta3;

#ifdef RANDOM_BENCHMARK
	begin_benchmark(&timer_benchmark);
#endif
#if defined (__i386__)
	if (boot_cpu_data.x86_capability & X86_FEATURE_TSC) {
		__u32 high;
		__asm__(".byte 0x0f,0x31"
			:"=a" (time), "=d" (high));
		num ^= high;
	} else {
		time = jiffies;
	}
#else
	time = jiffies;
#endif

	fast_add_entropy_words(r, (__u32)num, time);
	
	/*
	 * Calculate number of bits of randomness we probably added.
	 * We take into account the first, second and third-order deltas
	 * in order to make our estimate.
	 */
	if ((r->entropy_count < POOLBITS) && !state->dont_count_entropy) {
		delta = time - state->last_time;
		state->last_time = time;

		delta2 = delta - state->last_delta;
		state->last_delta = delta;

		delta3 = delta2 - state->last_delta2;
		state->last_delta2 = delta2;

		if (delta < 0)
			delta = -delta;
		if (delta2 < 0)
			delta2 = -delta2;
		if (delta3 < 0)
			delta3 = -delta3;
		if (delta > delta2)
			delta = delta2;
		if (delta > delta3)
			delta = delta3;

		/*
		 * delta is now minimum absolute delta.
		 * Round down by 1 bit on general principles,
		 * and limit entropy entimate to 12 bits.
		 */
		delta >>= 1;
		delta &= (1 << 12) - 1;

		r->entropy_count += int_ln_12bits(delta);

		/* Prevent overflow */
		if (r->entropy_count > POOLBITS)
			r->entropy_count = POOLBITS;

		/* Wake up waiting processes, if we have enough entropy. */
		if (r->entropy_count >= WAIT_INPUT_BITS)
			wake_up_interruptible(&random_read_wait);
	}
		
#ifdef RANDOM_BENCHMARK
	end_benchmark(&timer_benchmark);
#endif
}

void add_keyboard_randomness(unsigned char scancode)
{
	add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
}

void add_mouse_randomness(__u32 mouse_data)
{
	add_timer_randomness(&random_state, &mouse_timer_state, mouse_data);
}

void add_interrupt_randomness(int irq)
{
	if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
		return;

	add_timer_randomness(&random_state, irq_timer_state[irq], 0x100+irq);
}

void add_blkdev_randomness(int major)
{
	if (major >= MAX_BLKDEV)
		return;

	if (blkdev_timer_state[major] == 0) {
		rand_initialize_blkdev(major, GFP_ATOMIC);
		if (blkdev_timer_state[major] == 0)
			return;
	}
		
	add_timer_randomness(&random_state, blkdev_timer_state[major],
			     0x200+major);
}

/*
 * This chunk of code defines a function
 * void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
 * 		__u32 const data[16])
 * 
 * The function hashes the input data to produce a digest in the first
 * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE
 * more words for internal purposes.  (This buffer is exported so the
 * caller can wipe it once rather than this code doing it each call,
 * and tacking it onto the end of the digest[] array is the quick and
 * dirty way of doing it.)
 *
 * It so happens that MD5 and SHA share most of the initial vector
 * used to initialize the digest[] array before the first call:
 * 1) 0x67452301
 * 2) 0xefcdab89
 * 3) 0x98badcfe
 * 4) 0x10325476
 * 5) 0xc3d2e1f0 (SHA only)
 *
 * For /dev/random purposes, the length of the data being hashed is
 * fixed in length (at POOLWORDS words), so appending a bit count in
 * the usual way is not cryptographically necessary.
 */
#define USE_SHA

#ifdef USE_SHA

#define HASH_BUFFER_SIZE 5
#define HASH_EXTRA_SIZE 80
#define HASH_TRANSFORM SHATransform

/* Various size/speed tradeoffs are available.  Choose 0..3. */
#define SHA_CODE_SIZE 0

/*
 * SHA transform algorithm, taken from code written by Peter Gutmann,
 * and placed in the public domain.
 */

/* The SHA f()-functions.  */

#define f1(x,y,z)   ( z ^ (x & (y^z)) )		/* Rounds  0-19: x ? y : z */
#define f2(x,y,z)   (x ^ y ^ z)			/* Rounds 20-39: XOR */
#define f3(x,y,z)   ( (x & y) + (z & (x ^ y)) )	/* Rounds 40-59: majority */
#define f4(x,y,z)   (x ^ y ^ z)			/* Rounds 60-79: XOR */

/* The SHA Mysterious Constants */

#define K1  0x5A827999L			/* Rounds  0-19: sqrt(2) * 2^30 */
#define K2  0x6ED9EBA1L			/* Rounds 20-39: sqrt(3) * 2^30 */
#define K3  0x8F1BBCDCL			/* Rounds 40-59: sqrt(5) * 2^30 */
#define K4  0xCA62C1D6L			/* Rounds 60-79: sqrt(10) * 2^30 */

#define ROTL(n,X)  ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )

#define subRound(a, b, c, d, e, f, k, data) \
    ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )


static void SHATransform(__u32 digest[85], __u32 const data[16])
{
    __u32 A, B, C, D, E;     /* Local vars */
    __u32 TEMP;
    int	i;
#define W (digest + HASH_BUFFER_SIZE)	/* Expanded data array */

    /*
     * Do the preliminary expansion of 16 to 80 words.  Doing it
     * out-of-line line this is faster than doing it in-line on
     * register-starved machines like the x86, and not really any
     * slower on real processors.
     */
    memcpy(W, data, 16*sizeof(__u32));
    for (i = 0; i < 64; i++) {
	    TEMP = W[i] ^ W[i+2] ^ W[i+8] ^ W[i+13];
	    W[i+16] = ROTL(1, TEMP);
    }

    /* Set up first buffer and local data buffer */
    A = digest[ 0 ];
    B = digest[ 1 ];
    C = digest[ 2 ];
    D = digest[ 3 ];
    E = digest[ 4 ];

    /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */
#if SHA_CODE_SIZE == 0
    /*
     * Approximately 50% of the speed of the largest version, but
     * takes up 1/16 the space.  Saves about 6k on an i386 kernel.
     */
    for (i = 0; i < 80; i++) {
	if (i < 40) {
	    if (i < 20)
		TEMP = f1(B, C, D) + K1;
	    else
		TEMP = f2(B, C, D) + K2;
	} else {
	    if (i < 60)
		TEMP = f3(B, C, D) + K3;
	    else
		TEMP = f4(B, C, D) + K4;
	}
	TEMP += ROTL(5, A) + E + W[i];
	E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
    }
#elif SHA_CODE_SIZE == 1
    for (i = 0; i < 20; i++) {
	TEMP = f1(B, C, D) + K1 + ROTL(5, A) + E + W[i];
	E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
    }
    for (; i < 40; i++) {
	TEMP = f2(B, C, D) + K2 + ROTL(5, A) + E + W[i];
	E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
    }
    for (; i < 60; i++) {
	TEMP = f3(B, C, D) + K3 + ROTL(5, A) + E + W[i];
	E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
    }
    for (; i < 80; i++) {
	TEMP = f4(B, C, D) + K4 + ROTL(5, A) + E + W[i];
	E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
    }
#elif SHA_CODE_SIZE == 2
    for (i = 0; i < 20; i += 5) {
	subRound( A, B, C, D, E, f1, K1, W[ i   ] );
	subRound( E, A, B, C, D, f1, K1, W[ i+1 ] );
	subRound( D, E, A, B, C, f1, K1, W[ i+2 ] );
	subRound( C, D, E, A, B, f1, K1, W[ i+3 ] );
	subRound( B, C, D, E, A, f1, K1, W[ i+4 ] );
    }
    for (; i < 40; i += 5) {
	subRound( A, B, C, D, E, f2, K2, W[ i   ] );
	subRound( E, A, B, C, D, f2, K2, W[ i+1 ] );
	subRound( D, E, A, B, C, f2, K2, W[ i+2 ] );
	subRound( C, D, E, A, B, f2, K2, W[ i+3 ] );
	subRound( B, C, D, E, A, f2, K2, W[ i+4 ] );
    }
    for (; i < 60; i += 5) {
	subRound( A, B, C, D, E, f3, K3, W[ i   ] );
	subRound( E, A, B, C, D, f3, K3, W[ i+1 ] );
	subRound( D, E, A, B, C, f3, K3, W[ i+2 ] );
	subRound( C, D, E, A, B, f3, K3, W[ i+3 ] );
	subRound( B, C, D, E, A, f3, K3, W[ i+4 ] );
    }