lfsr.c revision 153816
150472Speter/* 237Srgrimes * Copyright (C) 2004, 2005 Internet Systems Consortium, Inc. ("ISC") 378822Snik * Copyright (C) 1999-2002 Internet Software Consortium. 450203Srgrimes * 537Srgrimes * Permission to use, copy, modify, and distribute this software for any 639161Sobrien * purpose with or without fee is hereby granted, provided that the above 739490Sobrien * copyright notice and this permission notice appear in all copies. 88571Srgrimes * 92878Srgrimes * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 1072515Sru * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 1172515Sru * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 128571Srgrimes * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 132878Srgrimes * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 148571Srgrimes * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 158571Srgrimes * PERFORMANCE OF THIS SOFTWARE. 1672515Sru */ 172878Srgrimes 1872515Sru/* $Id: lfsr.c,v 1.11.2.2.2.6 2005/10/14 01:38:50 marka Exp $ */ 19155345Srwatson 20155197Srwatson#include <config.h> 21155197Srwatson 22244398Srwatson#include <stddef.h> 23244398Srwatson#include <stdlib.h> 24244398Srwatson 25244398Srwatson#include <isc/assertions.h> 26155345Srwatson#include <isc/lfsr.h> 2772515Sru#include <isc/util.h> 282878Srgrimes 29219820Sjeff#define VALID_LFSR(x) (x != NULL) 30219820Sjeff 3172515Sruvoid 322878Srgrimesisc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits, 3372515Sru isc_uint32_t tap, unsigned int count, 3472515Sru isc_lfsrreseed_t reseed, void *arg) 352878Srgrimes{ 362878Srgrimes REQUIRE(VALID_LFSR(lfsr)); 3772515Sru REQUIRE(8 <= bits && bits <= 32); 3872515Sru REQUIRE(tap != 0); 3972515Sru 4045173Sasami lfsr->state = state; 41200054Scperciva lfsr->bits = bits; 42161748Scperciva lfsr->tap = tap; 4386601Sru lfsr->count = count; 4485220Sdarrenr lfsr->reseed = reseed; 4572515Sru lfsr->arg = arg; 4672515Sru 47124753Seivind if (count == 0 && reseed != NULL) 48124753Seivind reseed(lfsr, arg); 49148871Scperciva if (lfsr->state == 0) 50148871Scperciva lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 512878Srgrimes} 52123051Sru 5398699Sdes/* 54123051Sru * Return the next state of the lfsr. 55106403Smarkm */ 5685484Srustatic inline isc_uint32_t 5780516Smarkmlfsr_generate(isc_lfsr_t *lfsr) 5839490Sobrien{ 592878Srgrimes 6086601Sru /* 612878Srgrimes * If the previous state is zero, we must fill it with something 6212388Sache * here, or we will begin to generate an extremely predictable output. 632878Srgrimes * 64136552Sru * First, give the reseed function a crack at it. If the state is 65135875Sdougb * still 0, set it to all ones. 6639490Sobrien */ 672878Srgrimes if (lfsr->state == 0) { 6839490Sobrien if (lfsr->reseed != NULL) 6982191Skuriyama lfsr->reseed(lfsr, lfsr->arg); 7082191Skuriyama if (lfsr->state == 0) 7185848Scjc lfsr->state = 0xffffffffU >> (32 - lfsr->bits); 7285916Scjc } 73212411Sbschmidt 74212411Sbschmidt if (lfsr->state & 0x01) { 752878Srgrimes lfsr->state = (lfsr->state >> 1) ^ lfsr->tap; 7686601Sru return (1); 772878Srgrimes } else { 7872515Sru lfsr->state >>= 1; 7986601Sru return (0); 802878Srgrimes } 8172515Sru} 8241855Speter 832878Srgrimesvoid 8441855Speterisc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count) 852878Srgrimes{ 8650296Srgrimes unsigned char *p; 8750296Srgrimes unsigned int bit; 8841855Speter unsigned int byte; 8950296Srgrimes 9050296Srgrimes REQUIRE(VALID_LFSR(lfsr)); 912878Srgrimes REQUIRE(data != NULL); 9286601Sru REQUIRE(count > 0); 932878Srgrimes 9472515Sru p = data; 9572515Sru byte = count; 968571Srgrimes 972878Srgrimes while (byte--) { 9841855Speter *p = 0; 998571Srgrimes for (bit = 0; bit < 7; bit++) { 100949Snate *p |= lfsr_generate(lfsr); 101 *p <<= 1; 102 } 103 *p |= lfsr_generate(lfsr); 104 p++; 105 } 106 107 if (lfsr->count != 0 && lfsr->reseed != NULL) { 108 if (lfsr->count <= count * 8) 109 lfsr->reseed(lfsr, lfsr->arg); 110 else 111 lfsr->count -= (count * 8); 112 } 113} 114 115static inline isc_uint32_t 116lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip) 117{ 118 while (skip--) 119 (void)lfsr_generate(lfsr); 120 121 (void)lfsr_generate(lfsr); 122 123 return (lfsr->state); 124} 125 126/* 127 * Skip "skip" states in "lfsr". 128 */ 129void 130isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip) 131{ 132 REQUIRE(VALID_LFSR(lfsr)); 133 134 while (skip--) 135 (void)lfsr_generate(lfsr); 136} 137 138/* 139 * Skip states in lfsr1 and lfsr2 using the other's current state. 140 * Return the final state of lfsr1 ^ lfsr2. 141 */ 142isc_uint32_t 143isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2) 144{ 145 isc_uint32_t state1, state2; 146 isc_uint32_t skip1, skip2; 147 148 REQUIRE(VALID_LFSR(lfsr1)); 149 REQUIRE(VALID_LFSR(lfsr2)); 150 151 skip1 = lfsr1->state & 0x01; 152 skip2 = lfsr2->state & 0x01; 153 154 /* cross-skip. */ 155 state1 = lfsr_skipgenerate(lfsr1, skip2); 156 state2 = lfsr_skipgenerate(lfsr2, skip1); 157 158 return (state1 ^ state2); 159} 160