Line data Source code
1 : #include "passgen/generate.h"
2 :
3 : #include "passgen/assert.h"
4 : #include "passgen/container/hashmap.h"
5 : #include "passgen/container/stack.h"
6 : #include "passgen/markov.h"
7 : #include "passgen/pattern/group.h"
8 : #include "passgen/pattern/literal.h"
9 : #include "passgen/pattern/pattern.h"
10 : #include "passgen/pattern/range.h"
11 : #include "passgen/pattern/repeat.h"
12 : #include "passgen/pattern/segment.h"
13 : #include "passgen/pattern/segment_item.h"
14 : #include "passgen/pattern/set.h"
15 : #include "passgen/pattern/special.h"
16 : #include "passgen/util/utf8.h"
17 : #include "passgen/wordlist.h"
18 : #include "try.h"
19 :
20 : #include <string.h>
21 :
22 : typedef struct {
23 : passgen_env *env;
24 : size_t depth;
25 : double *entropy;
26 : void *data;
27 : passgen_generate_cb *func;
28 : } passgen_generate_context;
29 :
30 : // Emit a character
31 144 : static inline int emit(passgen_generate_context *context, uint32_t codepoint) {
32 144 : return context->func(context->data, codepoint);
33 : }
34 :
35 : // Recurse
36 92 : static inline int descend(passgen_generate_context *context) {
37 92 : if(!context->depth) {
38 3 : return 1;
39 : }
40 :
41 89 : context->depth -= 1;
42 89 : return 0;
43 : }
44 :
45 86 : static inline void ascend(passgen_generate_context *context) {
46 86 : context->depth += 1;
47 86 : }
48 :
49 : static size_t passgen_generate_repeat(
50 : passgen_generate_context *context,
51 : const passgen_pattern_repeat *repeat);
52 :
53 : static int passgen_generate_set(
54 : passgen_generate_context *context,
55 : const passgen_pattern_set *set);
56 :
57 : static int passgen_generate_literal(
58 : passgen_generate_context *context,
59 : const passgen_pattern_literal *character);
60 :
61 : static int passgen_generate_special_markov(
62 : passgen_generate_context *context,
63 : const passgen_pattern_special *special);
64 :
65 : static int passgen_generate_special_wordlist(
66 : passgen_generate_context *context,
67 : const passgen_pattern_special *special);
68 :
69 : static int passgen_generate_special(
70 : passgen_generate_context *context,
71 : const passgen_pattern_special *special);
72 :
73 : static int passgen_generate_group(
74 : passgen_generate_context *context,
75 : const passgen_pattern_group *group);
76 :
77 : static int passgen_generate_item(
78 : passgen_generate_context *context,
79 : const passgen_pattern_item *item);
80 :
81 : static int passgen_generate_segment(
82 : passgen_generate_context *context,
83 : const passgen_pattern_segment *segment);
84 :
85 : struct fillpos {
86 : uint32_t *buffer;
87 : size_t cur;
88 : size_t len;
89 : };
90 :
91 : struct fillpos_utf8 {
92 : uint8_t *buffer;
93 : size_t cur;
94 : size_t len;
95 : };
96 :
97 47 : static int passgen_generate_write_buffer(void *data, uint32_t codepoint) {
98 47 : struct fillpos *fillpos = data;
99 :
100 47 : if(fillpos->cur == fillpos->len) {
101 0 : return -1;
102 : }
103 :
104 47 : fillpos->buffer[fillpos->cur] = codepoint;
105 47 : fillpos->cur++;
106 :
107 47 : return 0;
108 : }
109 :
110 91 : static int passgen_generate_write_buffer_utf8(void *data, uint32_t codepoint) {
111 91 : struct fillpos_utf8 *fillpos = data;
112 :
113 91 : if(fillpos->cur == fillpos->len) {
114 0 : return -1;
115 : }
116 :
117 91 : if((fillpos->cur + 4) <= fillpos->len) {
118 91 : int bytes = passgen_utf8_encode_codepoint(
119 91 : (uint8_t *) &fillpos->buffer[fillpos->cur],
120 : codepoint);
121 :
122 91 : if(bytes < 0) {
123 : // error happened during encoding.
124 0 : return -1;
125 : }
126 :
127 91 : fillpos->cur += bytes;
128 : } else {
129 : char buffer[4];
130 : int bytes =
131 0 : passgen_utf8_encode_codepoint((uint8_t *) &buffer[0], codepoint);
132 :
133 0 : if(bytes < 0) {
134 : // error happened during encoding.
135 0 : return -1;
136 : }
137 :
138 0 : if((size_t)bytes <= (fillpos->len - fillpos->cur)) {
139 0 : memcpy(&fillpos->buffer[fillpos->cur], &buffer[0], bytes);
140 0 : fillpos->cur += bytes;
141 : } else {
142 : // error: encoded doesn't fit in buffer.
143 0 : return -1;
144 : }
145 : }
146 :
147 91 : return 0;
148 : }
149 :
150 : /// Write JSON-escaped UTF-8 to buffer.
151 : static int
152 0 : passgen_generate_write_buffer_json_utf8(void *data, uint32_t codepoint) {
153 0 : struct fillpos_utf8 *fillpos = data;
154 :
155 0 : if(fillpos->cur == fillpos->len) {
156 0 : return -1;
157 : }
158 :
159 0 : unsigned char buffer[4] = {'\\', 0};
160 0 : size_t bytes = 2;
161 0 : switch(codepoint) {
162 0 : case '"':
163 0 : buffer[1] = '"';
164 0 : break;
165 0 : case '\\':
166 0 : buffer[1] = '\\';
167 0 : break;
168 0 : case '\b':
169 0 : buffer[1] = 'b';
170 0 : break;
171 0 : case '\f':
172 0 : buffer[1] = 'f';
173 0 : break;
174 0 : case '\r':
175 0 : buffer[1] = 'r';
176 0 : break;
177 0 : case '\n':
178 0 : buffer[1] = 'n';
179 0 : break;
180 0 : case '\t':
181 0 : buffer[1] = 't';
182 0 : break;
183 0 : default:
184 0 : bytes = passgen_utf8_encode_codepoint(
185 : (uint8_t *) &buffer[0],
186 : codepoint);
187 : }
188 :
189 : // check that no error happened.
190 0 : if(!bytes) {
191 0 : return -1;
192 : }
193 :
194 : // make sure it fits.
195 0 : if(bytes <= (fillpos->len - fillpos->cur)) {
196 0 : memcpy(&fillpos->buffer[fillpos->cur], &buffer[0], bytes);
197 0 : fillpos->cur += bytes;
198 : } else {
199 0 : return -1;
200 : }
201 :
202 0 : return 0;
203 : }
204 :
205 28 : size_t passgen_generate_fill_unicode(
206 : const passgen_pattern *pattern,
207 : passgen_env *env,
208 : double *entropy,
209 : uint32_t *buffer,
210 : size_t len) {
211 28 : struct fillpos fillpos = {
212 : .buffer = buffer,
213 : .len = len,
214 : .cur = 0,
215 : };
216 :
217 28 : int ret = passgen_generate(
218 : pattern,
219 : env,
220 : entropy,
221 : &fillpos,
222 : passgen_generate_write_buffer);
223 :
224 28 : if(ret != 0) {
225 0 : return 0;
226 : }
227 :
228 28 : return fillpos.cur;
229 : }
230 :
231 31 : size_t passgen_generate_fill_utf8(
232 : const passgen_pattern *pattern,
233 : passgen_env *env,
234 : double *entropy,
235 : uint8_t *buffer,
236 : size_t len) {
237 31 : struct fillpos_utf8 fillpos = {
238 : .buffer = buffer,
239 : .len = len,
240 : .cur = 0,
241 : };
242 :
243 31 : int ret = passgen_generate(
244 : pattern,
245 : env,
246 : entropy,
247 : &fillpos,
248 : passgen_generate_write_buffer_utf8);
249 :
250 31 : if(ret != 0) {
251 0 : return 0;
252 : }
253 :
254 31 : return fillpos.cur;
255 : }
256 :
257 0 : size_t passgen_generate_fill_json_utf8(
258 : const passgen_pattern *pattern,
259 : passgen_env *env,
260 : double *entropy,
261 : uint8_t *buffer,
262 : size_t len) {
263 0 : struct fillpos_utf8 fillpos = {
264 : .buffer = buffer,
265 : .len = len,
266 : .cur = 0,
267 : };
268 :
269 0 : int ret = passgen_generate(
270 : pattern,
271 : env,
272 : entropy,
273 : &fillpos,
274 : passgen_generate_write_buffer_json_utf8);
275 :
276 0 : if(ret != 0) {
277 0 : return 0;
278 : }
279 :
280 0 : return fillpos.cur;
281 : }
282 :
283 87 : static size_t passgen_generate_repeat(
284 : passgen_generate_context *context,
285 : const passgen_pattern_repeat *repeat) {
286 87 : size_t difference = repeat->max - repeat->min;
287 :
288 : // if there is no difference to pick, just return here
289 87 : if(0 == difference) {
290 81 : return repeat->min;
291 : }
292 :
293 : // get random number to choose from the range
294 : size_t choice =
295 6 : passgen_random_u64_max(context->env->random, difference + 1);
296 :
297 : // keep track of entropy
298 6 : if(context->entropy) {
299 4 : *context->entropy *= difference + 1;
300 : }
301 :
302 6 : return repeat->min + choice;
303 : }
304 :
305 26 : static int passgen_generate_set(
306 : passgen_generate_context *context,
307 : const passgen_pattern_set *set) {
308 : // if this set is empty, we're done.
309 26 : if(set->items.len == 0) {
310 0 : return 0;
311 : }
312 :
313 : // compute number of possible codepoints
314 26 : size_t possible = set->choices_list[set->items.len - 1];
315 26 : passgen_assert(possible != 0);
316 26 : size_t choice = passgen_random_u64_max(context->env->random, possible);
317 :
318 : // keep track of entropy
319 26 : if(context->entropy) {
320 14 : *context->entropy *= possible;
321 : }
322 :
323 : // locate choice in list of choices.
324 : // TODO: binary search.
325 : size_t num;
326 41 : for(num = 0; num < set->items.len; num++) {
327 41 : if(choice < set->choices_list[num]) {
328 26 : break;
329 : }
330 : }
331 :
332 26 : passgen_assert(num != set->items.len);
333 :
334 : /* adjust choice to be relative offset */
335 26 : if(num) {
336 9 : choice -= set->choices_list[num - 1];
337 : }
338 :
339 26 : passgen_pattern_range *range = passgen_stack_get(&set->items, num);
340 :
341 26 : return emit(context, range->start + choice);
342 : }
343 :
344 52 : static int passgen_generate_literal(
345 : passgen_generate_context *context,
346 : const passgen_pattern_literal *literal) {
347 52 : passgen_assert(literal->count > 0);
348 52 : passgen_assert(literal->count < 8);
349 :
350 170 : for(size_t i = 0; i < literal->count; i++) {
351 118 : try(emit(context, literal->codepoints[i]));
352 : }
353 :
354 52 : return 0;
355 : }
356 :
357 0 : static int passgen_generate_special_markov(
358 : passgen_generate_context *context,
359 : const passgen_pattern_special *special) {
360 : passgen_hashmap_entry *entry =
361 0 : passgen_hashmap_lookup(&context->env->wordlists, special->parameters);
362 0 : if(!entry) {
363 0 : return -1;
364 : }
365 0 : passgen_wordlist *wordlist = entry->value;
366 0 : if(!wordlist->parsed) {
367 0 : passgen_wordlist_parse(wordlist);
368 : }
369 0 : if(!wordlist->parsed_markov) {
370 0 : passgen_wordlist_parse_markov(wordlist);
371 : }
372 0 : passgen_markov *markov = &wordlist->markov;
373 : uint32_t word[128];
374 0 : size_t pos = markov->level;
375 0 : memset(word, 0, pos * sizeof(uint32_t));
376 0 : double *entropy = context->entropy ? &*context->entropy : NULL;
377 : do {
378 0 : word[pos] = passgen_markov_generate(
379 : markov,
380 0 : &word[pos - markov->level],
381 0 : context->env->random,
382 : entropy);
383 0 : pos++;
384 0 : } while(word[pos - 1]);
385 :
386 0 : pos = markov->level;
387 0 : while(word[pos]) {
388 0 : try(emit(context, word[pos]));
389 0 : pos++;
390 : }
391 :
392 0 : return 0;
393 : }
394 :
395 0 : static int passgen_generate_special_wordlist(
396 : passgen_generate_context *context,
397 : const passgen_pattern_special *special) {
398 : passgen_hashmap_entry *entry =
399 0 : passgen_hashmap_lookup(&context->env->wordlists, special->parameters);
400 0 : if(!entry) {
401 0 : return -1;
402 : }
403 0 : passgen_wordlist *wordlist = entry->value;
404 0 : if(!wordlist->parsed) {
405 0 : passgen_wordlist_parse(wordlist);
406 : }
407 :
408 : // pick word at random
409 0 : const char *word = passgen_wordlist_random(wordlist, context->env->random);
410 :
411 : // UTF8-decode word and write codepoints
412 : // TODO: handle longer words
413 0 : size_t word_len = strlen(word);
414 0 : const char **word_pos = &word;
415 : uint32_t codepoints[128];
416 0 : uint32_t *codepoints_pos = &codepoints[0];
417 0 : try(passgen_utf8_decode(&codepoints_pos, 128, NULL, (const uint8_t **) word_pos, word_len));
418 0 : for(int i = 0; &codepoints[i] < codepoints_pos; i++) {
419 0 : try(emit(context, codepoints[i]));
420 : }
421 :
422 0 : if(context->entropy) {
423 0 : *context->entropy *= passgen_wordlist_count(wordlist);
424 : }
425 :
426 0 : return 0;
427 : }
428 :
429 0 : static int passgen_generate_special_preset(
430 : passgen_generate_context *context,
431 : const passgen_pattern_special *special) {
432 : (void) context;
433 : (void) special;
434 : // TODO: implement
435 0 : return 0;
436 : }
437 :
438 0 : static int passgen_generate_special(
439 : passgen_generate_context *context,
440 : const passgen_pattern_special *special) {
441 0 : switch(special->kind) {
442 0 : case PASSGEN_PATTERN_SPECIAL_MARKOV:
443 0 : return passgen_generate_special_markov(context, special);
444 0 : case PASSGEN_PATTERN_SPECIAL_WORDLIST:
445 0 : return passgen_generate_special_wordlist(context, special);
446 0 : case PASSGEN_PATTERN_SPECIAL_PRESET:
447 0 : return passgen_generate_special_preset(context, special);
448 0 : default:
449 0 : return 1;
450 : }
451 : return 0;
452 : }
453 :
454 88 : static int passgen_generate_item(
455 : passgen_generate_context *context,
456 : const passgen_pattern_item *item) {
457 : // if it is a maybe (has a question mark following it), decide first if we
458 : // want to emit it or not.
459 88 : if(item->maybe) {
460 6 : if(!passgen_random_bool(context->env->random)) {
461 1 : return 0;
462 : }
463 : }
464 :
465 : // compute random number of repetitions
466 87 : size_t reps = passgen_generate_repeat(context, &item->repeat);
467 :
468 190 : for(size_t i = 0; i < reps; i++) {
469 106 : switch(item->kind) {
470 26 : case PASSGEN_PATTERN_SET:
471 26 : try(passgen_generate_set(context, &item->data.set));
472 26 : break;
473 52 : case PASSGEN_PATTERN_LITERAL:
474 52 : try(passgen_generate_literal(context, &item->data.literal));
475 52 : break;
476 0 : case PASSGEN_PATTERN_SPECIAL:
477 0 : try(passgen_generate_special(context, &item->data.special));
478 0 : break;
479 28 : case PASSGEN_PATTERN_GROUP:
480 28 : try(passgen_generate_group(context, &item->data.group));
481 25 : break;
482 0 : default:
483 0 : passgen_assert(false);
484 0 : break;
485 : }
486 : }
487 :
488 : // unreachable
489 84 : return 0;
490 : }
491 :
492 89 : static int passgen_generate_segment(
493 : passgen_generate_context *context,
494 : const passgen_pattern_segment *segment) {
495 174 : for(size_t i = 0; i < segment->items.len; i++) {
496 88 : passgen_pattern_item *item = passgen_stack_get(&segment->items, i);
497 :
498 88 : try(passgen_generate_item(context, item));
499 : }
500 :
501 86 : return 0;
502 : }
503 :
504 92 : static int passgen_generate_group(
505 : passgen_generate_context *context,
506 : const passgen_pattern_group *group) {
507 : // descend in depth
508 92 : try(descend(context));
509 :
510 89 : if(group->multiplier_sum == 0) {
511 0 : return 1;
512 : }
513 :
514 : // choose random segment from segments
515 : size_t choice =
516 89 : passgen_random_u64_max(context->env->random, group->multiplier_sum);
517 89 : size_t segment_index = 0;
518 : passgen_pattern_segment *segment =
519 89 : passgen_stack_get(&group->segments, segment_index);
520 :
521 104 : while(choice >= segment->multiplier) {
522 15 : choice -= segment->multiplier;
523 15 : segment_index += 1;
524 15 : segment = passgen_stack_get(&group->segments, segment_index);
525 : }
526 :
527 : // keep track of entropy
528 89 : if(context->entropy) {
529 47 : *context->entropy *= group->multiplier_sum;
530 47 : *context->entropy /= segment->multiplier;
531 : }
532 :
533 89 : try(passgen_generate_segment(context, segment));
534 :
535 86 : ascend(context);
536 :
537 86 : return 0;
538 : }
539 :
540 64 : int passgen_generate(
541 : const passgen_pattern *pattern,
542 : passgen_env *env,
543 : double *entropy,
544 : void *data,
545 : passgen_generate_cb *func) {
546 : // when entropy collection is request (by passing a non-NULL pointer),
547 : // initialize it.
548 64 : if(entropy) {
549 31 : *entropy = 1.0;
550 : }
551 :
552 64 : passgen_generate_context context = {
553 : .env = env,
554 64 : .depth = env->depth_limit,
555 : .func = func,
556 : .data = data,
557 : .entropy = entropy,
558 : };
559 :
560 64 : return passgen_generate_group(&context, &pattern->group);
561 : }
|
