Patch 8.1.2356
Problem: rand() does not use the best algorithm.
Solution: use xoshiro128** instead of xorshift. (Kaito Udagawa,
closes #5279)
Files: runtime/doc/eval.txt, src/evalfunc.c, src/testdir/test_random.vim
*** ../vim-8.1.2355/runtime/doc/eval.txt 2019-11-25 15:40:28.849612230
+0100
--- runtime/doc/eval.txt 2019-11-28 22:09:22.062103970 +0100
***************
*** 7635,7651 ****
<
rand([{expr}]) *rand()*
! Return a pseudo-random Number generated with an xorshift
! algorithm using seed {expr}. {expr} can be initialized by
! |srand()| and will be updated by rand().
! If {expr} is omitted, an internal seed value is used and
! updated.
Examples: >
:echo rand()
:let seed = srand()
:echo rand(seed)
! :echo rand(seed)
<
*readdir()*
readdir({directory} [, {expr}])
--- 7641,7658 ----
<
rand([{expr}]) *rand()*
! Return a pseudo-random Number generated with an xoshiro128**
! algorithm using seed {expr}. The returned number is 32 bits,
! also on 64 bits systems, for consistency.
! {expr} can be initialized by |srand()| and will be updated by
! rand(). If {expr} is omitted, an internal seed value is used
! and updated.
Examples: >
:echo rand()
:let seed = srand()
:echo rand(seed)
! :echo rand(seed) % 16 " random number 0 - 15
<
*readdir()*
readdir({directory} [, {expr}])
***************
*** 9125,9134 ****
srand([{expr}]) *srand()*
Initialize seed used by |rand()|:
- If {expr} is not given, seed values are initialized by
! time(NULL) a.k.a. epoch time.
! - If {expr} is given, return seed values which x element is
! {expr}. This is useful for testing or when a predictable
! sequence is expected.
Examples: >
:let seed = srand()
--- 9150,9160 ----
srand([{expr}]) *srand()*
Initialize seed used by |rand()|:
- If {expr} is not given, seed values are initialized by
! reading from /dev/urandom, if possible, or using time(NULL)
! a.k.a. epoch time otherwise; this only has second accuracy.
! - If {expr} is given it must be a Number. It is used to
! initialize the seed values. This is useful for testing or
! when a predictable sequence is intended.
Examples: >
:let seed = srand()
*** ../vim-8.1.2355/src/evalfunc.c 2019-11-26 12:23:26.679820852 +0100
--- src/evalfunc.c 2019-11-28 22:07:57.582720830 +0100
***************
*** 5139,5208 ****
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));
if (argvars[0].v_type == VAR_UNKNOWN)
{
! // When argument is not given, return random number initialized
! // statically.
! if (!rand_seed_initialized)
! {
! xyzw[0] = (varnumber_T)time(NULL);
! rand_seed_initialized = TRUE;
! }
!
! 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 if (argvars[0].v_type == VAR_LIST)
{
- listitem_T *lx, *ly, *lz, *lw;
-
l = argvars[0].vval.v_list;
! if (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;
rettv->v_type = VAR_NUMBER;
! rettv->vval.v_number = (varnumber_T)w;
return;
theend:
semsg(_(e_invarg2), tv_get_string(&argvars[0]));
}
/*
--- 5139,5212 ----
f_rand(typval_T *argvars, typval_T *rettv)
{
list_T *l = NULL;
! 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 no argument is given use the global seed list.
! if (globl == NULL)
! {
! // 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;
! }
! else
! l = globl;
}
else if (argvars[0].v_type == VAR_LIST)
{
l = argvars[0].vval.v_list;
! if (l == NULL || list_len(l) != 4)
goto theend;
}
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)result;
return;
theend:
semsg(_(e_invarg2), tv_get_string(&argvars[0]));
+ rettv->v_type = VAR_NUMBER;
+ rettv->vval.v_number = -1;
}
/*
***************
*** 7096,7101 ****
--- 7100,7106 ----
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,7130 ****
else
{
dev_urandom_state = OK;
! list_append_number(rettv->vval.v_list,
! (varnumber_T)buf.cont.number);
}
close(fd);
}
--- 7128,7134 ----
else
{
dev_urandom_state = OK;
! x = buf.cont.number;
}
close(fd);
}
***************
*** 7132,7152 ****
}
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());
}
else
{
int error = FALSE;
- UINT32_T 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);
}
/*
--- 7136,7163 ----
}
if (dev_urandom_state != OK)
// Reading /dev/urandom doesn't work, fall back to time().
! x = vim_time();
}
else
{
int error = FALSE;
+ x = (UINT32_T)tv_get_number_chk(&argvars[0], &error);
if (error)
return;
}
!
! #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);
}
/*
*** ../vim-8.1.2355/src/testdir/test_random.vim 2019-11-26 12:23:26.679820852
+0100
--- src/testdir/test_random.vim 2019-11-28 21:47:49.441003109 +0100
***************
*** 2,13 ****
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 test_settime(12341234)
let s = srand()
--- 2,13 ----
func Test_Rand()
let r = srand(123456789)
! 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()
*** ../vim-8.1.2355/src/version.c 2019-11-28 21:16:02.317772240 +0100
--- src/version.c 2019-11-28 21:49:05.524654891 +0100
***************
*** 739,740 ****
--- 739,742 ----
{ /* Add new patch number below this line */
+ /**/
+ 2356,
/**/
--
hundred-and-one symptoms of being an internet addict:
135. You cut classes or miss work so you can stay home and browse the web.
/// Bram Moolenaar -- [email protected] -- http://www.Moolenaar.net \\\
/// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/vim_dev/201911282114.xASLEnJ6009669%40masaka.moolenaar.net.
