BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
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 }