1290001Sglebius/* 2290001Sglebius * Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC") 3290001Sglebius * Copyright (C) 1999-2002 Internet Software Consortium. 4290001Sglebius * 5290001Sglebius * Permission to use, copy, modify, and/or distribute this software for any 6290001Sglebius * purpose with or without fee is hereby granted, provided that the above 7290001Sglebius * copyright notice and this permission notice appear in all copies. 8290001Sglebius * 9290001Sglebius * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10290001Sglebius * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11290001Sglebius * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12290001Sglebius * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13290001Sglebius * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14290001Sglebius * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15290001Sglebius * PERFORMANCE OF THIS SOFTWARE. 16290001Sglebius */ 17290001Sglebius 18290001Sglebius/* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */ 19290001Sglebius 20290001Sglebius/*! \file */ 21290001Sglebius 22290001Sglebius#include <config.h> 23290001Sglebius 24290001Sglebius#include <stddef.h> 25290001Sglebius#include <stdlib.h> 26290001Sglebius 27290001Sglebius#include <isc/assertions.h> 28290001Sglebius#include <isc/lfsr.h> 29290001Sglebius#include <isc/util.h> 30290001Sglebius 31290001Sglebius#define VALID_LFSR(x) (x != NULL) 32290001Sglebius 33290001Sglebiusvoid 34290001Sglebiusisc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits, 35290001Sglebius isc_uint32_t tap, unsigned int count, 36290001Sglebius isc_lfsrreseed_t reseed, void *arg) 37290001Sglebius{ 38290001Sglebius REQUIRE(VALID_LFSR(lfsr)); 39290001Sglebius REQUIRE(8 <= bits && bits <= 32); 40290001Sglebius REQUIRE(tap != 0); 41290001Sglebius 42290001Sglebius lfsr->state = state; 43290001Sglebius lfsr->bits = bits; 44290001Sglebius lfsr->tap = tap; 45290001Sglebius lfsr->count = count; 46290001Sglebius lfsr->reseed = reseed; 47290001Sglebius lfsr->arg = arg; 48290001Sglebius 49290001Sglebius if (count == 0 && reseed != NULL) 50290001Sglebius reseed(lfsr, arg); 51290001Sglebius if (lfsr->state == 0) 52290001Sglebius lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 53290001Sglebius} 54290001Sglebius 55290001Sglebius/*! 56290001Sglebius * Return the next state of the lfsr. 57290001Sglebius */ 58290001Sglebiusstatic inline isc_uint32_t 59290001Sglebiuslfsr_generate(isc_lfsr_t *lfsr) 60290001Sglebius{ 61290001Sglebius 62290001Sglebius /* 63290001Sglebius * If the previous state is zero, we must fill it with something 64290001Sglebius * here, or we will begin to generate an extremely predictable output. 65290001Sglebius * 66290001Sglebius * First, give the reseed function a crack at it. If the state is 67290001Sglebius * still 0, set it to all ones. 68290001Sglebius */ 69290001Sglebius if (lfsr->state == 0) { 70290001Sglebius if (lfsr->reseed != NULL) 71290001Sglebius lfsr->reseed(lfsr, lfsr->arg); 72290001Sglebius if (lfsr->state == 0) 73290001Sglebius lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 74290001Sglebius } 75290001Sglebius 76290001Sglebius if (lfsr->state & 0x01) { 77290001Sglebius lfsr->state = (lfsr->state >> 1) ^ lfsr->tap; 78290001Sglebius return (1); 79290001Sglebius } else { 80290001Sglebius lfsr->state >>= 1; 81290001Sglebius return (0); 82290001Sglebius } 83290001Sglebius} 84290001Sglebius 85290001Sglebiusvoid 86290001Sglebiusisc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) 87290001Sglebius{ 88290001Sglebius unsigned char *p; 89290001Sglebius unsigned int bit; 90290001Sglebius unsigned int byte; 91290001Sglebius 92290001Sglebius REQUIRE(VALID_LFSR(lfsr)); 93290001Sglebius REQUIRE(data != NULL); 94290001Sglebius REQUIRE(count > 0); 95290001Sglebius 96290001Sglebius p = data; 97290001Sglebius byte = count; 98290001Sglebius 99290001Sglebius while (byte--) { 100290001Sglebius *p = 0; 101290001Sglebius for (bit = 0; bit < 7; bit++) { 102290001Sglebius *p |= lfsr_generate(lfsr); 103290001Sglebius *p <<= 1; 104290001Sglebius } 105290001Sglebius *p |= lfsr_generate(lfsr); 106290001Sglebius p++; 107290001Sglebius } 108290001Sglebius 109290001Sglebius if (lfsr->count != 0 && lfsr->reseed != NULL) { 110290001Sglebius if (lfsr->count <= count * 8) 111290001Sglebius lfsr->reseed(lfsr, lfsr->arg); 112290001Sglebius else 113290001Sglebius lfsr->count -= (count * 8); 114290001Sglebius } 115290001Sglebius} 116290001Sglebius 117290001Sglebiusstatic inline isc_uint32_t 118290001Sglebiuslfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) 119290001Sglebius{ 120290001Sglebius while (skip--) 121290001Sglebius (void)lfsr_generate(lfsr); 122290001Sglebius 123290001Sglebius (void)lfsr_generate(lfsr); 124290001Sglebius 125290001Sglebius return (lfsr->state); 126290001Sglebius} 127290001Sglebius 128290001Sglebius/* 129290001Sglebius * Skip "skip" states in "lfsr". 130290001Sglebius */ 131290001Sglebiusvoid 132290001Sglebiusisc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) 133290001Sglebius{ 134290001Sglebius REQUIRE(VALID_LFSR(lfsr)); 135290001Sglebius 136290001Sglebius while (skip--) 137290001Sglebius (void)lfsr_generate(lfsr); 138290001Sglebius} 139290001Sglebius 140290001Sglebius/* 141290001Sglebius * Skip states in lfsr1 and lfsr2 using the other's current state. 142290001Sglebius * Return the final state of lfsr1 ^ lfsr2. 143290001Sglebius */ 144290001Sglebiusisc_uint32_t 145290001Sglebiusisc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) 146290001Sglebius{ 147290001Sglebius isc_uint32_t state1, state2; 148290001Sglebius isc_uint32_t skip1, skip2; 149290001Sglebius 150290001Sglebius REQUIRE(VALID_LFSR(lfsr1)); 151290001Sglebius REQUIRE(VALID_LFSR(lfsr2)); 152290001Sglebius 153290001Sglebius skip1 = lfsr1->state & 0x01; 154290001Sglebius skip2 = lfsr2->state & 0x01; 155290001Sglebius 156290001Sglebius /* cross-skip. */ 157290001Sglebius state1 = lfsr_skipgenerate(lfsr1, skip2); 158290001Sglebius state2 = lfsr_skipgenerate(lfsr2, skip1); 159290001Sglebius 160290001Sglebius return (state1 ^ state2); 161290001Sglebius} 162