1 /* $NetBSD: lfsr.c,v 1.4 2014/12/10 04:37:59 christos Exp $ */ 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 35 void 36 isc_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 */ 60 static inline isc_uint32_t 61 lfsr_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 87 void 88 isc_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 119 static inline isc_uint32_t 120 lfsr_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 */ 133 void 134 isc_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 */ 146 isc_uint32_t 147 isc_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