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-2011 Julian Seward 11 jseward (at) 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 (*s1 == 0 && *s2 == 0) return 0; 307 if (*s1 == 0) return -1; 308 if (*s2 == 0) return 1; 309 310 if (*(UChar*)s1 < *(UChar*)s2) return -1; 311 if (*(UChar*)s1 > *(UChar*)s2) return 1; 312 313 s1++; s2++; 314 } 315 } 316 317 Int VG_(strcasecmp) ( const Char* s1, const Char* s2 ) 318 { 319 while (True) { 320 UChar c1 = (UChar)VG_(tolower)(*s1); 321 UChar c2 = (UChar)VG_(tolower)(*s2); 322 if (c1 == 0 && c2 == 0) return 0; 323 if (c1 == 0) return -1; 324 if (c2 == 0) return 1; 325 326 if (c1 < c2) return -1; 327 if (c1 > c2) return 1; 328 329 s1++; s2++; 330 } 331 } 332 333 Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax ) 334 { 335 SizeT n = 0; 336 while (True) { 337 if (n >= nmax) return 0; 338 if (*s1 == 0 && *s2 == 0) return 0; 339 if (*s1 == 0) return -1; 340 if (*s2 == 0) return 1; 341 342 if (*(UChar*)s1 < *(UChar*)s2) return -1; 343 if (*(UChar*)s1 > *(UChar*)s2) return 1; 344 345 s1++; s2++; n++; 346 } 347 } 348 349 Int VG_(strncasecmp) ( const Char* s1, const Char* s2, SizeT nmax ) 350 { 351 Int n = 0; 352 while (True) { 353 UChar c1; 354 UChar c2; 355 if (n >= nmax) return 0; 356 c1 = (UChar)VG_(tolower)(*s1); 357 c2 = (UChar)VG_(tolower)(*s2); 358 if (c1 == 0 && c2 == 0) return 0; 359 if (c1 == 0) return -1; 360 if (c2 == 0) return 1; 361 362 if (c1 < c2) return -1; 363 if (c1 > c2) return 1; 364 365 s1++; s2++; n++; 366 } 367 } 368 369 Char* VG_(strstr) ( const Char* haystack, Char* needle ) 370 { 371 SizeT n; 372 if (haystack == NULL) 373 return NULL; 374 n = VG_(strlen)(needle); 375 while (True) { 376 if (haystack[0] == 0) 377 return NULL; 378 if (VG_(strncmp)(haystack, needle, n) == 0) 379 return (Char*)haystack; 380 haystack++; 381 } 382 } 383 384 Char* VG_(strcasestr) ( const Char* haystack, Char* needle ) 385 { 386 Int n; 387 if (haystack == NULL) 388 return NULL; 389 n = VG_(strlen)(needle); 390 while (True) { 391 if (haystack[0] == 0) 392 return NULL; 393 if (VG_(strncasecmp)(haystack, needle, n) == 0) 394 return (Char*)haystack; 395 haystack++; 396 } 397 } 398 399 Char* VG_(strchr) ( const Char* s, Char c ) 400 { 401 while (True) { 402 if (*s == c) return (Char*)s; 403 if (*s == 0) return NULL; 404 s++; 405 } 406 } 407 408 Char* VG_(strrchr) ( const Char* s, Char c ) 409 { 410 Int n = VG_(strlen)(s); 411 while (--n > 0) { 412 if (s[n] == c) return (Char*)s + n; 413 } 414 return NULL; 415 } 416 417 /* (code copied from glib then updated to valgrind types) */ 418 static Char *olds; 419 Char * 420 VG_(strtok) (Char *s, const Char *delim) 421 { 422 return VG_(strtok_r) (s, delim, &olds); 423 } 424 425 Char * 426 VG_(strtok_r) (Char* s, const Char* delim, Char** saveptr) 427 { 428 Char *token; 429 430 if (s == NULL) 431 s = *saveptr; 432 433 /* Scan leading delimiters. */ 434 s += VG_(strspn (s, delim)); 435 if (*s == '\0') 436 { 437 *saveptr = s; 438 return NULL; 439 } 440 441 /* Find the end of the token. */ 442 token = s; 443 s = VG_(strpbrk (token, delim)); 444 if (s == NULL) 445 /* This token finishes the string. */ 446 *saveptr = token + VG_(strlen) (token); 447 else 448 { 449 /* Terminate the token and make OLDS point past it. */ 450 *s = '\0'; 451 *saveptr = s + 1; 452 } 453 return token; 454 } 455 456 static Bool isHex ( UChar c ) 457 { 458 return ((c >= '0' && c <= '9') || 459 (c >= 'a' && c <= 'f') || 460 (c >= 'A' && c <= 'F')); 461 } 462 463 static UInt fromHex ( UChar c ) 464 { 465 if (c >= '0' && c <= '9') 466 return (UInt)c - (UInt)'0'; 467 if (c >= 'a' && c <= 'f') 468 return 10 + (UInt)c - (UInt)'a'; 469 if (c >= 'A' && c <= 'F') 470 return 10 + (UInt)c - (UInt)'A'; 471 /*NOTREACHED*/ 472 // ??? need to vg_assert(0); 473 return 0; 474 } 475 476 Bool VG_(parse_Addr) ( UChar** ppc, Addr* result ) 477 { 478 Int used, limit = 2 * sizeof(Addr); 479 if (**ppc != '0') 480 return False; 481 (*ppc)++; 482 if (**ppc != 'x') 483 return False; 484 (*ppc)++; 485 *result = 0; 486 used = 0; 487 while (isHex(**ppc)) { 488 // ??? need to vg_assert(d < fromHex(**ppc)); 489 *result = ((*result) << 4) | fromHex(**ppc); 490 (*ppc)++; 491 used++; 492 if (used > limit) return False; 493 } 494 if (used == 0) 495 return False; 496 return True; 497 } 498 499 SizeT VG_(strspn) ( const Char* s, const Char* accpt ) 500 { 501 const Char *p, *a; 502 SizeT count = 0; 503 for (p = s; *p != '\0'; ++p) { 504 for (a = accpt; *a != '\0'; ++a) 505 if (*p == *a) 506 break; 507 if (*a == '\0') 508 return count; 509 else 510 ++count; 511 } 512 return count; 513 } 514 515 SizeT VG_(strcspn) ( const Char* s, const char* reject ) 516 { 517 SizeT count = 0; 518 while (*s != '\0') { 519 if (VG_(strchr) (reject, *s++) == NULL) 520 ++count; 521 else 522 return count; 523 } 524 return count; 525 } 526 527 528 /* --------------------------------------------------------------------- 529 mem* functions 530 ------------------------------------------------------------------ */ 531 532 void* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) 533 { 534 const UChar* s = (const UChar*)src; 535 UChar* d = (UChar*)dest; 536 const UInt* sI = (const UInt*)src; 537 UInt* dI = (UInt*)dest; 538 539 if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { 540 while (sz >= 16) { 541 dI[0] = sI[0]; 542 dI[1] = sI[1]; 543 dI[2] = sI[2]; 544 dI[3] = sI[3]; 545 sz -= 16; 546 dI += 4; 547 sI += 4; 548 } 549 if (sz == 0) 550 return dest; 551 while (sz >= 4) { 552 dI[0] = sI[0]; 553 sz -= 4; 554 dI += 1; 555 sI += 1; 556 } 557 if (sz == 0) 558 return dest; 559 s = (const UChar*)sI; 560 d = (UChar*)dI; 561 } 562 563 while (sz--) 564 *d++ = *s++; 565 566 return dest; 567 } 568 569 void* VG_(memmove)(void *dest, const void *src, SizeT sz) 570 { 571 SizeT i; 572 if (sz == 0) 573 return dest; 574 if (dest < src) { 575 for (i = 0; i < sz; i++) { 576 ((UChar*)dest)[i] = ((UChar*)src)[i]; 577 } 578 } 579 else if (dest > src) { 580 for (i = 0; i < sz; i++) { 581 ((UChar*)dest)[sz-i-1] = ((UChar*)src)[sz-i-1]; 582 } 583 } 584 return dest; 585 } 586 587 void* VG_(memset) ( void *destV, Int c, SizeT sz ) 588 { 589 Int c4; 590 Char* d = (Char*)destV; 591 while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) { 592 d[0] = c; 593 d++; 594 sz--; 595 } 596 if (sz == 0) 597 return destV; 598 c4 = c & 0xFF; 599 c4 |= (c4 << 8); 600 c4 |= (c4 << 16); 601 while (sz >= 16) { 602 ((Int*)d)[0] = c4; 603 ((Int*)d)[1] = c4; 604 ((Int*)d)[2] = c4; 605 ((Int*)d)[3] = c4; 606 d += 16; 607 sz -= 16; 608 } 609 while (sz >= 4) { 610 ((Int*)d)[0] = c4; 611 d += 4; 612 sz -= 4; 613 } 614 while (sz >= 1) { 615 d[0] = c; 616 d++; 617 sz--; 618 } 619 return destV; 620 } 621 622 Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) 623 { 624 Int res; 625 const UChar *p1 = s1; 626 const UChar *p2 = s2; 627 UChar a0; 628 UChar b0; 629 630 while (n != 0) { 631 a0 = p1[0]; 632 b0 = p2[0]; 633 p1 += 1; 634 p2 += 1; 635 res = a0 - b0; 636 if (res != 0) 637 return res; 638 n -= 1; 639 } 640 return 0; 641 } 642 643 /* --------------------------------------------------------------------- 644 Misc useful functions 645 ------------------------------------------------------------------ */ 646 647 ///////////////////////////////////////////////////////////// 648 ///////////////////////////////////////////////////////////// 649 /// begin Bentley-McIlroy style quicksort 650 /// See "Engineering a Sort Function". Jon L Bentley, M. Douglas 651 /// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993. 652 653 #define BM_MIN(a, b) \ 654 (a) < (b) ? a : b 655 656 #define BM_SWAPINIT(a, es) \ 657 swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \ 658 : es > (SizeT)sizeof(Word) ? 1 \ 659 : 0 660 661 #define BM_EXCH(a, b, t) \ 662 (t = a, a = b, b = t) 663 664 #define BM_SWAP(a, b) \ 665 swaptype != 0 \ 666 ? bm_swapfunc(a, b, es, swaptype) \ 667 : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t) 668 669 #define BM_VECSWAP(a, b, n) \ 670 if (n > 0) bm_swapfunc(a, b, n, swaptype) 671 672 #define BM_PVINIT(pv, pm) \ 673 if (swaptype != 0) \ 674 pv = a, BM_SWAP(pv, pm); \ 675 else \ 676 pv = (Char*)&v, v = *(Word*)pm 677 678 static Char* bm_med3 ( Char* a, Char* b, Char* c, 679 Int (*cmp)(void*,void*) ) { 680 return cmp(a, b) < 0 681 ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) 682 : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); 683 } 684 685 static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype ) 686 { 687 if (swaptype <= 1) { 688 Word t; 689 for ( ; n > 0; a += sizeof(Word), b += sizeof(Word), 690 n -= sizeof(Word)) 691 BM_EXCH(*(Word*)a, *(Word*)b, t); 692 } else { 693 Char t; 694 for ( ; n > 0; a += 1, b += 1, n -= 1) 695 BM_EXCH(*a, *b, t); 696 } 697 } 698 699 static void bm_qsort ( Char* a, SizeT n, SizeT es, 700 Int (*cmp)(void*,void*) ) 701 { 702 Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; 703 Int r, swaptype; 704 Word t, v; 705 SizeT s, s1, s2; 706 tailcall: 707 BM_SWAPINIT(a, es); 708 if (n < 7) { 709 for (pm = a + es; pm < a + n*es; pm += es) 710 for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 711 BM_SWAP(pl, pl-es); 712 return; 713 } 714 pm = a + (n/2)*es; 715 if (n > 7) { 716 pl = a; 717 pn = a + (n-1)*es; 718 if (n > 40) { 719 s = (n/8)*es; 720 pl = bm_med3(pl, pl+s, pl+2*s, cmp); 721 pm = bm_med3(pm-s, pm, pm+s, cmp); 722 pn = bm_med3(pn-2*s, pn-s, pn, cmp); 723 } 724 pm = bm_med3(pl, pm, pn, cmp); 725 } 726 BM_PVINIT(pv, pm); 727 pa = pb = a; 728 pc = pd = a + (n-1)*es; 729 for (;;) { 730 while (pb <= pc && (r = cmp(pb, pv)) <= 0) { 731 if (r == 0) { BM_SWAP(pa, pb); pa += es; } 732 pb += es; 733 } 734 while (pc >= pb && (r = cmp(pc, pv)) >= 0) { 735 if (r == 0) { BM_SWAP(pc, pd); pd -= es; } 736 pc -= es; 737 } 738 if (pb > pc) break; 739 BM_SWAP(pb, pc); 740 pb += es; 741 pc -= es; 742 } 743 pn = a + n*es; 744 s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s); 745 s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s); 746 /* Now recurse. Do the smaller partition first with an explicit 747 recursion, then do the larger partition using a tail call. 748 Except we can't rely on gcc to implement a tail call in any sane 749 way, so simply jump back to the start. This guarantees stack 750 growth can never exceed O(log N) even in the worst case. */ 751 s1 = pb-pa; 752 s2 = pd-pc; 753 if (s1 < s2) { 754 if (s1 > es) { 755 bm_qsort(a, s1/es, es, cmp); 756 } 757 if (s2 > es) { 758 /* bm_qsort(pn-s2, s2/es, es, cmp); */ 759 a = pn-s2; n = s2/es; es = es; cmp = cmp; 760 goto tailcall; 761 } 762 } else { 763 if (s2 > es) { 764 bm_qsort(pn-s2, s2/es, es, cmp); 765 } 766 if (s1 > es) { 767 /* bm_qsort(a, s1/es, es, cmp); */ 768 a = a; n = s1/es; es = es; cmp = cmp; 769 goto tailcall; 770 } 771 } 772 } 773 774 #undef BM_MIN 775 #undef BM_SWAPINIT 776 #undef BM_EXCH 777 #undef BM_SWAP 778 #undef BM_VECSWAP 779 #undef BM_PVINIT 780 781 /// end Bentley-McIlroy style quicksort 782 ///////////////////////////////////////////////////////////// 783 ///////////////////////////////////////////////////////////// 784 785 /* Returns the base-2 logarithm of x. Returns -1 if x is not a power 786 of two. */ 787 Int VG_(log2) ( UInt x ) 788 { 789 Int i; 790 /* Any more than 32 and we overflow anyway... */ 791 for (i = 0; i < 32; i++) { 792 if ((1U << i) == x) return i; 793 } 794 return -1; 795 } 796 797 /* Ditto for 64 bit numbers. */ 798 Int VG_(log2_64) ( ULong x ) 799 { 800 Int i; 801 for (i = 0; i < 64; i++) { 802 if ((1ULL << i) == x) return i; 803 } 804 return -1; 805 } 806 807 // Generic quick sort. 808 void VG_(ssort)( void* base, SizeT nmemb, SizeT size, 809 Int (*compar)(void*, void*) ) 810 { 811 bm_qsort(base,nmemb,size,compar); 812 } 813 814 815 // This random number generator is based on the one suggested in Kernighan 816 // and Ritchie's "The C Programming Language". 817 818 // A pseudo-random number generator returning a random UInt. If pSeed 819 // is NULL, it uses its own seed, which starts at zero. If pSeed is 820 // non-NULL, it uses and updates whatever pSeed points at. 821 822 static UInt seed = 0; 823 824 UInt VG_(random)( /*MOD*/UInt* pSeed ) 825 { 826 if (pSeed == NULL) 827 pSeed = &seed; 828 829 *pSeed = (1103515245 * *pSeed + 12345); 830 return *pSeed; 831 } 832 833 /*--------------------------------------------------------------------*/ 834 /*--- end ---*/ 835 /*--------------------------------------------------------------------*/ 836 837
