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