coregrind/m_libcbase.c

   1
   2 /*--------------------------------------------------------------------*/
   3 /*--- Entirely standalone libc stuff.                 m_libcbase.c ---*/
   4 /*--------------------------------------------------------------------*/
   5
   6 /*
   7    This file is part of Valgrind, a dynamic binary instrumentation
   8    framework.
   9
  10    Copyright (C) 2000-2013 Julian Seward
  11       jseward@acm.org
  12
  13    This program is free software; you can redistribute it and/or
  14    modify it under the terms of the GNU General Public License as
  15    published by the Free Software Foundation; either version 2 of the
  16    License, or (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  26    02111-1307, USA.
  27
  28    The GNU General Public License is contained in the file COPYING.
  29 */
  30
  31 #include "pub_core_basics.h"
  32 #include "pub_core_libcassert.h"    // VG_(exit_now)
  33 #include "pub_core_debuglog.h"      // VG_(debugLog)
  34 #include "pub_core_libcbase.h"
  35
  36
  37 /* ---------------------------------------------------------------------
  38    Assert machinery for use in this file. vg_assert cannot be called
  39    here due to cyclic dependencies.
  40    ------------------------------------------------------------------ */
  41 #if 0
  42 #define libcbase_assert(expr)                             \
  43   ((void) (LIKELY(expr) ? 0 :                             \
  44            (ML_(libcbase_assert_fail)(#expr,              \
  45                                 __FILE__, __LINE__,       \
  46                                 __PRETTY_FUNCTION__))))
  47
  48 static void ML_(libcbase_assert_fail)( const HChar *expr,
  49                                        const HChar *file,
  50                                        Int line,
  51                                        const HChar *fn )
  52 {
  53    VG_(debugLog)(0, "libcbase",
  54                     "Valgrind: FATAL: assertion failed:\n");
  55    VG_(debugLog)(0, "libcbase", "  %s\n", expr);
  56    VG_(debugLog)(0, "libcbase", "  at %s:%d (%s)\n", file, line, fn);
  57    VG_(debugLog)(0, "libcbase", "Exiting now.\n");
  58    VG_(exit_now)(1);
  59 }
  60 #endif
  61
  62 /* ---------------------------------------------------------------------
  63    HChar functions.
  64    ------------------------------------------------------------------ */
  65
  66 Bool VG_(isspace) ( HChar c )
  67 {
  68    return (c == ' '  || c == '\n' || c == '\t' ||
  69            c == '\f' || c == '\v' || c == '\r');
  70 }
  71
  72 Bool VG_(isdigit) ( HChar c )
  73 {
  74    return (c >= '0' && c <= '9');
  75 }
  76
  77 /* ---------------------------------------------------------------------
  78    Converting strings to numbers
  79    ------------------------------------------------------------------ */
  80
  81 static Bool is_dec_digit(HChar c, Long* digit)
  82 {
  83    if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
  84    return False;
  85 }
  86
  87 static Bool is_hex_digit(HChar c, Long* digit)
  88 {
  89    if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
  90    if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; }
  91    if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; }
  92    return False;
  93 }
  94
  95 Long VG_(strtoll10) ( const HChar* str, HChar** endptr )
  96 {
  97    Bool neg = False, converted = False;
  98    Long n = 0, digit = 0;
  99    const HChar* str0 = str;
 100
 101    // Skip leading whitespace.
 102    while (VG_(isspace)(*str)) str++;
 103
 104    // Allow a leading '-' or '+'.
 105    if (*str == '-') { str++; neg = True; }
 106    else if (*str == '+') { str++; }
 107
 108    while (is_dec_digit(*str, &digit)) {
 109       converted = True;          // Ok, we've actually converted a digit.
 110       n = 10*n + digit;
 111       str++;
 112    }
 113
 114    if (!converted) str = str0;   // If nothing converted, endptr points to
 115    if (neg) n = -n;              //   the start of the string.
 116    if (endptr)
 117       *endptr = CONST_CAST(HChar *,str); // Record first failing character.
 118    return n;
 119 }
 120
 121 ULong VG_(strtoull10) ( const HChar* str, HChar** endptr )
 122 {
 123    Bool converted = False;
 124    ULong n = 0;
 125    Long digit = 0;
 126    const HChar* str0 = str;
 127
 128    // Skip leading whitespace.
 129    while (VG_(isspace)(*str)) str++;
 130
 131    // Allow a leading '+'.
 132    if (*str == '+') { str++; }
 133
 134    while (is_dec_digit(*str, &digit)) {
 135       converted = True;          // Ok, we've actually converted a digit.
 136       n = 10*n + digit;
 137       str++;
 138    }
 139
 140    if (!converted) str = str0;   // If nothing converted, endptr points to
 141    //   the start of the string.
 142    if (endptr)
 143       *endptr = CONST_CAST(HChar *,str); // Record first failing character.
 144    return n;
 145 }
 146
 147 Long VG_(strtoll16) ( const HChar* str, HChar** endptr )
 148 {
 149    Bool neg = False, converted = False;
 150    Long n = 0, digit = 0;
 151    const HChar* str0 = str;
 152
 153    // Skip leading whitespace.
 154    while (VG_(isspace)(*str)) str++;
 155
 156    // Allow a leading '-' or '+'.
 157    if (*str == '-') { str++; neg = True; }
 158    else if (*str == '+') { str++; }
 159
 160    // Allow leading "0x", but only if there's a hex digit
 161    // following it.
 162    if (*str == '0'
 163     && (*(str+1) == 'x' || *(str+1) == 'X')
 164     && is_hex_digit( *(str+2), &digit )) {
 165       str += 2;
 166    }
 167
 168    while (is_hex_digit(*str, &digit)) {
 169       converted = True;          // Ok, we've actually converted a digit.
 170       n = 16*n + digit;
 171       str++;
 172    }
 173
 174    if (!converted) str = str0;   // If nothing converted, endptr points to
 175    if (neg) n = -n;              //   the start of the string.
 176    if (endptr)
 177       *endptr = CONST_CAST(HChar *,str); // Record first failing character.
 178    return n;
 179 }
 180
 181 ULong VG_(strtoull16) ( const HChar* str, HChar** endptr )
 182 {
 183    Bool converted = False;
 184    ULong n = 0;
 185    Long digit = 0;
 186    const HChar* str0 = str;
 187
 188    // Skip leading whitespace.
 189    while (VG_(isspace)(*str)) str++;
 190
 191    // Allow a leading '+'.
 192    if (*str == '+') { str++; }
 193
 194    // Allow leading "0x", but only if there's a hex digit
 195    // following it.
 196    if (*str == '0'
 197     && (*(str+1) == 'x' || *(str+1) == 'X')
 198     && is_hex_digit( *(str+2), &digit )) {
 199       str += 2;
 200    }
 201
 202    while (is_hex_digit(*str, &digit)) {
 203       converted = True;          // Ok, we've actually converted a digit.
 204       n = 16*n + digit;
 205       str++;
 206    }
 207
 208    if (!converted) str = str0;   // If nothing converted, endptr points to
 209    //   the start of the string.
 210    if (endptr)
 211       *endptr = CONST_CAST(HChar *,str); // Record first failing character.
 212    return n;
 213 }
 214
 215 double VG_(strtod) ( const HChar* str, HChar** endptr )
 216 {
 217    Bool neg = False;
 218    Long digit;
 219    double n = 0, frac = 0, x = 0.1;
 220
 221    // Skip leading whitespace.
 222    while (VG_(isspace)(*str)) str++;
 223
 224    // Allow a leading '-' or '+'.
 225    if (*str == '-') { str++; neg = True; }
 226    else if (*str == '+') { str++; }
 227
 228    while (is_dec_digit(*str, &digit)) {
 229       n = 10*n + digit;
 230       str++;
 231    }
 232
 233    if (*str == '.') {
 234       str++;
 235       while (is_dec_digit(*str, &digit)) {
 236          frac += x*digit;
 237          x /= 10;
 238          str++;
 239       }
 240    }
 241
 242    n += frac;
 243    if (neg) n = -n;
 244    if (endptr)
 245       *endptr = CONST_CAST(HChar *,str); // Record first failing character.
 246    return n;
 247 }
 248
 249 HChar VG_(tolower) ( HChar c )
 250 {
 251    if ( c >= 'A'  &&  c <= 'Z' ) {
 252       return c - 'A' + 'a';
 253    } else {
 254       return c;
 255    }
 256 }
 257
 258 /* ---------------------------------------------------------------------
 259    String functions
 260    ------------------------------------------------------------------ */
 261
 262 SizeT VG_(strlen) ( const HChar* str )
 263 {
 264    SizeT i = 0;
 265    while (str[i] != 0) i++;
 266    return i;
 267 }
 268
 269 HChar* VG_(strcat) ( HChar* dest, const HChar* src )
 270 {
 271    HChar* dest_orig = dest;
 272    while (*dest) dest++;
 273    while (*src) *dest++ = *src++;
 274    *dest = 0;
 275    return dest_orig;
 276 }
 277
 278 HChar* VG_(strncat) ( HChar* dest, const HChar* src, SizeT n )
 279 {
 280    HChar* dest_orig = dest;
 281    while (*dest) dest++;
 282    while (*src && n > 0) { *dest++ = *src++; n--; }
 283    *dest = 0;
 284    return dest_orig;
 285 }
 286
 287 HChar* VG_(strpbrk) ( const HChar* s, const HChar* accpt )
 288 {
 289    const HChar* a;
 290    while (*s) {
 291       a = accpt;
 292       while (*a)
 293          if (*a++ == *s)
 294             return CONST_CAST(HChar *,s);
 295       s++;
 296    }
 297    return NULL;
 298 }
 299
 300 HChar* VG_(strcpy) ( HChar* dest, const HChar* src )
 301 {
 302    HChar* dest_orig = dest;
 303    while (*src) *dest++ = *src++;
 304    *dest = 0;
 305    return dest_orig;
 306 }
 307
 308 HChar* VG_(strncpy) ( HChar* dest, const HChar* src, SizeT ndest )
 309 {
 310    SizeT i = 0;
 311    while (True) {
 312       if (i >= ndest) return dest;     /* reached limit */
 313       dest[i] = src[i];
 314       if (src[i++] == 0) {
 315          /* reached NUL;  pad rest with zeroes as required */
 316          while (i < ndest) dest[i++] = 0;
 317          return dest;
 318       }
 319    }
 320 }
 321
 322 Int VG_(strcmp) ( const HChar* s1, const HChar* s2 )
 323 {
 324    while (True) {
 325       if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
 326       if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
 327
 328       /* *s1 == *s2 */
 329       if (*s1 == 0) return 0;
 330
 331       s1++; s2++;
 332    }
 333 }
 334
 335 Int VG_(strcasecmp) ( const HChar* s1, const HChar* s2 )
 336 {
 337    while (True) {
 338       UChar c1 = (UChar)VG_(tolower)(*s1);
 339       UChar c2 = (UChar)VG_(tolower)(*s2);
 340       if (c1 < c2) return -1;
 341       if (c1 > c2) return 1;
 342
 343       /* c1 == c2 */
 344       if (c1 == 0) return 0;
 345
 346       s1++; s2++;
 347    }
 348 }
 349
 350 Int VG_(strncmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
 351 {
 352    SizeT n = 0;
 353    while (True) {
 354       if (n >= nmax) return 0;
 355       if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
 356       if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
 357
 358       /* *s1 == *s2 */
 359       if (*s1 == 0) return 0;
 360
 361       s1++; s2++; n++;
 362    }
 363 }
 364
 365 Int VG_(strncasecmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
 366 {
 367    Int n = 0;
 368    while (True) {
 369       UChar c1;
 370       UChar c2;
 371       if (n >= nmax) return 0;
 372       c1 = (UChar)VG_(tolower)(*s1);
 373       c2 = (UChar)VG_(tolower)(*s2);
 374       if (c1 < c2) return -1;
 375       if (c1 > c2) return 1;
 376
 377       /* c1 == c2 */
 378       if (c1 == 0) return 0;
 379
 380       s1++; s2++; n++;
 381    }
 382 }
 383
 384 HChar* VG_(strstr) ( const HChar* haystack, const HChar* needle )
 385 {
 386    SizeT n;
 387    if (haystack == NULL)
 388       return NULL;
 389    n = VG_(strlen)(needle);
 390    while (True) {
 391       if (haystack[0] == 0)
 392          return NULL;
 393       if (VG_(strncmp)(haystack, needle, n) == 0)
 394          return CONST_CAST(HChar *,haystack);
 395       haystack++;
 396    }
 397 }
 398
 399 HChar* VG_(strcasestr) ( const HChar* haystack, const HChar* needle )
 400 {
 401    Int n;
 402    if (haystack == NULL)
 403       return NULL;
 404    n = VG_(strlen)(needle);
 405    while (True) {
 406       if (haystack[0] == 0)
 407          return NULL;
 408       if (VG_(strncasecmp)(haystack, needle, n) == 0)
 409          return CONST_CAST(HChar *,haystack);
 410       haystack++;
 411    }
 412 }
 413
 414 HChar* VG_(strchr) ( const HChar* s, HChar c )
 415 {
 416    while (True) {
 417       if (*s == c) return CONST_CAST(HChar *,s);
 418       if (*s == 0) return NULL;
 419       s++;
 420    }
 421 }
 422
 423 HChar* VG_(strrchr) ( const HChar* s, HChar c )
 424 {
 425    Int n = VG_(strlen)(s);
 426    while (--n > 0) {
 427       if (s[n] == c) return CONST_CAST(HChar *,s) + n;
 428    }
 429    return NULL;
 430 }
 431
 432 /* (code copied from glib then updated to valgrind types) */
 433 static HChar *olds;
 434 HChar *
 435 VG_(strtok) (HChar *s, const HChar *delim)
 436 {
 437    return VG_(strtok_r) (s, delim, &olds);
 438 }
 439
 440 HChar *
 441 VG_(strtok_r) (HChar* s, const HChar* delim, HChar** saveptr)
 442 {
 443    HChar *token;
 444
 445    if (s == NULL)
 446       s = *saveptr;
 447
 448    /* Scan leading delimiters.  */
 449    s += VG_(strspn (s, delim));
 450    if (*s == '\0')
 451       {
 452          *saveptr = s;
 453          return NULL;
 454       }
 455
 456    /* Find the end of the token.  */
 457    token = s;
 458    s = VG_(strpbrk (token, delim));
 459    if (s == NULL)
 460       /* This token finishes the string.  */
 461       *saveptr = token + VG_(strlen) (token);
 462    else
 463       {
 464          /* Terminate the token and make OLDS point past it.  */
 465          *s = '\0';
 466          *saveptr = s + 1;
 467       }
 468    return token;
 469 }
 470
 471 static Bool isHex ( HChar c )
 472 {
 473   return ((c >= '0' && c <= '9') ||
 474           (c >= 'a' && c <= 'f') ||
 475           (c >= 'A' && c <= 'F'));
 476 }
 477
 478 static UInt fromHex ( HChar c )
 479 {
 480    if (c >= '0' && c <= '9')
 481       return (UInt)c - (UInt)'0';
 482    if (c >= 'a' && c <= 'f')
 483       return 10 +  (UInt)c - (UInt)'a';
 484    if (c >= 'A' && c <= 'F')
 485       return 10 +  (UInt)c - (UInt)'A';
 486    /*NOTREACHED*/
 487    // ??? need to vg_assert(0);
 488    return 0;
 489 }
 490
 491 Bool VG_(parse_Addr) ( const HChar** ppc, Addr* result )
 492 {
 493    Int used, limit = 2 * sizeof(Addr);
 494    if (**ppc != '0')
 495       return False;
 496    (*ppc)++;
 497    if (**ppc != 'x')
 498       return False;
 499    (*ppc)++;
 500    *result = 0;
 501    used = 0;
 502    while (isHex(**ppc)) {
 503       // ??? need to vg_assert(d < fromHex(**ppc));
 504       *result = ((*result) << 4) | fromHex(**ppc);
 505       (*ppc)++;
 506       used++;
 507       if (used > limit) return False;
 508    }
 509    if (used == 0)
 510       return False;
 511    return True;
 512 }
 513
 514 Bool VG_(parse_enum_set) ( const HChar *tokens,
 515                            Bool  allow_all,
 516                            const HChar *input,
 517                            UInt *enum_set)
 518 {
 519    const SizeT tokens_len = VG_(strlen)(tokens);
 520    if (tokens_len > 1000) return False; /* "obviously invalid" */
 521    HChar  tok_tokens[tokens_len+1];
 522    HChar *tokens_saveptr;
 523    HChar *token;
 524    UInt token_nr = 0;
 525    UInt all_set = 0;
 526
 527    const SizeT input_len = VG_(strlen)(input);
 528    if (input_len > 1000) return False; /* "obviously invalid" */
 529    HChar  tok_input[input_len+1];
 530    HChar *input_saveptr;
 531    HChar *input_word;
 532    UInt word_nr = 0;
 533    UInt known_words = 0;
 534    Bool seen_all_kw = False;
 535    Bool seen_none_kw = False;
 536
 537    *enum_set = 0;
 538
 539    VG_(strcpy) (tok_input, input);
 540    for (input_word = VG_(strtok_r)(tok_input, ",", &input_saveptr);
 541         input_word;
 542         input_word = VG_(strtok_r)(NULL, ",", &input_saveptr)) {
 543       word_nr++;
 544       if (allow_all && 0 == VG_(strcmp)(input_word, "all")) {
 545          seen_all_kw = True;
 546          known_words++;
 547       } else if (0 == VG_(strcmp)(input_word, "none")) {
 548          seen_none_kw = True;
 549          known_words++;
 550       }
 551
 552       // Scan tokens + compute all_set. Do that even if all or none was
 553       // recognised to have a correct value for all_set when exiting
 554       // of the 'input' loop.
 555       all_set = 0;
 556       token_nr = 0;
 557       VG_(strcpy) (tok_tokens, tokens);
 558       for (token = VG_(strtok_r)(tok_tokens, ",", &tokens_saveptr);
 559            token;
 560            token = VG_(strtok_r)(NULL, ",", &tokens_saveptr)) {
 561          if (0 != VG_(strcmp)(token, "-")) {
 562             if (0 == VG_(strcmp)(input_word, token)) {
 563                *enum_set |= 1 << token_nr;
 564                known_words++;
 565             }
 566             all_set |= 1 << token_nr;
 567          }
 568          token_nr++;
 569       }
 570    }
 571
 572    if (known_words != word_nr)
 573       return False; // One or more input_words not recognised.
 574    if (seen_all_kw) {
 575       if (seen_none_kw || *enum_set)
 576          return False; // mixing all with either none or a specific value.
 577       *enum_set = all_set;
 578    } else if (seen_none_kw) {
 579       if (seen_all_kw || *enum_set)
 580          return False; // mixing none with either all or a specific value.
 581       *enum_set = 0;
 582    } else {
 583       // seen neither all or none, we must see at least one value
 584       if (*enum_set == 0)
 585          return False;
 586    }
 587
 588    return True;
 589 }
 590
 591 SizeT VG_(strspn) ( const HChar* s, const HChar* accpt )
 592 {
 593    const HChar *p, *a;
 594    SizeT count = 0;
 595    for (p = s; *p != '\0'; ++p) {
 596       for (a = accpt; *a != '\0'; ++a)
 597          if (*p == *a)
 598             break;
 599       if (*a == '\0')
 600          return count;
 601       else
 602          ++count;
 603    }
 604    return count;
 605 }
 606
 607 SizeT VG_(strcspn) ( const HChar* s, const HChar* reject )
 608 {
 609    SizeT count = 0;
 610    while (*s != '\0') {
 611       if (VG_(strchr) (reject, *s++) == NULL)
 612          ++count;
 613       else
 614          return count;
 615    }
 616    return count;
 617 }
 618
 619
 620 /* ---------------------------------------------------------------------
 621    mem* functions
 622    ------------------------------------------------------------------ */
 623
 624 void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
 625 {
 626    const UChar* s  = (const UChar*)src;
 627          UChar* d  =       (UChar*)dest;
 628    const UInt*  sI = (const UInt*)src;
 629          UInt*  dI =       (UInt*)dest;
 630
 631    if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
 632       while (sz >= 16) {
 633          dI[0] = sI[0];
 634          dI[1] = sI[1];
 635          dI[2] = sI[2];
 636          dI[3] = sI[3];
 637          sz -= 16;
 638          dI += 4;
 639          sI += 4;
 640       }
 641       if (sz == 0)
 642          return dest;
 643       while (sz >= 4) {
 644          dI[0] = sI[0];
 645          sz -= 4;
 646          dI += 1;
 647          sI += 1;
 648       }
 649       if (sz == 0)
 650          return dest;
 651       s = (const UChar*)sI;
 652       d = (UChar*)dI;
 653    }
 654
 655    /* If we're unlucky, the alignment constraints for the fast case
 656       above won't apply, and we'll have to do it all here.  Hence the
 657       unrolling. */
 658    while (sz >= 4) {
 659       d[0] = s[0];
 660       d[1] = s[1];
 661       d[2] = s[2];
 662       d[3] = s[3];
 663       d += 4;
 664       s += 4;
 665       sz -= 4;
 666    }
 667    while (sz >= 1) {
 668       d[0] = s[0];
 669       d += 1;
 670       s += 1;
 671       sz -= 1;
 672    }
 673
 674    return dest;
 675 }
 676
 677 void* VG_(memmove)(void *dest, const void *src, SizeT sz)
 678 {
 679    SizeT i;
 680    if (sz == 0)
 681       return dest;
 682    if (dest < src) {
 683       for (i = 0; i < sz; i++) {
 684          ((UChar*)dest)[i] = ((const UChar*)src)[i];
 685       }
 686    }
 687    else if (dest > src) {
 688       for (i = 0; i < sz; i++) {
 689          ((UChar*)dest)[sz-i-1] = ((const UChar*)src)[sz-i-1];
 690       }
 691    }
 692    return dest;
 693 }
 694
 695 void* VG_(memset) ( void *destV, Int c, SizeT sz )
 696 {
 697    UInt   c4;
 698    UChar* d = destV;
 699    UChar uc = c;
 700
 701    while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) {
 702       d[0] = uc;
 703       d++;
 704       sz--;
 705    }
 706    if (sz == 0)
 707       return destV;
 708    c4 = uc;
 709    c4 |= (c4 << 8);
 710    c4 |= (c4 << 16);
 711    while (sz >= 16) {
 712       ((UInt*)d)[0] = c4;
 713       ((UInt*)d)[1] = c4;
 714       ((UInt*)d)[2] = c4;
 715       ((UInt*)d)[3] = c4;
 716       d += 16;
 717       sz -= 16;
 718    }
 719    while (sz >= 4) {
 720       ((UInt*)d)[0] = c4;
 721       d += 4;
 722       sz -= 4;
 723    }
 724    while (sz >= 1) {
 725       d[0] = c;
 726       d++;
 727       sz--;
 728    }
 729    return destV;
 730 }
 731
 732 Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
 733 {
 734    Int res;
 735    const UChar *p1 = s1;
 736    const UChar *p2 = s2;
 737    UChar a0;
 738    UChar b0;
 739
 740    while (n != 0) {
 741       a0 = p1[0];
 742       b0 = p2[0];
 743       p1 += 1;
 744       p2 += 1;
 745       res = a0 - b0;
 746       if (res != 0)
 747          return res;
 748       n -= 1;
 749    }
 750    return 0;
 751 }
 752
 753 /* ---------------------------------------------------------------------
 754    Misc useful functions
 755    ------------------------------------------------------------------ */
 756
 757 /////////////////////////////////////////////////////////////
 758 /////////////////////////////////////////////////////////////
 759 /// begin Bentley-McIlroy style quicksort
 760 /// See "Engineering a Sort Function".  Jon L Bentley, M. Douglas
 761 /// McIlroy.  Software Practice and Experience Vol 23(11), Nov 1993.
 762
 763 #define BM_MIN(a, b)                                     \
 764    (a) < (b) ? a : b
 765
 766 #define BM_SWAPINIT(a, es)                               \
 767    swaptype =   ((a-(Char*)0) | es) % sizeof(Word)  ? 2  \
 768               : es > (SizeT)sizeof(Word) ? 1             \
 769               : 0
 770
 771 #define BM_EXCH(a, b, t)                                 \
 772    (t = a, a = b, b = t)
 773
 774 #define BM_SWAP(a, b)                                    \
 775    swaptype != 0                                         \
 776       ? bm_swapfunc(a, b, es, swaptype)                  \
 777       : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t)
 778
 779 #define BM_VECSWAP(a, b, n)                              \
 780    if (n > 0) bm_swapfunc(a, b, n, swaptype)
 781
 782 #define BM_PVINIT(pv, pm)                                \
 783    if (swaptype != 0)                                    \
 784       pv = a, BM_SWAP(pv, pm);                           \
 785    else                                                  \
 786       pv = (Char*)&v, v = *(Word*)pm
 787
 788 static Char* bm_med3 ( Char* a, Char* b, Char* c,
 789                        Int (*cmp)(const void*, const void*) ) {
 790    return cmp(a, b) < 0
 791           ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
 792           : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
 793 }
 794
 795 static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
 796 {
 797    if (swaptype <= 1) {
 798       Word t;
 799       for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
 800                                         n -= sizeof(Word))
 801          BM_EXCH(*(Word*)a, *(Word*)b, t);
 802    } else {
 803       Char t;
 804       for ( ; n > 0; a += 1, b += 1, n -= 1)
 805          BM_EXCH(*a, *b, t);
 806    }
 807 }
 808
 809 static void bm_qsort ( Char* a, SizeT n, SizeT es,
 810                        Int (*cmp)(const void*, const void*) )
 811 {
 812    Char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
 813    Int   r, swaptype;
 814    Word  t, v;
 815    SizeT s, s1, s2;
 816   tailcall:
 817    BM_SWAPINIT(a, es);
 818    if (n < 7) {
 819       for (pm = a + es; pm < a + n*es; pm += es)
 820          for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
 821             BM_SWAP(pl, pl-es);
 822       return;
 823    }
 824    pm = a + (n/2)*es;
 825    if (n > 7) {
 826       pl = a;
 827       pn = a + (n-1)*es;
 828       if (n > 40) {
 829          s = (n/8)*es;
 830          pl = bm_med3(pl, pl+s, pl+2*s, cmp);
 831          pm = bm_med3(pm-s, pm, pm+s, cmp);
 832          pn = bm_med3(pn-2*s, pn-s, pn, cmp);
 833       }
 834       pm = bm_med3(pl, pm, pn, cmp);
 835    }
 836    BM_PVINIT(pv, pm);
 837    pa = pb = a;
 838    pc = pd = a + (n-1)*es;
 839    for (;;) {
 840       while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
 841          if (r == 0) { BM_SWAP(pa, pb); pa += es; }
 842          pb += es;
 843       }
 844       while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
 845          if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
 846          pc -= es;
 847       }
 848       if (pb > pc) break;
 849       BM_SWAP(pb, pc);
 850       pb += es;
 851       pc -= es;
 852    }
 853    pn = a + n*es;
 854    s = BM_MIN(pa-a,  pb-pa   ); BM_VECSWAP(a,  pb-s, s);
 855    s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
 856    /* Now recurse.  Do the smaller partition first with an explicit
 857       recursion, then do the larger partition using a tail call.
 858       Except we can't rely on gcc to implement a tail call in any sane
 859       way, so simply jump back to the start.  This guarantees stack
 860       growth can never exceed O(log N) even in the worst case. */
 861    s1 = pb-pa;
 862    s2 = pd-pc;
 863    if (s1 < s2) {
 864       if (s1 > es) {
 865          bm_qsort(a, s1/es, es, cmp);
 866       }
 867       if (s2 > es) {
 868          /* bm_qsort(pn-s2, s2/es, es, cmp); */
 869          a = pn-s2; n = s2/es; es = es; cmp = cmp;
 870          goto tailcall;
 871       }
 872    } else {
 873       if (s2 > es) {
 874          bm_qsort(pn-s2, s2/es, es, cmp);
 875       }
 876       if (s1 > es) {
 877          /* bm_qsort(a, s1/es, es, cmp); */
 878          a = a; n = s1/es; es = es; cmp = cmp;
 879          goto tailcall;
 880       }
 881    }
 882 }
 883
 884 #undef BM_MIN
 885 #undef BM_SWAPINIT
 886 #undef BM_EXCH
 887 #undef BM_SWAP
 888 #undef BM_VECSWAP
 889 #undef BM_PVINIT
 890
 891 /// end Bentley-McIlroy style quicksort
 892 /////////////////////////////////////////////////////////////
 893 /////////////////////////////////////////////////////////////
 894
 895 /* Returns the base-2 logarithm of x.  Returns -1 if x is not a power
 896    of two. */
 897 Int VG_(log2) ( UInt x )
 898 {
 899    Int i;
 900    /* Any more than 32 and we overflow anyway... */
 901    for (i = 0; i < 32; i++) {
 902       if ((1U << i) == x) return i;
 903    }
 904    return -1;
 905 }
 906
 907 /* Ditto for 64 bit numbers. */
 908 Int VG_(log2_64) ( ULong x )
 909 {
 910    Int i;
 911    for (i = 0; i < 64; i++) {
 912       if ((1ULL << i) == x) return i;
 913    }
 914    return -1;
 915 }
 916
 917 // Generic quick sort.
 918 void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
 919                  Int (*compar)(const void*, const void*) )
 920 {
 921    bm_qsort(base,nmemb,size,compar);
 922 }
 923
 924
 925 // This random number generator is based on the one suggested in Kernighan
 926 // and Ritchie's "The C Programming Language".
 927
 928 // A pseudo-random number generator returning a random UInt.  If pSeed
 929 // is NULL, it uses its own seed, which starts at zero.  If pSeed is
 930 // non-NULL, it uses and updates whatever pSeed points at.
 931
 932 UInt VG_(random)( /*MOD*/UInt* pSeed )
 933 {
 934    static UInt seed = 0;
 935
 936    if (pSeed == NULL)
 937       pSeed = &seed;
 938
 939    *pSeed = (1103515245 * *pSeed + 12345);
 940    return *pSeed;
 941 }
 942
 943
 944 /* The following Adler-32 checksum code is taken from zlib-1.2.3, which
 945    has the following copyright notice. */
 946 /*
 947 Copyright notice:
 948
 949  (C) 1995-2004 Jean-loup Gailly and Mark Adler
 950
 951   This software is provided 'as-is', without any express or implied
 952   warranty.  In no event will the authors be held liable for any damages
 953   arising from the use of this software.
 954
 955   Permission is granted to anyone to use this software for any purpose,
 956   including commercial applications, and to alter it and redistribute it
 957   freely, subject to the following restrictions:
 958
 959   1. The origin of this software must not be misrepresented; you must not
 960      claim that you wrote the original software. If you use this software
 961      in a product, an acknowledgment in the product documentation would be
 962      appreciated but is not required.
 963   2. Altered source versions must be plainly marked as such, and must not be
 964      misrepresented as being the original software.
 965   3. This notice may not be removed or altered from any source distribution.
 966
 967   Jean-loup Gailly        Mark Adler
 968   jloup@gzip.org          madler@alumni.caltech.edu
 969
 970 If you use the zlib library in a product, we would appreciate *not*
 971 receiving lengthy legal documents to sign. The sources are provided
 972 for free but without warranty of any kind.  The library has been
 973 entirely written by Jean-loup Gailly and Mark Adler; it does not
 974 include third-party code.
 975
 976 If you redistribute modified sources, we would appreciate that you include
 977 in the file ChangeLog history information documenting your changes. Please
 978 read the FAQ for more information on the distribution of modified source
 979 versions.
 980 */
 981
 982 /* Update a running Adler-32 checksum with the bytes buf[0..len-1] and
 983    return the updated checksum. If buf is NULL, this function returns
 984    the required initial value for the checksum. An Adler-32 checksum is
 985    almost as reliable as a CRC32 but can be computed much faster. */
 986 UInt VG_(adler32)( UInt adler, const UChar* buf, UInt len )
 987 {
 988 #  define BASE 65521UL    /* largest prime smaller than 65536 */
 989 #  define NMAX 5552
 990    /* NMAX is the largest n such that
 991       255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
 992
 993 #  define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
 994 #  define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
 995 #  define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
 996 #  define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
 997 #  define DO16(buf)   DO8(buf,0); DO8(buf,8);
 998
 999    /* The zlib sources recommend this definition of MOD if the
1000       processor cannot do integer division in hardware. */
1001 #  define MOD(a) \
1002       do { \
1003           if (a >= (BASE << 16)) a -= (BASE << 16); \
1004           if (a >= (BASE << 15)) a -= (BASE << 15); \
1005           if (a >= (BASE << 14)) a -= (BASE << 14); \
1006           if (a >= (BASE << 13)) a -= (BASE << 13); \
1007           if (a >= (BASE << 12)) a -= (BASE << 12); \
1008           if (a >= (BASE << 11)) a -= (BASE << 11); \
1009           if (a >= (BASE << 10)) a -= (BASE << 10); \
1010           if (a >= (BASE << 9)) a -= (BASE << 9); \
1011           if (a >= (BASE << 8)) a -= (BASE << 8); \
1012           if (a >= (BASE << 7)) a -= (BASE << 7); \
1013           if (a >= (BASE << 6)) a -= (BASE << 6); \
1014           if (a >= (BASE << 5)) a -= (BASE << 5); \
1015           if (a >= (BASE << 4)) a -= (BASE << 4); \
1016           if (a >= (BASE << 3)) a -= (BASE << 3); \
1017           if (a >= (BASE << 2)) a -= (BASE << 2); \
1018           if (a >= (BASE << 1)) a -= (BASE << 1); \
1019           if (a >= BASE) a -= BASE; \
1020       } while (0)
1021 #  define MOD4(a) \
1022       do { \
1023           if (a >= (BASE << 4)) a -= (BASE << 4); \
1024           if (a >= (BASE << 3)) a -= (BASE << 3); \
1025           if (a >= (BASE << 2)) a -= (BASE << 2); \
1026           if (a >= (BASE << 1)) a -= (BASE << 1); \
1027           if (a >= BASE) a -= BASE; \
1028       } while (0)
1029
1030     UInt sum2;
1031     UInt n;
1032
1033     /* split Adler-32 into component sums */
1034     sum2 = (adler >> 16) & 0xffff;
1035     adler &= 0xffff;
1036
1037     /* in case user likes doing a byte at a time, keep it fast */
1038     if (len == 1) {
1039         adler += buf[0];
1040         if (adler >= BASE)
1041             adler -= BASE;
1042         sum2 += adler;
1043         if (sum2 >= BASE)
1044             sum2 -= BASE;
1045         return adler | (sum2 << 16);
1046     }
1047
1048     /* initial Adler-32 value (deferred check for len == 1 speed) */
1049     if (buf == NULL)
1050         return 1L;
1051
1052     /* in case short lengths are provided, keep it somewhat fast */
1053     if (len < 16) {
1054         while (len--) {
1055             adler += *buf++;
1056             sum2 += adler;
1057         }
1058         if (adler >= BASE)
1059             adler -= BASE;
1060         MOD4(sum2);             /* only added so many BASE's */
1061         return adler | (sum2 << 16);
1062     }
1063
1064     /* do length NMAX blocks -- requires just one modulo operation */
1065     while (len >= NMAX) {
1066         len -= NMAX;
1067         n = NMAX / 16;          /* NMAX is divisible by 16 */
1068         do {
1069             DO16(buf);          /* 16 sums unrolled */
1070             buf += 16;
1071         } while (--n);
1072         MOD(adler);
1073         MOD(sum2);
1074     }
1075
1076     /* do remaining bytes (less than NMAX, still just one modulo) */
1077     if (len) {                  /* avoid modulos if none remaining */
1078         while (len >= 16) {
1079             len -= 16;
1080             DO16(buf);
1081             buf += 16;
1082         }
1083         while (len--) {
1084             adler += *buf++;
1085             sum2 += adler;
1086         }
1087         MOD(adler);
1088         MOD(sum2);
1089     }
1090
1091     /* return recombined sums */
1092     return adler | (sum2 << 16);
1093
1094 #  undef MOD4
1095 #  undef MOD
1096 #  undef DO16
1097 #  undef DO8
1098 #  undef DO4
1099 #  undef DO2
1100 #  undef DO1
1101 #  undef NMAX
1102 #  undef BASE
1103 }
1104
1105 /*--------------------------------------------------------------------*/
1106 /*--- end                                                          ---*/
1107 /*--------------------------------------------------------------------*/
1108