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