lib/pattern.c

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