| |
| /*--------------------------------------------------------------------*/ |
| /*--- Entirely standalone libc stuff. m_libcbase.c ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| /* |
| This file is part of Valgrind, a dynamic binary instrumentation |
| framework. |
| |
| Copyright (C) 2000-2008 Julian Seward |
| jseward@acm.org |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of the |
| License, or (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307, USA. |
| |
| The GNU General Public License is contained in the file COPYING. |
| */ |
| |
| #include "pub_core_basics.h" |
| #include "pub_core_libcbase.h" |
| |
| /* --------------------------------------------------------------------- |
| Char functions. |
| ------------------------------------------------------------------ */ |
| |
| Bool VG_(isspace) ( Char c ) |
| { |
| return (c == ' ' || c == '\n' || c == '\t' || |
| c == '\f' || c == '\v' || c == '\r'); |
| } |
| |
| Bool VG_(isdigit) ( Char c ) |
| { |
| return (c >= '0' && c <= '9'); |
| } |
| |
| /* --------------------------------------------------------------------- |
| Converting strings to numbers |
| ------------------------------------------------------------------ */ |
| |
| static Bool is_oct_digit(Char c, Long* digit) |
| { |
| if (c >= '0' && c <= '7') { *digit = (Long)(c - '0'); return True; } |
| return False; |
| } |
| |
| static Bool is_dec_digit(Char c, Long* digit) |
| { |
| if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; } |
| return False; |
| } |
| |
| static Bool is_hex_digit(Char c, Long* digit) |
| { |
| if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; } |
| if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; } |
| if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; } |
| return False; |
| } |
| |
| static Bool is_base36_digit(Char c, Long* digit) |
| { |
| if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; } |
| if (c >= 'A' && c <= 'Z') { *digit = (Long)((c - 'A') + 10); return True; } |
| if (c >= 'a' && c <= 'z') { *digit = (Long)((c - 'a') + 10); return True; } |
| return False; |
| } |
| |
| Long VG_(strtoll8) ( Char* str, Char** endptr ) |
| { |
| Bool neg = False; |
| Long n = 0, digit = 0; |
| |
| // Skip leading whitespace. |
| while (VG_(isspace)(*str)) str++; |
| |
| // Allow a leading '-' or '+'. |
| if (*str == '-') { str++; neg = True; } |
| else if (*str == '+') { str++; } |
| |
| while (is_oct_digit(*str, &digit)) { |
| n = 8*n + digit; |
| str++; |
| } |
| |
| if (neg) n = -n; |
| if (endptr) *endptr = str; // Record first failing character. |
| return n; |
| } |
| |
| Long VG_(strtoll10) ( Char* str, Char** endptr ) |
| { |
| Bool neg = False; |
| Long n = 0, digit = 0; |
| |
| // Skip leading whitespace. |
| while (VG_(isspace)(*str)) str++; |
| |
| // Allow a leading '-' or '+'. |
| if (*str == '-') { str++; neg = True; } |
| else if (*str == '+') { str++; } |
| |
| while (is_dec_digit(*str, &digit)) { |
| n = 10*n + digit; |
| str++; |
| } |
| |
| if (neg) n = -n; |
| if (endptr) *endptr = str; // Record first failing character. |
| return n; |
| } |
| |
| Long VG_(strtoll16) ( Char* str, Char** endptr ) |
| { |
| Bool neg = False; |
| Long n = 0, digit = 0; |
| |
| // Skip leading whitespace. |
| while (VG_(isspace)(*str)) str++; |
| |
| // Allow a leading '-' or '+'. |
| if (*str == '-') { str++; neg = True; } |
| else if (*str == '+') { str++; } |
| |
| // Allow leading "0x", but only if there's a hex digit |
| // following it. |
| if (*str == '0' |
| && (*(str+1) == 'x' || *(str+1) == 'X') |
| && is_hex_digit( *(str+2), &digit )) { |
| str += 2; |
| } |
| |
| while (is_hex_digit(*str, &digit)) { |
| n = 16*n + digit; |
| str++; |
| } |
| |
| if (neg) n = -n; |
| if (endptr) *endptr = str; // Record first failing character. |
| return n; |
| } |
| |
| Long VG_(strtoll36) ( Char* str, Char** endptr ) |
| { |
| Bool neg = False; |
| Long n = 0, digit = 0; |
| |
| // Skip leading whitespace. |
| while (VG_(isspace)(*str)) str++; |
| |
| // Allow a leading '-' or '+'. |
| if (*str == '-') { str++; neg = True; } |
| else if (*str == '+') { str++; } |
| |
| while (is_base36_digit(*str, &digit)) { |
| n = 36*n + digit; |
| str++; |
| } |
| |
| if (neg) n = -n; |
| if (endptr) *endptr = str; // Record first failing character. |
| return n; |
| } |
| |
| double VG_(strtod) ( Char* str, Char** endptr ) |
| { |
| Bool neg = False; |
| Long digit; |
| double n = 0, frac = 0, x = 0.1; |
| |
| // Skip leading whitespace. |
| while (VG_(isspace)(*str)) str++; |
| |
| // Allow a leading '-' or '+'. |
| if (*str == '-') { str++; neg = True; } |
| else if (*str == '+') { str++; } |
| |
| while (is_dec_digit(*str, &digit)) { |
| n = 10*n + digit; |
| str++; |
| } |
| |
| if (*str == '.') { |
| str++; |
| while (is_dec_digit(*str, &digit)) { |
| frac += x*digit; |
| x /= 10; |
| str++; |
| } |
| } |
| |
| n += frac; |
| if (neg) n = -n; |
| if (endptr) *endptr = str; // Record first failing character. |
| return n; |
| } |
| |
| Long VG_(atoll) ( Char* str ) |
| { |
| return VG_(strtoll10)(str, NULL); |
| } |
| |
| Long VG_(atoll16) ( Char* str ) |
| { |
| return VG_(strtoll16)(str, NULL); |
| } |
| |
| Long VG_(atoll36) ( Char* str ) |
| { |
| return VG_(strtoll36)(str, NULL); |
| } |
| |
| /* --------------------------------------------------------------------- |
| String functions |
| ------------------------------------------------------------------ */ |
| |
| Int VG_(strlen) ( const Char* str ) |
| { |
| Int i = 0; |
| while (str[i] != 0) i++; |
| return i; |
| } |
| |
| Char* VG_(strcat) ( Char* dest, const Char* src ) |
| { |
| Char* dest_orig = dest; |
| while (*dest) dest++; |
| while (*src) *dest++ = *src++; |
| *dest = 0; |
| return dest_orig; |
| } |
| |
| Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n ) |
| { |
| Char* dest_orig = dest; |
| while (*dest) dest++; |
| while (*src && n > 0) { *dest++ = *src++; n--; } |
| *dest = 0; |
| return dest_orig; |
| } |
| |
| Char* VG_(strpbrk) ( const Char* s, const Char* accept ) |
| { |
| const Char* a; |
| while (*s) { |
| a = accept; |
| while (*a) |
| if (*a++ == *s) |
| return (Char *) s; |
| s++; |
| } |
| return NULL; |
| } |
| |
| Char* VG_(strcpy) ( Char* dest, const Char* src ) |
| { |
| Char* dest_orig = dest; |
| while (*src) *dest++ = *src++; |
| *dest = 0; |
| return dest_orig; |
| } |
| |
| /* Copy bytes, not overrunning the end of dest and always ensuring |
| zero termination. */ |
| void VG_(strncpy_safely) ( Char* dest, const Char* src, SizeT ndest ) |
| { |
| Int i = 0; |
| while (True) { |
| dest[i] = 0; |
| if (src[i] == 0) return; |
| if (i >= ndest-1) return; |
| dest[i] = src[i]; |
| i++; |
| } |
| } |
| |
| Char* VG_(strncpy) ( Char* dest, const Char* src, SizeT ndest ) |
| { |
| Int i = 0; |
| while (True) { |
| if (i >= ndest) return dest; /* reached limit */ |
| dest[i] = src[i]; |
| if (src[i++] == 0) { |
| /* reached NUL; pad rest with zeroes as required */ |
| while (i < ndest) dest[i++] = 0; |
| return dest; |
| } |
| } |
| } |
| |
| Int VG_(strcmp) ( const Char* s1, const Char* s2 ) |
| { |
| while (True) { |
| if (*s1 == 0 && *s2 == 0) return 0; |
| if (*s1 == 0) return -1; |
| if (*s2 == 0) return 1; |
| |
| if (*(UChar*)s1 < *(UChar*)s2) return -1; |
| if (*(UChar*)s1 > *(UChar*)s2) return 1; |
| |
| s1++; s2++; |
| } |
| } |
| |
| static Bool isterm ( Char c ) |
| { |
| return ( VG_(isspace)(c) || 0 == c ); |
| } |
| |
| Int VG_(strcmp_ws) ( const Char* s1, const Char* s2 ) |
| { |
| while (True) { |
| if (isterm(*s1) && isterm(*s2)) return 0; |
| if (isterm(*s1)) return -1; |
| if (isterm(*s2)) return 1; |
| |
| if (*(UChar*)s1 < *(UChar*)s2) return -1; |
| if (*(UChar*)s1 > *(UChar*)s2) return 1; |
| |
| s1++; s2++; |
| } |
| } |
| |
| Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax ) |
| { |
| Int n = 0; |
| while (True) { |
| if (n >= nmax) return 0; |
| if (*s1 == 0 && *s2 == 0) return 0; |
| if (*s1 == 0) return -1; |
| if (*s2 == 0) return 1; |
| |
| if (*(UChar*)s1 < *(UChar*)s2) return -1; |
| if (*(UChar*)s1 > *(UChar*)s2) return 1; |
| |
| s1++; s2++; n++; |
| } |
| } |
| |
| Int VG_(strncmp_ws) ( const Char* s1, const Char* s2, SizeT nmax ) |
| { |
| Int n = 0; |
| while (True) { |
| if (n >= nmax) return 0; |
| if (isterm(*s1) && isterm(*s2)) return 0; |
| if (isterm(*s1)) return -1; |
| if (isterm(*s2)) return 1; |
| |
| if (*(UChar*)s1 < *(UChar*)s2) return -1; |
| if (*(UChar*)s1 > *(UChar*)s2) return 1; |
| |
| s1++; s2++; n++; |
| } |
| } |
| |
| Char* VG_(strstr) ( const Char* haystack, Char* needle ) |
| { |
| Int n; |
| if (haystack == NULL) |
| return NULL; |
| n = VG_(strlen)(needle); |
| while (True) { |
| if (haystack[0] == 0) |
| return NULL; |
| if (VG_(strncmp)(haystack, needle, n) == 0) |
| return (Char*)haystack; |
| haystack++; |
| } |
| } |
| |
| Char* VG_(strchr) ( const Char* s, Char c ) |
| { |
| while (True) { |
| if (*s == c) return (Char*)s; |
| if (*s == 0) return NULL; |
| s++; |
| } |
| } |
| |
| Char* VG_(strrchr) ( const Char* s, Char c ) |
| { |
| Int n = VG_(strlen)(s); |
| while (--n > 0) { |
| if (s[n] == c) return (Char*)s + n; |
| } |
| return NULL; |
| } |
| |
| /* --------------------------------------------------------------------- |
| A simple string matching routine, purloined from Hugs98. |
| '*' matches any sequence of zero or more characters |
| '?' matches any single character exactly |
| '\c' matches the character c only (ignoring special chars) |
| c matches the character c only |
| ------------------------------------------------------------------ */ |
| |
| /* Keep track of recursion depth. */ |
| static Int recDepth; |
| |
| // Nb: vg_assert disabled because we can't use it from this module... |
| static Bool string_match_wrk ( const Char* pat, const Char* str ) |
| { |
| //vg_assert(recDepth >= 0 && recDepth < 500); |
| recDepth++; |
| for (;;) { |
| switch (*pat) { |
| case '\0':recDepth--; |
| return (*str=='\0'); |
| case '*': do { |
| if (string_match_wrk(pat+1,str)) { |
| recDepth--; |
| return True; |
| } |
| } while (*str++); |
| recDepth--; |
| return False; |
| case '?': if (*str++=='\0') { |
| recDepth--; |
| return False; |
| } |
| pat++; |
| break; |
| case '\\':if (*++pat == '\0') { |
| recDepth--; |
| return False; /* spurious trailing \ in pattern */ |
| } |
| /* falls through to ... */ |
| default : if (*pat++ != *str++) { |
| recDepth--; |
| return False; |
| } |
| break; |
| } |
| } |
| } |
| |
| Bool VG_(string_match) ( const Char* pat, const Char* str ) |
| { |
| Bool b; |
| recDepth = 0; |
| b = string_match_wrk ( pat, str ); |
| //vg_assert(recDepth == 0); |
| /* |
| VG_(printf)("%s %s %s\n", |
| b?"TRUE ":"FALSE", pat, str); |
| */ |
| return b; |
| } |
| |
| |
| /* --------------------------------------------------------------------- |
| mem* functions |
| ------------------------------------------------------------------ */ |
| |
| void* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) |
| { |
| const UChar* s = (const UChar*)src; |
| UChar* d = (UChar*)dest; |
| const UInt* sI = (const UInt*)src; |
| UInt* dI = (UInt*)dest; |
| |
| if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { |
| while (sz >= 16) { |
| dI[0] = sI[0]; |
| dI[1] = sI[1]; |
| dI[2] = sI[2]; |
| dI[3] = sI[3]; |
| sz -= 16; |
| dI += 4; |
| sI += 4; |
| } |
| if (sz == 0) |
| return dest; |
| while (sz >= 4) { |
| dI[0] = sI[0]; |
| sz -= 4; |
| dI += 1; |
| sI += 1; |
| } |
| if (sz == 0) |
| return dest; |
| s = (const UChar*)sI; |
| d = (UChar*)dI; |
| } |
| |
| while (sz--) |
| *d++ = *s++; |
| |
| return dest; |
| } |
| |
| void* VG_(memmove)(void *dest, const void *src, SizeT sz) |
| { |
| SizeT i; |
| if (sz == 0) |
| return dest; |
| if (dest < src) { |
| for (i = 0; i < sz; i++) { |
| ((UChar*)dest)[i] = ((UChar*)src)[i]; |
| } |
| } |
| else if (dest > src) { |
| for (i = sz - 1; i >= 0; i--) { |
| ((UChar*)dest)[i] = ((UChar*)src)[i]; |
| } |
| } |
| return dest; |
| } |
| |
| void* VG_(memset) ( void *dest, Int c, SizeT sz ) |
| { |
| Char *d = (Char *)dest; |
| while (sz >= 4) { |
| d[0] = c; |
| d[1] = c; |
| d[2] = c; |
| d[3] = c; |
| d += 4; |
| sz -= 4; |
| } |
| while (sz > 0) { |
| d[0] = c; |
| d++; |
| sz--; |
| } |
| return dest; |
| } |
| |
| Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) |
| { |
| Int res; |
| const UChar *p1 = s1; |
| const UChar *p2 = s2; |
| UChar a0; |
| UChar b0; |
| |
| while (n != 0) { |
| a0 = p1[0]; |
| b0 = p2[0]; |
| p1 += 1; |
| p2 += 1; |
| res = a0 - b0; |
| if (res != 0) |
| return res; |
| n -= 1; |
| } |
| return 0; |
| } |
| |
| /* --------------------------------------------------------------------- |
| Misc useful functions |
| ------------------------------------------------------------------ */ |
| |
| /* Returns the base-2 logarithm of x. Returns -1 if x is not a power of two. */ |
| Int VG_(log2) ( Int x ) |
| { |
| Int i; |
| /* Any more than 32 and we overflow anyway... */ |
| for (i = 0; i < 32; i++) { |
| if (1 << i == x) return i; |
| } |
| return -1; |
| } |
| |
| |
| // Generic shell sort. Like stdlib.h's qsort(). |
| void VG_(ssort)( void* base, SizeT nmemb, SizeT size, |
| Int (*compar)(void*, void*) ) |
| { |
| Int incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280, |
| 9841, 29524, 88573, 265720, |
| 797161, 2391484 }; |
| Int lo = 0; |
| Int hi = nmemb-1; |
| Int i, j, h, bigN, hp; |
| |
| bigN = hi - lo + 1; if (bigN < 2) return; |
| hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--; |
| |
| #define SORT \ |
| for ( ; hp >= 0; hp--) { \ |
| h = incs[hp]; \ |
| for (i = lo + h; i <= hi; i++) { \ |
| ASSIGN(v,0, a,i); \ |
| j = i; \ |
| while (COMPAR(a,(j-h), v,0) > 0) { \ |
| ASSIGN(a,j, a,(j-h)); \ |
| j = j - h; \ |
| if (j <= (lo + h - 1)) break; \ |
| } \ |
| ASSIGN(a,j, v,0); \ |
| } \ |
| } |
| |
| // Specialised cases |
| if (sizeof(ULong) == size) { |
| |
| #define ASSIGN(dst, dsti, src, srci) \ |
| (dst)[(dsti)] = (src)[(srci)]; |
| |
| #define COMPAR(dst, dsti, src, srci) \ |
| compar( (void*)(& (dst)[(dsti)]), (void*)(& (src)[(srci)]) ) |
| |
| ULong* a = (ULong*)base; |
| ULong v[1]; |
| |
| SORT; |
| |
| } else if (sizeof(UInt) == size) { |
| |
| UInt* a = (UInt*)base; |
| UInt v[1]; |
| |
| SORT; |
| |
| } else if (sizeof(UShort) == size) { |
| UShort* a = (UShort*)base; |
| UShort v[1]; |
| |
| SORT; |
| |
| } else if (sizeof(UChar) == size) { |
| UChar* a = (UChar*)base; |
| UChar v[1]; |
| |
| SORT; |
| |
| #undef ASSIGN |
| #undef COMPAR |
| |
| } else if ( (4*sizeof(UWord)) == size ) { |
| /* special-case 4 word-elements. This captures a lot of cases |
| from symbol table reading/canonicalisaton, because both DiLoc |
| and DiSym are 4 word structures. */ |
| HChar* a = base; |
| HChar v[size]; |
| |
| #define ASSIGN(dst, dsti, src, srci) \ |
| do { UWord* dP = (UWord*)&dst[size*(dsti)]; \ |
| UWord* sP = (UWord*)&src[size*(srci)]; \ |
| dP[0] = sP[0]; \ |
| dP[1] = sP[1]; \ |
| dP[2] = sP[2]; \ |
| dP[3] = sP[3]; \ |
| } while (0) |
| |
| #define COMPAR(dst, dsti, src, srci) \ |
| compar( &dst[size*(dsti)], &src[size*(srci)] ) |
| |
| SORT; |
| |
| #undef ASSIGN |
| #undef COMPAR |
| |
| // General case |
| } else { |
| HChar* a = base; |
| HChar v[size]; // will be at least 'size' bytes |
| |
| #define ASSIGN(dst, dsti, src, srci) \ |
| VG_(memcpy)( &dst[size*(dsti)], &src[size*(srci)], size ); |
| |
| #define COMPAR(dst, dsti, src, srci) \ |
| compar( &dst[size*(dsti)], &src[size*(srci)] ) |
| |
| SORT; |
| |
| #undef ASSIGN |
| #undef COMPAR |
| } |
| #undef SORT |
| } |
| |
| // This random number generator is based on the one suggested in Kernighan |
| // and Ritchie's "The C Programming Language". |
| |
| // A pseudo-random number generator returning a random UInt. If pSeed |
| // is NULL, it uses its own seed, which starts at zero. If pSeed is |
| // non-NULL, it uses and updates whatever pSeed points at. |
| |
| static UInt seed = 0; |
| |
| UInt VG_(random)( /*MOD*/UInt* pSeed ) |
| { |
| if (pSeed == NULL) |
| pSeed = &seed; |
| |
| *pSeed = (1103515245 * *pSeed + 12345); |
| return *pSeed; |
| } |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- end ---*/ |
| /*--------------------------------------------------------------------*/ |
| |