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-2013 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
269HChar* VG_(strcat) ( HChar* dest, const HChar* src )
270{
271   HChar* dest_orig = dest;
272   while (*dest) dest++;
273   while (*src) *dest++ = *src++;
274   *dest = 0;
275   return dest_orig;
276}
277
278HChar* VG_(strncat) ( HChar* dest, const HChar* src, SizeT n )
279{
280   HChar* dest_orig = dest;
281   while (*dest) dest++;
282   while (*src && n > 0) { *dest++ = *src++; n--; }
283   *dest = 0;
284   return dest_orig;
285}
286
287HChar* VG_(strpbrk) ( const HChar* s, const HChar* accpt )
288{
289   const HChar* a;
290   while (*s) {
291      a = accpt;
292      while (*a)
293         if (*a++ == *s)
294            return CONST_CAST(HChar *,s);
295      s++;
296   }
297   return NULL;
298}
299
300HChar* VG_(strcpy) ( HChar* dest, const HChar* src )
301{
302   HChar* dest_orig = dest;
303   while (*src) *dest++ = *src++;
304   *dest = 0;
305   return dest_orig;
306}
307
308HChar* VG_(strncpy) ( HChar* dest, const HChar* src, SizeT ndest )
309{
310   SizeT i = 0;
311   while (True) {
312      if (i >= ndest) return dest;     /* reached limit */
313      dest[i] = src[i];
314      if (src[i++] == 0) {
315         /* reached NUL;  pad rest with zeroes as required */
316         while (i < ndest) dest[i++] = 0;
317         return dest;
318      }
319   }
320}
321
322Int VG_(strcmp) ( const HChar* s1, const HChar* s2 )
323{
324   while (True) {
325      if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
326      if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
327
328      /* *s1 == *s2 */
329      if (*s1 == 0) return 0;
330
331      s1++; s2++;
332   }
333}
334
335Int VG_(strcasecmp) ( const HChar* s1, const HChar* s2 )
336{
337   while (True) {
338      UChar c1 = (UChar)VG_(tolower)(*s1);
339      UChar c2 = (UChar)VG_(tolower)(*s2);
340      if (c1 < c2) return -1;
341      if (c1 > c2) return 1;
342
343      /* c1 == c2 */
344      if (c1 == 0) return 0;
345
346      s1++; s2++;
347   }
348}
349
350Int VG_(strncmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
351{
352   SizeT n = 0;
353   while (True) {
354      if (n >= nmax) return 0;
355      if (*(const UChar*)s1 < *(const UChar*)s2) return -1;
356      if (*(const UChar*)s1 > *(const UChar*)s2) return 1;
357
358      /* *s1 == *s2 */
359      if (*s1 == 0) return 0;
360
361      s1++; s2++; n++;
362   }
363}
364
365Int VG_(strncasecmp) ( const HChar* s1, const HChar* s2, SizeT nmax )
366{
367   Int n = 0;
368   while (True) {
369      UChar c1;
370      UChar c2;
371      if (n >= nmax) return 0;
372      c1 = (UChar)VG_(tolower)(*s1);
373      c2 = (UChar)VG_(tolower)(*s2);
374      if (c1 < c2) return -1;
375      if (c1 > c2) return 1;
376
377      /* c1 == c2 */
378      if (c1 == 0) return 0;
379
380      s1++; s2++; n++;
381   }
382}
383
384HChar* VG_(strstr) ( const HChar* haystack, const HChar* needle )
385{
386   SizeT n;
387   if (haystack == NULL)
388      return NULL;
389   n = VG_(strlen)(needle);
390   while (True) {
391      if (haystack[0] == 0)
392         return NULL;
393      if (VG_(strncmp)(haystack, needle, n) == 0)
394         return CONST_CAST(HChar *,haystack);
395      haystack++;
396   }
397}
398
399HChar* VG_(strcasestr) ( const HChar* haystack, const HChar* needle )
400{
401   Int n;
402   if (haystack == NULL)
403      return NULL;
404   n = VG_(strlen)(needle);
405   while (True) {
406      if (haystack[0] == 0)
407         return NULL;
408      if (VG_(strncasecmp)(haystack, needle, n) == 0)
409         return CONST_CAST(HChar *,haystack);
410      haystack++;
411   }
412}
413
414HChar* VG_(strchr) ( const HChar* s, HChar c )
415{
416   while (True) {
417      if (*s == c) return CONST_CAST(HChar *,s);
418      if (*s == 0) return NULL;
419      s++;
420   }
421}
422
423HChar* VG_(strrchr) ( const HChar* s, HChar c )
424{
425   Int n = VG_(strlen)(s);
426   while (--n > 0) {
427      if (s[n] == c) return CONST_CAST(HChar *,s) + n;
428   }
429   return NULL;
430}
431
432/* (code copied from glib then updated to valgrind types) */
433static HChar *olds;
434HChar *
435VG_(strtok) (HChar *s, const HChar *delim)
436{
437   return VG_(strtok_r) (s, delim, &olds);
438}
439
440HChar *
441VG_(strtok_r) (HChar* s, const HChar* delim, HChar** saveptr)
442{
443   HChar *token;
444
445   if (s == NULL)
446      s = *saveptr;
447
448   /* Scan leading delimiters.  */
449   s += VG_(strspn (s, delim));
450   if (*s == '\0')
451      {
452         *saveptr = s;
453         return NULL;
454      }
455
456   /* Find the end of the token.  */
457   token = s;
458   s = VG_(strpbrk (token, delim));
459   if (s == NULL)
460      /* This token finishes the string.  */
461      *saveptr = token + VG_(strlen) (token);
462   else
463      {
464         /* Terminate the token and make OLDS point past it.  */
465         *s = '\0';
466         *saveptr = s + 1;
467      }
468   return token;
469}
470
471static Bool isHex ( HChar c )
472{
473  return ((c >= '0' && c <= '9') ||
474	  (c >= 'a' && c <= 'f') ||
475	  (c >= 'A' && c <= 'F'));
476}
477
478static UInt fromHex ( HChar c )
479{
480   if (c >= '0' && c <= '9')
481      return (UInt)c - (UInt)'0';
482   if (c >= 'a' && c <= 'f')
483      return 10 +  (UInt)c - (UInt)'a';
484   if (c >= 'A' && c <= 'F')
485      return 10 +  (UInt)c - (UInt)'A';
486   /*NOTREACHED*/
487   // ??? need to vg_assert(0);
488   return 0;
489}
490
491Bool VG_(parse_Addr) ( const HChar** ppc, Addr* result )
492{
493   Int used, limit = 2 * sizeof(Addr);
494   if (**ppc != '0')
495      return False;
496   (*ppc)++;
497   if (**ppc != 'x')
498      return False;
499   (*ppc)++;
500   *result = 0;
501   used = 0;
502   while (isHex(**ppc)) {
503      // ??? need to vg_assert(d < fromHex(**ppc));
504      *result = ((*result) << 4) | fromHex(**ppc);
505      (*ppc)++;
506      used++;
507      if (used > limit) return False;
508   }
509   if (used == 0)
510      return False;
511   return True;
512}
513
514Bool VG_(parse_enum_set) ( const HChar *tokens,
515                           Bool  allow_all,
516                           const HChar *input,
517                           UInt *enum_set)
518{
519   const SizeT tokens_len = VG_(strlen)(tokens);
520   if (tokens_len > 1000) return False; /* "obviously invalid" */
521   HChar  tok_tokens[tokens_len+1];
522   HChar *tokens_saveptr;
523   HChar *token;
524   UInt token_nr = 0;
525   UInt all_set = 0;
526
527   const SizeT input_len = VG_(strlen)(input);
528   if (input_len > 1000) return False; /* "obviously invalid" */
529   HChar  tok_input[input_len+1];
530   HChar *input_saveptr;
531   HChar *input_word;
532   UInt word_nr = 0;
533   UInt known_words = 0;
534   Bool seen_all_kw = False;
535   Bool seen_none_kw = False;
536
537   *enum_set = 0;
538
539   VG_(strcpy) (tok_input, input);
540   for (input_word = VG_(strtok_r)(tok_input, ",", &input_saveptr);
541        input_word;
542        input_word = VG_(strtok_r)(NULL, ",", &input_saveptr)) {
543      word_nr++;
544      if (allow_all && 0 == VG_(strcmp)(input_word, "all")) {
545         seen_all_kw = True;
546         known_words++;
547      } else if (0 == VG_(strcmp)(input_word, "none")) {
548         seen_none_kw = True;
549         known_words++;
550      }
551
552      // Scan tokens + compute all_set. Do that even if all or none was
553      // recognised to have a correct value for all_set when exiting
554      // of the 'input' loop.
555      all_set = 0;
556      token_nr = 0;
557      VG_(strcpy) (tok_tokens, tokens);
558      for (token = VG_(strtok_r)(tok_tokens, ",", &tokens_saveptr);
559           token;
560           token = VG_(strtok_r)(NULL, ",", &tokens_saveptr)) {
561         if (0 != VG_(strcmp)(token, "-")) {
562            if (0 == VG_(strcmp)(input_word, token)) {
563               *enum_set |= 1 << token_nr;
564               known_words++;
565            }
566            all_set |= 1 << token_nr;
567         }
568         token_nr++;
569      }
570   }
571
572   if (known_words != word_nr)
573      return False; // One or more input_words not recognised.
574   if (seen_all_kw) {
575      if (seen_none_kw || *enum_set)
576         return False; // mixing all with either none or a specific value.
577      *enum_set = all_set;
578   } else if (seen_none_kw) {
579      if (seen_all_kw || *enum_set)
580         return False; // mixing none with either all or a specific value.
581      *enum_set = 0;
582   } else {
583      // seen neither all or none, we must see at least one value
584      if (*enum_set == 0)
585         return False;
586   }
587
588   return True;
589}
590
591SizeT VG_(strspn) ( const HChar* s, const HChar* accpt )
592{
593   const HChar *p, *a;
594   SizeT count = 0;
595   for (p = s; *p != '\0'; ++p) {
596      for (a = accpt; *a != '\0'; ++a)
597         if (*p == *a)
598            break;
599      if (*a == '\0')
600         return count;
601      else
602         ++count;
603   }
604   return count;
605}
606
607SizeT VG_(strcspn) ( const HChar* s, const HChar* reject )
608{
609   SizeT count = 0;
610   while (*s != '\0') {
611      if (VG_(strchr) (reject, *s++) == NULL)
612         ++count;
613      else
614         return count;
615   }
616   return count;
617}
618
619
620/* ---------------------------------------------------------------------
621   mem* functions
622   ------------------------------------------------------------------ */
623
624void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
625{
626   const UChar* s  = (const UChar*)src;
627         UChar* d  =       (UChar*)dest;
628   const UInt*  sI = (const UInt*)src;
629         UInt*  dI =       (UInt*)dest;
630
631   if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
632      while (sz >= 16) {
633         dI[0] = sI[0];
634         dI[1] = sI[1];
635         dI[2] = sI[2];
636         dI[3] = sI[3];
637         sz -= 16;
638         dI += 4;
639         sI += 4;
640      }
641      if (sz == 0)
642         return dest;
643      while (sz >= 4) {
644         dI[0] = sI[0];
645         sz -= 4;
646         dI += 1;
647         sI += 1;
648      }
649      if (sz == 0)
650         return dest;
651      s = (const UChar*)sI;
652      d = (UChar*)dI;
653   }
654
655   /* If we're unlucky, the alignment constraints for the fast case
656      above won't apply, and we'll have to to it all here.  Hence the
657      unrolling. */
658   while (sz >= 4) {
659      d[0] = s[0];
660      d[1] = s[1];
661      d[2] = s[2];
662      d[3] = s[3];
663      d += 4;
664      s += 4;
665      sz -= 4;
666   }
667   while (sz >= 1) {
668      d[0] = s[0];
669      d += 1;
670      s += 1;
671      sz -= 1;
672   }
673
674   return dest;
675}
676
677void* VG_(memmove)(void *dest, const void *src, SizeT sz)
678{
679   SizeT i;
680   if (sz == 0)
681      return dest;
682   if (dest < src) {
683      for (i = 0; i < sz; i++) {
684         ((UChar*)dest)[i] = ((const UChar*)src)[i];
685      }
686   }
687   else if (dest > src) {
688      for (i = 0; i < sz; i++) {
689         ((UChar*)dest)[sz-i-1] = ((const UChar*)src)[sz-i-1];
690      }
691   }
692   return dest;
693}
694
695void* VG_(memset) ( void *destV, Int c, SizeT sz )
696{
697   UInt   c4;
698   UChar* d = destV;
699   UChar uc = c;
700
701   while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) {
702      d[0] = uc;
703      d++;
704      sz--;
705   }
706   if (sz == 0)
707      return destV;
708   c4 = uc;
709   c4 |= (c4 << 8);
710   c4 |= (c4 << 16);
711   while (sz >= 16) {
712      ((UInt*)d)[0] = c4;
713      ((UInt*)d)[1] = c4;
714      ((UInt*)d)[2] = c4;
715      ((UInt*)d)[3] = c4;
716      d += 16;
717      sz -= 16;
718   }
719   while (sz >= 4) {
720      ((UInt*)d)[0] = c4;
721      d += 4;
722      sz -= 4;
723   }
724   while (sz >= 1) {
725      d[0] = c;
726      d++;
727      sz--;
728   }
729   return destV;
730}
731
732Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
733{
734   Int res;
735   const UChar *p1 = s1;
736   const UChar *p2 = s2;
737   UChar a0;
738   UChar b0;
739
740   while (n != 0) {
741      a0 = p1[0];
742      b0 = p2[0];
743      p1 += 1;
744      p2 += 1;
745      res = a0 - b0;
746      if (res != 0)
747         return res;
748      n -= 1;
749   }
750   return 0;
751}
752
753/* ---------------------------------------------------------------------
754   Misc useful functions
755   ------------------------------------------------------------------ */
756
757/////////////////////////////////////////////////////////////
758/////////////////////////////////////////////////////////////
759/// begin Bentley-McIlroy style quicksort
760/// See "Engineering a Sort Function".  Jon L Bentley, M. Douglas
761/// McIlroy.  Software Practice and Experience Vol 23(11), Nov 1993.
762
763#define BM_MIN(a, b)                                     \
764   (a) < (b) ? a : b
765
766#define BM_SWAPINIT(a, es)                               \
767   swaptype =   ((a-(Char*)0) | es) % sizeof(Word)  ? 2  \
768              : es > (SizeT)sizeof(Word) ? 1             \
769              : 0
770
771#define BM_EXCH(a, b, t)                                 \
772   (t = a, a = b, b = t)
773
774#define BM_SWAP(a, b)                                    \
775   swaptype != 0                                         \
776      ? bm_swapfunc(a, b, es, swaptype)                  \
777      : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t)
778
779#define BM_VECSWAP(a, b, n)                              \
780   if (n > 0) bm_swapfunc(a, b, n, swaptype)
781
782#define BM_PVINIT(pv, pm)                                \
783   if (swaptype != 0)                                    \
784      pv = a, BM_SWAP(pv, pm);                           \
785   else                                                  \
786      pv = (Char*)&v, v = *(Word*)pm
787
788static Char* bm_med3 ( Char* a, Char* b, Char* c,
789                       Int (*cmp)(const void*, const void*) ) {
790   return cmp(a, b) < 0
791          ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
792          : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
793}
794
795static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
796{
797   if (swaptype <= 1) {
798      Word t;
799      for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
800                                        n -= sizeof(Word))
801         BM_EXCH(*(Word*)a, *(Word*)b, t);
802   } else {
803      Char t;
804      for ( ; n > 0; a += 1, b += 1, n -= 1)
805         BM_EXCH(*a, *b, t);
806   }
807}
808
809static void bm_qsort ( Char* a, SizeT n, SizeT es,
810                       Int (*cmp)(const void*, const void*) )
811{
812   Char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
813   Int   r, swaptype;
814   Word  t, v;
815   SizeT s, s1, s2;
816  tailcall:
817   BM_SWAPINIT(a, es);
818   if (n < 7) {
819      for (pm = a + es; pm < a + n*es; pm += es)
820         for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
821            BM_SWAP(pl, pl-es);
822      return;
823   }
824   pm = a + (n/2)*es;
825   if (n > 7) {
826      pl = a;
827      pn = a + (n-1)*es;
828      if (n > 40) {
829         s = (n/8)*es;
830         pl = bm_med3(pl, pl+s, pl+2*s, cmp);
831         pm = bm_med3(pm-s, pm, pm+s, cmp);
832         pn = bm_med3(pn-2*s, pn-s, pn, cmp);
833      }
834      pm = bm_med3(pl, pm, pn, cmp);
835   }
836   BM_PVINIT(pv, pm);
837   pa = pb = a;
838   pc = pd = a + (n-1)*es;
839   for (;;) {
840      while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
841         if (r == 0) { BM_SWAP(pa, pb); pa += es; }
842         pb += es;
843      }
844      while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
845         if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
846         pc -= es;
847      }
848      if (pb > pc) break;
849      BM_SWAP(pb, pc);
850      pb += es;
851      pc -= es;
852   }
853   pn = a + n*es;
854   s = BM_MIN(pa-a,  pb-pa   ); BM_VECSWAP(a,  pb-s, s);
855   s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
856   /* Now recurse.  Do the smaller partition first with an explicit
857      recursion, then do the larger partition using a tail call.
858      Except we can't rely on gcc to implement a tail call in any sane
859      way, so simply jump back to the start.  This guarantees stack
860      growth can never exceed O(log N) even in the worst case. */
861   s1 = pb-pa;
862   s2 = pd-pc;
863   if (s1 < s2) {
864      if (s1 > es) {
865         bm_qsort(a, s1/es, es, cmp);
866      }
867      if (s2 > es) {
868         /* bm_qsort(pn-s2, s2/es, es, cmp); */
869         a = pn-s2; n = s2/es; es = es; cmp = cmp;
870         goto tailcall;
871      }
872   } else {
873      if (s2 > es) {
874         bm_qsort(pn-s2, s2/es, es, cmp);
875      }
876      if (s1 > es) {
877         /* bm_qsort(a, s1/es, es, cmp); */
878         a = a; n = s1/es; es = es; cmp = cmp;
879         goto tailcall;
880      }
881   }
882}
883
884#undef BM_MIN
885#undef BM_SWAPINIT
886#undef BM_EXCH
887#undef BM_SWAP
888#undef BM_VECSWAP
889#undef BM_PVINIT
890
891/// end Bentley-McIlroy style quicksort
892/////////////////////////////////////////////////////////////
893/////////////////////////////////////////////////////////////
894
895/* Returns the base-2 logarithm of x.  Returns -1 if x is not a power
896   of two. */
897Int VG_(log2) ( UInt x )
898{
899   Int i;
900   /* Any more than 32 and we overflow anyway... */
901   for (i = 0; i < 32; i++) {
902      if ((1U << i) == x) return i;
903   }
904   return -1;
905}
906
907/* Ditto for 64 bit numbers. */
908Int VG_(log2_64) ( ULong x )
909{
910   Int i;
911   for (i = 0; i < 64; i++) {
912      if ((1ULL << i) == x) return i;
913   }
914   return -1;
915}
916
917// Generic quick sort.
918void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
919                 Int (*compar)(const void*, const void*) )
920{
921   bm_qsort(base,nmemb,size,compar);
922}
923
924
925// This random number generator is based on the one suggested in Kernighan
926// and Ritchie's "The C Programming Language".
927
928// A pseudo-random number generator returning a random UInt.  If pSeed
929// is NULL, it uses its own seed, which starts at zero.  If pSeed is
930// non-NULL, it uses and updates whatever pSeed points at.
931
932UInt VG_(random)( /*MOD*/UInt* pSeed )
933{
934   static UInt seed = 0;
935
936   if (pSeed == NULL)
937      pSeed = &seed;
938
939   *pSeed = (1103515245 * *pSeed + 12345);
940   return *pSeed;
941}
942
943
944/* The following Adler-32 checksum code is taken from zlib-1.2.3, which
945   has the following copyright notice. */
946/*
947Copyright notice:
948
949 (C) 1995-2004 Jean-loup Gailly and Mark Adler
950
951  This software is provided 'as-is', without any express or implied
952  warranty.  In no event will the authors be held liable for any damages
953  arising from the use of this software.
954
955  Permission is granted to anyone to use this software for any purpose,
956  including commercial applications, and to alter it and redistribute it
957  freely, subject to the following restrictions:
958
959  1. The origin of this software must not be misrepresented; you must not
960     claim that you wrote the original software. If you use this software
961     in a product, an acknowledgment in the product documentation would be
962     appreciated but is not required.
963  2. Altered source versions must be plainly marked as such, and must not be
964     misrepresented as being the original software.
965  3. This notice may not be removed or altered from any source distribution.
966
967  Jean-loup Gailly        Mark Adler
968  jloup@gzip.org          madler@alumni.caltech.edu
969
970If you use the zlib library in a product, we would appreciate *not*
971receiving lengthy legal documents to sign. The sources are provided
972for free but without warranty of any kind.  The library has been
973entirely written by Jean-loup Gailly and Mark Adler; it does not
974include third-party code.
975
976If you redistribute modified sources, we would appreciate that you include
977in the file ChangeLog history information documenting your changes. Please
978read the FAQ for more information on the distribution of modified source
979versions.
980*/
981
982/* Update a running Adler-32 checksum with the bytes buf[0..len-1] and
983   return the updated checksum. If buf is NULL, this function returns
984   the required initial value for the checksum. An Adler-32 checksum is
985   almost as reliable as a CRC32 but can be computed much faster. */
986UInt VG_(adler32)( UInt adler, const UChar* buf, UInt len )
987{
988#  define BASE 65521UL    /* largest prime smaller than 65536 */
989#  define NMAX 5552
990   /* NMAX is the largest n such that
991      255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
992
993#  define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
994#  define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
995#  define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
996#  define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
997#  define DO16(buf)   DO8(buf,0); DO8(buf,8);
998
999   /* The zlib sources recommend this definition of MOD if the
1000      processor cannot do integer division in hardware. */
1001#  define MOD(a) \
1002      do { \
1003          if (a >= (BASE << 16)) a -= (BASE << 16); \
1004          if (a >= (BASE << 15)) a -= (BASE << 15); \
1005          if (a >= (BASE << 14)) a -= (BASE << 14); \
1006          if (a >= (BASE << 13)) a -= (BASE << 13); \
1007          if (a >= (BASE << 12)) a -= (BASE << 12); \
1008          if (a >= (BASE << 11)) a -= (BASE << 11); \
1009          if (a >= (BASE << 10)) a -= (BASE << 10); \
1010          if (a >= (BASE << 9)) a -= (BASE << 9); \
1011          if (a >= (BASE << 8)) a -= (BASE << 8); \
1012          if (a >= (BASE << 7)) a -= (BASE << 7); \
1013          if (a >= (BASE << 6)) a -= (BASE << 6); \
1014          if (a >= (BASE << 5)) a -= (BASE << 5); \
1015          if (a >= (BASE << 4)) a -= (BASE << 4); \
1016          if (a >= (BASE << 3)) a -= (BASE << 3); \
1017          if (a >= (BASE << 2)) a -= (BASE << 2); \
1018          if (a >= (BASE << 1)) a -= (BASE << 1); \
1019          if (a >= BASE) a -= BASE; \
1020      } while (0)
1021#  define MOD4(a) \
1022      do { \
1023          if (a >= (BASE << 4)) a -= (BASE << 4); \
1024          if (a >= (BASE << 3)) a -= (BASE << 3); \
1025          if (a >= (BASE << 2)) a -= (BASE << 2); \
1026          if (a >= (BASE << 1)) a -= (BASE << 1); \
1027          if (a >= BASE) a -= BASE; \
1028      } while (0)
1029
1030    UInt sum2;
1031    UInt n;
1032
1033    /* split Adler-32 into component sums */
1034    sum2 = (adler >> 16) & 0xffff;
1035    adler &= 0xffff;
1036
1037    /* in case user likes doing a byte at a time, keep it fast */
1038    if (len == 1) {
1039        adler += buf[0];
1040        if (adler >= BASE)
1041            adler -= BASE;
1042        sum2 += adler;
1043        if (sum2 >= BASE)
1044            sum2 -= BASE;
1045        return adler | (sum2 << 16);
1046    }
1047
1048    /* initial Adler-32 value (deferred check for len == 1 speed) */
1049    if (buf == NULL)
1050        return 1L;
1051
1052    /* in case short lengths are provided, keep it somewhat fast */
1053    if (len < 16) {
1054        while (len--) {
1055            adler += *buf++;
1056            sum2 += adler;
1057        }
1058        if (adler >= BASE)
1059            adler -= BASE;
1060        MOD4(sum2);             /* only added so many BASE's */
1061        return adler | (sum2 << 16);
1062    }
1063
1064    /* do length NMAX blocks -- requires just one modulo operation */
1065    while (len >= NMAX) {
1066        len -= NMAX;
1067        n = NMAX / 16;          /* NMAX is divisible by 16 */
1068        do {
1069            DO16(buf);          /* 16 sums unrolled */
1070            buf += 16;
1071        } while (--n);
1072        MOD(adler);
1073        MOD(sum2);
1074    }
1075
1076    /* do remaining bytes (less than NMAX, still just one modulo) */
1077    if (len) {                  /* avoid modulos if none remaining */
1078        while (len >= 16) {
1079            len -= 16;
1080            DO16(buf);
1081            buf += 16;
1082        }
1083        while (len--) {
1084            adler += *buf++;
1085            sum2 += adler;
1086        }
1087        MOD(adler);
1088        MOD(sum2);
1089    }
1090
1091    /* return recombined sums */
1092    return adler | (sum2 << 16);
1093
1094#  undef MOD4
1095#  undef MOD
1096#  undef DO16
1097#  undef DO8
1098#  undef DO4
1099#  undef DO2
1100#  undef DO1
1101#  undef NMAX
1102#  undef BASE
1103}
1104
1105/*--------------------------------------------------------------------*/
1106/*--- end                                                          ---*/
1107/*--------------------------------------------------------------------*/
1108
1109