epan/value_string.c

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