1135446Strhodes/* 2193149Sdougb * Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC") 3135446Strhodes * Copyright (C) 1999-2002 Internet Software Consortium. 4135446Strhodes * 5193149Sdougb * Permission to use, copy, modify, and/or distribute this software for any 6135446Strhodes * purpose with or without fee is hereby granted, provided that the above 7135446Strhodes * copyright notice and this permission notice appear in all copies. 8135446Strhodes * 9135446Strhodes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 10135446Strhodes * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 11135446Strhodes * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 12135446Strhodes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 13135446Strhodes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 14135446Strhodes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 15135446Strhodes * PERFORMANCE OF THIS SOFTWARE. 16135446Strhodes */ 17135446Strhodes 18234010Sdougb/* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */ 19135446Strhodes 20170222Sdougb/*! \file */ 21170222Sdougb 22135446Strhodes#include <config.h> 23135446Strhodes 24153816Sdougb#include <stddef.h> 25135446Strhodes#include <stdlib.h> 26135446Strhodes 27135446Strhodes#include <isc/assertions.h> 28135446Strhodes#include <isc/lfsr.h> 29135446Strhodes#include <isc/util.h> 30135446Strhodes 31135446Strhodes#define VALID_LFSR(x) (x != NULL) 32135446Strhodes 33135446Strhodesvoid 34135446Strhodesisc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits, 35135446Strhodes isc_uint32_t tap, unsigned int count, 36135446Strhodes isc_lfsrreseed_t reseed, void *arg) 37135446Strhodes{ 38135446Strhodes REQUIRE(VALID_LFSR(lfsr)); 39135446Strhodes REQUIRE(8 <= bits && bits <= 32); 40135446Strhodes REQUIRE(tap != 0); 41135446Strhodes 42135446Strhodes lfsr->state = state; 43135446Strhodes lfsr->bits = bits; 44135446Strhodes lfsr->tap = tap; 45135446Strhodes lfsr->count = count; 46135446Strhodes lfsr->reseed = reseed; 47135446Strhodes lfsr->arg = arg; 48135446Strhodes 49135446Strhodes if (count == 0 && reseed != NULL) 50135446Strhodes reseed(lfsr, arg); 51135446Strhodes if (lfsr->state == 0) 52135446Strhodes lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 53135446Strhodes} 54135446Strhodes 55170222Sdougb/*! 56135446Strhodes * Return the next state of the lfsr. 57135446Strhodes */ 58135446Strhodesstatic inline isc_uint32_t 59135446Strhodeslfsr_generate(isc_lfsr_t *lfsr) 60135446Strhodes{ 61135446Strhodes 62135446Strhodes /* 63135446Strhodes * If the previous state is zero, we must fill it with something 64135446Strhodes * here, or we will begin to generate an extremely predictable output. 65135446Strhodes * 66135446Strhodes * First, give the reseed function a crack at it. If the state is 67135446Strhodes * still 0, set it to all ones. 68135446Strhodes */ 69135446Strhodes if (lfsr->state == 0) { 70135446Strhodes if (lfsr->reseed != NULL) 71135446Strhodes lfsr->reseed(lfsr, lfsr->arg); 72135446Strhodes if (lfsr->state == 0) 73135446Strhodes lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 74135446Strhodes } 75135446Strhodes 76135446Strhodes if (lfsr->state & 0x01) { 77135446Strhodes lfsr->state = (lfsr->state >> 1) ^ lfsr->tap; 78135446Strhodes return (1); 79135446Strhodes } else { 80135446Strhodes lfsr->state >>= 1; 81135446Strhodes return (0); 82135446Strhodes } 83135446Strhodes} 84135446Strhodes 85135446Strhodesvoid 86135446Strhodesisc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) 87135446Strhodes{ 88135446Strhodes unsigned char *p; 89135446Strhodes unsigned int bit; 90135446Strhodes unsigned int byte; 91135446Strhodes 92135446Strhodes REQUIRE(VALID_LFSR(lfsr)); 93135446Strhodes REQUIRE(data != NULL); 94135446Strhodes REQUIRE(count > 0); 95135446Strhodes 96135446Strhodes p = data; 97135446Strhodes byte = count; 98135446Strhodes 99135446Strhodes while (byte--) { 100135446Strhodes *p = 0; 101135446Strhodes for (bit = 0; bit < 7; bit++) { 102135446Strhodes *p |= lfsr_generate(lfsr); 103135446Strhodes *p <<= 1; 104135446Strhodes } 105135446Strhodes *p |= lfsr_generate(lfsr); 106135446Strhodes p++; 107135446Strhodes } 108135446Strhodes 109135446Strhodes if (lfsr->count != 0 && lfsr->reseed != NULL) { 110135446Strhodes if (lfsr->count <= count * 8) 111135446Strhodes lfsr->reseed(lfsr, lfsr->arg); 112135446Strhodes else 113135446Strhodes lfsr->count -= (count * 8); 114135446Strhodes } 115135446Strhodes} 116135446Strhodes 117135446Strhodesstatic inline isc_uint32_t 118135446Strhodeslfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) 119135446Strhodes{ 120135446Strhodes while (skip--) 121135446Strhodes (void)lfsr_generate(lfsr); 122135446Strhodes 123135446Strhodes (void)lfsr_generate(lfsr); 124135446Strhodes 125135446Strhodes return (lfsr->state); 126135446Strhodes} 127135446Strhodes 128135446Strhodes/* 129135446Strhodes * Skip "skip" states in "lfsr". 130135446Strhodes */ 131135446Strhodesvoid 132135446Strhodesisc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) 133135446Strhodes{ 134135446Strhodes REQUIRE(VALID_LFSR(lfsr)); 135135446Strhodes 136135446Strhodes while (skip--) 137135446Strhodes (void)lfsr_generate(lfsr); 138135446Strhodes} 139135446Strhodes 140135446Strhodes/* 141135446Strhodes * Skip states in lfsr1 and lfsr2 using the other's current state. 142135446Strhodes * Return the final state of lfsr1 ^ lfsr2. 143135446Strhodes */ 144135446Strhodesisc_uint32_t 145135446Strhodesisc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) 146135446Strhodes{ 147135446Strhodes isc_uint32_t state1, state2; 148135446Strhodes isc_uint32_t skip1, skip2; 149135446Strhodes 150135446Strhodes REQUIRE(VALID_LFSR(lfsr1)); 151135446Strhodes REQUIRE(VALID_LFSR(lfsr2)); 152135446Strhodes 153135446Strhodes skip1 = lfsr1->state & 0x01; 154135446Strhodes skip2 = lfsr2->state & 0x01; 155135446Strhodes 156135446Strhodes /* cross-skip. */ 157135446Strhodes state1 = lfsr_skipgenerate(lfsr1, skip2); 158135446Strhodes state2 = lfsr_skipgenerate(lfsr2, skip1); 159135446Strhodes 160135446Strhodes return (state1 ^ state2); 161135446Strhodes} 162