About design

SmokeRand design philosophy resembles such TestU01 batteries as SmallCrush, Crush and BigCrush: implemented statistical tests are grouped into predefined batteries that consume fixed samples from a tested generator. It differs from PractRand and gjrand where tests are adaptive, i.e. gradually accumulate statistics from input samples. An important goal during SmokeRand development was to overcome TestU01 limitations such as support of only 32-bit PRNGs, some problems with lower bits analysis, absence of multithreading support.

Analysis of the lowest bits of generators output that improves sensitivity of tests, e.g. linear complexity, matrix rank or birthday spacings test.

A set of tests implemented in SmokeRand is probably not exhaustive but is intended to catch different types of statistical flaws. The main sources of inspiration:

NIST STS: frequency tests (in SmokeRand - for 1, 8 and 16-bit blocks).
TestU01: birthday spacings, collision over, matrix rank, classicaal gap test, linear complexity, sumcollector test.
PractRand: Hamming weights based tests, mod3 test.
gjrand: rda16 gap test modification.

Compilation

Some basic compilation tips are given in README.md, here we consider only targeting less-common platforms, usage of compiler-dependent C features (such as 128-bit arithmetics), working in memory-constrained environment etc.

Usage of Ninja and WMake

Usage of Ninja and WMake requires Lua 5.x interpreter for generation of build.ninja or Makefile.wat scripts respectively. See cfg_ninja.lua and cfg_wmake.lua for details.

Ninja

The build.ninja script is generated by cfg_ninja.lua Lua script. Usage

$ lua cfg_ninja.lua cfg_name
$ ninja

Supported configurations:

gcc, mingw: gcc with POSIX threads.
gcc32: gcc, cross-compilation for 32-bit platforms.
msvc: Microsoft Visual C, automatic resolution of .h-file dependencies is supported only for English version of MSVC.
mingw-hx: 32-bit binaries friendly to HX DOS Extender.
zigcc: clang from Zig programming language distribution as zig cc command, WinAPI threads will be used.

WMake (Open Watcom)

Designed for Open Watcom C/C++, compiles for 32-bit Windows NT, 32-bit DOS (with extenders) and 16-bit DOS. The dynamic libraries with PRNGs (DLLs) are shared between Windows and 32-bit DOS version. The Makefile.wat makefile for wmake is generated by means of the cfg_wmake.lua script:

> lua cfg_wmake.lua
> wmake -f Makefile.wat

Requirements for compiler and hardware

Minimal requirements:

C99 compiler; C99 standard was chosen instead of C89 due to mandatory support of 64-bit integers and inline keyword.
GNU make.
32-bit CPU.
1 GiB of RAM.

Recommended configuration:

C99 compiler with 128-bit integers support either through __uint128_t type (GCC, Clang) or _umul128/_addcarry_u64 intrinsics (Microsoft Visual C). They will significantly improve performance of some PRNGs such as 128-bit LCGs and MWCs, RANLUX++, wyrand etc.
64-bit CPU; in the case of x86-64 -- support of RDTSC and RDSEED instructions and AVX2 instructions set by a compiler.
Multithreading support: pthreads (POSIX threads) library or WinAPI threads.
CMake or Ninja + Lua 5.x for compilation by means of MSVC. Or Lua 5.x for compilation by means of Open Watcom C.
16 GiB of RAM, especially for multithreaded mode and/or coll64dec battery.

The next compilers are supported: GCC (including MinGW and DJGPP), Clang (as zig cc), MSVC (Microsoft Visual C) and Open Watcom C. It allows to compile SmokeRand under Windows, UNIX-like systems and DOS. A slightly modified 16-bit version (apps/sr_tiny.c) of express battery can be compiled even by Borland Turbo C 2.0 or any other ANSI C (C89) compiler.

Usage in memory constrained environment

32-bit DOS version was tested in VirtualBox virtual machine with 512 MiB of RAM, customization of "CollisionOver" tests allows to run SmokeRand even at 64 MiB of RAM. The version of express battery for 16-bit computers (apps/sr_tiny.c) can run even at 8086 with 640 KiB of RAM, tested in DosBOX.

The next tests will require a special tuning for running in an environment with limited amount of RAM, e.g. under 32-bit DOS extenders on old hardware:

gap16_count0 may consume several MiB for gaps and frequencies tables. Probably RAM consumption may be significantly reduces but it may slow down and complicate a program for 64-bit environments.
bspace uses more than 64 MiB of memory for 64-bit values. Its 32-bit variant needs less than 256 KiB of RAM.
collover may use about 0.5 GiB of memory in most batteries. It may be significantly reduced but the test will be slower and less sensitive for 64-bit systems.
hamming_ot uses relatively large (several MiB) frequency tables during the run.

DJGPP

DJGPP supports its own system of dynamically loaded modules in DXE3 format. They are essentially simplified versions of dynamic libraries / shared objects common in Windows NT and GNU/Linux. To build with DJGPP use the next command:

$ make -f Makefile.gnu PLATFORM_NAME=DJGPP

Long file names support must be enabled!

All plugins with PRNGs will be compiled as DXE3 modules using the dxe3gen linker that is specific to DJGPP. It is possible to make SmokeRand DJGPP build to use DLLs but it will require a cross-compilation of plugins with MinGW or Open Watcom that is not too practical.

SmokeRand man page can be converted to the overstrike based format using the next commands:

$ groff -mandoc -Tascii -P-cBoU smokerand.1 > smokerand.dos
$ less smokerand.dos

Loading DLL under DOS

32-bit DOS build for Open Watcom uses a simplified custom DLL loader (see the src/pe32loader.c and include/pe32loader.h files) that allows to use properly compiled plugins with PRNGs even without DOS extender with PE files support. 16-bit DOS version (see apps/sr_tiny.c) doesn't support dynamic libraries at all, tested generators should be embedded into its source code.

As it was mentioned above it is possible to use the same approach for DJGPP but it is disabled by default. See the src/threads_intf.c file for details.

Cross-compilation for AARCH64

A good tutorial about the cross-compilation on GNU/Linux can be found [here](see https://azeria-labs.com/arm-on-x86-qemu-user/). Makefile.gnu has a section for such cross-compilation (PLATFORM_NAME=GCC_AARCH64_CROSS).

Packages installation:

$ sudo apt install qemu-user qemu-user-static gcc-aarch64-linux-gnu
$ sudo apt install binutils-aarch64-linux-gnu binutils-aarch64-linux-gnu-dbg
$ sudo apt install build-essential

Cross-compilation and running inside the emulator:

$ aarch64-linux-gnu-gcc -o hello hello.c
$ qemu-aarch64 -L /usr/aarch64-linux-gnu ./hello

Batteries

Batteries from TestU01 use the next number of values:

SmallCrush --- 2^26 values (comparable to express battery)
Crush --- 2^35 values (comparable to default battery)
BigCrush -- 2^38 values (comparable to full battery)

However SmokeRand tests are about 5-10 times faster than tests from TestU01 due to optimized implementations that don't use floating point values and multiplications whenever possible. Birthday spacings tests use radix sort instead of QuickSort.

Test results interpretation

All statistical tests included in SmokeRand batteries return p-value. Their interpretation is rather simple and based on the next intervals:

Ok: in the (0.001 and 0.999) interval;
SUSPICIOUS: in the [1e-10; 0.001] and [0.999; 1-1e-10] intervals;
FAIL: in the [0; 1e-10) and (1 - 1e-10; 1] intervals.

Only systematic SUSPICIOUS or FAIL results must be interpreted as detected statistical flaw of the tested pseudorandom number generator. Such threshold values may seem unusually strict but allow to significantly reduce false positives. Tests sensitivity can be easily increased by using larger samples without altering critical p-values. Such approach is used in dieharder, TestU01, and PractRand test suites.

WARNING! The SmokeRand test batteries can detect flaws in many popular pseudorandom number generators but they cannot guarantee a high quality of generator that passed them, especially for cryptography. Consider them just as a "smoke test" for searching obvious defects in pseudorandom number generators.

A state-of-art general purpose PRNG must be cryptographically secure, i.e. its quality should be analysed not only by empirical test but by cryptoanalytic techniques. Of course, it should be used correctly, i.e. having period at least 2^64, not be prone to the birthday paradox, not be reseeded during the sample generation if reproducible simulation is desired etc.

Automatic quality assessment

SmokeRand makes an automatic quality assessment in the form of numerical grade from 0 (the lowest quality) to 4 (the highest quality). The grades are interpreted the next way:

4.0 - good generator, probably may be used as a general purpose PRNG.
3.0-3.99 - some issues have been detected, usage for any computational task requires an extra analysis.
2.0-2.99 - flawed generator. Cannot be recommended as a general purpose generator but detected flaws will probably cause problems only in some specific conditions.
1.0-1.99 - bad generator. Detected biases are serious and can easily distort results of Monte-Carlo simulations. But it may be suitable for e.g. programming games like TETRIS or generating some non-repeating values.
<1.0 - very bad generator. Can be used only if its replacement to a simple counter (0,1,2,3,....) would be totally acceptable.

The excellent grade is intentionally avoided because such grading is impossible without thorough cryptoanalysis that cannot be fully automated and represented as a battery of statistical tests.

The grading algorithm is rather simple and based on a penalty system. An initial grade is 4.0 and some penalty is subtracted from it for an every failed test. The used penalties for failures:

4.0 for frequency test and gap test.
3.0 for birthday spacings and collision over tests.
2.0 for Hamming weights based test, gap16_count0, mod3 and sumcollector tests.
1.0 for birthday spacings test with decimation.
0.25 for a matrix rank and linear complexity tests. If e.g. three test of this kind are failed - 0.75 is subtracted from the grade.

If the resulting grade is less than zero then it is converted to zero. Of course, this scale is very crude, partially subjective and probably rather strict. It is aimed on distinction between e.g. low linear complexity of some bits (important only in some specific cases) and failure of gap test (can easily distort a Monte-Carlo simulation results).

If failures for the birthday or freq extra batteries were observed then the 1.0 penalty value should be subtracted from the final grade for each failure. E.g. SplitMix and RC4 will be graded as 3.0 instead of 4.0.

Examples of grading for some generators:

good: AES128, ChaCha12, xoroshiro128++, KISS99, MWC64X.
some issues: Mersenne Twister, 128-bit LCG, xoroshiro128+, SplitMix, RC4, DES-CTR.
flawed: flea32x1, taus88, WELL1024a.
bad, very bad: RANDU, 32-bit and 64-bit LCGs with power of 2 modulo, xorwow, SWB, ChaCha12 with 32-bit counter, LFIB(607,273,+)

Grouping RANDU together with xorwow and additive lagged Fibonacci PRNGs may be seen as too pessimistic quality estimation of some generators. But it is partially based on the idea that usage of non-cryptographic generators that even pass all tests (have 4.0 final grade) is an intentional downgrade in quality, bithack that requires a special justification.

About checking statitical tests

SmokeRand includes a large collection of generators that was used and still can be used for checking correctness of its statistical tests. Examples:

chacha (ChaCha12), aes128, speck128 (Speck128/128) - all tests should pass, occasional SUSPICIOUS values are possible.
des, pcg64_64, splitmix64 - pass full battery but fail coll64dec (former birthday) battery.
ara32, flea32x1: fail the mod3 test even in the brief battery.
biski64: systematic SUSPICIOUS and/or FAIL values at hamming_distr test (XORing part) in the full battery.
chacha with the --param=avx-ctr32 parameter fails the gap_inv1024 test from the full battery.
lcg64prime: fails bspace64_1d even in the brief battery.
mwc64: fails only bspace21_3d in the brief battery and probably some other tests in default and full batteries.
lcg128 and lcg96: fail the bspace4_8d_dec test for the 64-bit output (default mode); lcg128 with the --param=x128u32 parameter passed the brief battery but fails the same test in the default battery.
mwc4691: fails the gap16_count0 test since the brief battery, it is the only test that it fails in SmokeRand batteries.
ranrot32: fails the hamming_ot_u128 test in the brief battery.
ranq2: fails the matrixrank_4096 test (but not linear complexity tests).
swbmwc32: fails the gap_inv8 test, it is the only test that it fails in SmokeRand batteries.
lfib_par with the --param=607+ parameter: fails the bspace32_1d, gap_inv512 and gap16_count0 tests from the brief battery.
lfib_par with the --param=19937+ parameter: fails the gap16_count0 test in the default and full batteries.
ranhash and wanghash64 fail the hamming_distr tests in the default battery.

About some compilers optimizations

It seems that GCC 15.2 at -O3 optimization level tries to vectorize the code to agressively and slows down some generators (KISS, Biski, Mother-of-All), especiall if they are called as small functions (get_bits). An example for mall32 PRNG is given below. The -fno-tree-slp-vectorize in GCC should be used for PRNG plugins compilation.

GCC 15.2 (w64devkit):

mov          rdx,rcx
mov          ecx,[rcx][4]
mov          eax,[rdx]
vmovd        xmm1,[rdx][00C]
vmovq        xmm0,rcx
imul         rcx,rcx,0000005D4
mov          r8d,[rdx][8]
imul         rax,rax,07DD4FFC7
vpinsrd      xmm0,xmm0,r8d,1
vadd         rax,rcx
mov          ecx,[rdx][010]
add          rax,rcx
vmovd        ecx,xmm1
imul         rcx,rcx,0000013FB
add          rax,rcx
mov          ecx,r8d
imul         rcx,rcx,0000006F0
add          rax,rcx
vpinsrd      xmm1,xmm1,eax,1
mov          rcx,rax
mov          eax,eax
vpunpcklqdq  xmm0,xmm0,xmm1
shr          rcx,020 ;' '
vmov         [rdx][010],ecx
vmovdqu      [rdx],xmm0
retn

GCC 10.3 (TDM-GCC):

mov          edx,[rcx][4]
mov          eax,[rcx]
mov          r10,rdx
imul         rax,rax,07DD4FFC7
imul         rdx,rdx,0000005D4
mov          r8d,[rcx][00C]
mov          r9d,[rcx][8]
add          rax,rdx
mov          edx,[rcx][010]
mov          [rcx],r10d
add          rax,rdx
mov          edx,r8d
imul         rdx,rdx,0000013FB
mov          [rcx][4],r9d
mov          [rcx][8],r8d
add          rax,rdx
mov          edx,r9d
imul         rdx,rdx,0000006F0
add          rax,rdx
mov          [rcx][00C],rax
mov          eax,eax
retn

FilesExpand file tree

technotes.md

Latest commit

History