[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
random number patch: 'sort -R' fixes for non-C locales; new cmd 'shuf'
|
From: |
Paul Eggert |
|
Subject: |
random number patch: 'sort -R' fixes for non-C locales; new cmd 'shuf' |
|
Date: |
Tue, 08 Aug 2006 15:38:26 -0700 |
|
User-agent: |
Gnus/5.1008 (Gnus v5.10.8) Emacs/21.4 (gnu/linux) |
I installed this long-promised patch to fix 'sort -R' so that it works
for non-C locales where strcoll can return 0 even when strcmp does
not, and avoids the (we hope mostly theoretical) problem of collisions
in the hash function; and to add a new command 'shuf' that generates
random permutations of its input (as opposed to 'sort -R', which keeps
duplicates together).
Apologies for the length of this patch, but it is a bit tricky to
split this up into multiple patches, and to some extent it is all the
same subject anyway.
2006-08-08 Paul Eggert <address@hidden>
Add a command 'shuf', and modify shred and sort to use the new
random number generator library of 'shuf'.
* AUTHORS: Add shuf.
* README: Likewise.
* NEWS: Likewise. Mention new --random-source option for shred
and sort. Move "sort +1 -2" notice to the appropriate section,
and clarify its role with respect to POSIXLY_CORRECT.
* doc/coreutils.texi (shuf invocation, Random sources): New sections.
(Operating on sorted files): Add shuf.
(sort invocation, shred invocation): New option --random-source.
(sort invocation): Fix typo: -R -> -r.
* lib/Makefile.am (libcoreutils_a_SOURCES): Add xmemxfrm.c, xmemxfrm.h.
* lib/memxfrm.c, lib/memxfrm.h, lib/randint.c, lib/randint.h:
* lib/randperm.c, lib/randperm.h, lib/randread.c, lib/randread.h:
* lib/xmemxfrm.c, lib/xmemxfrm.h: New files.
* lib/rand-isaac.h: New file.
* lib/rand-isaac.c: New file, mostly taken from ../src/rand-isaac.c.
* m4/memxfrm.m4, m4/randint.m4, m4/randperm.m4, m4/randread.m4:
New files.
* m4/prereq.m4 (gl_PREREQ): Require gl_MEMXFRM, gl_RANDINT, gl_RANDPERM,
gl_RANDREAD.
* m4/restrict.m4: Remove, since we no longer need gl_RESTRICT.
* m4/getaddrinfo.m4 (gl_PREREQ_GETADDRINFO): Use AC_C_RESTRICT, not
gl_C_RESTRICT, since we assume recent Autoconf.
* m4/regex.m4 (gl_PREREQ_REGEX): Likewise.
* m4/time_r.m4 (gl_TIME_R): Likewise.
* man/.cvsignore: Add shuf.1.
* man/Makefile.am (dist_man_MANS): Add shuf.1.
(shuf.1): New dependency.
* man/shuf.x: New file.
* src/Makefile.am (bin_PROGRAMS): Add shuf.
(EXTRA_DIST): Remove rand-isaac.c.
(shuf_LDADD): New macro.
* src/rand-isaac.c: Remove, moving most of its contents to
lib/rand-isaac.c.
* src/shuf.c: New file.
* src/shred.c: Use new random-number interface rather than rand-isaac.c.
Don't include rand-isaac.c; include randint.h and randread.h instead.
(RANDOM_SOURCE_OPTION): New enum.
(long_opts, usage, main): New option --random-source.
* src/sort.c: Likewise.
* src/shred.c (struct irand_state, irand_init, irand32, irand_mod):
Remove.
All callers changed to use randint interface.
(fillrand): Remove. All callers changed to use randread interface.
(dopass): Remove dependency on ISAAC buffer size.
(genpattern): Don't wipe the random state here.
(randint_source): New static var.
(clear_random_data): New function.
(main): Allocate random source, and arrange to wipe it on exit.
* src/sort.c: Include md5.h, randread.h, xmemxfrm.h.
(longopts, usage, main): Remove undocumented --seed option;
it's now replaced by --random-source.
(rand_state, get_hash): Remove.
(randread_source): New static var.
(random_state, cmp_hashes, compare_random): New functions; they
guarantee
no collisions in the random hash function.
(keycompare): Use compare_random for -R; don't fall back on comparing
via memcoll, since compare_random does the right thing.
* tests/misc/Makefile.am (TESTS): Add shuf.
* tests/misc/shuf: New file.
Index: AUTHORS
===================================================================
RCS file: /fetish/cu/AUTHORS,v
retrieving revision 1.9
diff -p -u -r1.9 AUTHORS
--- AUTHORS 27 Feb 2006 10:48:04 -0000 1.9
+++ AUTHORS 8 Aug 2006 22:08:33 -0000
@@ -67,6 +67,7 @@ sha256sum: Ulrich Drepper, Scott Miller,
sha384sum: Ulrich Drepper, Scott Miller, David Madore
sha512sum: Ulrich Drepper, Scott Miller, David Madore
shred: Colin Plumb
+shuf: Paul Eggert
sleep: Jim Meyering, Paul Eggert
sort: Mike Haertel, Paul Eggert
split: Torbjorn Granlund, Richard M. Stallman
Index: NEWS
===================================================================
RCS file: /fetish/cu/NEWS,v
retrieving revision 1.396
diff -p -u -r1.396 NEWS
--- NEWS 28 Jul 2006 07:27:56 -0000 1.396
+++ NEWS 8 Aug 2006 22:08:34 -0000
@@ -114,10 +114,6 @@ GNU coreutils NEWS
sort now reports incompatible options (e.g., -i and -n) rather than
silently ignoring one of them.
- sort now supports obsolete usages like "sort +1 -2" when conforming
- to POSIX 1003.1-2001, since this is a pure extension to POSIX.
- However, "sort +1" still sorts the file named "+1".
-
stat's --format=FMT option now works the way it did before 5.3.0:
FMT is automatically newline terminated. The first stable release
containing this change was 5.92.
@@ -158,6 +154,7 @@ GNU coreutils NEWS
sha256sum: print or check a SHA256 (256-bit) checksum
sha384sum: print or check a SHA384 (384-bit) checksum
sha512sum: print or check a SHA512 (512-bit) checksum
+ shuf: Shuffle lines of text.
** New features
@@ -186,8 +183,14 @@ GNU coreutils NEWS
for every file, but provides almost the same level of protection
against mistakes.
+ shred and sort now accept the --random-source option.
+
sort now accepts the --random-sort (-R) option and `R' ordering option.
+ sort now supports obsolete usages like "sort +1 -2" unless
+ POSIXLY_CORRECT is set. However, when conforming to POSIX
+ 1003.1-2001 "sort +1" still sorts the file named "+1".
+
wc accepts a new option --files0-from=FILE, where FILE contains a
list of NUL-terminated file names.
Index: README
===================================================================
RCS file: /fetish/cu/README,v
retrieving revision 1.25
diff -p -u -r1.25 README
--- README 9 Jul 2006 09:47:20 -0000 1.25
+++ README 8 Aug 2006 22:08:34 -0000
@@ -12,9 +12,9 @@ The programs that can be built with this
ginstall groups head hostid hostname id join kill link ln logname ls
md5sum mkdir mkfifo mknod mv nice nl nohup od paste pathchk pinky pr
printenv printf ptx pwd readlink rm rmdir seq sha1sum sha224sum sha256sum
- sha384sum sha512sum shred sleep sort split stat stty su sum sync tac tail
- tee test touch tr true tsort tty uname unexpand uniq unlink uptime users
- vdir wc who whoami yes
+ sha384sum sha512sum shred shuf sleep sort split stat stty su sum sync tac
+ tail tee test touch tr true tsort tty uname unexpand uniq unlink uptime
+ users vdir wc who whoami yes
See the file NEWS for a list of major changes in the current release.
Index: doc/coreutils.texi
===================================================================
RCS file: /fetish/cu/doc/coreutils.texi,v
retrieving revision 1.343
diff -p -u -r1.343 coreutils.texi
--- doc/coreutils.texi 28 Jul 2006 07:20:28 -0000 1.343
+++ doc/coreutils.texi 8 Aug 2006 22:08:37 -0000
@@ -97,6 +97,7 @@
* sha1sum: (coreutils)sha1sum invocation. Print or check SHA-1 digests.
* sha2: (coreutils)sha2 utilities. Print or check SHA-2 digests.
* shred: (coreutils)shred invocation. Remove files more securely.
+* shuf: (coreutils)shuf invocation. Shuffling text files.
* sleep: (coreutils)sleep invocation. Delay for a specified time.
* sort: (coreutils)sort invocation. Sort text files.
* split: (coreutils)split invocation. Split into fixed-size pieces.
@@ -174,7 +175,7 @@ Free Documentation License''.
* Formatting file contents:: fmt pr fold
* Output of parts of files:: head tail split csplit
* Summarizing files:: wc sum cksum md5sum sha1sum sha2
-* Operating on sorted files:: sort uniq comm ptx tsort
+* Operating on sorted files:: sort shuf uniq comm ptx tsort
* Operating on fields within a line:: cut paste join
* Operating on characters:: tr expand unexpand
* Directory listing:: ls dir vdir dircolors
@@ -207,6 +208,7 @@ Common Options
* Exit status:: Indicating program success or failure.
* Backup options:: Backup options
* Block size:: Block size
+* Random sources:: Sources of random data
* Target directory:: Target directory
* Trailing slashes:: Trailing slashes
* Traversing symlinks:: Traversing symlinks to directories
@@ -246,6 +248,7 @@ Summarizing files
Operating on sorted files
* sort invocation:: Sort text files.
+* shuf invocation:: Shuffle text files.
* uniq invocation:: Uniquify files.
* comm invocation:: Compare two sorted files line by line.
* ptx invocation:: Produce a permuted index of file contents.
@@ -641,6 +644,7 @@ name.
* Exit status:: Indicating program success or failure.
* Backup options:: -b -S, in some programs.
* Block size:: BLOCK_SIZE and --block-size, in some programs.
+* Random sources:: --random-source, in some programs.
* Target directory:: Specifying a target directory, in some
programs.
* Trailing slashes:: --strip-trailing-slashes, in some programs.
* Traversing symlinks:: -H, -L, or -P, in some programs.
@@ -920,6 +924,44 @@ set. The @option{-h} or @option{--human
@option{--block-size=human-readable}. The @option{--si} option is
equivalent to @option{--block-size=si}.
address@hidden Random sources
address@hidden Sources of random data
+
address@hidden random sources
+
+The @command{shuf}, @command{shred}, and @command{sort} commands
+sometimes need random data to do their work. For example, @samp{sort
+-R} must choose a hash function at random, and it needs random data to
+make this selection.
+
+Normally these commands use the device file @file{/dev/urandom} as the
+source of random data. Typically, this device gathers environmental
+noise from device drivers and other sources into an entropy pool, and
+uses the pool to generate random bits. If the pool is short of data,
+the device reuses the internal pool to produce more bits, using a
+cryptographically secure pseudorandom number generator.
+
address@hidden/dev/urandom} suffices for most practical uses, but applications
+requiring high-value or long-term protection of private data may
+require an alternate data source like @file{/dev/random} or
address@hidden/dev/arandom}. The set of available sources depends on your
+operating system.
+
+To use such a source, specify the @address@hidden
+option, e.g., @samp{shuf --random-source=/dev/random}. The contents
+of @var{file} should be as random as possible. An error is reported
+if @var{file} does not contain enough bytes to randomize the input
+adequately.
+
+To reproduce the results of an earlier invocation of a command, you
+can save some random data into a file and then use that file as the
+random source in earlier and later invocations of the command.
+
+Some old-fashioned or stripped-down operating systems lack support for
address@hidden/dev/urandom}. On these systems commands like @command{shuf}
+by default fall back on an internal pseudorandom generator initialized
+by a small amount of entropy.
+
@node Target directory
@section Target directory
@@ -3262,6 +3304,7 @@ These commands work with (or produce) so
@menu
* sort invocation:: Sort text files.
+* shuf invocation:: Shuffle text files.
* uniq invocation:: Uniquify files.
* comm invocation:: Compare two sorted files line by line.
* ptx invocation:: Produce a permuted index of file contents.
@@ -3509,9 +3552,19 @@ appear earlier in the output instead of
@opindex -R
@opindex --random-sort
@cindex random sort
-Sort by hashing the input keys and then sorting the hash values. This
-is much like a random shuffle of the inputs, except that keys with the
-same value sort together. The hash function is chosen at random.
+Sort by hashing the input keys and then sorting the hash values.
+Choose the hash function at random, ensuring that it is free of
+collisions so that differing keys have differing hash values. This is
+like a random permutation of the inputs (@pxref{shuf invocation}),
+except that keys with the same value sort together.
+
+If multiple random sort fields are specified, the same random hash
+function is used for all fields. To use different random hash
+functions for different fields, you can invoke @command{sort} more
+than once.
+
+The choice of hash function is affected by the
address@hidden option.
@end table
@@ -3550,6 +3603,13 @@ On newer systems, @option{-o} cannot app
scripts should specify @option{-o @var{output-file}} before any input
files.
address@hidden address@hidden
address@hidden --random-source
address@hidden random source for sorting
+Use @var{file} as a source of random data used to determine which
+random hash function to use with the @option{-R} option. @xref{Random
+sources}.
+
@item -s
@itemx --stable
@opindex -s
@@ -3559,7 +3619,7 @@ files.
Make @command{sort} stable by disabling its last-resort comparison.
This option has no effect if no fields or global ordering options
-other than @option{--reverse} (@option{-R}) are specified.
+other than @option{--reverse} (@option{-r}) are specified.
@item -S @var{size}
@itemx address@hidden
@@ -3835,6 +3895,147 @@ ls */* | sort -t / -k 1,1R -k 2,2
@end itemize
address@hidden shuf invocation
address@hidden @command{shuf}: Shuffling text
+
address@hidden shuf
address@hidden shuffling files
+
address@hidden shuffles its input by outputting a random permutation
+of its input lines. Each output permutation is equally likely.
+Synopses:
+
address@hidden
+shuf address@hidden@dots{} address@hidden
+shuf -e address@hidden@dots{} address@hidden@dots{}
+shuf -i @address@hidden address@hidden@dots{}
address@hidden example
+
address@hidden has three modes of operation that affect where it
+obtains its input lines. By default, it reads lines from standard
+input. The following options change the operation mode:
+
address@hidden @samp
+
address@hidden -e
address@hidden --echo
address@hidden -c
address@hidden --echo
address@hidden command-line operands to shuffle
+Treat each command-line operand as an input line.
+
address@hidden -i @address@hidden
address@hidden address@hidden@var{hi}
address@hidden -i
address@hidden --input-range
address@hidden input range to shuffle
+Act as if input came from a file containing the range of unsigned
+decimal integers @address@hidden@var{hi}, one per line.
+
address@hidden table
+
address@hidden's other options can affect its behavior in all
+operation modes:
+
address@hidden @samp
+
address@hidden -n @var{lines}
address@hidden address@hidden
address@hidden -n
address@hidden --head-lines
address@hidden head of output
+Output at most @var{lines} lines. By default, all input lines are
+output.
+
address@hidden -o @var{output-file}
address@hidden address@hidden
address@hidden -o
address@hidden --output
address@hidden overwriting of input, allowed
+Write output to @var{output-file} instead of standard output.
address@hidden reads all input before opening
address@hidden, so you can safely shuffle a file in place by using
+commands like @code{shuf -o F <F} and @code{cat F | shuf -o F}.
+
address@hidden address@hidden
address@hidden --random-source
address@hidden random source for shuffling
+Use @var{file} as a source of random data used to determine which
+permutation to generate. @xref{Random sources}.
+
address@hidden -z
address@hidden --zero-terminated
address@hidden -z
address@hidden --zero-terminated
address@hidden sort zero-terminated lines
+Treat the input and output as a set of lines, each terminated by a zero byte
+(@acronym{ASCII} @sc{nul} (Null) character) instead of an
address@hidden @sc{lf} (Line Feed).
+This option can be useful in conjunction with @samp{perl -0} or
address@hidden -print0} and @samp{xargs -0} which do the same in order to
+reliably handle arbitrary file names (even those containing blanks
+or other special characters).
+
address@hidden table
+
+For example:
+
address@hidden
+shuf <<EOF
+A man,
+a plan,
+a canal:
+Panama!
+EOF
address@hidden example
+
address@hidden
+might produce the output
+
address@hidden
+Panama!
+A man,
+a canal:
+a plan,
address@hidden example
+
address@hidden
+Similarly, the command:
+
address@hidden
+shuf -e clubs hearts diamonds spades
address@hidden example
+
address@hidden
+might output:
+
address@hidden
+clubs
+diamonds
+spades
+hearts
address@hidden example
+
address@hidden
+and the command @samp{shuf -i 1-4} might output:
+
address@hidden
+4
+2
+1
+3
address@hidden example
+
address@hidden
+These examples all have four input lines, so @command{shuf} might
+produce any of the twenty-four possible permutations of the input. In
+general, if there are @var{N} input lines, there are @var{N}! (i.e.,
address@hidden factorial, or @var{N} * (@var{N} - 1) * @dots{} * 1) possible
+output permutations.
+
address@hidden
+
+
@node uniq invocation
@section @command{uniq}: Uniquify files
@@ -7746,6 +7947,12 @@ for all of the useful overwrite patterns
You can reduce this to save time, or increase it if you have a lot of
time to waste.
address@hidden address@hidden
address@hidden --random-source
address@hidden random source for shredding
+Use @var{file} as a source of random data used to overwrite and to
+choose pass ordering. @xref{Random sources}.
+
@item -s @var{BYTES}
@itemx address@hidden
@opindex -s @var{BYTES}
Index: lib/Makefile.am
===================================================================
RCS file: /fetish/cu/lib/Makefile.am,v
retrieving revision 1.247
diff -p -u -r1.247 Makefile.am
--- lib/Makefile.am 9 Jul 2006 16:57:35 -0000 1.247
+++ lib/Makefile.am 8 Aug 2006 22:08:37 -0000
@@ -52,6 +52,7 @@ libcoreutils_a_SOURCES = \
xalloc-die.c \
xgethostname.c xgethostname.h \
xmemcoll.c xmemcoll.h \
+ xmemxfrm.c xmemxfrm.h \
xstrndup.c xstrndup.h \
xstrtoimax.c \
xstrtoumax.c
Index: m4/getaddrinfo.m4
===================================================================
RCS file: /fetish/cu/m4/getaddrinfo.m4,v
retrieving revision 1.13
diff -p -u -r1.13 getaddrinfo.m4
--- m4/getaddrinfo.m4 4 Jul 2006 05:39:08 -0000 1.13
+++ m4/getaddrinfo.m4 8 Aug 2006 22:08:37 -0000
@@ -1,4 +1,4 @@
-# getaddrinfo.m4 serial 10
+# getaddrinfo.m4 serial 11
dnl Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
dnl This file is free software; the Free Software Foundation
dnl gives unlimited permission to copy and/or distribute it,
@@ -52,7 +52,7 @@ AC_DEFUN([gl_PREREQ_GETADDRINFO], [
LIBS="$LIBS -lws2_32"
fi
])
- AC_REQUIRE([gl_C_RESTRICT])
+ AC_REQUIRE([AC_C_RESTRICT])
AC_REQUIRE([gl_SOCKET_FAMILIES])
AC_REQUIRE([gl_HEADER_SYS_SOCKET])
AC_REQUIRE([AC_C_INLINE])
Index: m4/prereq.m4
===================================================================
RCS file: /fetish/cu/m4/prereq.m4,v
retrieving revision 1.128
diff -p -u -r1.128 prereq.m4
--- m4/prereq.m4 22 Jul 2006 22:23:43 -0000 1.128
+++ m4/prereq.m4 8 Aug 2006 22:08:37 -0000
@@ -1,4 +1,4 @@
-#serial 68
+#serial 69
dnl We use gl_ for non Autoconf macros.
m4_pattern_forbid([^gl_[ABCDEFGHIJKLMNOPQRSTUVXYZ]])dnl
@@ -118,6 +118,7 @@ AC_DEFUN([gl_PREREQ],
AC_REQUIRE([gl_MBSWIDTH])
AC_REQUIRE([gl_MD5])
AC_REQUIRE([gl_MEMCOLL])
+ AC_REQUIRE([gl_MEMXFRM])
AC_REQUIRE([gl_MKANCESDIRS])
AC_REQUIRE([gl_MKDIR_PARENTS])
AC_REQUIRE([gl_MODECHANGE])
@@ -129,6 +130,9 @@ AC_DEFUN([gl_PREREQ],
AC_REQUIRE([gl_POSIXVER])
AC_REQUIRE([gl_QUOTEARG])
AC_REQUIRE([gl_QUOTE])
+ AC_REQUIRE([gl_RANDINT])
+ AC_REQUIRE([gl_RANDPERM])
+ AC_REQUIRE([gl_RANDREAD])
AC_REQUIRE([gl_READTOKENS])
AC_REQUIRE([gl_READUTMP])
AC_REQUIRE([gl_REGEX])
Index: m4/regex.m4
===================================================================
RCS file: /fetish/cu/m4/regex.m4,v
retrieving revision 1.49
diff -p -u -r1.49 regex.m4
--- m4/regex.m4 9 Jul 2006 16:59:35 -0000 1.49
+++ m4/regex.m4 8 Aug 2006 22:08:37 -0000
@@ -1,4 +1,4 @@
-#serial 37
+#serial 38
# Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
# 2006 Free Software Foundation, Inc.
@@ -163,7 +163,7 @@ AC_DEFUN([gl_REGEX],
AC_DEFUN([gl_PREREQ_REGEX],
[
AC_REQUIRE([AC_GNU_SOURCE])
- AC_REQUIRE([gl_C_RESTRICT])
+ AC_REQUIRE([AC_C_RESTRICT])
AC_REQUIRE([AM_LANGINFO_CODESET])
AC_CHECK_HEADERS_ONCE([locale.h wchar.h wctype.h])
AC_CHECK_FUNCS_ONCE([mbrtowc mempcpy wcrtomb wcscoll])
Index: m4/time_r.m4
===================================================================
RCS file: /fetish/cu/m4/time_r.m4,v
retrieving revision 1.2
diff -p -u -r1.2 time_r.m4
--- m4/time_r.m4 12 Apr 2006 07:11:52 -0000 1.2
+++ m4/time_r.m4 8 Aug 2006 22:08:37 -0000
@@ -11,7 +11,7 @@ AC_DEFUN([gl_TIME_R],
[
AC_LIBSOURCES([time_r.c, time_r.h])
AC_REQUIRE([gl_USE_SYSTEM_EXTENSIONS])
- AC_REQUIRE([gl_C_RESTRICT])
+ AC_REQUIRE([AC_C_RESTRICT])
AC_CACHE_CHECK([whether localtime_r is compatible with its POSIX signature],
[gl_cv_time_r_posix],
Index: man/.cvsignore
===================================================================
RCS file: /fetish/cu/man/.cvsignore,v
retrieving revision 1.6
diff -p -u -r1.6 .cvsignore
--- man/.cvsignore 27 Feb 2006 11:03:31 -0000 1.6
+++ man/.cvsignore 8 Aug 2006 22:08:37 -0000
@@ -65,6 +65,7 @@ sha256sum.1
sha384sum.1
sha512sum.1
shred.1
+shuf.1
sleep.1
sort.1
split.1
Index: man/Makefile.am
===================================================================
RCS file: /fetish/cu/man/Makefile.am,v
retrieving revision 1.41
diff -p -u -r1.41 Makefile.am
--- man/Makefile.am 27 Feb 2006 10:53:49 -0000 1.41
+++ man/Makefile.am 8 Aug 2006 22:08:37 -0000
@@ -8,7 +8,7 @@ dist_man_MANS = \
ls.1 md5sum.1 mkdir.1 mkfifo.1 mknod.1 mv.1 nice.1 nl.1 nohup.1 od.1 \
paste.1 pathchk.1 pinky.1 pr.1 printenv.1 printf.1 ptx.1 pwd.1 readlink.1 \
rm.1 rmdir.1 seq.1 sha1sum.1 sha224sum.1 sha256sum.1 sha384sum.1 sha512sum.1
\
- shred.1 sleep.1 sort.1 split.1 stat.1 stty.1 \
+ shred.1 shuf.1 sleep.1 sort.1 split.1 stat.1 stty.1 \
su.1 sum.1 sync.1 tac.1 tail.1 tee.1 test.1 touch.1 tr.1 true.1 tsort.1 \
tty.1 uname.1 unexpand.1 uniq.1 unlink.1 uptime.1 users.1 vdir.1 wc.1 \
who.1 whoami.1 yes.1
@@ -90,6 +90,7 @@ sha256sum.1: $(common_dep) $(srcdir)/sha
sha384sum.1: $(common_dep) $(srcdir)/sha384sum.x ../src/md5sum.c
sha512sum.1: $(common_dep) $(srcdir)/sha512sum.x ../src/md5sum.c
shred.1: $(common_dep) $(srcdir)/shred.x ../src/shred.c
+shuf.1: $(common_dep) $(srcdir)/shuf.x ../src/shuf.c
sleep.1: $(common_dep) $(srcdir)/sleep.x ../src/sleep.c
sort.1: $(common_dep) $(srcdir)/sort.x ../src/sort.c
split.1: $(common_dep) $(srcdir)/split.x ../src/split.c
Index: src/Makefile.am
===================================================================
RCS file: /fetish/cu/src/Makefile.am,v
retrieving revision 1.70
diff -p -u -r1.70 Makefile.am
--- src/Makefile.am 1 Jul 2006 00:07:26 -0000 1.70
+++ src/Makefile.am 8 Aug 2006 22:08:37 -0000
@@ -25,7 +25,7 @@ bin_PROGRAMS = [ chgrp chown chmod cp dd
mkfifo mknod mv nohup readlink rm rmdir shred stat sync touch unlink \
cat cksum comm csplit cut expand fmt fold head join md5sum \
nl od paste pr ptx sha1sum sha224sum sha256sum sha384sum sha512sum \
- sort split sum tac tail tr tsort unexpand uniq wc \
+ shuf sort split sum tac tail tr tsort unexpand uniq wc \
basename date dirname echo env expr factor false \
hostname id kill logname pathchk printenv printf pwd seq sleep tee \
test true tty whoami yes \
@@ -46,7 +46,7 @@ noinst_HEADERS = \
wheel-size.h \
wheel.h
-EXTRA_DIST = dcgen dircolors.hin rand-isaac.c tac-pipe.c \
+EXTRA_DIST = dcgen dircolors.hin tac-pipe.c \
groups.sh wheel-gen.pl extract-magic c99-to-c89.diff
CLEANFILES = $(SCRIPTS) su
@@ -75,6 +75,7 @@ dir_LDADD = $(LDADD) $(LIB_CLOCK_GETTIME
ls_LDADD = $(LDADD) $(LIB_CLOCK_GETTIME)
pr_LDADD = $(LDADD) $(LIB_CLOCK_GETTIME)
shred_LDADD = $(LDADD) $(LIB_GETHRXTIME) $(LIB_FDATASYNC)
+shuf_LDADD = $(LDADD) $(LIB_GETHRXTIME)
vdir_LDADD = $(LDADD) $(LIB_CLOCK_GETTIME)
## If necessary, add -lm to resolve use of pow in lib/strtod.c.
Index: src/shred.c
===================================================================
RCS file: /fetish/cu/src/shred.c,v
retrieving revision 1.124
diff -p -u -r1.124 shred.c
--- src/shred.c 19 Apr 2006 06:27:43 -0000 1.124
+++ src/shred.c 8 Aug 2006 22:08:38 -0000
@@ -60,9 +60,6 @@
* If asked to wipe a file, this also unlinks it, renaming it to in a
* clever way to try to leave no trace of the original filename.
*
- * The ISAAC code still bears some resemblance to the code written
- * by Bob Jenkins, but he permits pretty unlimited use.
- *
* This was inspired by a desire to improve on some code titled:
* Wipe V1.0-- Overwrite and delete files. S. 2/3/96
* but I've rewritten everything here so completely that no trace of
@@ -108,8 +105,8 @@
#include "inttostr.h"
#include "quotearg.h" /* For quotearg_colon */
#include "quote.h" /* For quotearg_colon */
-
-#include "rand-isaac.c"
+#include "randint.h"
+#include "randread.h"
#define DEFAULT_PASSES 25 /* Default */
@@ -128,12 +125,20 @@ struct Options
bool zero_fill; /* -z flag: Add a final zero pass */
};
+/* For long options that have no equivalent short option, use a
+ non-character as a pseudo short option, starting with CHAR_MAX + 1. */
+enum
+{
+ RANDOM_SOURCE_OPTION = CHAR_MAX + 1
+};
+
static struct option const long_opts[] =
{
{"exact", no_argument, NULL, 'x'},
{"force", no_argument, NULL, 'f'},
{"iterations", required_argument, NULL, 'n'},
{"size", required_argument, NULL, 's'},
+ {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
{"remove", no_argument, NULL, 'u'},
{"verbose", no_argument, NULL, 'v'},
{"zero", no_argument, NULL, 'z'},
@@ -165,6 +170,7 @@ Mandatory arguments to long options are
printf (_("\
-f, --force change permissions to allow writing if necessary\n\
-n, --iterations=N Overwrite N times instead of the default (%d)\n\
+ --random-source=FILE get random bytes from FILE (default
/dev/urandom)\n\
-s, --size=N shred this many bytes (suffixes like K, M, G accepted)\n\
"), DEFAULT_PASSES);
fputs (_("\
@@ -227,65 +233,6 @@ to be recovered later.\n\
exit (status);
}
-/* Single-word RNG built on top of ISAAC */
-struct irand_state
-{
- uint32_t r[ISAAC_WORDS];
- unsigned int numleft;
- struct isaac_state *s;
-};
-
-static void
-irand_init (struct irand_state *r, struct isaac_state *s)
-{
- r->numleft = 0;
- r->s = s;
-}
-
-/*
- * We take from the end of the block deliberately, so if we need
- * only a small number of values, we choose the final ones which are
- * marginally better mixed than the initial ones.
- */
-static uint32_t
-irand32 (struct irand_state *r)
-{
- if (!r->numleft)
- {
- isaac_refill (r->s, r->r);
- r->numleft = ISAAC_WORDS;
- }
- return r->r[--r->numleft];
-}
-
-/*
- * Return a uniformly distributed random number between 0 and n,
- * inclusive. Thus, the result is modulo n+1.
- *
- * Theory of operation: as x steps through every possible 32-bit number,
- * x % n takes each value at least 2^32 / n times (rounded down), but
- * the values less than 2^32 % n are taken one additional time. Thus,
- * x % n is not perfectly uniform. To fix this, the values of x less
- * than 2^32 % n are disallowed, and if the RNG produces one, we ask
- * for a new value.
- */
-static uint32_t
-irand_mod (struct irand_state *r, uint32_t n)
-{
- uint32_t x;
- uint32_t lim;
-
- if (!++n)
- return irand32 (r);
-
- lim = -n % n; /* == (2**32-n) % n == 2**32 % n */
- do
- {
- x = irand32 (r);
- }
- while (x < lim);
- return x % n;
-}
/*
* Fill a buffer with a fixed pattern.
@@ -315,23 +262,6 @@ fillpattern (int type, unsigned char *r,
}
/*
- * Fill a buffer, R (of size SIZE_MAX), with random data.
- * SIZE is rounded UP to a multiple of ISAAC_BYTES.
- */
-static void
-fillrand (struct isaac_state *s, uint32_t *r, size_t size_max, size_t size)
-{
- size_t refills = (size + ISAAC_BYTES - 1) / ISAAC_BYTES;
- assert (refills * ISAAC_BYTES <= size_max);
-
- while (refills--)
- {
- isaac_refill (s, r);
- r += ISAAC_WORDS;
- }
-}
-
-/*
* Generate a 6-character (+ nul) pass name string
* FIXME: allow translation of "random".
*/
@@ -419,7 +349,7 @@ direct_mode (int fd, bool enable)
*/
static int
dopass (int fd, char const *qname, off_t *sizep, int type,
- struct isaac_state *s, unsigned long int k, unsigned long int n)
+ struct randread_source *s, unsigned long int k, unsigned long int n)
{
off_t size = *sizep;
off_t offset; /* Current file posiiton */
@@ -428,7 +358,7 @@ dopass (int fd, char const *qname, off_t
size_t lim; /* Amount of data to try writing */
size_t soff; /* Offset into buffer for next write */
ssize_t ssize; /* Return value from write */
- uint32_t r[3 * MAX (ISAAC_WORDS, 1024)]; /* Fill pattern. */
+ uint32_t r[3 * 1024]; /* Fill pattern. */
char pass_string[PASS_NAME_SIZE]; /* Name of current pass */
bool write_error = false;
bool first_write = true;
@@ -481,7 +411,7 @@ dopass (int fd, char const *qname, off_t
break;
}
if (type < 0)
- fillrand (s, r, sizeof r, lim);
+ randread (s, r, lim);
/* Loop to retry partial writes. */
for (soff = 0; soff < lim; soff += ssize, first_write = false)
{
@@ -700,9 +630,8 @@ static int const
* order.
*/
static void
-genpattern (int *dest, size_t num, struct isaac_state *s)
+genpattern (int *dest, size_t num, struct randint_source *s)
{
- struct irand_state r;
size_t randpasses;
int const *p;
int *d;
@@ -713,8 +642,6 @@ genpattern (int *dest, size_t num, struc
if (!num)
return;
- irand_init (&r, s);
-
/* Stage 1: choose the passes to use */
p = patterns;
randpasses = 0;
@@ -756,7 +683,7 @@ genpattern (int *dest, size_t num, struc
{ /* Pad out with k of the n available */
do
{
- if (n == (size_t) k-- || irand_mod (&r, k) < n)
+ if (n == (size_t) k || randint_choose (s, k) < n)
{
*d++ = *p;
n--;
@@ -802,7 +729,7 @@ genpattern (int *dest, size_t num, struc
}
else
{
- swap = n + irand_mod (&r, top - n - 1);
+ swap = n + randint_choose (s, top - n);
k = dest[n];
dest[n] = dest[swap];
dest[swap] = k;
@@ -810,8 +737,6 @@ genpattern (int *dest, size_t num, struc
accum -= randpasses;
}
/* assert (top == num); */
-
- memset (&r, 0, sizeof r); /* Wipe this on general principles */
}
/*
@@ -819,7 +744,7 @@ genpattern (int *dest, size_t num, struc
* size bytes of the given fd. Return true if successful.
*/
static bool
-do_wipefd (int fd, char const *qname, struct isaac_state *s,
+do_wipefd (int fd, char const *qname, struct randint_source *s,
struct Options const *flags)
{
size_t i;
@@ -828,6 +753,7 @@ do_wipefd (int fd, char const *qname, st
unsigned long int n; /* Number of passes for printing purposes */
int *passarray;
bool ok = true;
+ struct randread_source *rs;
n = 0; /* dopass takes n -- 0 to mean "don't print progress" */
if (flags->verbose)
@@ -894,10 +820,12 @@ do_wipefd (int fd, char const *qname, st
/* Schedule the passes in random order. */
genpattern (passarray, flags->n_iterations, s);
+ rs = randint_get_source (s);
+
/* Do the work */
for (i = 0; i < flags->n_iterations; i++)
{
- int err = dopass (fd, qname, &size, passarray[i], s, i + 1, n);
+ int err = dopass (fd, qname, &size, passarray[i], rs, i + 1, n);
if (err)
{
if (err < 0)
@@ -915,7 +843,7 @@ do_wipefd (int fd, char const *qname, st
if (flags->zero_fill)
{
- int err = dopass (fd, qname, &size, 0, s, flags->n_iterations + 1, n);
+ int err = dopass (fd, qname, &size, 0, rs, flags->n_iterations + 1, n);
if (err)
{
if (err < 0)
@@ -939,7 +867,7 @@ do_wipefd (int fd, char const *qname, st
/* A wrapper with a little more checking for fds on the command line */
static bool
-wipefd (int fd, char const *qname, struct isaac_state *s,
+wipefd (int fd, char const *qname, struct randint_source *s,
struct Options const *flags)
{
int fd_flags = fcntl (fd, F_GETFL);
@@ -1110,7 +1038,7 @@ wipename (char *oldname, char const *qol
*/
static bool
wipefile (char *name, char const *qname,
- struct isaac_state *s, struct Options const *flags)
+ struct randint_source *s, struct Options const *flags)
{
bool ok;
int fd;
@@ -1137,16 +1065,30 @@ wipefile (char *name, char const *qname,
return ok;
}
+
+/* Buffers for random data. */
+static struct randint_source *randint_source;
+
+/* Just on general principles, wipe buffers containing information
+ that may be related to the possibly-pseudorandom values used during
+ shredding. */
+static void
+clear_random_data (void)
+{
+ randint_all_free (randint_source);
+}
+
+
int
main (int argc, char **argv)
{
- struct isaac_state s;
bool ok = true;
struct Options flags;
char **file;
int n_files;
int c;
int i;
+ char const *random_source = NULL;
initialize_main (&argc, &argv);
program_name = argv[0];
@@ -1156,8 +1098,6 @@ main (int argc, char **argv)
atexit (close_stdout);
- isaac_seed (&s);
-
memset (&flags, 0, sizeof flags);
flags.n_iterations = DEFAULT_PASSES;
@@ -1185,6 +1125,12 @@ main (int argc, char **argv)
}
break;
+ case RANDOM_SOURCE_OPTION:
+ if (random_source && !STREQ (random_source, optarg))
+ error (EXIT_FAILURE, 0, _("multiple random sources specified"));
+ random_source = optarg;
+ break;
+
case 'u':
flags.remove_file = true;
break;
@@ -1232,24 +1178,26 @@ main (int argc, char **argv)
usage (EXIT_FAILURE);
}
+ randint_source = randint_all_new (random_source, SIZE_MAX);
+ if (! randint_source)
+ error (EXIT_FAILURE, errno, "%s", quotearg_colon (random_source));
+ atexit (clear_random_data);
+
for (i = 0; i < n_files; i++)
{
char *qname = xstrdup (quotearg_colon (file[i]));
if (STREQ (file[i], "-"))
{
- ok &= wipefd (STDOUT_FILENO, qname, &s, &flags);
+ ok &= wipefd (STDOUT_FILENO, qname, randint_source, &flags);
}
else
{
/* Plain filename - Note that this overwrites *argv! */
- ok &= wipefile (file[i], qname, &s, &flags);
+ ok &= wipefile (file[i], qname, randint_source, &flags);
}
free (qname);
}
- /* Just on general principles, wipe s. */
- memset (&s, 0, sizeof s);
-
exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
}
/*
Index: src/sort.c
===================================================================
RCS file: /fetish/cu/src/sort.c,v
retrieving revision 1.338
diff -p -u -r1.338 sort.c
--- src/sort.c 9 Jul 2006 17:02:17 -0000 1.338
+++ src/sort.c 8 Aug 2006 22:08:38 -0000
@@ -30,13 +30,16 @@
#include "error.h"
#include "hard-locale.h"
#include "inttostr.h"
+#include "md5.h"
#include "physmem.h"
#include "posixver.h"
#include "quote.h"
-#include "stdlib--.h"
+#include "randread.h"
#include "stdio--.h"
+#include "stdlib--.h"
#include "strnumcmp.h"
#include "xmemcoll.h"
+#include "xmemxfrm.h"
#include "xstrtol.h"
#if HAVE_SYS_RESOURCE_H
@@ -77,8 +80,6 @@ double strtod ();
# define DEFAULT_TMPDIR "/tmp"
#endif
-#include "rand-isaac.c"
-
/* Exit statuses. */
enum
{
@@ -307,6 +308,7 @@ Ordering options:\n\
-M, --month-sort compare (unknown) < `JAN' < ... < `DEC'\n\
-n, --numeric-sort compare according to string numerical value\n\
-R, --random-sort sort by random hash of keys\n\
+ --random-source=FILE get random bytes from FILE (default
/dev/urandom)\n\
-r, --reverse reverse the result of comparisons\n\
\n\
"), stdout);
@@ -362,7 +364,7 @@ native byte values.\n\
non-character as a pseudo short option, starting with CHAR_MAX + 1. */
enum
{
- SEED_OPTION = CHAR_MAX + 1
+ RANDOM_SOURCE_OPTION = CHAR_MAX + 1
};
static char const short_options[] = "-bcdfgik:mMno:rRsS:t:T:uy:z";
@@ -380,6 +382,7 @@ static struct option const long_options[
{"month-sort", no_argument, NULL, 'M'},
{"numeric-sort", no_argument, NULL, 'n'},
{"random-sort", no_argument, NULL, 'R'},
+ {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
{"output", required_argument, NULL, 'o'},
{"reverse", no_argument, NULL, 'r'},
{"stable", no_argument, NULL, 's'},
@@ -388,7 +391,6 @@ static struct option const long_options[
{"temporary-directory", required_argument, NULL, 'T'},
{"unique", no_argument, NULL, 'u'},
{"zero-terminated", no_argument, NULL, 'z'},
- {"seed", required_argument, NULL, SEED_OPTION}, /* This will go away soon.
*/
{GETOPT_HELP_OPTION_DECL},
{GETOPT_VERSION_OPTION_DECL},
{NULL, 0, NULL, 0},
@@ -1166,19 +1168,117 @@ getmonth (char const *month, size_t len)
return 0;
}
-/* The ISAAC state resulting from the user-specified seed, or from
- random data taken from the environment. */
-static struct isaac_state rand_state;
+/* A source of random data. */
+static struct randread_source *randread_source;
-/* Set *RESULT to the ISAAC state resulting from applying TEXT (with
- length LEN) to rand_state. */
-static void
-get_hash (char const *text, size_t len, uint32_t resbuf[ISAAC_WORDS])
+/* Return the Ith randomly-generated state. The caller must invoke
+ random_state (H) for all H less than I before invoking random_state
+ (I). */
+
+static struct md5_ctx
+random_state (size_t i)
+{
+ /* An array of states resulting from the random data, and counts of
+ its used and allocated members. */
+ static struct md5_ctx *state;
+ static size_t used;
+ static size_t allocated;
+
+ struct md5_ctx *s = &state[i];
+
+ if (used <= i)
+ {
+ unsigned char buf[MD5_DIGEST_SIZE];
+
+ used++;
+
+ if (allocated <= i)
+ {
+ state = X2NREALLOC (state, &allocated);
+ s = &state[i];
+ }
+
+ randread (randread_source, buf, sizeof buf);
+ md5_init_ctx (s);
+ md5_process_bytes (buf, sizeof buf, s);
+ }
+
+ return *s;
+}
+
+/* Compare the hashes of TEXTA with length LENGTHA to those of TEXTB
+ with length LENGTHB. Return negative if less, zero if equal,
+ positive if greater. */
+
+static int
+cmp_hashes (char const *texta, size_t lena,
+ char const *textb, size_t lenb)
{
- struct isaac_state s = rand_state;
- isaac_seed_data (&s, text, len);
- isaac_seed_finish (&s);
- isaac_refill (&s, resbuf);
+ /* Try random hashes until a pair of hashes disagree. But if the
+ first pair of random hashes agree, check whether the keys are
+ identical and if so report no difference. */
+ int diff;
+ size_t i;
+ for (i = 0; ; i++)
+ {
+ uint32_t dig[2][MD5_DIGEST_SIZE / sizeof (uint32_t)];
+ struct md5_ctx s[2];
+ s[0] = s[1] = random_state (i);
+ md5_process_bytes (texta, lena, &s[0]); md5_finish_ctx (&s[0], dig[0]);
+ md5_process_bytes (textb, lenb, &s[1]); md5_finish_ctx (&s[1], dig[1]);
+ diff = memcmp (dig[0], dig[1], sizeof dig[0]);
+ if (diff != 0)
+ break;
+ if (i == 0 && lena == lenb && memcmp (texta, textb, lena) == 0)
+ break;
+ }
+
+ return diff;
+}
+
+/* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB)
+ using one or more random hash functions. */
+
+static int
+compare_random (char *restrict texta, size_t lena,
+ char *restrict textb, size_t lenb)
+{
+ int diff;
+
+ if (! hard_LC_COLLATE)
+ diff = cmp_hashes (texta, lena, textb, lenb);
+ else
+ {
+ /* Transform the text into the basis of comparison, so that byte
+ strings that would otherwise considered to be equal are
+ considered equal here even if their bytes differ. */
+
+ char *buf = NULL;
+ char stackbuf[4000];
+ size_t tlena = xmemxfrm (stackbuf, sizeof stackbuf, texta, lena);
+ bool a_fits = tlena <= sizeof stackbuf;
+ size_t tlenb = xmemxfrm ((a_fits ? stackbuf + tlena : NULL),
+ (a_fits ? sizeof stackbuf - tlena : 0),
+ textb, lenb);
+
+ if (a_fits && tlena + tlenb <= sizeof stackbuf)
+ buf = stackbuf;
+ else
+ {
+ /* Adding 1 to the buffer size lets xmemxfrm run a bit
+ faster by avoiding the need for an extra buffer copy. */
+ buf = xmalloc (tlena + tlenb + 1);
+ xmemxfrm (buf, tlena + 1, texta, lena);
+ xmemxfrm (buf + tlena, tlenb + 1, textb, lenb);
+ }
+
+ diff = cmp_hashes (buf, tlena, buf + tlena, tlenb);
+
+ if (buf != stackbuf)
+ free (buf);
+ }
+
+ return diff;
}
/* Compare two lines A and B trying every key in sequence until there
@@ -1210,29 +1310,8 @@ keycompare (const struct line *a, const
/* Actually compare the fields. */
if (key->random)
- {
- int i;
- uint32_t diga[ISAAC_WORDS];
- uint32_t digb[ISAAC_WORDS];
- get_hash (texta, lena, diga);
- get_hash (textb, lenb, digb);
-
- /* Go backwards, since the last words are marginally better
- mixed. */
- for (i = ISAAC_WORDS - 1; 0 <= i; i--)
- if (diga[i] != digb[i])
- {
- diff = (diga[i] < digb[i] ? -1 : 1);
- goto not_equal;
- }
-
- /* FIXME: Should break ties by rehashing with a different
- random hashing function (and repeat until the tie is
- broken) unless --seed was specified. The probability of
- this being needed should be infinitesimal. */
- }
-
- if (key->numeric | key->general_numeric)
+ diff = compare_random (texta, lena, textb, lenb);
+ else if (key->numeric | key->general_numeric)
{
char savea = *lima, saveb = *limb;
@@ -2208,7 +2287,7 @@ main (int argc, char **argv)
int c = 0;
bool checkonly = false;
bool mergeonly = false;
- char const *seed = NULL;
+ char *random_source = NULL;
bool need_random = false;
size_t nfiles = 0;
bool posixly_correct = (getenv ("POSIXLY_CORRECT") != NULL);
@@ -2447,9 +2526,11 @@ main (int argc, char **argv)
outfile = optarg;
break;
- case SEED_OPTION:
- seed = optarg;
- break;
+ case RANDOM_SOURCE_OPTION:
+ if (random_source && !STREQ (random_source, optarg))
+ error (SORT_FAILURE, 0, _("multiple random sources specified"));
+ random_source = optarg;
+ break;
case 's':
stable = true;
@@ -2563,13 +2644,9 @@ main (int argc, char **argv)
if (need_random)
{
- if (seed)
- {
- isaac_seed_start (&rand_state);
- isaac_seed_data (&rand_state, seed, strlen (seed));
- }
- else
- isaac_seed (&rand_state);
+ randread_source = randread_new (random_source, MD5_DIGEST_SIZE);
+ if (! randread_source)
+ die (_("open failed"), random_source);
}
if (temp_dir_count == 0)
Index: tests/misc/Makefile.am
===================================================================
RCS file: /fetish/cu/tests/misc/Makefile.am,v
retrieving revision 1.41
diff -p -u -r1.41 Makefile.am
--- tests/misc/Makefile.am 3 Jul 2006 12:55:33 -0000 1.41
+++ tests/misc/Makefile.am 8 Aug 2006 22:08:38 -0000
@@ -47,6 +47,7 @@ TESTS = \
sha256sum \
sha384sum \
sha512sum \
+ shuf \
sort-merge \
sort-rand \
split-a \
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/memxfrm.c 2006-08-06 10:03:00.000000000 -0700
@@ -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 <address@hidden>. */
+
+#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
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/memxfrm.h 2006-08-03 21:47:40.000000000 -0700
@@ -0,0 +1,2 @@
+#include <stddef.h>
+size_t memxfrm (char *restrict, size_t, char *restrict, size_t);
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/rand-isaac.c 2006-08-06 12:12:35.000000000 -0700
@@ -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);
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/rand-isaac.h 2006-08-06 12:15:19.000000000 -0700
@@ -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
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randint.c 2006-08-08 14:42:34.000000000 -0700
@@ -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;
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randint.h 2006-08-06 12:34:21.000000000 -0700
@@ -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
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randperm.c 2006-08-08 14:39:52.000000000 -0700
@@ -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;
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randperm.h 2006-08-08 13:43:30.000000000 -0700
@@ -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);
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randread.c 2006-08-08 14:20:09.000000000 -0700
@@ -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);
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/randread.h 2006-08-06 10:38:24.000000000 -0700
@@ -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
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/xmemxfrm.c 2006-08-03 21:46:00.000000000 -0700
@@ -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 <address@hidden>. */
+
+#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;
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ lib/xmemxfrm.h 2006-08-03 21:47:17.000000000 -0700
@@ -0,0 +1,2 @@
+#include <stddef.h>
+size_t xmemxfrm (char *restrict, size_t, char *restrict, size_t);
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ m4/memxfrm.m4 2006-08-03 20:45:58.000000000 -0700
@@ -0,0 +1,15 @@
+dnl Copyright (C) 2006 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_MEMXFRM],
+[
+ AC_LIBSOURCES([memxfrm.c, memxfrm.h])
+ AC_LIBOBJ([memxfrm])
+
+ AC_REQUIRE([AC_C_RESTRICT])
+
+ dnl Prerequisites of lib/memcoll.c.
+ AC_CHECK_FUNCS_ONCE([strxfrm])
+])
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ m4/randint.m4 2006-08-07 00:25:48.000000000 -0700
@@ -0,0 +1,12 @@
+dnl Copyright (C) 2006 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_RANDINT],
+[
+ AC_LIBSOURCES([randint.c, randint.h])
+ AC_LIBOBJ([randint])
+
+ AC_REQUIRE([AC_C_INLINE])
+])
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ m4/randperm.m4 2006-08-07 00:26:22.000000000 -0700
@@ -0,0 +1,10 @@
+dnl Copyright (C) 2006 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_RANDPERM],
+[
+ AC_LIBSOURCES([randperm.c, randperm.h])
+ AC_LIBOBJ([randperm])
+])
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ m4/randread.m4 2006-08-07 00:26:51.000000000 -0700
@@ -0,0 +1,11 @@
+dnl Copyright (C) 2006 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+AC_DEFUN([gl_RANDREAD],
+[
+ AC_LIBSOURCES([randread.c, randread.h, rand-isaac.c, rand-isaac.h])
+ AC_LIBOBJ([randread])
+ AC_LIBOBJ([rand-isaac])
+])
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ man/shuf.x 2006-08-08 15:00:26.000000000 -0700
@@ -0,0 +1,4 @@
+[NAME]
+shuf \- generate random permutations
+[DESCRIPTION]
+.\" Add any additional description here
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ src/shuf.c 2006-08-08 13:53:33.000000000 -0700
@@ -0,0 +1,401 @@
+/* Shuffle lines of text.
+
+ 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. */
+
+#include <config.h>
+
+#include <stdio.h>
+#include <sys/types.h>
+#include "system.h"
+
+#include "error.h"
+#include "getopt.h"
+#include "quote.h"
+#include "quotearg.h"
+#include "randint.h"
+#include "randperm.h"
+#include "xstrtol.h"
+
+/* The official name of this program (e.g., no `g' prefix). */
+#define PROGRAM_NAME "shuf"
+
+#define AUTHORS "Paul Eggert"
+
+/* The name this program was run with. */
+char *program_name;
+
+void
+usage (int status)
+{
+ if (status != EXIT_SUCCESS)
+ fprintf (stderr, _("Try `%s --help' for more information.\n"),
+ program_name);
+ else
+ {
+ printf (_("\
+Usage: %s [OPTION]... [FILE]\n\
+ or: %s -e [OPTION]... [ARG]...\n\
+ or: %s -i LO-HI [OPTION]...\n\
+"),
+ program_name, program_name, program_name);
+ fputs (_("\
+Write a random permutation of the input lines to standard output.\n\
+\n\
+"), stdout);
+ fputs (_("\
+Mandatory arguments to long options are mandatory for short options too.\n\
+"), stdout);
+ fputs (_("\
+ -e, --echo treat each ARG as an input line\n\
+ -i, --input-range=LO-HI treat each number LO through HI as an input line\n\
+ -n, --head-lines=LINES output at most LINES lines\n\
+ -o, --output=FILE write result to FILE instead of standard output\n\
+ --random-source=FILE get random bytes from FILE (default
/dev/urandom)\n\
+ -z, --zero-terminated end lines with 0 byte, not newline\n\
+"), stdout);
+ fputs (HELP_OPTION_DESCRIPTION, stdout);
+ fputs (VERSION_OPTION_DESCRIPTION, stdout);
+ fputs (_("\
+\n\
+With no FILE, or when FILE is -, read standard input.\n\
+"), stdout);
+ printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
+ }
+
+ exit (status);
+}
+
+/* For long options that have no equivalent short option, use a
+ non-character as a pseudo short option, starting with CHAR_MAX + 1. */
+enum
+{
+ RANDOM_SOURCE_OPTION = CHAR_MAX + 1
+};
+
+static struct option const long_opts[] =
+{
+ {"echo", no_argument, NULL, 'e'},
+ {"input-range", required_argument, NULL, 'i'},
+ {"head-count", required_argument, NULL, 'n'},
+ {"output", required_argument, NULL, 'o'},
+ {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
+ {"zero-terminated", no_argument, NULL, 'z'},
+ {GETOPT_HELP_OPTION_DECL},
+ {GETOPT_VERSION_OPTION_DECL},
+ {0, 0, 0, 0},
+};
+
+static bool
+input_numbers_option_used (size_t lo_input, size_t hi_input)
+{
+ return ! (lo_input == SIZE_MAX && hi_input == 0);
+}
+
+static void
+input_from_argv (char **operand, int n_operands, char eolbyte)
+{
+ char *p;
+ size_t size = n_operands;
+ int i;
+
+ for (i = 0; i < n_operands; i++)
+ size += strlen (operand[i]);
+ p = xmalloc (size);
+
+ for (i = 0; i < n_operands; i++)
+ {
+ char *p1 = stpcpy (p, operand[i]);
+ operand[i] = p;
+ p = p1;
+ *p++ = eolbyte;
+ }
+
+ operand[n_operands] = p;
+}
+
+/* Read data from file IN. Input lines are delimited by EOLBYTE;
+ silently append a trailing EOLBYTE if the file ends in some other
+ byte. Store a pointer to the resulting array of lines into *PLINE.
+ Return the number of lines read. Report an error and exit on
+ failure. */
+
+static size_t
+read_input (FILE *in, char eolbyte, char ***pline)
+{
+ char *p;
+ char *buf = NULL;
+ char *lim;
+ size_t alloc = 0;
+ size_t used = 0;
+ size_t next_alloc = (1 << 13) + 1;
+ size_t bytes_to_read;
+ size_t nread;
+ char **line;
+ size_t i;
+ size_t n_lines;
+ int fread_errno;
+ struct stat instat;
+
+ if (fstat (fileno (in), &instat) == 0 && S_ISREG (instat.st_mode))
+ {
+ off_t file_size = instat.st_size;
+ off_t current_offset = ftello (in);
+ if (0 <= current_offset)
+ {
+ off_t remaining_size =
+ (current_offset < file_size ? file_size - current_offset : 0);
+ if (SIZE_MAX - 2 < remaining_size)
+ xalloc_die ();
+ next_alloc = remaining_size + 2;
+ }
+ }
+
+ do
+ {
+ if (alloc == used)
+ {
+ if (alloc == SIZE_MAX)
+ xalloc_die ();
+ alloc = next_alloc;
+ next_alloc = alloc * 2;
+ if (next_alloc < alloc)
+ next_alloc = SIZE_MAX;
+ buf = xrealloc (buf, alloc);
+ }
+
+ bytes_to_read = alloc - used - 1;
+ nread = fread (buf + used, sizeof (char), bytes_to_read, in);
+ used += nread;
+ }
+ while (nread == bytes_to_read);
+
+ fread_errno = errno;
+
+ if (used && buf[used - 1] != eolbyte)
+ buf[used++] = eolbyte;
+
+ lim = buf + used;
+
+ n_lines = 0;
+ for (p = buf; p < lim; p = memchr (p, eolbyte, lim - p) + 1)
+ n_lines++;
+
+ *pline = line = xnmalloc (n_lines + 1, sizeof *line);
+
+ line[0] = p = buf;
+ for (i = 1; i <= n_lines; i++)
+ line[i] = p = memchr (p, eolbyte, lim - p) + 1;
+
+ errno = fread_errno;
+ return n_lines;
+}
+
+static int
+write_permuted_output (size_t n_lines, char * const *line, size_t lo_input,
+ size_t const *permutation)
+{
+ size_t i;
+
+ if (line)
+ for (i = 0; i < n_lines; i++)
+ {
+ char * const *p = line + permutation[i];
+ size_t len = p[1] - p[0];
+ if (fwrite (p[0], sizeof *p[0], len, stdout) != len)
+ return -1;
+ }
+ else
+ for (i = 0; i < n_lines; i++)
+ {
+ unsigned long int n = lo_input + permutation[i];
+ if (printf ("%lu\n", n) < 0)
+ return -1;
+ }
+
+ return 0;
+}
+
+int
+main (int argc, char **argv)
+{
+ bool echo = false;
+ size_t lo_input = SIZE_MAX;
+ size_t hi_input = 0;
+ size_t head_lines = SIZE_MAX;
+ char const *outfile = NULL;
+ char *random_source = NULL;
+ char eolbyte = '\n';
+
+ int optc;
+ int n_operands;
+ char **operand;
+ size_t n_lines;
+ char **line;
+ struct randint_source *randint_source;
+ size_t const *permutation;
+
+ initialize_main (&argc, &argv);
+ program_name = argv[0];
+ setlocale (LC_ALL, "");
+ bindtextdomain (PACKAGE, LOCALEDIR);
+ textdomain (PACKAGE);
+
+ atexit (close_stdout);
+
+ while ((optc = getopt_long (argc, argv, "ei:n:o:z", long_opts, NULL)) != -1)
+ switch (optc)
+ {
+ case 'e':
+ echo = true;
+ break;
+
+ case 'i':
+ {
+ unsigned long int argval = 0;
+ char *p = strchr (optarg, '-');
+ bool invalid = !p;
+
+ if (input_numbers_option_used (lo_input, hi_input))
+ error (EXIT_FAILURE, 0, _("multiple -i options specified"));
+
+ if (p)
+ {
+ *p = '\0';
+ invalid = ((xstrtoul (optarg, NULL, 10, &argval, NULL)
+ != LONGINT_OK)
+ || SIZE_MAX < argval);
+ *p = '-';
+ lo_input = argval;
+ optarg = p + 1;
+ }
+
+ invalid |= ((xstrtoul (optarg, NULL, 10, &argval, NULL)
+ != LONGINT_OK)
+ || SIZE_MAX < argval);
+ hi_input = argval;
+ n_lines = hi_input - lo_input + 1;
+ invalid |= ((lo_input <= hi_input) == (n_lines == 0));
+ if (invalid)
+ error (EXIT_FAILURE, 0, _("invalid input range %s"),
+ quote (optarg));
+ }
+ break;
+
+ case 'n':
+ {
+ unsigned long int argval;
+ strtol_error e = xstrtoul (optarg, NULL, 10, &argval, NULL);
+
+ if (e == LONGINT_OK)
+ head_lines = MIN (head_lines, argval);
+ else if (e != LONGINT_OVERFLOW)
+ error (EXIT_FAILURE, 0, _("invalid line count %s"),
+ quote (optarg));
+ }
+ break;
+
+ case 'o':
+ if (outfile && !STREQ (outfile, optarg))
+ error (EXIT_FAILURE, 0, _("multiple output files specified"));
+ outfile = optarg;
+ break;
+
+ case RANDOM_SOURCE_OPTION:
+ if (random_source && !STREQ (random_source, optarg))
+ error (EXIT_FAILURE, 0, _("multiple random sources specified"));
+ random_source = optarg;
+ break;
+
+ case 'z':
+ eolbyte = '\0';
+ break;
+
+ case_GETOPT_HELP_CHAR;
+ case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
+ default:
+ usage (EXIT_FAILURE);
+ }
+
+ n_operands = argc - optind;
+ operand = argv + optind;
+
+ if (echo)
+ {
+ if (input_numbers_option_used (lo_input, hi_input))
+ error (EXIT_FAILURE, 0, _("cannot combine -e and -i options"));
+ input_from_argv (operand, n_operands, eolbyte);
+ n_lines = n_operands;
+ line = operand;
+ }
+ else if (input_numbers_option_used (lo_input, hi_input))
+ {
+ if (n_operands)
+ {
+ error (0, 0, _("extra operand %s\n"), quote (operand[0]));
+ usage (EXIT_FAILURE);
+ }
+ n_lines = hi_input - lo_input + 1;
+ line = NULL;
+ }
+ else
+ {
+ char **input_lines;
+
+ switch (n_operands)
+ {
+ case 0:
+ break;
+
+ case 1:
+ if (! (STREQ (operand[0], "-") || freopen (operand[0], "r", stdin)))
+ error (EXIT_FAILURE, errno, "%s", operand[0]);
+ break;
+
+ default:
+ error (0, 0, _("extra operand %s"), quote (operand[1]));
+ usage (EXIT_FAILURE);
+ }
+
+ n_lines = read_input (stdin, eolbyte, &input_lines);
+ line = input_lines;
+ }
+
+ head_lines = MIN (head_lines, n_lines);
+
+ randint_source = randint_all_new (random_source,
+ randperm_bound (head_lines, n_lines));
+ if (! randint_source)
+ error (EXIT_FAILURE, errno, "%s", quotearg_colon (random_source));
+
+ /* Close stdin now, rather than earlier, so that randint_all_new
+ doesn't have to worry about opening something other than
+ stdin. */
+ if (! (echo || input_numbers_option_used (lo_input, hi_input))
+ && (ferror (stdin) || fclose (stdin) != 0))
+ error (EXIT_FAILURE, errno, _("read error"));
+
+ permutation = randperm_new (randint_source, head_lines, n_lines);
+
+ if (outfile && ! freopen (outfile, "w", stdout))
+ error (EXIT_FAILURE, errno, "%s", quotearg_colon (outfile));
+ if (write_permuted_output (head_lines, line, lo_input, permutation) != 0)
+ error (EXIT_FAILURE, errno, _("write error"));
+
+ return EXIT_SUCCESS;
+}
--- /dev/null 2005-09-24 22:00:15.000000000 -0700
+++ tests/misc/shuf 2006-08-01 19:55:35.000000000 -0700
@@ -0,0 +1,37 @@
+#!/bin/sh
+# Ensure that shuf randomizes its input.
+
+if test "$VERBOSE" = yes; then
+ set -x
+ shuf --version
+fi
+
+pwd=`pwd`
+t0=`echo "$0"|sed 's,.*/,,'`.tmp; tmp=$t0/$$
+trap 'status=$?; cd $pwd; chmod -R u+rwx $t0; rm -rf $t0 && exit $status' 0
+trap '(exit $?); exit $?' 1 2 13 15
+
+framework_failure=0
+mkdir -p $tmp || framework_failure=1
+cd $tmp || framework_failure=1
+seq 100 > in || framework_failure=1
+
+if test $framework_failure = 1; then
+ echo "$0: failure in testing framework" 1>&2
+ (exit 1); exit 1
+fi
+
+fail=0
+
+shuf in >out || fail=1
+
+# Fail if the input is the same as the output.
+# This is a probabilistic test :-)
+# However, the odds of failure are very low: 1 in 100! (~ 1 in 10^158)
+cmp in out > /dev/null && { fail=1; echo "not random?" 1>&2; }
+
+# Fail if the sorted output is not the same as the input.
+sort -n out > out1
+cmp in out1 || { fail=1; echo "not a permutation" 1>&2; }
+
+(exit $fail); exit $fail
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- random number patch: 'sort -R' fixes for non-C locales; new cmd 'shuf',
Paul Eggert <=