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 } 473