1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <limits.h>
5 #include <errno.h>
6 #include <assert.h>
7
8 #include "strntol.h"
9 #include "pattern.h"
10 #include "../minmax.h"
11 #include "../oslib/strcasestr.h"
12
13 /**
14 * parse_string() - parses string in double quotes, like "abc"
15 * @beg - string input
16 * @out - output buffer where parsed number should be put
17 * @out_len - length of the output buffer
18 * @filled - pointer where number of bytes successfully
19 * parsed will be put
20 *
21 * Returns the end pointer where parsing has been stopped.
22 * In case of parsing error or lack of bytes in output buffer
23 * NULL will be returned.
24 */
parse_string(const char * beg,char * out,unsigned int out_len,unsigned int * filled)25 static const char *parse_string(const char *beg, char *out,
26 unsigned int out_len,
27 unsigned int *filled)
28 {
29 const char *end;
30
31 if (!out_len)
32 return NULL;
33
34 assert(*beg == '"');
35 beg++;
36 end = strchr(beg, '"');
37 if (!end)
38 return NULL;
39 if (end - beg > out_len)
40 return NULL;
41
42 memcpy(out, beg, end - beg);
43 *filled = end - beg;
44
45 /* Catch up quote */
46 return end + 1;
47 }
48
49 /**
50 * parse_number() - parses numbers
51 * @beg - string input
52 * @out - output buffer where parsed number should be put
53 * @out_len - length of the output buffer
54 * @filled - pointer where number of bytes successfully
55 * parsed will be put
56 *
57 * Supports decimals in the range [INT_MIN, INT_MAX] and
58 * hexidecimals of any size, which should be started with
59 * prefix 0x or 0X.
60 *
61 * Returns the end pointer where parsing has been stopped.
62 * In case of parsing error or lack of bytes in output buffer
63 * NULL will be returned.
64 */
parse_number(const char * beg,char * out,unsigned int out_len,unsigned int * filled)65 static const char *parse_number(const char *beg, char *out,
66 unsigned int out_len,
67 unsigned int *filled)
68 {
69 const char *end;
70 unsigned int val;
71 long lval;
72 int num, i;
73
74 if (!out_len)
75 return NULL;
76
77 num = 0;
78 sscanf(beg, "0%*[xX]%*[0-9a-fA-F]%n", &num);
79 if (num == 0) {
80 /* Here we are trying to parse decimal */
81
82 char *_end;
83
84 /* Looking ahead */
85 _end = strcasestr(beg, "0x");
86 if (_end)
87 num = _end - beg;
88 if (num)
89 lval = strntol(beg, num, &_end, 10);
90 else
91 lval = strtol(beg, &_end, 10);
92 if (beg == _end || lval > INT_MAX || lval < INT_MIN)
93 return NULL;
94 end = _end;
95 i = 0;
96 if (!lval) {
97 num = 0;
98 out[i] = 0x00;
99 i = 1;
100 } else {
101 val = (unsigned int)lval;
102 for (; val && out_len; out_len--, i++, val >>= 8)
103 out[i] = val & 0xff;
104 if (val)
105 return NULL;
106 }
107 } else {
108 assert(num > 2);
109
110 /* Catch up 0x prefix */
111 num -= 2;
112 beg += 2;
113
114 /* Look back, handle this combined string: 0xff0x14 */
115 if (beg[num] && !strncasecmp(&beg[num - 1], "0x", 2))
116 num--;
117
118 end = beg + num;
119
120 for (i = 0; num && out_len;
121 out_len--, i++, num -= 2, beg += 2) {
122 const char *fmt;
123
124 fmt = (num & 1 ? "%1hhx" : "%2hhx");
125 sscanf(beg, fmt, &out[i]);
126 if (num & 1) {
127 num++;
128 beg--;
129 }
130 }
131 if (num)
132 return NULL;
133 }
134
135 *filled = i;
136 return end;
137
138 }
139
140 /**
141 * parse_format() - parses formats, like %o, etc
142 * @in - string input
143 * @out - output buffer where space for format should be reserved
144 * @parsed - number of bytes which were already parsed so far
145 * @out_len - length of the output buffer
146 * @fmt_desc - format descritor array, what we expect to find
147 * @fmt_desc_sz - size of the format descritor array
148 * @fmt - format array, the output
149 * @fmt_sz - size of format array
150 *
151 * This function tries to find formats, e.g.:
152 * %o - offset of the block
153 *
154 * In case of successfull parsing it fills the format param
155 * with proper offset and the size of the expected value, which
156 * should be pasted into buffer using the format 'func' callback.
157 *
158 * Returns the end pointer where parsing has been stopped.
159 * In case of parsing error or lack of bytes in output buffer
160 * NULL will be returned.
161 */
parse_format(const char * in,char * out,unsigned int parsed,unsigned int out_len,unsigned int * filled,const struct pattern_fmt_desc * fmt_desc,unsigned int fmt_desc_sz,struct pattern_fmt * fmt,unsigned int fmt_sz)162 static const char *parse_format(const char *in, char *out, unsigned int parsed,
163 unsigned int out_len, unsigned int *filled,
164 const struct pattern_fmt_desc *fmt_desc,
165 unsigned int fmt_desc_sz,
166 struct pattern_fmt *fmt, unsigned int fmt_sz)
167 {
168 int i;
169 struct pattern_fmt *f = NULL;
170 unsigned int len = 0;
171
172 if (!out_len || !fmt_desc || !fmt_desc_sz || !fmt || !fmt_sz)
173 return NULL;
174
175 assert(*in == '%');
176
177 for (i = 0; i < fmt_desc_sz; i++) {
178 const struct pattern_fmt_desc *desc;
179
180 desc = &fmt_desc[i];
181 len = strlen(desc->fmt);
182 if (0 == strncmp(in, desc->fmt, len)) {
183 fmt->desc = desc;
184 fmt->off = parsed;
185 f = fmt;
186 break;
187 }
188 }
189
190 if (!f)
191 return NULL;
192 if (f->desc->len > out_len)
193 return NULL;
194
195 memset(out, '\0', f->desc->len);
196 *filled = f->desc->len;
197
198 return in + len;
199 }
200
201 /**
202 * parse_and_fill_pattern() - Parses combined input, which consists of strings,
203 * numbers and pattern formats.
204 * @in - string input
205 * @in_len - size of the input string
206 * @out - output buffer where parsed result will be put
207 * @out_len - lengths of the output buffer
208 * @fmt_desc - array of pattern format descriptors [input]
209 * @fmt_desc_sz - size of the format descriptor array
210 * @fmt - array of pattern formats [output]
211 * @fmt_sz - pointer where the size of pattern formats array stored [input],
212 * after successfull parsing this pointer will contain the number
213 * of parsed formats if any [output].
214 *
215 * strings:
216 * bytes sequence in double quotes, e.g. "123".
217 * NOTE: there is no way to escape quote, so "123\"abc" does not work.
218 *
219 * numbers:
220 * hexidecimal - sequence of hex bytes starting from 0x or 0X prefix,
221 * e.g. 0xff12ceff1100ff
222 * decimal - decimal number in range [INT_MIN, INT_MAX]
223 *
224 * formats:
225 * %o - offset of block, reserved 8 bytes.
226 *
227 * Explicit examples of combined string:
228 * #1 #2 #3 #4
229 * in="abcd" in=-1024 in=66 in=0xFF0X1
230 * out=61 62 63 64 out=00 fc ff ff out=42 out=ff 01
231 *
232 * #5 #6
233 * in=%o in="123"0xFFeeCC
234 * out=00 00 00 00 00 00 00 00 out=31 32 33 ff ec cc
235 *
236 * #7
237 * in=-100xab"1"%o"2"
238 * out=f6 ff ff ff ab 31 00 00 00 00 00 00 00 00 32
239 *
240 * #9
241 * in=%o0xdeadbeef%o
242 * out=00 00 00 00 00 00 00 00 de ad be ef 00 00 00 00 00 00 00 00
243 *
244 * #10
245 * in=0xfefefefefefefefefefefefefefefefefefefefefe
246 * out=fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe fe
247 *
248 * Returns number of bytes filled or err < 0 in case of failure.
249 */
parse_and_fill_pattern(const char * in,unsigned int in_len,char * out,unsigned int out_len,const struct pattern_fmt_desc * fmt_desc,unsigned int fmt_desc_sz,struct pattern_fmt * fmt,unsigned int * fmt_sz_out)250 int parse_and_fill_pattern(const char *in, unsigned int in_len,
251 char *out, unsigned int out_len,
252 const struct pattern_fmt_desc *fmt_desc,
253 unsigned int fmt_desc_sz,
254 struct pattern_fmt *fmt,
255 unsigned int *fmt_sz_out)
256 {
257 const char *beg, *end, *out_beg = out;
258 unsigned int total = 0, fmt_rem = 0;
259
260 if (!in || !in_len || !out || !out_len)
261 return -EINVAL;
262 if (fmt_sz_out)
263 fmt_rem = *fmt_sz_out;
264
265 beg = in;
266 do {
267 unsigned int filled;
268 int parsed_fmt;
269
270 filled = 0;
271 parsed_fmt = 0;
272
273 switch (*beg) {
274 case '"':
275 end = parse_string(beg, out, out_len, &filled);
276 break;
277 case '%':
278 end = parse_format(beg, out, out - out_beg, out_len,
279 &filled, fmt_desc, fmt_desc_sz,
280 fmt, fmt_rem);
281 parsed_fmt = 1;
282 break;
283 default:
284 end = parse_number(beg, out, out_len, &filled);
285 break;
286 }
287
288 if (!end)
289 return -EINVAL;
290
291 if (parsed_fmt) {
292 assert(fmt_rem);
293 fmt_rem--;
294 fmt++;
295 }
296
297 assert(end - beg <= in_len);
298 in_len -= end - beg;
299 beg = end;
300
301 assert(filled);
302 assert(filled <= out_len);
303 out_len -= filled;
304 out += filled;
305 total += filled;
306
307 } while (in_len);
308
309 if (fmt_sz_out)
310 *fmt_sz_out -= fmt_rem;
311 return total;
312 }
313
314 /**
315 * dup_pattern() - Duplicates part of the pattern all over the buffer.
316 *
317 * Returns 0 in case of success or errno < 0 in case of failure.
318 */
dup_pattern(char * out,unsigned int out_len,unsigned int pattern_len)319 static int dup_pattern(char *out, unsigned int out_len, unsigned int pattern_len)
320 {
321 unsigned int left, len, off;
322
323 if (out_len <= pattern_len)
324 /* Normal case */
325 return 0;
326
327 off = pattern_len;
328 left = (out_len - off);
329 len = min(left, off);
330
331 /* Duplicate leftover */
332 while (left) {
333 memcpy(out + off, out, len);
334 left -= len;
335 off <<= 1;
336 len = min(left, off);
337 }
338
339 return 0;
340 }
341
342 /**
343 * cpy_pattern() - Copies pattern to the buffer.
344 *
345 * Function copies pattern along the whole buffer.
346 *
347 * Returns 0 in case of success or errno < 0 in case of failure.
348 */
cpy_pattern(const char * pattern,unsigned int pattern_len,char * out,unsigned int out_len)349 int cpy_pattern(const char *pattern, unsigned int pattern_len,
350 char *out, unsigned int out_len)
351 {
352 unsigned int len;
353
354 if (!pattern || !pattern_len || !out || !out_len)
355 return -EINVAL;
356
357 /* Copy pattern */
358 len = min(pattern_len, out_len);
359 memcpy(out, pattern, len);
360
361 /* Spread filled chunk all over the buffer */
362 return dup_pattern(out, out_len, pattern_len);
363 }
364
365 /**
366 * cmp_pattern() - Compares pattern and buffer.
367 *
368 * For the sake of performance this function avoids any loops.
369 * Firstly it tries to compare the buffer itself, checking that
370 * buffer consists of repeating patterns along the buffer size.
371 *
372 * If the difference is not found then the function tries to compare
373 * buffer and pattern.
374 *
375 * Returns 0 in case of success or errno < 0 in case of failure.
376 */
cmp_pattern(const char * pattern,unsigned int pattern_size,unsigned int off,const char * buf,unsigned int len)377 int cmp_pattern(const char *pattern, unsigned int pattern_size,
378 unsigned int off, const char *buf, unsigned int len)
379 {
380 int rc;
381 unsigned int size;
382
383 /* Find the difference in buffer */
384 if (len > pattern_size) {
385 rc = memcmp(buf, buf + pattern_size, len - pattern_size);
386 if (rc)
387 return -EILSEQ;
388 }
389 /* Compare second part of the pattern with buffer */
390 if (off) {
391 size = min(len, pattern_size - off);
392 rc = memcmp(buf, pattern + off, size);
393 if (rc)
394 return -EILSEQ;
395 buf += size;
396 len -= size;
397 }
398 /* Compare first part of the pattern or the whole pattern
399 * with buffer */
400 if (len) {
401 size = min(len, (off ? off : pattern_size));
402 rc = memcmp(buf, pattern, size);
403 if (rc)
404 return -EILSEQ;
405 }
406
407 return 0;
408 }
409
410 /**
411 * paste_format_inplace() - Pastes parsed formats to the pattern.
412 *
413 * This function pastes formats to the pattern. If @fmt_sz is 0
414 * function does nothing and pattern buffer is left untouched.
415 *
416 * Returns 0 in case of success or errno < 0 in case of failure.
417 */
paste_format_inplace(char * pattern,unsigned int pattern_len,struct pattern_fmt * fmt,unsigned int fmt_sz,void * priv)418 int paste_format_inplace(char *pattern, unsigned int pattern_len,
419 struct pattern_fmt *fmt, unsigned int fmt_sz,
420 void *priv)
421 {
422 int i, rc;
423 unsigned int len;
424
425 if (!pattern || !pattern_len || !fmt)
426 return -EINVAL;
427
428 /* Paste formats for first pattern chunk */
429 for (i = 0; i < fmt_sz; i++) {
430 struct pattern_fmt *f;
431
432 f = &fmt[i];
433 if (pattern_len <= f->off)
434 break;
435 len = min(pattern_len - f->off, f->desc->len);
436 rc = f->desc->paste(pattern + f->off, len, priv);
437 if (rc)
438 return rc;
439 }
440
441 return 0;
442 }
443
444 /**
445 * paste_format() - Pastes parsed formats to the buffer.
446 *
447 * This function copies pattern to the buffer, pastes format
448 * into it and then duplicates pattern all over the buffer size.
449 *
450 * Returns 0 in case of success or errno < 0 in case of failure.
451 */
paste_format(const char * pattern,unsigned int pattern_len,struct pattern_fmt * fmt,unsigned int fmt_sz,char * out,unsigned int out_len,void * priv)452 int paste_format(const char *pattern, unsigned int pattern_len,
453 struct pattern_fmt *fmt, unsigned int fmt_sz,
454 char *out, unsigned int out_len, void *priv)
455 {
456 int rc;
457 unsigned int len;
458
459 if (!pattern || !pattern_len || !out || !out_len)
460 return -EINVAL;
461
462 /* Copy pattern */
463 len = min(pattern_len, out_len);
464 memcpy(out, pattern, len);
465
466 rc = paste_format_inplace(out, len, fmt, fmt_sz, priv);
467 if (rc)
468 return rc;
469
470 /* Spread filled chunk all over the buffer */
471 return dup_pattern(out, out_len, pattern_len);
472 }
473