patch 8.1.2356: rand() does not use the best algorithm
Problem: rand() does not use the best algorithm.
Solution: use xoshiro128** instead of xorshift. (Kaito Udagawa,
closes #5279)
diff --git a/src/evalfunc.c b/src/evalfunc.c
index c6e4679..6b00b4e 100644
--- a/src/evalfunc.c
+++ b/src/evalfunc.c
@@ -5139,70 +5139,74 @@
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_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 @@
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 @@
}
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);
}
/*
diff --git a/src/testdir/test_random.vim b/src/testdir/test_random.vim
index 9fe71a9..f8ea407 100644
--- a/src/testdir/test_random.vim
+++ b/src/testdir/test_random.vim
@@ -2,12 +2,12 @@
func Test_Rand()
let r = srand(123456789)
- call assert_equal([123456789, 362436069, 521288629, 88675123], r)
- call assert_equal(3701687786, rand(r))
- call assert_equal(458299110, rand(r))
- call assert_equal(2500872618, rand(r))
- call assert_equal(3633119408, rand(r))
- call assert_equal(516391518, rand(r))
+ call assert_equal([1573771921, 319883699, 2742014374, 1324369493], r)
+ call assert_equal(4284103975, rand(r))
+ call assert_equal(1001954530, rand(r))
+ call assert_equal(2701803082, rand(r))
+ call assert_equal(2658065534, rand(r))
+ call assert_equal(3104308804, rand(r))
call test_settime(12341234)
let s = srand()
diff --git a/src/version.c b/src/version.c
index 4ca5c0f..7abb190 100644
--- a/src/version.c
+++ b/src/version.c
@@ -738,6 +738,8 @@
static int included_patches[] =
{ /* Add new patch number below this line */
/**/
+ 2356,
+/**/
2355,
/**/
2354,