Patch 8.1.2356

[Bram Moolenaar]

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 -- Br...@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 ///

[John Marriott]

On 29-Nov-2019 08:14, Bram Moolenaar wrote:
> 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
>
>
>

After this patch, mingw64 throws this compiler warning and linker error
if FEAT_FLOAT is disabled:
gcc -c -I. -Iproto -DWIN32 -DWINVER=0x0603 -D_WIN32_WINNT=0x0603
-DHAVE_PATHDEF -DFEAT_NORMAL -DHAVE_STDINT_H -DFEAT_GUI_MSWIN
-DFEAT_CLIPBOARD -pipe -march=native -Wall -O3 -fomit-frame-pointer
-freg-struct-return evalfunc.c -o gobjnative/evalfunc.o
evalfunc.c: In function 'f_rand':
evalfunc.c:5152:6: warning: implicit declaration of function 'f_srand';
did you mean 'f_rand'? [-Wimplicit-function-declaration]
 5152 |      f_srand(argvars, rettv);
      | ^~~~~~~
      |      f_rand
gcc -I. -Iproto -DWIN32 -DWINVER=0x0603 -D_WIN32_WINNT=0x0603
-DHAVE_PATHDEF -DFEAT_NORMAL -DHAVE_STDINT_H -pipe -march=native -Wall
-O3 -fomit-frame-pointer -freg-struct-return -Wl,-nxcompat,-dynamicbase
-municode -s -o vim.exe objnative/arabic.o objnative/arglist.o
objnative/autocmd.o objnative/beval.o objnative/blob.o
objnative/blowfish.o objnative/buffer.o objnative/bufwrite.o
objnative/change.o objnative/charset.o objnative/cindent.o
objnative/cmdexpand.o objnative/cmdhist.o objnative/crypt.o
objnative/crypt_zip.o objnative/debugger.o objnative/dict.o
objnative/diff.o objnative/digraph.o objnative/drawline.o
objnative/drawscreen.o objnative/edit.o objnative/eval.o
objnative/evalbuffer.o objnative/evalfunc.o objnative/evalvars.o
objnative/evalwindow.o objnative/ex_cmds.o objnative/ex_cmds2.o
objnative/ex_docmd.o objnative/ex_eval.o objnative/ex_getln.o
objnative/fileio.o objnative/filepath.o objnative/findfile.o
objnative/fold.o objnative/getchar.o objnative/hardcopy.o
objnative/hashtab.o objnative/highlight.o objnative/if_cscope.o
objnative/indent.o objnative/insexpand.o objnative/json.o
objnative/list.o objnative/main.o objnative/map.o objnative/mark.o
objnative/memfile.o objnative/memline.o objnative/menu.o
objnative/message.o objnative/misc1.o objnative/misc2.o
objnative/mouse.o objnative/move.o objnative/mbyte.o objnative/normal.o
objnative/ops.o objnative/option.o objnative/optionstr.o
objnative/os_mswin.o objnative/os_win32.o objnative/pathdef.o
objnative/popupmenu.o objnative/popupwin.o objnative/profiler.o
objnative/quickfix.o objnative/regexp.o objnative/register.o
objnative/scriptfile.o objnative/screen.o objnative/search.o
objnative/session.o objnative/sha256.o objnative/sign.o
objnative/spell.o objnative/spellfile.o objnative/spellsuggest.o
objnative/syntax.o objnative/tag.o objnative/term.o objnative/testing.o
objnative/textprop.o objnative/ui.o objnative/undo.o objnative/usercmd.o
objnative/userfunc.o objnative/version.o objnative/viminfo.o
objnative/winclip.o objnative/window.o objnative/os_w32exe.o
objnative/vimrc.o objnative/xdiffi.o objnative/xemit.o
objnative/xprepare.o objnative/xutils.o objnative/xhistogram.o
objnative/xpatience.o objnative/iscygpty.o -lkernel32 -luser32 -lgdi32
-ladvapi32 -lcomdlg32 -lcomctl32 -lnetapi32 -lversion -lole32 -luuid
D:/Users/John/Documents/software/MinGW/mingw64/bin/../lib/gcc/x86_64-w64-mingw32/9.2.1/../../../../x86_64-w64-mingw32/bin/ld.exe:
objnative/evalfunc.o:evalfunc.c:(.text+0x2d31): undefined reference to
`f_srand'
collect2.exe: error: ld returned 1 exit status

Cheers
John

[Bram Moolenaar]

John Marriott wrote:

> On 29-Nov-2019 08:14, Bram Moolenaar wrote:
> > 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
> >
> >
> >
> After this patch, mingw64 throws this compiler warning and linker error
> if FEAT_FLOAT is disabled:
> gcc -c -I. -Iproto -DWIN32 -DWINVER=0x0603 -D_WIN32_WINNT=0x0603
> -DHAVE_PATHDEF -DFEAT_NORMAL -DHAVE_STDINT_H -DFEAT_GUI_MSWIN
> -DFEAT_CLIPBOARD -pipe -march=native -Wall -O3 -fomit-frame-pointer
> -freg-struct-return evalfunc.c -o gobjnative/evalfunc.o
> evalfunc.c: In function 'f_rand':
> evalfunc.c:5152:6: warning: implicit declaration of function 'f_srand';
> did you mean 'f_rand'? [-Wimplicit-function-declaration]
>  5152 |      f_srand(argvars, rettv);
>       | ^~~~~~~
>       |      f_rand
> gcc -I. -Iproto -DWIN32 -DWINVER=0x0603 -D_WIN32_WINNT=0x0603

[...]

The #ifdefs are misplaced. I was wondering if we should graduate
FEAT_FLOAT, but apparently there are still builds without it.

--
hundred-and-one symptoms of being an internet addict:

139. You down your lunch in five minutes, at your desk, so you can
spend the rest of the hour surfing the Net.