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);