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-2012 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_libcbase.h"
  33
  34 /* ---------------------------------------------------------------------
  35    Char functions.
  36    ------------------------------------------------------------------ */
  37
  38 Bool VG_(isspace) ( Char c )
  39 {
  40    return (c == ' '  || c == '\n' || c == '\t' ||
  41            c == '\f' || c == '\v' || c == '\r');
  42 }
  43
  44 Bool VG_(isdigit) ( Char c )
  45 {
  46    return (c >= '0' && c <= '9');
  47 }
  48
  49 /* ---------------------------------------------------------------------
  50    Converting strings to numbers
  51    ------------------------------------------------------------------ */
  52
  53 static Bool is_dec_digit(Char c, Long* digit)
  54 {
  55    if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
  56    return False;
  57 }
  58
  59 static Bool is_hex_digit(Char c, Long* digit)
  60 {
  61    if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
  62    if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; }
  63    if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; }
  64    return False;
  65 }
  66
  67 Long VG_(strtoll10) ( Char* str, Char** endptr )
  68 {
  69    Bool neg = False, converted = False;
  70    Long n = 0, digit = 0;
  71    Char* str0 = str;
  72
  73    // Skip leading whitespace.
  74    while (VG_(isspace)(*str)) str++;
  75
  76    // Allow a leading '-' or '+'.
  77    if (*str == '-') { str++; neg = True; }
  78    else if (*str == '+') { str++; }
  79
  80    while (is_dec_digit(*str, &digit)) {
  81       converted = True;          // Ok, we've actually converted a digit.
  82       n = 10*n + digit;
  83       str++;
  84    }
  85
  86    if (!converted) str = str0;   // If nothing converted, endptr points to
  87    if (neg) n = -n;              //   the start of the string.
  88    if (endptr) *endptr = str;    // Record first failing character.
  89    return n;
  90 }
  91
  92 ULong VG_(strtoull10) ( Char* str, Char** endptr )
  93 {
  94    Bool converted = False;
  95    ULong n = 0;
  96    Long digit = 0;
  97    Char* str0 = str;
  98
  99    // Skip leading whitespace.
 100    while (VG_(isspace)(*str)) str++;
 101
 102    // Allow a leading '+'.
 103    if (*str == '+') { str++; }
 104
 105    while (is_dec_digit(*str, &digit)) {
 106       converted = True;          // Ok, we've actually converted a digit.
 107       n = 10*n + digit;
 108       str++;
 109    }
 110
 111    if (!converted) str = str0;   // If nothing converted, endptr points to
 112    //   the start of the string.
 113    if (endptr) *endptr = str;    // Record first failing character.
 114    return n;
 115 }
 116
 117 Long VG_(strtoll16) ( Char* str, Char** endptr )
 118 {
 119    Bool neg = False, converted = False;
 120    Long n = 0, digit = 0;
 121    Char* str0 = str;
 122
 123    // Skip leading whitespace.
 124    while (VG_(isspace)(*str)) str++;
 125
 126    // Allow a leading '-' or '+'.
 127    if (*str == '-') { str++; neg = True; }
 128    else if (*str == '+') { str++; }
 129
 130    // Allow leading "0x", but only if there's a hex digit
 131    // following it.
 132    if (*str == '0'
 133     && (*(str+1) == 'x' || *(str+1) == 'X')
 134     && is_hex_digit( *(str+2), &digit )) {
 135       str += 2;
 136    }
 137
 138    while (is_hex_digit(*str, &digit)) {
 139       converted = True;          // Ok, we've actually converted a digit.
 140       n = 16*n + digit;
 141       str++;
 142    }
 143
 144    if (!converted) str = str0;   // If nothing converted, endptr points to
 145    if (neg) n = -n;              //   the start of the string.
 146    if (endptr) *endptr = str;    // Record first failing character.
 147    return n;
 148 }
 149
 150 ULong VG_(strtoull16) ( Char* str, Char** endptr )
 151 {
 152    Bool converted = False;
 153    ULong n = 0;
 154    Long digit = 0;
 155    Char* str0 = str;
 156
 157    // Skip leading whitespace.
 158    while (VG_(isspace)(*str)) str++;
 159
 160    // Allow a leading '+'.
 161    if (*str == '+') { str++; }
 162
 163    // Allow leading "0x", but only if there's a hex digit
 164    // following it.
 165    if (*str == '0'
 166     && (*(str+1) == 'x' || *(str+1) == 'X')
 167     && is_hex_digit( *(str+2), &digit )) {
 168       str += 2;
 169    }
 170
 171    while (is_hex_digit(*str, &digit)) {
 172       converted = True;          // Ok, we've actually converted a digit.
 173       n = 16*n + digit;
 174       str++;
 175    }
 176
 177    if (!converted) str = str0;   // If nothing converted, endptr points to
 178    //   the start of the string.
 179    if (endptr) *endptr = str;    // Record first failing character.
 180    return n;
 181 }
 182
 183 double VG_(strtod) ( Char* str, Char** endptr )
 184 {
 185    Bool neg = False;
 186    Long digit;
 187    double n = 0, frac = 0, x = 0.1;
 188
 189    // Skip leading whitespace.
 190    while (VG_(isspace)(*str)) str++;
 191
 192    // Allow a leading '-' or '+'.
 193    if (*str == '-') { str++; neg = True; }
 194    else if (*str == '+') { str++; }
 195
 196    while (is_dec_digit(*str, &digit)) {
 197       n = 10*n + digit;
 198       str++;
 199    }
 200
 201    if (*str == '.') {
 202       str++;
 203       while (is_dec_digit(*str, &digit)) {
 204          frac += x*digit;
 205          x /= 10;
 206          str++;
 207       }
 208    }
 209
 210    n += frac;
 211    if (neg) n = -n;
 212    if (endptr) *endptr = str;    // Record first failing character.
 213    return n;
 214 }
 215
 216 Char VG_(tolower) ( Char c )
 217 {
 218    if ( c >= 'A'  &&  c <= 'Z' ) {
 219       return c - 'A' + 'a';
 220    } else {
 221       return c;
 222    }
 223 }
 224
 225 /* ---------------------------------------------------------------------
 226    String functions
 227    ------------------------------------------------------------------ */
 228
 229 SizeT VG_(strlen) ( const Char* str )
 230 {
 231    SizeT i = 0;
 232    while (str[i] != 0) i++;
 233    return i;
 234 }
 235
 236 Char* VG_(strcat) ( Char* dest, const Char* src )
 237 {
 238    Char* dest_orig = dest;
 239    while (*dest) dest++;
 240    while (*src) *dest++ = *src++;
 241    *dest = 0;
 242    return dest_orig;
 243 }
 244
 245 Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n )
 246 {
 247    Char* dest_orig = dest;
 248    while (*dest) dest++;
 249    while (*src && n > 0) { *dest++ = *src++; n--; }
 250    *dest = 0;
 251    return dest_orig;
 252 }
 253
 254 Char* VG_(strpbrk) ( const Char* s, const Char* accpt )
 255 {
 256    const Char* a;
 257    while (*s) {
 258       a = accpt;
 259       while (*a)
 260          if (*a++ == *s)
 261             return (Char *) s;
 262       s++;
 263    }
 264    return NULL;
 265 }
 266
 267 Char* VG_(strcpy) ( Char* dest, const Char* src )
 268 {
 269    Char* dest_orig = dest;
 270    while (*src) *dest++ = *src++;
 271    *dest = 0;
 272    return dest_orig;
 273 }
 274
 275 /* Copy bytes, not overrunning the end of dest and always ensuring
 276    zero termination. */
 277 void VG_(strncpy_safely) ( Char* dest, const Char* src, SizeT ndest )
 278 {
 279    SizeT i = 0;
 280    while (True) {
 281       dest[i] = 0;
 282       if (src[i] == 0) return;
 283       if (i >= ndest-1) return;
 284       dest[i] = src[i];
 285       i++;
 286    }
 287 }
 288
 289 Char* VG_(strncpy) ( Char* dest, const Char* src, SizeT ndest )
 290 {
 291    SizeT i = 0;
 292    while (True) {
 293       if (i >= ndest) return dest;     /* reached limit */
 294       dest[i] = src[i];
 295       if (src[i++] == 0) {
 296          /* reached NUL;  pad rest with zeroes as required */
 297          while (i < ndest) dest[i++] = 0;
 298          return dest;
 299       }
 300    }
 301 }
 302
 303 Int VG_(strcmp) ( const Char* s1, const Char* s2 )
 304 {
 305    while (True) {
 306       if (*(UChar*)s1 < *(UChar*)s2) return -1;
 307       if (*(UChar*)s1 > *(UChar*)s2) return 1;
 308
 309       /* *s1 == *s2 */
 310       if (*s1 == 0) return 0;
 311
 312       s1++; s2++;
 313    }
 314 }
 315
 316 Int VG_(strcasecmp) ( const Char* s1, const Char* s2 )
 317 {
 318    while (True) {
 319       UChar c1 = (UChar)VG_(tolower)(*s1);
 320       UChar c2 = (UChar)VG_(tolower)(*s2);
 321       if (c1 < c2) return -1;
 322       if (c1 > c2) return 1;
 323
 324       /* c1 == c2 */
 325       if (c1 == 0) return 0;
 326
 327       s1++; s2++;
 328    }
 329 }
 330
 331 Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax )
 332 {
 333    SizeT n = 0;
 334    while (True) {
 335       if (n >= nmax) return 0;
 336       if (*(UChar*)s1 < *(UChar*)s2) return -1;
 337       if (*(UChar*)s1 > *(UChar*)s2) return 1;
 338
 339       /* *s1 == *s2 */
 340       if (*s1 == 0) return 0;
 341
 342       s1++; s2++; n++;
 343    }
 344 }
 345
 346 Int VG_(strncasecmp) ( const Char* s1, const Char* s2, SizeT nmax )
 347 {
 348    Int n = 0;
 349    while (True) {
 350       UChar c1;
 351       UChar c2;
 352       if (n >= nmax) return 0;
 353       c1 = (UChar)VG_(tolower)(*s1);
 354       c2 = (UChar)VG_(tolower)(*s2);
 355       if (c1 < c2) return -1;
 356       if (c1 > c2) return 1;
 357
 358       /* c1 == c2 */
 359       if (c1 == 0) return 0;
 360
 361       s1++; s2++; n++;
 362    }
 363 }
 364
 365 Char* VG_(strstr) ( const Char* haystack, const Char* needle )
 366 {
 367    SizeT n;
 368    if (haystack == NULL)
 369       return NULL;
 370    n = VG_(strlen)(needle);
 371    while (True) {
 372       if (haystack[0] == 0)
 373          return NULL;
 374       if (VG_(strncmp)(haystack, needle, n) == 0)
 375          return (Char*)haystack;
 376       haystack++;
 377    }
 378 }
 379
 380 Char* VG_(strcasestr) ( const Char* haystack, const Char* needle )
 381 {
 382    Int n;
 383    if (haystack == NULL)
 384       return NULL;
 385    n = VG_(strlen)(needle);
 386    while (True) {
 387       if (haystack[0] == 0)
 388          return NULL;
 389       if (VG_(strncasecmp)(haystack, needle, n) == 0)
 390          return (Char*)haystack;
 391       haystack++;
 392    }
 393 }
 394
 395 Char* VG_(strchr) ( const Char* s, Char c )
 396 {
 397    while (True) {
 398       if (*s == c) return (Char*)s;
 399       if (*s == 0) return NULL;
 400       s++;
 401    }
 402 }
 403
 404 Char* VG_(strrchr) ( const Char* s, Char c )
 405 {
 406    Int n = VG_(strlen)(s);
 407    while (--n > 0) {
 408       if (s[n] == c) return (Char*)s + n;
 409    }
 410    return NULL;
 411 }
 412
 413 /* (code copied from glib then updated to valgrind types) */
 414 static Char *olds;
 415 Char *
 416 VG_(strtok) (Char *s, const Char *delim)
 417 {
 418    return VG_(strtok_r) (s, delim, &olds);
 419 }
 420
 421 Char *
 422 VG_(strtok_r) (Char* s, const Char* delim, Char** saveptr)
 423 {
 424    Char *token;
 425
 426    if (s == NULL)
 427       s = *saveptr;
 428
 429    /* Scan leading delimiters.  */
 430    s += VG_(strspn (s, delim));
 431    if (*s == '\0')
 432       {
 433          *saveptr = s;
 434          return NULL;
 435       }
 436
 437    /* Find the end of the token.  */
 438    token = s;
 439    s = VG_(strpbrk (token, delim));
 440    if (s == NULL)
 441       /* This token finishes the string.  */
 442       *saveptr = token + VG_(strlen) (token);
 443    else
 444       {
 445          /* Terminate the token and make OLDS point past it.  */
 446          *s = '\0';
 447          *saveptr = s + 1;
 448       }
 449    return token;
 450 }
 451
 452 static Bool isHex ( UChar c )
 453 {
 454   return ((c >= '0' && c <= '9') ||
 455           (c >= 'a' && c <= 'f') ||
 456           (c >= 'A' && c <= 'F'));
 457 }
 458
 459 static UInt fromHex ( UChar c )
 460 {
 461    if (c >= '0' && c <= '9')
 462       return (UInt)c - (UInt)'0';
 463    if (c >= 'a' && c <= 'f')
 464       return 10 +  (UInt)c - (UInt)'a';
 465    if (c >= 'A' && c <= 'F')
 466       return 10 +  (UInt)c - (UInt)'A';
 467    /*NOTREACHED*/
 468    // ??? need to vg_assert(0);
 469    return 0;
 470 }
 471
 472 Bool VG_(parse_Addr) ( UChar** ppc, Addr* result )
 473 {
 474    Int used, limit = 2 * sizeof(Addr);
 475    if (**ppc != '0')
 476       return False;
 477    (*ppc)++;
 478    if (**ppc != 'x')
 479       return False;
 480    (*ppc)++;
 481    *result = 0;
 482    used = 0;
 483    while (isHex(**ppc)) {
 484       // ??? need to vg_assert(d < fromHex(**ppc));
 485       *result = ((*result) << 4) | fromHex(**ppc);
 486       (*ppc)++;
 487       used++;
 488       if (used > limit) return False;
 489    }
 490    if (used == 0)
 491       return False;
 492    return True;
 493 }
 494
 495 SizeT VG_(strspn) ( const Char* s, const Char* accpt )
 496 {
 497    const Char *p, *a;
 498    SizeT count = 0;
 499    for (p = s; *p != '\0'; ++p) {
 500       for (a = accpt; *a != '\0'; ++a)
 501          if (*p == *a)
 502             break;
 503       if (*a == '\0')
 504          return count;
 505       else
 506          ++count;
 507    }
 508    return count;
 509 }
 510
 511 SizeT VG_(strcspn) ( const Char* s, const Char* reject )
 512 {
 513    SizeT count = 0;
 514    while (*s != '\0') {
 515       if (VG_(strchr) (reject, *s++) == NULL)
 516          ++count;
 517       else
 518          return count;
 519    }
 520    return count;
 521 }
 522
 523
 524 /* ---------------------------------------------------------------------
 525    mem* functions
 526    ------------------------------------------------------------------ */
 527
 528 void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
 529 {
 530    const UChar* s  = (const UChar*)src;
 531          UChar* d  =       (UChar*)dest;
 532    const UInt*  sI = (const UInt*)src;
 533          UInt*  dI =       (UInt*)dest;
 534
 535    if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
 536       while (sz >= 16) {
 537          dI[0] = sI[0];
 538          dI[1] = sI[1];
 539          dI[2] = sI[2];
 540          dI[3] = sI[3];
 541          sz -= 16;
 542          dI += 4;
 543          sI += 4;
 544       }
 545       if (sz == 0)
 546          return dest;
 547       while (sz >= 4) {
 548          dI[0] = sI[0];
 549          sz -= 4;
 550          dI += 1;
 551          sI += 1;
 552       }
 553       if (sz == 0)
 554          return dest;
 555       s = (const UChar*)sI;
 556       d = (UChar*)dI;
 557    }
 558
 559    while (sz--)
 560       *d++ = *s++;
 561
 562    return dest;
 563 }
 564
 565 void* VG_(memmove)(void *dest, const void *src, SizeT sz)
 566 {
 567    SizeT i;
 568    if (sz == 0)
 569       return dest;
 570    if (dest < src) {
 571       for (i = 0; i < sz; i++) {
 572          ((UChar*)dest)[i] = ((UChar*)src)[i];
 573       }
 574    }
 575    else if (dest > src) {
 576       for (i = 0; i < sz; i++) {
 577          ((UChar*)dest)[sz-i-1] = ((UChar*)src)[sz-i-1];
 578       }
 579    }
 580    return dest;
 581 }
 582
 583 void* VG_(memset) ( void *destV, Int c, SizeT sz )
 584 {
 585    Int   c4;
 586    Char* d = (Char*)destV;
 587    while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) {
 588       d[0] = c;
 589       d++;
 590       sz--;
 591    }
 592    if (sz == 0)
 593       return destV;
 594    c4 = c & 0xFF;
 595    c4 |= (c4 << 8);
 596    c4 |= (c4 << 16);
 597    while (sz >= 16) {
 598       ((Int*)d)[0] = c4;
 599       ((Int*)d)[1] = c4;
 600       ((Int*)d)[2] = c4;
 601       ((Int*)d)[3] = c4;
 602       d += 16;
 603       sz -= 16;
 604    }
 605    while (sz >= 4) {
 606       ((Int*)d)[0] = c4;
 607       d += 4;
 608       sz -= 4;
 609    }
 610    while (sz >= 1) {
 611       d[0] = c;
 612       d++;
 613       sz--;
 614    }
 615    return destV;
 616 }
 617
 618 Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
 619 {
 620    Int res;
 621    const UChar *p1 = s1;
 622    const UChar *p2 = s2;
 623    UChar a0;
 624    UChar b0;
 625
 626    while (n != 0) {
 627       a0 = p1[0];
 628       b0 = p2[0];
 629       p1 += 1;
 630       p2 += 1;
 631       res = a0 - b0;
 632       if (res != 0)
 633          return res;
 634       n -= 1;
 635    }
 636    return 0;
 637 }
 638
 639 /* ---------------------------------------------------------------------
 640    Misc useful functions
 641    ------------------------------------------------------------------ */
 642
 643 /////////////////////////////////////////////////////////////
 644 /////////////////////////////////////////////////////////////
 645 /// begin Bentley-McIlroy style quicksort
 646 /// See "Engineering a Sort Function".  Jon L Bentley, M. Douglas
 647 /// McIlroy.  Software Practice and Experience Vol 23(11), Nov 1993.
 648
 649 #define BM_MIN(a, b)                                     \
 650    (a) < (b) ? a : b
 651
 652 #define BM_SWAPINIT(a, es)                               \
 653    swaptype =   ((a-(Char*)0) | es) % sizeof(Word)  ? 2  \
 654               : es > (SizeT)sizeof(Word) ? 1             \
 655               : 0
 656
 657 #define BM_EXCH(a, b, t)                                 \
 658    (t = a, a = b, b = t)
 659
 660 #define BM_SWAP(a, b)                                    \
 661    swaptype != 0                                         \
 662       ? bm_swapfunc(a, b, es, swaptype)                  \
 663       : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t)
 664
 665 #define BM_VECSWAP(a, b, n)                              \
 666    if (n > 0) bm_swapfunc(a, b, n, swaptype)
 667
 668 #define BM_PVINIT(pv, pm)                                \
 669    if (swaptype != 0)                                    \
 670       pv = a, BM_SWAP(pv, pm);                           \
 671    else                                                  \
 672       pv = (Char*)&v, v = *(Word*)pm
 673
 674 static Char* bm_med3 ( Char* a, Char* b, Char* c,
 675                        Int (*cmp)(void*,void*) ) {
 676    return cmp(a, b) < 0
 677           ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
 678           : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
 679 }
 680
 681 static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
 682 {
 683    if (swaptype <= 1) {
 684       Word t;
 685       for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
 686                                         n -= sizeof(Word))
 687          BM_EXCH(*(Word*)a, *(Word*)b, t);
 688    } else {
 689       Char t;
 690       for ( ; n > 0; a += 1, b += 1, n -= 1)
 691          BM_EXCH(*a, *b, t);
 692    }
 693 }
 694
 695 static void bm_qsort ( Char* a, SizeT n, SizeT es,
 696                        Int (*cmp)(void*,void*) )
 697 {
 698    Char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
 699    Int   r, swaptype;
 700    Word  t, v;
 701    SizeT s, s1, s2;
 702   tailcall:
 703    BM_SWAPINIT(a, es);
 704    if (n < 7) {
 705       for (pm = a + es; pm < a + n*es; pm += es)
 706          for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
 707             BM_SWAP(pl, pl-es);
 708       return;
 709    }
 710    pm = a + (n/2)*es;
 711    if (n > 7) {
 712       pl = a;
 713       pn = a + (n-1)*es;
 714       if (n > 40) {
 715          s = (n/8)*es;
 716          pl = bm_med3(pl, pl+s, pl+2*s, cmp);
 717          pm = bm_med3(pm-s, pm, pm+s, cmp);
 718          pn = bm_med3(pn-2*s, pn-s, pn, cmp);
 719       }
 720       pm = bm_med3(pl, pm, pn, cmp);
 721    }
 722    BM_PVINIT(pv, pm);
 723    pa = pb = a;
 724    pc = pd = a + (n-1)*es;
 725    for (;;) {
 726       while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
 727          if (r == 0) { BM_SWAP(pa, pb); pa += es; }
 728          pb += es;
 729       }
 730       while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
 731          if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
 732          pc -= es;
 733       }
 734       if (pb > pc) break;
 735       BM_SWAP(pb, pc);
 736       pb += es;
 737       pc -= es;
 738    }
 739    pn = a + n*es;
 740    s = BM_MIN(pa-a,  pb-pa   ); BM_VECSWAP(a,  pb-s, s);
 741    s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
 742    /* Now recurse.  Do the smaller partition first with an explicit
 743       recursion, then do the larger partition using a tail call.
 744       Except we can't rely on gcc to implement a tail call in any sane
 745       way, so simply jump back to the start.  This guarantees stack
 746       growth can never exceed O(log N) even in the worst case. */
 747    s1 = pb-pa;
 748    s2 = pd-pc;
 749    if (s1 < s2) {
 750       if (s1 > es) {
 751          bm_qsort(a, s1/es, es, cmp);
 752       }
 753       if (s2 > es) {
 754          /* bm_qsort(pn-s2, s2/es, es, cmp); */
 755          a = pn-s2; n = s2/es; es = es; cmp = cmp;
 756          goto tailcall;
 757       }
 758    } else {
 759       if (s2 > es) {
 760          bm_qsort(pn-s2, s2/es, es, cmp);
 761       }
 762       if (s1 > es) {
 763          /* bm_qsort(a, s1/es, es, cmp); */
 764          a = a; n = s1/es; es = es; cmp = cmp;
 765          goto tailcall;
 766       }
 767    }
 768 }
 769
 770 #undef BM_MIN
 771 #undef BM_SWAPINIT
 772 #undef BM_EXCH
 773 #undef BM_SWAP
 774 #undef BM_VECSWAP
 775 #undef BM_PVINIT
 776
 777 /// end Bentley-McIlroy style quicksort
 778 /////////////////////////////////////////////////////////////
 779 /////////////////////////////////////////////////////////////
 780
 781 /* Returns the base-2 logarithm of x.  Returns -1 if x is not a power
 782    of two. */
 783 Int VG_(log2) ( UInt x )
 784 {
 785    Int i;
 786    /* Any more than 32 and we overflow anyway... */
 787    for (i = 0; i < 32; i++) {
 788       if ((1U << i) == x) return i;
 789    }
 790    return -1;
 791 }
 792
 793 /* Ditto for 64 bit numbers. */
 794 Int VG_(log2_64) ( ULong x )
 795 {
 796    Int i;
 797    for (i = 0; i < 64; i++) {
 798       if ((1ULL << i) == x) return i;
 799    }
 800    return -1;
 801 }
 802
 803 // Generic quick sort.
 804 void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
 805                  Int (*compar)(void*, void*) )
 806 {
 807    bm_qsort(base,nmemb,size,compar);
 808 }
 809
 810
 811 // This random number generator is based on the one suggested in Kernighan
 812 // and Ritchie's "The C Programming Language".
 813
 814 // A pseudo-random number generator returning a random UInt.  If pSeed
 815 // is NULL, it uses its own seed, which starts at zero.  If pSeed is
 816 // non-NULL, it uses and updates whatever pSeed points at.
 817
 818 static UInt seed = 0;
 819
 820 UInt VG_(random)( /*MOD*/UInt* pSeed )
 821 {
 822    if (pSeed == NULL)
 823       pSeed = &seed;
 824
 825    *pSeed = (1103515245 * *pSeed + 12345);
 826    return *pSeed;
 827 }
 828
 829 /*--------------------------------------------------------------------*/
 830 /*--- end                                                          ---*/
 831 /*--------------------------------------------------------------------*/
 832