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-2017 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_libcassert.h"    // VG_(exit_now)
33#include "pub_core_debuglog.h"      // VG_(debugLog)
34#include "pub_core_libcbase.h"
35
36
37/* ---------------------------------------------------------------------
38   Assert machinery for use in this file. vg_assert cannot be called
39   here due to cyclic dependencies.
40   ------------------------------------------------------------------ */
41#if 0
42#define libcbase_assert(expr)                             \
43  ((void) (LIKELY(expr) ? 0 :                             \
44           (ML_(libcbase_assert_fail)(#expr,              \
45                                __FILE__, __LINE__,       \
46                                __PRETTY_FUNCTION__))))
47
48static void ML_(libcbase_assert_fail)( const HChar *expr,
49                                       const HChar *file,
50                                       Int line,
51                                       const HChar *fn )
52{
53   VG_(debugLog)(0, "libcbase",
54                    "Valgrind: FATAL: assertion failed:\n");
55   VG_(debugLog)(0, "libcbase", "  %s\n", expr);
56   VG_(debugLog)(0, "libcbase", "  at %s:%d (%s)\n", file, line, fn);
57   VG_(debugLog)(0, "libcbase", "Exiting now.\n");
58   VG_(exit_now)(1);
59}
60#endif
61
62/* ---------------------------------------------------------------------
63   HChar functions.
64   ------------------------------------------------------------------ */
65
66Bool VG_(isspace) ( HChar c )
67{
68   return (c == ' '  || c == '\n' || c == '\t' ||
69           c == '\f' || c == '\v' || c == '\r');
70}
71
72Bool VG_(isdigit) ( HChar c )
73{
74   return (c >= '0' && c <= '9');
75}
76
77/* ---------------------------------------------------------------------
78   Converting strings to numbers
79   ------------------------------------------------------------------ */
80
81static Bool is_dec_digit(HChar c, Long* digit)
82{
83   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
84   return False;
85}
86
87static Bool is_hex_digit(HChar c, Long* digit)
88{
89   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
90   if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; }
91   if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; }
92   return False;
93}
94
95Long VG_(strtoll10) ( const HChar* str, HChar** endptr )
96{
97   Bool neg = False, converted = False;
98   Long n = 0, digit = 0;
99   const HChar* str0 = str;
100
101   // Skip leading whitespace.
102   while (VG_(isspace)(*str)) str++;
103
104   // Allow a leading '-' or '+'.
105   if (*str == '-') { str++; neg = True; }
106   else if (*str == '+') { str++; }
107
108   while (is_dec_digit(*str, &digit)) {
109      converted = True;          // Ok, we've actually converted a digit.
110      n = 10*n + digit;
111      str++;
112   }
113
114   if (!converted) str = str0;   // If nothing converted, endptr points to
115   if (neg) n = -n;              //   the start of the string.
116   if (endptr)
117      *endptr = CONST_CAST(HChar *,str); // Record first failing character.
118   return n;
119}
120
121ULong VG_(strtoull10) ( const HChar* str, HChar** endptr )
122{
123   Bool converted = False;
124   ULong n = 0;
125   Long digit = 0;
126   const HChar* str0 = str;
127
128   // Skip leading whitespace.
129   while (VG_(isspace)(*str)) str++;
130
131   // Allow a leading '+'.
132   if (*str == '+') { str++; }
133
134   while (is_dec_digit(*str, &digit)) {
135      converted = True;          // Ok, we've actually converted a digit.
136      n = 10*n + digit;
137      str++;
138   }
139
140   if (!converted) str = str0;   // If nothing converted, endptr points to
141   //   the start of the string.
142   if (endptr)
143      *endptr = CONST_CAST(HChar *,str); // Record first failing character.
144   return n;
145}
146
147Long VG_(strtoll16) ( const HChar* str, HChar** endptr )
148{
149   Bool neg = False, converted = False;
150   Long n = 0, digit = 0;
151   const HChar* str0 = str;
152
153   // Skip leading whitespace.
154   while (VG_(isspace)(*str)) str++;
155
156   // Allow a leading '-' or '+'.
157   if (*str == '-') { str++; neg = True; }
158   else if (*str == '+') { str++; }
159
160   // Allow leading "0x", but only if there's a hex digit
161   // following it.
162   if (*str == '0'
163    && (*(str+1) == 'x' || *(str+1) == 'X')
164    && is_hex_digit( *(str+2), &digit )) {
165      str += 2;
166   }
167
168   while (is_hex_digit(*str, &digit)) {
169      converted = True;          // Ok, we've actually converted a digit.
170      n = 16*n + digit;
171      str++;
172   }
173
174   if (!converted) str = str0;   // If nothing converted, endptr points to
175   if (neg) n = -n;              //   the start of the string.
176   if (endptr)
177      *endptr = CONST_CAST(HChar *,str); // Record first failing character.
178   return n;
179}
180
181ULong VG_(strtoull16) ( const HChar* str, HChar** endptr )
182{
183   Bool converted = False;
184   ULong n = 0;
185   Long digit = 0;
186   const HChar* str0 = str;
187
188   // Skip leading whitespace.
189   while (VG_(isspace)(*str)) str++;
190
191   // Allow a leading '+'.
192   if (*str == '+') { str++; }
193
194   // Allow leading "0x", but only if there's a hex digit
195   // following it.
196   if (*str == '0'
197    && (*(str+1) == 'x' || *(str+1) == 'X')
198    && is_hex_digit( *(str+2), &digit )) {
199      str += 2;
200   }
201
202   while (is_hex_digit(*str, &digit)) {
203      converted = True;          // Ok, we've actually converted a digit.
204      n = 16*n + digit;
205      str++;
206   }
207
208   if (!converted) str = str0;   // If nothing converted, endptr points to
209   //   the start of the string.
210   if (endptr)
211      *endptr = CONST_CAST(HChar *,str); // Record first failing character.
212   return n;
213}
214
215double VG_(strtod) ( const HChar* str, HChar** endptr )
216{
217   Bool neg = False;
218   Long digit;
219   double n = 0, frac = 0, x = 0.1;
220
221   // Skip leading whitespace.
222   while (VG_(isspace)(*str)) str++;
223
224   // Allow a leading '-' or '+'.
225   if (*str == '-') { str++; neg = True; }
226   else if (*str == '+') { str++; }
227
228   while (is_dec_digit(*str, &digit)) {
229      n = 10*n + digit;
230      str++;
231   }
232
233   if (*str == '.') {
234      str++;
235      while (is_dec_digit(*str, &digit)) {
236         frac += x*digit;
237         x /= 10;
238         str++;
239      }
240   }
241
242   n += frac;
243   if (neg) n = -n;
244   if (endptr)
245      *endptr = CONST_CAST(HChar *,str); // Record first failing character.
246   return n;
247}
248
249HChar VG_(tolower) ( HChar c )
250{
251   if ( c >= 'A'  &&  c <= 'Z' ) {
252      return c - 'A' + 'a';
253   } else {
254      return c;
255   }
256}
257
258/* ---------------------------------------------------------------------
259   String functions
260   ------------------------------------------------------------------ */
261
262SizeT VG_(strlen) ( const HChar* str )
263{
264   SizeT i = 0;
265   while (str[i] != 0) i++;
266   return i;
267}
268
269SizeT VG_(strnlen)(const HChar* str, SizeT n)
270{
271   SizeT i = 0;
272   while (i < n && str[i] != 0)
273      i++;
274   return i;
275}
276
277HChar* VG_(strcat) ( HChar* dest, const HChar* src )
278{
279   HChar* dest_orig = dest;
280   while (*dest) dest++;
281   while (*src) *dest++ = *src++;
282   *dest = 0;
283   return dest_orig;
284}
285
286HChar* VG_(strncat) ( HChar* dest, const HChar* src, SizeT n )
287{
288   HChar* dest_orig = dest;
289   while (*dest) dest++;
290   while (*src && n > 0) { *dest++ = *src++; n--; }
291   *dest = 0;
292   return dest_orig;
293}
294
295HChar* VG_(strpbrk) ( const HChar* s, const HChar* accpt )
296{
297   const HChar* a;
298   while (*s) {
299      a = accpt;
300      while (*a)
301         if (*a++ == *s)
302            return CONST_CAST(HChar *,s);
303      s++;
304   }
305   return NULL;
306}
307
308HChar* VG_(strcpy) ( HChar* dest, const HChar* src )
309{
310   HChar* dest_orig = dest;
311   while (*src) *dest++ = *src++;
312   *dest = 0;
313   return dest_orig;
314}
315
316HChar* VG_(strncpy) ( HChar* dest, const HChar* src, SizeT ndest )
317{
318   SizeT i = 0;
319   while (True) {
320      if (i >= ndest) return dest;     /* reached limit */
321      dest[i] = src[i];
322      if (src[i++] == 0) {
323         /* reached NUL;  pad rest with zeroes as required */
324         while (i < ndest) dest[i++] = 0;
325         return dest;
326      }
327   }
328}
329
330/* Copies up to n-1 bytes from src to dst. Then nul-terminate dst if n > 0.
331   Returns strlen(src). Does not zero-fill the remainder of dst. */
332SizeT VG_(strlcpy)(HChar *dst, const HChar *src, SizeT n)
333{
334   const HChar *src_orig = src;
335   SizeT m = 0;
336
337   while (m < n - 1 && *src != '\0') {
338      m++;
339      *dst++ = *src++;
340   }
341
342   /* Nul-terminate dst. */ \
343   if (n > 0)
344      *dst = 0;
345
346   /* Finish counting strlen(src). */ \
347   while (*src != '\0')
348      src++;
349
350   return src - src_orig;
351}
352
353Int VG_(strcmp) ( const HChar* s1, const HChar* s2 )
354{
355   while (True) {
356      if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
357      if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
358
359      /* *s1 == *s2 */
360      if (*s1 == 0) return 0;
361
362      s1++; s2++;
363   }
364}
365
366Int VG_(strcasecmp) ( const HChar* s1, const HChar* s2 )
367{
368   while (True) {
369      UChar c1 = (UChar)VG_(tolower)(*s1);
370      UChar c2 = (UChar)VG_(tolower)(*s2);
371      if (c1 < c2) return -1;
372      if (c1 > c2) return 1;
373
374      /* c1 == c2 */
375      if (c1 == 0) return 0;
376
377      s1++; s2++;
378   }
379}
380
381Int VG_(strncmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
382{
383   SizeT n = 0;
384   while (True) {
385      if (n >= nmax) return 0;
386      if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
387      if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
388
389      /* *s1 == *s2 */
390      if (*s1 == 0) return 0;
391
392      s1++; s2++; n++;
393   }
394}
395
396Int VG_(strncasecmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
397{
398   Int n = 0;
399   while (True) {
400      UChar c1;
401      UChar c2;
402      if (n >= nmax) return 0;
403      c1 = (UChar)VG_(tolower)(*s1);
404      c2 = (UChar)VG_(tolower)(*s2);
405      if (c1 < c2) return -1;
406      if (c1 > c2) return 1;
407
408      /* c1 == c2 */
409      if (c1 == 0) return 0;
410
411      s1++; s2++; n++;
412   }
413}
414
415HChar* VG_(strstr) ( const HChar* haystack, const HChar* needle )
416{
417   SizeT n;
418   if (haystack == NULL)
419      return NULL;
420   n = VG_(strlen)(needle);
421   while (True) {
422      if (haystack[0] == 0)
423         return NULL;
424      if (VG_(strncmp)(haystack, needle, n) == 0)
425         return CONST_CAST(HChar *,haystack);
426      haystack++;
427   }
428}
429
430HChar* VG_(strcasestr) ( const HChar* haystack, const HChar* needle )
431{
432   Int n;
433   if (haystack == NULL)
434      return NULL;
435   n = VG_(strlen)(needle);
436   while (True) {
437      if (haystack[0] == 0)
438         return NULL;
439      if (VG_(strncasecmp)(haystack, needle, n) == 0)
440         return CONST_CAST(HChar *,haystack);
441      haystack++;
442   }
443}
444
445HChar* VG_(strchr) ( const HChar* s, HChar c )
446{
447   while (True) {
448      if (*s == c) return CONST_CAST(HChar *,s);
449      if (*s == 0) return NULL;
450      s++;
451   }
452}
453
454HChar* VG_(strrchr) ( const HChar* s, HChar c )
455{
456   Int n = VG_(strlen)(s);
457   while (--n > 0) {
458      if (s[n] == c) return CONST_CAST(HChar *,s) + n;
459   }
460   return NULL;
461}
462
463/* (code copied from glib then updated to valgrind types) */
464static HChar *olds;
465HChar *
466VG_(strtok) (HChar *s, const HChar *delim)
467{
468   return VG_(strtok_r) (s, delim, &olds);
469}
470
471HChar *
472VG_(strtok_r) (HChar* s, const HChar* delim, HChar** saveptr)
473{
474   HChar *token;
475
476   if (s == NULL)
477      s = *saveptr;
478
479   /* Scan leading delimiters.  */
480   s += VG_(strspn) (s, delim);
481   if (*s == '\0')
482      {
483         *saveptr = s;
484         return NULL;
485      }
486
487   /* Find the end of the token.  */
488   token = s;
489   s = VG_(strpbrk) (token, delim);
490   if (s == NULL)
491      /* This token finishes the string.  */
492      *saveptr = token + VG_(strlen) (token);
493   else
494      {
495         /* Terminate the token and make OLDS point past it.  */
496         *s = '\0';
497         *saveptr = s + 1;
498      }
499   return token;
500}
501
502static Bool isHex ( HChar c )
503{
504  return ((c >= '0' && c <= '9') ||
505	  (c >= 'a' && c <= 'f') ||
506	  (c >= 'A' && c <= 'F'));
507}
508
509static UInt fromHex ( HChar c )
510{
511   if (c >= '0' && c <= '9')
512      return (UInt)c - (UInt)'0';
513   if (c >= 'a' && c <= 'f')
514      return 10 +  (UInt)c - (UInt)'a';
515   if (c >= 'A' && c <= 'F')
516      return 10 +  (UInt)c - (UInt)'A';
517   /*NOTREACHED*/
518   // ??? need to vg_assert(0);
519   return 0;
520}
521
522Bool VG_(parse_Addr) ( const HChar** ppc, Addr* result )
523{
524   Int used, limit = 2 * sizeof(Addr);
525   if (**ppc != '0')
526      return False;
527   (*ppc)++;
528   if (**ppc != 'x')
529      return False;
530   (*ppc)++;
531   *result = 0;
532   used = 0;
533   while (isHex(**ppc)) {
534      // ??? need to vg_assert(d < fromHex(**ppc));
535      *result = ((*result) << 4) | fromHex(**ppc);
536      (*ppc)++;
537      used++;
538      if (used > limit) return False;
539   }
540   if (used == 0)
541      return False;
542   return True;
543}
544
545Bool VG_(parse_UInt) ( const HChar** ppc, UInt* result )
546{
547   ULong res64 = 0;
548   Int used, limit = 10;
549   used = 0;
550   while (VG_(isdigit)(**ppc)) {
551      res64 = res64 * 10 + ((ULong)(**ppc)) - (ULong)'0';
552      (*ppc)++;
553      used++;
554      if (used > limit) return False;
555   }
556   if (used == 0)
557      return False;
558   if ((res64 >> 32) != 0)
559      return False;
560   *result = (UInt)res64;
561   return True;
562}
563
564Bool VG_(parse_enum_set) ( const HChar *tokens,
565                           Bool  allow_all,
566                           const HChar *input,
567                           UInt *enum_set)
568{
569   const SizeT tokens_len = VG_(strlen)(tokens);
570   if (tokens_len > 1000) return False; /* "obviously invalid" */
571   HChar  tok_tokens[tokens_len+1];
572   HChar *tokens_saveptr;
573   HChar *token;
574   UInt token_nr = 0;
575   UInt all_set = 0;
576
577   const SizeT input_len = VG_(strlen)(input);
578   if (input_len > 1000) return False; /* "obviously invalid" */
579   HChar  tok_input[input_len+1];
580   HChar *input_saveptr;
581   HChar *input_word;
582   UInt word_nr = 0;
583   UInt known_words = 0;
584   Bool seen_all_kw = False;
585   Bool seen_none_kw = False;
586
587   *enum_set = 0;
588
589   VG_(strcpy) (tok_input, input);
590   for (input_word = VG_(strtok_r)(tok_input, ",", &input_saveptr);
591        input_word;
592        input_word = VG_(strtok_r)(NULL, ",", &input_saveptr)) {
593      word_nr++;
594      if (allow_all && 0 == VG_(strcmp)(input_word, "all")) {
595         seen_all_kw = True;
596         known_words++;
597      } else if (0 == VG_(strcmp)(input_word, "none")) {
598         seen_none_kw = True;
599         known_words++;
600      }
601
602      // Scan tokens + compute all_set. Do that even if all or none was
603      // recognised to have a correct value for all_set when exiting
604      // of the 'input' loop.
605      all_set = 0;
606      token_nr = 0;
607      VG_(strcpy) (tok_tokens, tokens);
608      for (token = VG_(strtok_r)(tok_tokens, ",", &tokens_saveptr);
609           token;
610           token = VG_(strtok_r)(NULL, ",", &tokens_saveptr)) {
611         if (0 != VG_(strcmp)(token, "-")) {
612            if (0 == VG_(strcmp)(input_word, token)) {
613               *enum_set |= 1 << token_nr;
614               known_words++;
615            }
616            all_set |= 1 << token_nr;
617         }
618         token_nr++;
619      }
620   }
621
622   if (known_words != word_nr)
623      return False; // One or more input_words not recognised.
624   if (seen_all_kw) {
625      if (seen_none_kw || *enum_set)
626         return False; // mixing all with either none or a specific value.
627      *enum_set = all_set;
628   } else if (seen_none_kw) {
629      if (seen_all_kw || *enum_set)
630         return False; // mixing none with either all or a specific value.
631      *enum_set = 0;
632   } else {
633      // seen neither all or none, we must see at least one value
634      if (*enum_set == 0)
635         return False;
636   }
637
638   return True;
639}
640
641SizeT VG_(strspn) ( const HChar* s, const HChar* accpt )
642{
643   const HChar *p, *a;
644   SizeT count = 0;
645   for (p = s; *p != '\0'; ++p) {
646      for (a = accpt; *a != '\0'; ++a)
647         if (*p == *a)
648            break;
649      if (*a == '\0')
650         return count;
651      else
652         ++count;
653   }
654   return count;
655}
656
657SizeT VG_(strcspn) ( const HChar* s, const HChar* reject )
658{
659   SizeT count = 0;
660   while (*s != '\0') {
661      if (VG_(strchr) (reject, *s++) == NULL)
662         ++count;
663      else
664         return count;
665   }
666   return count;
667}
668
669
670/* ---------------------------------------------------------------------
671   mem* functions
672   ------------------------------------------------------------------ */
673
674void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
675{
676   const UChar* s  = (const UChar*)src;
677         UChar* d  =       (UChar*)dest;
678   const UInt*  sI = (const UInt*)src;
679         UInt*  dI =       (UInt*)dest;
680
681   if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
682      while (sz >= 16) {
683         dI[0] = sI[0];
684         dI[1] = sI[1];
685         dI[2] = sI[2];
686         dI[3] = sI[3];
687         sz -= 16;
688         dI += 4;
689         sI += 4;
690      }
691      if (sz == 0)
692         return dest;
693      while (sz >= 4) {
694         dI[0] = sI[0];
695         sz -= 4;
696         dI += 1;
697         sI += 1;
698      }
699      if (sz == 0)
700         return dest;
701      s = (const UChar*)sI;
702      d = (UChar*)dI;
703   }
704
705   /* If we're unlucky, the alignment constraints for the fast case
706      above won't apply, and we'll have to do it all here.  Hence the
707      unrolling. */
708   while (sz >= 4) {
709      d[0] = s[0];
710      d[1] = s[1];
711      d[2] = s[2];
712      d[3] = s[3];
713      d += 4;
714      s += 4;
715      sz -= 4;
716   }
717   while (sz >= 1) {
718      d[0] = s[0];
719      d += 1;
720      s += 1;
721      sz -= 1;
722   }
723
724   return dest;
725}
726
727void* VG_(memmove)(void *dest, const void *src, SizeT sz)
728{
729   SizeT i;
730   if (sz == 0)
731      return dest;
732   if (dest < src) {
733      for (i = 0; i < sz; i++) {
734         ((UChar*)dest)[i] = ((const UChar*)src)[i];
735      }
736   }
737   else if (dest > src) {
738      for (i = 0; i < sz; i++) {
739         ((UChar*)dest)[sz-i-1] = ((const UChar*)src)[sz-i-1];
740      }
741   }
742   return dest;
743}
744
745void* VG_(memset) ( void *destV, Int c, SizeT sz )
746{
747   UInt   c4;
748   UChar* d = destV;
749   UChar uc = c;
750
751   while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) {
752      d[0] = uc;
753      d++;
754      sz--;
755   }
756   UInt* d4 = ASSUME_ALIGNED(UInt*, d);
757   if (sz == 0)
758      return destV;
759   c4 = uc;
760   c4 |= (c4 << 8);
761   c4 |= (c4 << 16);
762   while (sz >= 16) {
763      d4[0] = c4;
764      d4[1] = c4;
765      d4[2] = c4;
766      d4[3] = c4;
767      d4 += 4;
768      sz -= 16;
769   }
770   while (sz >= 4) {
771      d4[0] = c4;
772      d4 += 1;
773      sz -= 4;
774   }
775   d = (UChar*) d4;
776   while (sz >= 1) {
777      d[0] = c;
778      d++;
779      sz--;
780   }
781   return destV;
782}
783
784Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
785{
786   Int res;
787   const UChar *p1 = s1;
788   const UChar *p2 = s2;
789   UChar a0;
790   UChar b0;
791
792   while (n != 0) {
793      a0 = p1[0];
794      b0 = p2[0];
795      p1 += 1;
796      p2 += 1;
797      res = a0 - b0;
798      if (res != 0)
799         return res;
800      n -= 1;
801   }
802   return 0;
803}
804
805/* ---------------------------------------------------------------------
806   Misc useful functions
807   ------------------------------------------------------------------ */
808
809/////////////////////////////////////////////////////////////
810/////////////////////////////////////////////////////////////
811/// begin Bentley-McIlroy style quicksort
812/// See "Engineering a Sort Function".  Jon L Bentley, M. Douglas
813/// McIlroy.  Software Practice and Experience Vol 23(11), Nov 1993.
814
815#define BM_MIN(a, b)                                     \
816   (a) < (b) ? a : b
817
818#define BM_SWAPINIT(a, es)                               \
819   swaptype =   ((a-(Char*)0) | es) % sizeof(Word)  ? 2  \
820              : es > (SizeT)sizeof(Word) ? 1             \
821              : 0
822
823#define BM_EXCH(a, b, t)                                 \
824   (t = a, a = b, b = t)
825
826#define BM_SWAP(a, b)                                    \
827   swaptype != 0                                         \
828      ? bm_swapfunc(a, b, es, swaptype)                  \
829      : (void)BM_EXCH(*ASSUME_ALIGNED(Word*, (a)),       \
830                      *ASSUME_ALIGNED(Word*, (b)), t)
831
832#define BM_VECSWAP(a, b, n)                              \
833   if (n > 0) bm_swapfunc(a, b, n, swaptype)
834
835#define BM_PVINIT(pv, pm)                                \
836   if (swaptype != 0)                                    \
837      pv = a, BM_SWAP(pv, pm);                           \
838   else                                                  \
839      pv = (Char*)&v, v = *ASSUME_ALIGNED(Word*, pm)
840
841static Char* bm_med3 ( Char* a, Char* b, Char* c,
842                       Int (*cmp)(const void*, const void*) ) {
843   return cmp(a, b) < 0
844          ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
845          : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
846}
847
848static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
849{
850   if (swaptype <= 1) {
851      Word t;
852      for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
853                                        n -= sizeof(Word))
854         BM_EXCH(*ASSUME_ALIGNED(Word*, a), *ASSUME_ALIGNED(Word*, b), t);
855   } else {
856      Char t;
857      for ( ; n > 0; a += 1, b += 1, n -= 1)
858         BM_EXCH(*a, *b, t);
859   }
860}
861
862static void bm_qsort ( Char* a, SizeT n, SizeT es,
863                       Int (*cmp)(const void*, const void*) )
864{
865   Char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
866   Int   r, swaptype;
867   Word  t, v;
868   SizeT s, s1, s2;
869  tailcall:
870   BM_SWAPINIT(a, es);
871   if (n < 7) {
872      for (pm = a + es; pm < a + n*es; pm += es)
873         for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
874            BM_SWAP(pl, pl-es);
875      return;
876   }
877   pm = a + (n/2)*es;
878   if (n > 7) {
879      pl = a;
880      pn = a + (n-1)*es;
881      if (n > 40) {
882         s = (n/8)*es;
883         pl = bm_med3(pl, pl+s, pl+2*s, cmp);
884         pm = bm_med3(pm-s, pm, pm+s, cmp);
885         pn = bm_med3(pn-2*s, pn-s, pn, cmp);
886      }
887      pm = bm_med3(pl, pm, pn, cmp);
888   }
889   BM_PVINIT(pv, pm);
890   pa = pb = a;
891   pc = pd = a + (n-1)*es;
892   for (;;) {
893      while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
894         if (r == 0) { BM_SWAP(pa, pb); pa += es; }
895         pb += es;
896      }
897      while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
898         if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
899         pc -= es;
900      }
901      if (pb > pc) break;
902      BM_SWAP(pb, pc);
903      pb += es;
904      pc -= es;
905   }
906   pn = a + n*es;
907   s = BM_MIN(pa-a,  pb-pa   ); BM_VECSWAP(a,  pb-s, s);
908   s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
909   /* Now recurse.  Do the smaller partition first with an explicit
910      recursion, then do the larger partition using a tail call.
911      Except we can't rely on gcc to implement a tail call in any sane
912      way, so simply jump back to the start.  This guarantees stack
913      growth can never exceed O(log N) even in the worst case. */
914   s1 = pb-pa;
915   s2 = pd-pc;
916   if (s1 < s2) {
917      if (s1 > es) {
918         bm_qsort(a, s1/es, es, cmp);
919      }
920      if (s2 > es) {
921         /* bm_qsort(pn-s2, s2/es, es, cmp); */
922         a = pn-s2; n = s2/es; es = es; cmp = cmp;
923         goto tailcall;
924      }
925   } else {
926      if (s2 > es) {
927         bm_qsort(pn-s2, s2/es, es, cmp);
928      }
929      if (s1 > es) {
930         /* bm_qsort(a, s1/es, es, cmp); */
931         a = a; n = s1/es; es = es; cmp = cmp;
932         goto tailcall;
933      }
934   }
935}
936
937#undef BM_MIN
938#undef BM_SWAPINIT
939#undef BM_EXCH
940#undef BM_SWAP
941#undef BM_VECSWAP
942#undef BM_PVINIT
943
944/// end Bentley-McIlroy style quicksort
945/////////////////////////////////////////////////////////////
946/////////////////////////////////////////////////////////////
947
948/* Returns the base-2 logarithm of x.  Returns -1 if x is not a power
949   of two. */
950Int VG_(log2) ( UInt x )
951{
952   Int i;
953   /* Any more than 32 and we overflow anyway... */
954   for (i = 0; i < 32; i++) {
955      if ((1U << i) == x) return i;
956   }
957   return -1;
958}
959
960/* Ditto for 64 bit numbers. */
961Int VG_(log2_64) ( ULong x )
962{
963   Int i;
964   for (i = 0; i < 64; i++) {
965      if ((1ULL << i) == x) return i;
966   }
967   return -1;
968}
969
970// Generic quick sort.
971void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
972                 Int (*compar)(const void*, const void*) )
973{
974   bm_qsort(base,nmemb,size,compar);
975}
976
977
978// This random number generator is based on the one suggested in Kernighan
979// and Ritchie's "The C Programming Language".
980
981// A pseudo-random number generator returning a random UInt.  If pSeed
982// is NULL, it uses its own seed, which starts at zero.  If pSeed is
983// non-NULL, it uses and updates whatever pSeed points at.
984
985UInt VG_(random)( /*MOD*/UInt* pSeed )
986{
987   static UInt seed = 0;
988
989   if (pSeed == NULL)
990      pSeed = &seed;
991
992   *pSeed = (1103515245 * *pSeed + 12345);
993   return *pSeed;
994}
995
996
997/* The following Adler-32 checksum code is taken from zlib-1.2.3, which
998   has the following copyright notice. */
999/*
1000Copyright notice:
1001
1002 (C) 1995-2004 Jean-loup Gailly and Mark Adler
1003
1004  This software is provided 'as-is', without any express or implied
1005  warranty.  In no event will the authors be held liable for any damages
1006  arising from the use of this software.
1007
1008  Permission is granted to anyone to use this software for any purpose,
1009  including commercial applications, and to alter it and redistribute it
1010  freely, subject to the following restrictions:
1011
1012  1. The origin of this software must not be misrepresented; you must not
1013     claim that you wrote the original software. If you use this software
1014     in a product, an acknowledgment in the product documentation would be
1015     appreciated but is not required.
1016  2. Altered source versions must be plainly marked as such, and must not be
1017     misrepresented as being the original software.
1018  3. This notice may not be removed or altered from any source distribution.
1019
1020  Jean-loup Gailly        Mark Adler
1021  jloup@gzip.org          madler@alumni.caltech.edu
1022
1023If you use the zlib library in a product, we would appreciate *not*
1024receiving lengthy legal documents to sign. The sources are provided
1025for free but without warranty of any kind.  The library has been
1026entirely written by Jean-loup Gailly and Mark Adler; it does not
1027include third-party code.
1028
1029If you redistribute modified sources, we would appreciate that you include
1030in the file ChangeLog history information documenting your changes. Please
1031read the FAQ for more information on the distribution of modified source
1032versions.
1033*/
1034
1035/* Update a running Adler-32 checksum with the bytes buf[0..len-1] and
1036   return the updated checksum. If buf is NULL, this function returns
1037   the required initial value for the checksum. An Adler-32 checksum is
1038   almost as reliable as a CRC32 but can be computed much faster. */
1039UInt VG_(adler32)( UInt adler, const UChar* buf, UInt len )
1040{
1041#  define BASE 65521UL    /* largest prime smaller than 65536 */
1042#  define NMAX 5552
1043   /* NMAX is the largest n such that
1044      255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
1045
1046#  define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
1047#  define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
1048#  define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
1049#  define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
1050#  define DO16(buf)   DO8(buf,0); DO8(buf,8);
1051
1052   /* The zlib sources recommend this definition of MOD if the
1053      processor cannot do integer division in hardware. */
1054#  define MOD(a) \
1055      do { \
1056          if (a >= (BASE << 16)) a -= (BASE << 16); \
1057          if (a >= (BASE << 15)) a -= (BASE << 15); \
1058          if (a >= (BASE << 14)) a -= (BASE << 14); \
1059          if (a >= (BASE << 13)) a -= (BASE << 13); \
1060          if (a >= (BASE << 12)) a -= (BASE << 12); \
1061          if (a >= (BASE << 11)) a -= (BASE << 11); \
1062          if (a >= (BASE << 10)) a -= (BASE << 10); \
1063          if (a >= (BASE << 9)) a -= (BASE << 9); \
1064          if (a >= (BASE << 8)) a -= (BASE << 8); \
1065          if (a >= (BASE << 7)) a -= (BASE << 7); \
1066          if (a >= (BASE << 6)) a -= (BASE << 6); \
1067          if (a >= (BASE << 5)) a -= (BASE << 5); \
1068          if (a >= (BASE << 4)) a -= (BASE << 4); \
1069          if (a >= (BASE << 3)) a -= (BASE << 3); \
1070          if (a >= (BASE << 2)) a -= (BASE << 2); \
1071          if (a >= (BASE << 1)) a -= (BASE << 1); \
1072          if (a >= BASE) a -= BASE; \
1073      } while (0)
1074#  define MOD4(a) \
1075      do { \
1076          if (a >= (BASE << 4)) a -= (BASE << 4); \
1077          if (a >= (BASE << 3)) a -= (BASE << 3); \
1078          if (a >= (BASE << 2)) a -= (BASE << 2); \
1079          if (a >= (BASE << 1)) a -= (BASE << 1); \
1080          if (a >= BASE) a -= BASE; \
1081      } while (0)
1082
1083    UInt sum2;
1084    UInt n;
1085
1086    /* split Adler-32 into component sums */
1087    sum2 = (adler >> 16) & 0xffff;
1088    adler &= 0xffff;
1089
1090    /* in case user likes doing a byte at a time, keep it fast */
1091    if (len == 1) {
1092        adler += buf[0];
1093        if (adler >= BASE)
1094            adler -= BASE;
1095        sum2 += adler;
1096        if (sum2 >= BASE)
1097            sum2 -= BASE;
1098        return adler | (sum2 << 16);
1099    }
1100
1101    /* initial Adler-32 value (deferred check for len == 1 speed) */
1102    if (buf == NULL)
1103        return 1L;
1104
1105    /* in case short lengths are provided, keep it somewhat fast */
1106    if (len < 16) {
1107        while (len--) {
1108            adler += *buf++;
1109            sum2 += adler;
1110        }
1111        if (adler >= BASE)
1112            adler -= BASE;
1113        MOD4(sum2);             /* only added so many BASE's */
1114        return adler | (sum2 << 16);
1115    }
1116
1117    /* do length NMAX blocks -- requires just one modulo operation */
1118    while (len >= NMAX) {
1119        len -= NMAX;
1120        n = NMAX / 16;          /* NMAX is divisible by 16 */
1121        do {
1122            DO16(buf);          /* 16 sums unrolled */
1123            buf += 16;
1124        } while (--n);
1125        MOD(adler);
1126        MOD(sum2);
1127    }
1128
1129    /* do remaining bytes (less than NMAX, still just one modulo) */
1130    if (len) {                  /* avoid modulos if none remaining */
1131        while (len >= 16) {
1132            len -= 16;
1133            DO16(buf);
1134            buf += 16;
1135        }
1136        while (len--) {
1137            adler += *buf++;
1138            sum2 += adler;
1139        }
1140        MOD(adler);
1141        MOD(sum2);
1142    }
1143
1144    /* return recombined sums */
1145    return adler | (sum2 << 16);
1146
1147#  undef MOD4
1148#  undef MOD
1149#  undef DO16
1150#  undef DO8
1151#  undef DO4
1152#  undef DO2
1153#  undef DO1
1154#  undef NMAX
1155#  undef BASE
1156}
1157
1158/*--------------------------------------------------------------------*/
1159/*--- end                                                          ---*/
1160/*--------------------------------------------------------------------*/
1161
1162