BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | #include <stddef.h> |
2 | |||
3 | #include <misc/debug.h> |
||
4 | #include <misc/memref.h> |
||
5 | |||
6 | static void build_substring_backtrack_table (MemRef str, size_t *out_table) |
||
7 | { |
||
8 | ASSERT(str.len > 0) |
||
9 | |||
10 | size_t x = 0; |
||
11 | |||
12 | for (size_t i = 1; i < str.len; i++) { |
||
13 | out_table[i] = x; |
||
14 | while (x > 0 && str.ptr[i] != str.ptr[x]) { |
||
15 | x = out_table[x]; |
||
16 | } |
||
17 | if (str.ptr[i] == str.ptr[x]) { |
||
18 | x++; |
||
19 | } |
||
20 | } |
||
21 | } |
||
22 | |||
23 | static int find_substring (MemRef text, MemRef word, const size_t *table, size_t *out_position) |
||
24 | { |
||
25 | ASSERT(word.len > 0) |
||
26 | |||
27 | size_t x = 0; |
||
28 | |||
29 | for (size_t i = 0; i < text.len; i++) { |
||
30 | while (x > 0 && text.ptr[i] != word.ptr[x]) { |
||
31 | x = table[x]; |
||
32 | } |
||
33 | if (text.ptr[i] == word.ptr[x]) { |
||
34 | if (x + 1 == word.len) { |
||
35 | *out_position = i - x; |
||
36 | return 1; |
||
37 | } |
||
38 | x++; |
||
39 | } |
||
40 | } |
||
41 | |||
42 | return 0; |
||
43 | } |
||
44 | |||
45 | static void build_substring_backtrack_table_reverse (MemRef str, size_t *out_table) |
||
46 | { |
||
47 | ASSERT(str.len > 0) |
||
48 | |||
49 | size_t x = 0; |
||
50 | |||
51 | for (size_t i = 1; i < str.len; i++) { |
||
52 | out_table[i] = x; |
||
53 | while (x > 0 && str.ptr[str.len - 1 - i] != str.ptr[str.len - 1 - x]) { |
||
54 | x = out_table[x]; |
||
55 | } |
||
56 | if (str.ptr[str.len - 1 - i] == str.ptr[str.len - 1 - x]) { |
||
57 | x++; |
||
58 | } |
||
59 | } |
||
60 | } |
||
61 | |||
62 | static int find_substring_reverse (MemRef text, MemRef word, const size_t *table, size_t *out_position) |
||
63 | { |
||
64 | ASSERT(word.len > 0) |
||
65 | |||
66 | size_t x = 0; |
||
67 | |||
68 | for (size_t i = 0; i < text.len; i++) { |
||
69 | while (x > 0 && text.ptr[text.len - 1 - i] != word.ptr[word.len - 1 - x]) { |
||
70 | x = table[x]; |
||
71 | } |
||
72 | if (text.ptr[text.len - 1 - i] == word.ptr[word.len - 1 - x]) { |
||
73 | if (x + 1 == word.len) { |
||
74 | *out_position = (text.len - 1 - i); |
||
75 | return 1; |
||
76 | } |
||
77 | x++; |
||
78 | } |
||
79 | } |
||
80 | |||
81 | return 0; |
||
82 | } |