epan/range.c

   1 /* range.c
   2  * Range routines
   3  *
   4  * Dick Gooris <gooris@lucent.com>
   5  * Ulf Lamping <ulf.lamping@web.de>
   6  *
   7  * Wireshark - Network traffic analyzer
   8  * By Gerald Combs <gerald@wireshark.org>
   9  * Copyright 1998 Gerald Combs
  10  *
  11  * SPDX-License-Identifier: GPL-2.0-or-later
  12  */
  13
  14 #include "config.h"
  15
  16 #include <stdio.h>
  17 #include <string.h>
  18 #include <stdlib.h>
  19 #include <errno.h>
  20
  21 #include <glib.h>
  22
  23 #include <epan/frame_data.h>
  24
  25 #include <epan/range.h>
  26
  27 #include <wsutil/strtoi.h>
  28
  29 /*
  30  * Size of the header of a range_t.
  31  */
  32 #define RANGE_HDR_SIZE (sizeof (range_t))
  33
  34 /* Allocate an empty range. */
  35 range_t *range_empty(wmem_allocator_t *scope)
  36 {
  37    range_t *range;
  38
  39    range = (range_t *)wmem_alloc(scope, RANGE_HDR_SIZE);
  40    range->nranges = 0;
  41    return range;
  42 }
  43
  44 /******************** Range Entry Parser *********************************/
  45
  46 /* Converts a range string to a fast comparable array of ranges.
  47  * The parameter 'es' points to the string to be converted.
  48  * The parameter 'max_value' specifies the maximum value in a
  49  * range.
  50  *
  51  * This function allocates a range_t large enough to hold the number
  52  * of ranges specified, and fills the array range->ranges containing
  53  * low and high values with the number of ranges being range->nranges.
  54  * After having called this function, the function value_is_in_range()
  55  * determines whether a given number is within the range or not.
  56  *
  57  * In case of a single number, we make a range where low is equal to high.
  58  * We take care on wrongly entered ranges; opposite order will be taken
  59  * care of.
  60  *
  61  * The following syntax is accepted :
  62  *
  63  *   1-20,30-40     Range from 1 to 20, and packets 30 to 40
  64  *   -20,30         Range from 1 to 20, and packet 30
  65  *   20,30,40-      20, 30, and the range from 40 to the end
  66  *   20-10,30-25    Range from 10 to 20, and from 25 to 30
  67  *   -              All values
  68  */
  69
  70 convert_ret_t
  71 range_convert_str(wmem_allocator_t *scope, range_t **rangep, const char *es, uint32_t max_value)
  72 {
  73    return range_convert_str_work(scope, rangep, es, max_value, true);
  74 }
  75
  76 /*  This version of range_convert_str() allows the caller to specify whether
  77  *  values in excess of the range's specified maximum should cause an error or
  78  *  be silently lowered.
  79  *  XXX - both the function and the variable could probably use better names.
  80  */
  81 convert_ret_t
  82 range_convert_str_work(wmem_allocator_t *scope, range_t **rangep, const char *es, uint32_t max_value,
  83                        bool err_on_max)
  84 {
  85
  86    range_t       *range;
  87    unsigned      nranges;
  88    const char    *p;
  89    const char    *endp;
  90    char          c;
  91    unsigned      i;
  92    uint32_t      tmp;
  93    uint32_t      val;
  94
  95    if ( (rangep == NULL) || (es == NULL) )
  96       return CVT_SYNTAX_ERROR;
  97
  98    /* Allocate a range; this has room for one subrange. */
  99    range = (range_t *)wmem_alloc(scope, RANGE_HDR_SIZE + sizeof (range_admin_t));
 100    range->nranges = 0;
 101    nranges = 1;
 102
 103    /* Process the ranges separately until we get a comma or end of string.
 104     *
 105     * We build a structure array called ranges of high and low values. After the
 106     * following loop, we have the nranges variable which tells how many ranges
 107     * were found. The number of individual ranges is limited to 'MaxRanges'
 108     */
 109
 110    p = es;
 111    for (;;) {
 112       /* Skip white space. */
 113       while ((c = *p) == ' ' || c == '\t')
 114          p++;
 115       if (c == '\0')
 116          break;
 117
 118       /* This must be a subrange.  Make sure we have room for it. */
 119       if (range->nranges >= nranges) {
 120          /* Grow the structure.
 121           * 4 is an arbitrarily chosen number.
 122           * We start with 1, under the assumption that people
 123           * will often give a single number or range, and then
 124           * proceed to keep it a multiple of 4.
 125           */
 126          if (nranges == 1)
 127             nranges = 4;
 128          else
 129             nranges += 4;
 130          range = (range_t *)wmem_realloc(scope, range, RANGE_HDR_SIZE +
 131                                       nranges*sizeof (range_admin_t));
 132       }
 133
 134       if (c == '-') {
 135          /* Subrange starts with 1. */
 136          range->ranges[range->nranges].low = 1;
 137       } else if (g_ascii_isdigit(c)) {
 138          /* Subrange starts with the specified number */
 139          errno = 0;
 140          ws_basestrtou32(p, &endp, &val, 0);
 141          if (errno == EINVAL) {
 142             /* That wasn't a valid number. */
 143             wmem_free(scope, range);
 144             return CVT_SYNTAX_ERROR;
 145          }
 146          if (errno == ERANGE || val > max_value) {
 147             /* That was valid, but it's too big.  Return an error if requested
 148              * (e.g., except when reading from the preferences file).
 149              */
 150             if (err_on_max) {
 151                wmem_free(scope, range);
 152                return CVT_NUMBER_TOO_BIG;
 153             } else {
 154                /* Silently use the range's maximum value */
 155                val = max_value;
 156             }
 157          }
 158          p = endp;
 159          range->ranges[range->nranges].low = val;
 160
 161          /* Skip white space. */
 162          while ((c = *p) == ' ' || c == '\t')
 163             p++;
 164       } else {
 165          /* Neither empty nor a number. */
 166          wmem_free(scope, range);
 167          return CVT_SYNTAX_ERROR;
 168       }
 169
 170       if (c == '-') {
 171          /* There's a hyphen in the range.  Skip past it. */
 172          p++;
 173
 174          /* Skip white space. */
 175          while ((c = *p) == ' ' || c == '\t')
 176             p++;
 177
 178          if (c == ',' || c == '\0') {
 179             /* End of subrange string; that means the subrange ends
 180              * with max_value.
 181              */
 182             range->ranges[range->nranges].high = max_value;
 183          } else if (g_ascii_isdigit(c)) {
 184             /* Subrange ends with the specified number. */
 185             errno = 0;
 186             ws_basestrtou32(p, &endp, &val, 0);
 187             if (errno == EINVAL) {
 188                /* That wasn't a valid number. */
 189                wmem_free(scope, range);
 190                return CVT_SYNTAX_ERROR;
 191             }
 192             if (errno == ERANGE || val > max_value) {
 193                /* That was valid, but it's too big.  Return an error if requested
 194                 * (e.g., except when reading from the preferences file).
 195                 */
 196                if (err_on_max) {
 197                   wmem_free(scope, range);
 198                   return CVT_NUMBER_TOO_BIG;
 199                } else {
 200                   /* Silently use the range's maximum value */
 201                   val = max_value;
 202                }
 203             }
 204             p = endp;
 205             range->ranges[range->nranges].high = val;
 206
 207             /* Skip white space. */
 208             while ((c = *p) == ' ' || c == '\t')
 209                p++;
 210          } else {
 211             /* Neither empty nor a number. */
 212             wmem_free(scope, range);
 213             return CVT_SYNTAX_ERROR;
 214          }
 215       } else if (c == ',' || c == '\0') {
 216          /* End of subrange string; that means there's no hyphen
 217           * in the subrange, so the start and the end are the same.
 218           */
 219          range->ranges[range->nranges].high = range->ranges[range->nranges].low;
 220       } else {
 221          /* Invalid character. */
 222          wmem_free(scope, range);
 223          return CVT_SYNTAX_ERROR;
 224       }
 225       range->nranges++;
 226
 227       if (c == ',') {
 228          /* Subrange is followed by a comma; skip it. */
 229          p++;
 230       }
 231    }
 232
 233    /* Now we are going through the low and high values, and check
 234     * whether they are in a proper order. Low should be equal or lower
 235     * than high. So, go through the loop and swap if needed.
 236     */
 237    for (i=0; i < range->nranges; i++) {
 238       if (range->ranges[i].low > range->ranges[i].high) {
 239          tmp = range->ranges[i].low;
 240          range->ranges[i].low  = range->ranges[i].high;
 241          range->ranges[i].high = tmp;
 242       }
 243    }
 244
 245    /* In case we want to know what the result ranges are :
 246     *
 247     * for (i=0; i < range->nranges; i++) {
 248     *  printf("Function : range_convert_str L=%u \t H=%u\n",range->ranges[i].low,range->ranges[i].high);
 249     * }
 250     *
 251     */
 252    *rangep = range;
 253    return CVT_NO_ERROR;
 254 } /* range_convert_str */
 255
 256 /* This function returns true if a given value is within one of the ranges
 257  * stored in the ranges array.
 258  */
 259 bool
 260 value_is_in_range(const range_t *range, uint32_t val)
 261 {
 262    unsigned i;
 263
 264    if (range) {
 265       for (i=0; i < range->nranges; i++) {
 266          if (val >= range->ranges[i].low && val <= range->ranges[i].high)
 267             return true;
 268       }
 269    }
 270    return false;
 271 }
 272
 273 /* This function returns true if val has successfully been added to
 274  * a range.  This may extend an existing range or create a new one
 275  */
 276 bool
 277 range_add_value(wmem_allocator_t *scope, range_t **range, uint32_t val)
 278 {
 279    unsigned i;
 280
 281    if ((range) && (*range)) {
 282       for (i=0; i < (*range)->nranges; i++) {
 283          if (val >= (*range)->ranges[i].low && val <= (*range)->ranges[i].high)
 284             return true;
 285
 286          if (val == (*range)->ranges[i].low-1)
 287          {
 288              /* Sink to a new low */
 289              (*range)->ranges[i].low = val;
 290              return true;
 291          }
 292
 293          if (val == (*range)->ranges[i].high+1)
 294          {
 295              /* Reach a new high */
 296              (*range)->ranges[i].high = val;
 297              return true;
 298          }
 299       }
 300
 301       (*range) = (range_t *)wmem_realloc(scope, (*range), RANGE_HDR_SIZE +
 302                                 ((*range)->nranges+1)*sizeof (range_admin_t));
 303       (*range)->nranges++;
 304       (*range)->ranges[i].low = (*range)->ranges[i].high = val;
 305       return true;
 306    }
 307    return false;
 308 }
 309
 310 /* This function returns true if val has successfully been removed from
 311  * a range.  This may delete an existing range
 312  */
 313 bool
 314 range_remove_value(wmem_allocator_t *scope, range_t **range, uint32_t val)
 315 {
 316    unsigned i, j, new_j;
 317    range_t *new_range;
 318
 319    if ((range) && (*range)) {
 320       for (i=0; i < (*range)->nranges; i++) {
 321
 322           /* value is in the middle of the range, so it can't really be removed */
 323          if (val > (*range)->ranges[i].low && val < (*range)->ranges[i].high)
 324             return true;
 325
 326          if ((val ==  (*range)->ranges[i].low) && (val == (*range)->ranges[i].high))
 327          {
 328              /* Remove the range item entirely */
 329              new_range = (range_t*)wmem_alloc(scope, RANGE_HDR_SIZE + ((*range)->nranges-1)*sizeof (range_admin_t));
 330              new_range->nranges = (*range)->nranges-1;
 331              for (j=0, new_j = 0; j < (*range)->nranges; j++) {
 332
 333                  /* Skip the current range */
 334                  if (j == i)
 335                      continue;
 336
 337                  new_range->ranges[new_j].low = (*range)->ranges[j].low;
 338                  new_range->ranges[new_j].high = (*range)->ranges[j].high;
 339                  new_j++;
 340              }
 341
 342              wmem_free(scope, *range);
 343              *range = new_range;
 344              return true;
 345          }
 346
 347          if (val == (*range)->ranges[i].low)
 348          {
 349              /* Raise low */
 350              (*range)->ranges[i].low++;
 351              return true;
 352          }
 353
 354          if (val == (*range)->ranges[i].high)
 355          {
 356              /* Reach a new high */
 357              (*range)->ranges[i].high--;
 358              return true;
 359          }
 360       }
 361       return true;
 362    }
 363    return false;
 364 }
 365
 366 /* This function returns true if the two given range_t's are equal.
 367  */
 368 bool
 369 ranges_are_equal(const range_t *a, const range_t *b)
 370 {
 371    unsigned i;
 372
 373    if ( (a == NULL) || (b == NULL) )
 374        return false;
 375
 376    if (a->nranges != b->nranges)
 377       return false;
 378
 379    for (i=0; i < a->nranges; i++) {
 380       if (a->ranges[i].low != b->ranges[i].low)
 381          return false;
 382
 383       if (a->ranges[i].high != b->ranges[i].high)
 384          return false;
 385    }
 386
 387    return true;
 388
 389 }
 390
 391 /* This function calls the provided callback function for each value in
 392  * in the range.
 393  */
 394 void
 395 range_foreach(range_t *range, void (*callback)(uint32_t val, void *ptr), void *ptr)
 396 {
 397    uint32_t i, j;
 398
 399    if (range && callback) {
 400       for (i=0; i < range->nranges; i++) {
 401          for (j = range->ranges[i].low; j <= range->ranges[i].high; j++)
 402             callback(j, ptr);
 403       }
 404    }
 405 }
 406
 407 /* This function converts a range_t to a (wmem-allocated) string.  */
 408 char *
 409 range_convert_range(wmem_allocator_t *scope, const range_t *range)
 410 {
 411    uint32_t i;
 412    bool prepend_comma = false;
 413    wmem_strbuf_t *strbuf;
 414
 415    strbuf=wmem_strbuf_new(scope, "");
 416
 417    if (range) {
 418       for (i=0; i < range->nranges; i++) {
 419          if (range->ranges[i].low == range->ranges[i].high) {
 420             wmem_strbuf_append_printf(strbuf, "%s%u", prepend_comma?",":"", range->ranges[i].low);
 421          } else {
 422             wmem_strbuf_append_printf(strbuf, "%s%u-%u", prepend_comma?",":"", range->ranges[i].low, range->ranges[i].high);
 423          }
 424          prepend_comma = true;
 425       }
 426    }
 427    return wmem_strbuf_finalize(strbuf);
 428 }
 429
 430 /* Create a copy of a range. */
 431 range_t *
 432 range_copy(wmem_allocator_t *scope, const range_t *src)
 433 {
 434    range_t *dst;
 435    size_t range_size;
 436
 437    if (src == NULL)
 438        return NULL;
 439
 440    range_size = RANGE_HDR_SIZE + src->nranges*sizeof (range_admin_t);
 441    dst = (range_t *)wmem_memdup(scope, src, range_size);
 442    return dst;
 443 }
 444
 445 #if 0
 446 /* This is a debug function to check the range functionality */
 447 static void
 448 value_is_in_range_check(range_t *range, uint32_t val)
 449 {
 450    /* Print the result for a given value */
 451    printf("Function : value_is_in_range_check Number %u\t",val);
 452
 453    if (value_is_in_range(range, val)) {
 454       printf("is in range\n");
 455    } else {
 456       printf("is not in range\n");
 457    }
 458 }
 459 #endif
 460
 461 /*
 462  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
 463  *
 464  * Local Variables:
 465  * c-basic-offset: 3
 466  * tab-width: 8
 467  * indent-tabs-mode: nil
 468  * End:
 469  *
 470  * ex: set shiftwidth=3 tabstop=8 expandtab:
 471  * :indentSize=3:tabSize=8:noTabs=true:
 472  */