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