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