To: vim_dev@googlegroups.com Subject: Patch 8.1.2356 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ 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 -- Bram@Moolenaar.net -- 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 ///