Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Port scan randomization

By: robert_david_graham on Oct 27th, 2012  |  syntax: C for Macs  |  size: 22.76 KB  |  views: 391  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2.  
  3.  ABSTRACT
  4.  
  5.  I want to randomize TCP/IP port scans (like those with nmap) for large-scale
  6.  scans of the entire Internet. I want to use a random number generator, rather
  7.  than keeping track in memory, becuase the memory needed to scan the entire
  8.  Internet would be too large.
  9.  
  10.  Using the "linear congruential generator" behind the typical 'rand()' function
  11.  seems the obvious choice. Indeed, it's what many worms used (like Slammer and
  12.  Witty) to scan the entire Internet. However, a typical 'rand()' function only
  13.  works when the ranges are a power of 2. When using for odd sized ranges, I
  14.  need different internal constants.
  15.  
  16.  That's what this program is for: given a range, choose the constants 'a' and
  17.  'c' to randomize the range. I'll practice with this code manually to figure
  18.  things out, then copy this code into a port scanner to make the process
  19.  automated.
  20.  
  21.  
  22.  BUILD
  23.  
  24.  It's just standard C, so all you need do is compile it on your favorite system.
  25.  Though on GNU you may need to link to the math library.
  26.  
  27.  Mac:     gcc lcgtest.c -O3 -o lcgtest
  28.  Ubuntu:  gcc lcgtest.c -O3 -o lggtest -lm
  29.  Windows: I create a VisualStudio project and just compile it
  30.  
  31.  
  32.  USAGE
  33.  
  34.  lcgtest <range>
  35.  
  36.  where <range> is a number like 100 or 0xffff11223344. Since the idea is
  37.  to scan the entire Interent and all ports, the max size for the range
  38.  can be up to a 48 bit number.
  39.  
  40.  
  41.  MATH THEORY
  42.  
  43.  One way of randomizing a range is the "full cycle" technique:
  44.  http://en.wikipedia.org/wiki/Full_cycle
  45.  Given a range 'range' (like 100), we enumerate the new indexes with:
  46.  
  47.     next_index = (index + c) % range;
  48.  
  49.  1. The value of 'c' is relatively prime with 'range', meaning these two
  50.     numbers have no prime factors in common. Thus, for a 'range' of 100
  51.     addresses, you could choose '17' or '977', since they have no prime
  52.     factors in common with '100'.
  53.  
  54.  This full cycle technique isn't random enough, which is why we look at
  55.  a function like 'rand()'. This function is known as a Linear Congruential
  56.  Generator, and is described here:
  57.  http://en.wikipedia.org/wiki/Linear_congruential_generator
  58.  
  59.  This function looks like:
  60.  
  61.      next_index = (index * a + c) % range;
  62.  
  63.  The constants have the rules:
  64.  
  65.   1. The value 'c' is relatively prime with 'range', as before.
  66.   2. The value (a - 1) is divisible by all prime factors of 'range'
  67.   3. The value (a - 1) is a multiple of 4 if 'range' is a multiple of 4
  68.  
  69.  In other words, it's the same as before, but we add a multiplication along
  70.  with the addition.
  71.  
  72.  
  73.  PRIME FACTORS
  74.  
  75.  So, to find the constants 'a' and 'c' for a range, we need to do prime
  76.  factorization. How do we do that efficiently? Curiously, I couldn't find
  77.  answers to that. Everyone is concerned with the theoretical problem of
  78.  factoring 1000 bit numbers, but all I want to do is factor a 48 bit number.
  79.  
  80.  It turns out that the best answer for small numbers is obvious answer: just
  81.  take a list of primes and try them all one-by-one until you've found all the
  82.  factors.
  83.  
  84.  How to get the list of primes starting from 2, 3, 5, 7, 11, 17, 19, ...? The
  85.  answer is to use the well-known "Sieve of Eratosthenes". This turns out to
  86.  be the most expensive part of the code, taking 2 seconds of compute power on
  87.  an Atom 1.6 Ghz x86 CPU and 2-megabytes of RAM. I could precompute them, but
  88.  then I'd have to ship around a 5-megabyte file of integers along with the
  89.  program.
  90.  
  91.  An important note is that I don't have to factor a 48 bit number, but only
  92.  a 24 bit number. A 48 bit number can have at most one prime factor larger
  93.  than 24 bits, and once I've found all the other factors smaller than 24 bits,
  94.  this larger factor will be the only one left. Thus, I use the sieve to go
  95.  through 24 bits or 16-million combinations, which can be done in 2-megabytes
  96.  of RAM. I think a big reason the Atom is slow is that this can't fit in the
  97.  cache.
  98.  
  99.  
  100.  SO WHAT THIS PROGRAM DOES
  101.  
  102.  Given a 'range', this program does:
  103.  1. sieves it to find all prime numbers smaller than the sqrt(range).
  104.  2. finds all the prime factors of 'range'
  105.  3. calculates a value of 'a' and 'c' that meat the requirements for 'rand()'
  106.  4. for small ranges, verifies that 1-to-1 really works
  107.  5. prints the first few random numbers output, so that we can see how random
  108.     they are visually.
  109.  
  110.  NOTES
  111.  
  112.  If I google harder, I might come up with a better way of factoring large
  113.  numbers. For example, instead of the basic Sieve of Eratosthenes, I could
  114.  instead use DJB's "primegen". On a Raspberry Pi (400 MHz ARM), primegen
  115.  is about 10 times faster factoring small numbers, and uses less memory.
  116.  */
  117. #include <ctype.h>
  118. #include <string.h>
  119. #include <stdio.h>
  120. #include <stdlib.h>
  121. #include <stdint.h>
  122. #include <time.h>
  123. #include <math.h>
  124.  
  125.  
  126. /* A 64-bit number cannot have more than 16 prime factors */
  127. typedef unsigned PRIMEFACTORS[16];
  128.  
  129. #if defined(_MSC_VER)
  130. #define strtoll _strtoi64
  131. #endif
  132.  
  133. /****************************************************************************
  134.  * A object for creating a list of prime numbers, then using those primes
  135.  * to find the prime factors of a number.
  136.  *
  137.  * To find the first primes up to 'n', we use the Sieve of Eratosthenes
  138.  * algorithm. It's the slowest part of the whole thing.
  139.  *
  140.  * To find the prime factors of a number, we just brute force check every
  141.  * prime number in the list.
  142.  ****************************************************************************/
  143. struct PrimeList
  144. {
  145.     unsigned char *list;
  146.     unsigned count;
  147.     unsigned max;
  148. };
  149.  
  150.  
  151. /****************************************************************************
  152.  * When running the Sieve of Eratosthenes, mark a number as not being prime.
  153.  * Numbers are represented as a bit mask, so clear the bit representing
  154.  * that number.
  155.  *
  156.  * @param list
  157.  *        A bit mask of bits representing all numbers from 0 to 'n'.
  158.  * @param num
  159.  *        The number we are checking to see if it's prime or not.
  160.  ****************************************************************************/
  161. static __inline void
  162. sieve_clear(unsigned char *list, unsigned num)
  163. {
  164.     unsigned bit = num & 0x7;
  165.     unsigned index = num / 8;
  166.    
  167.     list[index] &= ~(1 << bit);
  168. }
  169.  
  170.  
  171. /****************************************************************************
  172.  * Test a number to see if it's in our list of primes. Numbers are
  173.  * represented with a bit mask, so if it's prime, the bit is set, and if
  174.  * it's not prime, the corresponding bit is clear. Finding the next prime
  175.  * in the list means skip the bits that are clear.
  176.  *
  177.  * @param list
  178.  *        A bit mask of bits representing all numbers from 0 to 'n'.
  179.  * @param num
  180.  *        The number we are checking to see if it's prime or not.
  181.  ****************************************************************************/
  182. static __inline unsigned
  183. sieve_is_clear(const unsigned char *list, unsigned num)
  184. {
  185.     unsigned bit = num & 0x7;
  186.     unsigned index = num / 8;
  187.    
  188.     return (list[index] & (1 << bit)) == 0;
  189. }
  190.  
  191.  
  192. /****************************************************************************
  193.  * Create an object for dealing with a list of first primes.
  194.  *
  195.  * We do this creation as a separate step because we want to also benchmark
  196.  * the actual seiving step. That's because seiving up to 24 bit numbers can
  197.  * take several seconds on low-power processors.
  198.  *
  199.  * @param largest_number
  200.  *        Find all primes up to this number.
  201.  ****************************************************************************/
  202. struct PrimeList *
  203. primes_create(unsigned largest_number)
  204. {
  205.     struct PrimeList *primes;
  206.    
  207.     /* allocate the main object memory */
  208.     primes = (struct PrimeList *)malloc(sizeof(*primes));
  209.     memset(primes, 0, sizeof(*primes));
  210.    
  211.     /* Set the largest number we are going to look for */
  212.     primes->max = largest_number;
  213.    
  214.     /* Allocate the sieve bit-mask. This uses one bit for each candidate
  215.      * number. In other words, if we are looking for all primes up to
  216.      * 100, then we'll need 12.5 bytes to store one bit for each number */
  217.     primes->count = (largest_number+7)/8;
  218.     primes->list = (unsigned char *)malloc(primes->count);
  219.    
  220.     /* Set to all 1. As we sieve the primes, we'll clear the bits for
  221.      * numbers that aren't prime. */
  222.     memset(primes->list, 0xFF, primes->count);
  223.    
  224.     /* 0 and 1 are not prime */
  225.     sieve_clear(primes->list, 0);
  226.     sieve_clear(primes->list, 1);
  227.    
  228.     /* the padding bits at the end aren't prime (well, if they are, we
  229.      * don't care) */
  230.     while (largest_number+1 < primes->count*8) {
  231.         sieve_clear(primes->list, largest_number+1);
  232.         largest_number++;
  233.     }
  234.    
  235.     return primes;
  236. }
  237.  
  238. /****************************************************************************
  239.  * Clean up the object created by 'primes_create()'.
  240.  ****************************************************************************/
  241. void
  242. primes_destroy(struct PrimeList *primes)
  243. {
  244.     if (primes == NULL)
  245.         return;
  246.     if (primes->list)
  247.         free(primes->list);
  248.     free(primes);
  249. }
  250.  
  251.  
  252. /****************************************************************************
  253.  * Run the "Sieve of Eratosthenes" to find all prime numbers up to 'n'. The
  254.  * value of 'n' was set when we initialized the object.
  255.  *
  256.  * The sieving process works by doing:
  257.  *  - remove all even numbers from the list of possible primes (except for 2)
  258.  *  - remove all multiples of 3 (except for 3 itself)
  259.  *  - remove all multiples of 5 (except for 5 itself)
  260.  *  - remove all multiples of 7 (except for 7 itself)
  261.  *  - ... and so on for all prime numbers
  262.  *
  263.  ****************************************************************************/
  264. void
  265. primes_run_sieve(struct PrimeList *primes)
  266. {
  267.     unsigned char *list = primes->list;
  268.     unsigned max = primes->max;
  269.     unsigned prime = 2;
  270.    
  271.     /* for all primes ... */
  272.     for (prime = 2; prime < max; ) {
  273.         unsigned j;
  274.        
  275.         /* clear all bits representing multiples of this prime number*/
  276.         for (j = prime*2;  j < max;  j += prime)
  277.             sieve_clear(list, j);
  278.        
  279.         /* goto next prime number */
  280.         prime++;
  281.         while (prime < max && sieve_is_clear(list, prime))
  282.             prime++;
  283.     }
  284.    
  285. }
  286.  
  287.  
  288. /****************************************************************************
  289.  * For enumerating the primes in the list of primes after we've done
  290.  * a 'run'.
  291.  *
  292.  * @param primes
  293.  *        A list of prime numbers (that we probably created with the Sieve)
  294.  * @param prime
  295.  *        A prime number, like 2, 5, 17, 1699999
  296.  * @return
  297.  *        the next prime in the list. Given a prime number like '2', this
  298.  *        function returns '3'.
  299.  ****************************************************************************/
  300. unsigned
  301. primes_next(const struct PrimeList *primes, unsigned prime)
  302. {
  303.     const unsigned char *list = primes->list;
  304.     unsigned max = primes->max;
  305.    
  306.     /* skip cleared bits representing non-primes until we get to the first
  307.      * set bit representing a prime number */
  308.     prime++;
  309.     while (prime < max && sieve_is_clear(list, prime))
  310.         prime++;
  311.     return prime;
  312. }
  313.  
  314. /****************************************************************************
  315.  * Count the number of primes we've found. This just brute-force counts all
  316.  * the bits set in the bit-mask.
  317.  ****************************************************************************/
  318. unsigned
  319. primes_count(const struct PrimeList *primes)
  320. {
  321.     const unsigned char *list = primes->list;
  322.     unsigned max = primes->count;
  323.     unsigned i;
  324.     unsigned count = 0;
  325.    
  326.     for (i=0; i<max; i++) {
  327.         unsigned char c = list[i];
  328.         count += (c&1); c >>= 1;
  329.         count += (c&1); c >>= 1;
  330.         count += (c&1); c >>= 1;
  331.         count += (c&1); c >>= 1;
  332.         count += (c&1); c >>= 1;
  333.         count += (c&1); c >>= 1;
  334.         count += (c&1); c >>= 1;
  335.         count += (c&1);
  336.     }
  337.    
  338.     return count;
  339. }
  340.  
  341.  
  342. /****************************************************************************
  343.  * Do the prime factorization of a number. This first runs the "Sieve of
  344.  * Eratosthenes" to find all the small primes, then it does a brute-force
  345.  * search of all the prime numbers in order to find the list of factors
  346.  * of the number.
  347.  *
  348.  * @param m
  349.  *      The number we are factoring.
  350.  * @param factors
  351.  *      The output of this function listing the prime factors of 'm'.
  352.  *      If 'm' is prime, then 'm' will be the only member of this list.
  353.  * @param elapsed
  354.  *      Since the 'sieve' takes a long time to run, we can benchmark it,
  355.  *      outputing the number of seconds taken. This is optional, if NULL,
  356.  *      then benchmarking isn't done.
  357.  ****************************************************************************/
  358. void
  359. primes_factor(uint64_t m, PRIMEFACTORS factors, double *elapsed)
  360. {
  361.     uint64_t root;
  362.     struct PrimeList *primes;
  363.     clock_t start, stop; /* for benchmark */
  364.    
  365.     /*
  366.      * Calculate the square-root. That's because no prime factor can be
  367.      * larger than the square-root of a number, except for the largest
  368.      * one. In other words, all prime factors of '14' are less than the
  369.      * square root (3.742), except for the largest prime factor (7).
  370.      */
  371.     root = (unsigned)sqrt(m+1.0);
  372.    
  373.     /*
  374.      * Create a Seive of Erastothenes that finds all primes up to the
  375.      * root, then tries them all to see if they are prime factors.
  376.      */
  377.     primes = primes_create((unsigned)root);
  378.    
  379.     /*
  380.      * Run the sieve to find primes. This will take 0.2 seconds on a
  381.      * Nehalem+ Intel x86 CPU for the full 48 bit range
  382.      */
  383.     start = clock();
  384.     primes_run_sieve(primes);
  385.     stop = clock();
  386.     if (elapsed)
  387.         *elapsed = (double)(stop - start)/(double)CLOCKS_PER_SEC;
  388.    
  389.     /*
  390.      * Now we factor our original number.
  391.      */
  392.     {
  393.         unsigned temp = (unsigned)m;
  394.         unsigned prime;
  395.         unsigned count = 0;
  396.        
  397.         memset(factors, 0, sizeof(factors));
  398.        
  399.         /* for all primes ... */
  400.         for (prime = 2;
  401.              prime < root;
  402.              prime = primes_next(primes, prime)) {
  403.            
  404.             /* see if we have a prime factor */
  405.             if ((temp % prime) != 0)
  406.                 continue; /* not a prime factor */
  407.            
  408.             /* add this factor to our list */
  409.             factors[count++] = prime;
  410.            
  411.             /* remove this factor from our 'temp' variable */
  412.             while ((temp % prime) == 0)
  413.                 temp /= prime;
  414.         }
  415.        
  416.         /* the residual may also be a factor, in which case, add it
  417.          * to our list as well */
  418.         if (temp != 1)
  419.             factors[count++] = temp;
  420.     }
  421.    
  422.     /* free the memory we allocated for sieving the primes */
  423.     primes_destroy(primes);
  424. }
  425.  
  426.  
  427. /****************************************************************************
  428.  * Do a pseudo-random 1-to-1 translation of a number within a range to
  429.  * another number in that range.
  430.  *
  431.  * The constants 'a' and 'c' must be chosen to match the LCG algorithm
  432.  * to fit 'm' (range).
  433.  *
  434.  * This the same as the function 'rand()', except all the constants and
  435.  * seeds are specified as parameters.
  436.  *
  437.  * @param index
  438.  *      The index within the range that we are randomizing.
  439.  * @param a
  440.  *      The 'multiplier' of the LCG algorithm.
  441.  * @param c
  442.  *      The 'increment' of the LCG algorithm.
  443.  * @param range
  444.  *      The 'modulus' of the LCG algorithm.
  445.  ****************************************************************************/
  446. uint64_t
  447. lcg(uint64_t index, uint64_t a, uint64_t c, uint64_t range)
  448. {
  449.     return (index * a + c) % range;
  450. }
  451.  
  452.  
  453. /****************************************************************************
  454.  * Verify the LCG algorithm. You shouldn't do this for large ranges,
  455.  * because we'll run out of memory. Therefore, this algorithm allocates
  456.  * a buffer only up to a smaller range. We still have to traverse the
  457.  * entire range of numbers, but we only need store values for a smaller
  458.  * range. If 10% of the range checks out, then there's a good chance
  459.  * it applies to the other 90% as well.
  460.  *
  461.  * This works by counting the results of rand(), which should be produced
  462.  * exactly once.
  463.  ****************************************************************************/
  464. unsigned
  465. lcg_verify(uint64_t a, uint64_t c, uint64_t range, uint64_t max)
  466. {
  467.     unsigned char *list;
  468.     uint64_t i;
  469.     unsigned is_success = 1;
  470.    
  471.     /* Allocate a list of 1-byte counters */
  472.     list = (unsigned char *)malloc((range<max)?range:max);
  473.     memset(list, 0, (range<max)?range:max);
  474.    
  475.     /* For all numbers in the range, verify increment the counter for the
  476.      * the output. */
  477.     for (i=0; i<range; i++) {
  478.         uint64_t x = lcg(i, a, c, range);
  479.         if (x < max)
  480.             list[x]++;
  481.     }
  482.    
  483.     /* Now check the output to make sure that every counter is set exactly
  484.      * to the value of '1'. */
  485.     for (i=0; i<max && i<range; i++) {
  486.         if (list[i] != 1)
  487.             is_success = 0;
  488.     }
  489.    
  490.     free(list);
  491.    
  492.     return is_success;
  493. }
  494.  
  495.  
  496. /****************************************************************************
  497.  * Count the number of digits in a number so that we can pretty-print a
  498.  * bunch of numbers in nice columns.
  499.  ****************************************************************************/
  500. unsigned
  501. count_digits(uint64_t num)
  502. {
  503.     unsigned result = 0;
  504.    
  505.     while (num) {
  506.         result++;
  507.         num /= 10;
  508.     }
  509.    
  510.     return result;
  511. }
  512.  
  513. /****************************************************************************
  514.  * Tell whether the number has any prime factors in common with the list
  515.  * of factors. In other words, if it's not coprime with the other number.
  516.  * @param c
  517.  *      The number we want to see has common factors with the other number.
  518.  * @param factors
  519.  *      The factors from the other number
  520.  * @return
  521.  *      !is_coprime(c, factors)
  522.  ****************************************************************************/
  523. unsigned
  524. has_factors_in_common(uint64_t c, PRIMEFACTORS factors)
  525. {
  526.     unsigned i;
  527.    
  528.     for (i=0; factors[i]; i++) {
  529.         if ((c % factors[i]) == 0)
  530.             return factors[i]; /* found a common factor */
  531.     }
  532.     return 0; /* no factors in common */
  533. }
  534.  
  535.  
  536. /****************************************************************************
  537.  ****************************************************************************/
  538. int main(int argc, char *argv[])
  539. {
  540.     uint64_t m=2;   /* LCG modulus aka. the IP address range size */
  541.     uint64_t a;     /* LCG multiplier */
  542.     uint64_t c = 0; /* LCG increment */
  543.     double elapsed = 0.0; /* Benchmark of 'sieve' algorithm */
  544.     uint64_t i;
  545.     PRIMEFACTORS factors; /* List of prime factors of 'm' */
  546.     uint64_t a_offset = 1;
  547.    
  548.     memset(factors, 0, sizeof(factors));    
  549.    
  550.     /* usage info if nothing specified */
  551. usage:
  552.     if (argc < 2) {
  553.         printf("usage:\n lcgtest <range> [-c num] [-a num]\n");
  554.         printf("Finds constants for randomizing range using a typical "
  555.                "linear congruent generator\n");
  556.         printf("<range> may be up to 48 bits in size\n");
  557.         printf("[-c num] suggests a 'c' constant\n");
  558.         printf("[-a num] suggests a 'a' scaling factor\n");
  559.         printf("Numbers may be decimal or hex\n");
  560.         return 0;
  561.     }
  562.        
  563.     /*
  564.      * Get the input
  565.      * Read in optional additional parameters, such as a starting value for
  566.      * 'c' or a scaling factor for 'a'.
  567.      */
  568.     for (i=1; i<(unsigned)argc; i++) {
  569.         if (isdigit(argv[i][0]&0xFF))
  570.             m = strtoll(argv[1], 0, 0);
  571.         else if (argv[i][0] == '-') {
  572.             switch (tolower(argv[i][1]&0xFF)) {
  573.                case 'a':
  574.                     if (argv[i][2] == '\0')
  575.                         a_offset = strtoll(argv[++i], 0, 0);
  576.                     else
  577.                         a_offset = strtoll(argv[i]+2, 0, 0);
  578.                     break;
  579.                 case 'c':
  580.                     if (argv[i][2] == '\0')
  581.                         c = strtoll(argv[++i], 0, 0);
  582.                     else
  583.                         c = strtoll(argv[i]+2, 0, 0);
  584.                     break;
  585.                 case 'h':
  586.                 case '?':
  587.                     goto usage;
  588.                 case '-':
  589.                     goto usage;
  590.                 default:
  591.                     fprintf(stderr, "unknown parm: %s\n", argv[i]);
  592.                     goto usage;
  593.             }
  594.            
  595.         } else {
  596.             fprintf(stderr, "unknown parm: %s\n", argv[i]);
  597.             goto usage;
  598.         }
  599.        
  600.     }
  601.    
  602.     /*
  603.      * Find all the prime factors of the number. This step can take several
  604.      * seconds for 48 bit numbers, which is why we benchmark how long it
  605.      * takes.
  606.      */
  607.     primes_factor(m, factors, &elapsed);
  608.    
  609.     /*
  610.      * Calculate the 'a-1' constant. It must share all the prime factors
  611.      * with the range, and if the range is a multiple of 4, must also
  612.      * be a multiple of 4
  613.      */
  614.     a = 1;
  615.     for (i=0; factors[i]; i++)
  616.         a = a * factors[i];
  617.     if ((m % 4) == 0)
  618.         a *= 2;
  619.     a *= a_offset; /* maybe improve for better randomness */
  620.     a += 1;
  621.    
  622.    
  623.     /*
  624.      * Calculate the 'c' constant. It must have no prime factors in
  625.      * common with the range.
  626.      */
  627.     if (c == 0)
  628.         c = 29752039458; /* something random */
  629.     while (has_factors_in_common(c, factors))
  630.         c++;
  631.    
  632.    
  633.     /*
  634.      * print the results
  635.      */
  636.     //printf("sizeof(int) = %llu-bits\n", (uint64_t)(sizeof(size_t)*8));
  637.     printf("elapsed     = %5.3f-seconds\n", elapsed);
  638.     printf("factors     = ");
  639.     for (i=0; factors[i]; i++)
  640.         printf("%u ", factors[i]);
  641.     printf("%s\n", factors[0]?"":"(none)");
  642.     printf("m           = %-24llu (0x%llx)\n", m, m);
  643.     printf("a           = %-24llu (0x%llx)\n", a, a);
  644.     printf("c           = %-24llu (0x%llx)\n", c, c);
  645.     printf("c%%m         = %-24llu (0x%llx)\n", c%m, c%m);
  646.    
  647.     if (m < 1000000000) {
  648.         if (lcg_verify(a, c+1, m, 280))
  649.             printf("verify      = success\n");
  650.         else
  651.             printf("verify      = failure\n");
  652.     } else {
  653.         printf("verify      = too big to check\n");
  654.     }
  655.        
  656.    
  657.     /*
  658.      * Print some first numbers. We use these to visually inspect whether
  659.      * the results are random or not.
  660.      */
  661.     {
  662.         unsigned count = 0;
  663.         uint64_t x = 0;
  664.         unsigned digits = count_digits(m);
  665.        
  666.         for (i=0; i<100 && i < m; i++) {
  667.             x = lcg(x, a, c, m);
  668.             count += printf("%*llu ", digits, x);
  669.             if (count >= 70) {
  670.                 count = 0;
  671.                 printf("\n");
  672.             }
  673.         }
  674.         printf("\n");
  675.     }
  676.    
  677.     return 0;
  678. }
clone this paste RAW Paste Data