doc: clarify ln's --help output
[coreutils/ericb.git] / gl / lib / rand-isaac.c
blob375cfc2dc50d5b8c0d180598c2af9b5ebc271c02
1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64.
3 Copyright (C) 1999-2006, 2009-2011 Free Software Foundation, Inc.
4 Copyright (C) 1997, 1998, 1999 Colin Plumb.
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
19 Written by Colin Plumb and Paul Eggert. */
22 * --------------------------------------------------------------------
23 * We need a source of random numbers for some data.
24 * Cryptographically secure is desirable, but it's not life-or-death
25 * so I can be a little bit experimental in the choice of RNGs here.
27 * This generator is based somewhat on RC4, but has analysis
28 * <http://burtleburtle.net/bob/rand/isaacafa.html>
29 * pointing to it actually being better. I like it because it's nice
30 * and fast, and because the author did good work analyzing it.
31 * --------------------------------------------------------------------
33 #include <config.h>
35 #include "rand-isaac.h"
37 #include <limits.h>
39 /* The minimum of two sizes A and B. */
40 static inline size_t
41 min (size_t a, size_t b)
43 return (a < b ? a : b);
46 /* A if 32-bit ISAAC, B if 64-bit. This is a macro, not an inline
47 function, to prevent undefined behavior if the unused argument
48 shifts by more than a word width. */
49 #define IF32(a, b) (ISAAC_BITS == 32 ? (a) : (b))
51 /* Discard bits outside the desired range. On typical machines, any
52 decent compiler should optimize this function call away to nothing.
53 But machines with pad bits in integers may need to do more work. */
54 static inline isaac_word
55 just (isaac_word a)
57 isaac_word desired_bits = ((isaac_word) 1 << 1 << (ISAAC_BITS - 1)) - 1;
58 return a & desired_bits;
61 /* The index operation. On typical machines whose words are exactly
62 the right size, this is optimized to a mask, an addition, and an
63 indirect load. Atypical machines need more work. */
64 static inline isaac_word
65 ind (isaac_word const *m, isaac_word x)
67 return (sizeof *m * CHAR_BIT == ISAAC_BITS
68 ? (* (isaac_word *) ((char *) m
69 + (x & ((ISAAC_WORDS - 1) * sizeof *m))))
70 : m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)]);
73 /* Use and update *S to generate random data to fill RESULT. */
74 void
75 isaac_refill (struct isaac_state *s, isaac_word result[ISAAC_WORDS])
77 /* Caches of S->a and S->b. */
78 isaac_word a = s->a;
79 isaac_word b = s->b + (++s->c);
81 /* Pointers into state array and into result. */
82 isaac_word *m = s->m;
83 isaac_word *r = result;
85 enum { HALF = ISAAC_WORDS / 2 };
87 /* The central step. S->m is the whole state array, while M is a
88 pointer to the current word. OFF is the offset from M to the
89 word ISAAC_WORDS/2 words away in the SM array, i.e. +/-
90 ISAAC_WORDS/2. A and B are state variables, and R the result.
91 This updates A, B, M[I], and R[I]. */
92 #define ISAAC_STEP(i, off, mix) \
93 { \
94 isaac_word x, y; \
95 a = (IF32 (a, 0) ^ (mix)) + m[off + (i)]; \
96 x = m[i]; \
97 m[i] = y = ind (s->m, x) + a + b; \
98 r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \
103 ISAAC_STEP (0, HALF, IF32 ( a << 13, ~ (a ^ (a << 21))));
104 ISAAC_STEP (1, HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));
105 ISAAC_STEP (2, HALF, IF32 ( a << 2, a ^ ( a << 12)));
106 ISAAC_STEP (3, HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
107 r += 4;
109 while ((m += 4) < s->m + HALF);
113 ISAAC_STEP (0, -HALF, IF32 ( a << 13, ~ (a ^ (a << 21))));
114 ISAAC_STEP (1, -HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));
115 ISAAC_STEP (2, -HALF, IF32 ( a << 2, a ^ ( a << 12)));
116 ISAAC_STEP (3, -HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
117 r += 4;
119 while ((m += 4) < s->m + ISAAC_WORDS);
121 s->a = a;
122 s->b = b;
126 * The basic seed-scrambling step for initialization, based on Bob
127 * Jenkins' 256-bit hash.
129 #if ISAAC_BITS == 32
130 #define mix(a, b, c, d, e, f, g, h) \
132 a ^= b << 11; d += a; \
133 b += c; b ^= just (c) >> 2; e += b; \
134 c += d; c ^= d << 8; f += c; \
135 d += e; d ^= just (e) >> 16; g += d; \
136 e += f; e ^= f << 10; h += e; \
137 f += g; f ^= just (g) >> 4; a += f; \
138 g += h; g ^= h << 8; b += g; \
139 h += a; h ^= just (a) >> 9; c += h; \
140 a += b; \
142 #else
143 #define mix(a, b, c, d, e, f, g, h) \
145 a -= e; f ^= just (h) >> 9; h += a; \
146 b -= f; g ^= a << 9; a += b; \
147 c -= g; h ^= just (b) >> 23; b += c; \
148 d -= h; a ^= c << 15; c += d; \
149 e -= a; b ^= just (d) >> 14; d += e; \
150 f -= b; c ^= e << 20; e += f; \
151 g -= c; d ^= just (f) >> 17; f += g; \
152 h -= d; e ^= g << 14; g += h; \
154 #endif
157 /* The basic ISAAC initialization pass. */
158 #define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \
160 int i; \
162 for (i = 0; i < ISAAC_WORDS; i += 8) \
164 a += seed[i]; \
165 b += seed[i + 1]; \
166 c += seed[i + 2]; \
167 d += seed[i + 3]; \
168 e += seed[i + 4]; \
169 f += seed[i + 5]; \
170 g += seed[i + 6]; \
171 h += seed[i + 7]; \
172 mix (a, b, c, d, e, f, g, h); \
173 s->m[i] = a; \
174 s->m[i + 1] = b; \
175 s->m[i + 2] = c; \
176 s->m[i + 3] = d; \
177 s->m[i + 4] = e; \
178 s->m[i + 5] = f; \
179 s->m[i + 6] = g; \
180 s->m[i + 7] = h; \
184 #if 0 /* Provided for reference only; not used in this code */
186 * Initialize the ISAAC RNG with the given seed material.
187 * Its size MUST be a multiple of ISAAC_BYTES, and may be
188 * stored in the s->m array.
190 * This is a generalization of the original ISAAC initialization code
191 * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES,
192 * it is identical.
194 static void
195 isaac_init (struct isaac_state *s, isaac_word const *seed, size_t seedsize)
197 isaac_word a, b, c, d, e, f, g, h;
199 a = b = c = d = e = f = g = h = /* the golden ratio */
200 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
201 for (int i = 0; i < 4; i++) /* scramble it */
202 mix (a, b, c, d, e, f, g, h);
203 s->a = s->b = s->c = 0;
205 if (seedsize)
207 /* First pass (as in reference ISAAC code) */
208 ISAAC_MIX (s, a, b, c, d, e, f, g, h, seed);
209 /* Second and subsequent passes (extension to ISAAC) */
210 while (seedsize -= ISAAC_BYTES)
212 seed += ISAAC_WORDS;
213 for (i = 0; i < ISAAC_WORDS; i++)
214 s->m[i] += seed[i];
215 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
218 else
220 /* The no seed case (as in reference ISAAC code) */
221 for (i = 0; i < ISAAC_WORDS; i++)
222 s->m[i] = 0;
225 /* Final pass */
226 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
228 #endif
230 /* Initialize *S to a somewhat-random value, derived from a seed
231 stored in S->m. */
232 void
233 isaac_seed (struct isaac_state *s)
235 isaac_word a = IF32 (UINT32_C (0x1367df5a), UINT64_C (0x647c4677a2884b7c));
236 isaac_word b = IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862));
237 isaac_word c = IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0));
238 isaac_word d = IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524));
239 isaac_word e = IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce));
240 isaac_word f = IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315));
241 isaac_word g = IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed));
242 isaac_word h = IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab));
244 #if 0
245 /* The initialization of a through h is a precomputed form of: */
246 a = b = c = d = e = f = g = h = /* the golden ratio */
247 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
248 for (int i = 0; i < 4; i++) /* scramble it */
249 mix (a, b, c, d, e, f, g, h);
250 #endif
252 /* Mix S->m so that every part of the seed affects every part of the
253 state. */
254 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
255 ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
257 s->a = s->b = s->c = 0;