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-2010 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 Long VG_(strtoll16) ( Char* str, Char** endptr ) 93 { 94 Bool neg = False, converted = False; 95 Long n = 0, digit = 0; 96 Char* str0 = str; 97 98 // Skip leading whitespace. 99 while (VG_(isspace)(*str)) str++; 100 101 // Allow a leading '-' or '+'. 102 if (*str == '-') { str++; neg = True; } 103 else if (*str == '+') { str++; } 104 105 // Allow leading "0x", but only if there's a hex digit 106 // following it. 107 if (*str == '0' 108 && (*(str+1) == 'x' || *(str+1) == 'X') 109 && is_hex_digit( *(str+2), &digit )) { 110 str += 2; 111 } 112 113 while (is_hex_digit(*str, &digit)) { 114 converted = True; // Ok, we've actually converted a digit. 115 n = 16*n + digit; 116 str++; 117 } 118 119 if (!converted) str = str0; // If nothing converted, endptr points to 120 if (neg) n = -n; // the start of the string. 121 if (endptr) *endptr = str; // Record first failing character. 122 return n; 123 } 124 125 double VG_(strtod) ( Char* str, Char** endptr ) 126 { 127 Bool neg = False; 128 Long digit; 129 double n = 0, frac = 0, x = 0.1; 130 131 // Skip leading whitespace. 132 while (VG_(isspace)(*str)) str++; 133 134 // Allow a leading '-' or '+'. 135 if (*str == '-') { str++; neg = True; } 136 else if (*str == '+') { str++; } 137 138 while (is_dec_digit(*str, &digit)) { 139 n = 10*n + digit; 140 str++; 141 } 142 143 if (*str == '.') { 144 str++; 145 while (is_dec_digit(*str, &digit)) { 146 frac += x*digit; 147 x /= 10; 148 str++; 149 } 150 } 151 152 n += frac; 153 if (neg) n = -n; 154 if (endptr) *endptr = str; // Record first failing character. 155 return n; 156 } 157 158 Char VG_(tolower) ( Char c ) 159 { 160 if ( c >= 'A' && c <= 'Z' ) { 161 return c - 'A' + 'a'; 162 } else { 163 return c; 164 } 165 } 166 167 /* --------------------------------------------------------------------- 168 String functions 169 ------------------------------------------------------------------ */ 170 171 SizeT VG_(strlen) ( const Char* str ) 172 { 173 SizeT i = 0; 174 while (str[i] != 0) i++; 175 return i; 176 } 177 178 Char* VG_(strcat) ( Char* dest, const Char* src ) 179 { 180 Char* dest_orig = dest; 181 while (*dest) dest++; 182 while (*src) *dest++ = *src++; 183 *dest = 0; 184 return dest_orig; 185 } 186 187 Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n ) 188 { 189 Char* dest_orig = dest; 190 while (*dest) dest++; 191 while (*src && n > 0) { *dest++ = *src++; n--; } 192 *dest = 0; 193 return dest_orig; 194 } 195 196 Char* VG_(strpbrk) ( const Char* s, const Char* accpt ) 197 { 198 const Char* a; 199 while (*s) { 200 a = accpt; 201 while (*a) 202 if (*a++ == *s) 203 return (Char *) s; 204 s++; 205 } 206 return NULL; 207 } 208 209 Char* VG_(strcpy) ( Char* dest, const Char* src ) 210 { 211 Char* dest_orig = dest; 212 while (*src) *dest++ = *src++; 213 *dest = 0; 214 return dest_orig; 215 } 216 217 /* Copy bytes, not overrunning the end of dest and always ensuring 218 zero termination. */ 219 void VG_(strncpy_safely) ( Char* dest, const Char* src, SizeT ndest ) 220 { 221 SizeT i = 0; 222 while (True) { 223 dest[i] = 0; 224 if (src[i] == 0) return; 225 if (i >= ndest-1) return; 226 dest[i] = src[i]; 227 i++; 228 } 229 } 230 231 Char* VG_(strncpy) ( Char* dest, const Char* src, SizeT ndest ) 232 { 233 SizeT i = 0; 234 while (True) { 235 if (i >= ndest) return dest; /* reached limit */ 236 dest[i] = src[i]; 237 if (src[i++] == 0) { 238 /* reached NUL; pad rest with zeroes as required */ 239 while (i < ndest) dest[i++] = 0; 240 return dest; 241 } 242 } 243 } 244 245 Int VG_(strcmp) ( const Char* s1, const Char* s2 ) 246 { 247 while (True) { 248 if (*s1 == 0 && *s2 == 0) return 0; 249 if (*s1 == 0) return -1; 250 if (*s2 == 0) return 1; 251 252 if (*(UChar*)s1 < *(UChar*)s2) return -1; 253 if (*(UChar*)s1 > *(UChar*)s2) return 1; 254 255 s1++; s2++; 256 } 257 } 258 259 Int VG_(strcasecmp) ( const Char* s1, const Char* s2 ) 260 { 261 while (True) { 262 UChar c1 = (UChar)VG_(tolower)(*s1); 263 UChar c2 = (UChar)VG_(tolower)(*s2); 264 if (c1 == 0 && c2 == 0) return 0; 265 if (c1 == 0) return -1; 266 if (c2 == 0) return 1; 267 268 if (c1 < c2) return -1; 269 if (c1 > c2) return 1; 270 271 s1++; s2++; 272 } 273 } 274 275 Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax ) 276 { 277 SizeT n = 0; 278 while (True) { 279 if (n >= nmax) return 0; 280 if (*s1 == 0 && *s2 == 0) return 0; 281 if (*s1 == 0) return -1; 282 if (*s2 == 0) return 1; 283 284 if (*(UChar*)s1 < *(UChar*)s2) return -1; 285 if (*(UChar*)s1 > *(UChar*)s2) return 1; 286 287 s1++; s2++; n++; 288 } 289 } 290 291 Int VG_(strncasecmp) ( const Char* s1, const Char* s2, SizeT nmax ) 292 { 293 Int n = 0; 294 while (True) { 295 UChar c1; 296 UChar c2; 297 if (n >= nmax) return 0; 298 c1 = (UChar)VG_(tolower)(*s1); 299 c2 = (UChar)VG_(tolower)(*s2); 300 if (c1 == 0 && c2 == 0) return 0; 301 if (c1 == 0) return -1; 302 if (c2 == 0) return 1; 303 304 if (c1 < c2) return -1; 305 if (c1 > c2) return 1; 306 307 s1++; s2++; n++; 308 } 309 } 310 311 Char* VG_(strstr) ( const Char* haystack, Char* needle ) 312 { 313 SizeT n; 314 if (haystack == NULL) 315 return NULL; 316 n = VG_(strlen)(needle); 317 while (True) { 318 if (haystack[0] == 0) 319 return NULL; 320 if (VG_(strncmp)(haystack, needle, n) == 0) 321 return (Char*)haystack; 322 haystack++; 323 } 324 } 325 326 Char* VG_(strcasestr) ( const Char* haystack, Char* needle ) 327 { 328 Int n; 329 if (haystack == NULL) 330 return NULL; 331 n = VG_(strlen)(needle); 332 while (True) { 333 if (haystack[0] == 0) 334 return NULL; 335 if (VG_(strncasecmp)(haystack, needle, n) == 0) 336 return (Char*)haystack; 337 haystack++; 338 } 339 } 340 341 Char* VG_(strchr) ( const Char* s, Char c ) 342 { 343 while (True) { 344 if (*s == c) return (Char*)s; 345 if (*s == 0) return NULL; 346 s++; 347 } 348 } 349 350 Char* VG_(strrchr) ( const Char* s, Char c ) 351 { 352 Int n = VG_(strlen)(s); 353 while (--n > 0) { 354 if (s[n] == c) return (Char*)s + n; 355 } 356 return NULL; 357 } 358 359 SizeT VG_(strspn) ( const Char* s, const Char* accpt ) 360 { 361 const Char *p, *a; 362 SizeT count = 0; 363 for (p = s; *p != '\0'; ++p) { 364 for (a = accpt; *a != '\0'; ++a) 365 if (*p == *a) 366 break; 367 if (*a == '\0') 368 return count; 369 else 370 ++count; 371 } 372 return count; 373 } 374 375 SizeT VG_(strcspn) ( const Char* s, const char* reject ) 376 { 377 SizeT count = 0; 378 while (*s != '\0') { 379 if (VG_(strchr) (reject, *s++) == NULL) 380 ++count; 381 else 382 return count; 383 } 384 return count; 385 } 386 387 388 /* --------------------------------------------------------------------- 389 mem* functions 390 ------------------------------------------------------------------ */ 391 392 void* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) 393 { 394 const UChar* s = (const UChar*)src; 395 UChar* d = (UChar*)dest; 396 const UInt* sI = (const UInt*)src; 397 UInt* dI = (UInt*)dest; 398 399 if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { 400 while (sz >= 16) { 401 dI[0] = sI[0]; 402 dI[1] = sI[1]; 403 dI[2] = sI[2]; 404 dI[3] = sI[3]; 405 sz -= 16; 406 dI += 4; 407 sI += 4; 408 } 409 if (sz == 0) 410 return dest; 411 while (sz >= 4) { 412 dI[0] = sI[0]; 413 sz -= 4; 414 dI += 1; 415 sI += 1; 416 } 417 if (sz == 0) 418 return dest; 419 s = (const UChar*)sI; 420 d = (UChar*)dI; 421 } 422 423 while (sz--) 424 *d++ = *s++; 425 426 return dest; 427 } 428 429 void* VG_(memmove)(void *dest, const void *src, SizeT sz) 430 { 431 SizeT i; 432 if (sz == 0) 433 return dest; 434 if (dest < src) { 435 for (i = 0; i < sz; i++) { 436 ((UChar*)dest)[i] = ((UChar*)src)[i]; 437 } 438 } 439 else if (dest > src) { 440 for (i = 0; i < sz; i++) { 441 ((UChar*)dest)[sz-i-1] = ((UChar*)src)[sz-i-1]; 442 } 443 } 444 return dest; 445 } 446 447 void* VG_(memset) ( void *destV, Int c, SizeT sz ) 448 { 449 Int c4; 450 Char* d = (Char*)destV; 451 while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) { 452 d[0] = c; 453 d++; 454 sz--; 455 } 456 if (sz == 0) 457 return destV; 458 c4 = c & 0xFF; 459 c4 |= (c4 << 8); 460 c4 |= (c4 << 16); 461 while (sz >= 16) { 462 ((Int*)d)[0] = c4; 463 ((Int*)d)[1] = c4; 464 ((Int*)d)[2] = c4; 465 ((Int*)d)[3] = c4; 466 d += 16; 467 sz -= 16; 468 } 469 while (sz >= 4) { 470 ((Int*)d)[0] = c4; 471 d += 4; 472 sz -= 4; 473 } 474 while (sz >= 1) { 475 d[0] = c; 476 d++; 477 sz--; 478 } 479 return destV; 480 } 481 482 Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) 483 { 484 Int res; 485 const UChar *p1 = s1; 486 const UChar *p2 = s2; 487 UChar a0; 488 UChar b0; 489 490 while (n != 0) { 491 a0 = p1[0]; 492 b0 = p2[0]; 493 p1 += 1; 494 p2 += 1; 495 res = a0 - b0; 496 if (res != 0) 497 return res; 498 n -= 1; 499 } 500 return 0; 501 } 502 503 /* --------------------------------------------------------------------- 504 Misc useful functions 505 ------------------------------------------------------------------ */ 506 507 ///////////////////////////////////////////////////////////// 508 ///////////////////////////////////////////////////////////// 509 /// begin Bentley-McIlroy style quicksort 510 /// See "Engineering a Sort Function". Jon L Bentley, M. Douglas 511 /// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993. 512 513 #define BM_MIN(a, b) \ 514 (a) < (b) ? a : b 515 516 #define BM_SWAPINIT(a, es) \ 517 swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \ 518 : es > (SizeT)sizeof(Word) ? 1 \ 519 : 0 520 521 #define BM_EXCH(a, b, t) \ 522 (t = a, a = b, b = t) 523 524 #define BM_SWAP(a, b) \ 525 swaptype != 0 \ 526 ? bm_swapfunc(a, b, es, swaptype) \ 527 : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t) 528 529 #define BM_VECSWAP(a, b, n) \ 530 if (n > 0) bm_swapfunc(a, b, n, swaptype) 531 532 #define BM_PVINIT(pv, pm) \ 533 if (swaptype != 0) \ 534 pv = a, BM_SWAP(pv, pm); \ 535 else \ 536 pv = (Char*)&v, v = *(Word*)pm 537 538 static Char* bm_med3 ( Char* a, Char* b, Char* c, 539 Int (*cmp)(void*,void*) ) { 540 return cmp(a, b) < 0 541 ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) 542 : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); 543 } 544 545 static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype ) 546 { 547 if (swaptype <= 1) { 548 Word t; 549 for ( ; n > 0; a += sizeof(Word), b += sizeof(Word), 550 n -= sizeof(Word)) 551 BM_EXCH(*(Word*)a, *(Word*)b, t); 552 } else { 553 Char t; 554 for ( ; n > 0; a += 1, b += 1, n -= 1) 555 BM_EXCH(*a, *b, t); 556 } 557 } 558 559 static void bm_qsort ( Char* a, SizeT n, SizeT es, 560 Int (*cmp)(void*,void*) ) 561 { 562 Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; 563 Int r, swaptype; 564 Word t, v; 565 SizeT s, s1, s2; 566 tailcall: 567 BM_SWAPINIT(a, es); 568 if (n < 7) { 569 for (pm = a + es; pm < a + n*es; pm += es) 570 for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 571 BM_SWAP(pl, pl-es); 572 return; 573 } 574 pm = a + (n/2)*es; 575 if (n > 7) { 576 pl = a; 577 pn = a + (n-1)*es; 578 if (n > 40) { 579 s = (n/8)*es; 580 pl = bm_med3(pl, pl+s, pl+2*s, cmp); 581 pm = bm_med3(pm-s, pm, pm+s, cmp); 582 pn = bm_med3(pn-2*s, pn-s, pn, cmp); 583 } 584 pm = bm_med3(pl, pm, pn, cmp); 585 } 586 BM_PVINIT(pv, pm); 587 pa = pb = a; 588 pc = pd = a + (n-1)*es; 589 for (;;) { 590 while (pb <= pc && (r = cmp(pb, pv)) <= 0) { 591 if (r == 0) { BM_SWAP(pa, pb); pa += es; } 592 pb += es; 593 } 594 while (pc >= pb && (r = cmp(pc, pv)) >= 0) { 595 if (r == 0) { BM_SWAP(pc, pd); pd -= es; } 596 pc -= es; 597 } 598 if (pb > pc) break; 599 BM_SWAP(pb, pc); 600 pb += es; 601 pc -= es; 602 } 603 pn = a + n*es; 604 s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s); 605 s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s); 606 /* Now recurse. Do the smaller partition first with an explicit 607 recursion, then do the larger partition using a tail call. 608 Except we can't rely on gcc to implement a tail call in any sane 609 way, so simply jump back to the start. This guarantees stack 610 growth can never exceed O(log N) even in the worst case. */ 611 s1 = pb-pa; 612 s2 = pd-pc; 613 if (s1 < s2) { 614 if (s1 > es) { 615 bm_qsort(a, s1/es, es, cmp); 616 } 617 if (s2 > es) { 618 /* bm_qsort(pn-s2, s2/es, es, cmp); */ 619 a = pn-s2; n = s2/es; es = es; cmp = cmp; 620 goto tailcall; 621 } 622 } else { 623 if (s2 > es) { 624 bm_qsort(pn-s2, s2/es, es, cmp); 625 } 626 if (s1 > es) { 627 /* bm_qsort(a, s1/es, es, cmp); */ 628 a = a; n = s1/es; es = es; cmp = cmp; 629 goto tailcall; 630 } 631 } 632 } 633 634 #undef BM_MIN 635 #undef BM_SWAPINIT 636 #undef BM_EXCH 637 #undef BM_SWAP 638 #undef BM_VECSWAP 639 #undef BM_PVINIT 640 641 /// end Bentley-McIlroy style quicksort 642 ///////////////////////////////////////////////////////////// 643 ///////////////////////////////////////////////////////////// 644 645 /* Returns the base-2 logarithm of x. Returns -1 if x is not a power 646 of two. */ 647 Int VG_(log2) ( UInt x ) 648 { 649 Int i; 650 /* Any more than 32 and we overflow anyway... */ 651 for (i = 0; i < 32; i++) { 652 if ((1U << i) == x) return i; 653 } 654 return -1; 655 } 656 657 658 // Generic quick sort. 659 void VG_(ssort)( void* base, SizeT nmemb, SizeT size, 660 Int (*compar)(void*, void*) ) 661 { 662 bm_qsort(base,nmemb,size,compar); 663 } 664 665 666 // This random number generator is based on the one suggested in Kernighan 667 // and Ritchie's "The C Programming Language". 668 669 // A pseudo-random number generator returning a random UInt. If pSeed 670 // is NULL, it uses its own seed, which starts at zero. If pSeed is 671 // non-NULL, it uses and updates whatever pSeed points at. 672 673 static UInt seed = 0; 674 675 UInt VG_(random)( /*MOD*/UInt* pSeed ) 676 { 677 if (pSeed == NULL) 678 pSeed = &seed; 679 680 *pSeed = (1103515245 * *pSeed + 12345); 681 return *pSeed; 682 } 683 684 /*--------------------------------------------------------------------*/ 685 /*--- end ---*/ 686 /*--------------------------------------------------------------------*/ 687 688
