knuth-lfib.c

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