BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file substring_test.c
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29  
30 #include <stdlib.h>
31 #include <string.h>
32 #include <stdio.h>
33 #include <time.h>
34  
35 #include <misc/substring.h>
36 #include <misc/debug.h>
37 #include <misc/balloc.h>
38 #include <misc/print_macros.h>
39  
40 static int find_substring_slow (const char *str, size_t str_len, const char *sub, size_t sub_len, size_t *out_pos)
41 {
42 ASSERT(sub_len > 0)
43  
44 if (str_len < sub_len) {
45 return 0;
46 }
47  
48 for (size_t i = 0; i <= str_len - sub_len; i++) {
49 if (!memcmp(str + i, sub, sub_len)) {
50 *out_pos = i;
51 return 1;
52 }
53 }
54  
55 return 0;
56 }
57  
58 static void print_data (const char *str, size_t str_len)
59 {
60 while (str_len > 0) {
61 printf("%02"PRIx8" ", (uint8_t)(*str));
62 str++;
63 str_len--;
64 }
65 printf("\n");
66 }
67  
68 static void print_table (const size_t *table, size_t len)
69 {
70 for (size_t i = 1; i < len; i++) {
71 printf("%zu ", table[i]);
72 }
73 printf("\n");
74 }
75  
76 static void test_tables (int len, int count)
77 {
78 ASSERT(len > 0)
79 ASSERT(count >= 0)
80  
81 char *word = (char *)BAllocSize(bsize_fromint(len));
82 ASSERT_FORCE(word)
83  
84 size_t *table = (size_t *)BAllocSize(bsize_mul(bsize_fromint(len), bsize_fromsize(sizeof(table[0]))));
85 ASSERT_FORCE(table)
86  
87 for (int i = 0; i < count; i++) {
88 for (int j = 0; j < len; j++) {
89 word[j] = rand() % 2;
90 }
91  
92 build_substring_backtrack_table(MemRef_Make(word, len), table);
93  
94 for (int j = 1; j < len; j++) {
95 for (int k = j - 1; k >= 0; k--) {
96 if (!memcmp(word + j - k, word, k)) {
97 ASSERT_FORCE(table[j] == k)
98 break;
99 }
100 }
101 }
102 }
103  
104 BFree(table);
105 BFree(word);
106 }
107  
108 static void test_substring (int word_len, int text_len, int word_count, int text_count)
109 {
110 assert(word_len > 0);
111 assert(text_len >= 0);
112 assert(word_count >= 0);
113 assert(text_count >= 0);
114  
115 char *word = (char *)BAllocSize(bsize_fromint(word_len));
116 ASSERT_FORCE(word)
117  
118 size_t *table = (size_t *)BAllocSize(bsize_mul(bsize_fromint(word_len), bsize_fromsize(sizeof(table[0]))));
119 ASSERT_FORCE(table)
120  
121 char *text = (char *)BAllocSize(bsize_fromint(text_len));
122 ASSERT_FORCE(text)
123  
124 for (int i = 0; i < word_count; i++) {
125 for (int j = 0; j < word_len; j++) {
126 word[j] = rand() % 2;
127 }
128  
129 build_substring_backtrack_table(MemRef_Make(word, word_len), table);
130  
131 for (int j = 0; j < text_count; j++) {
132 for (int k = 0; k < text_len; k++) {
133 text[k] = rand() % 2;
134 }
135  
136 size_t pos = 36; // to remove warning
137 int res = find_substring(MemRef_Make(text, text_len), MemRef_Make(word, word_len), table, &pos);
138  
139 size_t spos = 59; // to remove warning
140 int sres = find_substring_slow(text, text_len, word, word_len, &spos);
141  
142 ASSERT_FORCE(res == sres)
143 if (res) {
144 ASSERT_FORCE(pos == spos)
145 }
146 }
147 }
148  
149 BFree(text);
150 BFree(table);
151 BFree(word);
152 }
153  
154 int main (int argc, char *argv[])
155 {
156 if (argc != 7) {
157 printf("Usage: %s <tables length> <tables count> <word len> <text len> <word count> <text count>\n", (argc == 0 ? "" : argv[0]));
158 return 1;
159 }
160  
161 int tables_len = atoi(argv[1]);
162 int tables_count = atoi(argv[2]);
163 int word_len = atoi(argv[3]);
164 int text_len = atoi(argv[4]);
165 int word_count = atoi(argv[5]);
166 int text_count = atoi(argv[6]);
167  
168 if (tables_len <= 0 || tables_count < 0 || word_len <= 0 || text_len < 0 || word_count < 0 || text_count < 0) {
169 printf("Bad arguments.\n");
170 return 1;
171 }
172  
173 srand(time(NULL));
174  
175 test_tables(tables_len, tables_count);
176  
177 test_substring(word_len, text_len, word_count, text_count);
178  
179 {
180 char text[] = "aggagaa";
181 char word[] = "aga";
182 size_t table[sizeof(word) - 1];
183 build_substring_backtrack_table(MemRef_MakeCstr(word), table);
184  
185 size_t pos;
186 int res = find_substring(MemRef_MakeCstr(text), MemRef_MakeCstr(word), table, &pos);
187 ASSERT_FORCE(res)
188 ASSERT_FORCE(pos == 3)
189 }
190  
191 {
192 char text[] = "aagagga";
193 char word[] = "aga";
194 size_t table[sizeof(word) - 1];
195 build_substring_backtrack_table_reverse(MemRef_MakeCstr(word), table);
196  
197 size_t pos;
198 int res = find_substring_reverse(MemRef_MakeCstr(text), MemRef_MakeCstr(word), table, &pos);
199 ASSERT_FORCE(res)
200 ASSERT_FORCE(pos == 1)
201 }
202  
203 return 0;
204 }