lfsr.c revision 234010
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