lib/pattern.c

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