Coverage Report

Created: 2024-04-12 06:05

/builds/xfbs/passgen/src/tests/random.c
Line
Count
Source
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
1.05k
    do {                                                         \
14
1.05k
        size_t coverage_len = ((size_t) max) / (collate) + 1ULL; \
15
1.05k
        uint8_t *coverage = calloc((coverage_len + 7) / 8, 1);   \
16
1.05k
        bool full_coverage = false;                              \
17
21.3k
        while(!full_coverage) {                                  \
18
5.21M
            for(size_t i = 0; i < 256; 
i++5.19M
) { \
19
5.19M
                size_t pos = function / (collate);               \
20
5.19M
                coverage[pos / 8] |= 1 << (pos % 8);             \
21
5.19M
            }                                                    \
22
20.2k
            full_coverage = true;                                \
23
67.3M
            for(size_t i = 0; i <= (max / (collate)); 
i++67.2M
) { \
24
67.3M
                if(!(coverage[i / 8] & (1 << (i % 8)))) {        \
25
19.2k
                    full_coverage = false;                       \
26
19.2k
                    break;                                       \
27
19.2k
                }                                                \
28
67.3M
            }                                                    \
29
20.2k
        }                                                        \
30
1.05k
        free(coverage);                                          \
31
1.05k
    } while(false)
32
33
2
double standard_deviation(size_t count, uint32_t *elements) {
34
2
    (void) count;
35
2
    (void) elements;
36
2
    // TODO: determine deviation
37
2
    return 0;
38
2
}
39
40
/// Tests that a given function has an even distribution
41
#define TEST_DISTRIBUTION(max, bucket_num, target, function)   \
42
2
    uint32_t *buckets = calloc(bucket_num, sizeof(uint32_t));  \
43
1.89M
    while(true) {                                              \
44
1.89M
        size_t bucket = function / ((max) / (bucket_num) + 1); \
45
1.89M
        buckets[bucket] += 1;                                  \
46
1.89M
        if(buckets[bucket] == target) {                        \
47
2
            break;                                             \
48
2
        }                                                      \
49
1.89M
    }                                                          \
50
2
    assert(standard_deviation(bucket_num, buckets) < 10);      \
51
2
    free(buckets)
52
53
1
test_result test_random_u8(void) {
54
1
    passgen_random random;
55
1
    assert(passgen_random_open(&random, NULL));
56
1
57
1
    TEST_COVERAGE(UINT8_MAX, 1, passgen_random_u8(&random));
58
1
59
1
    passgen_random_close(&random);
60
1
61
1
    return test_ok;
62
1
}
63
64
1
test_result test_random_u8_max(void) {
65
1
    passgen_random random;
66
1
    assert(passgen_random_open(&random, NULL));
67
1
68
255
    for(size_t max = 1; max < UINT8_MAX; 
max++254
) {
69
254
        TEST_COVERAGE(max - 1, 1, passgen_random_u8_max(&random, max));
70
254
    }
71
1
72
1
    passgen_random_close(&random);
73
1
74
1
    return test_ok;
75
1
}
76
77
1
test_result test_random_u16(void) {
78
1
    passgen_random random;
79
1
    assert(passgen_random_open(&random, NULL));
80
1
81
1
    TEST_COVERAGE(UINT16_MAX, 1, passgen_random_u16(&random));
82
1
83
1
    passgen_random_close(&random);
84
1
85
1
    return test_ok;
86
1
}
87
88
1
test_result test_random_u16_max(void) {
89
1
    passgen_random random;
90
1
    assert(passgen_random_open(&random, NULL));
91
1
92
255
    for(size_t max = 1; max < UINT8_MAX; 
max++254
) {
93
254
        TEST_COVERAGE(max - 1, 1, passgen_random_u16_max(&random, max));
94
254
    }
95
1
96
12
    for(size_t max = 1; max < UINT16_MAX; 
max *= 311
) {
97
11
        TEST_COVERAGE(max - 1, 1, passgen_random_u16_max(&random, max));
98
11
    }
99
1
100
1
    passgen_random_close(&random);
101
1
102
1
    return test_ok;
103
1
}
104
105
1
test_result test_random_u32(void) {
106
1
    passgen_random random;
107
1
    assert(passgen_random_open(&random, NULL));
108
1
109
1
    TEST_COVERAGE(UINT32_MAX, 1 << 16, passgen_random_u32(&random));
110
1
    TEST_DISTRIBUTION(
111
1
        UINT32_MAX,
112
1
        1 << 10,
113
1
        1 << 10,
114
1
        passgen_random_u32(&random));
115
1
116
1
    passgen_random_close(&random);
117
1
118
1
    return test_ok;
119
1
}
120
121
1
test_result test_random_u32_max(void) {
122
1
    passgen_random random;
123
1
    assert(passgen_random_open(&random, NULL));
124
1
125
255
    for(size_t max = 1; max < UINT8_MAX; 
max++254
) {
126
254
        TEST_COVERAGE(max - 1, 1, passgen_random_u32_max(&random, max));
127
254
    }
128
1
129
12
    for(size_t max = 1; max < UINT16_MAX; 
max *= 311
) {
130
11
        TEST_COVERAGE(max - 1, 1, passgen_random_u32_max(&random, max));
131
11
    }
132
1
133
1
    passgen_random_close(&random);
134
1
135
1
    return test_ok;
136
1
}
137
138
1
test_result test_random_u64(void) {
139
1
    passgen_random random;
140
1
    assert(passgen_random_open(&random, NULL));
141
1
142
1
    // FIXME
143
1
    // TEST_COVERAGE(UINT64_MAX, 1ULL << 48, 1024, passgen_random_u32(&random));
144
1
    TEST_DISTRIBUTION(
145
1
        UINT64_MAX,
146
1
        1 << 10,
147
1
        1 << 10,
148
1
        passgen_random_u64(&random));
149
1
150
1
    passgen_random_close(&random);
151
1
152
1
    return test_ok;
153
1
}
154
155
1
test_result test_random_u64_max(void) {
156
1
    passgen_random random;
157
1
    assert(passgen_random_open(&random, NULL));
158
1
159
255
    for(size_t max = 1; max < UINT8_MAX; 
max++254
) {
160
254
        TEST_COVERAGE(max - 1, 1, passgen_random_u64_max(&random, max));
161
254
    }
162
1
163
12
    for(size_t max = 1; max < UINT16_MAX; 
max *= 311
) {
164
11
        TEST_COVERAGE(max - 1, 1, passgen_random_u64_max(&random, max));
165
11
    }
166
1
167
1.00M
    for(size_t i = 1; i < 1000000; 
i++999k
) {
168
999k
        uint32_t max = passgen_random_u64(&random);
169
999k
170
999k
        assert(passgen_random_u64_max(&random, max) < max);
171
999k
    }
172
1
173
1
    passgen_random_close(&random);
174
1
175
1
    return test_ok;
176
1
}
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
1
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
1
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
1
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
1
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
1
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
1
228
1
    return test_ok;
229
1
}
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
1
244
1
    return test_ok;
245
1
}
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
1
258
1
    return test_ok;
259
1
}
260
261
1
test_result test_random_new_path(void) {
262
1
    passgen_random *random;
263
1
    random = passgen_random_new_path("/dev/nonexistent");
264
1
    assert(!random);
265
1
266
1
    // 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
1
276
1
    return test_ok;
277
1
}
278
279
1
test_result test_random_open(void) {
280
1
    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
1
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
1
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
1
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
1
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
1
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
1
312
1
    return test_ok;
313
1
}
314
315
1
test_result test_random_open_path(void) {
316
1
    passgen_random random;
317
1
    assert(!passgen_random_open_path(&random, "/dev/nonexistent"));
318
1
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
1
328
1
    return test_ok;
329
1
}
330
331
1
test_result test_random_read(void) {
332
1
    passgen_random random;
333
1
    assert(passgen_random_open_xorshift(&random, XORSHIFT_SEED));
334
1
335
1
    uint8_t data[2000] = {0};
336
1
337
1
    // 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
1
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
1
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
1
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
1
369
1
    // test wraparound.
370
1.00k
    while(random.pos != (sizeof(random.buffer) - 1)) {
371
1.00k
        passgen_random_read(&random, &data[0], 1);
372
1.00k
    }
373
1
    passgen_random_read(&random, &data[0], 1);
374
1
    assert(random.pos == 0);
375
1
376
1.02k
    while(random.pos != (sizeof(random.buffer) - 1)) {
377
1.02k
        passgen_random_read(&random, &data[0], 1);
378
1.02k
    }
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
1
384
1
    // test reading larger.
385
1
    passgen_random_read(&random, &data[0], sizeof(random.buffer) + 1);
386
1
    assert(random.pos == 2);
387
1
388
1
    passgen_random_close(&random);
389
1
390
1
    return test_ok;
391
1
}
392
393
1
test_result test_random_xorshift(void) {
394
1
    passgen_random random;
395
1
396
1
    // 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
1
404
1
    // 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
1
412
1
    return test_ok;
413
1
}
414
415
#undef XORSHIFT_SEED