lfsr.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2004, 2005, 2007  Internet Systems Consortium, Inc. ("ISC")
00003  * Copyright (C) 1999-2002  Internet Software Consortium.
00004  *
00005  * Permission to use, copy, modify, and/or distribute this software for any
00006  * purpose with or without fee is hereby granted, provided that the above
00007  * copyright notice and this permission notice appear in all copies.
00008  *
00009  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
00010  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
00011  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
00012  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
00013  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
00014  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
00015  * PERFORMANCE OF THIS SOFTWARE.
00016  */
00017 
00018 /* $Id: lfsr.c,v 1.20 2007/06/19 23:47:17 tbox Exp $ */
00019 
00020 /*! \file */
00021 
00022 #include <config.h>
00023 
00024 #include <stddef.h>
00025 #include <stdlib.h>
00026 
00027 #include <isc/assertions.h>
00028 #include <isc/lfsr.h>
00029 #include <isc/util.h>
00030 
00031 #define VALID_LFSR(x)   (x != NULL)
00032 
00033 void
00034 isc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits,
00035               isc_uint32_t tap, unsigned int count,
00036               isc_lfsrreseed_t reseed, void *arg)
00037 {
00038         REQUIRE(VALID_LFSR(lfsr));
00039         REQUIRE(8 <= bits && bits <= 32);
00040         REQUIRE(tap != 0);
00041 
00042         lfsr->state = state;
00043         lfsr->bits = bits;
00044         lfsr->tap = tap;
00045         lfsr->count = count;
00046         lfsr->reseed = reseed;
00047         lfsr->arg = arg;
00048 
00049         if (count == 0 && reseed != NULL)
00050                 reseed(lfsr, arg);
00051         if (lfsr->state == 0)
00052                 lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
00053 }
00054 
00055 /*!
00056  * Return the next state of the lfsr.
00057  */
00058 static inline isc_uint32_t
00059 lfsr_generate(isc_lfsr_t *lfsr)
00060 {
00061 
00062         /*
00063          * If the previous state is zero, we must fill it with something
00064          * here, or we will begin to generate an extremely predictable output.
00065          *
00066          * First, give the reseed function a crack at it.  If the state is
00067          * still 0, set it to all ones.
00068          */
00069         if (lfsr->state == 0) {
00070                 if (lfsr->reseed != NULL)
00071                         lfsr->reseed(lfsr, lfsr->arg);
00072                 if (lfsr->state == 0)
00073                         lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
00074         }
00075 
00076         if (lfsr->state & 0x01) {
00077                 lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
00078                 return (1);
00079         } else {
00080                 lfsr->state >>= 1;
00081                 return (0);
00082         }
00083 }
00084 
00085 void
00086 isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count)
00087 {
00088         unsigned char *p;
00089         unsigned int bit;
00090         unsigned int byte;
00091 
00092         REQUIRE(VALID_LFSR(lfsr));
00093         REQUIRE(data != NULL);
00094         REQUIRE(count > 0);
00095 
00096         p = data;
00097         byte = count;
00098 
00099         while (byte--) {
00100                 *p = 0;
00101                 for (bit = 0; bit < 7; bit++) {
00102                         *p |= lfsr_generate(lfsr);
00103                         *p <<= 1;
00104                 }
00105                 *p |= lfsr_generate(lfsr);
00106                 p++;
00107         }
00108 
00109         if (lfsr->count != 0 && lfsr->reseed != NULL) {
00110                 if (lfsr->count <= count * 8)
00111                         lfsr->reseed(lfsr, lfsr->arg);
00112                 else
00113                         lfsr->count -= (count * 8);
00114         }
00115 }
00116 
00117 static inline isc_uint32_t
00118 lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip)
00119 {
00120         while (skip--)
00121                 (void)lfsr_generate(lfsr);
00122 
00123         (void)lfsr_generate(lfsr);
00124 
00125         return (lfsr->state);
00126 }
00127 
00128 /*
00129  * Skip "skip" states in "lfsr".
00130  */
00131 void
00132 isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip)
00133 {
00134         REQUIRE(VALID_LFSR(lfsr));
00135 
00136         while (skip--)
00137                 (void)lfsr_generate(lfsr);
00138 }
00139 
00140 /*
00141  * Skip states in lfsr1 and lfsr2 using the other's current state.
00142  * Return the final state of lfsr1 ^ lfsr2.
00143  */
00144 isc_uint32_t
00145 isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2)
00146 {
00147         isc_uint32_t state1, state2;
00148         isc_uint32_t skip1, skip2;
00149 
00150         REQUIRE(VALID_LFSR(lfsr1));
00151         REQUIRE(VALID_LFSR(lfsr2));
00152 
00153         skip1 = lfsr1->state & 0x01;
00154         skip2 = lfsr2->state & 0x01;
00155 
00156         /* cross-skip. */
00157         state1 = lfsr_skipgenerate(lfsr1, skip2);
00158         state2 = lfsr_skipgenerate(lfsr2, skip1);
00159 
00160         return (state1 ^ state2);
00161 }

Generated on Tue Apr 28 17:41:04 2015 by Doxygen 1.5.4 for BIND9 Internals 9.11.0pre-alpha