CVS import: othersrc/external/bsd/ibbs

["Alistair G. Crooks" <agc%netbsd.org@localhost>]

Module Name:    othersrc
Committed By:   agc
Date:           Mon Nov 23 05:56:01 UTC 2015

Update of /cvsroot/othersrc/external/bsd/ibbs
In directory ivanova.netbsd.org:/tmp/cvs-serv12751

Log Message:
Import an integer-based version of the Blum Blum Shub random number
generator into othersrc.

        IBBS - Integer Blum Blum Shub Random Number Generator
        =====================================================

        This is a small Blum Blum Shub implementation which uses a Mersenne
        Twister to take 4 bytes of entropy (retrieved from the microseconds
        part of gettimeofday(2)), and generates 2 prime numbers and a seed from
        this.  Each prime number and seed is 16 bits.  A deterministic prime
        check is used to ensure we are dealing with safe/unsafe prime numbers.

        Since 16 bits are used for the two primes, care is taken to avoid
        cycles in the BBS output. If a cycle is detected, the generator is
        re-seeded, and output starts again.

        The RNG seems to be quite efficient, generating numbers at 10 MBps
        on a NetBSD VM running in Fusion hosted on Mac OS X.


        Blum Blum Shub
        ==============

        More information can be found in:

                https://en.wikipedia.org/wiki/Blum_Blum_Shub

        In short, it's a simple, but slow (in theory), random number generator.


        Time to generate random data
        ============================

                % time ./ibbs -n 1000000000 -o 1.out
                99.453u 1.379s 1:41.53 99.3%    0+0k 0+128io 0pf+0w
                %
                
                % bc
                scale = 5
                1000000000 / 101
                9900990.09900

        Looks like almost 10MB/s.  Tests run on a NetBSD-7.99.21 VM running
        under Fusion hosted on an early 2015 Mac Book Pro.


        How random is it?
        =================

        For the dieharder tests, a file with 10^9 random bytes was generated
        and handed to dieharder.

        2 WEAK tests using dieharder-2 - these seem to vary in successive runs
        of tests.  1 FAILED test using dieharder-2.  Every test seems to fail
        this test, though, so something is weird with it.

        For dieharder-3, it's much easier to egrep output:

                % grep PASSED dist/dieharder.out | wc -l
                     109
                % egrep '(FAILED|WEAK)' dist/dieharder.out
                 marsaglia_tsang_gcd|   0|  10000000|     100|0.00374452|   WEAK
                            sts_runs|   2|    100000|     100|0.99938591|   WEAK
                          sts_serial|  12|    100000|     100|0.99799268|   WEAK
                      rgb_lagged_sum|  29|   1000000|     100|0.00041886|   WEAK
                      rgb_lagged_sum|  31|   1000000|     100|0.00000006|  FAILED
                %

        If you're worried about a random number generator failing these tests,
        please note the p-value, and read the dieharder man page, specifically
        the section on p-values.


        Provenance
        ==========
        The Mersenne Twister code comes from (the BSD-licensed):

                http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html

        and is used with thanks.

        Inspiration for the BBS code came from Pate Williams, who wrote some
        code based on multiple-precision numbers. However, ibbs has no
        common code with that.


        Reproducible Results
        ====================

        The API has been structured so that it's possible to have multiple
        ibbs generators in action at any one time. It's also possible to
        seed the ibbs generator so that it produces reproducible results
        (assuming the same seed is used, of course). Standard operation
        will be to have differing results on each run if ibbs_srandom()
        is not used.

I'd be really interested to hear other people's opinions on this code; I have
no idea how predictable this random number generator is - the focus was on
producing something which could be used earlier in the boot sequence, or on
smaller, embedded CPUs.

Status:

Vendor Tag:     CROOKS
Release Tags:   ibbs-base
                
N othersrc/external/bsd/ibbs/Makefile
N othersrc/external/bsd/ibbs/bin/Makefile
N othersrc/external/bsd/ibbs/dist/Makefile
N othersrc/external/bsd/ibbs/dist/dieharder.out
N othersrc/external/bsd/ibbs/dist/README
N othersrc/external/bsd/ibbs/dist/libibbs.3
N othersrc/external/bsd/ibbs/dist/ibbs.1
N othersrc/external/bsd/ibbs/dist/ibbs.c
N othersrc/external/bsd/ibbs/dist/ibbs.h
N othersrc/external/bsd/ibbs/dist/mersenne.h
N othersrc/external/bsd/ibbs/dist/main.c
N othersrc/external/bsd/ibbs/dist/mt19937ar.c
N othersrc/external/bsd/ibbs/dist/provenance
N othersrc/external/bsd/ibbs/lib/shlib_version
N othersrc/external/bsd/ibbs/lib/Makefile

No conflicts created by this import