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-2011 Julian Seward
11      jseward@acm.org
12
13   This program is free software; you can redistribute it and/or
14   modify it under the terms of the GNU General Public License as
15   published by the Free Software Foundation; either version 2 of the
16   License, or (at your option) any later version.
17
18   This program is distributed in the hope that it will be useful, but
19   WITHOUT ANY WARRANTY; without even the implied warranty of
20   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21   General Public License for more details.
22
23   You should have received a copy of the GNU General Public License
24   along with this program; if not, write to the Free Software
25   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
26   02111-1307, USA.
27
28   The GNU General Public License is contained in the file COPYING.
29*/
30
31#include "pub_core_basics.h"
32#include "pub_core_libcbase.h"
33
34/* ---------------------------------------------------------------------
35   Char functions.
36   ------------------------------------------------------------------ */
37
38Bool VG_(isspace) ( Char c )
39{
40   return (c == ' '  || c == '\n' || c == '\t' ||
41           c == '\f' || c == '\v' || c == '\r');
42}
43
44Bool VG_(isdigit) ( Char c )
45{
46   return (c >= '0' && c <= '9');
47}
48
49/* ---------------------------------------------------------------------
50   Converting strings to numbers
51   ------------------------------------------------------------------ */
52
53static Bool is_dec_digit(Char c, Long* digit)
54{
55   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; }
56   return False;
57}
58
59static Bool is_hex_digit(Char c, Long* digit)
60{
61   if (c >= '0' && c <= '9') { *digit = (Long)(c - '0');        return True; }
62   if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; }
63   if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; }
64   return False;
65}
66
67Long VG_(strtoll10) ( Char* str, Char** endptr )
68{
69   Bool neg = False, converted = False;
70   Long n = 0, digit = 0;
71   Char* str0 = str;
72
73   // Skip leading whitespace.
74   while (VG_(isspace)(*str)) str++;
75
76   // Allow a leading '-' or '+'.
77   if (*str == '-') { str++; neg = True; }
78   else if (*str == '+') { str++; }
79
80   while (is_dec_digit(*str, &digit)) {
81      converted = True;          // Ok, we've actually converted a digit.
82      n = 10*n + digit;
83      str++;
84   }
85
86   if (!converted) str = str0;   // If nothing converted, endptr points to
87   if (neg) n = -n;              //   the start of the string.
88   if (endptr) *endptr = str;    // Record first failing character.
89   return n;
90}
91
92ULong VG_(strtoull10) ( Char* str, Char** endptr )
93{
94   Bool converted = False;
95   ULong n = 0;
96   Long digit = 0;
97   Char* 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 = str;    // Record first failing character.
114   return n;
115}
116
117Long VG_(strtoll16) ( Char* str, Char** endptr )
118{
119   Bool neg = False, converted = False;
120   Long n = 0, digit = 0;
121   Char* 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 = str;    // Record first failing character.
147   return n;
148}
149
150ULong VG_(strtoull16) ( Char* str, Char** endptr )
151{
152   Bool converted = False;
153   ULong n = 0;
154   Long digit = 0;
155   Char* 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 = str;    // Record first failing character.
180   return n;
181}
182
183double VG_(strtod) ( Char* str, Char** 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 = str;    // Record first failing character.
213   return n;
214}
215
216Char VG_(tolower) ( Char 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 Char* str )
230{
231   SizeT i = 0;
232   while (str[i] != 0) i++;
233   return i;
234}
235
236Char* VG_(strcat) ( Char* dest, const Char* src )
237{
238   Char* dest_orig = dest;
239   while (*dest) dest++;
240   while (*src) *dest++ = *src++;
241   *dest = 0;
242   return dest_orig;
243}
244
245Char* VG_(strncat) ( Char* dest, const Char* src, SizeT n )
246{
247   Char* dest_orig = dest;
248   while (*dest) dest++;
249   while (*src && n > 0) { *dest++ = *src++; n--; }
250   *dest = 0;
251   return dest_orig;
252}
253
254Char* VG_(strpbrk) ( const Char* s, const Char* accpt )
255{
256   const Char* a;
257   while (*s) {
258      a = accpt;
259      while (*a)
260         if (*a++ == *s)
261            return (Char *) s;
262      s++;
263   }
264   return NULL;
265}
266
267Char* VG_(strcpy) ( Char* dest, const Char* src )
268{
269   Char* 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) ( Char* dest, const Char* 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
289Char* VG_(strncpy) ( Char* dest, const Char* 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 Char* s1, const Char* s2 )
304{
305   while (True) {
306      if (*s1 == 0 && *s2 == 0) return 0;
307      if (*s1 == 0) return -1;
308      if (*s2 == 0) return 1;
309
310      if (*(UChar*)s1 < *(UChar*)s2) return -1;
311      if (*(UChar*)s1 > *(UChar*)s2) return 1;
312
313      s1++; s2++;
314   }
315}
316
317Int VG_(strcasecmp) ( const Char* s1, const Char* s2 )
318{
319   while (True) {
320      UChar c1 = (UChar)VG_(tolower)(*s1);
321      UChar c2 = (UChar)VG_(tolower)(*s2);
322      if (c1 == 0 && c2 == 0) return 0;
323      if (c1 == 0) return -1;
324      if (c2 == 0) return 1;
325
326      if (c1 < c2) return -1;
327      if (c1 > c2) return 1;
328
329      s1++; s2++;
330   }
331}
332
333Int VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax )
334{
335   SizeT n = 0;
336   while (True) {
337      if (n >= nmax) return 0;
338      if (*s1 == 0 && *s2 == 0) return 0;
339      if (*s1 == 0) return -1;
340      if (*s2 == 0) return 1;
341
342      if (*(UChar*)s1 < *(UChar*)s2) return -1;
343      if (*(UChar*)s1 > *(UChar*)s2) return 1;
344
345      s1++; s2++; n++;
346   }
347}
348
349Int VG_(strncasecmp) ( const Char* s1, const Char* s2, SizeT nmax )
350{
351   Int n = 0;
352   while (True) {
353      UChar c1;
354      UChar c2;
355      if (n >= nmax) return 0;
356      c1 = (UChar)VG_(tolower)(*s1);
357      c2 = (UChar)VG_(tolower)(*s2);
358      if (c1 == 0 && c2 == 0) return 0;
359      if (c1 == 0) return -1;
360      if (c2 == 0) return 1;
361
362      if (c1 < c2) return -1;
363      if (c1 > c2) return 1;
364
365      s1++; s2++; n++;
366   }
367}
368
369Char* VG_(strstr) ( const Char* haystack, Char* needle )
370{
371   SizeT n;
372   if (haystack == NULL)
373      return NULL;
374   n = VG_(strlen)(needle);
375   while (True) {
376      if (haystack[0] == 0)
377         return NULL;
378      if (VG_(strncmp)(haystack, needle, n) == 0)
379         return (Char*)haystack;
380      haystack++;
381   }
382}
383
384Char* VG_(strcasestr) ( const Char* haystack, Char* needle )
385{
386   Int 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_(strncasecmp)(haystack, needle, n) == 0)
394         return (Char*)haystack;
395      haystack++;
396   }
397}
398
399Char* VG_(strchr) ( const Char* s, Char c )
400{
401   while (True) {
402      if (*s == c) return (Char*)s;
403      if (*s == 0) return NULL;
404      s++;
405   }
406}
407
408Char* VG_(strrchr) ( const Char* s, Char c )
409{
410   Int n = VG_(strlen)(s);
411   while (--n > 0) {
412      if (s[n] == c) return (Char*)s + n;
413   }
414   return NULL;
415}
416
417/* (code copied from glib then updated to valgrind types) */
418static Char *olds;
419Char *
420VG_(strtok) (Char *s, const Char *delim)
421{
422   return VG_(strtok_r) (s, delim, &olds);
423}
424
425Char *
426VG_(strtok_r) (Char* s, const Char* delim, Char** saveptr)
427{
428   Char *token;
429
430   if (s == NULL)
431      s = *saveptr;
432
433   /* Scan leading delimiters.  */
434   s += VG_(strspn (s, delim));
435   if (*s == '\0')
436      {
437         *saveptr = s;
438         return NULL;
439      }
440
441   /* Find the end of the token.  */
442   token = s;
443   s = VG_(strpbrk (token, delim));
444   if (s == NULL)
445      /* This token finishes the string.  */
446      *saveptr = token + VG_(strlen) (token);
447   else
448      {
449         /* Terminate the token and make OLDS point past it.  */
450         *s = '\0';
451         *saveptr = s + 1;
452      }
453   return token;
454}
455
456static Bool isHex ( UChar c )
457{
458  return ((c >= '0' && c <= '9') ||
459	  (c >= 'a' && c <= 'f') ||
460	  (c >= 'A' && c <= 'F'));
461}
462
463static UInt fromHex ( UChar c )
464{
465   if (c >= '0' && c <= '9')
466      return (UInt)c - (UInt)'0';
467   if (c >= 'a' && c <= 'f')
468      return 10 +  (UInt)c - (UInt)'a';
469   if (c >= 'A' && c <= 'F')
470      return 10 +  (UInt)c - (UInt)'A';
471   /*NOTREACHED*/
472   // ??? need to vg_assert(0);
473   return 0;
474}
475
476Bool VG_(parse_Addr) ( UChar** ppc, Addr* result )
477{
478   Int used, limit = 2 * sizeof(Addr);
479   if (**ppc != '0')
480      return False;
481   (*ppc)++;
482   if (**ppc != 'x')
483      return False;
484   (*ppc)++;
485   *result = 0;
486   used = 0;
487   while (isHex(**ppc)) {
488      // ??? need to vg_assert(d < fromHex(**ppc));
489      *result = ((*result) << 4) | fromHex(**ppc);
490      (*ppc)++;
491      used++;
492      if (used > limit) return False;
493   }
494   if (used == 0)
495      return False;
496   return True;
497}
498
499SizeT VG_(strspn) ( const Char* s, const Char* accpt )
500{
501   const Char *p, *a;
502   SizeT count = 0;
503   for (p = s; *p != '\0'; ++p) {
504      for (a = accpt; *a != '\0'; ++a)
505         if (*p == *a)
506            break;
507      if (*a == '\0')
508         return count;
509      else
510         ++count;
511   }
512   return count;
513}
514
515SizeT VG_(strcspn) ( const Char* s, const char* reject )
516{
517   SizeT count = 0;
518   while (*s != '\0') {
519      if (VG_(strchr) (reject, *s++) == NULL)
520         ++count;
521      else
522         return count;
523   }
524   return count;
525}
526
527
528/* ---------------------------------------------------------------------
529   mem* functions
530   ------------------------------------------------------------------ */
531
532void* VG_(memcpy) ( void *dest, const void *src, SizeT sz )
533{
534   const UChar* s  = (const UChar*)src;
535         UChar* d  =       (UChar*)dest;
536   const UInt*  sI = (const UInt*)src;
537         UInt*  dI =       (UInt*)dest;
538
539   if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) {
540      while (sz >= 16) {
541         dI[0] = sI[0];
542         dI[1] = sI[1];
543         dI[2] = sI[2];
544         dI[3] = sI[3];
545         sz -= 16;
546         dI += 4;
547         sI += 4;
548      }
549      if (sz == 0)
550         return dest;
551      while (sz >= 4) {
552         dI[0] = sI[0];
553         sz -= 4;
554         dI += 1;
555         sI += 1;
556      }
557      if (sz == 0)
558         return dest;
559      s = (const UChar*)sI;
560      d = (UChar*)dI;
561   }
562
563   while (sz--)
564      *d++ = *s++;
565
566   return dest;
567}
568
569void* VG_(memmove)(void *dest, const void *src, SizeT sz)
570{
571   SizeT i;
572   if (sz == 0)
573      return dest;
574   if (dest < src) {
575      for (i = 0; i < sz; i++) {
576         ((UChar*)dest)[i] = ((UChar*)src)[i];
577      }
578   }
579   else if (dest > src) {
580      for (i = 0; i < sz; i++) {
581         ((UChar*)dest)[sz-i-1] = ((UChar*)src)[sz-i-1];
582      }
583   }
584   return dest;
585}
586
587void* VG_(memset) ( void *destV, Int c, SizeT sz )
588{
589   Int   c4;
590   Char* d = (Char*)destV;
591   while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) {
592      d[0] = c;
593      d++;
594      sz--;
595   }
596   if (sz == 0)
597      return destV;
598   c4 = c & 0xFF;
599   c4 |= (c4 << 8);
600   c4 |= (c4 << 16);
601   while (sz >= 16) {
602      ((Int*)d)[0] = c4;
603      ((Int*)d)[1] = c4;
604      ((Int*)d)[2] = c4;
605      ((Int*)d)[3] = c4;
606      d += 16;
607      sz -= 16;
608   }
609   while (sz >= 4) {
610      ((Int*)d)[0] = c4;
611      d += 4;
612      sz -= 4;
613   }
614   while (sz >= 1) {
615      d[0] = c;
616      d++;
617      sz--;
618   }
619   return destV;
620}
621
622Int VG_(memcmp) ( const void* s1, const void* s2, SizeT n )
623{
624   Int res;
625   const UChar *p1 = s1;
626   const UChar *p2 = s2;
627   UChar a0;
628   UChar b0;
629
630   while (n != 0) {
631      a0 = p1[0];
632      b0 = p2[0];
633      p1 += 1;
634      p2 += 1;
635      res = a0 - b0;
636      if (res != 0)
637         return res;
638      n -= 1;
639   }
640   return 0;
641}
642
643/* ---------------------------------------------------------------------
644   Misc useful functions
645   ------------------------------------------------------------------ */
646
647/////////////////////////////////////////////////////////////
648/////////////////////////////////////////////////////////////
649/// begin Bentley-McIlroy style quicksort
650/// See "Engineering a Sort Function".  Jon L Bentley, M. Douglas
651/// McIlroy.  Software Practice and Experience Vol 23(11), Nov 1993.
652
653#define BM_MIN(a, b)                                     \
654   (a) < (b) ? a : b
655
656#define BM_SWAPINIT(a, es)                               \
657   swaptype =   ((a-(Char*)0) | es) % sizeof(Word)  ? 2  \
658              : es > (SizeT)sizeof(Word) ? 1             \
659              : 0
660
661#define BM_EXCH(a, b, t)                                 \
662   (t = a, a = b, b = t)
663
664#define BM_SWAP(a, b)                                    \
665   swaptype != 0                                         \
666      ? bm_swapfunc(a, b, es, swaptype)                  \
667      : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t)
668
669#define BM_VECSWAP(a, b, n)                              \
670   if (n > 0) bm_swapfunc(a, b, n, swaptype)
671
672#define BM_PVINIT(pv, pm)                                \
673   if (swaptype != 0)                                    \
674      pv = a, BM_SWAP(pv, pm);                           \
675   else                                                  \
676      pv = (Char*)&v, v = *(Word*)pm
677
678static Char* bm_med3 ( Char* a, Char* b, Char* c,
679                       Int (*cmp)(void*,void*) ) {
680   return cmp(a, b) < 0
681          ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a)
682          : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a);
683}
684
685static void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype )
686{
687   if (swaptype <= 1) {
688      Word t;
689      for ( ; n > 0; a += sizeof(Word), b += sizeof(Word),
690                                        n -= sizeof(Word))
691         BM_EXCH(*(Word*)a, *(Word*)b, t);
692   } else {
693      Char t;
694      for ( ; n > 0; a += 1, b += 1, n -= 1)
695         BM_EXCH(*a, *b, t);
696   }
697}
698
699static void bm_qsort ( Char* a, SizeT n, SizeT es,
700                       Int (*cmp)(void*,void*) )
701{
702   Char  *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv;
703   Int   r, swaptype;
704   Word  t, v;
705   SizeT s, s1, s2;
706  tailcall:
707   BM_SWAPINIT(a, es);
708   if (n < 7) {
709      for (pm = a + es; pm < a + n*es; pm += es)
710         for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
711            BM_SWAP(pl, pl-es);
712      return;
713   }
714   pm = a + (n/2)*es;
715   if (n > 7) {
716      pl = a;
717      pn = a + (n-1)*es;
718      if (n > 40) {
719         s = (n/8)*es;
720         pl = bm_med3(pl, pl+s, pl+2*s, cmp);
721         pm = bm_med3(pm-s, pm, pm+s, cmp);
722         pn = bm_med3(pn-2*s, pn-s, pn, cmp);
723      }
724      pm = bm_med3(pl, pm, pn, cmp);
725   }
726   BM_PVINIT(pv, pm);
727   pa = pb = a;
728   pc = pd = a + (n-1)*es;
729   for (;;) {
730      while (pb <= pc && (r = cmp(pb, pv)) <= 0) {
731         if (r == 0) { BM_SWAP(pa, pb); pa += es; }
732         pb += es;
733      }
734      while (pc >= pb && (r = cmp(pc, pv)) >= 0) {
735         if (r == 0) { BM_SWAP(pc, pd); pd -= es; }
736         pc -= es;
737      }
738      if (pb > pc) break;
739      BM_SWAP(pb, pc);
740      pb += es;
741      pc -= es;
742   }
743   pn = a + n*es;
744   s = BM_MIN(pa-a,  pb-pa   ); BM_VECSWAP(a,  pb-s, s);
745   s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s);
746   /* Now recurse.  Do the smaller partition first with an explicit
747      recursion, then do the larger partition using a tail call.
748      Except we can't rely on gcc to implement a tail call in any sane
749      way, so simply jump back to the start.  This guarantees stack
750      growth can never exceed O(log N) even in the worst case. */
751   s1 = pb-pa;
752   s2 = pd-pc;
753   if (s1 < s2) {
754      if (s1 > es) {
755         bm_qsort(a, s1/es, es, cmp);
756      }
757      if (s2 > es) {
758         /* bm_qsort(pn-s2, s2/es, es, cmp); */
759         a = pn-s2; n = s2/es; es = es; cmp = cmp;
760         goto tailcall;
761      }
762   } else {
763      if (s2 > es) {
764         bm_qsort(pn-s2, s2/es, es, cmp);
765      }
766      if (s1 > es) {
767         /* bm_qsort(a, s1/es, es, cmp); */
768         a = a; n = s1/es; es = es; cmp = cmp;
769         goto tailcall;
770      }
771   }
772}
773
774#undef BM_MIN
775#undef BM_SWAPINIT
776#undef BM_EXCH
777#undef BM_SWAP
778#undef BM_VECSWAP
779#undef BM_PVINIT
780
781/// end Bentley-McIlroy style quicksort
782/////////////////////////////////////////////////////////////
783/////////////////////////////////////////////////////////////
784
785/* Returns the base-2 logarithm of x.  Returns -1 if x is not a power
786   of two. */
787Int VG_(log2) ( UInt x )
788{
789   Int i;
790   /* Any more than 32 and we overflow anyway... */
791   for (i = 0; i < 32; i++) {
792      if ((1U << i) == x) return i;
793   }
794   return -1;
795}
796
797/* Ditto for 64 bit numbers. */
798Int VG_(log2_64) ( ULong x )
799{
800   Int i;
801   for (i = 0; i < 64; i++) {
802      if ((1ULL << i) == x) return i;
803   }
804   return -1;
805}
806
807// Generic quick sort.
808void VG_(ssort)( void* base, SizeT nmemb, SizeT size,
809                 Int (*compar)(void*, void*) )
810{
811   bm_qsort(base,nmemb,size,compar);
812}
813
814
815// This random number generator is based on the one suggested in Kernighan
816// and Ritchie's "The C Programming Language".
817
818// A pseudo-random number generator returning a random UInt.  If pSeed
819// is NULL, it uses its own seed, which starts at zero.  If pSeed is
820// non-NULL, it uses and updates whatever pSeed points at.
821
822static UInt seed = 0;
823
824UInt VG_(random)( /*MOD*/UInt* pSeed )
825{
826   if (pSeed == NULL)
827      pSeed = &seed;
828
829   *pSeed = (1103515245 * *pSeed + 12345);
830   return *pSeed;
831}
832
833/*--------------------------------------------------------------------*/
834/*--- end                                                          ---*/
835/*--------------------------------------------------------------------*/
836
837