New file, introduced for shuf, sort -R, and/or shred.

12 files changed, 1244 insertions, 0 deletions

diff --git a/lib/memxfrm.c b/lib/memxfrm.c
new file mode 100644
index 000000000..79db94b8f
--- /dev/null
+++ b/lib/memxfrm.c
@@ -0,0 +1,108 @@
+/* Locale-specific memory transformation
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Written by Paul Eggert <eggert@cs.ucla.edu>.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include "memxfrm.h"
+
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* Store into DEST (of size DESTSIZE) the text in SRC (of size SRCSIZE)
+   transformed so that the result of memcmp on two transformed texts
+   (with ties going to the longer text) is the same as the result of
+   memcoll on the two texts before their transformation.  Perhaps
+   temporarily modify the byte after SRC, but restore its original
+   contents before returning.
+
+   Return the size of the resulting text, or an indeterminate value if
+   there is an error.  Set errno to an error number if there is an
+   error, and to zero otherwise.  DEST contains an indeterminate value
+   if there is an error or if the resulting size is greater than
+   DESTSIZE.  */
+
+size_t
+memxfrm (char *restrict dest, size_t destsize,
+	 char *restrict src, size_t srcsize)
+{
+#if HAVE_STRXFRM
+
+  size_t di = 0;
+  size_t si = 0;
+  size_t result = 0;
+
+  char ch = src[srcsize];
+  src[srcsize] = '\0';
+
+  while (si < srcsize)
+    {
+      size_t slen = strlen (src + si);
+
+      size_t result0 = result;
+      errno = 0;
+      result += strxfrm (dest + di, src + si, destsize - di) + 1;
+      if (errno != 0)
+	break;
+      if (result <= result0)
+	{
+	  errno = ERANGE;
+	  break;
+	}
+
+      if (result == destsize + 1 && si + slen == srcsize)
+	{
+	  /* The destination is exactly the right size, but strxfrm wants
+	     room for a trailing null.  Work around the problem with a
+	     temporary buffer.  */
+	  size_t bufsize = destsize - di + 1;
+	  char stackbuf[4000];
+	  char *buf = stackbuf;
+	  if (sizeof stackbuf < bufsize)
+	    {
+	      buf = malloc (bufsize);
+	      if (! buf)
+		break;
+	    }
+	  strxfrm (buf, src + si, bufsize);
+	  memcpy (dest + di, buf, destsize - di);
+	  if (sizeof stackbuf < bufsize)
+	    free (buf);
+	  errno = 0;
+	}
+
+      di = (result < destsize ? result : destsize);
+      si += slen + 1;
+    }
+
+  src[srcsize] = ch;
+  return result - (si != srcsize);
+
+#else
+
+  if (srcsize < destsize)
+    memcpy (dest, src, srcsize);
+  errno = 0;
+  return srcsize;
+
+#endif
+}
diff --git a/lib/memxfrm.h b/lib/memxfrm.h
new file mode 100644
index 000000000..605421dc2
--- /dev/null
+++ b/lib/memxfrm.h
@@ -0,0 +1,2 @@
+#include <stddef.h>
+size_t memxfrm (char *restrict, size_t, char *restrict, size_t);
diff --git a/lib/rand-isaac.c b/lib/rand-isaac.c
new file mode 100644
index 000000000..6a0185934
--- /dev/null
+++ b/lib/rand-isaac.c
@@ -0,0 +1,300 @@
+/* Bob Jenkins's cryptographic random number generator, ISAAC.
+
+   Copyright (C) 1999-2006 Free Software Foundation, Inc.
+   Copyright (C) 1997, 1998, 1999 Colin Plumb.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+   Written by Colin Plumb.  */
+
+/*
+ * --------------------------------------------------------------------
+ * We need a source of random numbers for some data.
+ * Cryptographically secure is desirable, but it's not life-or-death
+ * so I can be a little bit experimental in the choice of RNGs here.
+ *
+ * This generator is based somewhat on RC4, but has analysis
+ * <http://burtleburtle.net/bob/rand/isaacafa.html>
+ * pointing to it actually being better.  I like it because it's nice
+ * and fast, and because the author did good work analyzing it.
+ * --------------------------------------------------------------------
+ */
+
+#include "rand-isaac.h"
+
+#include <string.h>
+#include <unistd.h>
+
+#include "gethrxtime.h"
+
+
+/* This index operation is more efficient on many processors */
+#define ind(mm, x) \
+  (* (uint32_t *) ((char *) (mm) \
+	           + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t))))
+
+/*
+ * The central step.  This uses two temporaries, x and y.  mm is the
+ * whole state array, while m is a pointer to the current word.  off is
+ * the offset from m to the word ISAAC_WORDS/2 words away in the mm array,
+ * i.e. +/- ISAAC_WORDS/2.
+ */
+#define isaac_step(mix, a, b, mm, m, off, r) \
+( \
+  a = ((a) ^ (mix)) + (m)[off], \
+  x = *(m), \
+  *(m) = y = ind (mm, x) + (a) + (b), \
+  *(r) = b = ind (mm, (y) >> ISAAC_LOG) + x \
+)
+
+/* Use and update *S to generate random data to fill R.  */
+void
+isaac_refill (struct isaac_state *s, uint32_t r[ISAAC_WORDS])
+{
+  uint32_t a, b;		/* Caches of a and b */
+  uint32_t x, y;		/* Temps needed by isaac_step macro */
+  uint32_t *m = s->mm;	/* Pointer into state array */
+
+  a = s->a;
+  b = s->b + (++s->c);
+
+  do
+    {
+      isaac_step (a << 13, a, b, s->mm, m, ISAAC_WORDS / 2, r);
+      isaac_step (a >> 6, a, b, s->mm, m + 1, ISAAC_WORDS / 2, r + 1);
+      isaac_step (a << 2, a, b, s->mm, m + 2, ISAAC_WORDS / 2, r + 2);
+      isaac_step (a >> 16, a, b, s->mm, m + 3, ISAAC_WORDS / 2, r + 3);
+      r += 4;
+    }
+  while ((m += 4) < s->mm + ISAAC_WORDS / 2);
+  do
+    {
+      isaac_step (a << 13, a, b, s->mm, m, -ISAAC_WORDS / 2, r);
+      isaac_step (a >> 6, a, b, s->mm, m + 1, -ISAAC_WORDS / 2, r + 1);
+      isaac_step (a << 2, a, b, s->mm, m + 2, -ISAAC_WORDS / 2, r + 2);
+      isaac_step (a >> 16, a, b, s->mm, m + 3, -ISAAC_WORDS / 2, r + 3);
+      r += 4;
+    }
+  while ((m += 4) < s->mm + ISAAC_WORDS);
+  s->a = a;
+  s->b = b;
+}
+
+/*
+ * The basic seed-scrambling step for initialization, based on Bob
+ * Jenkins' 256-bit hash.
+ */
+#define mix(a,b,c,d,e,f,g,h) \
+   (       a ^= b << 11, d += a, \
+   b += c, b ^= c >>  2, e += b, \
+   c += d, c ^= d <<  8, f += c, \
+   d += e, d ^= e >> 16, g += d, \
+   e += f, e ^= f << 10, h += e, \
+   f += g, f ^= g >>  4, a += f, \
+   g += h, g ^= h <<  8, b += g, \
+   h += a, h ^= a >>  9, c += h, \
+   a += b                        )
+
+/* The basic ISAAC initialization pass.  */
+static void
+isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */])
+{
+  int i;
+  uint32_t a = s->iv[0];
+  uint32_t b = s->iv[1];
+  uint32_t c = s->iv[2];
+  uint32_t d = s->iv[3];
+  uint32_t e = s->iv[4];
+  uint32_t f = s->iv[5];
+  uint32_t g = s->iv[6];
+  uint32_t h = s->iv[7];
+
+  for (i = 0; i < ISAAC_WORDS; i += 8)
+    {
+      a += seed[i];
+      b += seed[i + 1];
+      c += seed[i + 2];
+      d += seed[i + 3];
+      e += seed[i + 4];
+      f += seed[i + 5];
+      g += seed[i + 6];
+      h += seed[i + 7];
+
+      mix (a, b, c, d, e, f, g, h);
+
+      s->mm[i] = a;
+      s->mm[i + 1] = b;
+      s->mm[i + 2] = c;
+      s->mm[i + 3] = d;
+      s->mm[i + 4] = e;
+      s->mm[i + 5] = f;
+      s->mm[i + 6] = g;
+      s->mm[i + 7] = h;
+    }
+
+  s->iv[0] = a;
+  s->iv[1] = b;
+  s->iv[2] = c;
+  s->iv[3] = d;
+  s->iv[4] = e;
+  s->iv[5] = f;
+  s->iv[6] = g;
+  s->iv[7] = h;
+}
+
+#if 0 /* Provided for reference only; not used in this code */
+/*
+ * Initialize the ISAAC RNG with the given seed material.
+ * Its size MUST be a multiple of ISAAC_BYTES, and may be
+ * stored in the s->mm array.
+ *
+ * This is a generalization of the original ISAAC initialization code
+ * to support larger seed sizes.  For seed sizes of 0 and ISAAC_BYTES,
+ * it is identical.
+ */
+static void
+isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize)
+{
+  static uint32_t const iv[8] =
+  {
+    0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
+    0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119};
+  int i;
+
+# if 0
+  /* The initialization of iv is a precomputed form of: */
+  for (i = 0; i < 7; i++)
+    iv[i] = 0x9e3779b9;		/* the golden ratio */
+  for (i = 0; i < 4; ++i)	/* scramble it */
+    mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
+# endif
+  s->a = s->b = s->c = 0;
+
+  for (i = 0; i < 8; i++)
+    s->iv[i] = iv[i];
+
+  if (seedsize)
+    {
+      /* First pass (as in reference ISAAC code) */
+      isaac_mix (s, seed);
+      /* Second and subsequent passes (extension to ISAAC) */
+      while (seedsize -= ISAAC_BYTES)
+	{
+	  seed += ISAAC_WORDS;
+	  for (i = 0; i < ISAAC_WORDS; i++)
+	    s->mm[i] += seed[i];
+	  isaac_mix (s, s->mm);
+	}
+    }
+  else
+    {
+      /* The no seed case (as in reference ISAAC code) */
+      for (i = 0; i < ISAAC_WORDS; i++)
+	s->mm[i] = 0;
+    }
+
+  /* Final pass */
+  isaac_mix (s, s->mm);
+}
+#endif
+
+/* Initialize *S to a somewhat-random value.  */
+static void
+isaac_seed_start (struct isaac_state *s)
+{
+  static uint32_t const iv[8] =
+    {
+      0x1367df5a, 0x95d90059, 0xc3163e4b, 0x0f421ad8,
+      0xd92a4a78, 0xa51a3c49, 0xc4efea1b, 0x30609119
+    };
+
+#if 0
+  /* The initialization of iv is a precomputed form of: */
+  int i;
+  for (i = 0; i < 7; i++)
+    iv[i] = 0x9e3779b9;		/* the golden ratio */
+  for (i = 0; i < 4; ++i)	/* scramble it */
+    mix (iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]);
+#endif
+
+  memset (s->mm, 0, sizeof s->mm);
+  memcpy (s->iv, iv, sizeof s->iv);
+
+  /* s->c gets used for a data pointer during the seeding phase */
+  s->a = s->b = s->c = 0;
+}
+
+/* Add a buffer of seed material.  */
+static void
+isaac_seed_data (struct isaac_state *s, void const *buffer, size_t size)
+{
+  unsigned char const *buf = buffer;
+  unsigned char *p;
+  size_t avail;
+  size_t i;
+
+  avail = sizeof s->mm - s->c;	/* s->c is used as a write pointer */
+
+  /* Do any full buffers that are necessary */
+  while (size > avail)
+    {
+      p = (unsigned char *) s->mm + s->c;
+      for (i = 0; i < avail; i++)
+	p[i] ^= buf[i];
+      buf += avail;
+      size -= avail;
+      isaac_mix (s, s->mm);
+      s->c = 0;
+      avail = sizeof s->mm;
+    }
+
+  /* And the final partial block */
+  p = (unsigned char *) s->mm + s->c;
+  for (i = 0; i < size; i++)
+    p[i] ^= buf[i];
+  s->c = size;
+}
+
+
+/* End of seeding phase; get everything ready to produce output. */
+static void
+isaac_seed_finish (struct isaac_state *s)
+{
+  isaac_mix (s, s->mm);
+  isaac_mix (s, s->mm);
+  /* Now reinitialize c to start things off right */
+  s->c = 0;
+}
+#define ISAAC_SEED(s,x) isaac_seed_data (s, &(x), sizeof (x))
+
+/* Initialize *S to a somewhat-random value; this starts seeding,
+   seeds with somewhat-random data, and finishes seeding.  */
+void
+isaac_seed (struct isaac_state *s)
+{
+  isaac_seed_start (s);
+
+  { pid_t t = getpid ();   ISAAC_SEED (s, t); }
+  { pid_t t = getppid ();  ISAAC_SEED (s, t); }
+  { uid_t t = getuid ();   ISAAC_SEED (s, t); }
+  { gid_t t = getgid ();   ISAAC_SEED (s, t); }
+
+  {
+    xtime_t t = gethrxtime ();
+    ISAAC_SEED (s, t);
+  }
+
+  isaac_seed_finish (s);
+}
diff --git a/lib/rand-isaac.h b/lib/rand-isaac.h
new file mode 100644
index 000000000..f8daee03d
--- /dev/null
+++ b/lib/rand-isaac.h
@@ -0,0 +1,44 @@
+/* Bob Jenkins's cryptographic random number generator, ISAAC.
+
+   Copyright (C) 1999-2005 Free Software Foundation, Inc.
+   Copyright (C) 1997, 1998, 1999 Colin Plumb.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+
+   Written by Colin Plumb.  */
+
+#ifndef RAND_ISAAC_H
+# define RAND_ISAAC_H
+
+# include <stdint.h>
+
+/* Size of the state tables to use.  ISAAC_LOG should be at least 3,
+   and smaller values give less security.  */
+# define ISAAC_LOG 8
+# define ISAAC_WORDS (1 << ISAAC_LOG)
+# define ISAAC_BYTES (ISAAC_WORDS * sizeof (uint32_t))
+
+/* RNG state variables.  The members of this structure are private.  */
+struct isaac_state
+  {
+    uint32_t mm[ISAAC_WORDS];	/* Main state array */
+    uint32_t iv[8];		/* Seeding initial vector */
+    uint32_t a, b, c;		/* Extra index variables */
+  };
+
+void isaac_seed (struct isaac_state *);
+void isaac_refill (struct isaac_state *, uint32_t[ISAAC_WORDS]);
+
+#endif
diff --git a/lib/randint.c b/lib/randint.c
new file mode 100644
index 000000000..e461bf716
--- /dev/null
+++ b/lib/randint.c
@@ -0,0 +1,230 @@
+/* Generate random integers.
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Paul Eggert.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include "randint.h"
+
+#include <errno.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+#if TEST
+# include <inttypes.h>
+# include <stdio.h>
+
+int
+main (int argc, char **argv)
+{
+  randint i;
+  randint n = strtoumax (argv[1], NULL, 10);
+  randint choices = strtoumax (argv[2], NULL, 10);
+  char const *name = argv[3];
+  struct randint_source *ints = randint_all_new (name, SIZE_MAX);
+
+  for (i = 0; i < n; i++)
+    printf ("%"PRIuMAX"\n", randint_choose (ints, choices));
+
+  return (randint_all_free (ints) == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
+}
+#endif
+
+
+#include "xalloc.h"
+
+#ifndef MAX
+# define MAX(a,b) ((a) < (b) ? (b) : (a))
+#endif
+
+/* A source of random data for generating random integers.  */
+struct randint_source
+{
+  /* The source of random bytes.  */
+  struct randread_source *source;
+
+  /* RANDNUM is a buffered random integer, whose information has not
+     yet been delivered to the caller.  It is uniformly distributed in
+     the range 0 <= RANDNUM <= RANDMAX.  If RANDMAX is zero, then
+     RANDNUM must be zero (and in some sense it is not really
+     "random").  */
+  randint randnum;
+  randint randmax;
+};
+
+/* Create a new randint_source from SOURCE.  */
+
+struct randint_source *
+randint_new (struct randread_source *source)
+{
+  struct randint_source *s = xmalloc (sizeof *s);
+  s->source = source;
+  s->randnum = s->randmax = 0;
+  return s;
+}
+
+/* Create a new randint_source by creating a randread_source from
+   NAME and ESTIMATED_BYTES.  Return NULL (setting errno) if
+   unsuccessful.  */
+
+struct randint_source *
+randint_all_new (char const *name, size_t bytes_bound)
+{
+  struct randread_source *source = randread_new (name, bytes_bound);
+  return (source ? randint_new (source) : NULL);
+}
+
+/* Return the random data source of *S.  */
+
+struct randread_source *
+randint_get_source (struct randint_source const *s)
+{
+  return s->source;
+}
+
+/* HUGE_BYTES is true on hosts hosts where randint and unsigned char
+   have the same width and where shifting by the word size therefore
+   has undefined behavior.  */
+enum { HUGE_BYTES = RANDINT_MAX == UCHAR_MAX };
+
+/* Return X shifted left by CHAR_BIT bits.  */
+static inline randint shift_left (randint x)
+{
+  return HUGE_BYTES ? 0 : x << CHAR_BIT;
+}
+
+/* Return X shifted right by CHAR_BIT bits.  */
+static inline randint
+shift_right (randint x)
+{
+  return HUGE_BYTES ? 0 : x >> CHAR_BIT;
+}
+
+
+/* Consume random data from *S to generate a random number in the range
+   0 .. GENMAX.  */
+
+randint
+randint_genmax (struct randint_source *s, randint genmax)
+{
+  struct randread_source *source = s->source;
+  randint randnum = s->randnum;
+  randint randmax = s->randmax;
+  randint choices = genmax + 1;
+
+  for (;;)
+    {
+      if (randmax < genmax)
+	{
+	  /* Calculate how many input bytes will be needed, and read
+	     the bytes.  */
+
+	  size_t i = 0;
+	  randint rmax = randmax;
+	  unsigned char buf[sizeof randnum];
+
+	  do
+	    {
+	      rmax = shift_left (rmax) + UCHAR_MAX;
+	      i++;
+	    }
+	  while (rmax < genmax);
+
+	  randread (source, buf, i);
+
+	  /* Increase RANDMAX by appending random bytes to RANDNUM and
+	     UCHAR_MAX to RANDMAX until RANDMAX is no less than
+	     GENMAX.  This may lose up to CHAR_BIT bits of information
+	     if shift_right (RANDINT_MAX) < GENMAX, but it is not
+	     worth the programming hassle of saving these bits since
+	     GENMAX is rarely that large in practice.  */
+
+	  i = 0;
+
+	  do
+	    {
+	      randnum = shift_left (randnum) + buf[i];
+	      randmax = shift_left (randmax) + UCHAR_MAX;
+	      i++;
+	    }
+	  while (randmax < genmax);
+	}
+
+      if (randmax == genmax)
+	{
+	  s->randnum = s->randmax = 0;
+	  return randnum;
+	}
+      else
+	{
+	  /* GENMAX < RANDMAX, so attempt to generate a random number
+	     by taking RANDNUM modulo GENMAX+1.  This will choose
+	     fairly so long as RANDNUM falls within an integral
+	     multiple of GENMAX+1; otherwise, LAST_USABLE_CHOICE < RANDNUM,
+	     so discard this attempt and try again.
+
+	     Since GENMAX cannot be RANDINT_MAX, CHOICES cannot be
+	     zero and there is no need to worry about dividing by
+	     zero.  */
+
+	  randint excess_choices = randmax - genmax;
+	  randint unusable_choices = excess_choices % choices;
+	  randint last_usable_choice = randmax - unusable_choices;
+	  randint reduced_randnum = randnum % choices;
+
+	  if (randnum <= last_usable_choice)
+	    {
+	      s->randnum = randnum / choices;
+	      s->randmax = excess_choices / choices;
+	      return reduced_randnum;
+	    }
+
+	  /* Retry, but retain the randomness from the fact that RANDNUM fell
+	     into the range LAST_USABLE_CHOICE+1 .. RANDMAX.  */
+	  randnum = reduced_randnum;
+	  randmax = unusable_choices - 1;
+	}
+    }
+}
+
+/* Clear *S so that it no longer contains undelivered random data.  */
+
+void
+randint_free (struct randint_source *s)
+{
+  memset (s, 0, sizeof *s);
+  free (s);
+}
+
+/* Likewise, but also clear the underlying randread object.  Return
+   0 if successful, -1 (setting errno) otherwise.  */
+
+int
+randint_all_free (struct randint_source *s)
+{
+  int r = randread_free (s->source);
+  int e = errno;
+  randint_free (s);
+  errno = e;
+  return r;
+}
diff --git a/lib/randint.h b/lib/randint.h
new file mode 100644
index 000000000..4245a6d3f
--- /dev/null
+++ b/lib/randint.h
@@ -0,0 +1,52 @@
+/* Generate random integers.
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Paul Eggert.  */
+
+#ifndef RANDINT_H
+
+# define RANDINT_H 1
+
+# include <stdint.h>
+
+# include "randread.h"
+
+/* An unsigned integer type, used for random integers, and its maximum
+   value.  */
+typedef uintmax_t randint;
+# define RANDINT_MAX UINTMAX_MAX
+
+struct randint_source;
+
+struct randint_source *randint_new (struct randread_source *);
+struct randint_source *randint_all_new (char const *, size_t);
+struct randread_source *randint_get_source (struct randint_source const *);
+randint randint_genmax (struct randint_source *, randint genmax);
+
+/* Consume random data from *S to generate a random number in the range
+   0 .. CHOICES-1.  CHOICES must be nonzero.  */
+static inline randint
+randint_choose (struct randint_source *s, randint choices)
+{
+  return randint_genmax (s, choices - 1);
+}
+
+void randint_free (struct randint_source *);
+int randint_all_free (struct randint_source *);
+
+#endif
diff --git a/lib/randperm.c b/lib/randperm.c
new file mode 100644
index 000000000..96f049446
--- /dev/null
+++ b/lib/randperm.c
@@ -0,0 +1,105 @@
+/* Generate random permutations.
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Paul Eggert.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include "randperm.h"
+
+#include <limits.h>
+
+#include "xalloc.h"
+
+/* Return the ceiling of the log base 2 of N.  If N is zero, return
+   an unspecified value.  */
+
+static size_t
+ceil_lg (size_t n)
+{
+  size_t b = 0;
+  for (n--; n != 0; n /= 2)
+    b++;
+  return b;
+}
+
+/* Return an upper bound on the number of random bytes needed to
+   generate the first H elements of a random permutation of N
+   elements.  H must not exceed N.  */
+
+size_t
+randperm_bound (size_t h, size_t n)
+{
+  /* Upper bound on number of bits needed to generate the first number
+     of the permutation.  */
+  size_t lg_n = ceil_lg (n);
+
+  /* Upper bound on number of bits needed to generated the first H elements.  */
+  size_t ar = lg_n * h;
+
+  /* Convert the bit count to a byte count.  */
+  size_t bound = (ar + CHAR_BIT - 1) / CHAR_BIT;
+
+  return bound;
+}
+
+/* From R, allocate and return the first H elements of a random
+   permutation of N elements.  H must not exceed N.  Return NULL if H
+   is zero.  */
+
+size_t *
+randperm_new (struct randint_source *r, size_t h, size_t n)
+{
+  size_t *v;
+
+  switch (h)
+    {
+    case 0:
+      v = NULL;
+      break;
+
+    case 1:
+      v = xmalloc (sizeof *v);
+      v[0] = randint_choose (r, n);
+      break;
+
+    default:
+      {
+	size_t i;
+
+	v = xnmalloc (n, sizeof *v);
+	for (i = 0; i < n; i++)
+	  v[i] = i;
+
+	for (i = 0; i < h; i++)
+	  {
+	    size_t j = i + randint_choose (r, n - i);
+	    size_t t = v[i];
+	    v[i] = v[j];
+	    v[j] = t;
+	  }
+
+	v = xnrealloc (v, h, sizeof *v);
+      }
+      break;
+    }
+
+  return v;
+}
diff --git a/lib/randperm.h b/lib/randperm.h
new file mode 100644
index 000000000..79bbf9fe6
--- /dev/null
+++ b/lib/randperm.h
@@ -0,0 +1,4 @@
+#include "randint.h"
+#include <stddef.h>
+size_t randperm_bound (size_t, size_t);
+size_t *randperm_new (struct randint_source *, size_t, size_t);
diff --git a/lib/randread.c b/lib/randread.c
new file mode 100644
index 000000000..ff3f86900
--- /dev/null
+++ b/lib/randread.c
@@ -0,0 +1,298 @@
+/* Generate buffers of random data.
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Paul Eggert.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include "randread.h"
+
+#include <errno.h>
+#include <error.h>
+#include <exitfail.h>
+#include <quotearg.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "gettext.h"
+#define _(msgid) gettext (msgid)
+
+#include "rand-isaac.h"
+#include "stdio-safer.h"
+#include "unlocked-io.h"
+#include "xalloc.h"
+
+#ifndef MIN
+# define MIN(a, b) ((a) < (b) ? (a) : (b))
+#endif
+
+#if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+# define __attribute__(x)
+#endif
+
+#ifndef ATTRIBUTE_UNUSED
+# define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+#endif
+
+#if _STRING_ARCH_unaligned
+# define ALIGNED_POINTER(ptr, type) true
+#else
+# define alignof(type) offsetof (struct { char c; type x; }, x)
+# define ALIGNED_POINTER(ptr, type) ((size_t) (ptr) % alignof (type) == 0)
+#endif
+
+#ifndef DEFAULT_RANDOM_FILE
+# define DEFAULT_RANDOM_FILE "/dev/urandom"
+#endif
+
+/* The maximum buffer size used for reads of random data.  Using the
+   value 2 * ISAAC_BYTES makes this the largest power of two that
+   would not otherwise cause struct randread_source to grow.  */
+#define RANDREAD_BUFFER_SIZE (2 * ISAAC_BYTES)
+
+/* A source of random data for generating random buffers.  */
+struct randread_source
+{
+  /* Stream to read random bytes from.  If null, the behavior is
+     undefined; the current implementation uses ISAAC in this case,
+     but this is for old-fashioned implementations that lack
+     /dev/urandom and callers should not rely on this.  */
+  FILE *source;
+
+  /* Function to call, and its argument, if there is an input error or
+     end of file when reading from the stream; errno is nonzero if
+     there was an error.  If this function returns, it should fix the
+     problem before returning.  The default handler assumes that
+     handler_arg is the file name of the source.  */
+  void (*handler) (void *);
+  void *handler_arg;
+
+  /* The buffer for SOURCE.  It's kept here to simplify storage
+     allocation and to make it easier to clear out buffered random
+     data.  */
+  union
+  {
+    /* The stream buffer, if SOURCE is not null.  */
+    char c[RANDREAD_BUFFER_SIZE];
+
+    /* The buffered ISAAC pseudorandom buffer, if SOURCE is null.  */
+    struct isaac
+    {
+      /* The number of bytes that are buffered at the end of data.b.  */
+      size_t buffered;
+
+      /* State of the ISAAC generator.  */
+      struct isaac_state state;
+
+      /* Up to a buffer's worth of pseudorandom data.  */
+      union
+      {
+	uint32_t w[ISAAC_WORDS];
+	unsigned char b[ISAAC_BYTES];
+      } data;
+    } isaac;
+  } buf;
+};
+
+
+/* The default error handler.  */
+
+static void
+randread_error (void *file_name)
+{
+  if (file_name)
+    error (exit_failure, errno,
+	   _(errno == 0 ? "%s: end of file" : "%s: read error"),
+	   quotearg_colon (file_name));
+  abort ();
+}
+
+/* Simply return a new randread_source object with the default error
+   handler.  */
+
+static struct randread_source *
+simple_new (FILE *source, void *handler_arg)
+{
+  struct randread_source *s = xmalloc (sizeof *s);
+  s->source = source;
+  s->handler = randread_error;
+  s->handler_arg = handler_arg;
+  return s;
+}
+
+/* Create and initialize a random data source from NAME, or use a
+   reasonable default source if NAME is null.  BYTES_BOUND is an upper
+   bound on the number of bytes that will be needed.  If zero, it is a
+   hard bound; otherwise it is just an estimate.
+
+   If NAME is not null, NAME is saved for use as the argument of the
+   default handler.  Unless a non-default handler is used, NAME's
+   lifetime should be at least that of the returned value.
+
+   Return NULL (setting errno) on failure.  */
+
+struct randread_source *
+randread_new (char const *name, size_t bytes_bound)
+{
+  if (bytes_bound == 0)
+    return simple_new (NULL, NULL);
+  else
+    {
+      char const *file_name = (name ? name : DEFAULT_RANDOM_FILE);
+      FILE *source = fopen_safer (file_name, "rb");
+      struct randread_source *s;
+
+      if (! source)
+	{
+	  if (name)
+	    return NULL;
+	  file_name = NULL;
+	}
+
+      s = simple_new (source, (void *) file_name);
+
+      if (source)
+	setvbuf (source, s->buf.c, _IOFBF, MIN (sizeof s->buf.c, bytes_bound));
+      else
+	{
+	  s->buf.isaac.buffered = 0;
+	  isaac_seed (&s->buf.isaac.state);
+	}
+
+      return s;
+    }
+}
+
+
+/* Set S's handler and its argument.  HANDLER (HANDLER_ARG) is called
+   when there is a read error or end of file from the random data
+   source; errno is nonzero if there was an error.  If HANDLER
+   returns, it should fix the problem before returning.  The default
+   handler assumes that handler_arg is the file name of the source; it
+   does not return.  */
+
+void
+randread_set_handler (struct randread_source *s, void (*handler) (void *))
+{
+  s->handler = handler;
+}
+
+void
+randread_set_handler_arg (struct randread_source *s, void *handler_arg)
+{
+  s->handler_arg = handler_arg;
+}
+
+
+/* Place SIZE random bytes into the buffer beginning at P, using
+   the stream in S.  */
+
+static void
+readsource (struct randread_source *s, unsigned char *p, size_t size)
+{
+  for (;;)
+    {
+      size_t inbytes = fread (p, sizeof *p, size, s->source);
+      int fread_errno = errno;
+      p += inbytes;
+      size -= inbytes;
+      if (size == 0)
+	break;
+      errno = (ferror (s->source) ? fread_errno : 0);
+      s->handler (s->handler_arg);
+    }
+}
+
+
+/* Place SIZE pseudorandom bytes into the buffer beginning at P, using
+   the buffered ISAAC generator in ISAAC.  */
+
+static void
+readisaac (struct isaac *isaac, unsigned char *p, size_t size)
+{
+  size_t inbytes = isaac->buffered;
+
+  for (;;)
+    {
+      if (size <= inbytes)
+	{
+	  memcpy (p, isaac->data.b + ISAAC_BYTES - inbytes, size);
+	  isaac->buffered = inbytes - size;
+	  return;
+	}
+
+      memcpy (p, isaac->data.b + ISAAC_BYTES - inbytes, inbytes);
+      p += inbytes;
+      size -= inbytes;
+
+      /* If P is aligned, write to *P directly to avoid the overhead
+	 of copying from the buffer.  */
+      if (ALIGNED_POINTER (p, uint32_t))
+	{
+	  uint32_t *wp = (uint32_t *) p;
+	  while (ISAAC_BYTES <= size)
+	    {
+	      isaac_refill (&isaac->state, wp);
+	      wp += ISAAC_WORDS;
+	      size -= ISAAC_BYTES;
+	      if (size == 0)
+		{
+		  isaac->buffered = 0;
+		  return;
+		}
+	    }
+	  p = (unsigned char *) wp;
+	}
+
+      isaac_refill (&isaac->state, isaac->data.w);
+      inbytes = ISAAC_BYTES;
+    }
+}
+
+
+/* Consume random data from *S to generate a random buffer BUF of size
+   SIZE.  */
+
+void
+randread (struct randread_source *s, void *buf, size_t size)
+{
+  if (s->source)
+    readsource (s, buf, size);
+  else
+    readisaac (&s->buf.isaac, buf, size);
+}
+
+
+/* Clear *S so that it no longer contains undelivered random data, and
+   deallocate any system resources associated with *S.  Return 0 if
+   successful, a negative number (setting errno) if not (this is rare,
+   but can occur in theory if there is an input error).  */
+
+int
+randread_free (struct randread_source *s)
+{
+  FILE *source = s->source;
+  memset (s, 0, sizeof *s);
+  free (s);
+  return (source ? fclose (source) : 0);
+}
diff --git a/lib/randread.h b/lib/randread.h
new file mode 100644
index 000000000..b256386d2
--- /dev/null
+++ b/lib/randread.h
@@ -0,0 +1,34 @@
+/* Generate buffers of random data.
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
+
+/* Written by Paul Eggert.  */
+
+#ifndef RANDREAD_H
+# define RANDREAD_H 1
+
+# include <stddef.h>
+
+struct randread_source;
+
+struct randread_source *randread_new (char const *, size_t);
+void randread (struct randread_source *, void *, size_t);
+void randread_set_handler (struct randread_source *, void (*) (void *));
+void randread_set_handler_arg (struct randread_source *, void *);
+int randread_free (struct randread_source *);
+
+#endif
diff --git a/lib/xmemxfrm.c b/lib/xmemxfrm.c
new file mode 100644
index 000000000..6cc726a73
--- /dev/null
+++ b/lib/xmemxfrm.c
@@ -0,0 +1,65 @@
+/* Locale-specific memory transformation
+
+   Copyright (C) 2006 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Written by Paul Eggert <eggert@cs.ucla.edu>.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include "xmemxfrm.h"
+
+#include <errno.h>
+#include <stdlib.h>
+
+#include "gettext.h"
+#define _(msgid) gettext (msgid)
+
+#include "error.h"
+#include "exitfail.h"
+#include "memxfrm.h"
+#include "quotearg.h"
+
+/* Store into DEST (of size DESTSIZE) the text in SRC (of size
+   SRCSIZE) transformed so that the result of memcmp on two
+   transformed texts (with ties going to the longer text) is the same
+   as the result of memcoll on the two texts before their
+   transformation.  Perhaps temporarily modify the byte after SRC, but
+   restore its original contents before returning.
+
+   Return the size of the resulting text.  DEST contains an
+   indeterminate value if the resulting size is greater than DESTSIZE.
+   Report an error and exit if there is an error.  */
+
+size_t
+xmemxfrm (char *restrict dest, size_t destsize,
+	  char *restrict src, size_t srcsize)
+{
+  size_t translated_size = memxfrm (dest, destsize, src, srcsize);
+
+  if (errno)
+    {
+      error (0, errno, _("string transformation failed"));
+      error (0, 0, _("Set LC_ALL='C' to work around the problem."));
+      error (exit_failure, 0,
+	     _("The untransformed string was %s."),
+	     quotearg_n_style_mem (0, locale_quoting_style, src, srcsize));
+    }
+
+  return translated_size;
+}
diff --git a/lib/xmemxfrm.h b/lib/xmemxfrm.h
new file mode 100644
index 000000000..7c4b8ad7c
--- /dev/null
+++ b/lib/xmemxfrm.h
@@ -0,0 +1,2 @@
+#include <stddef.h>
+size_t xmemxfrm (char *restrict, size_t, char *restrict, size_t);