/builds/xfbs/passgen/src/tests/markov.c
Line | Count | Source |
1 | | #include "passgen/markov.h" |
2 | | #include "tests.h" |
3 | | #include <stdlib.h> |
4 | | |
5 | 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 | 1 | |
16 | 1 | assert_eq(node->capacity, 3); |
17 | 1 | |
18 | 1 | assert_eq( |
19 | 1 | &passgen_markov_node_codepoint(node, 0), |
20 | 1 | ((void *) node) + sizeof(size_t)); |
21 | 1 | assert_eq( |
22 | 1 | &passgen_markov_node_codepoint(node, 1), |
23 | 1 | ((void *) node) + sizeof(size_t) + 1 * sizeof(uint32_t)); |
24 | 1 | assert_eq( |
25 | 1 | &passgen_markov_node_codepoint(node, 2), |
26 | 1 | ((void *) node) + sizeof(size_t) + 2 * sizeof(uint32_t)); |
27 | 1 | |
28 | 1 | assert_eq( |
29 | 1 | &passgen_markov_node_child(node, 0), |
30 | 1 | ((void *) node) + sizeof(size_t) + 4 * sizeof(uint32_t)); |
31 | 1 | assert_eq( |
32 | 1 | &passgen_markov_node_child(node, 1), |
33 | 1 | ((void *) node) + 2 * sizeof(size_t) + 4 * sizeof(uint32_t)); |
34 | 1 | assert_eq( |
35 | 1 | &passgen_markov_node_child(node, 2), |
36 | 1 | ((void *) node) + 3 * sizeof(size_t) + 4 * sizeof(uint32_t)); |
37 | 1 | |
38 | 1 | free(node); |
39 | 1 | |
40 | 1 | return test_ok; |
41 | 1 | } |
42 | | |
43 | 1 | test_result test_markov_leaf_layout(void) { |
44 | 1 | passgen_markov_leaf *leaf = passgen_markov_leaf_new(0); |
45 | 1 | |
46 | 1 | assert_eq(leaf->capacity, 3); |
47 | 1 | |
48 | 1 | assert_eq( |
49 | 1 | &passgen_markov_leaf_codepoint_raw(leaf, 0), |
50 | 1 | ((void *) leaf) + 2 * sizeof(size_t)); |
51 | 1 | assert_eq( |
52 | 1 | &passgen_markov_leaf_codepoint_raw(leaf, 1), |
53 | 1 | ((void *) leaf) + 2 * sizeof(size_t) + 1 * sizeof(uint32_t)); |
54 | 1 | assert_eq( |
55 | 1 | &passgen_markov_leaf_codepoint_raw(leaf, 2), |
56 | 1 | ((void *) leaf) + 2 * sizeof(size_t) + 2 * sizeof(uint32_t)); |
57 | 1 | |
58 | 1 | assert_eq( |
59 | 1 | &passgen_markov_leaf_count_raw(leaf, 0), |
60 | 1 | ((void *) leaf) + 2 * sizeof(size_t) + 3 * sizeof(uint32_t)); |
61 | 1 | assert_eq( |
62 | 1 | &passgen_markov_leaf_count_raw(leaf, 1), |
63 | 1 | ((void *) leaf) + 2 * sizeof(size_t) + 4 * sizeof(uint32_t)); |
64 | 1 | assert_eq( |
65 | 1 | &passgen_markov_leaf_count_raw(leaf, 2), |
66 | 1 | ((void *) leaf) + 2 * sizeof(size_t) + 5 * sizeof(uint32_t)); |
67 | 1 | |
68 | 1 | free(leaf); |
69 | 1 | |
70 | 1 | return test_ok; |
71 | 1 | } |
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 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
89 | 1 | assert_eq(node->capacity, 3); |
90 | 1 | |
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 | 1 | |
95 | 1 | assert_eq(node->capacity, 7); |
96 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
113 | 1 | assert_eq(node->capacity, 17); |
114 | 1 | |
115 | 993 | for(size_t i = 8; i < 1000; i++992 ) { |
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 | 992 | } |
120 | 1 | |
121 | 1 | assert_eq(node->capacity, 1361); |
122 | 1 | |
123 | 1 | free(node); |
124 | 1 | |
125 | 1 | return test_ok; |
126 | 1 | } |
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 | 1 | |
132 | 1 | leaf = passgen_markov_leaf_insert(leaf, 0, 1); |
133 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 0) == 1); |
134 | 1 | |
135 | 1 | leaf = passgen_markov_leaf_insert(leaf, 0, 1); |
136 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 0) == 2); |
137 | 1 | |
138 | 1 | leaf = passgen_markov_leaf_insert(leaf, 1, 3); |
139 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 1) == 3); |
140 | 1 | |
141 | 1 | leaf = passgen_markov_leaf_insert(leaf, 2, 7); |
142 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 2) == 7); |
143 | 1 | |
144 | 1 | assert_eq(leaf->capacity, 3); |
145 | 1 | |
146 | 1 | leaf = passgen_markov_leaf_insert(leaf, 3, 2); |
147 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 3) == 2); |
148 | 1 | |
149 | 1 | assert_eq(leaf->capacity, 7); |
150 | 1 | |
151 | 1 | leaf = passgen_markov_leaf_insert(leaf, 4, 4); |
152 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 4) == 4); |
153 | 1 | |
154 | 1 | leaf = passgen_markov_leaf_insert(leaf, 5, 6); |
155 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 5) == 6); |
156 | 1 | |
157 | 1 | leaf = passgen_markov_leaf_insert(leaf, 6, 8); |
158 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 6) == 8); |
159 | 1 | |
160 | 1 | leaf = passgen_markov_leaf_insert(leaf, 7, 10); |
161 | 1 | assert(passgen_markov_leaf_count_raw(leaf, 7) == 10); |
162 | 1 | |
163 | 1 | assert_eq(leaf->capacity, 17); |
164 | 1 | |
165 | 993 | for(size_t i = 8; i < 1000; i++992 ) { |
166 | 992 | leaf = passgen_markov_leaf_insert(leaf, i, i); |
167 | 992 | assert(passgen_markov_leaf_count_raw(leaf, i) == i); |
168 | 992 | } |
169 | 1 | |
170 | 1 | assert_eq(leaf->capacity, 1361); |
171 | 1 | |
172 | 1 | free(leaf); |
173 | 1 | |
174 | 1 | return test_ok; |
175 | 1 | } |
176 | | |
177 | 1 | test_result test_markov_node_insert_word(void) { |
178 | 1 | passgen_markov_node *root_node = passgen_markov_node_new(0); |
179 | 1 | |
180 | 1 | const uint32_t word[] = {'h', 'e', 'l', 'l', 'o'}; |
181 | 1 | |
182 | 1 | root_node = |
183 | 1 | passgen_markov_node_insert_word(root_node, (void *) &word, 5, 1); |
184 | 1 | passgen_markov_node *node = root_node; |
185 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
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 | 1 | |
207 | 1 | passgen_markov_node_free(root_node, 4); |
208 | 1 | |
209 | 1 | return test_ok; |
210 | 1 | } |
211 | | |
212 | 1 | test_result test_markov_add(void) { |
213 | 1 | passgen_markov markov; |
214 | 1 | passgen_markov_node *node; |
215 | 1 | passgen_markov_leaf *leaf; |
216 | 1 | |
217 | 1 | // markov chain level 2, meaning two prefix chars |
218 | 1 | passgen_markov_init(&markov, 2); |
219 | 1 | |
220 | 1 | // this should have added 00a and 0a0 into the chain. |
221 | 1 | passgen_markov_add(&markov, (void *) &(const uint32_t[]){'a'}, 1, 1); |
222 | 1 | |
223 | 1 | // 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 | 1 | |
232 | 1 | // 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 | 1 | |
241 | 1 | // 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 | 1 | |
244 | 1 | // 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 | 1 | |
253 | 1 | // 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 | 1 | |
262 | 1 | // 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 | 1 | |
271 | 1 | passgen_markov_add(&markov, (void *) &(const uint32_t[]){'l', 'e'}, 2, 1); |
272 | 1 | passgen_markov_add( |
273 | 1 | &markov, |
274 | 1 | (void *) &(const uint32_t[]){'t', 'h', 'e'}, |
275 | 1 | 3, |
276 | 1 | 1); |
277 | 1 | passgen_markov_add( |
278 | 1 | &markov, |
279 | 1 | (void *) &(const uint32_t[]){'p', 'a', 'r', 't'}, |
280 | 1 | 4, |
281 | 1 | 1); |
282 | 1 | passgen_markov_add( |
283 | 1 | &markov, |
284 | 1 | (void *) &(const uint32_t[]){'p', 'h', 'o', 'n', 'e'}, |
285 | 1 | 5, |
286 | 1 | 1); |
287 | 1 | |
288 | 1 | passgen_markov_free(&markov); |
289 | 1 | |
290 | 1 | return test_ok; |
291 | 1 | } |
292 | | |
293 | 1 | test_result test_markov_add_random(void) { |
294 | 1 | passgen_markov markov; |
295 | 1 | passgen_random rand; |
296 | 1 | passgen_random_open_xorshift(&rand, SEED); |
297 | 1 | uint32_t word[12] = {0}; |
298 | 1 | |
299 | 8 | for(size_t length = 3; length < 10; length++7 ) { |
300 | 7 | passgen_markov_init(&markov, length); |
301 | 7 | |
302 | 7 | // FIXME: if you set count to 1000, it breaks. |
303 | 707 | for(size_t count = 0; count < 100; count++700 ) { |
304 | 9.10k | for(size_t offset = 0; offset < 12; offset++8.40k ) { |
305 | 8.40k | word[offset] = passgen_random_u32(&rand); |
306 | 8.40k | } |
307 | 700 | |
308 | 700 | passgen_markov_add(&markov, &word[0], 12, 1); |
309 | 700 | } |
310 | 7 | |
311 | 7 | passgen_markov_free(&markov); |
312 | 7 | } |
313 | 1 | |
314 | 1 | passgen_random_close(&rand); |
315 | 1 | |
316 | 1 | return test_ok; |
317 | 1 | } |
318 | | |
319 | 1 | test_result test_markov_leaf_count_random(void) { |
320 | 1 | passgen_random rand; |
321 | 1 | passgen_random_open_xorshift(&rand, SEED); |
322 | 1 | passgen_markov_leaf *leaf = passgen_markov_leaf_new(0); |
323 | 1 | |
324 | 1 | /// FIXME: if you 10x the count, it breaks. |
325 | 1.00k | for(size_t count = 0; count < 1000; count++1.00k ) { |
326 | 1.00k | uint32_t codepoint = passgen_random_u32(&rand); |
327 | 1.00k | uint32_t before = passgen_markov_leaf_count(leaf, codepoint); |
328 | 1.00k | assert_eq(before, 0); |
329 | 1.00k | } |
330 | 1 | |
331 | 1 | passgen_markov_leaf_free(leaf); |
332 | 1 | passgen_random_close(&rand); |
333 | 1 | |
334 | 1 | return test_ok; |
335 | 1 | } |
336 | | |
337 | 1 | test_result test_markov_leaf_insert_random(void) { |
338 | 1 | passgen_random rand; |
339 | 1 | passgen_random_open_xorshift(&rand, SEED); |
340 | 1 | passgen_markov_leaf *leaf = passgen_markov_leaf_new(0); |
341 | 1 | |
342 | 10.0k | for(size_t count = 0; count < 10000; count++10.0k ) { |
343 | 10.0k | uint32_t codepoint = passgen_random_u32(&rand); |
344 | 10.0k | uint32_t weight = passgen_random_u16(&rand); |
345 | 10.0k | uint32_t before = passgen_markov_leaf_count(leaf, codepoint); |
346 | 10.0k | leaf = passgen_markov_leaf_insert(leaf, codepoint, weight); |
347 | 10.0k | uint32_t after = passgen_markov_leaf_count(leaf, codepoint); |
348 | 10.0k | assert_eq(after - before, weight); |
349 | 10.0k | } |
350 | 1 | |
351 | 1 | passgen_markov_leaf_free(leaf); |
352 | 1 | passgen_random_close(&rand); |
353 | 1 | |
354 | 1 | return test_ok; |
355 | 1 | } |
356 | | |
357 | 1 | test_result test_markov_leaf_insert_sequential(void) { |
358 | 1 | passgen_random rand; |
359 | 1 | passgen_random_open_xorshift(&rand, SEED); |
360 | 1 | passgen_markov_leaf *leaf = passgen_markov_leaf_new(0); |
361 | 1 | |
362 | 100k | for(size_t count = 0; count < 100000; count++100k ) { |
363 | 100k | uint32_t codepoint = count; |
364 | 100k | uint32_t weight = passgen_random_u16(&rand); |
365 | 100k | uint32_t before = passgen_markov_leaf_count(leaf, codepoint); |
366 | 100k | leaf = passgen_markov_leaf_insert(leaf, codepoint, weight); |
367 | 100k | uint32_t after = passgen_markov_leaf_count(leaf, codepoint); |
368 | 100k | assert_eq(after - before, weight); |
369 | 100k | } |
370 | 1 | |
371 | 1 | passgen_markov_leaf_free(leaf); |
372 | 1 | passgen_random_close(&rand); |
373 | 1 | |
374 | 1 | return test_ok; |
375 | 1 | } |
376 | | |
377 | 1 | test_result test_markov_generate(void) { |
378 | 1 | passgen_random *rand = passgen_random_new_xorshift(SEED); |
379 | 1 | // passgen_random_open_xorshift(&rand, SEED); |
380 | 1 | |
381 | 1 | passgen_markov markov; |
382 | 1 | passgen_markov_init(&markov, 2); |
383 | 1 | |
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 | 1 | &markov, |
388 | 1 | &(const uint32_t[]){'c', 'd', 'e', 'f'}[0], |
389 | 1 | 4, |
390 | 1 | 1); |
391 | 1 | |
392 | 1 | /* |
393 | 1 | uint32_t next, word[32]; |
394 | 1 | memset(word, 0, sizeof(word)); |
395 | 1 | |
396 | 1 | word[2] = passgen_markov_generate(&markov, &word[0], rand); |
397 | 1 | assert(word[2] == 'c'); |
398 | 1 | word[3] = passgen_markov_generate(&markov, &word[1], rand); |
399 | 1 | assert(word[3] == 'd'); |
400 | 1 | word[4] = passgen_markov_generate(&markov, &word[2], rand); |
401 | 1 | assert(word[4] == 'e'); |
402 | 1 | word[5] = passgen_markov_generate(&markov, &word[3], rand); |
403 | 1 | assert(word[5] == 'f'); |
404 | 1 | word[6] = passgen_markov_generate(&markov, &word[4], rand); |
405 | 1 | assert(word[6] == 0); |
406 | 1 | |
407 | 1 | word[2] = passgen_markov_generate(&markov, &word[0], rand); |
408 | 1 | assert(word[2] == 'b'); |
409 | 1 | word[3] = passgen_markov_generate(&markov, &word[1], rand); |
410 | 1 | assert(word[3] == 0); |
411 | 1 | */ |
412 | 1 | |
413 | 1 | passgen_markov_free(&markov); |
414 | 1 | passgen_random_free(rand); |
415 | 1 | |
416 | 1 | return test_ok; |
417 | 1 | } |