/*
This software is free for commercial and non-commercial use
subject to the following conditions.

Copyright remains vested in QUALCOMM Incorporated, and Copyright
notices in the code are not to be removed.  If this package is used in
a product, QUALCOMM should be given attribution as the author this
software.  This can be in the form of a textual message at program
startup or in documentation (online or textual) provided with the
package.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

1. Redistributions of source code must retain the copyright notice,
   this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the
   distribution.

3. All advertising materials mentioning features or use of this
   software must display the following acknowledgement:  This product
   includes software developed by QUALCOMM Incorporated.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.

The license and distribution terms for any publically available version
or derivative of this code cannot be changed, that is, this code cannot
simply be copied and put under another distribution license including
the GNU Public License.
*/

/* Run FIPS 140 statistical tests on a file */
/* written by Greg Rose, Copyright C 2000 QUALCOMM Incorporated */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char    *myname;
int     bitnum = 0;

typedef unsigned char   uchar;

#define NBITS 20000
uchar   b[NBITS/8];
int     poker[16];
int     runs[2][7];
int     nerrs;
int     verbose = 0;

int     minrun[7] = { 0, 2267, 1079, 502, 223, 90, 90 };
int     maxrun[7] = { 0, 2733, 1421, 748, 402, 233, 233 };

/* Population count of 1's in a byte */
unsigned char Popcount[] = {
 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

/* end of run */
void
endrun(int last, int run)
{
    if (run >= 34) {
        printf("Sample fails long run test: Run of %d %ds found\n", 
            run, last);
        ++nerrs;
    }
    if (run > 6)
        run = 6;
    ++runs[last][run];
}

int
main(int ac, char **av)
{
    FILE                *f;
    register int        i;
    register uchar      *p;
    register int        c;
    double              X;
    register int        last;
    int                 run;

    myname = av[0];
    if (ac >= 2 && strcmp(av[1], "-v") == 0) {
        verbose = 1;
        ++av; --ac;
    }
    if (ac > 2) {
        fprintf(stderr, "usage: %s [-v] [file]\n", myname);
        return 1;
    }

    if (ac == 1 || strcmp(av[1], "-") == 0) {
        f = stdin;
    } else if ((f = fopen(av[1], "rb")) == NULL) {
        perror(av[1]);
        return 255;
    }

    /* test is defined on 20,000 bits. Read 'em. */
    if (fread(b, 1, sizeof b, f) != sizeof b) {
        fprintf(stderr,
            "Insufficient input for test; %d bits (%d bytes) required\n",
            NBITS, NBITS / 8);
        return 255;
    }

    /* monobit test */
    for (p = b, c = 0; p < &b[sizeof b]; ++p)
        c += Popcount[*p];
    if (verbose) printf("%d ones\n", c);
    if (c <= 9654 || 10346 <= c) {
        printf("Sample fails monobit test: %d ones\n", c);
        ++nerrs;
    }
    
    /* poker test */
    for (p = b; p < &b[sizeof b]; ++p) {
        ++poker[*p & 0xF];
        ++poker[(*p >> 4) & 0xF];
    }
    for (X = i = 0; i < 16; ++i) {
        X += (double)poker[i] * poker[i];
        if (verbose) printf("Poker test: %d 0x%Xs\n", poker[i], i);
    }
    X = 16.0 * X / 5000.0 - 5000.0;
    if (X <= 1.03 || 57.4 <= X) {
        printf("Sample fails poker test: parameter X = %g\n", X);
        ++nerrs;
    }

    /* runs test */
    last = b[0] & 1;
    run = 0;
    for (p = b; p < &b[sizeof b]; ++p) {
        c = *p;
        for (i = 0; i < 8; ++i) {
            if ((c & 1) != last) {
                endrun(last, run);
                run = 0;
                last = c & 1;
            }
            ++run;
            c >>= 1;
        }
    }
    endrun(last, run);

    for (run = 1; run <= 6; ++run) {
        for (last = 0; last <= 1; ++last) {
            if (verbose)
                printf("%d runs of %d %ds\n", runs[last][run], run, last);
            if (runs[last][run] < minrun[run]) {
                printf("Sample fails runs test: too few runs of %d %ds\n",
                    run, last);
                ++nerrs;
            }
            else if (runs[last][run] > maxrun[run]) {
                printf("Sample fails runs test: too many runs of %d %ds\n",
                    run, last);
                ++nerrs;
            }
        }
    }

    /* error code non-zero if problems found */
    if (verbose && nerrs)
        printf("%d errors found\n", nerrs);
    return nerrs <= 255 ? nerrs : 255;
}