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