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