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