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