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 }