Home | History | Annotate | Download | only in coregrind
      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 (at) 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 
     38 Bool VG_(isspace) ( HChar c )
     39 {
     40    return (c == ' '  || c == '\n' || c == '\t' ||
     41            c == '\f' || c == '\v' || c == '\r');
     42 }
     43 
     44 Bool VG_(isdigit) ( HChar c )
     45 {
     46    return (c >= '0' && c <= '9');
     47 }
     48 
     49 /* ---------------------------------------------------------------------
     50    Converting strings to numbers
     51    ------------------------------------------------------------------ */
     52 
     53 static 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 
     59 static 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 
     67 Long 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 
     92 ULong 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 
    117 Long 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 
    150 ULong 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 
    183 double 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 
    216 HChar 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 
    229 SizeT VG_(strlen) ( const HChar* str )
    230 {
    231    SizeT i = 0;
    232    while (str[i] != 0) i++;
    233    return i;
    234 }
    235 
    236 HChar* 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 
    245 HChar* 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 
    254 HChar* 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 
    267 HChar* 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. */
    277 void 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 
    289 HChar* 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 
    303 Int 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 
    316 Int 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 
    331 Int 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 
    346 Int 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 
    365 HChar* 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 
    380 HChar* 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 
    395 HChar* 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 
    404 HChar* 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) */
    414 static HChar *olds;
    415 HChar *
    416 VG_(strtok) (HChar *s, const HChar *delim)
    417 {
    418    return VG_(strtok_r) (s, delim, &olds);
    419 }
    420 
    421 HChar *
    422 VG_(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 
    452 static Bool isHex ( HChar c )
    453 {
    454   return ((c >= '0' && c <= '9') ||
    455 	  (c >= 'a' && c <= 'f') ||
    456 	  (c >= 'A' && c <= 'F'));
    457 }
    458 
    459 static 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 
    472 Bool 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 
    495 Bool 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 
    571 SizeT 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 
    587 SizeT 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 
    604 void* 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 
    657 void* 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 
    675 void* 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 
    710 Int 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 
    766 static 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 
    773 static 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 
    787 static 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. */
    875 Int 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. */
    886 Int 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.
    896 void 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 
    910 static UInt seed = 0;
    911 
    912 UInt 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 /*
    925 Copyright 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 (at) gzip.org          madler (at) alumni.caltech.edu
    947 
    948 If you use the zlib library in a product, we would appreciate *not*
    949 receiving lengthy legal documents to sign. The sources are provided
    950 for free but without warranty of any kind.  The library has been
    951 entirely written by Jean-loup Gailly and Mark Adler; it does not
    952 include third-party code.
    953 
    954 If you redistribute modified sources, we would appreciate that you include
    955 in the file ChangeLog history information documenting your changes. Please
    956 read the FAQ for more information on the distribution of modified source
    957 versions.
    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. */
    964 UInt 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