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  * This program is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License
  10  * as published by the Free Software Foundation; either version 2
  11  * of the License, or (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  21  */
  22
  23 #include "config.h"
  24
  25 #include <stdio.h>
  26 #include <string.h>
  27
  28 #include "wmem/wmem.h"
  29 #include "proto.h"
  30 #include "to_str.h"
  31 #include "value_string.h"
  32
  33 /* REGULAR VALUE STRING */
  34
  35 /* Tries to match val against each element in the value_string array vs.
  36    Returns the associated string ptr on a match.
  37    Formats val with fmt, and returns the resulting string, on failure. */
  38 const gchar *
  39 val_to_str(const guint32 val, const value_string *vs, const char *fmt)
  40 {
  41     const gchar *ret;
  42
  43     DISSECTOR_ASSERT(fmt != NULL);
  44
  45     ret = try_val_to_str(val, vs);
  46     if (ret != NULL)
  47         return ret;
  48
  49     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
  50 }
  51
  52 gchar *
  53 val_to_str_wmem(wmem_allocator_t *scope, const guint32 val, const value_string *vs, const char *fmt)
  54 {
  55     const gchar *ret;
  56
  57     DISSECTOR_ASSERT(fmt != NULL);
  58
  59     ret = try_val_to_str(val, vs);
  60     if (ret != NULL)
  61         return wmem_strdup(scope, ret);
  62
  63     return wmem_strdup_printf(scope, fmt, val);
  64 }
  65
  66 /* Tries to match val against each element in the value_string array vs.
  67    Returns the associated string ptr on a match.
  68    Returns 'unknown_str', on failure. */
  69 const gchar *
  70 val_to_str_const(const guint32 val, const value_string *vs,
  71         const char *unknown_str)
  72 {
  73     const gchar *ret;
  74
  75     DISSECTOR_ASSERT(unknown_str != NULL);
  76
  77     ret = try_val_to_str(val, vs);
  78     if (ret != NULL)
  79         return ret;
  80
  81     return unknown_str;
  82 }
  83
  84 /* Tries to match val against each element in the value_string array vs.
  85    Returns the associated string ptr, and sets "*idx" to the index in
  86    that table, on a match, and returns NULL, and sets "*idx" to -1,
  87    on failure. */
  88 const gchar *
  89 try_val_to_str_idx(const guint32 val, const value_string *vs, gint *idx)
  90 {
  91     gint i = 0;
  92
  93     DISSECTOR_ASSERT(idx != NULL);
  94
  95     if(vs) {
  96         while (vs[i].strptr) {
  97             if (vs[i].value == val) {
  98                 *idx = i;
  99                 return(vs[i].strptr);
 100             }
 101             i++;
 102         }
 103     }
 104
 105     *idx = -1;
 106     return NULL;
 107 }
 108
 109 /* Like try_val_to_str_idx(), but doesn't return the index. */
 110 const gchar *
 111 try_val_to_str(const guint32 val, const value_string *vs)
 112 {
 113     gint ignore_me;
 114     return try_val_to_str_idx(val, vs, &ignore_me);
 115 }
 116
 117 /* 64-BIT VALUE STRING */
 118
 119 const gchar *
 120 val64_to_str(const guint64 val, const val64_string *vs, const char *fmt)
 121 {
 122     const gchar *ret;
 123
 124     DISSECTOR_ASSERT(fmt != NULL);
 125
 126     ret = try_val64_to_str(val, vs);
 127     if (ret != NULL)
 128         return ret;
 129
 130     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 131 }
 132
 133 const gchar *
 134 val64_to_str_const(const guint64 val, const val64_string *vs,
 135         const char *unknown_str)
 136 {
 137     const gchar *ret;
 138
 139     DISSECTOR_ASSERT(unknown_str != NULL);
 140
 141     ret = try_val64_to_str(val, vs);
 142     if (ret != NULL)
 143         return ret;
 144
 145     return unknown_str;
 146 }
 147
 148 const gchar *
 149 try_val64_to_str_idx(const guint64 val, const val64_string *vs, gint *idx)
 150 {
 151     gint i = 0;
 152
 153     DISSECTOR_ASSERT(idx != NULL);
 154
 155     if(vs) {
 156         while (vs[i].strptr) {
 157             if (vs[i].value == val) {
 158                 *idx = i;
 159                 return(vs[i].strptr);
 160             }
 161             i++;
 162         }
 163     }
 164
 165     *idx = -1;
 166     return NULL;
 167 }
 168
 169 const gchar *
 170 try_val64_to_str(const guint64 val, const val64_string *vs)
 171 {
 172     gint ignore_me;
 173     return try_val64_to_str_idx(val, vs, &ignore_me);
 174 }
 175
 176 /* REVERSE VALUE STRING */
 177
 178 /* We use the same struct as for regular value strings, but we look up strings
 179  * and return values instead */
 180
 181 /* Like val_to_str except backwards */
 182 guint32
 183 str_to_val(const gchar *val, const value_string *vs, const guint32 err_val)
 184 {
 185     gint i;
 186
 187     i = str_to_val_idx(val, vs);
 188
 189     if (i >= 0) {
 190         return vs[i].value;
 191     }
 192
 193     return err_val;
 194 }
 195
 196 /* Find the index of a string in a value_string, or -1 when not present */
 197 gint
 198 str_to_val_idx(const gchar *val, const value_string *vs)
 199 {
 200     gint i = 0;
 201
 202     if(vs) {
 203
 204         while (vs[i].strptr) {
 205
 206             if (strcmp(vs[i].strptr, val) == 0) {
 207                 return i;
 208             }
 209
 210             i++;
 211         }
 212
 213     }
 214
 215     return -1;
 216 }
 217
 218 /* EXTENDED VALUE STRING */
 219
 220 /* Extended value strings allow fast(er) value_string array lookups by
 221  * using (if possible) direct access or a binary search of the array.
 222  *
 223  * If the values in the value_string array are a contiguous range of values
 224  * from min to max, the value will be used as as a direct index into the array.
 225  *
 226  * If the values in the array are not contiguous (ie: there are "gaps"),
 227  * but are in assending order a binary search will be used.
 228  *
 229  * If direct access or binary search cannot be used, then a linear search
 230  * is used and a warning is emitted.
 231  *
 232  * Note that the value_string array used with VALUE_STRING_EXT_INIT
 233  * *must* be terminated with {0, NULL}).
 234  *
 235  * Extended value strings are defined at compile time as follows:
 236  *   static const value_string vs[] = { {value1, "string1"},
 237  *                                      {value2, "string2"},
 238  *                                      ...,
 239  *                                      {0, NULL}};
 240  *   static value_string_ext vse = VALUE_STRING_EXT_INIT(vs);
 241  *
 242  * Extended value strings can be created at runtime by calling
 243  *   value_string_ext_new(<ptr to value_string array>,
 244  *                        <total number of entries in the value_string_array>,
 245  *                        <value_string_name>);
 246  * Note: The <total number of entries in the value_string_array> should include
 247  *       the {0, NULL} entry.
 248  */
 249
 250 /* Create a value_string_ext given a ptr to a value_string array and the total
 251  * number of entries. Note that the total number of entries should include the
 252  * required {0, NULL} terminating entry of the array.
 253  * Returns a pointer to an epan-scoped'd and initialized value_string_ext
 254  * struct. */
 255 value_string_ext *
 256 value_string_ext_new(const value_string *vs, guint vs_tot_num_entries,
 257         const gchar *vs_name)
 258 {
 259     value_string_ext *vse;
 260
 261     DISSECTOR_ASSERT (vs_name != NULL);
 262     DISSECTOR_ASSERT (vs_tot_num_entries > 0);
 263     /* Null-terminated value-string ? */
 264     DISSECTOR_ASSERT (vs[vs_tot_num_entries-1].strptr == NULL);
 265
 266     vse                  = wmem_new(wmem_epan_scope(), value_string_ext);
 267     vse->_vs_p           = vs;
 268     vse->_vs_num_entries = vs_tot_num_entries - 1;
 269     /* We set our 'match' function to the init function, which finishes by
 270      * setting the match function properly and then calling it. This is a
 271      * simple way to do lazy initialization of extended value strings.
 272      * The init function also sets up _vs_first_value for us. */
 273     vse->_vs_first_value = 0;
 274     vse->_vs_match2      = _try_val_to_str_ext_init;
 275     vse->_vs_name        = vs_name;
 276
 277     return vse;
 278 }
 279
 280 void
 281 value_string_ext_free(const value_string_ext *vse)
 282 {
 283     wmem_free(wmem_epan_scope(), (void *)vse);
 284 }
 285
 286 /* Like try_val_to_str for extended value strings */
 287 const gchar *
 288 try_val_to_str_ext(const guint32 val, value_string_ext *vse)
 289 {
 290     if (vse) {
 291         const value_string *vs = vse->_vs_match2(val, vse);
 292
 293         if (vs) {
 294             return vs->strptr;
 295         }
 296     }
 297
 298     return NULL;
 299 }
 300
 301 /* Like try_val_to_str_idx for extended value strings */
 302 const gchar *
 303 try_val_to_str_idx_ext(const guint32 val, value_string_ext *vse, gint *idx)
 304 {
 305     if (vse) {
 306         const value_string *vs = vse->_vs_match2(val, vse);
 307         if (vs) {
 308             *idx = (gint) (vs - vse->_vs_p);
 309             return vs->strptr;
 310         }
 311     }
 312     *idx = -1;
 313     return NULL;
 314 }
 315
 316 /* Like val_to_str for extended value strings */
 317 const gchar *
 318 val_to_str_ext(const guint32 val, value_string_ext *vse, const char *fmt)
 319 {
 320     const gchar *ret;
 321
 322     DISSECTOR_ASSERT(fmt != NULL);
 323
 324     ret = try_val_to_str_ext(val, vse);
 325     if (ret != NULL)
 326         return ret;
 327
 328     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 329 }
 330
 331 gchar *
 332 val_to_str_ext_wmem(wmem_allocator_t *scope, const guint32 val, value_string_ext *vse, const char *fmt)
 333 {
 334     const gchar *ret;
 335
 336     DISSECTOR_ASSERT(fmt != NULL);
 337
 338     ret = try_val_to_str_ext(val, vse);
 339     if (ret != NULL)
 340         return wmem_strdup(scope, ret);
 341
 342     return wmem_strdup_printf(scope, fmt, val);
 343 }
 344
 345 /* Like val_to_str_const for extended value strings */
 346 const gchar *
 347 val_to_str_ext_const(const guint32 val, value_string_ext *vse,
 348         const char *unknown_str)
 349 {
 350     const gchar *ret;
 351
 352     DISSECTOR_ASSERT(unknown_str != NULL);
 353
 354     ret = try_val_to_str_ext(val, vse);
 355     if (ret != NULL)
 356         return ret;
 357
 358     return unknown_str;
 359 }
 360
 361 /* Fallback linear matching algorithm for extended value strings */
 362 static const value_string *
 363 _try_val_to_str_linear(const guint32 val, value_string_ext *vse)
 364 {
 365     const value_string *vs_p = vse->_vs_p;
 366     guint i;
 367     for (i=0; i<vse->_vs_num_entries; i++) {
 368         if (vs_p[i].value == val)
 369             return &(vs_p[i]);
 370     }
 371     return NULL;
 372 }
 373
 374 /* Constant-time matching algorithm for contiguous extended value strings */
 375 static const value_string *
 376 _try_val_to_str_index(const guint32 val, value_string_ext *vse)
 377 {
 378     guint i;
 379
 380     i = val - vse->_vs_first_value;
 381     if (i < vse->_vs_num_entries) {
 382         g_assert (val == vse->_vs_p[i].value);
 383         return &(vse->_vs_p[i]);
 384     }
 385     return NULL;
 386 }
 387
 388 /* log(n)-time matching algorithm for sorted extended value strings */
 389 static const value_string *
 390 _try_val_to_str_bsearch(const guint32 val, value_string_ext *vse)
 391 {
 392     guint low, i, max;
 393     guint32 item;
 394
 395     for (low = 0, max = vse->_vs_num_entries; low < max; ) {
 396         i = (low + max) / 2;
 397         item = vse->_vs_p[i].value;
 398
 399         if (val < item)
 400             max = i;
 401         else if (val > item)
 402             low = i + 1;
 403         else
 404             return &(vse->_vs_p[i]);
 405     }
 406     return NULL;
 407 }
 408
 409 /* Initializes an extended value string. Behaves like a match function to
 410  * permit lazy initialization of extended value strings.
 411  * - Goes through the value_string array to determine the fastest possible
 412  *   access method.
 413  * - Verifies that the value_string contains no NULL string pointers.
 414  * - Verifies that the value_string is terminated by {0, NULL}
 415  */
 416 const value_string *
 417 _try_val_to_str_ext_init(const guint32 val, value_string_ext *vse)
 418 {
 419     const value_string *vs_p           = vse->_vs_p;
 420     const guint         vs_num_entries = vse->_vs_num_entries;
 421
 422     /* The matching algorithm used:
 423      * VS_SEARCH   - slow sequential search (as in a normal value string)
 424      * VS_BIN_TREE - log(n)-time binary search, the values must be sorted
 425      * VS_INDEX    - constant-time index lookup, the values must be contiguous
 426      */
 427     enum { VS_SEARCH, VS_BIN_TREE, VS_INDEX } type = VS_INDEX;
 428
 429     /* Note: The value_string 'value' is *unsigned*, but we do a little magic
 430      * to help with value strings that have negative values.
 431      *
 432      * { -3, -2, -1, 0, 1, 2 }
 433      * will be treated as "ascending ordered" (although it isn't technically),
 434      * thus allowing constant-time index search
 435      *
 436      * { -3, -2, 0, 1, 2 } and { -3, -2, -1, 0, 2 }
 437      * will both be considered as "out-of-order with gaps", thus falling
 438      * back to the slow linear search
 439      *
 440      * { 0, 1, 2, -3, -2 } and { 0, 2, -3, -2, -1 }
 441      * will be considered "ascending ordered with gaps" thus allowing
 442      * a log(n)-time 'binary' search
 443      *
 444      * If you're confused, think of how negative values are represented, or
 445      * google two's complement.
 446      */
 447
 448     guint32 prev_value;
 449     guint   first_value;
 450     guint   i;
 451
 452     DISSECTOR_ASSERT((vs_p[vs_num_entries].value  == 0) &&
 453                      (vs_p[vs_num_entries].strptr == NULL));
 454
 455     vse->_vs_first_value = vs_p[0].value;
 456     first_value          = vs_p[0].value;
 457     prev_value           = first_value;
 458
 459     for (i = 0; i < vs_num_entries; i++) {
 460         DISSECTOR_ASSERT(vs_p[i].strptr != NULL);
 461         if ((type == VS_INDEX) && (vs_p[i].value != (i + first_value))) {
 462             type = VS_BIN_TREE;
 463         }
 464         /* XXX: Should check for dups ?? */
 465         if (type == VS_BIN_TREE) {
 466             if (prev_value > vs_p[i].value) {
 467                 g_warning("Extended value string '%s' forced to fall back to linear search:\n"
 468                           "  entry %u, value %u [%#x] < previous entry, value %u [%#x]",
 469                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, prev_value, prev_value);
 470                 type = VS_SEARCH;
 471                 break;
 472             }
 473             if (first_value > vs_p[i].value) {
 474                 g_warning("Extended value string '%s' forced to fall back to linear search:\n"
 475                           "  entry %u, value %u [%#x] < first entry, value %u [%#x]",
 476                           vse->_vs_name, i, vs_p[i].value, vs_p[i].value, first_value, first_value);
 477                 type = VS_SEARCH;
 478                 break;
 479             }
 480         }
 481
 482         prev_value = vs_p[i].value;
 483     }
 484
 485     switch (type) {
 486         case VS_SEARCH:
 487             vse->_vs_match2 = _try_val_to_str_linear;
 488             break;
 489         case VS_BIN_TREE:
 490             vse->_vs_match2 = _try_val_to_str_bsearch;
 491             break;
 492         case VS_INDEX:
 493             vse->_vs_match2 = _try_val_to_str_index;
 494             break;
 495         default:
 496             g_assert_not_reached();
 497             break;
 498     }
 499
 500     return vse->_vs_match2(val, vse);
 501 }
 502
 503 /* STRING TO STRING MATCHING */
 504
 505 /* string_string is like value_string except the values being matched are
 506  * also strings (instead of unsigned integers) */
 507
 508 /* Like val_to_str except for string_string */
 509 const gchar *
 510 str_to_str(const gchar *val, const string_string *vs, const char *fmt)
 511 {
 512     const gchar *ret;
 513
 514     DISSECTOR_ASSERT(fmt != NULL);
 515
 516     ret = try_str_to_str(val, vs);
 517     if (ret != NULL)
 518         return ret;
 519
 520     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 521 }
 522
 523 /* Like try_val_to_str_idx except for string_string */
 524 const gchar *
 525 try_str_to_str_idx(const gchar *val, const string_string *vs, gint *idx)
 526 {
 527     gint i = 0;
 528
 529     if(vs) {
 530         while (vs[i].strptr) {
 531             if (!strcmp(vs[i].value,val)) {
 532                 *idx = i;
 533                 return(vs[i].strptr);
 534             }
 535             i++;
 536         }
 537     }
 538
 539     *idx = -1;
 540     return NULL;
 541 }
 542
 543 /* Like try_val_to_str except for string_string */
 544 const gchar *
 545 try_str_to_str(const gchar *val, const string_string *vs)
 546 {
 547     gint ignore_me;
 548     return try_str_to_str_idx(val, vs, &ignore_me);
 549 }
 550
 551 /* RANGE TO STRING MATCHING */
 552
 553 /* range_string is like value_string except the values being matched are
 554  * integer ranges (for example, 0-10, 11-19, etc.) instead of single values. */
 555
 556 /* Like val_to_str except for range_string */
 557 const gchar *
 558 rval_to_str(const guint32 val, const range_string *rs, const char *fmt)
 559 {
 560     const gchar *ret = NULL;
 561
 562     DISSECTOR_ASSERT(fmt != NULL);
 563
 564     ret = try_rval_to_str(val, rs);
 565     if(ret != NULL)
 566         return ret;
 567
 568     return wmem_strdup_printf(wmem_packet_scope(), fmt, val);
 569 }
 570
 571 /* Like val_to_str_const except for range_string */
 572 const gchar *
 573 rval_to_str_const(const guint32 val, const range_string *rs,
 574         const char *unknown_str)
 575 {
 576     const gchar *ret = NULL;
 577
 578     DISSECTOR_ASSERT(unknown_str != NULL);
 579
 580     ret = try_rval_to_str(val, rs);
 581     if(ret != NULL)
 582         return ret;
 583
 584     return unknown_str;
 585 }
 586
 587 /* Like try_val_to_str_idx except for range_string */
 588 const gchar *
 589 try_rval_to_str_idx(const guint32 val, const range_string *rs, gint *idx)
 590 {
 591     gint i = 0;
 592
 593     if(rs) {
 594         while(rs[i].strptr) {
 595             if( (val >= rs[i].value_min) && (val <= rs[i].value_max) ) {
 596                 *idx = i;
 597                 return (rs[i].strptr);
 598             }
 599             i++;
 600         }
 601     }
 602
 603     *idx = -1;
 604     return NULL;
 605 }
 606
 607 /* Like try_val_to_str except for range_string */
 608 const gchar *
 609 try_rval_to_str(const guint32 val, const range_string *rs)
 610 {
 611     gint ignore_me = 0;
 612     return try_rval_to_str_idx(val, rs, &ignore_me);
 613 }
 614
 615 /* MISC */
 616
 617 /* Functions for use by proto_registrar_dump_values(), see proto.c */
 618
 619 gboolean
 620 value_string_ext_validate(const value_string_ext *vse)
 621 {
 622     if (vse == NULL)
 623         return FALSE;
 624 #ifndef _WIN32  /* doesn't work on Windows for refs from another DLL ?? */
 625     if ((vse->_vs_match2 != _try_val_to_str_ext_init) &&
 626         (vse->_vs_match2 != _try_val_to_str_linear)   &&
 627         (vse->_vs_match2 != _try_val_to_str_bsearch)  &&
 628         (vse->_vs_match2 != _try_val_to_str_index))
 629         return FALSE;
 630 #endif
 631     return TRUE;
 632 }
 633
 634 const gchar *
 635 value_string_ext_match_type_str(const value_string_ext *vse)
 636 {
 637     if (vse->_vs_match2 == _try_val_to_str_ext_init)
 638         return "[Not Initialized]";
 639     if (vse->_vs_match2 == _try_val_to_str_linear)
 640         return "[Linear Search]";
 641     if (vse->_vs_match2 == _try_val_to_str_bsearch)
 642         return "[Binary Search]";
 643     if (vse->_vs_match2 == _try_val_to_str_index)
 644         return "[Direct (indexed) Access]";
 645     return "[Invalid]";
 646 }
 647
 648 /*
 649  * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 650  *
 651  * Local variables:
 652  * c-basic-offset: 4
 653  * tab-width: 8
 654  * indent-tabs-mode: nil
 655  * End:
 656  *
 657  * vi: set shiftwidth=4 tabstop=8 expandtab:
 658  * :indentSize=4:tabSize=8:noTabs=true:
 659  */