contrib/bind-9.3/lib/isc/lfsr.c

   1 /*
   2  * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2002  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.2.2.6 2005/10/14 01:38:50 marka Exp $ */
  19
  20 #include <config.h>
  21
  22 #include <stddef.h>
  23 #include <stdlib.h>
  24
  25 #include <isc/assertions.h>
  26 #include <isc/lfsr.h>
  27 #include <isc/util.h>
  28
  29 #define VALID_LFSR(x)   (x != NULL)
  30
  31 void
  32 isc_lfsr_init(isc_lfsr_t *lfsr, isc_uint32_t state, unsigned int bits,
  33               isc_uint32_t tap, unsigned int count,
  34               isc_lfsrreseed_t reseed, void *arg)
  35 {
  36         REQUIRE(VALID_LFSR(lfsr));
  37         REQUIRE(8 <= bits && bits <= 32);
  38         REQUIRE(tap != 0);
  39
  40         lfsr->state = state;
  41         lfsr->bits = bits;
  42         lfsr->tap = tap;
  43         lfsr->count = count;
  44         lfsr->reseed = reseed;
  45         lfsr->arg = arg;
  46
  47         if (count == 0 && reseed != NULL)
  48                 reseed(lfsr, arg);
  49         if (lfsr->state == 0)
  50                 lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
  51 }
  52
  53 /*
  54  * Return the next state of the lfsr.
  55  */
  56 static inline isc_uint32_t
  57 lfsr_generate(isc_lfsr_t *lfsr)
  58 {
  59
  60         /*
  61          * If the previous state is zero, we must fill it with something
  62          * here, or we will begin to generate an extremely predictable output.
  63          *
  64          * First, give the reseed function a crack at it.  If the state is
  65          * still 0, set it to all ones.
  66          */
  67         if (lfsr->state == 0) {
  68                 if (lfsr->reseed != NULL)
  69                         lfsr->reseed(lfsr, lfsr->arg);
  70                 if (lfsr->state == 0)
  71                         lfsr->state = 0xffffffffU >> (32 - lfsr->bits);
  72         }
  73
  74         if (lfsr->state & 0x01) {
  75                 lfsr->state = (lfsr->state >> 1) ^ lfsr->tap;
  76                 return (1);
  77         } else {
  78                 lfsr->state >>= 1;
  79                 return (0);
  80         }
  81 }
  82
  83 void
  84 isc_lfsr_generate(isc_lfsr_t *lfsr, void *data, unsigned int count)
  85 {
  86         unsigned char *p;
  87         unsigned int bit;
  88         unsigned int byte;
  89
  90         REQUIRE(VALID_LFSR(lfsr));
  91         REQUIRE(data != NULL);
  92         REQUIRE(count > 0);
  93
  94         p = data;
  95         byte = count;
  96
  97         while (byte--) {
  98                 *p = 0;
  99                 for (bit = 0; bit < 7; bit++) {
 100                         *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
 115 static inline isc_uint32_t
 116 lfsr_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  */
 129 void
 130 isc_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  */
 142 isc_uint32_t
 143 isc_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 }