1 /* $NetBSD: lfsr.c,v 1.1 2024/02/18 20:57:49 christos Exp $ */
2
3 /*
4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
5 *
6 * SPDX-License-Identifier: MPL-2.0
7 *
8 * This Source Code Form is subject to the terms of the Mozilla Public
9 * License, v. 2.0. If a copy of the MPL was not distributed with this
10 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
11 *
12 * See the COPYRIGHT file distributed with this work for additional
13 * information regarding copyright ownership.
14 */
15
16 /*! \file */
17
18 #include <inttypes.h>
19 #include <stddef.h>
20 #include <stdlib.h>
21
22 #include <isc/assertions.h>
23 #include <isc/lfsr.h>
24 #include <isc/util.h>
25
26 #define VALID_LFSR(x) (x != NULL)
27
28 void
isc_lfsr_init(isc_lfsr_t * lfsr,uint32_t state,unsigned int bits,uint32_t tap,unsigned int count,isc_lfsrreseed_t reseed,void * arg)29 isc_lfsr_init(isc_lfsr_t *lfsr, uint32_t state, unsigned int bits, uint32_t tap,
30 unsigned int count, isc_lfsrreseed_t reseed, void *arg) {
31 REQUIRE(VALID_LFSR(lfsr));
32 REQUIRE(8 <= bits && bits <= 32);
33 REQUIRE(tap != 0);
34
35 lfsr->state = state;
36 lfsr->bits = bits;
37 lfsr->tap = tap;
38 lfsr->count = count;
39 lfsr->reseed = reseed;
40 lfsr->arg = arg;
41
42 if (count == 0 && reseed != NULL) {
43 reseed(lfsr, arg);
44 }
45 if (lfsr->state == 0) {
46 lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
47 }
48 }
49
50 /*!
51 * Return the next state of the lfsr.
52 */
53 static uint32_t
lfsr_generate(isc_lfsr_t * lfsr)54 lfsr_generate(isc_lfsr_t *lfsr) {
55 /*
56 * If the previous state is zero, we must fill it with something
57 * here, or we will begin to generate an extremely predictable output.
58 *
59 * First, give the reseed function a crack at it. If the state is
60 * still 0, set it to all ones.
61 */
62 if (lfsr->state == 0) {
63 if (lfsr->reseed != NULL) {
64 lfsr->reseed(lfsr, lfsr->arg);
65 }
66 if (lfsr->state == 0) {
67 lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
68 }
69 }
70
71 if (lfsr->state & 0x01) {
72 lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
73 return (1);
74 } else {
75 lfsr->state >>= 1;
76 return (0);
77 }
78 }
79
80 void
isc_lfsr_generate(isc_lfsr_t * lfsr,void * data,unsigned int count)81 isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) {
82 unsigned char *p;
83 unsigned int bit;
84 unsigned int byte;
85
86 REQUIRE(VALID_LFSR(lfsr));
87 REQUIRE(data != NULL);
88 REQUIRE(count > 0);
89
90 p = data;
91 byte = count;
92
93 while (byte--) {
94 *p = 0;
95 for (bit = 0; bit < 7; bit++) {
96 *p |= lfsr_generate(lfsr);
97 *p <<= 1;
98 }
99 *p |= lfsr_generate(lfsr);
100 p++;
101 }
102
103 if (lfsr->count != 0 && lfsr->reseed != NULL) {
104 if (lfsr->count <= count * 8) {
105 lfsr->reseed(lfsr, lfsr->arg);
106 } else {
107 lfsr->count -= (count * 8);
108 }
109 }
110 }
111
112 static uint32_t
lfsr_skipgenerate(isc_lfsr_t * lfsr,unsigned int skip)113 lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) {
114 while (skip--) {
115 (void)lfsr_generate(lfsr);
116 }
117
118 (void)lfsr_generate(lfsr);
119
120 return (lfsr->state);
121 }
122
123 /*
124 * Skip "skip" states in "lfsr".
125 */
126 void
isc_lfsr_skip(isc_lfsr_t * lfsr,unsigned int skip)127 isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) {
128 REQUIRE(VALID_LFSR(lfsr));
129
130 while (skip--) {
131 (void)lfsr_generate(lfsr);
132 }
133 }
134
135 /*
136 * Skip states in lfsr1 and lfsr2 using the other's current state.
137 * Return the final state of lfsr1 ^ lfsr2.
138 */
139 uint32_t
isc_lfsr_generate32(isc_lfsr_t * lfsr1,isc_lfsr_t * lfsr2)140 isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) {
141 uint32_t state1, state2;
142 uint32_t skip1, skip2;
143
144 REQUIRE(VALID_LFSR(lfsr1));
145 REQUIRE(VALID_LFSR(lfsr2));
146
147 skip1 = lfsr1->state & 0x01;
148 skip2 = lfsr2->state & 0x01;
149
150 /* cross-skip. */
151 state1 = lfsr_skipgenerate(lfsr1, skip2);
152 state2 = lfsr_skipgenerate(lfsr2, skip1);
153
154 return (state1 ^ state2);
155 }
156