lfsr.c revision 290001 
1/*
2 * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 1999-2002  Internet Software Consortium.
4 *
5 * Permission to use, copy, modify, and/or distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
16 */
17
18/* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */
19
20/*! \file */
21
22#include <config.h>
23
24#include <stddef.h>
25#include <stdlib.h>
26
27#include <isc/assertions.h>
28#include <isc/lfsr.h>
29#include <isc/util.h>
30
31#define VALID_LFSR(x)	(x != NULL)
32
33void
34isc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits,
35	      isc_uint32_t tap, unsigned int count,
36	      isc_lfsrreseed_t reseed, void *arg)
37{
38	REQUIRE(VALID_LFSR(lfsr));
39	REQUIRE(8 <= bits && bits <= 32);
40	REQUIRE(tap != 0);
41
42	lfsr->state = state;
43	lfsr->bits = bits;
44	lfsr->tap = tap;
45	lfsr->count = count;
46	lfsr->reseed = reseed;
47	lfsr->arg = arg;
48
49	if (count == 0 && reseed != NULL)
50		reseed(lfsr, arg);
51	if (lfsr->state == 0)
52		lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
53}
54
55/*!
56 * Return the next state of the lfsr.
57 */
58static inline isc_uint32_t
59lfsr_generate(isc_lfsr_t *lfsr)
60{
61
62	/*
63	 * If the previous state is zero, we must fill it with something
64	 * here, or we will begin to generate an extremely predictable output.
65	 *
66	 * First, give the reseed function a crack at it.  If the state is
67	 * still 0, set it to all ones.
68	 */
69	if (lfsr->state == 0) {
70		if (lfsr->reseed != NULL)
71			lfsr->reseed(lfsr, lfsr->arg);
72		if (lfsr->state == 0)
73			lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
74	}
75
76	if (lfsr->state & 0x01) {
77		lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
78		return (1);
79	} else {
80		lfsr->state >>= 1;
81		return (0);
82	}
83}
84
85void
86isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count)
87{
88	unsigned char *p;
89	unsigned int bit;
90	unsigned int byte;
91
92	REQUIRE(VALID_LFSR(lfsr));
93	REQUIRE(data != NULL);
94	REQUIRE(count > 0);
95
96	p = data;
97	byte = count;
98
99	while (byte--) {
100		*p = 0;
101		for (bit = 0; bit < 7; bit++) {
102			*p |= lfsr_generate(lfsr);
103			*p <<= 1;
104		}
105		*p |= lfsr_generate(lfsr);
106		p++;
107	}
108
109	if (lfsr->count != 0 && lfsr->reseed != NULL) {
110		if (lfsr->count <= count * 8)
111			lfsr->reseed(lfsr, lfsr->arg);
112		else
113			lfsr->count -= (count * 8);
114	}
115}
116
117static inline isc_uint32_t
118lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip)
119{
120	while (skip--)
121		(void)lfsr_generate(lfsr);
122
123	(void)lfsr_generate(lfsr);
124
125	return (lfsr->state);
126}
127
128/*
129 * Skip "skip" states in "lfsr".
130 */
131void
132isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip)
133{
134	REQUIRE(VALID_LFSR(lfsr));
135
136	while (skip--)
137		(void)lfsr_generate(lfsr);
138}
139
140/*
141 * Skip states in lfsr1 and lfsr2 using the other's current state.
142 * Return the final state of lfsr1 ^ lfsr2.
143 */
144isc_uint32_t
145isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2)
146{
147	isc_uint32_t state1, state2;
148	isc_uint32_t skip1, skip2;
149
150	REQUIRE(VALID_LFSR(lfsr1));
151	REQUIRE(VALID_LFSR(lfsr2));
152
153	skip1 = lfsr1->state & 0x01;
154	skip2 = lfsr2->state & 0x01;
155
156	/* cross-skip. */
157	state1 = lfsr_skipgenerate(lfsr1, skip2);
158	state2 = lfsr_skipgenerate(lfsr2, skip1);
159
160	return (state1 ^ state2);
161}
162