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