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 (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 (*(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, 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, 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 833
