aboutsummaryrefslogtreecommitdiff
path: root/lmathlib.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-04-06 12:41:29 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-04-06 12:41:29 -0300
commitb8a04658b2787701996b6d787bf3cc256fd667d1 (patch)
tree65d6d6c75fb465878c5440ccb25f8da638c4fcd5 /lmathlib.c
parentb44787652bd3a51dfc2ee92120abe05b28159d32 (diff)
downloadlua-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.c182
1 files changed, 109 insertions, 73 deletions
diff --git a/lmathlib.c b/lmathlib.c
index 3e5ceea4..aa93f4be 100644
--- a/lmathlib.c
+++ b/lmathlib.c
@@ -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
232static int math_type (lua_State *L) { 232static 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 */
271typedef unsigned long long I; 269typedef 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 */
275static I rotl (I x, int n) { 284static 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
279static I nextrand (I *state) { 288static 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
301static lua_Number I2d (I x) { 311static 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;
321typedef unsigned long lu_int32; 331typedef unsigned long lu_int32;
322#endif 332#endif
323 333
334
324/* a 64-bit value */ 335/* a 64-bit value */
325typedef struct I { 336typedef 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
335static 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
356static 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) */ 363static Rand64 Ishl (Rand64 i, int n) {
343static 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
348static I Ixor (I i1, I i2) { 368static 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
352static I Iadd (I i1, I i2) { 373static 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/* 380static 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
363static I Irotli (I i, int n) { 384static Rand64 times9 (Rand64 i) {
364 n = 64 - n; 385 return Iadd(Ishl(i, 3), i); /* i * 9 == (i << 3) + i */
386}
387
388static 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 */
395static 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*/
373static I nextrand (I *state) { 405static 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
415static lua_Number I2d (I x) { 448static 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
422static lua_Unsigned I2UInt (I x) { 455static 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
427static I Int2I (lua_Unsigned n) { 460static 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*/
437typedef struct { 470typedef 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
510static void setseed (I *state, lua_Unsigned n) { 543static 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
519static int math_randomseed (lua_State *L) { 554static 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
533static void setrandfunc (lua_State *L) { 569static 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