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