diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-04-06 12:41:29 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-04-06 12:41:29 -0300 |
commit | b8a04658b2787701996b6d787bf3cc256fd667d1 (patch) | |
tree | 65d6d6c75fb465878c5440ccb25f8da638c4fcd5 /lmathlib.c | |
parent | b44787652bd3a51dfc2ee92120abe05b28159d32 (diff) | |
download | lua-b8a04658b2787701996b6d787bf3cc256fd667d1.tar.gz lua-b8a04658b2787701996b6d787bf3cc256fd667d1.tar.bz2 lua-b8a04658b2787701996b6d787bf3cc256fd667d1.zip |
PRNG changed from 'xoroshiro128+' to 'xoshiro256**' + "I' renamed 'Rand64'
+ implementation can use integer types larger than 64 (or 32) bits
Diffstat (limited to 'lmathlib.c')
-rw-r--r-- | lmathlib.c | 182 |
1 files changed, 109 insertions, 73 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lmathlib.c,v 1.128 2018/03/26 19:48:46 roberto Exp $ | 2 | ** $Id: lmathlib.c,v 1.129 2018/04/04 16:12:53 roberto Exp roberto $ |
3 | ** Standard mathematical library | 3 | ** Standard mathematical library |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -230,12 +230,8 @@ static int math_max (lua_State *L) { | |||
230 | 230 | ||
231 | 231 | ||
232 | static int math_type (lua_State *L) { | 232 | static int math_type (lua_State *L) { |
233 | if (lua_type(L, 1) == LUA_TNUMBER) { | 233 | if (lua_type(L, 1) == LUA_TNUMBER) |
234 | if (lua_isinteger(L, 1)) | 234 | lua_pushstring(L, (lua_isinteger(L, 1)) ? "integer" : "float"); |
235 | lua_pushliteral(L, "integer"); | ||
236 | else | ||
237 | lua_pushliteral(L, "float"); | ||
238 | } | ||
239 | else { | 235 | else { |
240 | luaL_checkany(L, 1); | 236 | luaL_checkany(L, 1); |
241 | lua_pushnil(L); | 237 | lua_pushnil(L); |
@@ -247,7 +243,7 @@ static int math_type (lua_State *L) { | |||
247 | 243 | ||
248 | /* | 244 | /* |
249 | ** {================================================================== | 245 | ** {================================================================== |
250 | ** Pseudo-Random Number Generator based on 'xoroshiro128+'. | 246 | ** Pseudo-Random Number Generator based on 'xoshiro256**'. |
251 | ** =================================================================== | 247 | ** =================================================================== |
252 | */ | 248 | */ |
253 | 249 | ||
@@ -261,29 +257,43 @@ static int math_type (lua_State *L) { | |||
261 | #endif | 257 | #endif |
262 | 258 | ||
263 | 259 | ||
264 | #if !defined(LUA_USE_C89) && defined(LLONG_MAX) && !defined(LUA_DEBUG) /* { */ | 260 | #if (!defined(LUA_USE_C89) && defined(LLONG_MAX) && !defined(LUA_DEBUG)) \ |
261 | || defined(Rand64) /* { */ | ||
265 | 262 | ||
266 | /* | 263 | /* |
267 | ** Assume long long. | 264 | ** Assume long long. |
268 | */ | 265 | */ |
269 | 266 | ||
267 | #if !defined(Rand64) | ||
270 | /* a 64-bit value */ | 268 | /* a 64-bit value */ |
271 | typedef unsigned long long I; | 269 | typedef unsigned long long Rand64; |
270 | #endif | ||
271 | |||
272 | |||
273 | /* | ||
274 | ** If 'Rand64' has more than 64 bits, the extra bits do not interfere | ||
275 | ** with the 64 initial bits, except in a right shift. Otherwise, we just | ||
276 | ** have to make sure we never use them. | ||
277 | */ | ||
278 | |||
279 | /* avoid using extra bits when needed */ | ||
280 | #define trim64(x) ((x) & 0xffffffffffffffff) | ||
272 | 281 | ||
273 | 282 | ||
274 | /* rotate left 'x' by 'n' bits */ | 283 | /* rotate left 'x' by 'n' bits */ |
275 | static I rotl (I x, int n) { | 284 | static Rand64 rotl (Rand64 x, int n) { |
276 | return (x << n) | (x >> (64 - n)); | 285 | return (x << n) | (trim64(x) >> (64 - n)); |
277 | } | 286 | } |
278 | 287 | ||
279 | static I nextrand (I *state) { | 288 | static Rand64 nextrand (Rand64 *state) { |
280 | I s0 = state[0]; | 289 | Rand64 res = rotl(state[0] * 5, 7) * 9; |
281 | I s1 = state[1]; | 290 | Rand64 t = state[1] << 17; |
282 | I res = s0 + s1; | 291 | state[2] ^= state[0]; |
283 | res = rotl(res, 41); /* extra step to change place of lower bits */ | 292 | state[3] ^= state[1]; |
284 | s1 = s1 ^ s0; | 293 | state[1] ^= state[2]; |
285 | state[0] = rotl(s0, 55) ^ (s1 ^ (s1 << 14)); | 294 | state[0] ^= state[3]; |
286 | state[1] = rotl(s1, 36); | 295 | state[2] ^= t; |
296 | state[3] = rotl(state[3], 45); | ||
287 | return res; | 297 | return res; |
288 | } | 298 | } |
289 | 299 | ||
@@ -298,15 +308,15 @@ static I nextrand (I *state) { | |||
298 | #define maskFIG (~(~1LLU << (FIGS - 1))) /* use FIGS bits */ | 308 | #define maskFIG (~(~1LLU << (FIGS - 1))) /* use FIGS bits */ |
299 | #define shiftFIG (l_mathop(0.5) / (1LLU << (FIGS - 1))) /* 2^(-FIGS) */ | 309 | #define shiftFIG (l_mathop(0.5) / (1LLU << (FIGS - 1))) /* 2^(-FIGS) */ |
300 | 310 | ||
301 | static lua_Number I2d (I x) { | 311 | static lua_Number I2d (Rand64 x) { |
302 | return (lua_Number)(x & maskFIG) * shiftFIG; | 312 | return (lua_Number)(x & maskFIG) * shiftFIG; |
303 | } | 313 | } |
304 | 314 | ||
305 | /* convert an 'I' to a lua_Unsigned */ | 315 | /* convert a 'Rand64' to a 'lua_Unsigned' */ |
306 | #define I2UInt(x) ((lua_Unsigned)(x)) | 316 | #define I2UInt(x) ((lua_Unsigned)trim64(x)) |
307 | 317 | ||
308 | /* convert a lua_Unsigned to an 'I' */ | 318 | /* convert a 'lua_Unsigned' to an 'Rand64' */ |
309 | #define Int2I(x) ((I)(x)) | 319 | #define Int2I(x) ((Rand64)(x)) |
310 | 320 | ||
311 | 321 | ||
312 | #else /* no long long }{ */ | 322 | #else /* no long long }{ */ |
@@ -321,69 +331,92 @@ typedef unsigned int lu_int32; | |||
321 | typedef unsigned long lu_int32; | 331 | typedef unsigned long lu_int32; |
322 | #endif | 332 | #endif |
323 | 333 | ||
334 | |||
324 | /* a 64-bit value */ | 335 | /* a 64-bit value */ |
325 | typedef struct I { | 336 | typedef struct Rand64 { |
326 | lu_int32 h; /* higher half */ | 337 | lu_int32 h; /* higher half */ |
327 | lu_int32 l; /* lower half */ | 338 | lu_int32 l; /* lower half */ |
328 | } I; | 339 | } Rand64; |
329 | 340 | ||
330 | 341 | ||
331 | /* | 342 | /* |
332 | ** basic operations on 'I' values | 343 | ** If 'lu_int32' has more than 32 bits, the extra bits do not interfere |
344 | ** with the 32 initial bits, except in a right shift and comparisons. | ||
345 | ** Otherwise, we just have to make sure we never use them. | ||
333 | */ | 346 | */ |
334 | 347 | ||
335 | static I packI (lu_int32 h, lu_int32 l) { | 348 | /* avoid using extra bits when needed */ |
336 | I result; | 349 | #define trim32(x) ((x) & 0xffffffff) |
350 | |||
351 | |||
352 | /* | ||
353 | ** basic operations on 'Rand64' values | ||
354 | */ | ||
355 | |||
356 | static Rand64 packI (lu_int32 h, lu_int32 l) { | ||
357 | Rand64 result; | ||
337 | result.h = h; | 358 | result.h = h; |
338 | result.l = l; | 359 | result.l = l; |
339 | return result; | 360 | return result; |
340 | } | 361 | } |
341 | 362 | ||
342 | /* i ^ (i << n) */ | 363 | static Rand64 Ishl (Rand64 i, int n) { |
343 | static I Ixorshl (I i, int n) { | ||
344 | lua_assert(n > 0 && n < 32); | 364 | lua_assert(n > 0 && n < 32); |
345 | return packI(i.h ^ ((i.h << n) | (i.l >> (32 - n))), i.l ^ (i.l << n)); | 365 | return packI((i.h << n) | (trim32(i.l) >> (32 - n)), i.l << n); |
346 | } | 366 | } |
347 | 367 | ||
348 | static I Ixor (I i1, I i2) { | 368 | static void Ixor (Rand64 *i1, Rand64 i2) { |
349 | return packI(i1.h ^ i2.h, i1.l ^ i2.l); | 369 | i1->h ^= i2.h; |
370 | i1->l ^= i2.l; | ||
350 | } | 371 | } |
351 | 372 | ||
352 | static I Iadd (I i1, I i2) { | 373 | static Rand64 Iadd (Rand64 i1, Rand64 i2) { |
353 | I result = packI(i1.h + i2.h, i1.l + i2.l); | 374 | Rand64 result = packI(i1.h + i2.h, i1.l + i2.l); |
354 | if (result.l < i1.l) /* carry? */ | 375 | if (trim32(result.l) < trim32(i1.l)) /* carry? */ |
355 | result.h++; | 376 | result.h++; |
356 | return result; | 377 | return result; |
357 | } | 378 | } |
358 | 379 | ||
359 | /* | 380 | static Rand64 times5 (Rand64 i) { |
360 | ** Rotate left. As all offsets here are larger than 32, do a rotate right | 381 | return Iadd(Ishl(i, 2), i); /* i * 5 == (i << 2) + i */ |
361 | ** of 64 - offset. | 382 | } |
362 | */ | 383 | |
363 | static I Irotli (I i, int n) { | 384 | static Rand64 times9 (Rand64 i) { |
364 | n = 64 - n; | 385 | return Iadd(Ishl(i, 3), i); /* i * 9 == (i << 3) + i */ |
386 | } | ||
387 | |||
388 | static Rand64 rotl (Rand64 i, int n) { | ||
365 | lua_assert(n > 0 && n < 32); | 389 | lua_assert(n > 0 && n < 32); |
366 | return packI((i.h >> n) | (i.l << (32 - n)), | 390 | return packI((i.h << n) | (trim32(i.l) >> (32 - n)), |
367 | (i.h << (32 - n)) | (i.l >> n)); | 391 | (trim32(i.h) >> (32 - n)) | (i.l << n)); |
392 | } | ||
393 | |||
394 | /* for offsets larger than 32, rotate right by 64 - offset */ | ||
395 | static Rand64 rotl1 (Rand64 i, int n) { | ||
396 | lua_assert(n > 32 && n < 64); | ||
397 | n = 64 - n; | ||
398 | return packI((trim32(i.h) >> n) | (i.l << (32 - n)), | ||
399 | (i.h << (32 - n)) | (trim32(i.l) >> n)); | ||
368 | } | 400 | } |
369 | 401 | ||
370 | /* | 402 | /* |
371 | ** implementation of 'xoroshiro128+' algorithm on 'I' values | 403 | ** implementation of 'xoshiro256**' algorithm on 'Rand64' values |
372 | */ | 404 | */ |
373 | static I nextrand (I *state) { | 405 | static Rand64 nextrand (Rand64 *state) { |
374 | I s0 = state[0]; | 406 | Rand64 res = times9(rotl(times5(state[0]), 7)); |
375 | I s1 = state[1]; | 407 | Rand64 t = Ishl(state[1], 17); |
376 | I res = Iadd(s0, s1); | 408 | Ixor(&state[2], state[0]); |
377 | res = Irotli(res, 41); | 409 | Ixor(&state[3], state[1]); |
378 | s1 = Ixor(s1, s0); | 410 | Ixor(&state[1], state[2]); |
379 | state[0] = Ixor(Irotli(s0, 55), Ixorshl(s1, 14)); | 411 | Ixor(&state[0], state[3]); |
380 | state[1] = Irotli(s1, 36); | 412 | Ixor(&state[2], t); |
413 | state[3] = rotl1(state[3], 45); | ||
381 | return res; | 414 | return res; |
382 | } | 415 | } |
383 | 416 | ||
384 | 417 | ||
385 | /* | 418 | /* |
386 | ** Converts an 'I' into a float. | 419 | ** Converts an 'Rand64' into a float. |
387 | */ | 420 | */ |
388 | 421 | ||
389 | /* an unsigned 1 with proper type */ | 422 | /* an unsigned 1 with proper type */ |
@@ -402,8 +435,8 @@ static I nextrand (I *state) { | |||
402 | /* use FIGS - 32 bits from higher half */ | 435 | /* use FIGS - 32 bits from higher half */ |
403 | #define maskHI (~(~UONE << (FIGS - 33))) | 436 | #define maskHI (~(~UONE << (FIGS - 33))) |
404 | 437 | ||
405 | /* use all bits from lower half */ | 438 | /* use 32 bits from lower half */ |
406 | #define maskLOW (~(lu_int32)0) | 439 | #define maskLOW (~(~UONE << 31)) |
407 | 440 | ||
408 | /* 2^(-FIGS) == (1 / 2^33) / 2^(FIGS-33) */ | 441 | /* 2^(-FIGS) == (1 / 2^33) / 2^(FIGS-33) */ |
409 | #define shiftFIG ((lua_Number)(1.0 / 8589934592.0) / (UONE << (FIGS - 33))) | 442 | #define shiftFIG ((lua_Number)(1.0 / 8589934592.0) / (UONE << (FIGS - 33))) |
@@ -412,30 +445,30 @@ static I nextrand (I *state) { | |||
412 | 445 | ||
413 | #define twoto32 l_mathop(4294967296.0) /* 2^32 */ | 446 | #define twoto32 l_mathop(4294967296.0) /* 2^32 */ |
414 | 447 | ||
415 | static lua_Number I2d (I x) { | 448 | static lua_Number I2d (Rand64 x) { |
416 | lua_Number h = (lua_Number)(x.h & maskHI); | 449 | lua_Number h = (lua_Number)(x.h & maskHI); |
417 | lua_Number l = (lua_Number)(x.l & maskLOW); | 450 | lua_Number l = (lua_Number)(x.l & maskLOW); |
418 | return (h * twoto32 + l) * shiftFIG; | 451 | return (h * twoto32 + l) * shiftFIG; |
419 | } | 452 | } |
420 | 453 | ||
421 | 454 | ||
422 | static lua_Unsigned I2UInt (I x) { | 455 | static lua_Unsigned I2UInt (Rand64 x) { |
423 | return ((lua_Unsigned)x.h << 31 << 1) | (lua_Unsigned)x.l; | 456 | return ((lua_Unsigned)x.h << 31 << 1) | (lua_Unsigned)trim32(x.l); |
424 | } | 457 | } |
425 | 458 | ||
426 | 459 | ||
427 | static I Int2I (lua_Unsigned n) { | 460 | static Rand64 Int2I (lua_Unsigned n) { |
428 | return packI((lu_int32)(n >> 31 >> 1), (lu_int32)n & ~(lu_int32)0); | 461 | return packI((lu_int32)(n >> 31 >> 1), (lu_int32)n); |
429 | } | 462 | } |
430 | 463 | ||
431 | #endif /* } */ | 464 | #endif /* } */ |
432 | 465 | ||
433 | 466 | ||
434 | /* | 467 | /* |
435 | ** A state uses two 'I' values. | 468 | ** A state uses four 'Rand64' values. |
436 | */ | 469 | */ |
437 | typedef struct { | 470 | typedef struct { |
438 | I s[2]; | 471 | Rand64 s[4]; |
439 | } RanState; | 472 | } RanState; |
440 | 473 | ||
441 | 474 | ||
@@ -476,7 +509,7 @@ static int math_random (lua_State *L) { | |||
476 | lua_Integer low, up; | 509 | lua_Integer low, up; |
477 | lua_Unsigned p; | 510 | lua_Unsigned p; |
478 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); | 511 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); |
479 | I rv = nextrand(state->s); /* next pseudo-random value */ | 512 | Rand64 rv = nextrand(state->s); /* next pseudo-random value */ |
480 | switch (lua_gettop(L)) { /* check number of arguments */ | 513 | switch (lua_gettop(L)) { /* check number of arguments */ |
481 | case 0: { /* no arguments */ | 514 | case 0: { /* no arguments */ |
482 | lua_pushnumber(L, I2d(rv)); /* float between 0 and 1 */ | 515 | lua_pushnumber(L, I2d(rv)); /* float between 0 and 1 */ |
@@ -507,10 +540,12 @@ static int math_random (lua_State *L) { | |||
507 | } | 540 | } |
508 | 541 | ||
509 | 542 | ||
510 | static void setseed (I *state, lua_Unsigned n) { | 543 | static void setseed (Rand64 *state, lua_Unsigned n1, lua_Unsigned n2) { |
511 | int i; | 544 | int i; |
512 | state[0] = Int2I(n); | 545 | state[0] = Int2I(n1); |
513 | state[1] = Int2I(0xff); /* avoid a zero state */ | 546 | state[1] = Int2I(0xff); /* avoid a zero state */ |
547 | state[2] = Int2I(n2); | ||
548 | state[3] = Int2I(0); | ||
514 | for (i = 0; i < 16; i++) | 549 | for (i = 0; i < 16; i++) |
515 | nextrand(state); /* discard initial values to "spread" seed */ | 550 | nextrand(state); /* discard initial values to "spread" seed */ |
516 | } | 551 | } |
@@ -518,8 +553,9 @@ static void setseed (I *state, lua_Unsigned n) { | |||
518 | 553 | ||
519 | static int math_randomseed (lua_State *L) { | 554 | static int math_randomseed (lua_State *L) { |
520 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); | 555 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); |
521 | lua_Integer n = luaL_checkinteger(L, 1); | 556 | lua_Integer n1 = luaL_checkinteger(L, 1); |
522 | setseed(state->s, n); | 557 | lua_Integer n2 = luaL_optinteger(L, 2, 0); |
558 | setseed(state->s, n1, n2); | ||
523 | return 0; | 559 | return 0; |
524 | } | 560 | } |
525 | 561 | ||
@@ -532,7 +568,7 @@ static const luaL_Reg randfuncs[] = { | |||
532 | 568 | ||
533 | static void setrandfunc (lua_State *L) { | 569 | static void setrandfunc (lua_State *L) { |
534 | RanState *state = (RanState *)lua_newuserdatauv(L, sizeof(RanState), 0); | 570 | RanState *state = (RanState *)lua_newuserdatauv(L, sizeof(RanState), 0); |
535 | setseed(state->s, 0); | 571 | setseed(state->s, 0, 0); |
536 | luaL_setfuncs(L, randfuncs, 1); | 572 | luaL_setfuncs(L, randfuncs, 1); |
537 | } | 573 | } |
538 | 574 | ||