Line data    Source code

       1             : #include "passgen/markov.h"
       2             : #include "tests.h"
       3             : #include <stdlib.h>
       4             : 
       5             : #define SEED 234720984723
       6             : 
       7             : #define passgen_markov_leaf_count_raw(leaf, codepoint) \
       8             :     leaf->entries[leaf->capacity].count[codepoint % leaf->capacity]
       9             : 
      10             : #define passgen_markov_leaf_codepoint_raw(leaf, index) \
      11             :     leaf->entries[0].codepoint[index % leaf->capacity]
      12             : 
      13           1 : test_result test_markov_node_layout(void) {
      14           1 :     passgen_markov_node *node = passgen_markov_node_new(0);
      15             : 
      16           1 :     assert_eq(node->capacity, 3);
      17             : 
      18             :     assert_eq(
      19             :         &passgen_markov_node_codepoint(node, 0),
      20             :         ((void *) node) + sizeof(size_t));
      21           1 :     assert_eq(
      22             :         &passgen_markov_node_codepoint(node, 1),
      23             :         ((void *) node) + sizeof(size_t) + 1 * sizeof(uint32_t));
      24           1 :     assert_eq(
      25             :         &passgen_markov_node_codepoint(node, 2),
      26             :         ((void *) node) + sizeof(size_t) + 2 * sizeof(uint32_t));
      27             : 
      28           1 :     assert_eq(
      29             :         &passgen_markov_node_child(node, 0),
      30             :         ((void *) node) + sizeof(size_t) + 4 * sizeof(uint32_t));
      31           1 :     assert_eq(
      32             :         &passgen_markov_node_child(node, 1),
      33             :         ((void *) node) + 2 * sizeof(size_t) + 4 * sizeof(uint32_t));
      34           1 :     assert_eq(
      35             :         &passgen_markov_node_child(node, 2),
      36             :         ((void *) node) + 3 * sizeof(size_t) + 4 * sizeof(uint32_t));
      37             : 
      38           1 :     free(node);
      39             : 
      40           1 :     return test_ok;
      41             : }
      42             : 
      43           1 : test_result test_markov_leaf_layout(void) {
      44           1 :     passgen_markov_leaf *leaf = passgen_markov_leaf_new(0);
      45             : 
      46           1 :     assert_eq(leaf->capacity, 3);
      47             : 
      48             :     assert_eq(
      49             :         &passgen_markov_leaf_codepoint_raw(leaf, 0),
      50             :         ((void *) leaf) + 2 * sizeof(size_t));
      51           1 :     assert_eq(
      52             :         &passgen_markov_leaf_codepoint_raw(leaf, 1),
      53             :         ((void *) leaf) + 2 * sizeof(size_t) + 1 * sizeof(uint32_t));
      54           1 :     assert_eq(
      55             :         &passgen_markov_leaf_codepoint_raw(leaf, 2),
      56             :         ((void *) leaf) + 2 * sizeof(size_t) + 2 * sizeof(uint32_t));
      57             : 
      58           1 :     assert_eq(
      59             :         &passgen_markov_leaf_count_raw(leaf, 0),
      60             :         ((void *) leaf) + 2 * sizeof(size_t) + 3 * sizeof(uint32_t));
      61           1 :     assert_eq(
      62             :         &passgen_markov_leaf_count_raw(leaf, 1),
      63             :         ((void *) leaf) + 2 * sizeof(size_t) + 4 * sizeof(uint32_t));
      64           1 :     assert_eq(
      65             :         &passgen_markov_leaf_count_raw(leaf, 2),
      66             :         ((void *) leaf) + 2 * sizeof(size_t) + 5 * sizeof(uint32_t));
      67             : 
      68           1 :     free(leaf);
      69             : 
      70           1 :     return test_ok;
      71             : }
      72             : 
      73           1 : test_result test_markov_node_insert(void) {
      74           1 :     passgen_markov_node *node = passgen_markov_node_new(0);
      75           1 :     assert_eq(node->capacity, 3);
      76             : 
      77           1 :     node = passgen_markov_node_insert(node, 0);
      78           1 :     assert(!passgen_markov_node_child(node, 0).node);
      79           1 :     passgen_markov_node_child(node, 0).node = (passgen_markov_node *) &node;
      80             : 
      81           1 :     node = passgen_markov_node_insert(node, 1);
      82           1 :     assert(!passgen_markov_node_child(node, 1).node);
      83           1 :     passgen_markov_node_child(node, 1).node = (passgen_markov_node *) &node;
      84             : 
      85           1 :     node = passgen_markov_node_insert(node, 2);
      86           1 :     assert(!passgen_markov_node_child(node, 2).node);
      87           1 :     passgen_markov_node_child(node, 2).node = (passgen_markov_node *) &node;
      88             : 
      89           1 :     assert_eq(node->capacity, 3);
      90             : 
      91           1 :     node = passgen_markov_node_insert(node, 3);
      92           1 :     assert(!passgen_markov_node_child(node, 3).node);
      93           1 :     passgen_markov_node_child(node, 3).node = (passgen_markov_node *) &node;
      94             : 
      95           1 :     assert_eq(node->capacity, 7);
      96             : 
      97           1 :     node = passgen_markov_node_insert(node, 4);
      98           1 :     assert(!passgen_markov_node_child(node, 4).node);
      99           1 :     passgen_markov_node_child(node, 4).node = (passgen_markov_node *) &node;
     100             : 
     101           1 :     node = passgen_markov_node_insert(node, 5);
     102           1 :     assert(!passgen_markov_node_child(node, 5).node);
     103           1 :     passgen_markov_node_child(node, 5).node = (passgen_markov_node *) &node;
     104             : 
     105           1 :     node = passgen_markov_node_insert(node, 6);
     106           1 :     assert(!passgen_markov_node_child(node, 6).node);
     107           1 :     passgen_markov_node_child(node, 6).node = (passgen_markov_node *) &node;
     108             : 
     109           1 :     node = passgen_markov_node_insert(node, 7);
     110           1 :     assert(!passgen_markov_node_child(node, 7).node);
     111           1 :     passgen_markov_node_child(node, 7).node = (passgen_markov_node *) &node;
     112             : 
     113           1 :     assert_eq(node->capacity, 17);
     114             : 
     115         993 :     for(size_t i = 8; i < 1000; i++) {
     116         992 :         node = passgen_markov_node_insert(node, i);
     117         992 :         assert(!passgen_markov_node_child(node, i).node);
     118         992 :         passgen_markov_node_child(node, i).node = (passgen_markov_node *) &node;
     119             :     }
     120             : 
     121           1 :     assert_eq(node->capacity, 1361);
     122             : 
     123           1 :     free(node);
     124             : 
     125           1 :     return test_ok;
     126             : }
     127             : 
     128           1 : test_result test_markov_leaf_insert(void) {
     129           1 :     passgen_markov_leaf *leaf = passgen_markov_leaf_new(0);
     130           1 :     assert_eq(leaf->capacity, 3);
     131             : 
     132           1 :     leaf = passgen_markov_leaf_insert(leaf, 0, 1);
     133           1 :     assert(passgen_markov_leaf_count_raw(leaf, 0) == 1);
     134             : 
     135           1 :     leaf = passgen_markov_leaf_insert(leaf, 0, 1);
     136           1 :     assert(passgen_markov_leaf_count_raw(leaf, 0) == 2);
     137             : 
     138           1 :     leaf = passgen_markov_leaf_insert(leaf, 1, 3);
     139           1 :     assert(passgen_markov_leaf_count_raw(leaf, 1) == 3);
     140             : 
     141           1 :     leaf = passgen_markov_leaf_insert(leaf, 2, 7);
     142           1 :     assert(passgen_markov_leaf_count_raw(leaf, 2) == 7);
     143             : 
     144           1 :     assert_eq(leaf->capacity, 3);
     145             : 
     146           1 :     leaf = passgen_markov_leaf_insert(leaf, 3, 2);
     147           1 :     assert(passgen_markov_leaf_count_raw(leaf, 3) == 2);
     148             : 
     149           1 :     assert_eq(leaf->capacity, 7);
     150             : 
     151           1 :     leaf = passgen_markov_leaf_insert(leaf, 4, 4);
     152           1 :     assert(passgen_markov_leaf_count_raw(leaf, 4) == 4);
     153             : 
     154           1 :     leaf = passgen_markov_leaf_insert(leaf, 5, 6);
     155           1 :     assert(passgen_markov_leaf_count_raw(leaf, 5) == 6);
     156             : 
     157           1 :     leaf = passgen_markov_leaf_insert(leaf, 6, 8);
     158           1 :     assert(passgen_markov_leaf_count_raw(leaf, 6) == 8);
     159             : 
     160           1 :     leaf = passgen_markov_leaf_insert(leaf, 7, 10);
     161           1 :     assert(passgen_markov_leaf_count_raw(leaf, 7) == 10);
     162             : 
     163           1 :     assert_eq(leaf->capacity, 17);
     164             : 
     165         993 :     for(size_t i = 8; i < 1000; i++) {
     166         992 :         leaf = passgen_markov_leaf_insert(leaf, i, i);
     167         992 :         assert(passgen_markov_leaf_count_raw(leaf, i) == i);
     168             :     }
     169             : 
     170           1 :     assert_eq(leaf->capacity, 1361);
     171             : 
     172           1 :     free(leaf);
     173             : 
     174           1 :     return test_ok;
     175             : }
     176             : 
     177           1 : test_result test_markov_node_insert_word(void) {
     178           1 :     passgen_markov_node *root_node = passgen_markov_node_new(0);
     179             : 
     180           1 :     const uint32_t word[] = {'h', 'e', 'l', 'l', 'o'};
     181             : 
     182             :     root_node =
     183           1 :         passgen_markov_node_insert_word(root_node, (void *) &word, 5, 1);
     184           1 :     passgen_markov_node *node = root_node;
     185             : 
     186           1 :     assert_eq(passgen_markov_node_codepoint(node, 'h'), 'h');
     187           1 :     node = passgen_markov_node_child(node, 'h').node;
     188           1 :     assert(node);
     189             : 
     190           1 :     assert_eq(passgen_markov_node_codepoint(node, 'e'), 'e');
     191           1 :     node = passgen_markov_node_child(node, 'e').node;
     192           1 :     assert(node);
     193             : 
     194           1 :     assert_eq(passgen_markov_node_codepoint(node, 'l'), 'l');
     195           1 :     node = passgen_markov_node_child(node, 'l').node;
     196           1 :     assert(node);
     197             : 
     198           1 :     assert_eq(passgen_markov_node_codepoint(node, 'l'), 'l');
     199           1 :     passgen_markov_leaf *leaf = passgen_markov_node_child(node, 'l').leaf;
     200           1 :     assert(leaf);
     201           1 :     assert_eq(leaf->capacity, 3);
     202           1 :     assert_eq(leaf->total_count, 1);
     203             : 
     204           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 'o'), 'o');
     205           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 'o'), 1);
     206             : 
     207           1 :     passgen_markov_node_free(root_node, 4);
     208             : 
     209           1 :     return test_ok;
     210             : }
     211             : 
     212           1 : test_result test_markov_add(void) {
     213             :     passgen_markov markov;
     214             :     passgen_markov_node *node;
     215             :     passgen_markov_leaf *leaf;
     216             : 
     217             :     // markov chain level 2, meaning two prefix chars
     218           1 :     passgen_markov_init(&markov, 2);
     219             : 
     220             :     // this should have added 00a and 0a0 into the chain.
     221           1 :     passgen_markov_add(&markov, (void *) &(const uint32_t[]){'a'}, 1, 1);
     222             : 
     223             :     // verify 00a is there
     224           1 :     node = passgen_markov_node_child(markov.root, 0).node;
     225           1 :     assert(node);
     226           1 :     leaf = passgen_markov_node_child(node, 0).leaf;
     227           1 :     assert(leaf);
     228           1 :     assert_eq(leaf->total_count, 1);
     229           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 'a'), 'a');
     230           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 'a'), 1);
     231             : 
     232             :     // verify 0a0 is there
     233           1 :     node = passgen_markov_node_child(markov.root, 0).node;
     234           1 :     assert(node);
     235           1 :     leaf = passgen_markov_node_child(node, 'a').leaf;
     236           1 :     assert(leaf);
     237           1 :     assert_eq(leaf->total_count, 1);
     238           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 0), 0);
     239           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 0), 1);
     240             : 
     241             :     // this should have added 00l, 0la, la0, each with a weight of 2.
     242           1 :     passgen_markov_add(&markov, (void *) &(const uint32_t[]){'l', 'a'}, 2, 2);
     243             : 
     244             :     // verify 00l is there
     245           1 :     node = passgen_markov_node_child(markov.root, 0).node;
     246           1 :     assert(node);
     247           1 :     leaf = passgen_markov_node_child(node, 0).leaf;
     248           1 :     assert(leaf);
     249           1 :     assert_eq(leaf->total_count, 3);
     250           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 'l'), 'l');
     251           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 'l'), 2);
     252             : 
     253             :     // verify 0la is there
     254           1 :     node = passgen_markov_node_child(markov.root, 0).node;
     255           1 :     assert(node);
     256           1 :     leaf = passgen_markov_node_child(node, 'l').leaf;
     257           1 :     assert(leaf);
     258           1 :     assert_eq(leaf->total_count, 2);
     259           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 'a'), 'a');
     260           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 'a'), 2);
     261             : 
     262             :     // verify la0 is there
     263           1 :     node = passgen_markov_node_child(markov.root, 'l').node;
     264           1 :     assert(node);
     265           1 :     leaf = passgen_markov_node_child(node, 'a').leaf;
     266           1 :     assert(leaf);
     267           1 :     assert_eq(leaf->total_count, 2);
     268           1 :     assert_eq(passgen_markov_leaf_codepoint_raw(leaf, 0), 0);
     269           1 :     assert_eq(passgen_markov_leaf_count_raw(leaf, 0), 2);
     270             : 
     271           1 :     passgen_markov_add(&markov, (void *) &(const uint32_t[]){'l', 'e'}, 2, 1);
     272           1 :     passgen_markov_add(
     273             :         &markov,
     274           1 :         (void *) &(const uint32_t[]){'t', 'h', 'e'},
     275             :         3,
     276             :         1);
     277           1 :     passgen_markov_add(
     278             :         &markov,
     279           1 :         (void *) &(const uint32_t[]){'p', 'a', 'r', 't'},
     280             :         4,
     281             :         1);
     282           1 :     passgen_markov_add(
     283             :         &markov,
     284           1 :         (void *) &(const uint32_t[]){'p', 'h', 'o', 'n', 'e'},
     285             :         5,
     286             :         1);
     287             : 
     288           1 :     passgen_markov_free(&markov);
     289             : 
     290           1 :     return test_ok;
     291             : }
     292             : 
     293           1 : test_result test_markov_add_random(void) {
     294             :     passgen_markov markov;
     295             :     passgen_random rand;
     296           1 :     passgen_random_open_xorshift(&rand, SEED);
     297           1 :     uint32_t word[12] = {0};
     298             : 
     299           8 :     for(size_t length = 3; length < 10; length++) {
     300           7 :         passgen_markov_init(&markov, length);
     301             : 
     302             :         // FIXME: if you set count to 1000, it breaks.
     303         707 :         for(size_t count = 0; count < 100; count++) {
     304        9100 :             for(size_t offset = 0; offset < 12; offset++) {
     305        8400 :                 word[offset] = passgen_random_u32(&rand);
     306             :             }
     307             : 
     308         700 :             passgen_markov_add(&markov, &word[0], 12, 1);
     309             :         }
     310             : 
     311           7 :         passgen_markov_free(&markov);
     312             :     }
     313             : 
     314           1 :     passgen_random_close(&rand);
     315             : 
     316           1 :     return test_ok;
     317             : }
     318             : 
     319           1 : test_result test_markov_leaf_count_random(void) {
     320             :     passgen_random rand;
     321           1 :     passgen_random_open_xorshift(&rand, SEED);
     322           1 :     passgen_markov_leaf *leaf = passgen_markov_leaf_new(0);
     323             : 
     324             :     /// FIXME: if you 10x the count, it breaks.
     325        1001 :     for(size_t count = 0; count < 1000; count++) {
     326        1000 :         uint32_t codepoint = passgen_random_u32(&rand);
     327        1000 :         uint32_t before = passgen_markov_leaf_count(leaf, codepoint);
     328        1000 :         assert_eq(before, 0);
     329             :     }
     330             : 
     331           1 :     passgen_markov_leaf_free(leaf);
     332           1 :     passgen_random_close(&rand);
     333             : 
     334           1 :     return test_ok;
     335             : }
     336             : 
     337           1 : test_result test_markov_leaf_insert_random(void) {
     338             :     passgen_random rand;
     339           1 :     passgen_random_open_xorshift(&rand, SEED);
     340           1 :     passgen_markov_leaf *leaf = passgen_markov_leaf_new(0);
     341             : 
     342       10001 :     for(size_t count = 0; count < 10000; count++) {
     343       10000 :         uint32_t codepoint = passgen_random_u32(&rand);
     344       10000 :         uint32_t weight = passgen_random_u16(&rand);
     345       10000 :         uint32_t before = passgen_markov_leaf_count(leaf, codepoint);
     346       10000 :         leaf = passgen_markov_leaf_insert(leaf, codepoint, weight);
     347       10000 :         uint32_t after = passgen_markov_leaf_count(leaf, codepoint);
     348       10000 :         assert_eq(after - before, weight);
     349             :     }
     350             : 
     351           1 :     passgen_markov_leaf_free(leaf);
     352           1 :     passgen_random_close(&rand);
     353             : 
     354           1 :     return test_ok;
     355             : }
     356             : 
     357           1 : test_result test_markov_leaf_insert_sequential(void) {
     358             :     passgen_random rand;
     359           1 :     passgen_random_open_xorshift(&rand, SEED);
     360           1 :     passgen_markov_leaf *leaf = passgen_markov_leaf_new(0);
     361             : 
     362      100001 :     for(size_t count = 0; count < 100000; count++) {
     363      100000 :         uint32_t codepoint = count;
     364      100000 :         uint32_t weight = passgen_random_u16(&rand);
     365      100000 :         uint32_t before = passgen_markov_leaf_count(leaf, codepoint);
     366      100000 :         leaf = passgen_markov_leaf_insert(leaf, codepoint, weight);
     367      100000 :         uint32_t after = passgen_markov_leaf_count(leaf, codepoint);
     368      100000 :         assert_eq(after - before, weight);
     369             :     }
     370             : 
     371           1 :     passgen_markov_leaf_free(leaf);
     372           1 :     passgen_random_close(&rand);
     373             : 
     374           1 :     return test_ok;
     375             : }
     376             : 
     377           1 : test_result test_markov_generate(void) {
     378           1 :     passgen_random *rand = passgen_random_new_xorshift(SEED);
     379             :     // passgen_random_open_xorshift(&rand, SEED);
     380             : 
     381             :     passgen_markov markov;
     382           1 :     passgen_markov_init(&markov, 2);
     383             : 
     384           1 :     passgen_markov_add(&markov, &(const uint32_t[]){'a', 'b'}[0], 2, 1);
     385           1 :     passgen_markov_add(&markov, &(const uint32_t[]){'b'}[0], 1, 1);
     386           1 :     passgen_markov_add(
     387             :         &markov,
     388           1 :         &(const uint32_t[]){'c', 'd', 'e', 'f'}[0],
     389             :         4,
     390             :         1);
     391             : 
     392             :     /*
     393             :     uint32_t next, word[32];
     394             :     memset(word, 0, sizeof(word));
     395             : 
     396             :     word[2] = passgen_markov_generate(&markov, &word[0], rand);
     397             :     assert(word[2] == 'c');
     398             :     word[3] = passgen_markov_generate(&markov, &word[1], rand);
     399             :     assert(word[3] == 'd');
     400             :     word[4] = passgen_markov_generate(&markov, &word[2], rand);
     401             :     assert(word[4] == 'e');
     402             :     word[5] = passgen_markov_generate(&markov, &word[3], rand);
     403             :     assert(word[5] == 'f');
     404             :     word[6] = passgen_markov_generate(&markov, &word[4], rand);
     405             :     assert(word[6] == 0);
     406             : 
     407             :     word[2] = passgen_markov_generate(&markov, &word[0], rand);
     408             :     assert(word[2] == 'b');
     409             :     word[3] = passgen_markov_generate(&markov, &word[1], rand);
     410             :     assert(word[3] == 0);
     411             :     */
     412             : 
     413           1 :     passgen_markov_free(&markov);
     414           1 :     passgen_random_free(rand);
     415             : 
     416           1 :     return test_ok;
     417             : }