gl/lib/rand-isaac.c

   1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64.
   2
   3    Copyright (C) 1999-2024 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 <https://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  * <https://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 /* A if 32-bit ISAAC, B if 64-bit.  This is a macro, not an inline
  52    function, to prevent undefined behavior if the unused argument
  53    shifts by more than a word width.  */
  54 #define IF32(a, b) (ISAAC_BITS == 32 ? (a) : (b))
  55
  56 /* Discard bits outside the desired range.  On typical machines, any
  57    decent compiler should optimize this function call away to nothing.
  58    But machines with pad bits in integers may need to do more work.  */
  59 static inline isaac_word
  60 just (isaac_word a)
  61 {
  62   isaac_word desired_bits = ((isaac_word) 1 << 1 << (ISAAC_BITS - 1)) - 1;
  63   return a & desired_bits;
  64 }
  65
  66 /* The index operation.  */
  67 static inline isaac_word
  68 ind (isaac_word const *m, isaac_word x)
  69 {
  70   if (sizeof *m * CHAR_BIT == ISAAC_BITS)
  71     {
  72       /* The typical case, where words are exactly the right size.
  73          Optimize this to a mask, an addition, and an indirect
  74          load.  */
  75       void const *void_m = m;
  76       char const *base_p = void_m;
  77       void const *word_p = base_p + (x & ((ISAAC_WORDS - 1) * sizeof *m));
  78       isaac_word const *p = word_p;
  79       return *p;
  80     }
  81   else
  82     {
  83       /* Atypical machines need more work.  */
  84       return m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)];
  85     }
  86 }
  87
  88 /* Use and update *S to generate random data to fill RESULT.  */
  89 void ATTRIBUTE_NO_WARN_SANITIZE_UNDEFINED
  90 isaac_refill (struct isaac_state *s, isaac_word result[ISAAC_WORDS])
  91 {
  92   /* Caches of S->a and S->b.  */
  93   isaac_word a = s->a;
  94   isaac_word b = s->b + (++s->c);
  95
  96   /* Pointers into state array and into result.  */
  97   isaac_word *m = s->m;
  98   isaac_word *r = result;
  99
 100   enum { HALF = ISAAC_WORDS / 2 };
 101
 102   /* The central step.  S->m is the whole state array, while M is a
 103      pointer to the current word.  OFF is the offset from M to the
 104      word ISAAC_WORDS/2 words away in the SM array, i.e., +/-
 105      ISAAC_WORDS/2.  A and B are state variables, and R the result.
 106      This updates A, B, M[I], and R[I].  */
 107   #define ISAAC_STEP(i, off, mix)                             \
 108     {                                                         \
 109       isaac_word x, y;                                        \
 110       a = (IF32 (a, 0) ^ (mix)) + m[off + (i)];               \
 111       x = m[i];                                               \
 112       m[i] = y = ind (s->m, x) + a + b;                       \
 113       r[i] = b = just (ind (s->m, y >> ISAAC_WORDS_LOG) + x); \
 114     }
 115
 116   do
 117     {
 118       ISAAC_STEP (0, HALF, IF32 (      a  << 13, ~ (a ^ (a << 21))));
 119       ISAAC_STEP (1, HALF, IF32 (just (a) >>  6, a ^ (just (a) >>  5)));
 120       ISAAC_STEP (2, HALF, IF32 (      a  <<  2, a ^ (      a  << 12)));
 121       ISAAC_STEP (3, HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
 122       r += 4;
 123     }
 124   while ((m += 4) < s->m + HALF);
 125
 126   do
 127     {
 128       ISAAC_STEP (0, -HALF, IF32 (      a  << 13, ~ (a ^ (a << 21))));
 129       ISAAC_STEP (1, -HALF, IF32 (just (a) >>  6, a ^ (just (a) >>  5)));
 130       ISAAC_STEP (2, -HALF, IF32 (      a  <<  2, a ^ (      a  << 12)));
 131       ISAAC_STEP (3, -HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));
 132       r += 4;
 133     }
 134   while ((m += 4) < s->m + ISAAC_WORDS);
 135
 136   s->a = a;
 137   s->b = b;
 138 }
 139
 140 /*
 141  * The basic seed-scrambling step for initialization, based on Bob
 142  * Jenkins' 256-bit hash.
 143  */
 144 #if ISAAC_BITS == 32
 145  #define mix(a, b, c, d, e, f, g, h)       \
 146     {                                      \
 147               a ^=       b  << 11; d += a; \
 148       b += c; b ^= just (c) >>  2; e += b; \
 149       c += d; c ^=       d  <<  8; f += c; \
 150       d += e; d ^= just (e) >> 16; g += d; \
 151       e += f; e ^=       f  << 10; h += e; \
 152       f += g; f ^= just (g) >>  4; a += f; \
 153       g += h; g ^=       h  <<  8; b += g; \
 154       h += a; h ^= just (a) >>  9; c += h; \
 155       a += b;                              \
 156     }
 157 #else
 158  #define mix(a, b, c, d, e, f, g, h)       \
 159     {                                      \
 160       a -= e; f ^= just (h) >>  9; h += a; \
 161       b -= f; g ^=       a  <<  9; a += b; \
 162       c -= g; h ^= just (b) >> 23; b += c; \
 163       d -= h; a ^=       c  << 15; c += d; \
 164       e -= a; b ^= just (d) >> 14; d += e; \
 165       f -= b; c ^=       e  << 20; e += f; \
 166       g -= c; d ^= just (f) >> 17; f += g; \
 167       h -= d; e ^=       g  << 14; g += h; \
 168     }
 169 #endif
 170
 171
 172 /* The basic ISAAC initialization pass.  */
 173 #define ISAAC_MIX(s, a, b, c, d, e, f, g, h, seed) \
 174   {                                                \
 175     int i;                                         \
 176                                                    \
 177     for (i = 0; i < ISAAC_WORDS; i += 8)           \
 178       {                                            \
 179         a += seed[i];                              \
 180         b += seed[i + 1];                          \
 181         c += seed[i + 2];                          \
 182         d += seed[i + 3];                          \
 183         e += seed[i + 4];                          \
 184         f += seed[i + 5];                          \
 185         g += seed[i + 6];                          \
 186         h += seed[i + 7];                          \
 187         mix (a, b, c, d, e, f, g, h);              \
 188         s->m[i] = a;                               \
 189         s->m[i + 1] = b;                           \
 190         s->m[i + 2] = c;                           \
 191         s->m[i + 3] = d;                           \
 192         s->m[i + 4] = e;                           \
 193         s->m[i + 5] = f;                           \
 194         s->m[i + 6] = g;                           \
 195         s->m[i + 7] = h;                           \
 196       }                                            \
 197   }
 198
 199 #if 0 /* Provided for reference only; not used in this code */
 200 /*
 201  * Initialize the ISAAC RNG with the given seed material.
 202  * Its size MUST be a multiple of ISAAC_BYTES, and may be
 203  * stored in the s->m array.
 204  *
 205  * This is a generalization of the original ISAAC initialization code
 206  * to support larger seed sizes.  For seed sizes of 0 and ISAAC_BYTES,
 207  * it is identical.
 208  */
 209 static void
 210 isaac_init (struct isaac_state *s, isaac_word const *seed, size_t seedsize)
 211 {
 212   isaac_word a, b, c, d, e, f, g, h;
 213
 214   a = b = c = d = e = f = g = h =          /* the golden ratio */
 215     IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
 216   for (int i = 0; i < 4; i++)              /* scramble it */
 217     mix (a, b, c, d, e, f, g, h);
 218   s->a = s->b = s->c = 0;
 219
 220   if (seedsize)
 221     {
 222       /* First pass (as in reference ISAAC code) */
 223       ISAAC_MIX (s, a, b, c, d, e, f, g, h, seed);
 224       /* Second and subsequent passes (extension to ISAAC) */
 225       while (seedsize -= ISAAC_BYTES)
 226         {
 227           seed += ISAAC_WORDS;
 228           for (i = 0; i < ISAAC_WORDS; i++)
 229             s->m[i] += seed[i];
 230           ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 231         }
 232     }
 233   else
 234     {
 235       /* The no seed case (as in reference ISAAC code) */
 236       for (i = 0; i < ISAAC_WORDS; i++)
 237         s->m[i] = 0;
 238     }
 239
 240   /* Final pass */
 241   ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 242 }
 243 #endif
 244
 245 /* Initialize *S to a somewhat-random value, derived from a seed
 246    stored in S->m.  */
 247 void
 248 isaac_seed (struct isaac_state *s)
 249 {
 250   isaac_word a = IF32 (UINT32_C (0x1367df5a), UINT64_C (0x647c4677a2884b7c));
 251   isaac_word b = IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862));
 252   isaac_word c = IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0));
 253   isaac_word d = IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524));
 254   isaac_word e = IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce));
 255   isaac_word f = IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315));
 256   isaac_word g = IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed));
 257   isaac_word h = IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab));
 258
 259 #if 0
 260   /* The initialization of a through h is a precomputed form of: */
 261   a = b = c = d = e = f = g = h =          /* the golden ratio */
 262     IF32 (UINT32_C (0x9e3779b9), UINT64_C (0x9e3779b97f4a7c13));
 263   for (int i = 0; i < 4; i++)              /* scramble it */
 264     mix (a, b, c, d, e, f, g, h);
 265 #endif
 266
 267   /* Mix S->m so that every part of the seed affects every part of the
 268      state.  */
 269   ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 270   ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);
 271
 272   s->a = s->b = s->c = 0;
 273 }