epan/value_string.c

   1 /* value_string.c
   2  * Routines for value_strings
   3  *
   4  * Wireshark - Network traffic analyzer
   5  * By Gerald Combs <gerald@wireshark.org>
   6  * Copyright 1998 Gerald Combs
   7  *
   8  * SPDX-License-Identifier: GPL-2.0-or-later
   9  */
  10
  11 #include "config.h"
  12 #define WS_LOG_DOMAIN LOG_DOMAIN_EPAN
  13
  14 #include <stdio.h>
  15 #include <string.h>
  16
  17 #include <epan/wmem_scopes.h>
  18 #include "proto.h"
  19 #include "to_str.h"
  20 #include "value_string.h"
  21 #include <wsutil/ws_assert.h>
  22
  23 #include <wsutil/wslog.h>
  24
  25 /* REGULAR VALUE STRING */
  26
  27 /* Tries to match val against each element in the value_string array vs.
  28    Returns the associated string ptr on a match.
  29    Formats val with fmt, and returns the resulting string, on failure. */
  30 const char *
  31 val_to_str(const uint32_t val, const value_string *vs, const char *fmt)
  32 {
  33     const char *ret;
  34
  35     DISSECTOR_ASSERT(fmt != NULL);
  36
  37     ret = try_val_to_str(val, vs);
  38     if (ret != NULL)
  39         return ret;
  40
  41     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
  42 }
  43
  44 char *
  45 val_to_str_wmem(wmem_allocator_t *scope, const uint32_t val, const value_string *vs, const char *fmt)
  46 {
  47     const char *ret;
  48
  49     DISSECTOR_ASSERT(fmt != NULL);
  50
  51     ret = try_val_to_str(val, vs);
  52     if (ret != NULL)
  53         return wmem_strdup(scope, ret);
  54
  55     return wmem_strdup_printf(scope, fmt, val);
  56 }
  57
  58 /* Tries to match val against each element in the value_string array vs.
  59    Returns the associated string ptr on a match.
  60    Returns 'unknown_str', on failure. */
  61 const char *
  62 val_to_str_const(const uint32_t val, const value_string *vs,
  63         const char *unknown_str)
  64 {
  65     const char *ret;
  66
  67     DISSECTOR_ASSERT(unknown_str != NULL);
  68
  69     ret = try_val_to_str(val, vs);
  70     if (ret != NULL)
  71         return ret;
  72
  73     return unknown_str;
  74 }
  75
  76 /* Tries to match val against each element in the value_string array vs.
  77    Returns the associated string ptr, and sets "*idx" to the index in
  78    that table, on a match, and returns NULL, and sets "*idx" to -1,
  79    on failure. */
  80 const char *
  81 try_val_to_str_idx(const uint32_t val, const value_string *vs, int *idx)
  82 {
  83     int i = 0;
  84
  85     DISSECTOR_ASSERT(idx != NULL);
  86
  87     if(vs) {
  88         while (vs[i].strptr) {
  89             if (vs[i].value == val) {
  90                 *idx = i;
  91                 return(vs[i].strptr);
  92             }
  93             i++;
  94         }
  95     }
  96
  97     *idx = -1;
  98     return NULL;
  99 }
 100
 101 /* Like try_val_to_str_idx(), but doesn't return the index. */
 102 const char *
 103 try_val_to_str(const uint32_t val, const value_string *vs)
 104 {
 105     int ignore_me;
 106     return try_val_to_str_idx(val, vs, &ignore_me);
 107 }
 108
 109 const char *
 110 char_val_to_str(char val, const value_string *vs, const char *msg)
 111 {
 112     const char *ret;
 113     char buf[7];
 114
 115     DISSECTOR_ASSERT(msg != NULL);
 116
 117     ret = try_val_to_str(val, vs);
 118     if (ret != NULL)
 119         return ret;
 120
 121     return wmem_strdup_printf(wmem_packet_scope(), "%s: %s",
 122             msg, hfinfo_char_value_format_display(BASE_HEX, buf, val));
 123 }
 124
 125 /* 64-BIT VALUE STRING */
 126
 127 const char *
 128 val64_to_str(const uint64_t val, const val64_string *vs, const char *fmt)
 129 {
 130     const char *ret;
 131
 132     DISSECTOR_ASSERT(fmt != NULL);
 133
 134     ret = try_val64_to_str(val, vs);
 135     if (ret != NULL)
 136         return ret;
 137
 138     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 139 }
 140
 141 const char *
 142 val64_to_str_const(const uint64_t val, const val64_string *vs,
 143         const char *unknown_str)
 144 {
 145     const char *ret;
 146
 147     DISSECTOR_ASSERT(unknown_str != NULL);
 148
 149     ret = try_val64_to_str(val, vs);
 150     if (ret != NULL)
 151         return ret;
 152
 153     return unknown_str;
 154 }
 155
 156 const char *
 157 try_val64_to_str_idx(const uint64_t val, const val64_string *vs, int *idx)
 158 {
 159     int i = 0;
 160
 161     DISSECTOR_ASSERT(idx != NULL);
 162
 163     if(vs) {
 164         while (vs[i].strptr) {
 165             if (vs[i].value == val) {
 166                 *idx = i;
 167                 return(vs[i].strptr);
 168             }
 169             i++;
 170         }
 171     }
 172
 173     *idx = -1;
 174     return NULL;
 175 }
 176
 177 const char *
 178 try_val64_to_str(const uint64_t val, const val64_string *vs)
 179 {
 180     int ignore_me;
 181     return try_val64_to_str_idx(val, vs, &ignore_me);
 182 }
 183
 184 /* REVERSE VALUE STRING */
 185
 186 /* We use the same struct as for regular value strings, but we look up strings
 187  * and return values instead */
 188
 189 /* Like val_to_str except backwards */
 190 uint32_t
 191 str_to_val(const char *val, const value_string *vs, const uint32_t err_val)
 192 {
 193     int i;
 194
 195     i = str_to_val_idx(val, vs);
 196
 197     if (i >= 0) {
 198         return vs[i].value;
 199     }
 200
 201     return err_val;
 202 }
 203
 204 /* Find the index of a string in a value_string, or -1 when not present */
 205 int
 206 str_to_val_idx(const char *val, const value_string *vs)
 207 {
 208     int i = 0;
 209
 210     if(vs) {
 211
 212         while (vs[i].strptr) {
 213
 214             if (strcmp(vs[i].strptr, val) == 0) {
 215                 return i;
 216             }
 217
 218             i++;
 219         }
 220
 221     }
 222
 223     return -1;
 224 }
 225
 226 /* EXTENDED VALUE STRING */
 227
 228 /* Extended value strings allow fast(er) value_string array lookups by
 229  * using (if possible) direct access or a binary search of the array.
 230  *
 231  * If the values in the value_string array are a contiguous range of values
 232  * from min to max, the value will be used as a direct index into the array.
 233  *
 234  * If the values in the array are not contiguous (ie: there are "gaps"),
 235  * but are in assending order a binary search will be used.
 236  *
 237  * If direct access or binary search cannot be used, then a linear search
 238  * is used and a warning is emitted.
 239  *
 240  * Note that the value_string array used with VALUE_STRING_EXT_INIT
 241  * *must* be terminated with {0, NULL}).
 242  *
 243  * Extended value strings are defined at compile time as follows:
 244  *   static const value_string vs[] = { {value1, "string1"},
 245  *                                      {value2, "string2"},
 246  *                                      ...,
 247  *                                      {0, NULL}};
 248  *   static value_string_ext vse = VALUE_STRING_EXT_INIT(vs);
 249  *
 250  * Extended value strings can be created at runtime by calling
 251  *   value_string_ext_new(<ptr to value_string array>,
 252  *                        <total number of entries in the value_string_array>,
 253  *                        <value_string_name>);
 254  * Note: The <total number of entries in the value_string_array> should include
 255  *       the {0, NULL} entry.
 256  */
 257
 258 /* Create a value_string_ext given a ptr to a value_string array and the total
 259  * number of entries. Note that the total number of entries should include the
 260  * required {0, NULL} terminating entry of the array.
 261  * Returns a pointer to an epan-scoped'd and initialized value_string_ext
 262  * struct. */
 263 value_string_ext *
 264 value_string_ext_new(const value_string *vs, unsigned vs_tot_num_entries,
 265         const char *vs_name)
 266 {
 267     value_string_ext *vse;
 268
 269     DISSECTOR_ASSERT (vs_name != NULL);
 270     DISSECTOR_ASSERT (vs_tot_num_entries > 0);
 271     /* Null-terminated value-string ? */
 272     DISSECTOR_ASSERT (vs[vs_tot_num_entries-1].strptr == NULL);
 273
 274     vse                  = wmem_new(wmem_epan_scope(), value_string_ext);
 275     vse->_vs_p           = vs;
 276     vse->_vs_num_entries = vs_tot_num_entries - 1;
 277     /* We set our 'match' function to the init function, which finishes by
 278      * setting the match function properly and then calling it. This is a
 279      * simple way to do lazy initialization of extended value strings.
 280      * The init function also sets up _vs_first_value for us. */
 281     vse->_vs_first_value = 0;
 282     vse->_vs_match2      = _try_val_to_str_ext_init;
 283     vse->_vs_name        = vs_name;
 284
 285     return vse;
 286 }
 287
 288 void
 289 value_string_ext_free(value_string_ext *vse)
 290 {
 291     wmem_free(wmem_epan_scope(), vse);
 292 }
 293
 294 /* Like try_val_to_str for extended value strings */
 295 const char *
 296 try_val_to_str_ext(const uint32_t val, value_string_ext *vse)
 297 {
 298     if (vse) {
 299         const value_string *vs = vse->_vs_match2(val, vse);
 300
 301         if (vs) {
 302             return vs->strptr;
 303         }
 304     }
 305
 306     return NULL;
 307 }
 308
 309 /* Like try_val_to_str_idx for extended value strings */
 310 const char *
 311 try_val_to_str_idx_ext(const uint32_t val, value_string_ext *vse, int *idx)
 312 {
 313     if (vse) {
 314         const value_string *vs = vse->_vs_match2(val, vse);
 315         if (vs) {
 316             *idx = (int) (vs - vse->_vs_p);
 317             return vs->strptr;
 318         }
 319     }
 320     *idx = -1;
 321     return NULL;
 322 }
 323
 324 /* Like val_to_str for extended value strings */
 325 const char *
 326 val_to_str_ext(const uint32_t val, value_string_ext *vse, const char *fmt)
 327 {
 328     const char *ret;
 329
 330     DISSECTOR_ASSERT(fmt != NULL);
 331
 332     ret = try_val_to_str_ext(val, vse);
 333     if (ret != NULL)
 334         return ret;
 335
 336     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 337 }
 338
 339 char *
 340 val_to_str_ext_wmem(wmem_allocator_t *scope, const uint32_t val, value_string_ext *vse, const char *fmt)
 341 {
 342     const char *ret;
 343
 344     DISSECTOR_ASSERT(fmt != NULL);
 345
 346     ret = try_val_to_str_ext(val, vse);
 347     if (ret != NULL)
 348         return wmem_strdup(scope, ret);
 349
 350     return wmem_strdup_printf(scope, fmt, val);
 351 }
 352
 353 /* Like val_to_str_const for extended value strings */
 354 const char *
 355 val_to_str_ext_const(const uint32_t val, value_string_ext *vse,
 356         const char *unknown_str)
 357 {
 358     const char *ret;
 359
 360     DISSECTOR_ASSERT(unknown_str != NULL);
 361
 362     ret = try_val_to_str_ext(val, vse);
 363     if (ret != NULL)
 364         return ret;
 365
 366     return unknown_str;
 367 }
 368
 369 /* Fallback linear matching algorithm for extended value strings */
 370 static const value_string *
 371 _try_val_to_str_linear(const uint32_t val, value_string_ext *vse)
 372 {
 373     const value_string *vs_p = vse->_vs_p;
 374     unsigned i;
 375     for (i=0; i<vse->_vs_num_entries; i++) {
 376         if (vs_p[i].value == val)
 377             return &(vs_p[i]);
 378     }
 379     return NULL;
 380 }
 381
 382 /* Constant-time matching algorithm for contiguous extended value strings */
 383 static const value_string *
 384 _try_val_to_str_index(const uint32_t val, value_string_ext *vse)
 385 {
 386     uint32_t i;
 387
 388     i = val - vse->_vs_first_value;
 389     if (i < vse->_vs_num_entries) {
 390         ws_assert (val == vse->_vs_p[i].value);
 391         return &(vse->_vs_p[i]);
 392     }
 393     return NULL;
 394 }
 395
 396 /* Value comparator for sorted extended value strings */
 397 static int
 398 val_to_str_compar(const void *v_needle, const void *v_item)
 399 {
 400     uint32_t needle = *(const uint32_t *)v_needle;
 401     uint32_t value = ((const value_string *)v_item)->value;
 402     return needle > value ? 1 : (needle < value ? -1 : 0);
 403 }
 404
 405 /* log(n)-time matching for sorted extended value strings */
 406 static const value_string *
 407 _try_val_to_str_bsearch(const uint32_t val, value_string_ext *vse)
 408 {
 409     return bsearch(&val, vse->_vs_p, vse->_vs_num_entries,
 410                    sizeof vse->_vs_p[0], val_to_str_compar);
 411 }
 412
 413 /* Initializes an extended value string. Behaves like a match function to
 414  * permit lazy initialization of extended value strings.
 415  * - Goes through the value_string array to determine the fastest possible
 416  *   access method.
 417  * - Verifies that the value_string contains no NULL string pointers.
 418  * - Verifies that the value_string is terminated by {0, NULL}
 419  */
 420 const value_string *
 421 _try_val_to_str_ext_init(const uint32_t val, value_string_ext *vse)
 422 {
 423     const value_string *vs_p           = vse->_vs_p;
 424     const unsigned      vs_num_entries = vse->_vs_num_entries;
 425
 426     /* The matching algorithm used:
 427      * VS_LIN_SEARCH - slow linear search (as in a normal value string)
 428      * VS_BIN_SEARCH - log(n)-time binary search, the values must be sorted
 429      * VS_INDEX      - constant-time index lookup, the values must be contiguous
 430      */
 431     enum { VS_LIN_SEARCH, VS_BIN_SEARCH, VS_INDEX } type = VS_INDEX;
 432
 433     /* Note: The value_string 'value' is *unsigned*, but we do a little magic
 434      * to help with value strings that have negative values.
 435      *
 436      * { -3, -2, -1, 0, 1, 2 }
 437      * will be treated as "ascending ordered" (although it isn't technically),
 438      * thus allowing constant-time index search
 439      *
 440      * { -3, -2, 0, 1, 2 } and { -3, -2, -1, 0, 2 }
 441      * will both be considered as "out-of-order with gaps", thus falling
 442      * back to the slow linear search
 443      *
 444      * { 0, 1, 2, -3, -2 } and { 0, 2, -3, -2, -1 }
 445      * will be considered "ascending ordered with gaps" thus allowing
 446      * a log(n)-time 'binary' search
 447      *
 448      * If you're confused, think of how negative values are represented, or
 449      * google two's complement.
 450      */
 451
 452     uint32_t prev_value;
 453     uint32_t first_value;
 454     unsigned   i;
 455
 456     DISSECTOR_ASSERT((vs_p[vs_num_entries].value  == 0) &&
 457                      (vs_p[vs_num_entries].strptr == NULL));
 458
 459     vse->_vs_first_value = vs_p[0].value;
 460     first_value          = vs_p[0].value;
 461     prev_value           = first_value;
 462
 463     for (i = 0; i < vs_num_entries; i++) {
 464         DISSECTOR_ASSERT(vs_p[i].strptr != NULL);
 465         if ((type == VS_INDEX) && (vs_p[i].value != (i + first_value))) {
 466             type = VS_BIN_SEARCH;
 467         }
 468         /* XXX: Should check for dups ?? */
 469         if (type == VS_BIN_SEARCH) {
 470             if (prev_value > vs_p[i].value) {
 471                 ws_warning("Extended value string '%s' forced to fall back to linear search:\n"
 472                           "  entry %u, value %u [%#x] < previous entry, value %u [%#x]",
 473                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, prev_value, prev_value);
 474                 type = VS_LIN_SEARCH;
 475                 break;
 476             }
 477             if (first_value > vs_p[i].value) {
 478                 ws_warning("Extended value string '%s' forced to fall back to linear search:\n"
 479                           "  entry %u, value %u [%#x] < first entry, value %u [%#x]",
 480                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, first_value, first_value);
 481                 type = VS_LIN_SEARCH;
 482                 break;
 483             }
 484         }
 485
 486         prev_value = vs_p[i].value;
 487     }
 488
 489     switch (type) {
 490         case VS_LIN_SEARCH:
 491             vse->_vs_match2 = _try_val_to_str_linear;
 492             break;
 493         case VS_BIN_SEARCH:
 494             vse->_vs_match2 = _try_val_to_str_bsearch;
 495             break;
 496         case VS_INDEX:
 497             vse->_vs_match2 = _try_val_to_str_index;
 498             break;
 499         default:
 500             ws_assert_not_reached();
 501             break;
 502     }
 503
 504     return vse->_vs_match2(val, vse);
 505 }
 506
 507 /* EXTENDED 64-BIT VALUE STRING */
 508
 509 /* Extended value strings allow fast(er) val64_string array lookups by
 510  * using (if possible) direct access or a binary search of the array.
 511  *
 512  * If the values in the val64_string array are a contiguous range of values
 513  * from min to max, the value will be used as a direct index into the array.
 514  *
 515  * If the values in the array are not contiguous (ie: there are "gaps"),
 516  * but are in assending order a binary search will be used.
 517  *
 518  * If direct access or binary search cannot be used, then a linear search
 519  * is used and a warning is emitted.
 520  *
 521  * Note that the val64_string array used with VAL64_STRING_EXT_INIT
 522  * *must* be terminated with {0, NULL}).
 523  *
 524  * Extended value strings are defined at compile time as follows:
 525  *   static const val64_string vs[] = { {value1, "string1"},
 526  *                                      {value2, "string2"},
 527  *                                      ...,
 528  *                                      {0, NULL}};
 529  *   static val64_string_ext vse = VAL64_STRING_EXT_INIT(vs);
 530  *
 531  * Extended value strings can be created at runtime by calling
 532  *   val64_string_ext_new(<ptr to val64_string array>,
 533  *                        <total number of entries in the val64_string_array>,
 534  *                        <val64_string_name>);
 535  * Note: The <total number of entries in the val64_string_array> should include
 536  *       the {0, NULL} entry.
 537  */
 538
 539 /* Create a val64_string_ext given a ptr to a val64_string array and the total
 540  * number of entries. Note that the total number of entries should include the
 541  * required {0, NULL} terminating entry of the array.
 542  * Returns a pointer to an epan-scoped'd and initialized val64_string_ext
 543  * struct. */
 544 val64_string_ext *
 545 val64_string_ext_new(const val64_string *vs, unsigned vs_tot_num_entries,
 546         const char *vs_name)
 547 {
 548     val64_string_ext *vse;
 549
 550     DISSECTOR_ASSERT (vs_name != NULL);
 551     DISSECTOR_ASSERT (vs_tot_num_entries > 0);
 552     /* Null-terminated value-string ? */
 553     DISSECTOR_ASSERT (vs[vs_tot_num_entries-1].strptr == NULL);
 554
 555     vse                  = wmem_new(wmem_epan_scope(), val64_string_ext);
 556     vse->_vs_p           = vs;
 557     vse->_vs_num_entries = vs_tot_num_entries - 1;
 558     /* We set our 'match' function to the init function, which finishes by
 559      * setting the match function properly and then calling it. This is a
 560      * simple way to do lazy initialization of extended value strings.
 561      * The init function also sets up _vs_first_value for us. */
 562     vse->_vs_first_value = 0;
 563     vse->_vs_match2      = _try_val64_to_str_ext_init;
 564     vse->_vs_name        = vs_name;
 565
 566     return vse;
 567 }
 568
 569 void
 570 val64_string_ext_free(val64_string_ext *vse)
 571 {
 572     wmem_free(wmem_epan_scope(), vse);
 573 }
 574
 575 /* Like try_val_to_str for extended value strings */
 576 const char *
 577 try_val64_to_str_ext(const uint64_t val, val64_string_ext *vse)
 578 {
 579     if (vse) {
 580         const val64_string *vs = vse->_vs_match2(val, vse);
 581
 582         if (vs) {
 583             return vs->strptr;
 584         }
 585     }
 586
 587     return NULL;
 588 }
 589
 590 /* Like try_val_to_str_idx for extended value strings */
 591 const char *
 592 try_val64_to_str_idx_ext(const uint64_t val, val64_string_ext *vse, int *idx)
 593 {
 594     if (vse) {
 595         const val64_string *vs = vse->_vs_match2(val, vse);
 596         if (vs) {
 597             *idx = (int) (vs - vse->_vs_p);
 598             return vs->strptr;
 599         }
 600     }
 601     *idx = -1;
 602     return NULL;
 603 }
 604
 605 /* Like val_to_str for extended value strings */
 606 const char *
 607 val64_to_str_ext(const uint64_t val, val64_string_ext *vse, const char *fmt)
 608 {
 609     const char *ret;
 610
 611     DISSECTOR_ASSERT(fmt != NULL);
 612
 613     ret = try_val64_to_str_ext(val, vse);
 614     if (ret != NULL)
 615         return ret;
 616
 617     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 618 }
 619
 620 char *
 621 val64_to_str_ext_wmem(wmem_allocator_t *scope, const uint64_t val, val64_string_ext *vse, const char *fmt)
 622 {
 623     const char *ret;
 624
 625     DISSECTOR_ASSERT(fmt != NULL);
 626
 627     ret = try_val64_to_str_ext(val, vse);
 628     if (ret != NULL)
 629         return wmem_strdup(scope, ret);
 630
 631     return wmem_strdup_printf(scope, fmt, val);
 632 }
 633
 634 /* Like val_to_str_const for extended value strings */
 635 const char *
 636 val64_to_str_ext_const(const uint64_t val, val64_string_ext *vse,
 637         const char *unknown_str)
 638 {
 639     const char *ret;
 640
 641     DISSECTOR_ASSERT(unknown_str != NULL);
 642
 643     ret = try_val64_to_str_ext(val, vse);
 644     if (ret != NULL)
 645         return ret;
 646
 647     return unknown_str;
 648 }
 649
 650 /* Fallback linear matching algorithm for extended value strings */
 651 static const val64_string *
 652 _try_val64_to_str_linear(const uint64_t val, val64_string_ext *vse)
 653 {
 654     const val64_string *vs_p = vse->_vs_p;
 655     unsigned i;
 656     for (i=0; i<vse->_vs_num_entries; i++) {
 657         if (vs_p[i].value == val)
 658             return &(vs_p[i]);
 659     }
 660     return NULL;
 661 }
 662
 663 /* Constant-time matching algorithm for contiguous extended value strings */
 664 static const val64_string *
 665 _try_val64_to_str_index(const uint64_t val, val64_string_ext *vse)
 666 {
 667     uint64_t i;
 668
 669     i = val - vse->_vs_first_value;
 670     if (i < vse->_vs_num_entries) {
 671         ws_assert (val == vse->_vs_p[i].value);
 672         return &(vse->_vs_p[i]);
 673     }
 674     return NULL;
 675 }
 676
 677 /* Value comparator for sorted extended value strings */
 678 static int
 679 val64_to_str_compar(const void *v_needle, const void *v_item)
 680 {
 681     uint64_t needle = *(const uint64_t *)v_needle;
 682     uint64_t value = ((const val64_string *)v_item)->value;
 683     return needle > value ? 1 : (needle < value ? -1 : 0);
 684 }
 685
 686 /* log(n)-time matching for sorted extended value strings */
 687 static const val64_string *
 688 _try_val64_to_str_bsearch(const uint64_t val, val64_string_ext *vse)
 689 {
 690     return bsearch(&val, vse->_vs_p, vse->_vs_num_entries,
 691                    sizeof vse->_vs_p[0], val64_to_str_compar);
 692 }
 693
 694 /* Initializes an extended value string. Behaves like a match function to
 695  * permit lazy initialization of extended value strings.
 696  * - Goes through the val64_string array to determine the fastest possible
 697  *   access method.
 698  * - Verifies that the val64_string contains no NULL string pointers.
 699  * - Verifies that the val64_string is terminated by {0, NULL}
 700  */
 701 const val64_string *
 702 _try_val64_to_str_ext_init(const uint64_t val, val64_string_ext *vse)
 703 {
 704     const val64_string *vs_p           = vse->_vs_p;
 705     const unsigned      vs_num_entries = vse->_vs_num_entries;
 706
 707     /* The matching algorithm used:
 708      * VS_LIN_SEARCH - slow linear search (as in a normal value string)
 709      * VS_BIN_SEARCH - log(n)-time binary search, the values must be sorted
 710      * VS_INDEX      - constant-time index lookup, the values must be contiguous
 711      */
 712     enum { VS_LIN_SEARCH, VS_BIN_SEARCH, VS_INDEX } type = VS_INDEX;
 713
 714     /* Note: The val64_string 'value' is *unsigned*, but we do a little magic
 715      * to help with value strings that have negative values.
 716      *
 717      * { -3, -2, -1, 0, 1, 2 }
 718      * will be treated as "ascending ordered" (although it isn't technically),
 719      * thus allowing constant-time index search
 720      *
 721      * { -3, -2, 0, 1, 2 } and { -3, -2, -1, 0, 2 }
 722      * will both be considered as "out-of-order with gaps", thus falling
 723      * back to the slow linear search
 724      *
 725      * { 0, 1, 2, -3, -2 } and { 0, 2, -3, -2, -1 }
 726      * will be considered "ascending ordered with gaps" thus allowing
 727      * a log(n)-time 'binary' search
 728      *
 729      * If you're confused, think of how negative values are represented, or
 730      * google two's complement.
 731      */
 732
 733     uint64_t prev_value;
 734     uint64_t first_value;
 735     unsigned   i;
 736
 737     DISSECTOR_ASSERT((vs_p[vs_num_entries].value  == 0) &&
 738                      (vs_p[vs_num_entries].strptr == NULL));
 739
 740     vse->_vs_first_value = vs_p[0].value;
 741     first_value          = vs_p[0].value;
 742     prev_value           = first_value;
 743
 744     for (i = 0; i < vs_num_entries; i++) {
 745         DISSECTOR_ASSERT(vs_p[i].strptr != NULL);
 746         if ((type == VS_INDEX) && (vs_p[i].value != (i + first_value))) {
 747             type = VS_BIN_SEARCH;
 748         }
 749         /* XXX: Should check for dups ?? */
 750         if (type == VS_BIN_SEARCH) {
 751             if (prev_value > vs_p[i].value) {
 752                 ws_warning("Extended value string '%s' forced to fall back to linear search:\n"
 753                           "  entry %u, value %" PRIu64 " [%#" PRIx64 "] < previous entry, value %" PRIu64 " [%#" PRIx64 "]",
 754                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, prev_value, prev_value);
 755                 type = VS_LIN_SEARCH;
 756                 break;
 757             }
 758             if (first_value > vs_p[i].value) {
 759                 ws_warning("Extended value string '%s' forced to fall back to linear search:\n"
 760                           "  entry %u, value %" PRIu64 " [%#" PRIx64 "] < first entry, value %" PRIu64 " [%#" PRIx64 "]",
 761                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, first_value, first_value);
 762                 type = VS_LIN_SEARCH;
 763                 break;
 764             }
 765         }
 766
 767         prev_value = vs_p[i].value;
 768     }
 769
 770     switch (type) {
 771         case VS_LIN_SEARCH:
 772             vse->_vs_match2 = _try_val64_to_str_linear;
 773             break;
 774         case VS_BIN_SEARCH:
 775             vse->_vs_match2 = _try_val64_to_str_bsearch;
 776             break;
 777         case VS_INDEX:
 778             vse->_vs_match2 = _try_val64_to_str_index;
 779             break;
 780         default:
 781             ws_assert_not_reached();
 782             break;
 783     }
 784
 785     return vse->_vs_match2(val, vse);
 786 }
 787
 788 /* STRING TO STRING MATCHING */
 789
 790 /* string_string is like value_string except the values being matched are
 791  * also strings (instead of unsigned integers) */
 792
 793 /* Like val_to_str except for string_string */
 794 const char *
 795 str_to_str(const char *val, const string_string *vs, const char *fmt)
 796 {
 797     const char *ret;
 798
 799     DISSECTOR_ASSERT(fmt != NULL);
 800
 801     ret = try_str_to_str(val, vs);
 802     if (ret != NULL)
 803         return ret;
 804
 805     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 806 }
 807
 808 /* Like try_val_to_str_idx except for string_string */
 809 const char *
 810 try_str_to_str_idx(const char *val, const string_string *vs, int *idx)
 811 {
 812     int i = 0;
 813
 814     if(vs) {
 815         while (vs[i].strptr) {
 816             if (!strcmp(vs[i].value,val)) {
 817                 *idx = i;
 818                 return(vs[i].strptr);
 819             }
 820             i++;
 821         }
 822     }
 823
 824     *idx = -1;
 825     return NULL;
 826 }
 827
 828 /* Like try_val_to_str except for string_string */
 829 const char *
 830 try_str_to_str(const char *val, const string_string *vs)
 831 {
 832     int ignore_me;
 833     return try_str_to_str_idx(val, vs, &ignore_me);
 834 }
 835
 836 /* RANGE TO STRING MATCHING */
 837
 838 /* range_string is like value_string except the values being matched are
 839  * integer ranges (for example, 0-10, 11-19, etc.) instead of single values. */
 840
 841 /* Like val_to_str except for range_string */
 842 const char *
 843 rval_to_str(const uint32_t val, const range_string *rs, const char *fmt)
 844 {
 845     const char *ret = NULL;
 846
 847     DISSECTOR_ASSERT(fmt != NULL);
 848
 849     ret = try_rval_to_str(val, rs);
 850     if(ret != NULL)
 851         return ret;
 852
 853     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 854 }
 855
 856 /* Like val_to_str_const except for range_string */
 857 const char *
 858 rval_to_str_const(const uint32_t val, const range_string *rs,
 859         const char *unknown_str)
 860 {
 861     const char *ret = NULL;
 862
 863     DISSECTOR_ASSERT(unknown_str != NULL);
 864
 865     ret = try_rval_to_str(val, rs);
 866     if(ret != NULL)
 867         return ret;
 868
 869     return unknown_str;
 870 }
 871
 872 /* Like try_val_to_str_idx except for range_string */
 873 const char *
 874 try_rval_to_str_idx(const uint32_t val, const range_string *rs, int *idx)
 875 {
 876     int i = 0;
 877
 878     if(rs) {
 879         while(rs[i].strptr) {
 880             if( (val >= rs[i].value_min) && (val <= rs[i].value_max) ) {
 881                 *idx = i;
 882                 return (rs[i].strptr);
 883             }
 884             i++;
 885         }
 886     }
 887
 888     *idx = -1;
 889     return NULL;
 890 }
 891
 892 /* Like try_val_to_str except for range_string */
 893 const char *
 894 try_rval_to_str(const uint32_t val, const range_string *rs)
 895 {
 896     int ignore_me = 0;
 897     return try_rval_to_str_idx(val, rs, &ignore_me);
 898 }
 899
 900 /* Like try_val_to_str_idx except for range_string */
 901 const char *
 902 try_rval64_to_str_idx(const uint64_t val, const range_string *rs, int *idx)
 903 {
 904     int i = 0;
 905
 906     if(rs) {
 907         while(rs[i].strptr) {
 908             if( (val >= rs[i].value_min) && (val <= rs[i].value_max) ) {
 909                 *idx = i;
 910                 return (rs[i].strptr);
 911             }
 912             i++;
 913         }
 914     }
 915
 916     *idx = -1;
 917     return NULL;
 918 }
 919
 920 /* Like try_val64_to_str except for range_string */
 921 const char *
 922 try_rval64_to_str(const uint64_t val, const range_string *rs)
 923 {
 924     int ignore_me = 0;
 925     return try_rval64_to_str_idx(val, rs, &ignore_me);
 926 }
 927
 928
 929 /* BYTE BUFFER TO STRING MATCHING */
 930
 931 /* Like val_to_str except for bytes_string */
 932 const char *
 933 bytesval_to_str(const uint8_t *val, const size_t val_len, const bytes_string *bs, const char *fmt)
 934 {
 935     const char *ret;
 936
 937     DISSECTOR_ASSERT(fmt != NULL);
 938
 939     ret = try_bytesval_to_str(val, val_len, bs);
 940     if (ret != NULL)
 941         return ret;
 942
 943     /*
 944      * XXX should this use bytes_to_str as format parameter for consistency?
 945      * Though for bytes I guess most of the time you want to show "Unknown"
 946      * anyway rather than "Unknown (\x13\x37...)"
 947      */
 948     return wmem_strdup(wmem_packet_scope(), fmt);
 949 }
 950
 951 /* Like try_val_to_str except for bytes_string */
 952 const char *
 953 try_bytesval_to_str(const uint8_t *val, const size_t val_len, const bytes_string *bs)
 954 {
 955     unsigned i = 0;
 956
 957     if (bs) {
 958         while (bs[i].strptr) {
 959             if (bs[i].value_length == val_len && !memcmp(bs[i].value, val, val_len)) {
 960                 return bs[i].strptr;
 961             }
 962             i++;
 963         }
 964     }
 965
 966     return NULL;
 967 }
 968
 969 /* Like val_to_str, but tries to find a prefix (instead of an exact) match
 970    of any prefix from the bytes_string array bs against the haystack. */
 971 const char *
 972 bytesprefix_to_str(const uint8_t *haystack, const size_t haystack_len, const bytes_string *bs, const char *fmt)
 973 {
 974     const char *ret;
 975
 976     DISSECTOR_ASSERT(fmt != NULL);
 977
 978     ret = try_bytesprefix_to_str(haystack, haystack_len, bs);
 979     if (ret != NULL)
 980         return ret;
 981
 982     /* XXX See note at bytesval_to_str. */
 983     return wmem_strdup(wmem_packet_scope(), fmt);
 984 }
 985
 986 /* Like try_val_to_str, but tries to find a prefix (instead of an exact) match
 987    of any prefix from the bytes_string array bs against the haystack. */
 988 const char *
 989 try_bytesprefix_to_str(const uint8_t *haystack, const size_t haystack_len, const bytes_string *bs)
 990 {
 991     unsigned i = 0;
 992
 993     if (bs) {
 994         while (bs[i].strptr) {
 995             if (haystack_len >= bs[i].value_length &&
 996                 !memcmp(bs[i].value, haystack, bs[i].value_length)) {
 997                 return bs[i].strptr;
 998             }
 999             i++;
1000         }
1001     }
1002
1003     return NULL;
1004 }
1005
1006 /* MISC */
1007
1008 /* Functions for use by proto_registrar_dump_values(), see proto.c */
1009
1010 bool
1011 value_string_ext_validate(const value_string_ext *vse)
1012 {
1013     if (vse == NULL)
1014         return false;
1015 #ifndef _WIN32  /* doesn't work on Windows for refs from another DLL ?? */
1016     if ((vse->_vs_match2 != _try_val_to_str_ext_init) &&
1017         (vse->_vs_match2 != _try_val_to_str_linear)   &&
1018         (vse->_vs_match2 != _try_val_to_str_bsearch)  &&
1019         (vse->_vs_match2 != _try_val_to_str_index))
1020         return false;
1021 #endif
1022     return true;
1023 }
1024
1025 const char *
1026 value_string_ext_match_type_str(const value_string_ext *vse)
1027 {
1028     if (vse->_vs_match2 == _try_val_to_str_ext_init)
1029         return "[Not Initialized]";
1030     if (vse->_vs_match2 == _try_val_to_str_linear)
1031         return "[Linear Search]";
1032     if (vse->_vs_match2 == _try_val_to_str_bsearch)
1033         return "[Binary Search]";
1034     if (vse->_vs_match2 == _try_val_to_str_index)
1035         return "[Direct (indexed) Access]";
1036     return "[Invalid]";
1037 }
1038
1039 bool
1040 val64_string_ext_validate(const val64_string_ext *vse)
1041 {
1042     if (vse == NULL)
1043         return false;
1044 #ifndef _WIN32  /* doesn't work on Windows for refs from another DLL ?? */
1045     if ((vse->_vs_match2 != _try_val64_to_str_ext_init) &&
1046         (vse->_vs_match2 != _try_val64_to_str_linear)   &&
1047         (vse->_vs_match2 != _try_val64_to_str_bsearch)  &&
1048         (vse->_vs_match2 != _try_val64_to_str_index))
1049         return false;
1050 #endif
1051     return true;
1052 }
1053
1054 const char *
1055 val64_string_ext_match_type_str(const val64_string_ext *vse)
1056 {
1057     if (vse->_vs_match2 == _try_val64_to_str_ext_init)
1058         return "[Not Initialized]";
1059     if (vse->_vs_match2 == _try_val64_to_str_linear)
1060         return "[Linear Search]";
1061     if (vse->_vs_match2 == _try_val64_to_str_bsearch)
1062         return "[Binary Search]";
1063     if (vse->_vs_match2 == _try_val64_to_str_index)
1064         return "[Direct (indexed) Access]";
1065     return "[Invalid]";
1066 }
1067
1068 /*
1069  * Editor modelines  -  https://www.wireshark.org/tools/modelines.html
1070  *
1071  * Local variables:
1072  * c-basic-offset: 4
1073  * tab-width: 8
1074  * indent-tabs-mode: nil
1075  * End:
1076  *
1077  * vi: set shiftwidth=4 tabstop=8 expandtab:
1078  * :indentSize=4:tabSize=8:noTabs=true:
1079  */