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-2015 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_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 48 static 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 66 Bool VG_(isspace) ( HChar c ) 67 { 68 return (c == ' ' || c == '\n' || c == '\t' || 69 c == '\f' || c == '\v' || c == '\r'); 70 } 71 72 Bool VG_(isdigit) ( HChar c ) 73 { 74 return (c >= '0' && c <= '9'); 75 } 76 77 /* --------------------------------------------------------------------- 78 Converting strings to numbers 79 ------------------------------------------------------------------ */ 80 81 static 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 87 static 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 95 Long 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 121 ULong 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 147 Long 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 181 ULong 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 215 double 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 249 HChar 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 262 SizeT VG_(strlen) ( const HChar* str ) 263 { 264 SizeT i = 0; 265 while (str[i] != 0) i++; 266 return i; 267 } 268 269 HChar* VG_(strcat) ( HChar* dest, const HChar* src ) 270 { 271 HChar* dest_orig = dest; 272 while (*dest) dest++; 273 while (*src) *dest++ = *src++; 274 *dest = 0; 275 return dest_orig; 276 } 277 278 HChar* VG_(strncat) ( HChar* dest, const HChar* src, SizeT n ) 279 { 280 HChar* dest_orig = dest; 281 while (*dest) dest++; 282 while (*src && n > 0) { *dest++ = *src++; n--; } 283 *dest = 0; 284 return dest_orig; 285 } 286 287 HChar* VG_(strpbrk) ( const HChar* s, const HChar* accpt ) 288 { 289 const HChar* a; 290 while (*s) { 291 a = accpt; 292 while (*a) 293 if (*a++ == *s) 294 return CONST_CAST(HChar *,s); 295 s++; 296 } 297 return NULL; 298 } 299 300 HChar* VG_(strcpy) ( HChar* dest, const HChar* src ) 301 { 302 HChar* dest_orig = dest; 303 while (*src) *dest++ = *src++; 304 *dest = 0; 305 return dest_orig; 306 } 307 308 HChar* VG_(strncpy) ( HChar* dest, const HChar* src, SizeT ndest ) 309 { 310 SizeT i = 0; 311 while (True) { 312 if (i >= ndest) return dest; /* reached limit */ 313 dest[i] = src[i]; 314 if (src[i++] == 0) { 315 /* reached NUL; pad rest with zeroes as required */ 316 while (i < ndest) dest[i++] = 0; 317 return dest; 318 } 319 } 320 } 321 322 Int VG_(strcmp) ( const HChar* s1, const HChar* s2 ) 323 { 324 while (True) { 325 if (*(const UChar*)s1 < *(const UChar*)s2) return -1; 326 if (*(const UChar*)s1 > *(const UChar*)s2) return 1; 327 328 /* *s1 == *s2 */ 329 if (*s1 == 0) return 0; 330 331 s1++; s2++; 332 } 333 } 334 335 Int VG_(strcasecmp) ( const HChar* s1, const HChar* s2 ) 336 { 337 while (True) { 338 UChar c1 = (UChar)VG_(tolower)(*s1); 339 UChar c2 = (UChar)VG_(tolower)(*s2); 340 if (c1 < c2) return -1; 341 if (c1 > c2) return 1; 342 343 /* c1 == c2 */ 344 if (c1 == 0) return 0; 345 346 s1++; s2++; 347 } 348 } 349 350 Int VG_(strncmp) ( const HChar* s1, const HChar* s2, SizeT nmax ) 351 { 352 SizeT n = 0; 353 while (True) { 354 if (n >= nmax) return 0; 355 if (*(const UChar*)s1 < *(const UChar*)s2) return -1; 356 if (*(const UChar*)s1 > *(const UChar*)s2) return 1; 357 358 /* *s1 == *s2 */ 359 if (*s1 == 0) return 0; 360 361 s1++; s2++; n++; 362 } 363 } 364 365 Int VG_(strncasecmp) ( const HChar* s1, const HChar* s2, SizeT nmax ) 366 { 367 Int n = 0; 368 while (True) { 369 UChar c1; 370 UChar c2; 371 if (n >= nmax) return 0; 372 c1 = (UChar)VG_(tolower)(*s1); 373 c2 = (UChar)VG_(tolower)(*s2); 374 if (c1 < c2) return -1; 375 if (c1 > c2) return 1; 376 377 /* c1 == c2 */ 378 if (c1 == 0) return 0; 379 380 s1++; s2++; n++; 381 } 382 } 383 384 HChar* VG_(strstr) ( const HChar* haystack, const HChar* needle ) 385 { 386 SizeT 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_(strncmp)(haystack, needle, n) == 0) 394 return CONST_CAST(HChar *,haystack); 395 haystack++; 396 } 397 } 398 399 HChar* VG_(strcasestr) ( const HChar* haystack, const HChar* needle ) 400 { 401 Int n; 402 if (haystack == NULL) 403 return NULL; 404 n = VG_(strlen)(needle); 405 while (True) { 406 if (haystack[0] == 0) 407 return NULL; 408 if (VG_(strncasecmp)(haystack, needle, n) == 0) 409 return CONST_CAST(HChar *,haystack); 410 haystack++; 411 } 412 } 413 414 HChar* VG_(strchr) ( const HChar* s, HChar c ) 415 { 416 while (True) { 417 if (*s == c) return CONST_CAST(HChar *,s); 418 if (*s == 0) return NULL; 419 s++; 420 } 421 } 422 423 HChar* VG_(strrchr) ( const HChar* s, HChar c ) 424 { 425 Int n = VG_(strlen)(s); 426 while (--n > 0) { 427 if (s[n] == c) return CONST_CAST(HChar *,s) + n; 428 } 429 return NULL; 430 } 431 432 /* (code copied from glib then updated to valgrind types) */ 433 static HChar *olds; 434 HChar * 435 VG_(strtok) (HChar *s, const HChar *delim) 436 { 437 return VG_(strtok_r) (s, delim, &olds); 438 } 439 440 HChar * 441 VG_(strtok_r) (HChar* s, const HChar* delim, HChar** saveptr) 442 { 443 HChar *token; 444 445 if (s == NULL) 446 s = *saveptr; 447 448 /* Scan leading delimiters. */ 449 s += VG_(strspn (s, delim)); 450 if (*s == '\0') 451 { 452 *saveptr = s; 453 return NULL; 454 } 455 456 /* Find the end of the token. */ 457 token = s; 458 s = VG_(strpbrk (token, delim)); 459 if (s == NULL) 460 /* This token finishes the string. */ 461 *saveptr = token + VG_(strlen) (token); 462 else 463 { 464 /* Terminate the token and make OLDS point past it. */ 465 *s = '\0'; 466 *saveptr = s + 1; 467 } 468 return token; 469 } 470 471 static Bool isHex ( HChar c ) 472 { 473 return ((c >= '0' && c <= '9') || 474 (c >= 'a' && c <= 'f') || 475 (c >= 'A' && c <= 'F')); 476 } 477 478 static UInt fromHex ( HChar c ) 479 { 480 if (c >= '0' && c <= '9') 481 return (UInt)c - (UInt)'0'; 482 if (c >= 'a' && c <= 'f') 483 return 10 + (UInt)c - (UInt)'a'; 484 if (c >= 'A' && c <= 'F') 485 return 10 + (UInt)c - (UInt)'A'; 486 /*NOTREACHED*/ 487 // ??? need to vg_assert(0); 488 return 0; 489 } 490 491 Bool VG_(parse_Addr) ( const HChar** ppc, Addr* result ) 492 { 493 Int used, limit = 2 * sizeof(Addr); 494 if (**ppc != '0') 495 return False; 496 (*ppc)++; 497 if (**ppc != 'x') 498 return False; 499 (*ppc)++; 500 *result = 0; 501 used = 0; 502 while (isHex(**ppc)) { 503 // ??? need to vg_assert(d < fromHex(**ppc)); 504 *result = ((*result) << 4) | fromHex(**ppc); 505 (*ppc)++; 506 used++; 507 if (used > limit) return False; 508 } 509 if (used == 0) 510 return False; 511 return True; 512 } 513 514 Bool VG_(parse_enum_set) ( const HChar *tokens, 515 Bool allow_all, 516 const HChar *input, 517 UInt *enum_set) 518 { 519 const SizeT tokens_len = VG_(strlen)(tokens); 520 if (tokens_len > 1000) return False; /* "obviously invalid" */ 521 HChar tok_tokens[tokens_len+1]; 522 HChar *tokens_saveptr; 523 HChar *token; 524 UInt token_nr = 0; 525 UInt all_set = 0; 526 527 const SizeT input_len = VG_(strlen)(input); 528 if (input_len > 1000) return False; /* "obviously invalid" */ 529 HChar tok_input[input_len+1]; 530 HChar *input_saveptr; 531 HChar *input_word; 532 UInt word_nr = 0; 533 UInt known_words = 0; 534 Bool seen_all_kw = False; 535 Bool seen_none_kw = False; 536 537 *enum_set = 0; 538 539 VG_(strcpy) (tok_input, input); 540 for (input_word = VG_(strtok_r)(tok_input, ",", &input_saveptr); 541 input_word; 542 input_word = VG_(strtok_r)(NULL, ",", &input_saveptr)) { 543 word_nr++; 544 if (allow_all && 0 == VG_(strcmp)(input_word, "all")) { 545 seen_all_kw = True; 546 known_words++; 547 } else if (0 == VG_(strcmp)(input_word, "none")) { 548 seen_none_kw = True; 549 known_words++; 550 } 551 552 // Scan tokens + compute all_set. Do that even if all or none was 553 // recognised to have a correct value for all_set when exiting 554 // of the 'input' loop. 555 all_set = 0; 556 token_nr = 0; 557 VG_(strcpy) (tok_tokens, tokens); 558 for (token = VG_(strtok_r)(tok_tokens, ",", &tokens_saveptr); 559 token; 560 token = VG_(strtok_r)(NULL, ",", &tokens_saveptr)) { 561 if (0 != VG_(strcmp)(token, "-")) { 562 if (0 == VG_(strcmp)(input_word, token)) { 563 *enum_set |= 1 << token_nr; 564 known_words++; 565 } 566 all_set |= 1 << token_nr; 567 } 568 token_nr++; 569 } 570 } 571 572 if (known_words != word_nr) 573 return False; // One or more input_words not recognised. 574 if (seen_all_kw) { 575 if (seen_none_kw || *enum_set) 576 return False; // mixing all with either none or a specific value. 577 *enum_set = all_set; 578 } else if (seen_none_kw) { 579 if (seen_all_kw || *enum_set) 580 return False; // mixing none with either all or a specific value. 581 *enum_set = 0; 582 } else { 583 // seen neither all or none, we must see at least one value 584 if (*enum_set == 0) 585 return False; 586 } 587 588 return True; 589 } 590 591 SizeT VG_(strspn) ( const HChar* s, const HChar* accpt ) 592 { 593 const HChar *p, *a; 594 SizeT count = 0; 595 for (p = s; *p != '\0'; ++p) { 596 for (a = accpt; *a != '\0'; ++a) 597 if (*p == *a) 598 break; 599 if (*a == '\0') 600 return count; 601 else 602 ++count; 603 } 604 return count; 605 } 606 607 SizeT VG_(strcspn) ( const HChar* s, const HChar* reject ) 608 { 609 SizeT count = 0; 610 while (*s != '\0') { 611 if (VG_(strchr) (reject, *s++) == NULL) 612 ++count; 613 else 614 return count; 615 } 616 return count; 617 } 618 619 620 /* --------------------------------------------------------------------- 621 mem* functions 622 ------------------------------------------------------------------ */ 623 624 void* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) 625 { 626 const UChar* s = (const UChar*)src; 627 UChar* d = (UChar*)dest; 628 const UInt* sI = (const UInt*)src; 629 UInt* dI = (UInt*)dest; 630 631 if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { 632 while (sz >= 16) { 633 dI[0] = sI[0]; 634 dI[1] = sI[1]; 635 dI[2] = sI[2]; 636 dI[3] = sI[3]; 637 sz -= 16; 638 dI += 4; 639 sI += 4; 640 } 641 if (sz == 0) 642 return dest; 643 while (sz >= 4) { 644 dI[0] = sI[0]; 645 sz -= 4; 646 dI += 1; 647 sI += 1; 648 } 649 if (sz == 0) 650 return dest; 651 s = (const UChar*)sI; 652 d = (UChar*)dI; 653 } 654 655 /* If we're unlucky, the alignment constraints for the fast case 656 above won't apply, and we'll have to do it all here. Hence the 657 unrolling. */ 658 while (sz >= 4) { 659 d[0] = s[0]; 660 d[1] = s[1]; 661 d[2] = s[2]; 662 d[3] = s[3]; 663 d += 4; 664 s += 4; 665 sz -= 4; 666 } 667 while (sz >= 1) { 668 d[0] = s[0]; 669 d += 1; 670 s += 1; 671 sz -= 1; 672 } 673 674 return dest; 675 } 676 677 void* VG_(memmove)(void *dest, const void *src, SizeT sz) 678 { 679 SizeT i; 680 if (sz == 0) 681 return dest; 682 if (dest < src) { 683 for (i = 0; i < sz; i++) { 684 ((UChar*)dest)[i] = ((const UChar*)src)[i]; 685 } 686 } 687 else if (dest > src) { 688 for (i = 0; i < sz; i++) { 689 ((UChar*)dest)[sz-i-1] = ((const UChar*)src)[sz-i-1]; 690 } 691 } 692 return dest; 693 } 694 695 void* VG_(memset) ( void *destV, Int c, SizeT sz ) 696 { 697 UInt c4; 698 UChar* d = destV; 699 UChar uc = c; 700 701 while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) { 702 d[0] = uc; 703 d++; 704 sz--; 705 } 706 if (sz == 0) 707 return destV; 708 c4 = uc; 709 c4 |= (c4 << 8); 710 c4 |= (c4 << 16); 711 while (sz >= 16) { 712 ((UInt*)d)[0] = c4; 713 ((UInt*)d)[1] = c4; 714 ((UInt*)d)[2] = c4; 715 ((UInt*)d)[3] = c4; 716 d += 16; 717 sz -= 16; 718 } 719 while (sz >= 4) { 720 ((UInt*)d)[0] = c4; 721 d += 4; 722 sz -= 4; 723 } 724 while (sz >= 1) { 725 d[0] = c; 726 d++; 727 sz--; 728 } 729 return destV; 730 } 731 732 Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) 733 { 734 Int res; 735 const UChar *p1 = s1; 736 const UChar *p2 = s2; 737 UChar a0; 738 UChar b0; 739 740 while (n != 0) { 741 a0 = p1[0]; 742 b0 = p2[0]; 743 p1 += 1; 744 p2 += 1; 745 res = a0 - b0; 746 if (res != 0) 747 return res; 748 n -= 1; 749 } 750 return 0; 751 } 752 753 /* --------------------------------------------------------------------- 754 Misc useful functions 755 ------------------------------------------------------------------ */ 756 757 ///////////////////////////////////////////////////////////// 758 ///////////////////////////////////////////////////////////// 759 /// begin Bentley-McIlroy style quicksort 760 /// See "Engineering a Sort Function". Jon L Bentley, M. Douglas 761 /// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993. 762 763 #define BM_MIN(a, b) \ 764 (a) < (b) ? a : b 765 766 #define BM_SWAPINIT(a, es) \ 767 swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \ 768 : es > (SizeT)sizeof(Word) ? 1 \ 769 : 0 770 771 #define BM_EXCH(a, b, t) \ 772 (t = a, a = b, b = t) 773 774 #define BM_SWAP(a, b) \ 775 swaptype != 0 \ 776 ? bm_swapfunc(a, b, es, swaptype) \ 777 : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t) 778 779 #define BM_VECSWAP(a, b, n) \ 780 if (n > 0) bm_swapfunc(a, b, n, swaptype) 781 782 #define BM_PVINIT(pv, pm) \ 783 if (swaptype != 0) \ 784 pv = a, BM_SWAP(pv, pm); \ 785 else \ 786 pv = (Char*)&v, v = *(Word*)pm 787 788 static Char* bm_med3 ( Char* a, Char* b, Char* c, 789 Int (*cmp)(const void*, const void*) ) { 790 return cmp(a, b) < 0 791 ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) 792 : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); 793 } 794 795 static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype ) 796 { 797 if (swaptype <= 1) { 798 Word t; 799 for ( ; n > 0; a += sizeof(Word), b += sizeof(Word), 800 n -= sizeof(Word)) 801 BM_EXCH(*(Word*)a, *(Word*)b, t); 802 } else { 803 Char t; 804 for ( ; n > 0; a += 1, b += 1, n -= 1) 805 BM_EXCH(*a, *b, t); 806 } 807 } 808 809 static void bm_qsort ( Char* a, SizeT n, SizeT es, 810 Int (*cmp)(const void*, const void*) ) 811 { 812 Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; 813 Int r, swaptype; 814 Word t, v; 815 SizeT s, s1, s2; 816 tailcall: 817 BM_SWAPINIT(a, es); 818 if (n < 7) { 819 for (pm = a + es; pm < a + n*es; pm += es) 820 for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 821 BM_SWAP(pl, pl-es); 822 return; 823 } 824 pm = a + (n/2)*es; 825 if (n > 7) { 826 pl = a; 827 pn = a + (n-1)*es; 828 if (n > 40) { 829 s = (n/8)*es; 830 pl = bm_med3(pl, pl+s, pl+2*s, cmp); 831 pm = bm_med3(pm-s, pm, pm+s, cmp); 832 pn = bm_med3(pn-2*s, pn-s, pn, cmp); 833 } 834 pm = bm_med3(pl, pm, pn, cmp); 835 } 836 BM_PVINIT(pv, pm); 837 pa = pb = a; 838 pc = pd = a + (n-1)*es; 839 for (;;) { 840 while (pb <= pc && (r = cmp(pb, pv)) <= 0) { 841 if (r == 0) { BM_SWAP(pa, pb); pa += es; } 842 pb += es; 843 } 844 while (pc >= pb && (r = cmp(pc, pv)) >= 0) { 845 if (r == 0) { BM_SWAP(pc, pd); pd -= es; } 846 pc -= es; 847 } 848 if (pb > pc) break; 849 BM_SWAP(pb, pc); 850 pb += es; 851 pc -= es; 852 } 853 pn = a + n*es; 854 s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s); 855 s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s); 856 /* Now recurse. Do the smaller partition first with an explicit 857 recursion, then do the larger partition using a tail call. 858 Except we can't rely on gcc to implement a tail call in any sane 859 way, so simply jump back to the start. This guarantees stack 860 growth can never exceed O(log N) even in the worst case. */ 861 s1 = pb-pa; 862 s2 = pd-pc; 863 if (s1 < s2) { 864 if (s1 > es) { 865 bm_qsort(a, s1/es, es, cmp); 866 } 867 if (s2 > es) { 868 /* bm_qsort(pn-s2, s2/es, es, cmp); */ 869 a = pn-s2; n = s2/es; es = es; cmp = cmp; 870 goto tailcall; 871 } 872 } else { 873 if (s2 > es) { 874 bm_qsort(pn-s2, s2/es, es, cmp); 875 } 876 if (s1 > es) { 877 /* bm_qsort(a, s1/es, es, cmp); */ 878 a = a; n = s1/es; es = es; cmp = cmp; 879 goto tailcall; 880 } 881 } 882 } 883 884 #undef BM_MIN 885 #undef BM_SWAPINIT 886 #undef BM_EXCH 887 #undef BM_SWAP 888 #undef BM_VECSWAP 889 #undef BM_PVINIT 890 891 /// end Bentley-McIlroy style quicksort 892 ///////////////////////////////////////////////////////////// 893 ///////////////////////////////////////////////////////////// 894 895 /* Returns the base-2 logarithm of x. Returns -1 if x is not a power 896 of two. */ 897 Int VG_(log2) ( UInt x ) 898 { 899 Int i; 900 /* Any more than 32 and we overflow anyway... */ 901 for (i = 0; i < 32; i++) { 902 if ((1U << i) == x) return i; 903 } 904 return -1; 905 } 906 907 /* Ditto for 64 bit numbers. */ 908 Int VG_(log2_64) ( ULong x ) 909 { 910 Int i; 911 for (i = 0; i < 64; i++) { 912 if ((1ULL << i) == x) return i; 913 } 914 return -1; 915 } 916 917 // Generic quick sort. 918 void VG_(ssort)( void* base, SizeT nmemb, SizeT size, 919 Int (*compar)(const void*, const void*) ) 920 { 921 bm_qsort(base,nmemb,size,compar); 922 } 923 924 925 // This random number generator is based on the one suggested in Kernighan 926 // and Ritchie's "The C Programming Language". 927 928 // A pseudo-random number generator returning a random UInt. If pSeed 929 // is NULL, it uses its own seed, which starts at zero. If pSeed is 930 // non-NULL, it uses and updates whatever pSeed points at. 931 932 UInt VG_(random)( /*MOD*/UInt* pSeed ) 933 { 934 static UInt seed = 0; 935 936 if (pSeed == NULL) 937 pSeed = &seed; 938 939 *pSeed = (1103515245 * *pSeed + 12345); 940 return *pSeed; 941 } 942 943 944 /* The following Adler-32 checksum code is taken from zlib-1.2.3, which 945 has the following copyright notice. */ 946 /* 947 Copyright notice: 948 949 (C) 1995-2004 Jean-loup Gailly and Mark Adler 950 951 This software is provided 'as-is', without any express or implied 952 warranty. In no event will the authors be held liable for any damages 953 arising from the use of this software. 954 955 Permission is granted to anyone to use this software for any purpose, 956 including commercial applications, and to alter it and redistribute it 957 freely, subject to the following restrictions: 958 959 1. The origin of this software must not be misrepresented; you must not 960 claim that you wrote the original software. If you use this software 961 in a product, an acknowledgment in the product documentation would be 962 appreciated but is not required. 963 2. Altered source versions must be plainly marked as such, and must not be 964 misrepresented as being the original software. 965 3. This notice may not be removed or altered from any source distribution. 966 967 Jean-loup Gailly Mark Adler 968 jloup (at) gzip.org madler (at) alumni.caltech.edu 969 970 If you use the zlib library in a product, we would appreciate *not* 971 receiving lengthy legal documents to sign. The sources are provided 972 for free but without warranty of any kind. The library has been 973 entirely written by Jean-loup Gailly and Mark Adler; it does not 974 include third-party code. 975 976 If you redistribute modified sources, we would appreciate that you include 977 in the file ChangeLog history information documenting your changes. Please 978 read the FAQ for more information on the distribution of modified source 979 versions. 980 */ 981 982 /* Update a running Adler-32 checksum with the bytes buf[0..len-1] and 983 return the updated checksum. If buf is NULL, this function returns 984 the required initial value for the checksum. An Adler-32 checksum is 985 almost as reliable as a CRC32 but can be computed much faster. */ 986 UInt VG_(adler32)( UInt adler, const UChar* buf, UInt len ) 987 { 988 # define BASE 65521UL /* largest prime smaller than 65536 */ 989 # define NMAX 5552 990 /* NMAX is the largest n such that 991 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 992 993 # define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 994 # define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 995 # define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 996 # define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 997 # define DO16(buf) DO8(buf,0); DO8(buf,8); 998 999 /* The zlib sources recommend this definition of MOD if the 1000 processor cannot do integer division in hardware. */ 1001 # define MOD(a) \ 1002 do { \ 1003 if (a >= (BASE << 16)) a -= (BASE << 16); \ 1004 if (a >= (BASE << 15)) a -= (BASE << 15); \ 1005 if (a >= (BASE << 14)) a -= (BASE << 14); \ 1006 if (a >= (BASE << 13)) a -= (BASE << 13); \ 1007 if (a >= (BASE << 12)) a -= (BASE << 12); \ 1008 if (a >= (BASE << 11)) a -= (BASE << 11); \ 1009 if (a >= (BASE << 10)) a -= (BASE << 10); \ 1010 if (a >= (BASE << 9)) a -= (BASE << 9); \ 1011 if (a >= (BASE << 8)) a -= (BASE << 8); \ 1012 if (a >= (BASE << 7)) a -= (BASE << 7); \ 1013 if (a >= (BASE << 6)) a -= (BASE << 6); \ 1014 if (a >= (BASE << 5)) a -= (BASE << 5); \ 1015 if (a >= (BASE << 4)) a -= (BASE << 4); \ 1016 if (a >= (BASE << 3)) a -= (BASE << 3); \ 1017 if (a >= (BASE << 2)) a -= (BASE << 2); \ 1018 if (a >= (BASE << 1)) a -= (BASE << 1); \ 1019 if (a >= BASE) a -= BASE; \ 1020 } while (0) 1021 # define MOD4(a) \ 1022 do { \ 1023 if (a >= (BASE << 4)) a -= (BASE << 4); \ 1024 if (a >= (BASE << 3)) a -= (BASE << 3); \ 1025 if (a >= (BASE << 2)) a -= (BASE << 2); \ 1026 if (a >= (BASE << 1)) a -= (BASE << 1); \ 1027 if (a >= BASE) a -= BASE; \ 1028 } while (0) 1029 1030 UInt sum2; 1031 UInt n; 1032 1033 /* split Adler-32 into component sums */ 1034 sum2 = (adler >> 16) & 0xffff; 1035 adler &= 0xffff; 1036 1037 /* in case user likes doing a byte at a time, keep it fast */ 1038 if (len == 1) { 1039 adler += buf[0]; 1040 if (adler >= BASE) 1041 adler -= BASE; 1042 sum2 += adler; 1043 if (sum2 >= BASE) 1044 sum2 -= BASE; 1045 return adler | (sum2 << 16); 1046 } 1047 1048 /* initial Adler-32 value (deferred check for len == 1 speed) */ 1049 if (buf == NULL) 1050 return 1L; 1051 1052 /* in case short lengths are provided, keep it somewhat fast */ 1053 if (len < 16) { 1054 while (len--) { 1055 adler += *buf++; 1056 sum2 += adler; 1057 } 1058 if (adler >= BASE) 1059 adler -= BASE; 1060 MOD4(sum2); /* only added so many BASE's */ 1061 return adler | (sum2 << 16); 1062 } 1063 1064 /* do length NMAX blocks -- requires just one modulo operation */ 1065 while (len >= NMAX) { 1066 len -= NMAX; 1067 n = NMAX / 16; /* NMAX is divisible by 16 */ 1068 do { 1069 DO16(buf); /* 16 sums unrolled */ 1070 buf += 16; 1071 } while (--n); 1072 MOD(adler); 1073 MOD(sum2); 1074 } 1075 1076 /* do remaining bytes (less than NMAX, still just one modulo) */ 1077 if (len) { /* avoid modulos if none remaining */ 1078 while (len >= 16) { 1079 len -= 16; 1080 DO16(buf); 1081 buf += 16; 1082 } 1083 while (len--) { 1084 adler += *buf++; 1085 sum2 += adler; 1086 } 1087 MOD(adler); 1088 MOD(sum2); 1089 } 1090 1091 /* return recombined sums */ 1092 return adler | (sum2 << 16); 1093 1094 # undef MOD4 1095 # undef MOD 1096 # undef DO16 1097 # undef DO8 1098 # undef DO4 1099 # undef DO2 1100 # undef DO1 1101 # undef NMAX 1102 # undef BASE 1103 } 1104 1105 /*--------------------------------------------------------------------*/ 1106 /*--- end ---*/ 1107 /*--------------------------------------------------------------------*/ 1108 1109
