Line data    Source code

       1             : #include "passgen/util/random.h"
       2             : 
       3             : #include <stdbool.h>
       4             : #include <stdio.h>
       5             : #include <stdlib.h>
       6             : 
       7             : #include "tests.h"
       8             : 
       9             : #define XORSHIFT_SEED 234720984723
      10             : 
      11             : /// Tests that a given function covers all possible outputs (0..max, inclusive).
      12             : #define TEST_COVERAGE(max, collate, function)                    \
      13             :     do {                                                         \
      14             :         size_t coverage_len = ((size_t) max) / (collate) + 1ULL; \
      15             :         uint8_t *coverage = calloc((coverage_len + 7) / 8, 1);   \
      16             :         bool full_coverage = false;                              \
      17             :         while(!full_coverage) {                                  \
      18             :             for(size_t i = 0; i < 256; i++) {                    \
      19             :                 size_t pos = function / (collate);               \
      20             :                 coverage[pos / 8] |= 1 << (pos % 8);             \
      21             :             }                                                    \
      22             :             full_coverage = true;                                \
      23             :             for(size_t i = 0; i <= (max / (collate)); i++) {     \
      24             :                 if(!(coverage[i / 8] & (1 << (i % 8)))) {        \
      25             :                     full_coverage = false;                       \
      26             :                     break;                                       \
      27             :                 }                                                \
      28             :             }                                                    \
      29             :         }                                                        \
      30             :         free(coverage);                                          \
      31             :     } while(false)
      32             : 
      33           2 : double standard_deviation(size_t count, uint32_t *elements) {
      34             :     (void) count;
      35             :     (void) elements;
      36             :     // TODO: determine deviation
      37           2 :     return 0;
      38             : }
      39             : 
      40             : /// Tests that a given function has an even distribution
      41             : #define TEST_DISTRIBUTION(max, bucket_num, target, function)   \
      42             :     uint32_t *buckets = calloc(bucket_num, sizeof(uint32_t));  \
      43             :     while(true) {                                              \
      44             :         size_t bucket = function / ((max) / (bucket_num) + 1); \
      45             :         buckets[bucket] += 1;                                  \
      46             :         if(buckets[bucket] == target) {                        \
      47             :             break;                                             \
      48             :         }                                                      \
      49             :     }                                                          \
      50             :     assert(standard_deviation(bucket_num, buckets) < 10);      \
      51             :     free(buckets)
      52             : 
      53           1 : test_result test_random_u8(void) {
      54             :     passgen_random random;
      55           1 :     assert(passgen_random_open(&random, NULL));
      56             : 
      57        2313 :     TEST_COVERAGE(UINT8_MAX, 1, passgen_random_u8(&random));
      58             : 
      59           1 :     passgen_random_close(&random);
      60             : 
      61           1 :     return test_ok;
      62             : }
      63             : 
      64           1 : test_result test_random_u8_max(void) {
      65             :     passgen_random random;
      66           1 :     assert(passgen_random_open(&random, NULL));
      67             : 
      68         255 :     for(size_t max = 1; max < UINT8_MAX; max++) {
      69      277344 :         TEST_COVERAGE(max - 1, 1, passgen_random_u8_max(&random, max));
      70             :     }
      71             : 
      72           1 :     passgen_random_close(&random);
      73             : 
      74           1 :     return test_ok;
      75             : }
      76             : 
      77           1 : test_result test_random_u16(void) {
      78             :     passgen_random random;
      79           1 :     assert(passgen_random_open(&random, NULL));
      80             : 
      81    48976355 :     TEST_COVERAGE(UINT16_MAX, 1, passgen_random_u16(&random));
      82             : 
      83           1 :     passgen_random_close(&random);
      84             : 
      85           1 :     return test_ok;
      86             : }
      87             : 
      88           1 : test_result test_random_u16_max(void) {
      89             :     passgen_random random;
      90           1 :     assert(passgen_random_open(&random, NULL));
      91             : 
      92         255 :     for(size_t max = 1; max < UINT8_MAX; max++) {
      93      270977 :         TEST_COVERAGE(max - 1, 1, passgen_random_u16_max(&random, max));
      94             :     }
      95             : 
      96          12 :     for(size_t max = 1; max < UINT16_MAX; max *= 3) {
      97     6040552 :         TEST_COVERAGE(max - 1, 1, passgen_random_u16_max(&random, max));
      98             :     }
      99             : 
     100           1 :     passgen_random_close(&random);
     101             : 
     102           1 :     return test_ok;
     103             : }
     104             : 
     105           1 : test_result test_random_u32(void) {
     106             :     passgen_random random;
     107           1 :     assert(passgen_random_open(&random, NULL));
     108             : 
     109    22037444 :     TEST_COVERAGE(UINT32_MAX, 1 << 16, passgen_random_u32(&random));
     110      956453 :     TEST_DISTRIBUTION(
     111             :         UINT32_MAX,
     112             :         1 << 10,
     113             :         1 << 10,
     114             :         passgen_random_u32(&random));
     115             : 
     116           1 :     passgen_random_close(&random);
     117             : 
     118           1 :     return test_ok;
     119             : }
     120             : 
     121           1 : test_result test_random_u32_max(void) {
     122             :     passgen_random random;
     123           1 :     assert(passgen_random_open(&random, NULL));
     124             : 
     125         255 :     for(size_t max = 1; max < UINT8_MAX; max++) {
     126      270119 :         TEST_COVERAGE(max - 1, 1, passgen_random_u32_max(&random, max));
     127             :     }
     128             : 
     129          12 :     for(size_t max = 1; max < UINT16_MAX; max *= 3) {
     130    16104007 :         TEST_COVERAGE(max - 1, 1, passgen_random_u32_max(&random, max));
     131             :     }
     132             : 
     133           1 :     passgen_random_close(&random);
     134             : 
     135           1 :     return test_ok;
     136             : }
     137             : 
     138           1 : test_result test_random_u64(void) {
     139             :     passgen_random random;
     140           1 :     assert(passgen_random_open(&random, NULL));
     141             : 
     142             :     // FIXME
     143             :     // TEST_COVERAGE(UINT64_MAX, 1ULL << 48, 1024, passgen_random_u32(&random));
     144      927705 :     TEST_DISTRIBUTION(
     145             :         UINT64_MAX,
     146             :         1 << 10,
     147             :         1 << 10,
     148             :         passgen_random_u64(&random));
     149             : 
     150           1 :     passgen_random_close(&random);
     151             : 
     152           1 :     return test_ok;
     153             : }
     154             : 
     155           1 : test_result test_random_u64_max(void) {
     156             :     passgen_random random;
     157           1 :     assert(passgen_random_open(&random, NULL));
     158             : 
     159         255 :     for(size_t max = 1; max < UINT8_MAX; max++) {
     160      276467 :         TEST_COVERAGE(max - 1, 1, passgen_random_u64_max(&random, max));
     161             :     }
     162             : 
     163          12 :     for(size_t max = 1; max < UINT16_MAX; max *= 3) {
     164    11302227 :         TEST_COVERAGE(max - 1, 1, passgen_random_u64_max(&random, max));
     165             :     }
     166             : 
     167     1000000 :     for(size_t i = 1; i < 1000000; i++) {
     168      999999 :         uint32_t max = passgen_random_u64(&random);
     169             : 
     170      999999 :         assert(passgen_random_u64_max(&random, max) < max);
     171             :     }
     172             : 
     173           1 :     passgen_random_close(&random);
     174             : 
     175           1 :     return test_ok;
     176             : }
     177             : 
     178           1 : test_result test_random_new(void) {
     179           1 :     passgen_random *random_default = passgen_random_new(NULL);
     180           1 :     assert(random_default);
     181           1 :     assert(random_default->read);
     182           1 :     assert(random_default->close);
     183             : 
     184           1 :     passgen_random *random = passgen_random_new("system");
     185           1 :     assert(random);
     186           1 :     assert_eq(random->read, random_default->read);
     187           1 :     assert_eq(random->close, random_default->close);
     188           1 :     passgen_random_free(random);
     189           1 :     passgen_random_free(random_default);
     190             : 
     191           1 :     random = passgen_random_new("zero");
     192           1 :     assert(random);
     193           1 :     assert(random->read);
     194           1 :     assert(random->close);
     195           1 :     assert_eq(passgen_random_u8(random), 0);
     196           1 :     assert_eq(passgen_random_u16(random), 0);
     197           1 :     assert_eq(passgen_random_u32(random), 0);
     198           1 :     assert_eq(passgen_random_u64(random), 0);
     199           1 :     passgen_random_free(random);
     200             : 
     201           1 :     random = passgen_random_new("xorshift:1234");
     202           1 :     assert(random);
     203           1 :     assert(random->read);
     204           1 :     assert(random->close);
     205           1 :     assert_eq(passgen_random_u8(random), 91);
     206           1 :     assert_eq(passgen_random_u16(random), 11632);
     207           1 :     assert_eq(passgen_random_u32(random), 79584);
     208           1 :     assert_eq(passgen_random_u64(random), 3801598356675656448ULL);
     209           1 :     assert_eq(passgen_random_u64_max(random, 999999999), 851051297);
     210           1 :     passgen_random_free(random);
     211             : 
     212           1 :     random = passgen_random_new("file:/dev/zero");
     213           1 :     assert(random);
     214           1 :     assert(random->read);
     215           1 :     assert(random->close);
     216           1 :     assert_eq(passgen_random_u8(random), 0);
     217           1 :     assert_eq(passgen_random_u16(random), 0);
     218           1 :     assert_eq(passgen_random_u32(random), 0);
     219           1 :     assert_eq(passgen_random_u64(random), 0);
     220           1 :     passgen_random_free(random);
     221             : 
     222           1 :     assert(!passgen_random_new("other"));
     223           1 :     assert(!passgen_random_new("xorshift:abc"));
     224           1 :     assert(!passgen_random_new("xorshift:"));
     225           1 :     assert(!passgen_random_new("file:"));
     226           1 :     assert(!passgen_random_new("file:/dev/nonexistant"));
     227             : 
     228           1 :     return test_ok;
     229             : }
     230             : 
     231           1 : test_result test_random_file(void) {
     232           1 :     FILE *file = fopen("/dev/zero", "r");
     233           1 :     assert(file);
     234           1 :     passgen_random *random = passgen_random_new_file(file);
     235           1 :     assert(random);
     236           1 :     assert(random->read);
     237           1 :     assert(random->close);
     238           1 :     assert_eq(passgen_random_u8(random), 0);
     239           1 :     assert_eq(passgen_random_u16(random), 0);
     240           1 :     assert_eq(passgen_random_u32(random), 0);
     241           1 :     assert_eq(passgen_random_u64(random), 0);
     242           1 :     passgen_random_free(random);
     243             : 
     244           1 :     return test_ok;
     245             : }
     246             : 
     247           1 : test_result test_random_zero(void) {
     248           1 :     passgen_random *random = passgen_random_new_zero();
     249           1 :     assert(random);
     250           1 :     assert(random->read);
     251           1 :     assert(random->close);
     252           1 :     assert_eq(passgen_random_u8(random), 0);
     253           1 :     assert_eq(passgen_random_u16(random), 0);
     254           1 :     assert_eq(passgen_random_u32(random), 0);
     255           1 :     assert_eq(passgen_random_u64(random), 0);
     256           1 :     passgen_random_free(random);
     257             : 
     258           1 :     return test_ok;
     259             : }
     260             : 
     261           1 : test_result test_random_new_path(void) {
     262             :     passgen_random *random;
     263           1 :     random = passgen_random_new_path("/dev/nonexistent");
     264           1 :     assert(!random);
     265             : 
     266             :     // reading from /dev/zero should always yield zero.
     267           1 :     random = passgen_random_new_path("/dev/zero");
     268           1 :     assert(random);
     269           1 :     assert(random->data);
     270           1 :     assert(passgen_random_u8(random) == 0);
     271           1 :     assert(passgen_random_u16(random) == 0);
     272           1 :     assert(passgen_random_u32(random) == 0);
     273           1 :     assert(passgen_random_u64(random) == 0);
     274           1 :     passgen_random_free(random);
     275             : 
     276           1 :     return test_ok;
     277             : }
     278             : 
     279           1 : test_result test_random_open(void) {
     280             :     passgen_random random;
     281           1 :     assert(passgen_random_open(&random, NULL));
     282           1 :     assert(random.read);
     283           1 :     assert(random.close);
     284           1 :     passgen_random_close(&random);
     285           1 :     assert(!random.read);
     286             : 
     287           1 :     assert(passgen_random_open(&random, "system"));
     288           1 :     assert(random.read);
     289           1 :     assert(random.close);
     290           1 :     passgen_random_close(&random);
     291             : 
     292           1 :     assert(passgen_random_open(&random, "xorshift:1234"));
     293           1 :     assert(random.read);
     294           1 :     assert(random.close);
     295           1 :     passgen_random_close(&random);
     296             : 
     297           1 :     assert(passgen_random_open(&random, "zero"));
     298           1 :     assert(random.read);
     299           1 :     assert(random.close);
     300           1 :     passgen_random_close(&random);
     301             : 
     302           1 :     assert(passgen_random_open(&random, "file:/dev/random"));
     303           1 :     assert(random.read);
     304           1 :     assert(random.close);
     305           1 :     passgen_random_close(&random);
     306             : 
     307           1 :     assert(!passgen_random_open(&random, "other"));
     308           1 :     assert(!passgen_random_open(&random, "file:/dev/notexists"));
     309           1 :     assert(!passgen_random_open(&random, "xorshift:"));
     310           1 :     assert(!passgen_random_open(&random, "xorshift:abc"));
     311             : 
     312           1 :     return test_ok;
     313             : }
     314             : 
     315           1 : test_result test_random_open_path(void) {
     316             :     passgen_random random;
     317           1 :     assert(!passgen_random_open_path(&random, "/dev/nonexistent"));
     318             : 
     319           1 :     assert(passgen_random_open_path(&random, "/dev/zero"));
     320           1 :     assert(random.data);
     321           1 :     assert(passgen_random_u8(&random) == 0);
     322           1 :     assert(passgen_random_u16(&random) == 0);
     323           1 :     assert(passgen_random_u32(&random) == 0);
     324           1 :     assert(passgen_random_u64(&random) == 0);
     325           1 :     passgen_random_close(&random);
     326           1 :     assert(!random.data);
     327             : 
     328           1 :     return test_ok;
     329             : }
     330             : 
     331           1 : test_result test_random_read(void) {
     332             :     passgen_random random;
     333           1 :     assert(passgen_random_open_xorshift(&random, XORSHIFT_SEED));
     334             : 
     335           1 :     uint8_t data[2000] = {0};
     336             : 
     337             :     // fill small.
     338           1 :     passgen_random_read(&random, &data[0], 1);
     339           1 :     assert(random.pos == 1);
     340           1 :     assert(data[0] == random.buffer[0]);
     341           1 :     assert(data[1] == 0);
     342             : 
     343           1 :     passgen_random_read(&random, &data[0], 2);
     344           1 :     assert(random.pos == 3);
     345           1 :     assert(data[0] == random.buffer[1]);
     346           1 :     assert(data[1] == random.buffer[2]);
     347           1 :     assert(data[2] == 0);
     348             : 
     349           1 :     passgen_random_read(&random, &data[0], 4);
     350           1 :     assert(random.pos == 7);
     351           1 :     assert(data[0] == random.buffer[3]);
     352           1 :     assert(data[1] == random.buffer[4]);
     353           1 :     assert(data[2] == random.buffer[5]);
     354           1 :     assert(data[3] == random.buffer[6]);
     355           1 :     assert(data[4] == 0);
     356             : 
     357           1 :     passgen_random_read(&random, &data[0], 8);
     358           1 :     assert(random.pos == 15);
     359           1 :     assert(data[0] == random.buffer[7]);
     360           1 :     assert(data[1] == random.buffer[8]);
     361           1 :     assert(data[2] == random.buffer[9]);
     362           1 :     assert(data[3] == random.buffer[10]);
     363           1 :     assert(data[4] == random.buffer[11]);
     364           1 :     assert(data[5] == random.buffer[12]);
     365           1 :     assert(data[6] == random.buffer[13]);
     366           1 :     assert(data[7] == random.buffer[14]);
     367           1 :     assert(data[8] == 0);
     368             : 
     369             :     // test wraparound.
     370        1009 :     while(random.pos != (sizeof(random.buffer) - 1)) {
     371        1008 :         passgen_random_read(&random, &data[0], 1);
     372             :     }
     373           1 :     passgen_random_read(&random, &data[0], 1);
     374           1 :     assert(random.pos == 0);
     375             : 
     376        1024 :     while(random.pos != (sizeof(random.buffer) - 1)) {
     377        1023 :         passgen_random_read(&random, &data[0], 1);
     378             :     }
     379           1 :     passgen_random_read(&random, &data[0], 3);
     380           1 :     assert(data[1] == random.buffer[0]);
     381           1 :     assert(data[2] == random.buffer[1]);
     382           1 :     assert(random.pos == 2);
     383             : 
     384             :     // test reading larger.
     385           1 :     passgen_random_read(&random, &data[0], sizeof(random.buffer) + 1);
     386           1 :     assert(random.pos == 2);
     387             : 
     388           1 :     passgen_random_close(&random);
     389             : 
     390           1 :     return test_ok;
     391             : }
     392             : 
     393           1 : test_result test_random_xorshift(void) {
     394             :     passgen_random random;
     395             : 
     396             :     // using a state of zero generates only zeroes.
     397           1 :     assert(passgen_random_open_xorshift(&random, 0) != NULL);
     398           1 :     assert(passgen_random_u8(&random) == 0);
     399           1 :     assert(passgen_random_u16(&random) == 0);
     400           1 :     assert(passgen_random_u32(&random) == 0);
     401           1 :     assert(passgen_random_u64(&random) == 0);
     402           1 :     passgen_random_close(&random);
     403             : 
     404             :     // same seed always yields the same output
     405           1 :     assert(passgen_random_open_xorshift(&random, 123) != NULL);
     406           1 :     assert(passgen_random_u8(&random) == 187);
     407           1 :     assert(passgen_random_u16(&random) == 31102);
     408           1 :     assert(passgen_random_u32(&random) == 7933);
     409           1 :     assert(passgen_random_u64(&random) == 2214108778545186304ULL);
     410           1 :     passgen_random_close(&random);
     411             : 
     412           1 :     return test_ok;
     413             : }
     414             : 
     415             : #undef XORSHIFT_SEED