git.samba.org - gd/nettle/blob - knuth-lfib.c

   1 /* knuth-lfib.c
   2
   3    The "lagged fibonacci" pseudorandomness generator, described in
   4    Knuth, TAoCP, 3.6
   5
   6    Copyright (C) 2002 Niels Möller
   7
   8    This file is part of GNU Nettle.
   9
  10    GNU Nettle is free software: you can redistribute it and/or
  11    modify it under the terms of either:
  12
  13      * the GNU Lesser General Public License as published by the Free
  14        Software Foundation; either version 3 of the License, or (at your
  15        option) any later version.
  16
  17    or
  18
  19      * the GNU General Public License as published by the Free
  20        Software Foundation; either version 2 of the License, or (at your
  21        option) any later version.
  22
  23    or both in parallel, as here.
  24
  25    GNU Nettle is distributed in the hope that it will be useful,
  26    but WITHOUT ANY WARRANTY; without even the implied warranty of
  27    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28    General Public License for more details.
  29
  30    You should have received copies of the GNU General Public License and
  31    the GNU Lesser General Public License along with this program.  If
  32    not, see http://www.gnu.org/licenses/.
  33 */
  34
  35 /* This file includes code copied verbatim from Knuth's TAoCP.
  36    Technically, doing that probably requires asking for the author's
  37    explicit permission. I'd expect such a request to be granted, but I
  38    haven't asked, because I don't want to distract him from more
  39    important and interesting work. */
  40
  41
  42
  43 /* NOTE: This generator is totally inappropriate for cryptographic
  44  * applications. It is useful for generating deterministic but
  45  * random-looking test data, and is used by the Nettle testsuite. */
  46
  47 #if HAVE_CONFIG_H
  48 # include "config.h"
  49 #endif
  50
  51 #include <assert.h>
  52 #include <stdlib.h>
  53
  54 #include "knuth-lfib.h"
  55
  56 #include "macros.h"
  57
  58 #define KK _KNUTH_LFIB_KK
  59 #define LL 37
  60 #define MM (1UL << 30)
  61 #define TT 70
  62
  63 void
  64 knuth_lfib_init(struct knuth_lfib_ctx *ctx, uint32_t seed)
  65 {
  66   uint32_t t,j;
  67   uint32_t x[2*KK - 1];
  68   uint32_t ss = (seed + 2) & (MM-2);
  69
  70   for (j = 0; j<KK; j++)
  71     {
  72       x[j] = ss;
  73       ss <<= 1;  if (ss >= MM) ss -= (MM-2);
  74     }
  75   for (;j< 2*KK-1; j++)
  76     x[j] = 0;
  77
  78   x[1]++;
  79
  80   ss = seed & (MM-1);
  81   for (t = TT-1; t; )
  82     {
  83       for (j = KK-1; j>0; j--)
  84         x[j+j] = x[j];
  85       for (j = 2*KK-2; j > KK-LL; j-= 2)
  86         x[2*KK-1-j] = x[j] & ~1;
  87       for (j = 2*KK-2; j>=KK; j--)
  88         if (x[j] & 1)
  89           {
  90             x[j-(KK-LL)] = (x[j - (KK-LL)] - x[j]) & (MM-1);
  91             x[j-KK] = (x[j-KK] - x[j]) & (MM-1);
  92           }
  93       if (ss & 1)
  94         {
  95           for (j=KK; j>0; j--)
  96             x[j] = x[j-1];
  97           x[0] = x[KK];
  98           if (x[KK] & 1)
  99             x[LL] = (x[LL] - x[KK]) & (MM-1);
 100         }
 101       if (ss)
 102         ss >>= 1;
 103       else
 104         t--;
 105     }
 106   for (j=0; j<LL; j++)
 107     ctx->x[j+KK-LL] = x[j];
 108   for (; j<KK; j++)
 109     ctx->x[j-LL] = x[j];
 110
 111   ctx->index = 0;
 112 }
 113
 114 /* Get's a single number in the range 0 ... 2^30-1 */
 115 uint32_t
 116 knuth_lfib_get(struct knuth_lfib_ctx *ctx)
 117 {
 118   uint32_t value;
 119   assert(ctx->index < KK);
 120
 121   value = ctx->x[ctx->index];
 122   ctx->x[ctx->index] -= ctx->x[(ctx->index + KK - LL) % KK];
 123   ctx->x[ctx->index] &= (MM-1);
 124
 125   ctx->index = (ctx->index + 1) % KK;
 126
 127   return value;
 128 }
 129
 130 /* NOTE: Not at all optimized. */
 131 void
 132 knuth_lfib_get_array(struct knuth_lfib_ctx *ctx,
 133                      size_t n, uint32_t *a)
 134 {
 135   unsigned i;
 136
 137   for (i = 0; i<n; i++)
 138     a[i] = knuth_lfib_get(ctx);
 139 }
 140
 141 /* NOTE: Not at all optimized. */
 142 void
 143 knuth_lfib_random(struct knuth_lfib_ctx *ctx,
 144                   size_t n, uint8_t *dst)
 145 {
 146   /* Use 24 bits from each number, xoring together some of the
 147      bits. */
 148
 149   for (; n >= 3; n-=3, dst += 3)
 150     {
 151       uint32_t value = knuth_lfib_get(ctx);
 152
 153       /* Xor the most significant octet (containing 6 significant bits)
 154        * into the lower octet. */
 155       value ^= (value >> 24);
 156
 157       WRITE_UINT24(dst, value);
 158     }
 159   if (n)
 160     {
 161       /* We need one or two octets more */
 162       uint32_t value = knuth_lfib_get(ctx);
 163       switch (n)
 164         {
 165         case 1:
 166           *dst++ = value & 0xff;
 167           break;
 168         case 2:
 169           WRITE_UINT16(dst, value);
 170           break;
 171         default:
 172           abort();
 173         }
 174     }
 175 }