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