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