OpenCoverage

rand-isaac.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/rand-isaac.c

Source code

Switch to Preprocessed file

Line Source Count

1 /* Bob Jenkins's cryptographic random number generators, ISAAC and ISAAC64. -

2 -

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 * <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 /* 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; -

return a & desired_bits;

executed 815872 times by 7 tests: return a & desired_bits;

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

815872

64 } -

65 -

66 /* The index operation. */ -

67 static inline isaac_word -

68 ind (isaac_word const *m, isaac_word x) -

69 { -

if (sizeof *m * CHAR_BIT == ISAAC_BITS)

sizeof m 8 == (1 << 6)	Description
TRUE	evaluated 866304 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort
FALSE	never evaluated

0-866304

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

return *p;

executed 866304 times by 7 tests: return *p;

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

866304

80 } -

81 else -

82 { -

83 /* Atypical machines need more work. */ -

return m[(x / (ISAAC_BITS / CHAR_BIT)) & (ISAAC_WORDS - 1)];

never executed: return m[(x / ((1 << 6) / 8)) & ((1 << 8) - 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))));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

119

ISAAC_STEP (1, HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

120

ISAAC_STEP (2, HALF, IF32 ( a << 2, a ^ ( a << 12)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

121

ISAAC_STEP (3, HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

122 r += 4; -

123

}

executed 54144 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

54144

124

while ((m += 4) < s->m + HALF);

(m += 4) < s->m + HALF	Description
TRUE	evaluated 52452 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort
FALSE	evaluated 1692 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

1692-52452

125 -

126 do -

127 { -

128

ISAAC_STEP (0, -HALF, IF32 ( a << 13, ~ (a ^ (a << 21))));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

129

ISAAC_STEP (1, -HALF, IF32 (just (a) >> 6, a ^ (just (a) >> 5)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

130

ISAAC_STEP (2, -HALF, IF32 ( a << 2, a ^ ( a << 12)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

131

ISAAC_STEP (3, -HALF, IF32 (just (a) >> 16, a ^ (just (a) >> 33)));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 54144 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-54144

132 r += 4; -

133

}

executed 54144 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

54144

134

while ((m += 4) < s->m + ISAAC_WORDS);

(m += 4) < s->m + (1 << 8)	Description
TRUE	evaluated 52452 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort
FALSE	evaluated 1692 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

1692-52452

135 -

136 s->a = a; -

137 s->b = b; -

138

}

executed 1692 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

1692

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

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

251

isaac_word b = IF32 (UINT32_C (0x95d90059), UINT64_C (0xb9f8b322c73ac862));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

252

isaac_word c = IF32 (UINT32_C (0xc3163e4b), UINT64_C (0x8c0ea5053d4712a0));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

253

isaac_word d = IF32 (UINT32_C (0x0f421ad8), UINT64_C (0xb29b2e824a595524));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

254

isaac_word e = IF32 (UINT32_C (0xd92a4a78), UINT64_C (0x82f053db8355e0ce));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

255

isaac_word f = IF32 (UINT32_C (0xa51a3c49), UINT64_C (0x48fe4a0fa5a09315));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

256

isaac_word g = IF32 (UINT32_C (0xc4efea1b), UINT64_C (0xae985bf2cbfc89ed));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

257

isaac_word h = IF32 (UINT32_C (0x30609119), UINT64_C (0x98f5704f6c44c0ab));

(1 << 6) == 32	Description
TRUE	never evaluated
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

0-649

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

executed 20768 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

i < (1 << 8)	Description
TRUE	evaluated 20768 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

649-20768

270

ISAAC_MIX (s, a, b, c, d, e, f, g, h, s->m);

executed 20768 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

i < (1 << 8)	Description
TRUE	evaluated 20768 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort
FALSE	evaluated 649 times by 7 tests Evaluated by: cp ln mktemp mv shred shuf sort

649-20768

271 -

272 s->a = s->b = s->c = 0; -

273

}

executed 649 times by 7 tests: end of block

Executed by:

cp
ln
mktemp
mv
shred
shuf
sort

649

Source code

Switch to Preprocessed file

Generated by Squish Coco 4.1.2