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