l4/pkg/valgrind/src/valgrind-3.6.0-svn/coregrind/m_libcbase.c

   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@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