diff -N -ur -x '*.in' -x Makefile -x configure -x dircolors.h -x groups -x '*~' -x wheel.h -x 'localedir.*' -x 'stamp-*' -x wheel-size.h -x alloca.h -x .deps -x charset.alias -x getdate.c -x ref-add.sed -x ref-del.sed -x po -x config.h -x config.log -x config.status -x coreutils.info -x autom4te.cache -x 'output.*' -x confdefs.h -x '.#*' -x CVS -x tests -x '*.1' -x config.hin -x '*.orig' -x '*.rej' -x version.texi coreutils-cvs-2-sort-with-isaac/ChangeLog coreutils-cvs-3-sort-with-param-isaac/ChangeLog
--- coreutils-cvs-2-sort-with-isaac/ChangeLog 2005-12-01 03:07:15.000000000 +0000
+++ coreutils-cvs-3-sort-with-param-isaac/ChangeLog 2005-12-01 03:06:55.000000000 +0000
@@ -1,9 +1,11 @@
2005-11-25 Frederik Eaton
* src/shred.c:
- * src/isaac.h:
- * src/isaac.c: transfer ISAAC code (for cryptographic random
- number generation) from shred.c to new files isaac.c, isaac.h
+ * src/rand-isaac.h:
+ * src/rand-isaac.c (isaac_new, isaac_copy): transfer ISAAC code
+ (for cryptographic random number generation) from shred.c to new
+ files rand-isaac.c, rand-isaac.h; make state size
+ runtime-configurable and add functions isaac_new and isaac_copy
* src/Makefile.am (shred_SOURCES): isaac.c is now a source of shred
diff -N -ur -x '*.in' -x Makefile -x configure -x dircolors.h -x groups -x '*~' -x wheel.h -x 'localedir.*' -x 'stamp-*' -x wheel-size.h -x alloca.h -x .deps -x charset.alias -x getdate.c -x ref-add.sed -x ref-del.sed -x po -x config.h -x config.log -x config.status -x coreutils.info -x autom4te.cache -x 'output.*' -x confdefs.h -x '.#*' -x CVS -x tests -x '*.1' -x config.hin -x '*.orig' -x '*.rej' -x version.texi coreutils-cvs-2-sort-with-isaac/src/rand-isaac.c coreutils-cvs-3-sort-with-param-isaac/src/rand-isaac.c
--- coreutils-cvs-2-sort-with-isaac/src/rand-isaac.c 2005-12-01 00:04:51.000000000 +0000
+++ coreutils-cvs-3-sort-with-param-isaac/src/rand-isaac.c 2005-12-01 03:15:06.000000000 +0000
@@ -24,37 +24,72 @@
* --------------------------------------------------------------------
*/
+#define ISAAC_SIZE(words) \
+ (sizeof (struct isaac_state) - \
+ (ISAAC_MAX_WORDS - words) * sizeof (uint32_t))
+
+/*
+ * Create a new state, optionally at the location specified. This
+ * should be called to create/initialize each new isaac_state.
+ */
+struct isaac_state *
+isaac_new (struct isaac_state *s, int words)
+{
+ size_t w;
+ size_t ss = ISAAC_SIZE (words);
+ if (!s)
+ {
+ s = xmalloc (ss);
+ }
+ memset (s, 0, ss);
+ s->words = words;
+ s->log = 0;
+ for (w=1; wlog++) {}
+ return s;
+}
+
+/*
+ * Copy a state. Destination block must be at least as large as
+ * source.
+ */
+void
+isaac_copy (struct isaac_state *dst, struct isaac_state *src)
+{
+ memcpy(dst, src, ISAAC_SIZE (src->words));
+}
+
/*
* Refill the entire R array, and update S.
*/
void
-isaac_refill (struct isaac_state *s, uint32_t r[/* ISAAC_WORDS */])
+isaac_refill (struct isaac_state *s, uint32_t r[/* s>-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 */
+ uint32_t w = s->words;
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);
+ isaac_step (s, a << 13, a, b, m, w / 2, r);
+ isaac_step (s, a >> 6, a, b, m + 1, w / 2, r + 1);
+ isaac_step (s, a << 2, a, b, m + 2, w / 2, r + 2);
+ isaac_step (s, a >> 16, a, b, m + 3, w / 2, r + 3);
r += 4;
}
- while ((m += 4) < s->mm + ISAAC_WORDS / 2);
+ while ((m += 4) < s->mm + w / 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);
+ isaac_step (s, a << 13, a, b, m, -w / 2, r);
+ isaac_step (s, a >> 6, a, b, m + 1, -w / 2, r + 1);
+ isaac_step (s, a << 2, a, b, m + 2, -w / 2, r + 2);
+ isaac_step (s, a >> 16, a, b, m + 3, -w / 2, r + 3);
r += 4;
}
- while ((m += 4) < s->mm + ISAAC_WORDS);
+ while ((m += 4) < s->mm + w);
s->a = a;
s->b = b;
}
@@ -76,7 +111,7 @@
/* The basic ISAAC initialization pass. */
void
-isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */])
+isaac_mix (struct isaac_state *s, uint32_t const seed[/* s->words */])
{
int i;
uint32_t a = s->iv[0];
@@ -87,8 +122,9 @@
uint32_t f = s->iv[5];
uint32_t g = s->iv[6];
uint32_t h = s->iv[7];
+ uint32_t w = s->words;
- for (i = 0; i < ISAAC_WORDS; i += 8)
+ for (i = 0; i < w; i += 8)
{
a += seed[i];
b += seed[i + 1];
@@ -123,13 +159,13 @@
#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
+ * Initialize the ISAAC RNG with the given seed material. Its size
+ * MUST be a multiple of s->words * sizeof (uint32_t), 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.
+ * to support larger seed sizes. For seed sizes of 0 and s->words *
+ * sizeof (uint32_t), it is identical.
*/
void
isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize)
@@ -157,10 +193,10 @@
/* First pass (as in reference ISAAC code) */
isaac_mix (s, seed);
/* Second and subsequent passes (extension to ISAAC) */
- while (seedsize -= ISAAC_BYTES)
+ while (seedsize -= s->words * sizeof (uint32_t))
{
- seed += ISAAC_WORDS;
- for (i = 0; i < ISAAC_WORDS; i++)
+ seed += s->words;
+ for (i = 0; i < s->words; i++)
s->mm[i] += seed[i];
isaac_mix (s, s->mm);
}
@@ -168,7 +204,7 @@
else
{
/* The no seed case (as in reference ISAAC code) */
- for (i = 0; i < ISAAC_WORDS; i++)
+ for (i = 0; i < s->words; i++)
s->mm[i] = 0;
}
@@ -219,7 +255,7 @@
size_t avail;
size_t i;
- avail = sizeof s->mm - (size_t) s->c; /* s->c is used as a write pointer */
+ avail = s->words - (size_t) s->c; /* s->c is used as a write pointer */
/* Do any full buffers that are necessary */
while (size > avail)
@@ -231,7 +267,7 @@
size -= avail;
isaac_mix (s, s->mm);
s->c = 0;
- avail = sizeof s->mm;
+ avail = s->words;
}
/* And the final partial block */
@@ -302,6 +338,7 @@
{
r->numleft = 0;
r->s = s;
+ memset (r->r, 0, s->words * sizeof (uint32_t));
}
/*
@@ -315,7 +352,7 @@
if (!r->numleft)
{
isaac_refill (r->s, r->r);
- r->numleft = ISAAC_WORDS;
+ r->numleft = r->s->words;
}
return r->r[--r->numleft];
}
diff -N -ur -x '*.in' -x Makefile -x configure -x dircolors.h -x groups -x '*~' -x wheel.h -x 'localedir.*' -x 'stamp-*' -x wheel-size.h -x alloca.h -x .deps -x charset.alias -x getdate.c -x ref-add.sed -x ref-del.sed -x po -x config.h -x config.log -x config.status -x coreutils.info -x autom4te.cache -x 'output.*' -x confdefs.h -x '.#*' -x CVS -x tests -x '*.1' -x config.hin -x '*.orig' -x '*.rej' -x version.texi coreutils-cvs-2-sort-with-isaac/src/rand-isaac.h coreutils-cvs-3-sort-with-param-isaac/src/rand-isaac.h
--- coreutils-cvs-2-sort-with-isaac/src/rand-isaac.h 2005-12-01 02:56:41.000000000 +0000
+++ coreutils-cvs-3-sort-with-param-isaac/src/rand-isaac.h 2005-12-01 01:49:30.000000000 +0000
@@ -1,39 +1,49 @@
-/* Size of the state tables to use. (You may change ISAAC_LOG) */
+/* Size of the state tables to use. */
+/* (You may change ISAAC_LOG but it should be >= 3, and smaller values
+ * give less security) */
+#ifndef ISAAC_LOG
#define ISAAC_LOG 8
-#define ISAAC_WORDS (1 << ISAAC_LOG)
-#define ISAAC_BYTES (ISAAC_WORDS * sizeof (uint32_t))
+#endif
+#define ISAAC_MAX_WORDS (1 << ISAAC_LOG)
+#define ISAAC_MAX_BYTES (ISAAC_MAX_WORDS * sizeof (uint32_t))
/* RNG state variables */
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 */
+ uint32_t iv[8]; /* Seeding initial vector */
+ uint32_t a, b, c; /* Extra index variables */
+ uint32_t words; /* Words in main state array */
+ uint32_t log; /* Log of words */
+ uint32_t mm[ISAAC_MAX_WORDS]; /* Main state array */
};
/* This index operation is more efficient on many processors */
-#define ind(mm, x) \
+#define ind(words, mm, x) \
(* (uint32_t *) ((char *) (mm) \
- + ((x) & (ISAAC_WORDS - 1) * sizeof (uint32_t))))
+ + ((x) & (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.
+ * The central step. This uses two temporaries, x and y. s is the
+ * state, while m is a pointer to the current word. off is the offset
+ * from m to the word s->words/2 words away in the mm array, i.e.
+ * +/- s->words/2.
*/
-#define isaac_step(mix, a, b, mm, m, off, r) \
+#define isaac_step(s, mix, a, b, 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 \
+ *(m) = y = ind (s->words, s->mm, x) + (a) + (b), \
+ *(r) = b = ind (s->words, s->mm, (y) >> s->log) + x \
)
+struct isaac_state *
+isaac_new (struct isaac_state *s, int words);
void
-isaac_refill (struct isaac_state *s, uint32_t r[/* ISAAC_WORDS */]);
+isaac_copy (struct isaac_state *dst, struct isaac_state *src);
void
-isaac_mix (struct isaac_state *s, uint32_t const seed[/* ISAAC_WORDS */]);
+isaac_refill (struct isaac_state *s, uint32_t r[/* s->words */]);
+void
+isaac_mix (struct isaac_state *s, uint32_t const seed[/* s->words */]);
void
isaac_init (struct isaac_state *s, uint32_t const *seed, size_t seedsize);
void
@@ -49,7 +59,7 @@
/* Single-word RNG built on top of ISAAC */
struct irand_state
{
- uint32_t r[ISAAC_WORDS];
+ uint32_t r[ISAAC_MAX_WORDS];
unsigned int numleft;
struct isaac_state *s;
};
diff -N -ur -x '*.in' -x Makefile -x configure -x dircolors.h -x groups -x '*~' -x wheel.h -x 'localedir.*' -x 'stamp-*' -x wheel-size.h -x alloca.h -x .deps -x charset.alias -x getdate.c -x ref-add.sed -x ref-del.sed -x po -x config.h -x config.log -x config.status -x coreutils.info -x autom4te.cache -x 'output.*' -x confdefs.h -x '.#*' -x CVS -x tests -x '*.1' -x config.hin -x '*.orig' -x '*.rej' -x version.texi coreutils-cvs-2-sort-with-isaac/src/shred.c coreutils-cvs-3-sort-with-param-isaac/src/shred.c
--- coreutils-cvs-2-sort-with-isaac/src/shred.c 2005-11-26 22:49:12.000000000 +0000
+++ coreutils-cvs-3-sort-with-param-isaac/src/shred.c 2005-12-01 00:33:14.000000000 +0000
@@ -256,18 +256,19 @@
/*
* Fill a buffer, R (of size SIZE_MAX), with random data.
- * SIZE is rounded UP to a multiple of ISAAC_BYTES.
+ * SIZE is rounded UP to a multiple of s->words * sizeof (uint32_t).
*/
static void
fillrand (struct isaac_state *s, uint32_t *r, size_t size_max, size_t size)
{
- size = (size + ISAAC_BYTES - 1) / ISAAC_BYTES;
+ size_t bytes = s->words * sizeof (uint32_t);
+ size = (size + bytes - 1) / bytes;
assert (size <= size_max);
while (size--)
{
isaac_refill (s, r);
- r += ISAAC_WORDS;
+ r += s->words;
}
}
@@ -369,7 +370,7 @@
size_t soff; /* Offset into buffer for next write */
ssize_t ssize; /* Return value from write */
uint32_t *r; /* Fill pattern. */
- size_t rsize = 3 * MAX (ISAAC_WORDS, 1024) * sizeof *r; /* Fill size. */
+ size_t rsize = 3 * MAX (s->words, 1024) * sizeof *r; /* Fill size. */
size_t ralign = lcm (getpagesize (), sizeof *r); /* Fill alignment. */
char pass_string[PASS_NAME_SIZE]; /* Name of current pass */
bool write_error = false;
@@ -1103,6 +1104,7 @@
atexit (close_stdout);
+ isaac_new (&s, ISAAC_MAX_WORDS);
isaac_seed (&s);
memset (&flags, 0, sizeof flags);
diff -N -ur -x '*.in' -x Makefile -x configure -x dircolors.h -x groups -x '*~' -x wheel.h -x 'localedir.*' -x 'stamp-*' -x wheel-size.h -x alloca.h -x .deps -x charset.alias -x getdate.c -x ref-add.sed -x ref-del.sed -x po -x config.h -x config.log -x config.status -x coreutils.info -x autom4te.cache -x 'output.*' -x confdefs.h -x '.#*' -x CVS -x tests -x '*.1' -x config.hin -x '*.orig' -x '*.rej' -x version.texi coreutils-cvs-2-sort-with-isaac/src/sort.c coreutils-cvs-3-sort-with-param-isaac/src/sort.c
--- coreutils-cvs-2-sort-with-isaac/src/sort.c 2005-11-30 12:48:44.000000000 +0000
+++ coreutils-cvs-3-sort-with-param-isaac/src/sort.c 2005-12-01 02:35:23.000000000 +0000
@@ -79,6 +79,8 @@
# define DEFAULT_TMPDIR "/tmp"
#endif
+#define SORT_ISAAC_WORDS 8
+
/* Exit statuses. */
enum
{
@@ -1173,16 +1175,17 @@
{
struct isaac_state s;
int i;
- memcpy (&s, rand_state, sizeof s);
+ isaac_copy (&s, rand_state);
isaac_seed_data (&s, text, len);
/* we can call isaac_seed_finish multiple times, but should only
call isaac_seed_start once */
isaac_seed_finish (&s);
+
/* getting an irand_state and drawing random numbers would be more
kosher here, but also slower. so we just peek at the ISAAC state
array instead */
for (i = 0; i < HASH_WORDS; i++)
- resbuf[i] = s.mm[ISAAC_WORDS - 1 - i];
+ resbuf[i] = s.mm[s.words - 1 - i];
}
/* Compare two lines A and B trying every key in sequence until there
@@ -1223,8 +1226,8 @@
}
else if (key->random_hash)
{
- uint32_t diga[HASH_SIZE];
- uint32_t digb[HASH_SIZE];
+ uint32_t diga[HASH_WORDS];
+ uint32_t digb[HASH_WORDS];
get_hash (texta, lena, diga);
get_hash (textb, lenb, digb);
diff = memcmp (diga, digb, sizeof (diga));
@@ -2490,7 +2493,7 @@
if (need_rand)
{
- rand_state = xzalloc (sizeof *rand_state);
+ rand_state = isaac_new (NULL, SORT_ISAAC_WORDS);
if (randseed)
{
isaac_seed_start (rand_state);