rand16.c

/* rand16.c - 128-bit linear congruential generator
 *
 * Version 1.0  16 Feb 2009  Chris Nyberg <chris.nyberg@ordinal.com>
 */

/* This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the author be held liable for any damages
 * arising from the use of this software.
 */

/* This file implements a 128-bit linear congruential generator.
 * Specifically, if X0 is the most recently issued 128-bit random
 * number (or a seed of 0 if no random number has already been generated,
 * the next number to be generated, X1, is equal to:
 * X1 = (a * X0 + c) mod 2**128
 * where a is 47026247687942121848144207491837523525
 *            or 0x2360ed051fc65da44385df649fccf645
 *   and c is 98910279301475397889117759788405497857
 *            or 0x4a696d47726179524950202020202001
 * The coefficient "a" is suggested by:
 * Pierre L'Ecuyer, "Tables of linear congruential generators of different
 * sizes and good lattice structure", Mathematics of Computation, 68
 * pp. 249 - 260 (1999)
 * http://www.ams.org/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf
 * The constant "c" meets the simple suggestion by the same reference that
 * it be odd.
 *
 * There is also a facility for quickly advancing the state of the
 * generator by a fixed number of steps - this facilitates parallel
 * generation.
 *
 *
 */
#include <stdio.h>
#include <string.h>
#include "rand16.h"


/* The "Gen" array contain powers of 2 of the linear congruential generator.
 * The index 0 struct contain the "a" coefficient and "c" constant for the
 * generator.  That is, the generator is:
 *    f(x) = (Gen[0].a * x + Gen[0].c) mod 2**128
 *
 * All structs after the first contain an "a" and "c" that
 * comprise the square of the previous function.
 *
 * f**2(x) = (Gen[1].a * x + Gen[1].c) mod 2**128
 * f**4(x) = (Gen[2].a * x + Gen[2].c) mod 2**128
 * f**8(x) = (Gen[3].a * x + Gen[3].c) mod 2**128
 * ...
 */
static struct
{
    u16 a;
    u16 c;
} Gen[128] =
{
    /* [  0].a */ {{0x2360ed051fc65da4LL, 0x4385df649fccf645LL},
    /* [  0].c */     {0x4a696d4772617952LL, 0x4950202020202001LL}},
    /* [  1].a */ {{0x17bce35bdf69743cLL, 0x529ed9eb20e0ae99LL},
    /* [  1].c */     {0x95e0e48262b3edfeLL, 0x04479485c755b646LL}},
    /* [  2].a */ {{0xf4dd417327db7a9bLL, 0xd194dfbe42d45771LL},
    /* [  2].c */     {0x882a02c315362b60LL, 0x765f100068b33a1cLL}},
    /* [  3].a */ {{0x6347af777a7898f6LL, 0xd1a2d6f33505ffe1LL},
    /* [  3].c */     {0x5efc4abfaca23e8cLL, 0xa8edb1f2dfbf6478LL}},
    /* [  4].a */ {{0xb6a4239f3b315f84LL, 0xf6ef6d3d288c03c1LL},
    /* [  4].c */     {0xf25bd15439d16af5LL, 0x94c1b1bafa6239f0LL}},
    /* [  5].a */ {{0x2c82901ad1cb0cd1LL, 0x82b631ba6b261781LL},
    /* [  5].c */     {0x89ca67c29c9397d5LL, 0x9c612596145db7e0LL}},
    /* [  6].a */ {{0xdab03f988288676eLL, 0xe49e66c4d2746f01LL},
    /* [  6].c */     {0x8b6ae036713bd578LL, 0xa8093c8eae5c7fc0LL}},
    /* [  7].a */ {{0x602167331d86cf56LL, 0x84fe009a6d09de01LL},
    /* [  7].c */     {0x98a2542fd23d0dbdLL, 0xff3b886cdb1d3f80LL}},
    /* [  8].a */ {{0x61ecb5c24d95b058LL, 0xf04c80a23697bc01LL},
    /* [  8].c */     {0x954db923fdb7933eLL, 0x947cd1edcecb7f00LL}},
    /* [  9].a */ {{0x4a5c31e0654c28aaLL, 0x60474e83bf3f7801LL},
    /* [  9].c */     {0x00be4a36657c98cdLL, 0x204e8c8af7dafe00LL}},
    /* [ 10].a */ {{0xae4f079d54fbece1LL, 0x478331d3c6bef001LL},
    /* [ 10].c */     {0x991965329dccb28dLL, 0x581199ab18c5fc00LL}},
    /* [ 11].a */ {{0x101b8cb830c7cb92LL, 0x7ff1ed50ae7de001LL},
    /* [ 11].c */     {0xe1a8705b63ad5b8cLL, 0xd6c3d268d5cbf800LL}},
    /* [ 12].a */ {{0xf54a27fc056b00e7LL, 0x563f3505e0fbc001LL},
    /* [ 12].c */     {0x2b657bbfd6ed9d63LL, 0x2079e70c3c97f000LL}},
    /* [ 13].a */ {{0xdf8a6fc1a833d201LL, 0xf98d719dd1f78001LL},
    /* [ 13].c */     {0x59b60ee4c52fa49eLL, 0x9fe90682bd2fe000LL}},
    /* [ 14].a */ {{0x5480a5015f101a4eLL, 0xa7e3f183e3ef0001LL},
    /* [ 14].c */     {0xcc099c8803067946LL, 0x4fe86aae8a5fc000LL}},
    /* [ 15].a */ {{0xa498509e76e5d792LL, 0x5f539c28c7de0001LL},
    /* [ 15].c */     {0x06b9abff9f9f33ddLL, 0x30362c0154bf8000LL}},
    /* [ 16].a */ {{0x0798a3d8b10dc72eLL, 0x60121cd58fbc0001LL},
    /* [ 16].c */     {0xe296707121688d5aLL, 0x0260b293a97f0000LL}},
    /* [ 17].a */ {{0x1647d1e78ec02e66LL, 0x5fafcbbb1f780001LL},
    /* [ 17].c */     {0x189ffc4701ff23cbLL, 0x8f8acf6b52fe0000LL}},
    /* [ 18].a */ {{0xa7c982285e72bf8cLL, 0x0c8ddfb63ef00001LL},
    /* [ 18].c */     {0x5141110ab208fb9dLL, 0x61fb47e6a5fc0000LL}},
    /* [ 19].a */ {{0x3eb78ee8fb8c56dbLL, 0xc5d4e06c7de00001LL},
    /* [ 19].c */     {0x3c97caa62540f294LL, 0x8d8d340d4bf80000LL}},
    /* [ 20].a */ {{0x72d03b6f4681f2f9LL, 0xfe8e44d8fbc00001LL},
    /* [ 20].c */     {0x1b25cb9cfe5a0c96LL, 0x3174f91a97f00000LL}},
    /* [ 21].a */ {{0xea85f81e4f502c9bLL, 0xc8ae99b1f7800001LL},
    /* [ 21].c */     {0x0c644570b4a48710LL, 0x3c5436352fe00000LL}},
    /* [ 22].a */ {{0x629c320db08b00c6LL, 0xbfa57363ef000001LL},
    /* [ 22].c */     {0x3d0589c28869472bLL, 0xde517c6a5fc00000LL}},
    /* [ 23].a */ {{0xc5c4b9ce268d074aLL, 0x386be6c7de000001LL},
    /* [ 23].c */     {0xbc95e5ab36477e65LL, 0x534738d4bf800000LL}},
    /* [ 24].a */ {{0xf30bbbbed1596187LL, 0x555bcd8fbc000001LL},
    /* [ 24].c */     {0xddb02ff72a031c01LL, 0x011f71a97f000000LL}},
    /* [ 25].a */ {{0x4a1000fb26c9eedaLL, 0x3cc79b1f78000001LL},
    /* [ 25].c */     {0x2561426086d9acdbLL, 0x6c82e352fe000000LL}},
    /* [ 26].a */ {{0x89fb5307f6bf8ce2LL, 0xc1cf363ef0000001LL},
    /* [ 26].c */     {0x64a788e3c118ed1cLL, 0x8215c6a5fc000000LL}},
    /* [ 27].a */ {{0x830b7b3358a5d67eLL, 0xa49e6c7de0000001LL},
    /* [ 27].c */     {0xe65ea321908627cfLL, 0xa86b8d4bf8000000LL}},
    /* [ 28].a */ {{0xfd8a51da91a69fe1LL, 0xcd3cd8fbc0000001LL},
    /* [ 28].c */     {0x53d27225604d85f9LL, 0xe1d71a97f0000000LL}},
    /* [ 29].a */ {{0x901a48b642b90b55LL, 0xaa79b1f780000001LL},
    /* [ 29].c */     {0xca5ec7a3ed1fe55eLL, 0x07ae352fe0000000LL}},
    /* [ 30].a */ {{0x118cdefdf32144f3LL, 0x94f363ef00000001LL},
    /* [ 30].c */     {0x4daebb2e08533065LL, 0x1f5c6a5fc0000000LL}},
    /* [ 31].a */ {{0x0a88c0a91cff4308LL, 0x29e6c7de00000001LL},
    /* [ 31].c */     {0x9d6f1a00a8f3f76eLL, 0x7eb8d4bf80000000LL}},
    /* [ 32].a */ {{0x433bef4314f16a94LL, 0x53cd8fbc00000001LL},
    /* [ 32].c */     {0x158c62f2b31e496dLL, 0xfd71a97f00000000LL}},
    /* [ 33].a */ {{0xc294b02995ae6738LL, 0xa79b1f7800000001LL},
    /* [ 33].c */     {0x290e84a2eb15fd1fLL, 0xfae352fe00000000LL}},
    /* [ 34].a */ {{0x913575e0da8b16b1LL, 0x4f363ef000000001LL},
    /* [ 34].c */     {0xe3dc1bfbe991a34fLL, 0xf5c6a5fc00000000LL}},
    /* [ 35].a */ {{0x2f61b9f871cf4e62LL, 0x9e6c7de000000001LL},
    /* [ 35].c */     {0xddf540d020b9eadfLL, 0xeb8d4bf800000000LL}},
    /* [ 36].a */ {{0x78d26ccbd68320c5LL, 0x3cd8fbc000000001LL},
    /* [ 36].c */     {0x8ee4950177ce66bfLL, 0xd71a97f000000000LL}},
    /* [ 37].a */ {{0x8b7ebd037898518aLL, 0x79b1f78000000001LL},
    /* [ 37].c */     {0x39e0f787c907117fLL, 0xae352fe000000000LL}},
    /* [ 38].a */ {{0x0b5507b61f78e314LL, 0xf363ef0000000001LL},
    /* [ 38].c */     {0x659d2522f7b732ffLL, 0x5c6a5fc000000000LL}},
    /* [ 39].a */ {{0x4f884628f812c629LL, 0xe6c7de0000000001LL},
    /* [ 39].c */     {0x9e8722938612a5feLL, 0xb8d4bf8000000000LL}},
    /* [ 40].a */ {{0xbe896744d4a98c53LL, 0xcd8fbc0000000001LL},
    /* [ 40].c */     {0xe941a65d66b64bfdLL, 0x71a97f0000000000LL}},
    /* [ 41].a */ {{0xdaf63a553b6318a7LL, 0x9b1f780000000001LL},
    /* [ 41].c */     {0x7b50d19437b097faLL, 0xe352fe0000000000LL}},
    /* [ 42].a */ {{0x2d7a23d8bf06314fLL, 0x363ef00000000001LL},
    /* [ 42].c */     {0x59d7b68e18712ff5LL, 0xc6a5fc0000000000LL}},
    /* [ 43].a */ {{0x392b046a9f0c629eLL, 0x6c7de00000000001LL},
    /* [ 43].c */     {0x4087bab2d5225febLL, 0x8d4bf80000000000LL}},
    /* [ 44].a */ {{0xeb30fbb9c218c53cLL, 0xd8fbc00000000001LL},
    /* [ 44].c */     {0xb470abc03b44bfd7LL, 0x1a97f00000000000LL}},
    /* [ 45].a */ {{0xb9cdc30594318a79LL, 0xb1f7800000000001LL},
    /* [ 45].c */     {0x366630eaba897faeLL, 0x352fe00000000000LL}},
    /* [ 46].a */ {{0x014ab453686314f3LL, 0x63ef000000000001LL},
    /* [ 46].c */     {0xa2dfc77e8512ff5cLL, 0x6a5fc00000000000LL}},
    /* [ 47].a */ {{0x395221c7d0c629e6LL, 0xc7de000000000001LL},
    /* [ 47].c */     {0x1e0d25a14a25feb8LL, 0xd4bf800000000000LL}},
    /* [ 48].a */ {{0x4d972813a18c53cdLL, 0x8fbc000000000001LL},
    /* [ 48].c */     {0x9d50a5d3944bfd71LL, 0xa97f000000000000LL}},
    /* [ 49].a */ {{0x06f9e2374318a79bLL, 0x1f78000000000001LL},
    /* [ 49].c */     {0xbf7ab5eb2897fae3LL, 0x52fe000000000000LL}},
    /* [ 50].a */ {{0xbd220cae86314f36LL, 0x3ef0000000000001LL},
    /* [ 50].c */     {0x925b14e6512ff5c6LL, 0xa5fc000000000000LL}},
    /* [ 51].a */ {{0x36fd3a5d0c629e6cLL, 0x7de0000000000001LL},
    /* [ 51].c */     {0x724cce0ca25feb8dLL, 0x4bf8000000000000LL}},
    /* [ 52].a */ {{0x60def8ba18c53cd8LL, 0xfbc0000000000001LL},
    /* [ 52].c */     {0x1af42d1944bfd71aLL, 0x97f0000000000000LL}},
    /* [ 53].a */ {{0x8d500174318a79b1LL, 0xf780000000000001LL},
    /* [ 53].c */     {0x0f529e32897fae35LL, 0x2fe0000000000000LL}},
    /* [ 54].a */ {{0x48e842e86314f363LL, 0xef00000000000001LL},
    /* [ 54].c */     {0x844e4c6512ff5c6aLL, 0x5fc0000000000000LL}},
    /* [ 55].a */ {{0x4af185d0c629e6c7LL, 0xde00000000000001LL},
    /* [ 55].c */     {0x9f40d8ca25feb8d4LL, 0xbf80000000000000LL}},
    /* [ 56].a */ {{0x7a670ba18c53cd8fLL, 0xbc00000000000001LL},
    /* [ 56].c */     {0x9912b1944bfd71a9LL, 0x7f00000000000000LL}},
    /* [ 57].a */ {{0x86de174318a79b1fLL, 0x7800000000000001LL},
    /* [ 57].c */     {0x9c69632897fae352LL, 0xfe00000000000000LL}},
    /* [ 58].a */ {{0x55fc2e86314f363eLL, 0xf000000000000001LL},
    /* [ 58].c */     {0xe1e2c6512ff5c6a5LL, 0xfc00000000000000LL}},
    /* [ 59].a */ {{0xccf85d0c629e6c7dLL, 0xe000000000000001LL},
    /* [ 59].c */     {0x68058ca25feb8d4bLL, 0xf800000000000000LL}},
    /* [ 60].a */ {{0x1df0ba18c53cd8fbLL, 0xc000000000000001LL},
    /* [ 60].c */     {0x610b1944bfd71a97LL, 0xf000000000000000LL}},
    /* [ 61].a */ {{0x4be174318a79b1f7LL, 0x8000000000000001LL},
    /* [ 61].c */     {0x061632897fae352fLL, 0xe000000000000000LL}},
    /* [ 62].a */ {{0xd7c2e86314f363efLL, 0x0000000000000001LL},
    /* [ 62].c */     {0x1c2c6512ff5c6a5fLL, 0xc000000000000000LL}},
    /* [ 63].a */ {{0xaf85d0c629e6c7deLL, 0x0000000000000001LL},
    /* [ 63].c */     {0x7858ca25feb8d4bfLL, 0x8000000000000000LL}},
    /* [ 64].a */ {{0x5f0ba18c53cd8fbcLL, 0x0000000000000001LL},
    /* [ 64].c */     {0xf0b1944bfd71a97fLL, 0x0000000000000000LL}},
    /* [ 65].a */ {{0xbe174318a79b1f78LL, 0x0000000000000001LL},
    /* [ 65].c */     {0xe1632897fae352feLL, 0x0000000000000000LL}},
    /* [ 66].a */ {{0x7c2e86314f363ef0LL, 0x0000000000000001LL},
    /* [ 66].c */     {0xc2c6512ff5c6a5fcLL, 0x0000000000000000LL}},
    /* [ 67].a */ {{0xf85d0c629e6c7de0LL, 0x0000000000000001LL},
    /* [ 67].c */     {0x858ca25feb8d4bf8LL, 0x0000000000000000LL}},
    /* [ 68].a */ {{0xf0ba18c53cd8fbc0LL, 0x0000000000000001LL},
    /* [ 68].c */     {0x0b1944bfd71a97f0LL, 0x0000000000000000LL}},
    /* [ 69].a */ {{0xe174318a79b1f780LL, 0x0000000000000001LL},
    /* [ 69].c */     {0x1632897fae352fe0LL, 0x0000000000000000LL}},
    /* [ 70].a */ {{0xc2e86314f363ef00LL, 0x0000000000000001LL},
    /* [ 70].c */     {0x2c6512ff5c6a5fc0LL, 0x0000000000000000LL}},
    /* [ 71].a */ {{0x85d0c629e6c7de00LL, 0x0000000000000001LL},
    /* [ 71].c */     {0x58ca25feb8d4bf80LL, 0x0000000000000000LL}},
    /* [ 72].a */ {{0x0ba18c53cd8fbc00LL, 0x0000000000000001LL},
    /* [ 72].c */     {0xb1944bfd71a97f00LL, 0x0000000000000000LL}},
    /* [ 73].a */ {{0x174318a79b1f7800LL, 0x0000000000000001LL},
    /* [ 73].c */     {0x632897fae352fe00LL, 0x0000000000000000LL}},
    /* [ 74].a */ {{0x2e86314f363ef000LL, 0x0000000000000001LL},
    /* [ 74].c */     {0xc6512ff5c6a5fc00LL, 0x0000000000000000LL}},
    /* [ 75].a */ {{0x5d0c629e6c7de000LL, 0x0000000000000001LL},
    /* [ 75].c */     {0x8ca25feb8d4bf800LL, 0x0000000000000000LL}},
    /* [ 76].a */ {{0xba18c53cd8fbc000LL, 0x0000000000000001LL},
    /* [ 76].c */     {0x1944bfd71a97f000LL, 0x0000000000000000LL}},
    /* [ 77].a */ {{0x74318a79b1f78000LL, 0x0000000000000001LL},
    /* [ 77].c */     {0x32897fae352fe000LL, 0x0000000000000000LL}},
    /* [ 78].a */ {{0xe86314f363ef0000LL, 0x0000000000000001LL},
    /* [ 78].c */     {0x6512ff5c6a5fc000LL, 0x0000000000000000LL}},
    /* [ 79].a */ {{0xd0c629e6c7de0000LL, 0x0000000000000001LL},
    /* [ 79].c */     {0xca25feb8d4bf8000LL, 0x0000000000000000LL}},
    /* [ 80].a */ {{0xa18c53cd8fbc0000LL, 0x0000000000000001LL},
    /* [ 80].c */     {0x944bfd71a97f0000LL, 0x0000000000000000LL}},
    /* [ 81].a */ {{0x4318a79b1f780000LL, 0x0000000000000001LL},
    /* [ 81].c */     {0x2897fae352fe0000LL, 0x0000000000000000LL}},
    /* [ 82].a */ {{0x86314f363ef00000LL, 0x0000000000000001LL},
    /* [ 82].c */     {0x512ff5c6a5fc0000LL, 0x0000000000000000LL}},
    /* [ 83].a */ {{0x0c629e6c7de00000LL, 0x0000000000000001LL},
    /* [ 83].c */     {0xa25feb8d4bf80000LL, 0x0000000000000000LL}},
    /* [ 84].a */ {{0x18c53cd8fbc00000LL, 0x0000000000000001LL},
    /* [ 84].c */     {0x44bfd71a97f00000LL, 0x0000000000000000LL}},
    /* [ 85].a */ {{0x318a79b1f7800000LL, 0x0000000000000001LL},
    /* [ 85].c */     {0x897fae352fe00000LL, 0x0000000000000000LL}},
    /* [ 86].a */ {{0x6314f363ef000000LL, 0x0000000000000001LL},
    /* [ 86].c */     {0x12ff5c6a5fc00000LL, 0x0000000000000000LL}},
    /* [ 87].a */ {{0xc629e6c7de000000LL, 0x0000000000000001LL},
    /* [ 87].c */     {0x25feb8d4bf800000LL, 0x0000000000000000LL}},
    /* [ 88].a */ {{0x8c53cd8fbc000000LL, 0x0000000000000001LL},
    /* [ 88].c */     {0x4bfd71a97f000000LL, 0x0000000000000000LL}},
    /* [ 89].a */ {{0x18a79b1f78000000LL, 0x0000000000000001LL},
    /* [ 89].c */     {0x97fae352fe000000LL, 0x0000000000000000LL}},
    /* [ 90].a */ {{0x314f363ef0000000LL, 0x0000000000000001LL},
    /* [ 90].c */     {0x2ff5c6a5fc000000LL, 0x0000000000000000LL}},
    /* [ 91].a */ {{0x629e6c7de0000000LL, 0x0000000000000001LL},
    /* [ 91].c */     {0x5feb8d4bf8000000LL, 0x0000000000000000LL}},
    /* [ 92].a */ {{0xc53cd8fbc0000000LL, 0x0000000000000001LL},
    /* [ 92].c */     {0xbfd71a97f0000000LL, 0x0000000000000000LL}},
    /* [ 93].a */ {{0x8a79b1f780000000LL, 0x0000000000000001LL},
    /* [ 93].c */     {0x7fae352fe0000000LL, 0x0000000000000000LL}},
    /* [ 94].a */ {{0x14f363ef00000000LL, 0x0000000000000001LL},
    /* [ 94].c */     {0xff5c6a5fc0000000LL, 0x0000000000000000LL}},
    /* [ 95].a */ {{0x29e6c7de00000000LL, 0x0000000000000001LL},
    /* [ 95].c */     {0xfeb8d4bf80000000LL, 0x0000000000000000LL}},
    /* [ 96].a */ {{0x53cd8fbc00000000LL, 0x0000000000000001LL},
    /* [ 96].c */     {0xfd71a97f00000000LL, 0x0000000000000000LL}},
    /* [ 97].a */ {{0xa79b1f7800000000LL, 0x0000000000000001LL},
    /* [ 97].c */     {0xfae352fe00000000LL, 0x0000000000000000LL}},
    /* [ 98].a */ {{0x4f363ef000000000LL, 0x0000000000000001LL},
    /* [ 98].c */     {0xf5c6a5fc00000000LL, 0x0000000000000000LL}},
    /* [ 99].a */ {{0x9e6c7de000000000LL, 0x0000000000000001LL},
    /* [ 99].c */     {0xeb8d4bf800000000LL, 0x0000000000000000LL}},
    /* [100].a */ {{0x3cd8fbc000000000LL, 0x0000000000000001LL},
    /* [100].c */     {0xd71a97f000000000LL, 0x0000000000000000LL}},
    /* [101].a */ {{0x79b1f78000000000LL, 0x0000000000000001LL},
    /* [101].c */     {0xae352fe000000000LL, 0x0000000000000000LL}},
    /* [102].a */ {{0xf363ef0000000000LL, 0x0000000000000001LL},
    /* [102].c */     {0x5c6a5fc000000000LL, 0x0000000000000000LL}},
    /* [103].a */ {{0xe6c7de0000000000LL, 0x0000000000000001LL},
    /* [103].c */     {0xb8d4bf8000000000LL, 0x0000000000000000LL}},
    /* [104].a */ {{0xcd8fbc0000000000LL, 0x0000000000000001LL},
    /* [104].c */     {0x71a97f0000000000LL, 0x0000000000000000LL}},
    /* [105].a */ {{0x9b1f780000000000LL, 0x0000000000000001LL},
    /* [105].c */     {0xe352fe0000000000LL, 0x0000000000000000LL}},
    /* [106].a */ {{0x363ef00000000000LL, 0x0000000000000001LL},
    /* [106].c */     {0xc6a5fc0000000000LL, 0x0000000000000000LL}},
    /* [107].a */ {{0x6c7de00000000000LL, 0x0000000000000001LL},
    /* [107].c */     {0x8d4bf80000000000LL, 0x0000000000000000LL}},
    /* [108].a */ {{0xd8fbc00000000000LL, 0x0000000000000001LL},
    /* [108].c */     {0x1a97f00000000000LL, 0x0000000000000000LL}},
    /* [109].a */ {{0xb1f7800000000000LL, 0x0000000000000001LL},
    /* [109].c */     {0x352fe00000000000LL, 0x0000000000000000LL}},
    /* [110].a */ {{0x63ef000000000000LL, 0x0000000000000001LL},
    /* [110].c */     {0x6a5fc00000000000LL, 0x0000000000000000LL}},
    /* [111].a */ {{0xc7de000000000000LL, 0x0000000000000001LL},
    /* [111].c */     {0xd4bf800000000000LL, 0x0000000000000000LL}},
    /* [112].a */ {{0x8fbc000000000000LL, 0x0000000000000001LL},
    /* [112].c */     {0xa97f000000000000LL, 0x0000000000000000LL}},
    /* [113].a */ {{0x1f78000000000000LL, 0x0000000000000001LL},
    /* [113].c */     {0x52fe000000000000LL, 0x0000000000000000LL}},
    /* [114].a */ {{0x3ef0000000000000LL, 0x0000000000000001LL},
    /* [114].c */     {0xa5fc000000000000LL, 0x0000000000000000LL}},
    /* [115].a */ {{0x7de0000000000000LL, 0x0000000000000001LL},
    /* [115].c */     {0x4bf8000000000000LL, 0x0000000000000000LL}},
    /* [116].a */ {{0xfbc0000000000000LL, 0x0000000000000001LL},
    /* [116].c */     {0x97f0000000000000LL, 0x0000000000000000LL}},
    /* [117].a */ {{0xf780000000000000LL, 0x0000000000000001LL},
    /* [117].c */     {0x2fe0000000000000LL, 0x0000000000000000LL}},
    /* [118].a */ {{0xef00000000000000LL, 0x0000000000000001LL},
    /* [118].c */     {0x5fc0000000000000LL, 0x0000000000000000LL}},
    /* [119].a */ {{0xde00000000000000LL, 0x0000000000000001LL},
    /* [119].c */     {0xbf80000000000000LL, 0x0000000000000000LL}},
    /* [120].a */ {{0xbc00000000000000LL, 0x0000000000000001LL},
    /* [120].c */     {0x7f00000000000000LL, 0x0000000000000000LL}},
    /* [121].a */ {{0x7800000000000000LL, 0x0000000000000001LL},
    /* [121].c */     {0xfe00000000000000LL, 0x0000000000000000LL}},
    /* [122].a */ {{0xf000000000000000LL, 0x0000000000000001LL},
    /* [122].c */     {0xfc00000000000000LL, 0x0000000000000000LL}},
    /* [123].a */ {{0xe000000000000000LL, 0x0000000000000001LL},
    /* [123].c */     {0xf800000000000000LL, 0x0000000000000000LL}},
    /* [124].a */ {{0xc000000000000000LL, 0x0000000000000001LL},
    /* [124].c */     {0xf000000000000000LL, 0x0000000000000000LL}},
    /* [125].a */ {{0x8000000000000000LL, 0x0000000000000001LL},
    /* [125].c */     {0xe000000000000000LL, 0x0000000000000000LL}},
    /* [126].a */ {{0x0000000000000000LL, 0x0000000000000001LL},
    /* [126].c */     {0xc000000000000000LL, 0x0000000000000000LL}},
    /* [127].a */ {{0x0000000000000000LL, 0x0000000000000001LL},
    /* [127].c */     {0x8000000000000000LL, 0x0000000000000000LL}}
};


/* hex_to_u16 - convert a hexadecimal string to a u16
 */
u16 hex_to_u16(const char *s)
{
    u16         result;
    size_t      len;
    char        sub[16 + 1];
    u8          temp;

    result.hi8 = 0;
    result.lo8 = 0;
    len = strlen(s);
    if (len <= 16)
    {
        sscanf(s, "%llx", &temp);
        result.lo8 = temp;
    }
    else
    {
        strncpy(sub, s + len - 16, 16);
        sscanf(sub, "%llx", &temp);
        result.lo8 = temp;

        if (len <= 32)
        {
            strncpy(sub, s, len - 16);
            sub[len - 16] = '\0';
            sscanf(sub, "%llx", &temp);
            result.hi8 = temp;
        }
        else
        {
            /* this actually an error to have more that 32 hex digits.
             * but only look at low-order 32 digits.
             */
            strncpy(sub, s + len - 32, 16);
            sscanf(sub, "%llx", &temp);
            result.hi8 = temp;
        }
    }
    return (result);
}


/* dec_to_u16 - convert a (unsigned) decimal string to a u16
 */
u16 dec_to_u16(const char *s)
{
    u16         result;
    u16         temp;
    const char  *p;

    result.hi8 = 0;
    result.lo8 = 0;
    for (p = s; *p >= '0' && *p <= '9'; p++)
    {
        /* another digit, multiply result so far by 10
         * the multiplication is done by adding the left shift by 3 (times 8)
         * to the left shift by 1 (times 2).
         */
        temp = result;
        result.hi8 <<= 3;
        result.hi8 += (result.lo8 & 0xE000000000000000ULL) >> 61;
        result.lo8 <<= 3;
        temp.hi8 <<= 1;
        temp.hi8 += (temp.lo8 & 0x8000000000000000ULL) >> 63;
        temp.lo8 <<= 1;
        result = add16(result, temp);  /* add the times 8 to the times 2 */

        /* add in new digit */
        temp.hi8 = 0;
        temp.lo8 = *p - '0';
        result = add16(result, temp);
    }
    return (result);
}


/* u16_to_hex - convert a u16 to a hexadecimal string and write that string
 *              into the provided buffer which must be at least 33 bytes long.
 */
char *u16_to_hex(u16 k, char *buf)
{
    char        *p;

    if (k.hi8 == 0)
        sprintf(buf, "%llx", k.lo8);
    else
    {
        sprintf(buf, "%llx", k.hi8);
        p = buf + strlen(buf);
        sprintf(p, "%016llx", k.lo8);
    }
    return (buf);
}

static u8 hi2loQuot[10] = {
    0ULL,
    1844674407370955161ULL,
    3689348814741910323ULL,
    5534023222112865484ULL,
    7378697629483820646ULL,
    9223372036854775808ULL,
    11068046444225730969ULL,
    12912720851596686131ULL,
    14757395258967641292ULL,
    16602069666338596454ULL
};

static u8 hi2loMod[10] = {
    0,
    6,
    2,
    8,
    4,
    0,
    6,
    2,
    8,
    4
};

/* u16_to_dec - convert a u16 to a decimal string and write that string
 *              into the provided buffer
 * Args:
 *    k -   the u16 number to be converted to a decimal string.
 *    buf - pointer to a character buffer of size U16_ASCII_BUF_SIZE.
 * Returns:
 *    pointer the "buf" arg which contains the decimal string.
 */
char *u16_to_dec(u16 k, char *buf)
{
    u8          hi8 = k.hi8;
    u8          lo8 = k.lo8;
    int         himod;
    int         lomod;
    char        temp[U16_ASCII_BUF_SIZE];
    char        *digit = temp;
    char        *tail;

    while (hi8)
    {
        himod = (int)(hi8 % 10);
        hi8 /= 10;
        lomod = (int)(lo8 % 10);
        lo8 /= 10;

        lo8 += hi2loQuot[himod] ;
        lomod += (int)hi2loMod[himod];

        if (lomod >= 10)       /* if adding to 2 mods caused a "carry" */
        {
            lomod -= 10;
            lo8 += 1;
        }
        *digit++ = '0' + lomod;
    }
    sprintf(buf, "%llu", lo8);
    /* concatenate low order digits computed before hi8 was reduced to 0 */
    tail = buf + strlen(buf);
    while (digit > temp)
        *tail++ = *--digit;
    *tail = '\0';
    return (buf);
}


/* mult16 - multiply two 16-byte numbers
 */
u16 mult16(u16 a, u16 b)
{
    u16 prod;
    u8  ahi4, alow4, bhi4, blow4, temp;
    u8  reshibit, hibit0, hibit1;

    prod.hi8 = 0;

    ahi4 = a.lo8 >> 32;        /* get hi 4 bytes of the low 8 bytes */
    alow4 = (a.lo8 & 0xFFFFFFFFLL);  /* get low 4 bytes of the low 8 bytes */
    bhi4 = b.lo8 >> 32;        /* get hi 4 bytes of the low 8 bytes */
    blow4 = (b.lo8 & 0xFFFFFFFFLL);  /* get low 4 bytes of the low 8 bytes */

    /* assign 8-byte product of the lower 4 bytes of "a" and the lower 4 bytes
     * of "b" to the lower 8 bytes of the result product.
     */
    prod.lo8 = alow4 * blow4;
 
    temp = ahi4 * blow4; /* mult high 4 bytes of "a" by low 4 bytes of "b" */
    prod.hi8 += temp >> 32; /* add high 4 bytes to high 8 result bytes*/
    temp <<= 32;     /* get lower half ready to add to lower 8 result bytes */
    hibit0 = (temp & 0x8000000000000000LL);
    hibit1 = (prod.lo8 & 0x8000000000000000LL);
    prod.lo8 += temp;
    reshibit = (prod.lo8 & 0x8000000000000000LL);
    if ((hibit0 & hibit1) || ((hibit0 ^ hibit1) && reshibit == 0LL))
        prod.hi8++;  /* add carry bit */
 
    temp = alow4 * bhi4; /* mult low 4 bytes of "a" by high 4 bytes of "b" */
    prod.hi8 += temp >> 32; /* add high 4 bytes to high 8 result bytes*/
    temp <<= 32;     /* get lower half ready to add to lower 8 result bytes */
    hibit0 = (temp & 0x8000000000000000LL);
    hibit1 = (prod.lo8 & 0x8000000000000000LL);
    prod.lo8 += temp;
    reshibit = (prod.lo8 & 0x8000000000000000LL);
    if ((hibit0 & hibit1) || ((hibit0 ^ hibit1) && reshibit == 0LL))
        prod.hi8++;  /* add carry bit */

    prod.hi8 += ahi4 * bhi4;
    prod.hi8 += a.lo8 * b.hi8;
    prod.hi8 += a.hi8 * b.lo8;
    return (prod);    
}


/* add16 - add two 16-byte numbers
 */
u16 add16(u16 a, u16 b)
{
    u16 sum;
    u8  reshibit, hibit0, hibit1;

    sum.hi8 = a.hi8 + b.hi8;

    hibit0 = (a.lo8 & 0x8000000000000000LL);
    hibit1 = (b.lo8 & 0x8000000000000000LL);
    sum.lo8 = a.lo8 + b.lo8;
    reshibit = (sum.lo8 & 0x8000000000000000LL);
    if ((hibit0 & hibit1) || ((hibit0 ^ hibit1) && reshibit == 0LL))
        sum.hi8++;  /* add carry bit */
    return (sum);    
}


/* skip_ahead_rand - generate the random number that is "advance" steps
 *              from an initial random number of 0.  This is done by
 *              starting with 0, and then advancing the by the
 *              appropriate powers of 2 of the linear congruential
 *              generator.
 */
u16 skip_ahead_rand(u16 advance)
{
    int         i;
    u16         new;
    u8          bit_map;

    new.hi8 = 0;
    new.lo8 = 0;
    bit_map = advance.lo8;
    for (i = 0; bit_map && i < 64; i++)
    {
        if (bit_map & ((u8)1 << i))
        {
            /* advance random number by f**(2**i) (x)
             */
            new = add16(mult16(new, Gen[i].a), Gen[i].c);
            bit_map &= ~((u8)1 << i);
        }
    }
    bit_map = advance.hi8;
    for (i = 0; bit_map && i < 64; i++)
    {
        if (bit_map & ((u8)1 << i))
        {
            /* advance random number by f**(2**(i + 64)) (x)
             */
            new = add16(mult16(new, Gen[i + 64].a), Gen[i + 64].c);
            bit_map &= ~((u8)1 << i);
        }
    }
    return (new);
}


/* next_rand - the sequential 128-bit random number generator.
 */
u16 next_rand(u16 rand)
{
    /* advance the random number forward once using the linear congruential
     * generator, and then return the new random number
     */
    rand = add16(mult16(rand, Gen[0].a), Gen[0].c);
    return (rand);
}