gl/lib/rand-isaac.c

   1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64.
   2
   3    Copyright (C) 1999-2017 Free Software Foundation, Inc.
   4    Copyright (C) 1997, 1998, 1999 Colin Plumb.
   5
   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.
  10
  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.
  15
  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/>.
  18
  19    Written by Colin Plumb and Paul Eggert.  */
  20
  21 /*
  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.
  26  *
  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  * --------------------------------------------------------------------
  32  */
  33 #include <config.h>
  34
  35 #include "rand-isaac.h"
  36
  37 #include <limits.h>
  38 #include <string.h>
  39
  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 */
  46 #else
  47 # define ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED \
  48   __attribute__ ((__no_sanitize_undefined__))
  49 #endif
  50
  51 /* The minimum of two sizes A and B.  */
  52 static inline size_t
  53 min (size_t a, size_t b)
  54 {
  55   return (a < b ? a : b);
  56 }
  57
  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))
  62
  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
  67 just (isaac_word a)
  68 {
  69   isaac_word desired_bits = ((isaac_word) 1 << 1 << (ISAAC_BITS - 1)) - 1;
  70   return a & desired_bits;
  71 }
  72
  73 /* The index operation.  */
  74 static inline isaac_word
  75 ind (isaac_word const *m, isaac_word x)
  76 {
  77   if (sizeof *m * CHAR_BIT == ISAAC_BITS)
  78     {
  79       /* The typical case, where words are exactly the right size.
  80          Optimize this to a mask, an addition, and an indirect
  81          load.  */
  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;
  86       return *p;
  87     }
  88   else
  89     {
  90       /* Atypical machines need more work.  */
  91       return m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)];
  92     }
  93 }
  94
  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])
  98 {
  99   /* Caches of S->a and S->b.  */
 100   isaac_word a = s->a;
 101   isaac_word b = s->b + (++s->c);
 102
 103   /* Pointers into state array and into result.  */
 104   isaac_word *m = s->m;
 105   isaac_word *r = result;
 106
 107   enum { HALF = ISAAC_WORDS / 2 };
 108
 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)                             \
 115     {                                                         \
 116       isaac_word x, y;                                        \
 117       a = (IF32 (a, 0) ^ (mix)) + m[off + (i)];               \
 118       x = m[i];                                               \
 119       m[i] = y = ind (s->m, x) + a + b;                       \
 120       r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \
 121     }
 122
 123   do
 124     {
 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)));
 129       r += 4;
 130     }
 131   while ((m += 4) < s->m + HALF);
 132
 133   do
 134     {
 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)));
 139       r += 4;
 140     }
 141   while ((m += 4) < s->m + ISAAC_WORDS);
 142
 143   s->a = a;
 144   s->b = b;
 145 }
 146
 147 /*
 148  * The basic seed-scrambling step for initialization, based on Bob
 149  * Jenkins' 256-bit hash.
 150  */
 151 #if ISAAC_BITS == 32
 152  #define mix(a, b, c, d, e, f, g, h)       \
 153     {                                      \
 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; \
 162       a += b;                              \
 163     }
 164 #else
 165  #define mix(a, b, c, d, e, f, g, h)       \
 166     {                                      \
 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; \
 175     }
 176 #endif
 177
 178
 179 /* The basic ISAAC initialization pass.  */
 180 #define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \
 181   {                                                \
 182     int i;                                         \
 183                                                    \
 184     for (i = 0; i < ISAAC_WORDS; i += 8)           \
 185       {                                            \
 186         a += seed[i];                              \
 187         b += seed[i + 1];                          \
 188         c += seed[i + 2];                          \
 189         d += seed[i + 3];                          \
 190         e += seed[i + 4];                          \
 191         f += seed[i + 5];                          \
 192         g += seed[i + 6];                          \
 193         h += seed[i + 7];                          \
 194         mix (a, b, c, d, e, f, g, h);              \
 195         s->m[i] = a;                               \
 196         s->m[i + 1] = b;                           \
 197         s->m[i + 2] = c;                           \
 198         s->m[i + 3] = d;                           \
 199         s->m[i + 4] = e;                           \
 200         s->m[i + 5] = f;                           \
 201         s->m[i + 6] = g;                           \
 202         s->m[i + 7] = h;                           \
 203       }                                            \
 204   }
 205
 206 #if 0 /* Provided for reference only; not used in this code */
 207 /*
 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.
 211  *
 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,
 214  * it is identical.
 215  */
 216 static void
 217 isaac_init (struct isaac_state *s, isaac_word const *seed, size_t seedsize)
 218 {
 219   isaac_word a, b, c, d, e, f, g, h;
 220
 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;
 226
 227   if (seedsize)
 228     {
 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)
 233         {
 234           seed += ISAAC_WORDS;
 235           for (i = 0; i < ISAAC_WORDS; i++)
 236             s->m[i] += seed[i];
 237           ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 238         }
 239     }
 240   else
 241     {
 242       /* The no seed case (as in reference ISAAC code) */
 243       for (i = 0; i < ISAAC_WORDS; i++)
 244         s->m[i] = 0;
 245     }
 246
 247   /* Final pass */
 248   ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 249 }
 250 #endif
 251
 252 /* Initialize *S to a somewhat-random value, derived from a seed
 253    stored in S->m.  */
 254 void
 255 isaac_seed (struct isaac_state *s)
 256 {
 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));
 265
 266 #if 0
 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);
 272 #endif
 273
 274   /* Mix S->m so that every part of the seed affects every part of the
 275      state.  */
 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);
 278
 279   s->a = s->b = s->c = 0;
 280 }