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 48static 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 66Bool VG_(isspace) ( HChar c ) 67{ 68 return (c == ' ' || c == '\n' || c == '\t' || 69 c == '\f' || c == '\v' || c == '\r'); 70} 71 72Bool VG_(isdigit) ( HChar c ) 73{ 74 return (c >= '0' && c <= '9'); 75} 76 77/* --------------------------------------------------------------------- 78 Converting strings to numbers 79 ------------------------------------------------------------------ */ 80 81static 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 87static 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 95Long 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 121ULong 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 147Long 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 181ULong 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 215double 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 249HChar 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 262SizeT VG_(strlen) ( const HChar* str ) 263{ 264 SizeT i = 0; 265 while (str[i] != 0) i++; 266 return i; 267} 268 269SizeT 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 277HChar* 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 286HChar* 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 295HChar* 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 308HChar* 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 316HChar* 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. */ 332SizeT 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 353Int 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 366Int 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 381Int 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 396Int 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 415HChar* 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 430HChar* 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 445HChar* 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 454HChar* 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) */ 464static HChar *olds; 465HChar * 466VG_(strtok) (HChar *s, const HChar *delim) 467{ 468 return VG_(strtok_r) (s, delim, &olds); 469} 470 471HChar * 472VG_(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 502static Bool isHex ( HChar c ) 503{ 504 return ((c >= '0' && c <= '9') || 505 (c >= 'a' && c <= 'f') || 506 (c >= 'A' && c <= 'F')); 507} 508 509static 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 522Bool 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 545Bool 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 564Bool 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 641SizeT 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 657SizeT 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 674void* 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 727void* 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 745void* 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 784Int 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 841static 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 848static 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 862static 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. */ 950Int 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. */ 961Int 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. 971void 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 985UInt 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/* 1000Copyright 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 1023If you use the zlib library in a product, we would appreciate *not* 1024receiving lengthy legal documents to sign. The sources are provided 1025for free but without warranty of any kind. The library has been 1026entirely written by Jean-loup Gailly and Mark Adler; it does not 1027include third-party code. 1028 1029If you redistribute modified sources, we would appreciate that you include 1030in the file ChangeLog history information documenting your changes. Please 1031read the FAQ for more information on the distribution of modified source 1032versions. 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. */ 1039UInt 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 1162