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