Mercurial > vim
changeset 18732:2513e666aa82 v8.1.2356
patch 8.1.2356: rand() does not use the best algorithm
Commit: https://github.com/vim/vim/commit/f8c1f9200c4b50969a8191a4fe0b0d09edb38979
Author: Bram Moolenaar <Bram@vim.org>
Date: Thu Nov 28 22:13:14 2019 +0100
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)
| author | Bram Moolenaar <Bram@vim.org> |
|---|---|
| date | Thu, 28 Nov 2019 22:15:04 +0100 |
| parents | e55bced76a31 |
| children | 8c088288a96b |
| files | runtime/doc/eval.txt src/evalfunc.c src/testdir/test_random.vim src/version.c |
| diffstat | 4 files changed, 82 insertions(+), 69 deletions(-) [+] |
line wrap: on
line diff
--- a/runtime/doc/eval.txt +++ b/runtime/doc/eval.txt @@ -1,4 +1,4 @@ -*eval.txt* For Vim version 8.1. Last change: 2019 Nov 25 +*eval.txt* For Vim version 8.1. Last change: 2019 Nov 28 VIM REFERENCE MANUAL by Bram Moolenaar @@ -7641,7 +7641,7 @@ range({expr} [, {max} [, {stride}]]) < rand([{expr}]) *rand()* - Return a pseudo-random Number generated with an xorshift + 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 @@ -9150,11 +9150,11 @@ sqrt({expr}) *sqrt()* 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. This only has second - accuracy. - - If {expr} is given, return seed values which x element is - {expr}. This is useful for testing or when a predictable - sequence is expected. + 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()
--- a/src/evalfunc.c +++ b/src/evalfunc.c @@ -5139,70 +5139,74 @@ f_pyxeval(typval_T *argvars, typval_T *r 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 *rett 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 *ret 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 *ret } 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); } /*
--- 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()