LinuxQuestions.org
Page 1 of 3 1 23
Show 50 post(s) from this thread on one page

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Need a fast von Neumann randomness extractor (https://www.linuxquestions.org/questions/programming-9/need-a-fast-von-neumann-randomness-extractor-938949/)

H_TeXMeX_H 04-09-2012 02:39 PM
Need a fast von Neumann randomness extractor
 
What would be the most efficient way of coding this:
https://en.wikipedia.org/wiki/Bernou...ess_extraction

Code:
input        output
00        discard
01        0
10        1
11        discard
I know bash and some C.

The problem is that this maybe very inefficient. I mean how do I work with two bits at a time. I don't even think I can do this in C efficiently.

Any hints on how to go about this ?

I need it because I want to extract randomness from radio signals, and although hashing the input works well, when I look at the histogram I see that it is not level and that there are many values at the two extremes, maybe due to non-uniformity. I was thinking this extractor would help ... I'm no expert tho, but I will try it.

One thing I have done is use GIMP on a generated pnm and tried to change the histogram by hand. It has worked quite well, but would like to do it a different way if possible.

EDIT: The idea is from:
http://www.entropykey.co.uk/res/down...xplanation.pdf
Basically the von Neumann extractor first, and then the hash (which I have working already).

ButterflyMelissa 04-09-2012 02:56 PM
Hmm, a quick thought...
I'd use Perl to get around it, use a for loop, but step per two, then get bit (n) and bit (n-1) and compare.

A quick table:

Quote:
0 AND NOT 0 = 0 dump
1 AND NOT 1 = 0 dump
1 AND NOT 0 = 1 keep
0 AND NOT 1 = 1 keep
If oyu'd like, I'll try some Perl on it...my Perl is somewhat (very) rusty, but I'd like to try... ;)

Thor

H_TeXMeX_H 04-10-2012 06:59 AM
Ok, I think this code works, but do check it:

PHP Code:
// von Neumann extractor
#include <stdio.h>
#include <stdlib.h>

#define WORDSIZE sizeof(int)*8 // in bits

int main (void)
{
    // ! init
    unsigned int input;
    unsigned int counter;
    unsigned int array[WORDSIZE]; // array of bit masks
    
    // init
    unsigned int output = 0;
    unsigned int done = 0;
    unsigned int acounter = 1;
    
    // initialize array
    for (counter = 0; counter < WORDSIZE; counter++)
    {
        array[counter] = acounter;
        acounter *= 2;
    }
    
    fread(&input, sizeof(int), 1, stdin);
    
    while (!feof(stdin))
    {
        for (counter = 0; counter < WORDSIZE; counter += 2)
        {
            if ((input & array[counter]) ^ ((input & array[counter+1]) >> 1))
            {
                output |= (input & array[done]);
                done++;
                if (done == WORDSIZE)
                {
                    fwrite(&output, sizeof(int), 1, stdout);
                    output = 0;
                    done = 0;
                }
            }
        }
        fread(&input, sizeof(int), 1, stdin);
    }    
    
    return 0;
} 
I can see that it does something useful, but I can't be 100% sure that it does what I want. It took 2-3 hours to write.

EDIT: I've done more testing and it works very well, especially after hashing. So I do raw -> extractor -> hash, and the output is very much random.

However, I do want someone to look over the code and see if it does what I think it does. I've never coded stuff like this before.

Nominal Animal 04-10-2012 08:04 AM
I wrote a slightly optimized version. It uses a 256-byte translation table (small enough to stay in CPU cache) to map each input byte to 0 to 4 output bits. Using a single core on Athlon II X4 640 (3GHz) it translates about 200 MB/s (1600 Mbit/s). (Tested using a 256MB file containing all byte values in sequence.)

This is not the fastest I can do, but going faster gets less portable and progressively harder to read and to maintain.

Depending on how you use the data, you probably want to tweak the input and output buffer sizes.
Code:
#include <unistd.h>
#include <errno.h>
#include <poll.h>

/* Buffer sizes. */
#define  IN_BUFSIZ    65536
#define OUT_BUFSIZ    65536

/* Milliseconds to block at most, if input/output nonblocking. */
#define  IN_MILLISECS 10000
#define OUT_MILLISECS 1000

/* Four high bits denote the number of bits used (0-4, 0/16/32/64),
 * and four low bits are the bit pattern.
*/
static const unsigned char bitmap[256] = {
    0, /*  0: 0 bits, ---- */
    16, /*  1: 1 bits, ---0 */
    17, /*  2: 1 bits, ---1 */
    0, /*  3: 0 bits, ---- */
    16, /*  4: 1 bits, --0- */
    32, /*  5: 2 bits, --00 */
    33, /*  6: 2 bits, --01 */
    16, /*  7: 1 bits, --0- */
    17, /*  8: 1 bits, --1- */
    34, /*  9: 2 bits, --10 */
    35, /*  10: 2 bits, --11 */
    17, /*  11: 1 bits, --1- */
    0, /*  12: 0 bits, ---- */
    16, /*  13: 1 bits, ---0 */
    17, /*  14: 1 bits, ---1 */
    0, /*  15: 0 bits, ---- */
    16, /*  16: 1 bits, -0-- */
    32, /*  17: 2 bits, -0-0 */
    33, /*  18: 2 bits, -0-1 */
    16, /*  19: 1 bits, -0-- */
    32, /*  20: 2 bits, -00- */
    48, /*  21: 3 bits, -000 */
    49, /*  22: 3 bits, -001 */
    32, /*  23: 2 bits, -00- */
    33, /*  24: 2 bits, -01- */
    50, /*  25: 3 bits, -010 */
    51, /*  26: 3 bits, -011 */
    33, /*  27: 2 bits, -01- */
    16, /*  28: 1 bits, -0-- */
    32, /*  29: 2 bits, -0-0 */
    33, /*  30: 2 bits, -0-1 */
    16, /*  31: 1 bits, -0-- */
    17, /*  32: 1 bits, -1-- */
    34, /*  33: 2 bits, -1-0 */
    35, /*  34: 2 bits, -1-1 */
    17, /*  35: 1 bits, -1-- */
    34, /*  36: 2 bits, -10- */
    52, /*  37: 3 bits, -100 */
    53, /*  38: 3 bits, -101 */
    34, /*  39: 2 bits, -10- */
    35, /*  40: 2 bits, -11- */
    54, /*  41: 3 bits, -110 */
    55, /*  42: 3 bits, -111 */
    35, /*  43: 2 bits, -11- */
    17, /*  44: 1 bits, -1-- */
    34, /*  45: 2 bits, -1-0 */
    35, /*  46: 2 bits, -1-1 */
    17, /*  47: 1 bits, -1-- */
    0, /*  48: 0 bits, ---- */
    16, /*  49: 1 bits, ---0 */
    17, /*  50: 1 bits, ---1 */
    0, /*  51: 0 bits, ---- */
    16, /*  52: 1 bits, --0- */
    32, /*  53: 2 bits, --00 */
    33, /*  54: 2 bits, --01 */
    16, /*  55: 1 bits, --0- */
    17, /*  56: 1 bits, --1- */
    34, /*  57: 2 bits, --10 */
    35, /*  58: 2 bits, --11 */
    17, /*  59: 1 bits, --1- */
    0, /*  60: 0 bits, ---- */
    16, /*  61: 1 bits, ---0 */
    17, /*  62: 1 bits, ---1 */
    0, /*  63: 0 bits, ---- */
    16, /*  64: 1 bits, 0--- */
    32, /*  65: 2 bits, 0--0 */
    33, /*  66: 2 bits, 0--1 */
    16, /*  67: 1 bits, 0--- */
    32, /*  68: 2 bits, 0-0- */
    48, /*  69: 3 bits, 0-00 */
    49, /*  70: 3 bits, 0-01 */
    32, /*  71: 2 bits, 0-0- */
    33, /*  72: 2 bits, 0-1- */
    50, /*  73: 3 bits, 0-10 */
    51, /*  74: 3 bits, 0-11 */
    33, /*  75: 2 bits, 0-1- */
    16, /*  76: 1 bits, 0--- */
    32, /*  77: 2 bits, 0--0 */
    33, /*  78: 2 bits, 0--1 */
    16, /*  79: 1 bits, 0--- */
    32, /*  80: 2 bits, 00-- */
    48, /*  81: 3 bits, 00-0 */
    49, /*  82: 3 bits, 00-1 */
    32, /*  83: 2 bits, 00-- */
    48, /*  84: 3 bits, 000- */
    64, /*  85: 4 bits, 0000 */
    65, /*  86: 4 bits, 0001 */
    48, /*  87: 3 bits, 000- */
    49, /*  88: 3 bits, 001- */
    66, /*  89: 4 bits, 0010 */
    67, /*  90: 4 bits, 0011 */
    49, /*  91: 3 bits, 001- */
    32, /*  92: 2 bits, 00-- */
    48, /*  93: 3 bits, 00-0 */
    49, /*  94: 3 bits, 00-1 */
    32, /*  95: 2 bits, 00-- */
    33, /*  96: 2 bits, 01-- */
    50, /*  97: 3 bits, 01-0 */
    51, /*  98: 3 bits, 01-1 */
    33, /*  99: 2 bits, 01-- */
    50, /* 100: 3 bits, 010- */
    68, /* 101: 4 bits, 0100 */
    69, /* 102: 4 bits, 0101 */
    50, /* 103: 3 bits, 010- */
    51, /* 104: 3 bits, 011- */
    70, /* 105: 4 bits, 0110 */
    71, /* 106: 4 bits, 0111 */
    51, /* 107: 3 bits, 011- */
    33, /* 108: 2 bits, 01-- */
    50, /* 109: 3 bits, 01-0 */
    51, /* 110: 3 bits, 01-1 */
    33, /* 111: 2 bits, 01-- */
    16, /* 112: 1 bits, 0--- */
    32, /* 113: 2 bits, 0--0 */
    33, /* 114: 2 bits, 0--1 */
    16, /* 115: 1 bits, 0--- */
    32, /* 116: 2 bits, 0-0- */
    48, /* 117: 3 bits, 0-00 */
    49, /* 118: 3 bits, 0-01 */
    32, /* 119: 2 bits, 0-0- */
    33, /* 120: 2 bits, 0-1- */
    50, /* 121: 3 bits, 0-10 */
    51, /* 122: 3 bits, 0-11 */
    33, /* 123: 2 bits, 0-1- */
    16, /* 124: 1 bits, 0--- */
    32, /* 125: 2 bits, 0--0 */
    33, /* 126: 2 bits, 0--1 */
    16, /* 127: 1 bits, 0--- */
    17, /* 128: 1 bits, 1--- */
    34, /* 129: 2 bits, 1--0 */
    35, /* 130: 2 bits, 1--1 */
    17, /* 131: 1 bits, 1--- */
    34, /* 132: 2 bits, 1-0- */
    52, /* 133: 3 bits, 1-00 */
    53, /* 134: 3 bits, 1-01 */
    34, /* 135: 2 bits, 1-0- */
    35, /* 136: 2 bits, 1-1- */
    54, /* 137: 3 bits, 1-10 */
    55, /* 138: 3 bits, 1-11 */
    35, /* 139: 2 bits, 1-1- */
    17, /* 140: 1 bits, 1--- */
    34, /* 141: 2 bits, 1--0 */
    35, /* 142: 2 bits, 1--1 */
    17, /* 143: 1 bits, 1--- */
    34, /* 144: 2 bits, 10-- */
    52, /* 145: 3 bits, 10-0 */
    53, /* 146: 3 bits, 10-1 */
    34, /* 147: 2 bits, 10-- */
    52, /* 148: 3 bits, 100- */
    72, /* 149: 4 bits, 1000 */
    73, /* 150: 4 bits, 1001 */
    52, /* 151: 3 bits, 100- */
    53, /* 152: 3 bits, 101- */
    74, /* 153: 4 bits, 1010 */
    75, /* 154: 4 bits, 1011 */
    53, /* 155: 3 bits, 101- */
    34, /* 156: 2 bits, 10-- */
    52, /* 157: 3 bits, 10-0 */
    53, /* 158: 3 bits, 10-1 */
    34, /* 159: 2 bits, 10-- */
    35, /* 160: 2 bits, 11-- */
    54, /* 161: 3 bits, 11-0 */
    55, /* 162: 3 bits, 11-1 */
    35, /* 163: 2 bits, 11-- */
    54, /* 164: 3 bits, 110- */
    76, /* 165: 4 bits, 1100 */
    77, /* 166: 4 bits, 1101 */
    54, /* 167: 3 bits, 110- */
    55, /* 168: 3 bits, 111- */
    78, /* 169: 4 bits, 1110 */
    79, /* 170: 4 bits, 1111 */
    55, /* 171: 3 bits, 111- */
    35, /* 172: 2 bits, 11-- */
    54, /* 173: 3 bits, 11-0 */
    55, /* 174: 3 bits, 11-1 */
    35, /* 175: 2 bits, 11-- */
    17, /* 176: 1 bits, 1--- */
    34, /* 177: 2 bits, 1--0 */
    35, /* 178: 2 bits, 1--1 */
    17, /* 179: 1 bits, 1--- */
    34, /* 180: 2 bits, 1-0- */
    52, /* 181: 3 bits, 1-00 */
    53, /* 182: 3 bits, 1-01 */
    34, /* 183: 2 bits, 1-0- */
    35, /* 184: 2 bits, 1-1- */
    54, /* 185: 3 bits, 1-10 */
    55, /* 186: 3 bits, 1-11 */
    35, /* 187: 2 bits, 1-1- */
    17, /* 188: 1 bits, 1--- */
    34, /* 189: 2 bits, 1--0 */
    35, /* 190: 2 bits, 1--1 */
    17, /* 191: 1 bits, 1--- */
    0, /* 192: 0 bits, ---- */
    16, /* 193: 1 bits, ---0 */
    17, /* 194: 1 bits, ---1 */
    0, /* 195: 0 bits, ---- */
    16, /* 196: 1 bits, --0- */
    32, /* 197: 2 bits, --00 */
    33, /* 198: 2 bits, --01 */
    16, /* 199: 1 bits, --0- */
    17, /* 200: 1 bits, --1- */
    34, /* 201: 2 bits, --10 */
    35, /* 202: 2 bits, --11 */
    17, /* 203: 1 bits, --1- */
    0, /* 204: 0 bits, ---- */
    16, /* 205: 1 bits, ---0 */
    17, /* 206: 1 bits, ---1 */
    0, /* 207: 0 bits, ---- */
    16, /* 208: 1 bits, -0-- */
    32, /* 209: 2 bits, -0-0 */
    33, /* 210: 2 bits, -0-1 */
    16, /* 211: 1 bits, -0-- */
    32, /* 212: 2 bits, -00- */
    48, /* 213: 3 bits, -000 */
    49, /* 214: 3 bits, -001 */
    32, /* 215: 2 bits, -00- */
    33, /* 216: 2 bits, -01- */
    50, /* 217: 3 bits, -010 */
    51, /* 218: 3 bits, -011 */
    33, /* 219: 2 bits, -01- */
    16, /* 220: 1 bits, -0-- */
    32, /* 221: 2 bits, -0-0 */
    33, /* 222: 2 bits, -0-1 */
    16, /* 223: 1 bits, -0-- */
    17, /* 224: 1 bits, -1-- */
    34, /* 225: 2 bits, -1-0 */
    35, /* 226: 2 bits, -1-1 */
    17, /* 227: 1 bits, -1-- */
    34, /* 228: 2 bits, -10- */
    52, /* 229: 3 bits, -100 */
    53, /* 230: 3 bits, -101 */
    34, /* 231: 2 bits, -10- */
    35, /* 232: 2 bits, -11- */
    54, /* 233: 3 bits, -110 */
    55, /* 234: 3 bits, -111 */
    35, /* 235: 2 bits, -11- */
    17, /* 236: 1 bits, -1-- */
    34, /* 237: 2 bits, -1-0 */
    35, /* 238: 2 bits, -1-1 */
    17, /* 239: 1 bits, -1-- */
    0, /* 240: 0 bits, ---- */
    16, /* 241: 1 bits, ---0 */
    17, /* 242: 1 bits, ---1 */
    0, /* 243: 0 bits, ---- */
    16, /* 244: 1 bits, --0- */
    32, /* 245: 2 bits, --00 */
    33, /* 246: 2 bits, --01 */
    16, /* 247: 1 bits, --0- */
    17, /* 248: 1 bits, --1- */
    34, /* 249: 2 bits, --10 */
    35, /* 250: 2 bits, --11 */
    17, /* 251: 1 bits, --1- */
    0, /* 252: 0 bits, ---- */
    16, /* 253: 1 bits, ---0 */
    17, /* 254: 1 bits, ---1 */
    0, /* 255: 0 bits, ---- */
};

/* Write all of the data. Return 0 if success, errno otherwise.
*/
static int writeall(const int fd, unsigned char *const data, size_t const size)
{
    unsigned char *const ends = data + size;
    unsigned char      *next = data;
    struct pollfd        list[2];
    ssize_t              bytes;
    int                  saved_errno;

    saved_errno = errno;

    while (next < ends) {

        bytes = write(fd, next, (size_t)(ends - next));

        if (bytes > (ssize_t)0) {
            next += bytes;
            continue;
        }

        /* Library error? */
        if (bytes != (ssize_t)-1)
            return errno = EIO;

        /* Interrupted by a signal? */
        if (errno == EINTR)
            continue;

        /* Nonblocking output? */
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            list[0].fd = fd;
            list[0].events = POLLOUT | POLLERR | POLLHUP;
            list[0].revents = 0;
            poll((struct pollfd *)&list, 1, OUT_MILLISECS);
            continue;
        }

        /* Write error. */
        return errno;
    }

    /* Success. */
    errno = saved_errno;
    return 0;
}

/* Read some input, up to the buffer full.
 * Return number of bytes read, or -1 with errno set.
*/
static ssize_t readany(const int fd, unsigned char *const data, size_t const size)
{
    struct pollfd list[2];
    ssize_t      bytes;
    int          saved_errno;

    saved_errno = errno;

    while (1) {

        bytes = read(fd, data, size);

        /* End of input, or more data read? */
        if (bytes >= (ssize_t)0) {
            errno = saved_errno;
            return bytes;
        }

        /* Library error? */
        if (bytes != (ssize_t)-1) {
            errno = EIO;
            return (ssize_t)-1;
        }

        /* Interrupted by a signal? */
        if (errno == EINTR)
            continue;

        /* Nonblocking input, and should block? */
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            list[0].fd = fd;
            list[0].events = POLLIN | POLLPRI;
            list[0].revents = 0;

            poll((struct pollfd *)&list, 1, IN_MILLISECS);
            continue;
        }

        /* I/O error. */
        return (ssize_t)-1;
    }
}

int main(void)
{
    const int            in_fd = STDIN_FILENO;
    unsigned char        in_data[IN_BUFSIZ];

    const int            out_fd = STDOUT_FILENO;
    unsigned char        out_data[OUT_BUFSIZ];
    unsigned char      *out_next = out_data;
    unsigned char *const out_ends = out_data + sizeof out_data;
    unsigned int        out_bits = 0U;
    unsigned int        out_part = 0U;

    ssize_t              bytes;
    int                  result = 0;
    int                  exitcode = 0;

    while (1) {

        bytes = readany(in_fd, in_data, sizeof in_data);

        /* End of input? */
        if (bytes == (ssize_t)0)
            break;

        /* Read error? */
        if (bytes == (ssize_t)-1) {
            exitcode = 1;
            break;
        }

        /* We did receive 'bytes' bytes. */
        {
            unsigned char      *in_next = in_data;
            unsigned char *const in_ends = in_data + bytes;

            while (in_next < in_ends) {
                const unsigned char byte = bitmap[*(in_next++)];
                const unsigned int  part = byte & 15U; /* Bit pattern */
                const unsigned int  bits = byte >> 4U; /* Number of bits */

                /* Add the bits to current temporary part. */
                out_part <<= bits;  /* Shift existing bits up, */
                out_part |= part;  /* to make room for the new bits, */
                out_bits += bits;  /* and add the new bit count to the total. */

                /* Full byte? */
                if (out_bits >= 8U) {
                    /* Save the highest/oldest bits. */
                    *(out_next++) = out_part >> (out_bits - 8U);
                    out_bits -= 8;
                    out_part &= (1U << out_bits) - 1U;

                    /* Time to flush output buffer? */
                    if (out_next >= out_ends) {
                        result = writeall(out_fd, out_data, (size_t)(out_next - out_data));
                        if (result)
                            break;

                        out_next = out_data;
                    }
                }
            }
        }

        /* Write error? */
        if (result)
            break;
    }

    /* Flush output buffer? */
    if (!result && out_next > out_data)
        result = writeall(out_fd, out_data, (size_t)(out_next - out_data));

    /* Note write error in the exit code. */
    if (result)
        exitcode |= 2;

    return exitcode;
}
The core of the code is rather simple: with in_data pointing to the buffer containing bytes bytes,
Code:
            unsigned char      *in_next = in_data;
            unsigned char *const in_ends = in_data + bytes;

            while (in_next < in_ends) {
                const unsigned char byte = bitmap[*(in_next++)];
                const unsigned int  part = byte & 15U; /* Bit pattern */
                const unsigned int  bits = byte >> 4U; /* Number of bits */

                /* Add the bits to current temporary part. */
                out_part <<= bits;  /* Shift existing bits up, */
                out_part |= part;  /* to make room for the new bits, */
                out_bits += bits;  /* and add the new bit count to the total. */

                /* Full byte? */
                if (out_bits >= 8U) {
                    /* Save the highest/oldest bits. */
                    *(out_next++) = out_part >> (out_bits - 8U);
                    out_bits -= 8;
                    out_part &= (1U << out_bits) - 1U;
Above, part contains the actual bits, bits the number of valid (low) bits in part. A larger accumulator, out_part with out_bits low bits in it collects the bit groups, then stores full bytes into a buffer. Note that highest bits are the oldest in out_part.

The bitmask array maps each input byte into two nibbles (high and low four bits):(the number of) bits and part. I used a trivial generator program to compute the array. (Note: And I got it wrong on the first edit. This is the fixed version.)

When a full byte is extracted, we need to extract the high bits (since they are the oldest bits), and keep the excess (low/new) bits intact. Masking the input (the last line) is not really necessary, since we do shift the value before adding the new bits (i.e. new bits are always added to clear bits) -- in other words the results are the same if you remove the masking altogether -- but I like to be careful.

The program will work with both blocking and non-blocking standard input and output.

Let me know if you want it in a "library" form you can embed in your own code.

I'll take a look at your own code next, H_TeXMeX_H.

Edit: H_TeXMeX_H, your code should work perfectly, as far as I can tell. I can see nothing wrong in it. (I did not test it, though.)

Your code will be limited by stdio.h (fread() and fwrite()) speed; that is why I used low-level I/O instead. You can alleviate that by reading and writing larger buffers at once, or you too can switch to low-level I/O.

Also, my tests indicate that on an Athlon II X4 640, doing bit pairs at a time takes about 5x to 6x the time the lookup takes, thus incurring > 5x slowdown compared to my lookup method.

Note: This is the fixed version, which only works with architectures that have 8-bit unsigned chars; the code does not check that, though. Look at my post #10 in this thread for a better example code. It is slightly faster, too, and much more portable.

H_TeXMeX_H 04-10-2012 08:32 AM
Wow, that's way past my abilities. Many thanks for taking the time to write it. I will try it right away :)

H_TeXMeX_H 04-10-2012 09:36 AM
Ok, I have fixed my code and it works properly now, there was a mistake which I missed:

PHP Code:
// von Neumann extractor
#include <stdio.h>
#include <stdlib.h>

#define WORDSIZE sizeof(int)*8 // in bits

int main (void)
{
    // ! init
    unsigned int input;
    unsigned int counter;
    unsigned int array[WORDSIZE]; // array of bit masks
    
    // init
    unsigned int output = 0;
    unsigned int done = 0;
    unsigned int acounter = 1;
    
    // initialize array
    for (counter = 0; counter < WORDSIZE; counter++)
    {
        array[counter] = acounter;
        acounter *= 2;
    }
    
    while (fread(&input, sizeof(int), 1, stdin))
    {
        for (counter = 0; counter < WORDSIZE; counter += 2)
        {
            if ((input & array[counter]) ^ ((input & array[counter+1]) >> 1))
            {
                if (counter > done)
                {
                    output |= ((input & array[counter]) >> (counter-done));
                }
                else if (counter < done)
                {
                    output |= ((input & array[counter]) << (done-counter));
                }
                else
                {
                    output |= (input & array[counter]);
                }
                done++;
                if (done == WORDSIZE)
                {
                    fwrite(&output, sizeof(int), 1, stdout);
                    output = 0;
                    done = 0;
                }
            }
        }
    }    
    
    return 0;
} 
My code now works better than I could have hoped. The output is random as is, without any hashing, but even better with hashing.

However, there is something unusual...

@ Nominal Animal

Using your code I don't get the same result. This is strange. I tested results from both and mine produces more random output. I'm not sure of the cause. Yours is most certainly the fastest. I will try to investigate into the cause of this discrepancy.

Nominal Animal 04-10-2012 11:39 AM
Quote:
Originally Posted by H_TeXMeX_H (Post 4649292)
@ Nominal Animal

Using your code I don't get the same result. This is strange.
Is it just because we build the result bytes in opposite orders? In my code, highest bit in each output byte is the earliest from input; in yours, the lowest bit is. I'll write some test cases to check my code. I often make mistakes, so it is more than likely there is a bug there.

Edit: Oh, yes, I mangled the output bit order. Fixed now; both my codes yield the same output, the one I outline in post #9 in this thread.

H_TeXMeX_H 04-10-2012 12:19 PM
Oh, ok, the output order may be it. I'll run some more tests.

Nominal Animal 04-10-2012 02:09 PM
Yes, there was a bug on my code (in the bitmask array and how it was used). It's fixed now.

Here is the table of bits you should get from eight-bit bytes, with - indicating discarded bit pair, zero 01 and one 10 bit pairs, with most significant bits left. First row corresponds to values 0 to 15, and last row to values 240 to 255:
Code:
---- ---0 ---1 ---- --0- --00 --01 --0- --1- --10 --11 --1- ---- ---0 ---1 ----
-0-- -0-0 -0-1 -0-- -00- -000 -001 -00- -01- -010 -011 -01- -0-- -0-0 -0-1 -0--
-1-- -1-0 -1-1 -1-- -10- -100 -101 -10- -11- -110 -111 -11- -1-- -1-0 -1-1 -1--
---- ---0 ---1 ---- --0- --00 --01 --0- --1- --10 --11 --1- ---- ---0 ---1 ----
0--- 0--0 0--1 0--- 0-0- 0-00 0-01 0-0- 0-1- 0-10 0-11 0-1- 0--- 0--0 0--1 0---
00-- 00-0 00-1 00-- 000- 0000 0001 000- 001- 0010 0011 001- 00-- 00-0 00-1 00--
01-- 01-0 01-1 01-- 010- 0100 0101 010- 011- 0110 0111 011- 01-- 01-0 01-1 01--
0--- 0--0 0--1 0--- 0-0- 0-00 0-01 0-0- 0-1- 0-10 0-11 0-1- 0--- 0--0 0--1 0---
1--- 1--0 1--1 1--- 1-0- 1-00 1-01 1-0- 1-1- 1-10 1-11 1-1- 1--- 1--0 1--1 1---
10-- 10-0 10-1 10-- 100- 1000 1001 100- 101- 1010 1011 101- 10-- 10-0 10-1 10--
11-- 11-0 11-1 11-- 110- 1100 1101 110- 111- 1110 1111 111- 11-- 11-0 11-1 11--
1--- 1--0 1--1 1--- 1-0- 1-00 1-01 1-0- 1-1- 1-10 1-11 1-1- 1--- 1--0 1--1 1---
---- ---0 ---1 ---- --0- --00 --01 --0- --1- --10 --11 --1- ---- ---0 ---1 ----
-0-- -0-0 -0-1 -0-- -00- -000 -001 -00- -01- -010 -011 -01- -0-- -0-0 -0-1 -0--
-1-- -1-0 -1-1 -1-- -10- -100 -101 -10- -11- -110 -111 -11- -1-- -1-0 -1-1 -1--
---- ---0 ---1 ---- --0- --00 --01 --0- --1- --10 --11 --1- ---- ---0 ---1 ----
In hexadecimal, the above zero and one bits correspond to 64 bytes,
Code:
42 dd 08 04 53 42 de 96  f7 f7 42 dd 08 04 53 42
01 00 08 24 64 04 53 52  2a 6c ed 4d 08 04 53 42
de 96 f7 f7 a5 a4 4c b5  76 96 f7 f6 6e fd ff df
de 96 f7 f7 42 dd 08 04  53 42 de 96 f7 f7 42 dd
The byte values are a very good test vector, which you can generate in e.g. Bash using
Code:
for ((i=0; i<256; i++)) ; do h=$(printf '%02x' $i) ; printf "\x$h" ; done

Nominal Animal 04-10-2012 05:03 PM
Here is my von Neumann randomness extractor, which provides the output described in my post above.

Instead of hardcoding the array, I precalculate it at the beginning of the program. This way the code should compile on architectures with different byte size (as long as it is at most the size of an unsigned int, as I use an unsigned int bit accumulator).

The precalculator, init_random(), simply takes each possible input value (unsigned char) and converts it bit pair by bit pair. It consumes and saves ascending bits, starting with the lowest bits first. The value loop is in descending order, but since each value is a self-contained unit, this does not matter. While calculating bit pairs is slow compared to using a lookup, doing it once for each possible input value does not take appreciable time, and allows portable code. Therefore it is worthwhile.

You might notice in the inner loop that I handle the bit accumulator has more than a word and bit accumulator has exactly a word cases separately. It turns out that on my architecture and gcc-4.6.1, this is ten percent faster.

This version is roughly 5% faster on my architecture than my previous code in this thread, handling about 218000000 bytes of input per second on an Athlon II X4 640.
Code:
#include <unistd.h>
#include <limits.h>    /* For CHAR_BIT */
#include <poll.h>
#include <errno.h>

/* Input and output buffer sizes */
#define  OUTPUT_CHARS          65536
#define  INPUT_CHARS          65536

/* Maximum polling durations in milliseconds */
#define  OUTPUT_POLL_MILLISECS  10000
#define  INPUT_POLL_MILLISECS  10000

/* Number of random bit in each unsigned char */
static unsigned char random_bits[1 << CHAR_BIT];

/* Random bit patterns for each unsigned char */
static unsigned char random_pattern[1 << CHAR_BIT];

/* Initialize the above randomness arrays.
*/
static void init_random(void)
{
    unsigned int    i = 1U << CHAR_BIT;
    unsigned char  bit_pattern, bit_count, left;

    while (i-->0U) {

        left = i;
        bit_pattern = 0U;
        bit_count = 0U;

        while (left)
            if ((left & 3U) == 1U) {
                bit_count++;
                left >>= 2U;

            } else
            if ((left & 3U) == 2U) {
                bit_pattern |= 1U << bit_count;
                bit_count++;
                left >>= 2U;

            } else
                left >>= 2U;

        random_bits[i] = bit_count;
        random_pattern[i] = bit_pattern;
    }
}

/* Output buffer. */
static int                  output_descriptor = STDOUT_FILENO;
static unsigned char        output_data[OUTPUT_CHARS];
static unsigned char        *output_next = output_data;
static unsigned char *const  output_ends = output_data + sizeof output_data;

/* Returns zero if success, nonzero errno otherwise.
*/
static int output_flush(void)
{
    struct pollfd              list[1];
    const unsigned char        *head = output_data;
    const unsigned char *const  tail = output_next;
    ssize_t                    bytes;

    output_next = output_data;

    while (head < tail) {

        bytes = write(output_descriptor, head, (size_t)(tail - head));

        if (bytes > (ssize_t)0) {
            head += bytes;
            continue;

        } else
        if (bytes != (ssize_t)-1) {
            return errno = EIO;

        } else
        if (errno == EINTR) {
            /* Interrupted by a signal. */
            continue;

        } else
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            /* Nonblocking I/O. Block until output is possible. */
            list[0].fd = output_descriptor;
            list[0].events = POLLOUT | POLLERR | POLLHUP;
            list[0].revents = 0;
            /* Ignore poll result, */
            poll((struct pollfd *)&list, 1, OUTPUT_POLL_MILLISECS);
            /* since we retry write anyway. */
            continue;
        } else {
            /* Write error. */
            return errno;
        }
    }

    /* Success. */
    return 0;
}

/* Helper function to read any data.
 * Returns the number of bytes actually read,
 * or zero with errno zero if end of input,
 * or zero with errno set if read error.
*/
static size_t readany(const int descriptor, void *const data, const size_t size)
{
    struct pollfd  list[0];
    ssize_t        bytes;

    while (1) {

        bytes = read(descriptor, data, size);

        if (bytes > (ssize_t)0) {
            return (size_t)bytes;

        } else
        if (bytes == (ssize_t)0) {
            errno = 0;
            return (size_t)0;

        } else
        if (bytes != (ssize_t)-1) {
            errno = EIO;
            return (size_t)0;

        } else
        if (errno == EINTR) {
            /* Interrupted by a signal; retry */
            continue;

        } else
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            /* Nonblocking I/O; poll */
            list[0].fd = descriptor;
            list[0].events = POLLIN | POLLPRI;
            list[0].revents = 0;
            /* Ignore poll() return values, */
            poll((struct pollfd *)&list, 1, INPUT_POLL_MILLISECS);
            /* since we retry the read anyway. */
            continue;

        } else {
            /* Read error; reason already in errno. */
            return (size_t)0;
        }
    }
}

int main(void)
{
    unsigned char  input_data[INPUT_CHARS];
    size_t          input_size;

    int            curr_bits = 0;
    unsigned int    curr_pattern = 0U;

    int            exit_status = 0;

    init_random();

    while (1) {

        input_size = readany(STDIN_FILENO, input_data, sizeof input_data);
        if (!input_size) {
            if (errno)
                exit_status |= 1; /* For read error */
            break;
        }

        {
            const unsigned char      *head = input_data;
            const unsigned char *const tail = input_data + input_size;

            while (head < tail) {
                const int          bits = random_bits[*head];
                const unsigned int pattern = random_pattern[*head];

                head++;

                if (!bits)
                    continue;
                   
                curr_pattern = (curr_pattern << bits) | pattern;
                curr_bits += bits;

                if (curr_bits > CHAR_BIT) {

                    *(output_next++) = curr_pattern >> (curr_bits - CHAR_BIT);
                    curr_pattern &= (1U << (curr_bits - CHAR_BIT)) - 1U;
                    curr_bits -= CHAR_BIT;

                    if (output_next >= output_ends)
                        if (output_flush()) {
                            exit_status |= 2;
                            break;
                        }

                } else
                if (curr_bits == CHAR_BIT) {

                    *(output_next++) = curr_pattern;
                    curr_pattern = 0U;
                    curr_bits = 0U;

                    if (output_next >= output_ends)
                        if (output_flush()) {
                            exit_status |= 2;
                            break;
                        }

                }
            }

            if (exit_status)
                break;

        }
    }

    if (output_flush())
        exit_status |= 2;

    return exit_status;
}

H_TeXMeX_H 04-11-2012 04:13 AM
Thanks, I think that fixed it. It now seems to generate equivalent randomness to mine. It is about 7 times faster, so many thanks again :)

I will mark this solved.

ta0kira 04-11-2012 12:03 PM
Here's another take on it, if you're interested. It's shorter than the last one Nominal Animal posted, but about 7% slower. I'm pretty sure the difference is due to more stack usage (i.e. less can be taken care of in registers.)
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <unistd.h>
#include <stdint.h>


int main(int argc, char *argv[])
{
        const unsigned int buffer_size = sysconf(_SC_PAGESIZE);
        unsigned char *input_buffer = malloc(buffer_size), *output_buffer = malloc(buffer_size);
        ssize_t read_size, output_size = 0;
        unsigned char *byte;
        int I;

        typedef uint64_t working_type;
        working_type input = 0, output = 0, bit = 1;

        while ((read_size = read(STDIN_FILENO, input_buffer, buffer_size)) > 0)
        for (byte = input_buffer; byte < input_buffer + read_size; byte += sizeof input)
        for (I = 0, input = *(working_type*) byte; I < sizeof input * CHAR_BIT; I += 2, input >>= 2)
        if ((input & 3) == 1 || (input & 3) == 2) //(using '(input & 3) % 3' looks cleaner, but it's slower)
        {
        if (input & 1) output |= bit;
        if (!(bit <<= 1))
        {
        *(working_type*) (output_buffer + output_size) = output;
        if ((output_size += sizeof output) >= buffer_size)
          {
        write(STDOUT_FILENO, output_buffer, buffer_size);
        output_size = 0;
          }
        output = 0;
        bit    = 1;
        }
        }

        write(STDOUT_FILENO, output_buffer, output_size);

        return 0;
}
Kevin Barry

edit: Actually, it takes 3.5x longer when reading from a file and dumping to /dev/null. Sorry about the false claim!

H_TeXMeX_H 04-11-2012 12:54 PM
Thanks for the other take. I will try to understand it as well :)

I do not understand one thing:

Using the test sequence (0-255), the output for mine and ta0kira:

Code:
0x00000000: DD42F7F7 96DE4253 0408DD42 F7F796DE    ÝB÷÷.ÞBS..ÝB÷÷.Þ
0x00000010: DFFFFD6E F6F79676 B54CA4A5 F7F796DE    ßÿýnö÷.vµL¤¥÷÷.Þ
0x00000020: 42530408 4DED6C2A 52530464 24080001    BS..Míl*RS.d$...
0x00000030: 42530408 DD42F7F7 96DE4253 0408DD42    BS..ÝB÷÷.ÞBS..ÝB
Output for Nominal Animal:

Code:
0x00000000: 42DD0804 5342DE96 F7F742DD 08045342    BÝ..SBÞ.÷÷BÝ..SB
0x00000010: 01000824 64045352 2A6CED4D 08045342    ...$d.SR*líM..SB
0x00000020: DE96F7F7 A5A44CB5 7696F7F6 6EFDFFDF    Þ.÷÷¥¤Lµv.÷önýÿß
0x00000030: DE96F7F7 42DD0804 5342DE96 F7F742DD    Þ.÷÷BÝ..SBÞ.÷÷BÝ
How does this difference appear ? It doesn't seem to be reversed completely, only parts of it. It is hard to understand. I know all of these work just fine, but I can't understand the difference.

ta0kira 04-11-2012 01:49 PM
Quote:
Originally Posted by H_TeXMeX_H (Post 4650371)
Thanks for the other take. I will try to understand it as well :)
I ran mine differently and it's slower than I thought (see my edit.)
Quote:
Originally Posted by H_TeXMeX_H (Post 4650371)
How does this difference appear ? It doesn't seem to be reversed completely, only parts of it. It is hard to understand. I know all of these work just fine, but I can't understand the difference.
I think the difference is where the new bit is placed in the output. I put the new bit in the next-lowest bit of a 64-bit integer. If I'd used a 32-bit or 8-bit then the output would be different. It would also be different if I shifted the old value and placed the new bit in bit 1. I think Nominal Animal did one or more of those things differently.
Kevin Barry

H_TeXMeX_H 04-11-2012 02:13 PM
I see, so it really depends on many things. Still the output is equivalent, so I can use it.

In case anyone is wondering what I'm doing with all this.

I hooked up a radio headphone jack to my mic jack using an audio recording cable, something like:
http://www.sonicelectronix.com/item_...he-AUX3BL.html

I tuned the radio to a noisy channel. This is the hardest part, because noise doesn't always mean randomness. I did tests on the output using ENT and this script:

Code:
#!/bin/sh

if test $# != 1
then
        echo "Usage: $(basename $0) input"
        echo 'input: input file'
        exit 1
fi

side="$(stat -c '%s' "$1" | awk '{ print int($1^(1/2)) }')"

rawtopgm "$side" "$side" "$1"

exit 0
Once I have a decent channel, I have to extract randomness as much as possible. The results vary.

As per the schema I posted in the OP, I first run a von Neumann extractor, any of these will work just fine, but performance differs. Nominal Animal's code is unsurpassed.

Then I run a hash on blocks of that output. This was hard to code, probably because I'm not that good at C. However, I have coded a small add-on to the whirlpool hash reference implementation. This is the part that I changed:

Code:
int main(void) {
       
        // ! init
        struct NESSIEstruct w;
        u8 digest[DIGESTBYTES];
       
        // ! free
        unsigned char * buffer;
       
        // malloc
        buffer = (unsigned char*) malloc (DIGESTBYTES);
        if ( buffer == NULL )
        {
                fprintf(stderr, "ERROR: not enough memory !\n");
                exit(2);
        }
       
        // hash
        while (fread(buffer, DIGESTBYTES, 1, stdin))
        {
                NESSIEinit(&w);
                NESSIEadd(buffer, DIGESTBITS, &w); // in bits
                NESSIEfinalize(&w, digest);
               
                fwrite(digest, DIGESTBYTES, 1, stdout);
        }
       
        // free
        free(buffer);
       
        return 0;
}
The output is quite random, and I would say may be good enough to use as such, at least according to the tests. You should do your own tests tho, because there's a lot of variables here.

I can just pipe the output from the radio like this:

Code:
rrec | vnemed | whash > output
rrec is just a wrapper for 'arecord -c 1 -r 44100 -t raw', the rest are the extractor and whirlpool hash.


All times are GMT -5. The time now is 04:30 AM.
Page 1 of 3 1 23
Show 50 post(s) from this thread on one page