m_libcbase.c revision 7d9b3af56d1f31210684811fa8cad8c27b00d003 
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-2007 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
38Bool VG_(isspace) ( Char c )
39{
40   return (c == ' '  || c == '\n' || c == '\t' ||
41           c == '\f' || c == '\v' || c == '\r');
42}
43
44Bool VG_(isdigit) ( Char c )
45{
46   return (c >= '0' && c <= '9');
47}
48
49/* ---------------------------------------------------------------------
50   Converting strings to numbers
51   ------------------------------------------------------------------ */
52
53static Bool is_oct_digit(Char c, Long* digit)
54{
55   if (c >= '0' && c <= '7') { *digit = (Long)(c - '0'); return True; }
56   return False;
57}
58
59static Bool is_dec_digit(Char c, Long* digit)
60{
61   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
62   return False;
63}
64
65static Bool is_hex_digit(Char c, Long* digit)
66{
67   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
68   if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; }
69   if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; }
70   return False;
71}
72
73static Bool is_base36_digit(Char c, Long* digit)
74{
75   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
76   if (c >= 'A' && c <= 'Z') { *digit = (Long)((c - 'A') + 10); return True; }
77   if (c >= 'a' && c <= 'z') { *digit = (Long)((c - 'a') + 10); return True; }
78   return False;
79}
80
81Long VG_(strtoll8) ( Char* str, Char** endptr )
82{
83   Bool neg = False;
84   Long n = 0, digit = 0;
85
86   // Skip leading whitespace.
87   while (VG_(isspace)(*str)) str++;
88
89   // Allow a leading '-' or '+'.
90   if (*str == '-') { str++; neg = True; }
91   else if (*str == '+') { str++; }
92
93   while (is_oct_digit(*str, &digit)) {
94      n = 8*n + digit;
95      str++;
96   }
97
98   if (neg) n = -n;
99   if (endptr) *endptr = str;    // Record first failing character.
100   return n;
101}
102
103Long VG_(strtoll10) ( Char* str, Char** endptr )
104{
105   Bool neg = False;
106   Long n = 0, digit = 0;
107
108   // Skip leading whitespace.
109   while (VG_(isspace)(*str)) str++;
110
111   // Allow a leading '-' or '+'.
112   if (*str == '-') { str++; neg = True; }
113   else if (*str == '+') { str++; }
114
115   while (is_dec_digit(*str, &digit)) {
116      n = 10*n + digit;
117      str++;
118   }
119
120   if (neg) n = -n;
121   if (endptr) *endptr = str;    // Record first failing character.
122   return n;
123}
124
125Long VG_(strtoll16) ( Char* str, Char** endptr )
126{
127   Bool neg = False;
128   Long n = 0, digit = 0;
129
130   // Skip leading whitespace.
131   while (VG_(isspace)(*str)) str++;
132
133   // Allow a leading '-' or '+'.
134   if (*str == '-') { str++; neg = True; }
135   else if (*str == '+') { str++; }
136
137   // Allow leading "0x", but only if there's a hex digit
138   // following it.
139   if (*str == '0'
140    && (*(str+1) == 'x' || *(str+1) == 'X')
141    && is_hex_digit( *(str+2), &digit )) {
142      str += 2;
143   }
144
145   while (is_hex_digit(*str, &digit)) {
146      n = 16*n + digit;
147      str++;
148   }
149
150   if (neg) n = -n;
151   if (endptr) *endptr = str;    // Record first failing character.
152   return n;
153}
154
155Long VG_(strtoll36) ( Char* str, Char** endptr )
156{
157   Bool neg = False;
158   Long n = 0, digit = 0;
159
160   // Skip leading whitespace.
161   while (VG_(isspace)(*str)) str++;
162
163   // Allow a leading '-' or '+'.
164   if (*str == '-') { str++; neg = True; }
165   else if (*str == '+') { str++; }
166
167   while (is_base36_digit(*str, &digit)) {
168      n = 36*n + digit;
169      str++;
170   }
171
172   if (neg) n = -n;
173   if (endptr) *endptr = str;    // Record first failing character.
174   return n;
175}
176
177double VG_(strtod) ( Char* str, Char** endptr )
178{
179   Bool neg = False;
180   Long digit;
181   double n = 0, frac = 0, x = 0.1;
182
183   // Skip leading whitespace.
184   while (VG_(isspace)(*str)) str++;
185
186   // Allow a leading '-' or '+'.
187   if (*str == '-') { str++; neg = True; }
188   else if (*str == '+') { str++; }
189
190   while (is_dec_digit(*str, &digit)) {
191      n = 10*n + digit;
192      str++;
193   }
194
195   if (*str == '.') {
196      str++;
197      while (is_dec_digit(*str, &digit)) {
198         frac += x*digit;
199         x /= 10;
200         str++;
201      }
202   }
203
204   n += frac;
205   if (neg) n = -n;
206   if (endptr) *endptr = str;    // Record first failing character.
207   return n;
208}
209
210Long VG_(atoll) ( Char* str )
211{
212   return VG_(strtoll10)(str, NULL);
213}
214
215Long VG_(atoll16) ( Char* str )
216{
217   return VG_(strtoll16)(str, NULL);
218}
219
220Long VG_(atoll36) ( Char* str )
221{
222   return VG_(strtoll36)(str, NULL);
223}
224
225/* ---------------------------------------------------------------------
226   String functions
227   ------------------------------------------------------------------ */
228
229Int VG_(strlen) ( const Char* str )
230{
231   Int i = 0;
232   while (str[i] != 0) i++;
233   return i;
234}
235
236Char* VG_(strcat) ( Char* dest, const Char* src )
237{
238   Char* dest_orig = dest;
239   while (*dest) dest++;
240   while (*src) *dest++ = *src++;
241   *dest = 0;
242   return dest_orig;
243}
244
245Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n )
246{
247   Char* dest_orig = dest;
248   while (*dest) dest++;
249   while (*src && n > 0) { *dest++ = *src++; n--; }
250   *dest = 0;
251   return dest_orig;
252}
253
254Char* VG_(strpbrk) ( const Char* s, const Char* accept )
255{
256   const Char* a;
257   while (*s) {
258      a = accept;
259      while (*a)
260         if (*a++ == *s)
261            return (Char *) s;
262      s++;
263   }
264   return NULL;
265}
266
267Char* VG_(strcpy) ( Char* dest, const Char* src )
268{
269   Char* dest_orig = dest;
270   while (*src) *dest++ = *src++;
271   *dest = 0;
272   return dest_orig;
273}
274
275/* Copy bytes, not overrunning the end of dest and always ensuring
276   zero termination. */
277void VG_(strncpy_safely) ( Char* dest, const Char* src, SizeT ndest )
278{
279   Int i = 0;
280   while (True) {
281      dest[i] = 0;
282      if (src[i] == 0) return;
283      if (i >= ndest-1) return;
284      dest[i] = src[i];
285      i++;
286   }
287}
288
289Char* VG_(strncpy) ( Char* dest, const Char* src, SizeT ndest )
290{
291   Int i = 0;
292   while (True) {
293      if (i >= ndest) return dest;     /* reached limit */
294      dest[i] = src[i];
295      if (src[i++] == 0) {
296         /* reached NUL;  pad rest with zeroes as required */
297         while (i < ndest) dest[i++] = 0;
298         return dest;
299      }
300   }
301}
302
303Int VG_(strcmp) ( const Char* s1, const Char* s2 )
304{
305   while (True) {
306      if (*s1 == 0 && *s2 == 0) return 0;
307      if (*s1 == 0) return -1;
308      if (*s2 == 0) return 1;
309
310      if (*(UChar*)s1 < *(UChar*)s2) return -1;
311      if (*(UChar*)s1 > *(UChar*)s2) return 1;
312
313      s1++; s2++;
314   }
315}
316
317static Bool isterm ( Char c )
318{
319   return ( VG_(isspace)(c) || 0 == c );
320}
321
322Int VG_(strcmp_ws) ( const Char* s1, const Char* s2 )
323{
324   while (True) {
325      if (isterm(*s1) && isterm(*s2)) return 0;
326      if (isterm(*s1)) return -1;
327      if (isterm(*s2)) return 1;
328
329      if (*(UChar*)s1 < *(UChar*)s2) return -1;
330      if (*(UChar*)s1 > *(UChar*)s2) return 1;
331
332      s1++; s2++;
333   }
334}
335
336Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax )
337{
338   Int n = 0;
339   while (True) {
340      if (n >= nmax) return 0;
341      if (*s1 == 0 && *s2 == 0) return 0;
342      if (*s1 == 0) return -1;
343      if (*s2 == 0) return 1;
344
345      if (*(UChar*)s1 < *(UChar*)s2) return -1;
346      if (*(UChar*)s1 > *(UChar*)s2) return 1;
347
348      s1++; s2++; n++;
349   }
350}
351
352Int VG_(strncmp_ws) ( const Char* s1, const Char* s2, SizeT nmax )
353{
354   Int n = 0;
355   while (True) {
356      if (n >= nmax) return 0;
357      if (isterm(*s1) && isterm(*s2)) return 0;
358      if (isterm(*s1)) return -1;
359      if (isterm(*s2)) return 1;
360
361      if (*(UChar*)s1 < *(UChar*)s2) return -1;
362      if (*(UChar*)s1 > *(UChar*)s2) return 1;
363
364      s1++; s2++; n++;
365   }
366}
367
368Char* VG_(strstr) ( const Char* haystack, Char* needle )
369{
370   Int n;
371   if (haystack == NULL)
372      return NULL;
373   n = VG_(strlen)(needle);
374   while (True) {
375      if (haystack[0] == 0)
376         return NULL;
377      if (VG_(strncmp)(haystack, needle, n) == 0)
378         return (Char*)haystack;
379      haystack++;
380   }
381}
382
383Char* VG_(strchr) ( const Char* s, Char c )
384{
385   while (True) {
386      if (*s == c) return (Char*)s;
387      if (*s == 0) return NULL;
388      s++;
389   }
390}
391
392Char* VG_(strrchr) ( const Char* s, Char c )
393{
394   Int n = VG_(strlen)(s);
395   while (--n > 0) {
396      if (s[n] == c) return (Char*)s + n;
397   }
398   return NULL;
399}
400
401/* ---------------------------------------------------------------------
402   A simple string matching routine, purloined from Hugs98.
403      '*'    matches any sequence of zero or more characters
404      '?'    matches any single character exactly
405      '\c'   matches the character c only (ignoring special chars)
406      c      matches the character c only
407   ------------------------------------------------------------------ */
408
409/* Keep track of recursion depth. */
410static Int recDepth;
411
412// Nb: vg_assert disabled because we can't use it from this module...
413static Bool string_match_wrk ( const Char* pat, const Char* str )
414{
415   //vg_assert(recDepth >= 0 && recDepth < 500);
416   recDepth++;
417   for (;;) {
418      switch (*pat) {
419      case '\0':recDepth--;
420                return (*str=='\0');
421      case '*': do {
422                   if (string_match_wrk(pat+1,str)) {
423                      recDepth--;
424                      return True;
425                   }
426                } while (*str++);
427                recDepth--;
428                return False;
429      case '?': if (*str++=='\0') {
430                   recDepth--;
431                   return False;
432                }
433                pat++;
434                break;
435      case '\\':if (*++pat == '\0') {
436                   recDepth--;
437                   return False; /* spurious trailing \ in pattern */
438                }
439                /* falls through to ... */
440      default : if (*pat++ != *str++) {
441                   recDepth--;
442                   return False;
443                }
444                break;
445      }
446   }
447}
448
449Bool VG_(string_match) ( const Char* pat, const Char* str )
450{
451   Bool b;
452   recDepth = 0;
453   b = string_match_wrk ( pat, str );
454   //vg_assert(recDepth == 0);
455   /*
456   VG_(printf)("%s   %s   %s\n",
457	       b?"TRUE ":"FALSE", pat, str);
458   */
459   return b;
460}
461
462
463/* ---------------------------------------------------------------------
464   mem* functions
465   ------------------------------------------------------------------ */
466
467void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
468{
469   const UChar* s  = (const UChar*)src;
470         UChar* d  =       (UChar*)dest;
471   const UInt*  sI = (const UInt*)src;
472         UInt*  dI =       (UInt*)dest;
473
474   if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
475      while (sz >= 16) {
476         dI[0] = sI[0];
477         dI[1] = sI[1];
478         dI[2] = sI[2];
479         dI[3] = sI[3];
480         sz -= 16;
481         dI += 4;
482         sI += 4;
483      }
484      if (sz == 0)
485         return dest;
486      while (sz >= 4) {
487         dI[0] = sI[0];
488         sz -= 4;
489         dI += 1;
490         sI += 1;
491      }
492      if (sz == 0)
493         return dest;
494      s = (const UChar*)sI;
495      d = (UChar*)dI;
496   }
497
498   while (sz--)
499      *d++ = *s++;
500
501   return dest;
502}
503
504void* VG_(memset) ( void *dest, Int c, SizeT sz )
505{
506   Char *d = (Char *)dest;
507   while (sz >= 4) {
508      d[0] = c;
509      d[1] = c;
510      d[2] = c;
511      d[3] = c;
512      d += 4;
513      sz -= 4;
514   }
515   while (sz > 0) {
516      d[0] = c;
517      d++;
518      sz--;
519   }
520   return dest;
521}
522
523Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
524{
525   Int res;
526   const UChar *p1 = s1;
527   const UChar *p2 = s2;
528   UChar a0;
529   UChar b0;
530
531   while (n != 0) {
532      a0 = p1[0];
533      b0 = p2[0];
534      p1 += 1;
535      p2 += 1;
536      res = a0 - b0;
537      if (res != 0)
538         return res;
539      n -= 1;
540   }
541   return 0;
542}
543
544/* ---------------------------------------------------------------------
545   Misc useful functions
546   ------------------------------------------------------------------ */
547
548/* Returns the base-2 logarithm of x.  Returns -1 if x is not a power of two. */
549Int VG_(log2) ( Int x )
550{
551   Int i;
552   /* Any more than 32 and we overflow anyway... */
553   for (i = 0; i < 32; i++) {
554      if (1 << i == x) return i;
555   }
556   return -1;
557}
558
559
560// Generic shell sort.  Like stdlib.h's qsort().
561void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
562                 Int (*compar)(void*, void*) )
563{
564   Int   incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
565                      9841, 29524, 88573, 265720,
566                      797161, 2391484 };
567   Int   lo = 0;
568   Int   hi = nmemb-1;
569   Int   i, j, h, bigN, hp;
570
571   bigN = hi - lo + 1; if (bigN < 2) return;
572   hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--;
573
574   #define SORT \
575   for ( ; hp >= 0; hp--) { \
576      h = incs[hp]; \
577      for (i = lo + h; i <= hi; i++) { \
578         ASSIGN(v,0, a,i); \
579         j = i; \
580         while (COMPAR(a,(j-h), v,0) > 0) { \
581            ASSIGN(a,j, a,(j-h)); \
582            j = j - h; \
583            if (j <= (lo + h - 1)) break; \
584         } \
585         ASSIGN(a,j, v,0); \
586      } \
587   }
588
589   // Specialised cases
590   if (sizeof(ULong) == size) {
591
592      #define ASSIGN(dst, dsti, src, srci) \
593      (dst)[(dsti)] = (src)[(srci)];
594
595      #define COMPAR(dst, dsti, src, srci) \
596      compar( (void*)(& (dst)[(dsti)]), (void*)(& (src)[(srci)]) )
597
598      ULong* a = (ULong*)base;
599      ULong  v[1];
600
601      SORT;
602
603   } else if (sizeof(UInt) == size) {
604
605      UInt* a = (UInt*)base;
606      UInt  v[1];
607
608      SORT;
609
610   } else if (sizeof(UShort) == size) {
611      UShort* a = (UShort*)base;
612      UShort  v[1];
613
614      SORT;
615
616   } else if (sizeof(UChar) == size) {
617      UChar* a = (UChar*)base;
618      UChar  v[1];
619
620      SORT;
621
622      #undef ASSIGN
623      #undef COMPAR
624
625   } else if ( (4*sizeof(UWord)) == size ) {
626      /* special-case 4 word-elements.  This captures a lot of cases
627         from symbol table reading/canonicalisaton, because both DiLoc
628         and DiSym are 4 word structures. */
629      HChar* a = base;
630      HChar  v[size];
631
632      #define ASSIGN(dst, dsti, src, srci) \
633       do { UWord* dP = (UWord*)&dst[size*(dsti)]; \
634            UWord* sP = (UWord*)&src[size*(srci)]; \
635            dP[0] = sP[0]; \
636            dP[1] = sP[1]; \
637            dP[2] = sP[2]; \
638            dP[3] = sP[3]; \
639          } while (0)
640
641      #define COMPAR(dst, dsti, src, srci) \
642      compar( &dst[size*(dsti)], &src[size*(srci)] )
643
644      SORT;
645
646      #undef ASSIGN
647      #undef COMPAR
648
649   // General case
650   } else {
651      HChar* a = base;
652      HChar  v[size];      // will be at least 'size' bytes
653
654      #define ASSIGN(dst, dsti, src, srci) \
655      VG_(memcpy)( &dst[size*(dsti)], &src[size*(srci)], size );
656
657      #define COMPAR(dst, dsti, src, srci) \
658      compar( &dst[size*(dsti)], &src[size*(srci)] )
659
660      SORT;
661
662      #undef ASSIGN
663      #undef COMPAR
664   }
665   #undef SORT
666}
667
668// This random number generator is based on the one suggested in Kernighan
669// and Ritchie's "The C Programming Language".
670
671// A pseudo-random number generator returning a random UInt.  If pSeed
672// is NULL, it uses its own seed, which starts at zero.  If pSeed is
673// non-NULL, it uses and updates whatever pSeed points at.
674
675static UInt seed = 0;
676
677UInt VG_(random)( /*MOD*/UInt* pSeed )
678{
679   if (pSeed == NULL)
680      pSeed = &seed;
681
682   *pSeed = (1103515245 * *pSeed + 12345);
683   return *pSeed;
684}
685
686/*--------------------------------------------------------------------*/
687/*--- end                                                          ---*/
688/*--------------------------------------------------------------------*/
689
690