1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64.
3 Copyright (C) 1999-2017 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 * --------------------------------------------------------------------
35 #include "rand-isaac.h"
40 /* If the platform supports unaligned access,
41 then don't have -fsanitize=undefined warn about it. */
42 #undef ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED
43 #if !(_STRING_ARCH_unaligned || _STRING_INLINE_unaligned) \
44 || __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 9)
45 # define ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED /* empty */
47 # define ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED \
48 __attribute__ ((__no_sanitize_undefined__))
51 /* The minimum of two sizes A and B. */
53 min (size_t a
, size_t b
)
55 return (a
< b
? a
: b
);
58 /* A if 32-bit ISAAC, B if 64-bit. This is a macro, not an inline
59 function, to prevent undefined behavior if the unused argument
60 shifts by more than a word width. */
61 #define IF32(a, b) (ISAAC_BITS == 32 ? (a) : (b))
63 /* Discard bits outside the desired range. On typical machines, any
64 decent compiler should optimize this function call away to nothing.
65 But machines with pad bits in integers may need to do more work. */
66 static inline isaac_word
69 isaac_word desired_bits
= ((isaac_word
) 1 << 1 << (ISAAC_BITS
- 1)) - 1;
70 return a
& desired_bits
;
73 /* The index operation. */
74 static inline isaac_word
75 ind (isaac_word
const *m
, isaac_word x
)
77 if (sizeof *m
* CHAR_BIT
== ISAAC_BITS
)
79 /* The typical case, where words are exactly the right size.
80 Optimize this to a mask, an addition, and an indirect
82 void const *void_m
= m
;
83 char const *base_p
= void_m
;
84 void const *word_p
= base_p
+ (x
& ((ISAAC_WORDS
- 1) * sizeof *m
));
85 isaac_word
const *p
= word_p
;
90 /* Atypical machines need more work. */
91 return m
[(x
/ (ISAAC_BITS
/ CHAR_BIT
)) & (ISAAC_WORDS
- 1)];
95 /* Use and update *S to generate random data to fill RESULT. */
96 void ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED
97 isaac_refill (struct isaac_state
*s
, isaac_word result
[ISAAC_WORDS
])
99 /* Caches of S->a and S->b. */
101 isaac_word b
= s
->b
+ (++s
->c
);
103 /* Pointers into state array and into result. */
104 isaac_word
*m
= s
->m
;
105 isaac_word
*r
= result
;
107 enum { HALF
= ISAAC_WORDS
/ 2 };
109 /* The central step. S->m is the whole state array, while M is a
110 pointer to the current word. OFF is the offset from M to the
111 word ISAAC_WORDS/2 words away in the SM array, i.e., +/-
112 ISAAC_WORDS/2. A and B are state variables, and R the result.
113 This updates A, B, M[I], and R[I]. */
114 #define ISAAC_STEP(i, off, mix) \
117 a = (IF32 (a, 0) ^ (mix)) + m[off + (i)]; \
119 m[i] = y = ind (s->m, x) + a + b; \
120 r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \
125 ISAAC_STEP (0, HALF
, IF32 ( a
<< 13, ~ (a
^ (a
<< 21))));
126 ISAAC_STEP (1, HALF
, IF32 (just (a
) >> 6, a
^ (just (a
) >> 5)));
127 ISAAC_STEP (2, HALF
, IF32 ( a
<< 2, a
^ ( a
<< 12)));
128 ISAAC_STEP (3, HALF
, IF32 (just (a
) >> 16, a
^ (just (a
) >> 33)));
131 while ((m
+= 4) < s
->m
+ HALF
);
135 ISAAC_STEP (0, -HALF
, IF32 ( a
<< 13, ~ (a
^ (a
<< 21))));
136 ISAAC_STEP (1, -HALF
, IF32 (just (a
) >> 6, a
^ (just (a
) >> 5)));
137 ISAAC_STEP (2, -HALF
, IF32 ( a
<< 2, a
^ ( a
<< 12)));
138 ISAAC_STEP (3, -HALF
, IF32 (just (a
) >> 16, a
^ (just (a
) >> 33)));
141 while ((m
+= 4) < s
->m
+ ISAAC_WORDS
);
148 * The basic seed-scrambling step for initialization, based on Bob
149 * Jenkins' 256-bit hash.
152 #define mix(a, b, c, d, e, f, g, h) \
154 a ^= b << 11; d += a; \
155 b += c; b ^= just (c) >> 2; e += b; \
156 c += d; c ^= d << 8; f += c; \
157 d += e; d ^= just (e) >> 16; g += d; \
158 e += f; e ^= f << 10; h += e; \
159 f += g; f ^= just (g) >> 4; a += f; \
160 g += h; g ^= h << 8; b += g; \
161 h += a; h ^= just (a) >> 9; c += h; \
165 #define mix(a, b, c, d, e, f, g, h) \
167 a -= e; f ^= just (h) >> 9; h += a; \
168 b -= f; g ^= a << 9; a += b; \
169 c -= g; h ^= just (b) >> 23; b += c; \
170 d -= h; a ^= c << 15; c += d; \
171 e -= a; b ^= just (d) >> 14; d += e; \
172 f -= b; c ^= e << 20; e += f; \
173 g -= c; d ^= just (f) >> 17; f += g; \
174 h -= d; e ^= g << 14; g += h; \
179 /* The basic ISAAC initialization pass. */
180 #define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \
184 for (i = 0; i < ISAAC_WORDS; i += 8) \
194 mix (a, b, c, d, e, f, g, h); \
206 #if 0 /* Provided for reference only; not used in this code */
208 * Initialize the ISAAC RNG with the given seed material.
209 * Its size MUST be a multiple of ISAAC_BYTES, and may be
210 * stored in the s->m array.
212 * This is a generalization of the original ISAAC initialization code
213 * to support larger seed sizes. For seed sizes of 0 and ISAAC_BYTES,
217 isaac_init (struct isaac_state
*s
, isaac_word
const *seed
, size_t seedsize
)
219 isaac_word a
, b
, c
, d
, e
, f
, g
, h
;
221 a
= b
= c
= d
= e
= f
= g
= h
= /* the golden ratio */
222 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
223 for (int i
= 0; i
< 4; i
++) /* scramble it */
224 mix (a
, b
, c
, d
, e
, f
, g
, h
);
225 s
->a
= s
->b
= s
->c
= 0;
229 /* First pass (as in reference ISAAC code) */
230 ISAAC_MIX (s
, a
, b
, c
, d
, e
, f
, g
, h
, seed
);
231 /* Second and subsequent passes (extension to ISAAC) */
232 while (seedsize
-= ISAAC_BYTES
)
235 for (i
= 0; i
< ISAAC_WORDS
; i
++)
237 ISAAC_MIX (s
, a
, b
, c
, d
, e
, f
, g
, h
, s
->m
);
242 /* The no seed case (as in reference ISAAC code) */
243 for (i
= 0; i
< ISAAC_WORDS
; i
++)
248 ISAAC_MIX (s
, a
, b
, c
, d
, e
, f
, g
, h
, s
->m
);
252 /* Initialize *S to a somewhat-random value, derived from a seed
255 isaac_seed (struct isaac_state
*s
)
257 isaac_word a
= IF32 (UINT32_C (0x1367df5a), UINT64_C (0x647c4677a2884b7c));
258 isaac_word b
= IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862));
259 isaac_word c
= IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0));
260 isaac_word d
= IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524));
261 isaac_word e
= IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce));
262 isaac_word f
= IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315));
263 isaac_word g
= IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed));
264 isaac_word h
= IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab));
267 /* The initialization of a through h is a precomputed form of: */
268 a
= b
= c
= d
= e
= f
= g
= h
= /* the golden ratio */
269 IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
270 for (int i
= 0; i
< 4; i
++) /* scramble it */
271 mix (a
, b
, c
, d
, e
, f
, g
, h
);
274 /* Mix S->m so that every part of the seed affects every part of the
276 ISAAC_MIX (s
, a
, b
, c
, d
, e
, f
, g
, h
, s
->m
);
277 ISAAC_MIX (s
, a
, b
, c
, d
, e
, f
, g
, h
, s
->m
);
279 s
->a
= s
->b
= s
->c
= 0;