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@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 38Bool VG_(isspace) ( Char c ) 39{ 40 return (c == ' ' || c == '\n' || c == '\t' || 41 c == '\f' || c == '\v' || c == '\r'); 42} 43 44Bool VG_(isdigit) ( Char c ) 45{ 46 return (c >= '0' && c <= '9'); 47} 48 49/* --------------------------------------------------------------------- 50 Converting strings to numbers 51 ------------------------------------------------------------------ */ 52 53static 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 59static 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 67Long 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 92ULong 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 117Long 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 150ULong 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 183double 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 216Char 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 229SizeT VG_(strlen) ( const Char* str ) 230{ 231 SizeT i = 0; 232 while (str[i] != 0) i++; 233 return i; 234} 235 236Char* 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 245Char* 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 254Char* 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 267Char* 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. */ 277void 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 289Char* 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 303Int 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 317Int 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 333Int 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 349Int 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 369Char* 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 384Char* 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 399Char* 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 408Char* 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) */ 418static Char *olds; 419Char * 420VG_(strtok) (Char *s, const Char *delim) 421{ 422 return VG_(strtok_r) (s, delim, &olds); 423} 424 425Char * 426VG_(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 456static Bool isHex ( UChar c ) 457{ 458 return ((c >= '0' && c <= '9') || 459 (c >= 'a' && c <= 'f') || 460 (c >= 'A' && c <= 'F')); 461} 462 463static 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 476Bool 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 499SizeT 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 515SizeT 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 532void* 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 569void* 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 587void* 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 622Int 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 678static 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 685static 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 699static 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. */ 787Int 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. */ 798Int 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. 808void 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 822static UInt seed = 0; 823 824UInt 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