knuth-lfib.c

/* knuth-lfib.c
 *
 * A "lagged fibonacci" pseudorandomness generator.
 *
 * Described in Knuth, TAOCP, 3.6
 */

/* nettle, low-level cryptographics library
 *
 * Copyright (C) 2002 Niels Mller
 *
 * Includes code copied verbatim from Knuth's TAOCP.
 *  
 * The nettle library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 * 
 * The nettle library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 * License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/* NOTE: This generator is totally inappropriate for cryptographic
 * applications. It is useful for generating deterministic but
 * random-looking test data, and is used by the Nettle testsuite. */

#if HAVE_CONFIG_H
# include "config.h"
#endif

#include <assert.h>
#include <stdlib.h>

#include "knuth-lfib.h"

#include "macros.h"

#define KK _KNUTH_LFIB_KK
#define LL 37
#define MM (1UL << 30)
#define TT 70

void
knuth_lfib_init(struct knuth_lfib_ctx *ctx, uint32_t seed)
{
  uint32_t t,j;
  uint32_t x[2*KK - 1];
  uint32_t ss = (seed + 2) & (MM-2);

  for (j = 0; j<KK; j++)
    {
      x[j] = ss;
      ss <<= 1;  if (ss >= MM) ss -= (MM-2);
    }
  for (;j< 2*KK-1; j++)
    x[j] = 0;

  x[1]++;

  ss = seed & (MM-1);
  for (t = TT-1; t; )
    {
      for (j = KK-1; j>0; j--)