BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file explode.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 * @section DESCRIPTION
30 *
31 *
32 * Synopsis:
33 * compile_search(string str)
34 *
35 * Description:
36 * Performs calculations to enable efficient string searches for the
37 * given string (builds the KMP table). The string must be non-empty.
38 *
39 *
40 * Synopsis:
41 * explode(string delimiter, string input [, string limit])
42 * compile_search::explode(string input [, string limit])
43 *
44 * Description:
45 * Splits the string 'input' into a list of components. The first component
46 * is the part of 'input' until the first occurence of 'delimiter', if any.
47 * If 'delimiter' was found, the remaining components are defined recursively
48 * via the same procedure, starting with the part of 'input' after the first
49 * substring.
50 * 'delimiter' must be nonempty.
51 * The compile_search variant uses an precompiled delimiter string for better
52 * performance.
53 *
54 * Variables:
55 * list (empty) - the components of 'input', determined based on 'delimiter'
56 */
57  
58 #include <stdlib.h>
59 #include <string.h>
60 #include <limits.h>
61  
62 #include <misc/exparray.h>
63 #include <misc/string_begins_with.h>
64 #include <misc/substring.h>
65 #include <misc/balloc.h>
66  
67 #include <ncd/module_common.h>
68  
69 #include <generated/blog_channel_ncd_explode.h>
70  
71 struct compile_search_instance {
72 NCDModuleInst *i;
73 MemRef str;
74 size_t *table;
75 };
76  
77 struct instance {
78 NCDModuleInst *i;
79 NCDValRef input;
80 struct ExpArray arr;
81 size_t num;
82 };
83  
84 static void compile_search_new (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
85 {
86 struct compile_search_instance *o = vo;
87 o->i = i;
88  
89 NCDValRef str_arg;
90 if (!NCDVal_ListRead(params->args, 1, &str_arg)) {
91 ModuleLog(i, BLOG_ERROR, "wrong arity");
92 goto fail0;
93 }
94 if (!NCDVal_IsString(str_arg)) {
95 ModuleLog(i, BLOG_ERROR, "wrong type");
96 goto fail0;
97 }
98  
99 o->str = NCDVal_StringMemRef(str_arg);
100 if (o->str.len == 0) {
101 ModuleLog(i, BLOG_ERROR, "string must be nonempty");
102 goto fail0;
103 }
104  
105 o->table = BAllocArray(o->str.len, sizeof(o->table[0]));
106 if (!o->table) {
107 ModuleLog(i, BLOG_ERROR, "BAllocArray failed");
108 goto fail0;
109 }
110  
111 build_substring_backtrack_table(o->str, o->table);
112  
113 NCDModuleInst_Backend_Up(i);
114 return;
115  
116 fail0:
117 NCDModuleInst_Backend_DeadError(i);
118 }
119  
120 static void compile_search_die (void *vo)
121 {
122 struct compile_search_instance *o = vo;
123  
124 BFree(o->table);
125  
126 NCDModuleInst_Backend_Dead(o->i);
127 }
128  
129 static void func_new_common (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params, struct compile_search_instance *compiled)
130 {
131 struct instance *o = vo;
132 o->i = i;
133  
134 int arg_start;
135 MemRef del;
136 size_t const *table;
137  
138 if (compiled) {
139 arg_start = 0;
140 del = compiled->str;
141 table = compiled->table;
142 } else {
143 NCDValRef delimiter_arg;
144 if (!NCDVal_ListReadHead(params->args, 1, &delimiter_arg)) {
145 ModuleLog(i, BLOG_ERROR, "missing delimiter argument");
146 goto fail0;
147 }
148 if (!NCDVal_IsString(delimiter_arg)) {
149 ModuleLog(i, BLOG_ERROR, "wrong delimiter type");
150 goto fail0;
151 }
152 arg_start = 1;
153  
154 del = NCDVal_StringMemRef(delimiter_arg);
155 if (del.len == 0) {
156 ModuleLog(i, BLOG_ERROR, "delimiter must be nonempty");
157 goto fail0;
158 }
159  
160 table = BAllocArray(del.len, sizeof(table[0]));
161 if (!table) {
162 ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
163 goto fail0;
164 }
165  
166 build_substring_backtrack_table(del, (size_t *)table);
167 }
168  
169 // read arguments
170 NCDValRef input_arg;
171 NCDValRef limit_arg = NCDVal_NewInvalid();
172 if (!NCDVal_ListReadStart(params->args, arg_start, 1, &input_arg) && !NCDVal_ListReadStart(params->args, arg_start, 2, &input_arg, &limit_arg)) {
173 ModuleLog(i, BLOG_ERROR, "wrong arity");
174 goto fail1;
175 }
176 if (!NCDVal_IsString(input_arg)) {
177 ModuleLog(i, BLOG_ERROR, "wrong type");
178 goto fail1;
179 }
180 o->input = input_arg;
181  
182 size_t limit = SIZE_MAX;
183 if (!NCDVal_IsInvalid(limit_arg)) {
184 uintmax_t n;
185 if (!ncd_read_uintmax(limit_arg, &n) || n == 0) {
186 ModuleLog(i, BLOG_ERROR, "bad limit argument");
187 goto fail1;
188 }
189 n--;
190 limit = (n <= SIZE_MAX ? n : SIZE_MAX);
191 }
192  
193 if (!ExpArray_init(&o->arr, sizeof(MemRef), 8)) {
194 ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
195 goto fail1;
196 }
197 o->num = 0;
198  
199 MemRef data = NCDVal_StringMemRef(input_arg);
200  
201 while (1) {
202 size_t start;
203 int is_end = 0;
204 if (limit == 0 || !find_substring(data, del, table, &start)) {
205 start = data.len;
206 is_end = 1;
207 }
208  
209 if (!ExpArray_resize(&o->arr, o->num + 1)) {
210 ModuleLog(i, BLOG_ERROR, "ExpArray_init failed");
211 goto fail2;
212 }
213  
214 ((MemRef *)o->arr.v)[o->num] = MemRef_SubTo(data, start);
215 o->num++;
216  
217 if (is_end) {
218 break;
219 }
220  
221 data = MemRef_SubFrom(data, start + del.len);
222 limit--;
223 }
224  
225 if (!compiled) {
226 BFree((size_t *)table);
227 }
228  
229 // signal up
230 NCDModuleInst_Backend_Up(i);
231 return;
232  
233 fail2:
234 free(o->arr.v);
235 fail1:
236 if (!compiled) {
237 BFree((size_t *)table);
238 }
239 fail0:
240 NCDModuleInst_Backend_DeadError(i);
241 }
242  
243 static void func_new (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
244 {
245 return func_new_common(vo, i, params, NULL);
246 }
247  
248 static void func_new_compiled (void *vo, NCDModuleInst *i, const struct NCDModuleInst_new_params *params)
249 {
250 struct compile_search_instance *compiled = NCDModuleInst_Backend_GetUser((NCDModuleInst *)params->method_user);
251  
252 return func_new_common(vo, i, params, compiled);
253 }
254  
255 static void func_die (void *vo)
256 {
257 struct instance *o = vo;
258  
259 free(o->arr.v);
260  
261 NCDModuleInst_Backend_Dead(o->i);
262 }
263  
264 static int func_getvar2 (void *vo, NCD_string_id_t name, NCDValMem *mem, NCDValRef *out)
265 {
266 struct instance *o = vo;
267  
268 if (name == NCD_STRING_EMPTY) {
269 *out = NCDVal_NewList(mem, o->num);
270 if (NCDVal_IsInvalid(*out)) {
271 goto fail;
272 }
273 int is_external = NCDVal_IsExternalString(o->input);
274 for (size_t j = 0; j < o->num; j++) {
275 MemRef elem = ((MemRef *)o->arr.v)[j];
276 NCDValRef str;
277 if (is_external) {
278 str = NCDVal_NewExternalString(mem, elem.ptr, elem.len, NCDVal_ExternalStringTarget(o->input));
279 } else {
280 str = NCDVal_NewStringBinMr(mem, elem);
281 }
282 if (NCDVal_IsInvalid(str)) {
283 goto fail;
284 }
285 if (!NCDVal_ListAppend(*out, str)) {
286 goto fail;
287 }
288 }
289 return 1;
290 }
291  
292 return 0;
293  
294 fail:
295 *out = NCDVal_NewInvalid();
296 return 1;
297 }
298  
299 static struct NCDModule modules[] = {
300 {
301 .type = "compile_search",
302 .func_new2 = compile_search_new,
303 .func_die = compile_search_die,
304 .alloc_size = sizeof(struct compile_search_instance)
305 }, {
306 .type = "explode",
307 .func_new2 = func_new,
308 .func_die = func_die,
309 .func_getvar2 = func_getvar2,
310 .alloc_size = sizeof(struct instance)
311 }, {
312 .type = "compile_search::explode",
313 .func_new2 = func_new_compiled,
314 .func_die = func_die,
315 .func_getvar2 = func_getvar2,
316 .alloc_size = sizeof(struct instance)
317 }, {
318 .type = NULL
319 }
320 };
321  
322 const struct NCDModuleGroup ncdmodule_explode = {
323 .modules = modules
324 };