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