patch 8.1.2356: rand() does not use the best algorithmv8.1.2356

Problem:    rand() does not use the best algorithm.
Solution:   use xoshiro128** instead of xorshift. (Kaito Udagawa,
            closes #5279)

1 files changed, 65 insertions, 54 deletions

diff --git a/src/evalfunc.c b/src/evalfunc.c
index c6e4679e54..6b00b4e656 100644
--- a/src/evalfunc.c
+++ b/src/evalfunc.c
@@ -5139,70 +5139,74 @@ f_pyxeval(typval_T *argvars, typval_T *rettv)
 f_rand(typval_T *argvars, typval_T *rettv)
 {
     list_T	*l = NULL;
-    UINT32_T	x, y, z, w, t;
-    static int	rand_seed_initialized = FALSE;
-    static UINT32_T xyzw[4] = {123456789, 362436069, 521288629, 88675123};
-
-#define SHUFFLE_XORSHIFT128 \
-	t = x ^ (x << 11); \
-	x = y; y = z; z = w; \
-	w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
+    static list_T *globl = NULL;
+    UINT32_T	x, y, z, w, t, result;
+    listitem_T	*lx, *ly, *lz, *lw;
 
     if (argvars[0].v_type == VAR_UNKNOWN)
     {
-	// When argument is not given, return random number initialized
-	// statically.
-	if (!rand_seed_initialized)
+	// When no argument is given use the global seed list.
+	if (globl == NULL)
 	{
-	    xyzw[0] = (varnumber_T)time(NULL);
-	    rand_seed_initialized = TRUE;
+	    // Initialize the global seed list.
+	    f_srand(argvars, rettv);
+	    l = rettv->vval.v_list;
+	    if (l == NULL || list_len(l) != 4)
+	    {
+		clear_tv(rettv);
+		goto theend;
+	    }
+	    globl = l;
 	}
-
-	x = xyzw[0];
-	y = xyzw[1];
-	z = xyzw[2];
-	w = xyzw[3];
-	SHUFFLE_XORSHIFT128;
-	xyzw[0] = x;
-	xyzw[1] = y;
-	xyzw[2] = z;
-	xyzw[3] = w;
+	else
+	    l = globl;
     }
     else if (argvars[0].v_type == VAR_LIST)
     {
-	listitem_T	*lx, *ly, *lz, *lw;
-
 	l = argvars[0].vval.v_list;
-	if (list_len(l) != 4)
+	if (l == NULL || list_len(l) != 4)
 	    goto theend;
-
-	lx = list_find(l, 0L);
-	ly = list_find(l, 1L);
-	lz = list_find(l, 2L);
-	lw = list_find(l, 3L);
-	if (lx->li_tv.v_type != VAR_NUMBER) goto theend;
-	if (ly->li_tv.v_type != VAR_NUMBER) goto theend;
-	if (lz->li_tv.v_type != VAR_NUMBER) goto theend;
-	if (lw->li_tv.v_type != VAR_NUMBER) goto theend;
-	x = (UINT32_T)lx->li_tv.vval.v_number;
-	y = (UINT32_T)ly->li_tv.vval.v_number;
-	z = (UINT32_T)lz->li_tv.vval.v_number;
-	w = (UINT32_T)lw->li_tv.vval.v_number;
-	SHUFFLE_XORSHIFT128;
-	lx->li_tv.vval.v_number = (varnumber_T)x;
-	ly->li_tv.vval.v_number = (varnumber_T)y;
-	lz->li_tv.vval.v_number = (varnumber_T)z;
-	lw->li_tv.vval.v_number = (varnumber_T)w;
     }
     else
 	goto theend;
 
+    lx = list_find(l, 0L);
+    ly = list_find(l, 1L);
+    lz = list_find(l, 2L);
+    lw = list_find(l, 3L);
+    if (lx->li_tv.v_type != VAR_NUMBER) goto theend;
+    if (ly->li_tv.v_type != VAR_NUMBER) goto theend;
+    if (lz->li_tv.v_type != VAR_NUMBER) goto theend;
+    if (lw->li_tv.v_type != VAR_NUMBER) goto theend;
+    x = (UINT32_T)lx->li_tv.vval.v_number;
+    y = (UINT32_T)ly->li_tv.vval.v_number;
+    z = (UINT32_T)lz->li_tv.vval.v_number;
+    w = (UINT32_T)lw->li_tv.vval.v_number;
+
+    // SHUFFLE_XOSHIRO128STARSTAR
+#define ROTL(x, k) ((x << k) | (x >> (32 - k)))
+    result = ROTL(y * 5, 7) * 9;
+    t = y << 9;
+    z ^= x;
+    w ^= y;
+    y ^= z, x ^= w;
+    z ^= t;
+    w = ROTL(w, 11);
+#undef ROTL
+
+    lx->li_tv.vval.v_number = (varnumber_T)x;
+    ly->li_tv.vval.v_number = (varnumber_T)y;
+    lz->li_tv.vval.v_number = (varnumber_T)z;
+    lw->li_tv.vval.v_number = (varnumber_T)w;
+
     rettv->v_type = VAR_NUMBER;
-    rettv->vval.v_number = (varnumber_T)w;
+    rettv->vval.v_number = (varnumber_T)result;
     return;
 
 theend:
     semsg(_(e_invarg2), tv_get_string(&argvars[0]));
+    rettv->v_type = VAR_NUMBER;
+    rettv->vval.v_number = -1;
 }
 
 /*
@@ -7096,6 +7100,7 @@ f_sqrt(typval_T *argvars, typval_T *rettv)
 f_srand(typval_T *argvars, typval_T *rettv)
 {
     static int dev_urandom_state = -1;  // FAIL or OK once tried
+    UINT32_T x = 0, z;
 
     if (rettv_list_alloc(rettv) == FAIL)
 	return;
@@ -7123,8 +7128,7 @@ f_srand(typval_T *argvars, typval_T *rettv)
 		else
 		{
 		    dev_urandom_state = OK;
-		    list_append_number(rettv->vval.v_list,
-						 (varnumber_T)buf.cont.number);
+		    x = buf.cont.number;
 		}
 		close(fd);
 	    }
@@ -7132,21 +7136,28 @@ f_srand(typval_T *argvars, typval_T *rettv)
 	}
 	if (dev_urandom_state != OK)
 	    // Reading /dev/urandom doesn't work, fall back to time().
-	    list_append_number(rettv->vval.v_list, (varnumber_T)vim_time());
+	    x = vim_time();
     }
     else
     {
 	int	    error = FALSE;
-	UINT32_T    x = (UINT32_T)tv_get_number_chk(&argvars[0], &error);
 
+	x = (UINT32_T)tv_get_number_chk(&argvars[0], &error);
 	if (error)
 	    return;
-
-	list_append_number(rettv->vval.v_list, (varnumber_T)x);
     }
-    list_append_number(rettv->vval.v_list, 362436069);
-    list_append_number(rettv->vval.v_list, 521288629);
-    list_append_number(rettv->vval.v_list, 88675123);
+
+#define SPLITMIX32 ( \
+    z = (x += 0x9e3779b9), \
+    z = (z ^ (z >> 16)) * 0x85ebca6b, \
+    z = (z ^ (z >> 13)) * 0xc2b2ae35, \
+    z ^ (z >> 16) \
+    )
+
+    list_append_number(rettv->vval.v_list, (varnumber_T)SPLITMIX32);
+    list_append_number(rettv->vval.v_list, (varnumber_T)SPLITMIX32);
+    list_append_number(rettv->vval.v_list, (varnumber_T)SPLITMIX32);
+    list_append_number(rettv->vval.v_list, (varnumber_T)SPLITMIX32);
 }
 
 /*