random.c

linux和2410结合开发 用他可以生成2410所需的zImage文件

{
	return (word << i) | (word >> (32 - i));
	
}
#else
extern inline __u32 rotate_left(int i, __u32 word)
{
	__asm__("roll %%cl,%0"
		:"=r" (word)
		:"0" (word),"c" (i));
	return word;
}
#endif

/*
 * More asm magic....
 * 
 * For entropy estimation, we need to do an integral base 2
 * logarithm.  
 *
 * Note the "12bits" suffix - this is used for numbers between
 * 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

#if 0
#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
#else
#define DEBUG_ENT(fmt, arg...) do {} while (0)
#endif

/**********************************************************************
 *
 * OS independent entropy store.   Here are the functions which handle
 * storing entropy in an entropy pool.
 * 
 **********************************************************************/

struct entropy_store {
	unsigned	add_ptr;
	int		entropy_count;
	int		input_rotate;
	int		extract_count;
	struct poolinfo poolinfo;
	__u32		*pool;
};

/*
 * Initialize the entropy store.  The input argument is the size of
 * the random pool.
 *
 * Returns an negative error if there is a problem.
 */
static int create_entropy_store(int size, struct entropy_store **ret_bucket)
{
	struct	entropy_store	*r;
	struct	poolinfo	*p;
	int	poolwords;

	poolwords = (size + 3) / 4; /* Convert bytes->words */
	/* The pool size must be a multiple of 16 32-bit words */
	poolwords = ((poolwords + 15) / 16) * 16; 

	for (p = poolinfo_table; p->poolwords; p++) {
		if (poolwords == p->poolwords)
			break;
	}
	if (p->poolwords == 0)
		return -EINVAL;

	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
	if (!r)
		return -ENOMEM;

	memset (r, 0, sizeof(struct entropy_store));
	r->poolinfo = *p;

	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
	if (!r->pool) {
		kfree(r);
		return -ENOMEM;
	}
	memset(r->pool, 0, POOLBYTES);
	*ret_bucket = r;
	return 0;
}

/* Clear the entropy pool and associated counters. */
static void clear_entropy_store(struct entropy_store *r)
{
	r->add_ptr = 0;
	r->entropy_count = 0;
	r->input_rotate = 0;
	r->extract_count = 0;
	memset(r->pool, 0, r->poolinfo.POOLBYTES);
}

static void free_entropy_store(struct entropy_store *r)
{
	if (r->pool)
		kfree(r->pool);
	kfree(r);
}

/*
 * This function adds a byte into the entropy "pool".  It does not
 * update the entropy estimate.  The caller should call
 * credit_entropy_store if this is appropriate.
 * 
 * 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.
 */
static void add_entropy_words(struct entropy_store *r, const __u32 *in,
			      int nwords)
{
	static __u32 const twist_table[8] = {
		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
	unsigned i;
	int new_rotate;
	int wordmask = r->poolinfo.poolwords - 1;
	__u32 w;

	while (nwords--) {
		w = rotate_left(r->input_rotate, *in++);
		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
		/*
		 * Normally, we add 7 bits of rotation to the pool.
		 * At the beginning of the pool, add an extra 7 bits
		 * rotation, so that successive passes spread the
		 * input bits across the pool evenly.
		 */
		new_rotate = r->input_rotate + 14;
		if (i)
			new_rotate = r->input_rotate + 7;
		r->input_rotate = new_rotate & 31;

		/* XOR in the various taps */
		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
		w ^= r->pool[i];
		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
	}
}

/*
 * Credit (or debit) the entropy store with n bits of entropy
 */
static void credit_entropy_store(struct entropy_store *r, int nbits)
{
	if (r->entropy_count + nbits < 0) {
		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
			  r->entropy_count, nbits);
		r->entropy_count = 0;
	} else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) {
		r->entropy_count = r->poolinfo.POOLBITS;
	} else {
		r->entropy_count += nbits;
		if (nbits)
			DEBUG_ENT("%s added %d bits, now %d\n",
				  r == sec_random_state ? "secondary" :
				  r == random_state ? "primary" : "unknown",
				  nbits, r->entropy_count);
	}
}

/**********************************************************************
 *
 * Entropy batch input management
 *
 * We batch entropy to be added to avoid increasing interrupt latency
 *
 **********************************************************************/

static __u32	*batch_entropy_pool;
static int	*batch_entropy_credit;
static int	batch_max;
static int	batch_head, batch_tail;
static struct tq_struct	batch_tqueue;
static void batch_entropy_process(void *private_);

/* note: the size must be a power of 2 */
static int __init batch_entropy_init(int size, struct entropy_store *r)
{
	batch_entropy_pool = kmalloc(2*size*sizeof(__u32), GFP_KERNEL);
	if (!batch_entropy_pool)
		return -1;
	batch_entropy_credit =kmalloc(size*sizeof(int), GFP_KERNEL);
	if (!batch_entropy_credit) {
		kfree(batch_entropy_pool);
		return -1;
	}
	batch_head = batch_tail = 0;
	batch_max = size;
	batch_tqueue.routine = batch_entropy_process;
	batch_tqueue.data = r;
	return 0;
}

/*
 * Changes to the entropy data is put into a queue rather than being added to
 * the entropy counts directly.  This is presumably to avoid doing heavy
 * hashing calculations during an interrupt in add_timer_randomness().
 * Instead, the entropy is only added to the pool once per timer tick.
 */
void batch_entropy_store(u32 a, u32 b, int num)
{
	int	new;

	if (!batch_max)
		return;
	
	batch_entropy_pool[2*batch_head] = a;
	batch_entropy_pool[(2*batch_head) + 1] = b;
	batch_entropy_credit[batch_head] = num;

	new = (batch_head+1) & (batch_max-1);
	if (new != batch_tail) {
		queue_task(&batch_tqueue, &tq_timer);
		batch_head = new;
	} else {
		DEBUG_ENT("batch entropy buffer full\n");
	}
}

/*
 * Flush out the accumulated entropy operations, adding entropy to the passed
 * store (normally random_state).  If that store has enough entropy, alternate
 * between randomizing the data of the primary and secondary stores.
 */
static void batch_entropy_process(void *private_)
{
	struct entropy_store *r	= (struct entropy_store *) private_, *p;
	int max_entropy = r->poolinfo.POOLBITS;

	if (!batch_max)
		return;

	p = r;
	while (batch_head != batch_tail) {
		if (r->entropy_count >= max_entropy) {
			r = (r == sec_random_state) ?	random_state :
							sec_random_state;
			max_entropy = r->poolinfo.POOLBITS;
		}
		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
		batch_tail = (batch_tail+1) & (batch_max-1);
	}
	if (p->entropy_count >= random_read_wakeup_thresh)
		wake_up_interruptible(&random_read_wait);
}

/*********************************************************************
 *
 * Entropy input management
 *
 *********************************************************************/

/* There is one of these per entropy source */
struct timer_rand_state {
	__u32		last_time;
	__s32		last_delta,last_delta2;
	int		dont_count_entropy:1;
};

static struct timer_rand_state keyboard_timer_state;
static struct timer_rand_state mouse_timer_state;
static struct timer_rand_state extract_timer_state;
static struct timer_rand_state *irq_timer_state[NR_IRQS];
static struct timer_rand_state *blkdev_timer_state[MAX_BLKDEV];

/*
 * 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 timer_rand_state *state, unsigned num)
{
	__u32		time;
	__s32		delta, delta2, delta3;
	int		entropy = 0;

#if defined (__i386__)
	if ( test_bit(X86_FEATURE_TSC, &boot_cpu_data.x86_capability) ) {
		__u32 high;
		rdtsc(time, high);
		num ^= high;
	} else {
		time = jiffies;
	}
#elif defined (__x86_64__)
	__u32 high;
	rdtsc(time, high);
	num ^= high;
#else
	time = jiffies;
#endif

	/*
	 * 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 (!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;

		entropy = int_ln_12bits(delta);
	}
	batch_entropy_store(num, time, entropy);
}

void add_keyboard_randomness(unsigned char scancode)
{
	static unsigned char last_scancode;
	/* ignore autorepeat (multiple key down w/o key up) */
	if (scancode != last_scancode) {
		last_scancode = scancode;
		add_timer_randomness(&keyboard_timer_state, scancode);
	}
}

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

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

	add_timer_randomness(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(blkdev_timer_state[major], 0x200+major);
}

/******************************************************************
 *