m_libcbase.c revision 9abd608244d8123868d027f616fa928156615d5a 
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-2005 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 "core.h"       // XXX: temporary, for NULL, VG_(), Char, etc
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
53Long VG_(atoll) ( Char* str )
54{
55   Bool neg = False;
56   Long n = 0;
57   if (*str == '-') { str++; neg = True; };
58   while (*str >= '0' && *str <= '9') {
59      n = 10*n + (Long)(*str - '0');
60      str++;
61   }
62   if (neg) n = -n;
63   return n;
64}
65
66Long VG_(atoll36) ( Char* str )
67{
68   Bool neg = False;
69   Long n = 0;
70   if (*str == '-') { str++; neg = True; };
71   while (True) {
72      Char c = *str;
73      if (c >= '0' && c <= (Char)'9') {
74         n = 36*n + (Long)(c - '0');
75      }
76      else
77      if (c >= 'A' && c <= (Char)'Z') {
78         n = 36*n + (Long)((c - 'A') + 10);
79      }
80      else
81      if (c >= 'a' && c <= (Char)'z') {
82         n = 36*n + (Long)((c - 'a') + 10);
83      }
84      else {
85	break;
86      }
87      str++;
88   }
89   if (neg) n = -n;
90   return n;
91}
92
93/* ---------------------------------------------------------------------
94   String functions
95   ------------------------------------------------------------------ */
96
97Int VG_(strlen) ( const Char* str )
98{
99   Int i = 0;
100   while (str[i] != 0) i++;
101   return i;
102}
103
104Char* VG_(strcat) ( Char* dest, const Char* src )
105{
106   Char* dest_orig = dest;
107   while (*dest) dest++;
108   while (*src) *dest++ = *src++;
109   *dest = 0;
110   return dest_orig;
111}
112
113Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n )
114{
115   Char* dest_orig = dest;
116   while (*dest) dest++;
117   while (*src && n > 0) { *dest++ = *src++; n--; }
118   *dest = 0;
119   return dest_orig;
120}
121
122Char* VG_(strpbrk) ( const Char* s, const Char* accept )
123{
124   const Char* a;
125   while (*s) {
126      a = accept;
127      while (*a)
128         if (*a++ == *s)
129            return (Char *) s;
130      s++;
131   }
132   return NULL;
133}
134
135Char* VG_(strcpy) ( Char* dest, const Char* src )
136{
137   Char* dest_orig = dest;
138   while (*src) *dest++ = *src++;
139   *dest = 0;
140   return dest_orig;
141}
142
143/* Copy bytes, not overrunning the end of dest and always ensuring
144   zero termination. */
145void VG_(strncpy_safely) ( Char* dest, const Char* src, SizeT ndest )
146{
147   Int i = 0;
148   while (True) {
149      dest[i] = 0;
150      if (src[i] == 0) return;
151      if (i >= ndest-1) return;
152      dest[i] = src[i];
153      i++;
154   }
155}
156
157Char* VG_(strncpy) ( Char* dest, const Char* src, SizeT ndest )
158{
159   Int i = 0;
160   while (True) {
161      if (i >= ndest) return dest;     /* reached limit */
162      dest[i] = src[i];
163      if (src[i++] == 0) {
164         /* reached NUL;  pad rest with zeroes as required */
165         while (i < ndest) dest[i++] = 0;
166         return dest;
167      }
168   }
169}
170
171Int VG_(strcmp) ( const Char* s1, const Char* s2 )
172{
173   while (True) {
174      if (*s1 == 0 && *s2 == 0) return 0;
175      if (*s1 == 0) return -1;
176      if (*s2 == 0) return 1;
177
178      if (*(UChar*)s1 < *(UChar*)s2) return -1;
179      if (*(UChar*)s1 > *(UChar*)s2) return 1;
180
181      s1++; s2++;
182   }
183}
184
185static Bool isterm ( Char c )
186{
187   return ( VG_(isspace)(c) || 0 == c );
188}
189
190Int VG_(strcmp_ws) ( const Char* s1, const Char* s2 )
191{
192   while (True) {
193      if (isterm(*s1) && isterm(*s2)) return 0;
194      if (isterm(*s1)) return -1;
195      if (isterm(*s2)) return 1;
196
197      if (*(UChar*)s1 < *(UChar*)s2) return -1;
198      if (*(UChar*)s1 > *(UChar*)s2) return 1;
199
200      s1++; s2++;
201   }
202}
203
204Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax )
205{
206   Int n = 0;
207   while (True) {
208      if (n >= nmax) return 0;
209      if (*s1 == 0 && *s2 == 0) return 0;
210      if (*s1 == 0) return -1;
211      if (*s2 == 0) return 1;
212
213      if (*(UChar*)s1 < *(UChar*)s2) return -1;
214      if (*(UChar*)s1 > *(UChar*)s2) return 1;
215
216      s1++; s2++; n++;
217   }
218}
219
220Int VG_(strncmp_ws) ( const Char* s1, const Char* s2, SizeT nmax )
221{
222   Int n = 0;
223   while (True) {
224      if (n >= nmax) return 0;
225      if (isterm(*s1) && isterm(*s2)) return 0;
226      if (isterm(*s1)) return -1;
227      if (isterm(*s2)) return 1;
228
229      if (*(UChar*)s1 < *(UChar*)s2) return -1;
230      if (*(UChar*)s1 > *(UChar*)s2) return 1;
231
232      s1++; s2++; n++;
233   }
234}
235
236Char* VG_(strstr) ( const Char* haystack, Char* needle )
237{
238   Int n;
239   if (haystack == NULL)
240      return NULL;
241   n = VG_(strlen)(needle);
242   while (True) {
243      if (haystack[0] == 0)
244         return NULL;
245      if (VG_(strncmp)(haystack, needle, n) == 0)
246         return (Char*)haystack;
247      haystack++;
248   }
249}
250
251Char* VG_(strchr) ( const Char* s, Char c )
252{
253   while (True) {
254      if (*s == c) return (Char*)s;
255      if (*s == 0) return NULL;
256      s++;
257   }
258}
259
260Char* VG_(strrchr) ( const Char* s, Char c )
261{
262   Int n = VG_(strlen)(s);
263   while (--n > 0) {
264      if (s[n] == c) return (Char*)s + n;
265   }
266   return NULL;
267}
268
269/* ---------------------------------------------------------------------
270   A simple string matching routine, purloined from Hugs98.
271      '*'    matches any sequence of zero or more characters
272      '?'    matches any single character exactly
273      '\c'   matches the character c only (ignoring special chars)
274      c      matches the character c only
275   ------------------------------------------------------------------ */
276
277/* Keep track of recursion depth. */
278static Int recDepth;
279
280// Nb: vg_assert disabled because we can't use it from this module...
281static Bool string_match_wrk ( const Char* pat, const Char* str )
282{
283   //vg_assert(recDepth >= 0 && recDepth < 500);
284   recDepth++;
285   for (;;) {
286      switch (*pat) {
287      case '\0':recDepth--;
288                return (*str=='\0');
289      case '*': do {
290                   if (string_match_wrk(pat+1,str)) {
291                      recDepth--;
292                      return True;
293                   }
294                } while (*str++);
295                recDepth--;
296                return False;
297      case '?': if (*str++=='\0') {
298                   recDepth--;
299                   return False;
300                }
301                pat++;
302                break;
303      case '\\':if (*++pat == '\0') {
304                   recDepth--;
305                   return False; /* spurious trailing \ in pattern */
306                }
307                /* falls through to ... */
308      default : if (*pat++ != *str++) {
309                   recDepth--;
310                   return False;
311                }
312                break;
313      }
314   }
315}
316
317Bool VG_(string_match) ( const Char* pat, const Char* str )
318{
319   Bool b;
320   recDepth = 0;
321   b = string_match_wrk ( pat, str );
322   //vg_assert(recDepth == 0);
323   /*
324   VG_(printf)("%s   %s   %s\n",
325	       b?"TRUE ":"FALSE", pat, str);
326   */
327   return b;
328}
329
330
331/* ---------------------------------------------------------------------
332   mem* functions
333   ------------------------------------------------------------------ */
334
335void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
336{
337   const Char *s = (const Char *)src;
338   Char *d = (Char *)dest;
339
340   while (sz--)
341      *d++ = *s++;
342
343   return dest;
344}
345
346void* VG_(memset) ( void *dest, Int c, SizeT sz )
347{
348   Char *d = (Char *)dest;
349
350   while (sz--)
351      *d++ = c;
352
353   return dest;
354}
355
356Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
357{
358   Int res;
359   UChar a0;
360   UChar b0;
361
362   while (n != 0) {
363      a0 = ((UChar *) s1)[0];
364      b0 = ((UChar *) s2)[0];
365      s1 += 1;
366      s2 += 1;
367      res = a0 - b0;
368      if (res != 0)
369         return res;
370      n -= 1;
371   }
372   return 0;
373}
374
375/* ---------------------------------------------------------------------
376   Misc useful functions
377   ------------------------------------------------------------------ */
378
379Int VG_(log2) ( Int x )
380{
381   Int i;
382   /* Any more than 32 and we overflow anyway... */
383   for (i = 0; i < 32; i++) {
384      if (1 << i == x) return i;
385   }
386   return -1;
387}
388
389
390// Generic shell sort.  Like stdlib.h's qsort().
391void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
392                 Int (*compar)(void*, void*) )
393{
394   Int   incs[14] = { 1, 4, 13, 40, 121, 364, 1093, 3280,
395                      9841, 29524, 88573, 265720,
396                      797161, 2391484 };
397   Int   lo = 0;
398   Int   hi = nmemb-1;
399   Int   i, j, h, bigN, hp;
400
401   bigN = hi - lo + 1; if (bigN < 2) return;
402   hp = 0; while (hp < 14 && incs[hp] < bigN) hp++; hp--;
403
404   #define SORT \
405   for ( ; hp >= 0; hp--) { \
406      h = incs[hp]; \
407      for (i = lo + h; i <= hi; i++) { \
408         ASSIGN(v,0, a,i); \
409         j = i; \
410         while (COMPAR(a,(j-h), v,0) > 0) { \
411            ASSIGN(a,j, a,(j-h)); \
412            j = j - h; \
413            if (j <= (lo + h - 1)) break; \
414         } \
415         ASSIGN(a,j, v,0); \
416      } \
417   }
418
419   // Specialised cases
420   if (sizeof(ULong) == size) {
421
422      #define ASSIGN(dst, dsti, src, srci) \
423      (dst)[(dsti)] = (src)[(srci)];
424
425      #define COMPAR(dst, dsti, src, srci) \
426      compar( (void*)(& (dst)[(dsti)]), (void*)(& (src)[(srci)]) )
427
428      ULong* a = (ULong*)base;
429      ULong  v[1];
430
431      SORT;
432
433   } else if (sizeof(UInt) == size) {
434
435      UInt* a = (UInt*)base;
436      UInt  v[1];
437
438      SORT;
439
440   } else if (sizeof(UShort) == size) {
441      UShort* a = (UShort*)base;
442      UShort  v[1];
443
444      SORT;
445
446   } else if (sizeof(UChar) == size) {
447      UChar* a = (UChar*)base;
448      UChar  v[1];
449
450      SORT;
451
452      #undef ASSIGN
453      #undef COMPAR
454
455   // General case
456   } else {
457      char* a = base;
458      char  v[size];      // will be at least 'size' bytes
459
460      #define ASSIGN(dst, dsti, src, srci) \
461      VG_(memcpy)( &dst[size*(dsti)], &src[size*(srci)], size );
462
463      #define COMPAR(dst, dsti, src, srci) \
464      compar( &dst[size*(dsti)], &src[size*(srci)] )
465
466      SORT;
467
468      #undef ASSIGN
469      #undef COMPAR
470   }
471   #undef SORT
472}
473
474/*--------------------------------------------------------------------*/
475/*--- end                                                          ---*/
476/*--------------------------------------------------------------------*/
477
478