fixes #2472 (Update liblua to 5.4)

1 files changed, 393 insertions, 40 deletions

diff --git a/libs/liblua/src/lmathlib.c b/libs/liblua/src/lmathlib.c
index 7ef7e593fd..86def470c4 100644
--- a/libs/liblua/src/lmathlib.c
+++ b/libs/liblua/src/lmathlib.c
@@ -1,5 +1,5 @@
 /*
-** $Id: lmathlib.c,v 1.119.1.1 2017/04/19 17:20:42 roberto Exp $
+** $Id: lmathlib.c $
 ** Standard mathematical library
 ** See Copyright Notice in lua.h
 */
@@ -10,8 +10,11 @@
 #include "lprefix.h"
 
 
-#include <stdlib.h>
+#include <float.h>
+#include <limits.h>
 #include <math.h>
+#include <stdlib.h>
+#include <time.h>
 
 #include "lua.h"
 
@@ -23,19 +26,6 @@
 #define PI	(l_mathop(3.141592653589793238462643383279502884))
 
 
-#if !defined(l_rand)		/* { */
-#if defined(LUA_USE_POSIX)
-#define l_rand()	random()
-#define l_srand(x)	srandom(x)
-#define L_RANDMAX	2147483647	/* (2^31 - 1), following POSIX */
-#else
-#define l_rand()	rand()
-#define l_srand(x)	srand(x)
-#define L_RANDMAX	RAND_MAX
-#endif
-#endif				/* } */
-
-
 static int math_abs (lua_State *L) {
   if (lua_isinteger(L, 1)) {
     lua_Integer n = lua_tointeger(L, 1);
@@ -87,7 +77,7 @@ static int math_toint (lua_State *L) {
     lua_pushinteger(L, n);
   else {
     luaL_checkany(L, 1);
-    lua_pushnil(L);  /* value is not convertible to integer */
+    luaL_pushfail(L);  /* value is not convertible to integer */
   }
   return 1;
 }
@@ -239,22 +229,347 @@ static int math_max (lua_State *L) {
   return 1;
 }
 
+
+static int math_type (lua_State *L) {
+  if (lua_type(L, 1) == LUA_TNUMBER)
+    lua_pushstring(L, (lua_isinteger(L, 1)) ? "integer" : "float");
+  else {
+    luaL_checkany(L, 1);
+    luaL_pushfail(L);
+  }
+  return 1;
+}
+
+
+
+/*
+** {==================================================================
+** Pseudo-Random Number Generator based on 'xoshiro256**'.
+** ===================================================================
+*/
+
+/* number of binary digits in the mantissa of a float */
+#define FIGS	l_floatatt(MANT_DIG)
+
+#if FIGS > 64
+/* there are only 64 random bits; use them all */
+#undef FIGS
+#define FIGS	64
+#endif
+
+
+/*
+** LUA_RAND32 forces the use of 32-bit integers in the implementation
+** of the PRN generator (mainly for testing).
+*/
+#if !defined(LUA_RAND32) && !defined(Rand64)
+
+/* try to find an integer type with at least 64 bits */
+
+#if (ULONG_MAX >> 31 >> 31) >= 3
+
+/* 'long' has at least 64 bits */
+#define Rand64		unsigned long
+
+#elif !defined(LUA_USE_C89) && defined(LLONG_MAX)
+
+/* there is a 'long long' type (which must have at least 64 bits) */
+#define Rand64		unsigned long long
+
+#elif (LUA_MAXUNSIGNED >> 31 >> 31) >= 3
+
+/* 'lua_Integer' has at least 64 bits */
+#define Rand64		lua_Unsigned
+
+#endif
+
+#endif
+
+
+#if defined(Rand64)  /* { */
+
+/*
+** Standard implementation, using 64-bit integers.
+** If 'Rand64' has more than 64 bits, the extra bits do not interfere
+** with the 64 initial bits, except in a right shift. Moreover, the
+** final result has to discard the extra bits.
+*/
+
+/* avoid using extra bits when needed */
+#define trim64(x)	((x) & 0xffffffffffffffffu)
+
+
+/* rotate left 'x' by 'n' bits */
+static Rand64 rotl (Rand64 x, int n) {
+  return (x << n) | (trim64(x) >> (64 - n));
+}
+
+static Rand64 nextrand (Rand64 *state) {
+  Rand64 state0 = state[0];
+  Rand64 state1 = state[1];
+  Rand64 state2 = state[2] ^ state0;
+  Rand64 state3 = state[3] ^ state1;
+  Rand64 res = rotl(state1 * 5, 7) * 9;
+  state[0] = state0 ^ state3;
+  state[1] = state1 ^ state2;
+  state[2] = state2 ^ (state1 << 17);
+  state[3] = rotl(state3, 45);
+  return res;
+}
+
+
+/* must take care to not shift stuff by more than 63 slots */
+
+
+/*
+** Convert bits from a random integer into a float in the
+** interval [0,1), getting the higher FIG bits from the
+** random unsigned integer and converting that to a float.
+*/
+
+/* must throw out the extra (64 - FIGS) bits */
+#define shift64_FIG	(64 - FIGS)
+
+/* to scale to [0, 1), multiply by scaleFIG = 2^(-FIGS) */
+#define scaleFIG	(l_mathop(0.5) / ((Rand64)1 << (FIGS - 1)))
+
+static lua_Number I2d (Rand64 x) {
+  return (lua_Number)(trim64(x) >> shift64_FIG) * scaleFIG;
+}
+
+/* convert a 'Rand64' to a 'lua_Unsigned' */
+#define I2UInt(x)	((lua_Unsigned)trim64(x))
+
+/* convert a 'lua_Unsigned' to a 'Rand64' */
+#define Int2I(x)	((Rand64)(x))
+
+
+#else	/* no 'Rand64'   }{ */
+
+/* get an integer with at least 32 bits */
+#if LUAI_IS32INT
+typedef unsigned int lu_int32;
+#else
+typedef unsigned long lu_int32;
+#endif
+
+
 /*
-** This function uses 'double' (instead of 'lua_Number') to ensure that
-** all bits from 'l_rand' can be represented, and that 'RANDMAX + 1.0'
-** will keep full precision (ensuring that 'r' is always less than 1.0.)
+** Use two 32-bit integers to represent a 64-bit quantity.
 */
+typedef struct Rand64 {
+  lu_int32 h;  /* higher half */
+  lu_int32 l;  /* lower half */
+} Rand64;
+
+
+/*
+** If 'lu_int32' has more than 32 bits, the extra bits do not interfere
+** with the 32 initial bits, except in a right shift and comparisons.
+** Moreover, the final result has to discard the extra bits.
+*/
+
+/* avoid using extra bits when needed */
+#define trim32(x)	((x) & 0xffffffffu)
+
+
+/*
+** basic operations on 'Rand64' values
+*/
+
+/* build a new Rand64 value */
+static Rand64 packI (lu_int32 h, lu_int32 l) {
+  Rand64 result;
+  result.h = h;
+  result.l = l;
+  return result;
+}
+
+/* return i << n */
+static Rand64 Ishl (Rand64 i, int n) {
+  lua_assert(n > 0 && n < 32);
+  return packI((i.h << n) | (trim32(i.l) >> (32 - n)), i.l << n);
+}
+
+/* i1 ^= i2 */
+static void Ixor (Rand64 *i1, Rand64 i2) {
+  i1->h ^= i2.h;
+  i1->l ^= i2.l;
+}
+
+/* return i1 + i2 */
+static Rand64 Iadd (Rand64 i1, Rand64 i2) {
+  Rand64 result = packI(i1.h + i2.h, i1.l + i2.l);
+  if (trim32(result.l) < trim32(i1.l))  /* carry? */
+    result.h++;
+  return result;
+}
+
+/* return i * 5 */
+static Rand64 times5 (Rand64 i) {
+  return Iadd(Ishl(i, 2), i);  /* i * 5 == (i << 2) + i */
+}
+
+/* return i * 9 */
+static Rand64 times9 (Rand64 i) {
+  return Iadd(Ishl(i, 3), i);  /* i * 9 == (i << 3) + i */
+}
+
+/* return 'i' rotated left 'n' bits */
+static Rand64 rotl (Rand64 i, int n) {
+  lua_assert(n > 0 && n < 32);
+  return packI((i.h << n) | (trim32(i.l) >> (32 - n)),
+               (trim32(i.h) >> (32 - n)) | (i.l << n));
+}
+
+/* for offsets larger than 32, rotate right by 64 - offset */
+static Rand64 rotl1 (Rand64 i, int n) {
+  lua_assert(n > 32 && n < 64);
+  n = 64 - n;
+  return packI((trim32(i.h) >> n) | (i.l << (32 - n)),
+               (i.h << (32 - n)) | (trim32(i.l) >> n));
+}
+
+/*
+** implementation of 'xoshiro256**' algorithm on 'Rand64' values
+*/
+static Rand64 nextrand (Rand64 *state) {
+  Rand64 res = times9(rotl(times5(state[1]), 7));
+  Rand64 t = Ishl(state[1], 17);
+  Ixor(&state[2], state[0]);
+  Ixor(&state[3], state[1]);
+  Ixor(&state[1], state[2]);
+  Ixor(&state[0], state[3]);
+  Ixor(&state[2], t);
+  state[3] = rotl1(state[3], 45);
+  return res;
+}
+
+
+/*
+** Converts a 'Rand64' into a float.
+*/
+
+/* an unsigned 1 with proper type */
+#define UONE		((lu_int32)1)
+
+
+#if FIGS <= 32
+
+/* 2^(-FIGS) */
+#define scaleFIG       (l_mathop(0.5) / (UONE << (FIGS - 1)))
+
+/*
+** get up to 32 bits from higher half, shifting right to
+** throw out the extra bits.
+*/
+static lua_Number I2d (Rand64 x) {
+  lua_Number h = (lua_Number)(trim32(x.h) >> (32 - FIGS));
+  return h * scaleFIG;
+}
+
+#else	/* 32 < FIGS <= 64 */
+
+/* must take care to not shift stuff by more than 31 slots */
+
+/* 2^(-FIGS) = 1.0 / 2^30 / 2^3 / 2^(FIGS-33) */
+#define scaleFIG  \
+	((lua_Number)1.0 / (UONE << 30) / 8.0 / (UONE << (FIGS - 33)))
+
+/*
+** use FIGS - 32 bits from lower half, throwing out the other
+** (32 - (FIGS - 32)) = (64 - FIGS) bits
+*/
+#define shiftLOW	(64 - FIGS)
+
+/*
+** higher 32 bits go after those (FIGS - 32) bits: shiftHI = 2^(FIGS - 32)
+*/
+#define shiftHI		((lua_Number)(UONE << (FIGS - 33)) * 2.0)
+
+
+static lua_Number I2d (Rand64 x) {
+  lua_Number h = (lua_Number)trim32(x.h) * shiftHI;
+  lua_Number l = (lua_Number)(trim32(x.l) >> shiftLOW);
+  return (h + l) * scaleFIG;
+}
+
+#endif
+
+
+/* convert a 'Rand64' to a 'lua_Unsigned' */
+static lua_Unsigned I2UInt (Rand64 x) {
+  return ((lua_Unsigned)trim32(x.h) << 31 << 1) | (lua_Unsigned)trim32(x.l);
+}
+
+/* convert a 'lua_Unsigned' to a 'Rand64' */
+static Rand64 Int2I (lua_Unsigned n) {
+  return packI((lu_int32)(n >> 31 >> 1), (lu_int32)n);
+}
+
+#endif  /* } */
+
+
+/*
+** A state uses four 'Rand64' values.
+*/
+typedef struct {
+  Rand64 s[4];
+} RanState;
+
+
+/*
+** Project the random integer 'ran' into the interval [0, n].
+** Because 'ran' has 2^B possible values, the projection can only be
+** uniform when the size of the interval is a power of 2 (exact
+** division). Otherwise, to get a uniform projection into [0, n], we
+** first compute 'lim', the smallest Mersenne number not smaller than
+** 'n'. We then project 'ran' into the interval [0, lim].  If the result
+** is inside [0, n], we are done. Otherwise, we try with another 'ran',
+** until we have a result inside the interval.
+*/
+static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n,
+                             RanState *state) {
+  if ((n & (n + 1)) == 0)  /* is 'n + 1' a power of 2? */
+    return ran & n;  /* no bias */
+  else {
+    lua_Unsigned lim = n;
+    /* compute the smallest (2^b - 1) not smaller than 'n' */
+    lim |= (lim >> 1);
+    lim |= (lim >> 2);
+    lim |= (lim >> 4);
+    lim |= (lim >> 8);
+    lim |= (lim >> 16);
+#if (LUA_MAXUNSIGNED >> 31) >= 3
+    lim |= (lim >> 32);  /* integer type has more than 32 bits */
+#endif
+    lua_assert((lim & (lim + 1)) == 0  /* 'lim + 1' is a power of 2, */
+      && lim >= n  /* not smaller than 'n', */
+      && (lim >> 1) < n);  /* and it is the smallest one */
+    while ((ran &= lim) > n)  /* project 'ran' into [0..lim] */
+      ran = I2UInt(nextrand(state->s));  /* not inside [0..n]? try again */
+    return ran;
+  }
+}
+
+
 static int math_random (lua_State *L) {
   lua_Integer low, up;
-  double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0));
+  lua_Unsigned p;
+  RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1));
+  Rand64 rv = nextrand(state->s);  /* next pseudo-random value */
   switch (lua_gettop(L)) {  /* check number of arguments */
     case 0: {  /* no arguments */
-      lua_pushnumber(L, (lua_Number)r);  /* Number between 0 and 1 */
+      lua_pushnumber(L, I2d(rv));  /* float between 0 and 1 */
       return 1;
     }
     case 1: {  /* only upper limit */
       low = 1;
       up = luaL_checkinteger(L, 1);
+      if (up == 0) {  /* single 0 as argument? */
+        lua_pushinteger(L, I2UInt(rv));  /* full random integer */
+        return 1;
+      }
       break;
     }
     case 2: {  /* lower and upper limits */
@@ -266,35 +581,72 @@ static int math_random (lua_State *L) {
   }
   /* random integer in the interval [low, up] */
   luaL_argcheck(L, low <= up, 1, "interval is empty");
-  luaL_argcheck(L, low >= 0 || up <= LUA_MAXINTEGER + low, 1,
-                   "interval too large");
-  r *= (double)(up - low) + 1.0;
-  lua_pushinteger(L, (lua_Integer)r + low);
+  /* project random integer into the interval [0, up - low] */
+  p = project(I2UInt(rv), (lua_Unsigned)up - (lua_Unsigned)low, state);
+  lua_pushinteger(L, p + (lua_Unsigned)low);
   return 1;
 }
 
 
-static int math_randomseed (lua_State *L) {
-  l_srand((unsigned int)(lua_Integer)luaL_checknumber(L, 1));
-  (void)l_rand(); /* discard first value to avoid undesirable correlations */
-  return 0;
+static void setseed (lua_State *L, Rand64 *state,
+                     lua_Unsigned n1, lua_Unsigned n2) {
+  int i;
+  state[0] = Int2I(n1);
+  state[1] = Int2I(0xff);  /* avoid a zero state */
+  state[2] = Int2I(n2);
+  state[3] = Int2I(0);
+  for (i = 0; i < 16; i++)
+    nextrand(state);  /* discard initial values to "spread" seed */
+  lua_pushinteger(L, n1);
+  lua_pushinteger(L, n2);
 }
 
 
-static int math_type (lua_State *L) {
-  if (lua_type(L, 1) == LUA_TNUMBER) {
-      if (lua_isinteger(L, 1))
-        lua_pushliteral(L, "integer");
-      else
-        lua_pushliteral(L, "float");
+/*
+** Set a "random" seed. To get some randomness, use the current time
+** and the address of 'L' (in case the machine does address space layout
+** randomization).
+*/
+static void randseed (lua_State *L, RanState *state) {
+  lua_Unsigned seed1 = (lua_Unsigned)time(NULL);
+  lua_Unsigned seed2 = (lua_Unsigned)(size_t)L;
+  setseed(L, state->s, seed1, seed2);
+}
+
+
+static int math_randomseed (lua_State *L) {
+  RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1));
+  if (lua_isnone(L, 1)) {
+    randseed(L, state);
   }
   else {
-    luaL_checkany(L, 1);
-    lua_pushnil(L);
+    lua_Integer n1 = luaL_checkinteger(L, 1);
+    lua_Integer n2 = luaL_optinteger(L, 2, 0);
+    setseed(L, state->s, n1, n2);
   }
-  return 1;
+  return 2;  /* return seeds */
+}
+
+
+static const luaL_Reg randfuncs[] = {
+  {"random", math_random},
+  {"randomseed", math_randomseed},
+  {NULL, NULL}
+};
+
+
+/*
+** Register the random functions and initialize their state.
+*/
+static void setrandfunc (lua_State *L) {
+  RanState *state = (RanState *)lua_newuserdatauv(L, sizeof(RanState), 0);
+  randseed(L, state);  /* initialize with a "random" seed */
+  lua_pop(L, 2);  /* remove pushed seeds */
+  luaL_setfuncs(L, randfuncs, 1);
 }
 
+/* }================================================================== */
+
 
 /*
 ** {==================================================================
@@ -367,8 +719,6 @@ static const luaL_Reg mathlib[] = {
   {"min",   math_min},
   {"modf",   math_modf},
   {"rad",   math_rad},
-  {"random",     math_random},
-  {"randomseed", math_randomseed},
   {"sin",   math_sin},
   {"sqrt",  math_sqrt},
   {"tan",   math_tan},
@@ -384,6 +734,8 @@ static const luaL_Reg mathlib[] = {
   {"log10", math_log10},
 #endif
   /* placeholders */
+  {"random", NULL},
+  {"randomseed", NULL},
   {"pi", NULL},
   {"huge", NULL},
   {"maxinteger", NULL},
@@ -405,6 +757,7 @@ LUAMOD_API int luaopen_math (lua_State *L) {
   lua_setfield(L, -2, "maxinteger");
   lua_pushinteger(L, LUA_MININTEGER);
   lua_setfield(L, -2, "mininteger");
+  setrandfunc(L);
   return 1;
 }