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
VG_(isspace)38 Bool VG_(isspace) ( Char c )
39 {
40 return (c == ' ' || c == '\n' || c == '\t' ||
41 c == '\f' || c == '\v' || c == '\r');
42 }
43
VG_(isdigit)44 Bool VG_(isdigit) ( Char c )
45 {
46 return (c >= '0' && c <= '9');
47 }
48
49 /* ---------------------------------------------------------------------
50 Converting strings to numbers
51 ------------------------------------------------------------------ */
52
is_dec_digit(Char c,Long * digit)53 static 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
is_hex_digit(Char c,Long * digit)59 static 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
VG_(strtoll10)67 Long 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
VG_(strtoull10)92 ULong 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
VG_(strtoll16)117 Long 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
VG_(strtoull16)150 ULong 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
VG_(strtod)183 double 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
VG_(tolower)216 Char 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
VG_(strlen)229 SizeT VG_(strlen) ( const Char* str )
230 {
231 SizeT i = 0;
232 while (str[i] != 0) i++;
233 return i;
234 }
235
VG_(strcat)236 Char* 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
VG_(strncat)245 Char* 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
VG_(strpbrk)254 Char* 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
VG_(strcpy)267 Char* 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. */
VG_(strncpy_safely)277 void 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
VG_(strncpy)289 Char* 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
VG_(strcmp)303 Int 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
VG_(strcasecmp)317 Int 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
VG_(strncmp)333 Int 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
VG_(strncasecmp)349 Int 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
VG_(strstr)369 Char* 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
VG_(strcasestr)384 Char* 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
VG_(strchr)399 Char* 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
VG_(strrchr)408 Char* 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) */
418 static Char *olds;
419 Char *
VG_(strtok)420 VG_(strtok) (Char *s, const Char *delim)
421 {
422 return VG_(strtok_r) (s, delim, &olds);
423 }
424
425 Char *
VG_(strtok_r)426 VG_(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
isHex(UChar c)456 static Bool isHex ( UChar c )
457 {
458 return ((c >= '0' && c <= '9') ||
459 (c >= 'a' && c <= 'f') ||
460 (c >= 'A' && c <= 'F'));
461 }
462
fromHex(UChar c)463 static 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
VG_(parse_Addr)476 Bool 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
VG_(strspn)499 SizeT 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
VG_(strcspn)515 SizeT 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
VG_(memcpy)532 void* 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
VG_(memmove)569 void* 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
VG_(memset)587 void* 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
VG_(memcmp)622 Int 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
bm_med3(Char * a,Char * b,Char * c,Int (* cmp)(void *,void *))678 static 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
bm_swapfunc(Char * a,Char * b,SizeT n,Int swaptype)685 static 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
bm_qsort(Char * a,SizeT n,SizeT es,Int (* cmp)(void *,void *))699 static 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. */
VG_(log2)787 Int 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. */
VG_(log2_64)798 Int 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.
VG_(ssort)808 void 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
822 static UInt seed = 0;
823
VG_(random)824 UInt 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