1258945Sroberto/* 2258945Sroberto * Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC") 3258945Sroberto * Copyright (C) 1999-2002 Internet Software Consortium. 4258945Sroberto * 5258945Sroberto * Permission to use, copy, modify, and/or distribute this software for any 6258945Sroberto * purpose with or without fee is hereby granted, provided that the above 7258945Sroberto * copyright notice and this permission notice appear in all copies. 8258945Sroberto * 9258945Sroberto * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10258945Sroberto * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11258945Sroberto * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12258945Sroberto * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13258945Sroberto * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14258945Sroberto * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15258945Sroberto * PERFORMANCE OF THIS SOFTWARE. 16258945Sroberto */ 17258945Sroberto 18258945Sroberto/* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */ 19258945Sroberto 20258945Sroberto/*! \file */ 21258945Sroberto 22258945Sroberto#include <config.h> 23258945Sroberto 24258945Sroberto#include <stddef.h> 25258945Sroberto#include <stdlib.h> 26258945Sroberto 27258945Sroberto#include <isc/assertions.h> 28258945Sroberto#include <isc/lfsr.h> 29258945Sroberto#include <isc/util.h> 30258945Sroberto 31258945Sroberto#define VALID_LFSR(x) (x != NULL) 32258945Sroberto 33258945Srobertovoid 34258945Srobertoisc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits, 35258945Sroberto isc_uint32_t tap, unsigned int count, 36258945Sroberto isc_lfsrreseed_t reseed, void *arg) 37258945Sroberto{ 38258945Sroberto REQUIRE(VALID_LFSR(lfsr)); 39258945Sroberto REQUIRE(8 <= bits && bits <= 32); 40258945Sroberto REQUIRE(tap != 0); 41258945Sroberto 42258945Sroberto lfsr->state = state; 43258945Sroberto lfsr->bits = bits; 44258945Sroberto lfsr->tap = tap; 45258945Sroberto lfsr->count = count; 46258945Sroberto lfsr->reseed = reseed; 47258945Sroberto lfsr->arg = arg; 48258945Sroberto 49258945Sroberto if (count == 0 && reseed != NULL) 50258945Sroberto reseed(lfsr, arg); 51258945Sroberto if (lfsr->state == 0) 52258945Sroberto lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 53258945Sroberto} 54258945Sroberto 55258945Sroberto/*! 56258945Sroberto * Return the next state of the lfsr. 57258945Sroberto */ 58258945Srobertostatic inline isc_uint32_t 59258945Srobertolfsr_generate(isc_lfsr_t *lfsr) 60258945Sroberto{ 61258945Sroberto 62258945Sroberto /* 63258945Sroberto * If the previous state is zero, we must fill it with something 64258945Sroberto * here, or we will begin to generate an extremely predictable output. 65258945Sroberto * 66258945Sroberto * First, give the reseed function a crack at it. If the state is 67258945Sroberto * still 0, set it to all ones. 68258945Sroberto */ 69258945Sroberto if (lfsr->state == 0) { 70258945Sroberto if (lfsr->reseed != NULL) 71258945Sroberto lfsr->reseed(lfsr, lfsr->arg); 72258945Sroberto if (lfsr->state == 0) 73258945Sroberto lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 74258945Sroberto } 75258945Sroberto 76258945Sroberto if (lfsr->state & 0x01) { 77258945Sroberto lfsr->state = (lfsr->state >> 1) ^ lfsr->tap; 78258945Sroberto return (1); 79258945Sroberto } else { 80258945Sroberto lfsr->state >>= 1; 81258945Sroberto return (0); 82258945Sroberto } 83258945Sroberto} 84258945Sroberto 85258945Srobertovoid 86258945Srobertoisc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) 87258945Sroberto{ 88258945Sroberto unsigned char *p; 89258945Sroberto unsigned int bit; 90258945Sroberto unsigned int byte; 91258945Sroberto 92258945Sroberto REQUIRE(VALID_LFSR(lfsr)); 93258945Sroberto REQUIRE(data != NULL); 94258945Sroberto REQUIRE(count > 0); 95258945Sroberto 96258945Sroberto p = data; 97258945Sroberto byte = count; 98258945Sroberto 99258945Sroberto while (byte--) { 100258945Sroberto *p = 0; 101258945Sroberto for (bit = 0; bit < 7; bit++) { 102258945Sroberto *p |= lfsr_generate(lfsr); 103258945Sroberto *p <<= 1; 104258945Sroberto } 105258945Sroberto *p |= lfsr_generate(lfsr); 106258945Sroberto p++; 107258945Sroberto } 108258945Sroberto 109258945Sroberto if (lfsr->count != 0 && lfsr->reseed != NULL) { 110258945Sroberto if (lfsr->count <= count * 8) 111258945Sroberto lfsr->reseed(lfsr, lfsr->arg); 112258945Sroberto else 113258945Sroberto lfsr->count -= (count * 8); 114258945Sroberto } 115258945Sroberto} 116258945Sroberto 117258945Srobertostatic inline isc_uint32_t 118258945Srobertolfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) 119258945Sroberto{ 120258945Sroberto while (skip--) 121258945Sroberto (void)lfsr_generate(lfsr); 122258945Sroberto 123258945Sroberto (void)lfsr_generate(lfsr); 124258945Sroberto 125258945Sroberto return (lfsr->state); 126258945Sroberto} 127258945Sroberto 128258945Sroberto/* 129258945Sroberto * Skip "skip" states in "lfsr". 130258945Sroberto */ 131258945Srobertovoid 132258945Srobertoisc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) 133258945Sroberto{ 134258945Sroberto REQUIRE(VALID_LFSR(lfsr)); 135258945Sroberto 136258945Sroberto while (skip--) 137258945Sroberto (void)lfsr_generate(lfsr); 138258945Sroberto} 139258945Sroberto 140258945Sroberto/* 141258945Sroberto * Skip states in lfsr1 and lfsr2 using the other's current state. 142258945Sroberto * Return the final state of lfsr1 ^ lfsr2. 143258945Sroberto */ 144258945Srobertoisc_uint32_t 145258945Srobertoisc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) 146258945Sroberto{ 147258945Sroberto isc_uint32_t state1, state2; 148258945Sroberto isc_uint32_t skip1, skip2; 149258945Sroberto 150258945Sroberto REQUIRE(VALID_LFSR(lfsr1)); 151258945Sroberto REQUIRE(VALID_LFSR(lfsr2)); 152258945Sroberto 153258945Sroberto skip1 = lfsr1->state & 0x01; 154258945Sroberto skip2 = lfsr2->state & 0x01; 155258945Sroberto 156258945Sroberto /* cross-skip. */ 157258945Sroberto state1 = lfsr_skipgenerate(lfsr1, skip2); 158258945Sroberto state2 = lfsr_skipgenerate(lfsr2, skip1); 159258945Sroberto 160258945Sroberto return (state1 ^ state2); 161258945Sroberto} 162