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
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_dec_digit(Char c, Long* digit)
54{
55   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
56   return False;
57}
58
59static 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
67Long 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
92Long 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
125double 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
158Char 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
171SizeT VG_(strlen) ( const Char* str )
172{
173   SizeT i = 0;
174   while (str[i] != 0) i++;
175   return i;
176}
177
178Char* 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
187Char* 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
196Char* 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
209Char* 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. */
219void 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
231Char* 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
245Int 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
259Int 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
275Int 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
291Int 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
311Char* 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
326Char* 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
341Char* 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
350Char* 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
359SizeT 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
375SizeT 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
392void* 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
429void* 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
447void* 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
482Int 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
538static 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
545static 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
559static 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. */
647Int 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.
659void 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
673static UInt seed = 0;
674
675UInt 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