| 1 | #include "tweak.h" |
| 2 | |
| 3 | #include <stdio.h> |
| 4 | #include <stdlib.h> |
| 5 | #include <string.h> |
| 6 | |
| 7 | static DFA build_dfa (char *pattern, int len) |
| 8 | { |
| 9 | int i, j, k, b; |
| 10 | char *tmp = malloc(len); |
| 11 | DFA dfa = malloc(len * sizeof(*dfa)); |
| 12 | |
| 13 | if (!dfa) |
| 14 | return NULL; |
| 15 | if (!tmp) |
| 16 | return NULL; |
| 17 | |
| 18 | memcpy (tmp, pattern, len); |
| 19 | |
| 20 | for (i=len; i-- ;) { |
| 21 | j = i+1; |
| 22 | for (b=0; b<256; b++) { |
| 23 | dfa[i][b] = 0; |
| 24 | if (memchr(pattern, b, len)) { |
| 25 | tmp[j-1] = b; |
| 26 | for (k=1; k<=j; k++) |
| 27 | if (!memcmp(tmp+j-k, pattern, k)) |
| 28 | dfa[i][b] = k; |
| 29 | } |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | return dfa; |
| 34 | } |
| 35 | |
| 36 | Search *build_search(char *pattern, int len) |
| 37 | { |
| 38 | Search *ret = malloc(sizeof(Search)); |
| 39 | char *revpat = malloc(len); |
| 40 | int i; |
| 41 | |
| 42 | ret->len = len; |
| 43 | ret->forward = build_dfa(pattern, len); |
| 44 | for (i = 0; i < len; i++) |
| 45 | revpat[i] = pattern[len-1-i]; |
| 46 | ret->reverse = build_dfa(revpat, len); |
| 47 | |
| 48 | return ret; |
| 49 | } |
| 50 | |
| 51 | void free_search(Search *s) |
| 52 | { |
| 53 | free(s->forward); |
| 54 | free(s->reverse); |
| 55 | free(s); |
| 56 | } |