contrib/bind-9.2.4rc7/lib/isc/lfsr.c

   1 /*
   2  * Copyright (C) 2004  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2001, 2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id: lfsr.c,v 1.11.2.3 2004/03/09 06:11:47 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stdlib.h>
  23
  24 #include <isc/assertions.h>
  25 #include <isc/lfsr.h>
  26 #include <isc/util.h>
  27
  28 #define VALID_LFSR(x)   (x != NULL)
  29
  30 void
  31 isc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits,
  32               isc_uint32_t tap, unsigned int count,
  33               isc_lfsrreseed_t reseed, void *arg)
  34 {
  35         REQUIRE(VALID_LFSR(lfsr));
  36         REQUIRE(8 <= bits && bits <= 32);
  37         REQUIRE(tap != 0);
  38
  39         lfsr->state = state;
  40         lfsr->bits = bits;
  41         lfsr->tap = tap;
  42         lfsr->count = count;
  43         lfsr->reseed = reseed;
  44         lfsr->arg = arg;
  45
  46         if (count == 0 && reseed != NULL)
  47                 reseed(lfsr, arg);
  48         if (lfsr->state == 0)
  49                 lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
  50 }
  51
  52 /*
  53  * Return the next state of the lfsr.
  54  */
  55 static inline isc_uint32_t
  56 lfsr_generate(isc_lfsr_t *lfsr)
  57 {
  58         unsigned int highbit;
  59
  60         highbit = 1 << (lfsr->bits - 1);
  61
  62         /*
  63          * If the previous state is zero, we must fill it with something
  64          * here, or we will begin to generate an extremely predictable output.
  65          *
  66          * First, give the reseed function a crack at it.  If the state is
  67          * still 0, set it to all ones.
  68          */
  69         if (lfsr->state == 0) {
  70                 if (lfsr->reseed != NULL)
  71                         lfsr->reseed(lfsr, lfsr->arg);
  72                 if (lfsr->state == 0)
  73                         lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
  74         }
  75
  76         if (lfsr->state & 0x01) {
  77                 lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
  78                 return (1);
  79         } else {
  80                 lfsr->state >>= 1;
  81                 return (0);
  82         }
  83 }
  84
  85 void
  86 isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count)
  87 {
  88         unsigned char *p;
  89         unsigned int bit;
  90         unsigned int byte;
  91
  92         REQUIRE(VALID_LFSR(lfsr));
  93         REQUIRE(data != NULL);
  94         REQUIRE(count > 0);
  95
  96         p = data;
  97         byte = count;
  98
  99         while (byte--) {
 100                 *p = 0;
 101                 for (bit = 0 ; bit < 7 ; bit++) {
 102                         *p |= lfsr_generate(lfsr);
 103                         *p <<= 1;
 104                 }
 105                 *p |= lfsr_generate(lfsr);
 106                 p++;
 107         }
 108
 109         if (lfsr->count != 0 && lfsr->reseed != NULL) {
 110                 if (lfsr->count <= count * 8)
 111                         lfsr->reseed(lfsr, lfsr->arg);
 112                 else
 113                         lfsr->count -= (count * 8);
 114         }
 115 }
 116
 117 static inline isc_uint32_t
 118 lfsr_skipgenerate(isc_lfsr_t *lfsr, unsigned int skip)
 119 {
 120         while (skip--)
 121                 (void)lfsr_generate(lfsr);
 122
 123         (void)lfsr_generate(lfsr);
 124
 125         return (lfsr->state);
 126 }
 127
 128 /*
 129  * Skip "skip" states in "lfsr".
 130  */
 131 void
 132 isc_lfsr_skip(isc_lfsr_t *lfsr, unsigned int skip)
 133 {
 134         REQUIRE(VALID_LFSR(lfsr));
 135
 136         while (skip--)
 137                 (void)lfsr_generate(lfsr);
 138 }
 139
 140 /*
 141  * Skip states in lfsr1 and lfsr2 using the other's current state.
 142  * Return the final state of lfsr1 ^ lfsr2.
 143  */
 144 isc_uint32_t
 145 isc_lfsr_generate32(isc_lfsr_t *lfsr1, isc_lfsr_t *lfsr2)
 146 {
 147         isc_uint32_t state1, state2;
 148         isc_uint32_t skip1, skip2;
 149
 150         REQUIRE(VALID_LFSR(lfsr1));
 151         REQUIRE(VALID_LFSR(lfsr2));
 152
 153         skip1 = lfsr1->state & 0x01;
 154         skip2 = lfsr2->state & 0x01;
 155
 156         /* cross-skip. */
 157         state1 = lfsr_skipgenerate(lfsr1, skip2);
 158         state2 = lfsr_skipgenerate(lfsr2, skip1);
 159
 160         return (state1 ^ state2);
 161 }