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