1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- Entirely standalone libc stuff. m_libcbase.c ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This file is part of Valgrind, a dynamic binary instrumentation 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown framework. 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 10436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Copyright (C) 2000-2013 Julian Seward 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown jseward@acm.org 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is free software; you can redistribute it and/or 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown modify it under the terms of the GNU General Public License as 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown published by the Free Software Foundation; either version 2 of the 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown License, or (at your option) any later version. 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown This program is distributed in the hope that it will be useful, but 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WITHOUT ANY WARRANTY; without even the implied warranty of 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown General Public License for more details. 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown You should have received a copy of the GNU General Public License 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown along with this program; if not, write to the Free Software 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 02111-1307, USA. 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown The GNU General Public License is contained in the file COPYING. 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown*/ 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_basics.h" 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcbase.h" 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 35436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar functions. 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovBool VG_(isspace) ( HChar c ) 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (c == ' ' || c == '\n' || c == '\t' || 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c == '\f' || c == '\v' || c == '\r'); 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovBool VG_(isdigit) ( HChar c ) 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (c >= '0' && c <= '9'); 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Converting strings to numbers 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 53436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstatic Bool is_dec_digit(HChar c, Long* digit) 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; } 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 59436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstatic Bool is_hex_digit(HChar c, Long* digit) 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c >= '0' && c <= '9') { *digit = (Long)(c - '0'); return True; } 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c >= 'A' && c <= 'F') { *digit = (Long)((c - 'A') + 10); return True; } 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c >= 'a' && c <= 'f') { *digit = (Long)((c - 'a') + 10); return True; } 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return False; 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 67436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovLong VG_(strtoll10) ( const HChar* str, HChar** endptr ) 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool neg = False, converted = False; 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Long n = 0, digit = 0; 71436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* str0 = str; 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Skip leading whitespace. 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (VG_(isspace)(*str)) str++; 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Allow a leading '-' or '+'. 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*str == '-') { str++; neg = True; } 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (*str == '+') { str++; } 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (is_dec_digit(*str, &digit)) { 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown converted = True; // Ok, we've actually converted a digit. 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 10*n + digit; 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str++; 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!converted) str = str0; // If nothing converted, endptr points to 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (neg) n = -n; // the start of the string. 88436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (endptr) *endptr = (HChar *)str; // Record first failing character. 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 92436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovULong VG_(strtoull10) ( const HChar* str, HChar** endptr ) 93b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 94b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Bool converted = False; 95b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov ULong n = 0; 96b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Long digit = 0; 97436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* str0 = str; 98b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 99b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // Skip leading whitespace. 100b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (VG_(isspace)(*str)) str++; 101b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 102b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // Allow a leading '+'. 103b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (*str == '+') { str++; } 104b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 105b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (is_dec_digit(*str, &digit)) { 106b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov converted = True; // Ok, we've actually converted a digit. 107b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov n = 10*n + digit; 108b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov str++; 109b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 110b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 111b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (!converted) str = str0; // If nothing converted, endptr points to 112b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // the start of the string. 113436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (endptr) *endptr = (HChar *)str; // Record first failing character. 114b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return n; 115b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 116b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 117436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovLong VG_(strtoll16) ( const HChar* str, HChar** endptr ) 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool neg = False, converted = False; 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Long n = 0, digit = 0; 121436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* str0 = str; 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Skip leading whitespace. 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (VG_(isspace)(*str)) str++; 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Allow a leading '-' or '+'. 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*str == '-') { str++; neg = True; } 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (*str == '+') { str++; } 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Allow leading "0x", but only if there's a hex digit 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // following it. 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*str == '0' 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && (*(str+1) == 'x' || *(str+1) == 'X') 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown && is_hex_digit( *(str+2), &digit )) { 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str += 2; 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (is_hex_digit(*str, &digit)) { 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown converted = True; // Ok, we've actually converted a digit. 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 16*n + digit; 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str++; 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (!converted) str = str0; // If nothing converted, endptr points to 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (neg) n = -n; // the start of the string. 146436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (endptr) *endptr = (HChar *)str; // Record first failing character. 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 150436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovULong VG_(strtoull16) ( const HChar* str, HChar** endptr ) 151b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 152b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Bool converted = False; 153b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov ULong n = 0; 154b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Long digit = 0; 155436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* str0 = str; 156b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 157b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // Skip leading whitespace. 158b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (VG_(isspace)(*str)) str++; 159b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 160b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // Allow a leading '+'. 161b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (*str == '+') { str++; } 162b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 163b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // Allow leading "0x", but only if there's a hex digit 164b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // following it. 165b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (*str == '0' 166b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov && (*(str+1) == 'x' || *(str+1) == 'X') 167b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov && is_hex_digit( *(str+2), &digit )) { 168b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov str += 2; 169b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 170b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 171b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (is_hex_digit(*str, &digit)) { 172b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov converted = True; // Ok, we've actually converted a digit. 173b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov n = 16*n + digit; 174b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov str++; 175b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 176b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 177b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (!converted) str = str0; // If nothing converted, endptr points to 178b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // the start of the string. 179436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (endptr) *endptr = (HChar *)str; // Record first failing character. 180b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return n; 181b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 182b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 183436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovdouble VG_(strtod) ( const HChar* str, HChar** endptr ) 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool neg = False; 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Long digit; 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown double n = 0, frac = 0, x = 0.1; 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Skip leading whitespace. 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (VG_(isspace)(*str)) str++; 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Allow a leading '-' or '+'. 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*str == '-') { str++; neg = True; } 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (*str == '+') { str++; } 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (is_dec_digit(*str, &digit)) { 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 10*n + digit; 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str++; 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*str == '.') { 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str++; 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (is_dec_digit(*str, &digit)) { 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown frac += x*digit; 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown x /= 10; 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown str++; 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n += frac; 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (neg) n = -n; 212436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (endptr) *endptr = (HChar *)str; // Record first failing character. 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 216436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar VG_(tolower) ( HChar c ) 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ( c >= 'A' && c <= 'Z' ) { 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return c - 'A' + 'a'; 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return c; 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown String functions 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 229436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovSizeT VG_(strlen) ( const HChar* str ) 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i = 0; 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (str[i] != 0) i++; 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return i; 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 236436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strcat) ( HChar* dest, const HChar* src ) 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 238436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* dest_orig = dest; 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*dest) dest++; 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*src) *dest++ = *src++; 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *dest = 0; 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest_orig; 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 245436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strncat) ( HChar* dest, const HChar* src, SizeT n ) 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 247436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* dest_orig = dest; 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*dest) dest++; 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*src && n > 0) { *dest++ = *src++; n--; } 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *dest = 0; 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest_orig; 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 254436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strpbrk) ( const HChar* s, const HChar* accpt ) 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 256436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar* a; 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*s) { 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = accpt; 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*a) 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*a++ == *s) 261436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return (HChar *)s; 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s++; 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 267436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strcpy) ( HChar* dest, const HChar* src ) 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 269436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* dest_orig = dest; 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*src) *dest++ = *src++; 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *dest = 0; 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest_orig; 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Copy bytes, not overrunning the end of dest and always ensuring 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown zero termination. */ 277436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid VG_(strncpy_safely) ( HChar* dest, const HChar* src, SizeT ndest ) 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i = 0; 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dest[i] = 0; 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (src[i] == 0) return; 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (i >= ndest-1) return; 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dest[i] = src[i]; 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown i++; 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 289436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strncpy) ( HChar* dest, const HChar* src, SizeT ndest ) 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i = 0; 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (i >= ndest) return dest; /* reached limit */ 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dest[i] = src[i]; 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (src[i++] == 0) { 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* reached NUL; pad rest with zeroes as required */ 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (i < ndest) dest[i++] = 0; 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 303436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovInt VG_(strcmp) ( const HChar* s1, const HChar* s2 ) 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 306436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*(const UChar*)s1 < *(const UChar*)s2) return -1; 307436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*(const UChar*)s1 > *(const UChar*)s2) return 1; 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 309663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng /* *s1 == *s2 */ 310663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (*s1 == 0) return 0; 311663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1++; s2++; 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 316436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovInt VG_(strcasecmp) ( const HChar* s1, const HChar* s2 ) 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar c1 = (UChar)VG_(tolower)(*s1); 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar c2 = (UChar)VG_(tolower)(*s2); 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c1 < c2) return -1; 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c1 > c2) return 1; 323663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 324663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng /* c1 == c2 */ 325663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (c1 == 0) return 0; 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1++; s2++; 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 331436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovInt VG_(strncmp) ( const HChar* s1, const HChar* s2, SizeT nmax ) 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT n = 0; 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n >= nmax) return 0; 336436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*(const UChar*)s1 < *(const UChar*)s2) return -1; 337436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*(const UChar*)s1 > *(const UChar*)s2) return 1; 338663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 339663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng /* *s1 == *s2 */ 340663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (*s1 == 0) return 0; 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1++; s2++; n++; 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 346436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovInt VG_(strncasecmp) ( const HChar* s1, const HChar* s2, SizeT nmax ) 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int n = 0; 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar c1; 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar c2; 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n >= nmax) return 0; 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c1 = (UChar)VG_(tolower)(*s1); 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c2 = (UChar)VG_(tolower)(*s2); 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c1 < c2) return -1; 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (c1 > c2) return 1; 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 358663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng /* c1 == c2 */ 359663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng if (c1 == 0) return 0; 360663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1++; s2++; n++; 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 365436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strstr) ( const HChar* haystack, const HChar* needle ) 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT n; 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (haystack == NULL) 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = VG_(strlen)(needle); 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (haystack[0] == 0) 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(strncmp)(haystack, needle, n) == 0) 375436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return (HChar*)haystack; 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown haystack++; 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 380436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strcasestr) ( const HChar* haystack, const HChar* needle ) 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int n; 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (haystack == NULL) 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = VG_(strlen)(needle); 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (haystack[0] == 0) 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(strncasecmp)(haystack, needle, n) == 0) 390436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return (HChar*)haystack; 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown haystack++; 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 395436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strchr) ( const HChar* s, HChar c ) 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 398436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*s == c) return (HChar *)s; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*s == 0) return NULL; 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s++; 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 404436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar* VG_(strrchr) ( const HChar* s, HChar c ) 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int n = VG_(strlen)(s); 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (--n > 0) { 408436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (s[n] == c) return (HChar *)s + n; 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 413b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* (code copied from glib then updated to valgrind types) */ 414436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstatic HChar *olds; 415436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar * 416436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovVG_(strtok) (HChar *s, const HChar *delim) 417b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 418b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return VG_(strtok_r) (s, delim, &olds); 419b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 420b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 421436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovHChar * 422436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovVG_(strtok_r) (HChar* s, const HChar* delim, HChar** saveptr) 423b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 424436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar *token; 425b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 426b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (s == NULL) 427b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov s = *saveptr; 428b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 429b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov /* Scan leading delimiters. */ 430b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov s += VG_(strspn (s, delim)); 431b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (*s == '\0') 432b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov { 433b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *saveptr = s; 434b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return NULL; 435b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 436b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 437b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov /* Find the end of the token. */ 438b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov token = s; 439b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov s = VG_(strpbrk (token, delim)); 440b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (s == NULL) 441b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov /* This token finishes the string. */ 442b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *saveptr = token + VG_(strlen) (token); 443b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov else 444b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov { 445b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov /* Terminate the token and make OLDS point past it. */ 446b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *s = '\0'; 447b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *saveptr = s + 1; 448b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 449b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return token; 450b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 451b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 452436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstatic Bool isHex ( HChar c ) 453b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 454b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return ((c >= '0' && c <= '9') || 455b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (c >= 'a' && c <= 'f') || 456b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (c >= 'A' && c <= 'F')); 457b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 458b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 459436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstatic UInt fromHex ( HChar c ) 460b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 461b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (c >= '0' && c <= '9') 462b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return (UInt)c - (UInt)'0'; 463b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (c >= 'a' && c <= 'f') 464b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return 10 + (UInt)c - (UInt)'a'; 465b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (c >= 'A' && c <= 'F') 466b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return 10 + (UInt)c - (UInt)'A'; 467b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov /*NOTREACHED*/ 468b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // ??? need to vg_assert(0); 469b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return 0; 470b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 471b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 472436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovBool VG_(parse_Addr) ( const HChar** ppc, Addr* result ) 473b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 474b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Int used, limit = 2 * sizeof(Addr); 475b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (**ppc != '0') 476b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return False; 477b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (*ppc)++; 478b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (**ppc != 'x') 479b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return False; 480b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (*ppc)++; 481b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *result = 0; 482b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov used = 0; 483b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov while (isHex(**ppc)) { 484b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov // ??? need to vg_assert(d < fromHex(**ppc)); 485b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov *result = ((*result) << 4) | fromHex(**ppc); 486b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov (*ppc)++; 487b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov used++; 488b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (used > limit) return False; 489b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 490b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (used == 0) 491b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return False; 492b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return True; 493b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 494b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 495eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy IvanovBool VG_(parse_enum_set) ( const HChar *tokens, 496eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov const HChar *input, 497eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov UInt *enum_set) 498eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov{ 499eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov const SizeT tokens_len = VG_(strlen)(tokens); 500eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (tokens_len > 1000) return False; /* "obviously invalid" */ 501eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar tok_tokens[tokens_len+1]; 502eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar *tokens_saveptr; 503eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar *token; 504eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov UInt token_nr = 0; 505eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov UInt all_set = 0; 506eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 507eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov const SizeT input_len = VG_(strlen)(input); 508eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (input_len > 1000) return False; /* "obviously invalid" */ 509eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar tok_input[input_len+1]; 510eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar *input_saveptr; 511eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov HChar *input_word; 512eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov UInt word_nr = 0; 513eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov UInt known_words = 0; 514eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov Bool seen_all_kw = False; 515eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov Bool seen_none_kw = False; 516eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 517eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov *enum_set = 0; 518eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 519eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov VG_(strcpy) (tok_input, input); 520eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov for (input_word = VG_(strtok_r)(tok_input, ",", &input_saveptr); 521eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov input_word; 522eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov input_word = VG_(strtok_r)(NULL, ",", &input_saveptr)) { 523eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov word_nr++; 524eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (0 == VG_(strcmp)(input_word, "all")) { 525eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov seen_all_kw = True; 526eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov known_words++; 527eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } else if (0 == VG_(strcmp)(input_word, "none")) { 528eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov seen_none_kw = True; 529eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov known_words++; 530eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 531eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 532eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // Scan tokens + compute all_set. Do that even if all or none was 533eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // recognised to have a correct value for all_set when exiting 534eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // of the 'input' loop. 535eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov all_set = 0; 536eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov token_nr = 0; 537eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov VG_(strcpy) (tok_tokens, tokens); 538eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov for (token = VG_(strtok_r)(tok_tokens, ",", &tokens_saveptr); 539eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov token; 540eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov token = VG_(strtok_r)(NULL, ",", &tokens_saveptr)) { 541eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (0 != VG_(strcmp)(token, "-")) { 542eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (0 == VG_(strcmp)(input_word, token)) { 543eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov *enum_set |= 1 << token_nr; 544eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov known_words++; 545eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 546eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov all_set |= 1 << token_nr; 547eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 548eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov token_nr++; 549eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 550eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 551eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 552eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (known_words != word_nr) 553eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov return False; // One or more input_words not recognised. 554eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (seen_all_kw) { 555eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (seen_none_kw || *enum_set) 556eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov return False; // mixing all with either none or a specific value. 557eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov *enum_set = all_set; 558eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } else if (seen_none_kw) { 559eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (seen_all_kw || *enum_set) 560eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov return False; // mixing none with either all or a specific value. 561eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov *enum_set = 0; 562eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } else { 563eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov // seen neither all or none, we must see at least one value 564eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov if (*enum_set == 0) 565eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov return False; 566eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov } 567eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 568eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov return True; 569eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov} 570eb0bae136f4eeaaf29761dddb148b118fb824632Dmitriy Ivanov 571436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovSizeT VG_(strspn) ( const HChar* s, const HChar* accpt ) 572ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 573436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov const HChar *p, *a; 574ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT count = 0; 575ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (p = s; *p != '\0'; ++p) { 576ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (a = accpt; *a != '\0'; ++a) 577ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*p == *a) 578ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 579ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*a == '\0') 580ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 581ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 582ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++count; 583ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 584ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 585ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 586ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 587436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovSizeT VG_(strcspn) ( const HChar* s, const HChar* reject ) 588ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 589ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT count = 0; 590ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*s != '\0') { 591ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(strchr) (reject, *s++) == NULL) 592ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++count; 593ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 594ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 595ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 596ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 597ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 598ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 599ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 600ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 601ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown mem* functions 602ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 603ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 604ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) 605ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 606ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar* s = (const UChar*)src; 607ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar* d = (UChar*)dest; 608ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UInt* sI = (const UInt*)src; 609ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt* dI = (UInt*)dest; 610ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 611ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { 612ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 16) { 613ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[0] = sI[0]; 614ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[1] = sI[1]; 615ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[2] = sI[2]; 616ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[3] = sI[3]; 617ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 16; 618ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI += 4; 619ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sI += 4; 620ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 621ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 622ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 623ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 4) { 624ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[0] = sI[0]; 625ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 4; 626ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI += 1; 627ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sI += 1; 628ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 629ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 630ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 631ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = (const UChar*)sI; 632ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d = (UChar*)dI; 633ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 634ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 635436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* If we're unlucky, the alignment constraints for the fast case 636436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov above won't apply, and we'll have to to it all here. Hence the 637436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov unrolling. */ 638436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (sz >= 4) { 639436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d[0] = s[0]; 640436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d[1] = s[1]; 641436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d[2] = s[2]; 642436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d[3] = s[3]; 643436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d += 4; 644436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov s += 4; 645436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sz -= 4; 646436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 647436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (sz >= 1) { 648436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d[0] = s[0]; 649436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov d += 1; 650436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov s += 1; 651436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sz -= 1; 652436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 653ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 654ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 655ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 656ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 657ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memmove)(void *dest, const void *src, SizeT sz) 658ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 659ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i; 660ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 661ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 662ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (dest < src) { 663ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < sz; i++) { 664436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov ((UChar*)dest)[i] = ((const UChar*)src)[i]; 665ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 666ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 667ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (dest > src) { 668ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < sz; i++) { 669436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov ((UChar*)dest)[sz-i-1] = ((const UChar*)src)[sz-i-1]; 670ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 671ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 672ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 673ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 674ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 675ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memset) ( void *destV, Int c, SizeT sz ) 676ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 677ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int c4; 678436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov HChar* d = (HChar*)destV; 679ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) { 680ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d[0] = c; 681ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d++; 682ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz--; 683ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 684ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 685ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return destV; 686ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 = c & 0xFF; 687ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 |= (c4 << 8); 688ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 |= (c4 << 16); 689ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 16) { 690ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[0] = c4; 691ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[1] = c4; 692ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[2] = c4; 693ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[3] = c4; 694ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d += 16; 695ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 16; 696ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 697ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 4) { 698ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[0] = c4; 699ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d += 4; 700ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 4; 701ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 702ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 1) { 703ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d[0] = c; 704ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d++; 705ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz--; 706ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 707ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return destV; 708ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 709ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 710ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) 711ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 712ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int res; 713ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar *p1 = s1; 714ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar *p2 = s2; 715ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar a0; 716ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar b0; 717ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 718ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (n != 0) { 719ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a0 = p1[0]; 720ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b0 = p2[0]; 721ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p1 += 1; 722ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 += 1; 723ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown res = a0 - b0; 724ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (res != 0) 725ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return res; 726ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n -= 1; 727ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 728ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 729ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 730ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 731ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 732ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Misc useful functions 733ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 734ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 735ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 736ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 737ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// begin Bentley-McIlroy style quicksort 738ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// See "Engineering a Sort Function". Jon L Bentley, M. Douglas 739ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993. 740ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 741ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_MIN(a, b) \ 742ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (a) < (b) ? a : b 743ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 744ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_SWAPINIT(a, es) \ 745ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \ 746ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : es > (SizeT)sizeof(Word) ? 1 \ 747ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : 0 748ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 749ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_EXCH(a, b, t) \ 750ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (t = a, a = b, b = t) 751ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 752ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_SWAP(a, b) \ 753ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swaptype != 0 \ 754ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ? bm_swapfunc(a, b, es, swaptype) \ 755ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t) 756ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 757ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_VECSWAP(a, b, n) \ 758ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 0) bm_swapfunc(a, b, n, swaptype) 759ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 760ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_PVINIT(pv, pm) \ 761ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swaptype != 0) \ 762ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = a, BM_SWAP(pv, pm); \ 763ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else \ 764ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = (Char*)&v, v = *(Word*)pm 765ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 766ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char* bm_med3 ( Char* a, Char* b, Char* c, 767436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Int (*cmp)(const void*, const void*) ) { 768ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return cmp(a, b) < 0 769ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) 770ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); 771ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 772ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 773ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype ) 774ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 775ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swaptype <= 1) { 776ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word t; 777ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; n > 0; a += sizeof(Word), b += sizeof(Word), 778ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n -= sizeof(Word)) 779ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_EXCH(*(Word*)a, *(Word*)b, t); 780ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 781ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char t; 782ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; n > 0; a += 1, b += 1, n -= 1) 783ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_EXCH(*a, *b, t); 784ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 785ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 786ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 787ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm_qsort ( Char* a, SizeT n, SizeT es, 788436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Int (*cmp)(const void*, const void*) ) 789ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 790ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; 791ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r, swaptype; 792ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word t, v; 793ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT s, s1, s2; 794ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tailcall: 795ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAPINIT(a, es); 796ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n < 7) { 797ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (pm = a + es; pm < a + n*es; pm += es) 798ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 799ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAP(pl, pl-es); 800ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 801ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 802ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = a + (n/2)*es; 803ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 7) { 804ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pl = a; 805ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = a + (n-1)*es; 806ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 40) { 807ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = (n/8)*es; 808ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pl = bm_med3(pl, pl+s, pl+2*s, cmp); 809ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = bm_med3(pm-s, pm, pm+s, cmp); 810ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = bm_med3(pn-2*s, pn-s, pn, cmp); 811ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 812ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = bm_med3(pl, pm, pn, cmp); 813ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 814ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_PVINIT(pv, pm); 815ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pa = pb = a; 816ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc = pd = a + (n-1)*es; 817ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (;;) { 818ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (pb <= pc && (r = cmp(pb, pv)) <= 0) { 819ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (r == 0) { BM_SWAP(pa, pb); pa += es; } 820ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pb += es; 821ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 822ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (pc >= pb && (r = cmp(pc, pv)) >= 0) { 823ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (r == 0) { BM_SWAP(pc, pd); pd -= es; } 824ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc -= es; 825ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 826ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pb > pc) break; 827ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAP(pb, pc); 828ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pb += es; 829ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc -= es; 830ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 831ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = a + n*es; 832ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s); 833ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s); 834ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Now recurse. Do the smaller partition first with an explicit 835ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown recursion, then do the larger partition using a tail call. 836ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Except we can't rely on gcc to implement a tail call in any sane 837ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown way, so simply jump back to the start. This guarantees stack 838ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown growth can never exceed O(log N) even in the worst case. */ 839ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1 = pb-pa; 840ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s2 = pd-pc; 841ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 < s2) { 842ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 > es) { 843ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(a, s1/es, es, cmp); 844ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 845ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s2 > es) { 846ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* bm_qsort(pn-s2, s2/es, es, cmp); */ 847ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = pn-s2; n = s2/es; es = es; cmp = cmp; 848ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto tailcall; 849ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 850ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 851ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s2 > es) { 852ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(pn-s2, s2/es, es, cmp); 853ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 854ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 > es) { 855ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* bm_qsort(a, s1/es, es, cmp); */ 856ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = a; n = s1/es; es = es; cmp = cmp; 857ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto tailcall; 858ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 859ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 860ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 861ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 862ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_MIN 863ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_SWAPINIT 864ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_EXCH 865ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_SWAP 866ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_VECSWAP 867ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_PVINIT 868ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 869ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// end Bentley-McIlroy style quicksort 870ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 871ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 872ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 873ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Returns the base-2 logarithm of x. Returns -1 if x is not a power 874ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown of two. */ 875ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(log2) ( UInt x ) 876ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 877ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 878ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Any more than 32 and we overflow anyway... */ 879ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 32; i++) { 880ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((1U << i) == x) return i; 881ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 882ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return -1; 883ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 884ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 885b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* Ditto for 64 bit numbers. */ 886b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovInt VG_(log2_64) ( ULong x ) 887b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 888b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Int i; 889b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov for (i = 0; i < 64; i++) { 890b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if ((1ULL << i) == x) return i; 891b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 892b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return -1; 893b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 894ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 895ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Generic quick sort. 896ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(ssort)( void* base, SizeT nmemb, SizeT size, 897436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Int (*compar)(const void*, const void*) ) 898ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 899ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(base,nmemb,size,compar); 900ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 901ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 902ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 903ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This random number generator is based on the one suggested in Kernighan 904ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// and Ritchie's "The C Programming Language". 905ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 906ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// A pseudo-random number generator returning a random UInt. If pSeed 907ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// is NULL, it uses its own seed, which starts at zero. If pSeed is 908ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// non-NULL, it uses and updates whatever pSeed points at. 909ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 910ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt seed = 0; 911ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 912ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUInt VG_(random)( /*MOD*/UInt* pSeed ) 913ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 914ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pSeed == NULL) 915ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pSeed = &seed; 916ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 917ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *pSeed = (1103515245 * *pSeed + 12345); 918ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return *pSeed; 919ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 920ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 921436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 922436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* The following Adler-32 checksum code is taken from zlib-1.2.3, which 923436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov has the following copyright notice. */ 924436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* 925436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovCopyright notice: 926436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 927436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov (C) 1995-2004 Jean-loup Gailly and Mark Adler 928436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 929436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov This software is provided 'as-is', without any express or implied 930436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov warranty. In no event will the authors be held liable for any damages 931436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov arising from the use of this software. 932436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 933436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Permission is granted to anyone to use this software for any purpose, 934436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov including commercial applications, and to alter it and redistribute it 935436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov freely, subject to the following restrictions: 936436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 937436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1. The origin of this software must not be misrepresented; you must not 938436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov claim that you wrote the original software. If you use this software 939436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov in a product, an acknowledgment in the product documentation would be 940436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov appreciated but is not required. 941436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 2. Altered source versions must be plainly marked as such, and must not be 942436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov misrepresented as being the original software. 943436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 3. This notice may not be removed or altered from any source distribution. 944436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 945436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov Jean-loup Gailly Mark Adler 946436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov jloup@gzip.org madler@alumni.caltech.edu 947436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 948436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovIf you use the zlib library in a product, we would appreciate *not* 949436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovreceiving lengthy legal documents to sign. The sources are provided 950436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovfor free but without warranty of any kind. The library has been 951436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanoventirely written by Jean-loup Gailly and Mark Adler; it does not 952436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovinclude third-party code. 953436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 954436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovIf you redistribute modified sources, we would appreciate that you include 955436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovin the file ChangeLog history information documenting your changes. Please 956436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovread the FAQ for more information on the distribution of modified source 957436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovversions. 958436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov*/ 959436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 960436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* Update a running Adler-32 checksum with the bytes buf[0..len-1] and 961436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return the updated checksum. If buf is NULL, this function returns 962436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov the required initial value for the checksum. An Adler-32 checksum is 963436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov almost as reliable as a CRC32 but can be computed much faster. */ 964436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy IvanovUInt VG_(adler32)( UInt adler, const UChar* buf, UInt len ) 965436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov{ 966436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define BASE 65521UL /* largest prime smaller than 65536 */ 967436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define NMAX 5552 968436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* NMAX is the largest n such that 969436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 970436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 971436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 972436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 973436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 974436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 975436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define DO16(buf) DO8(buf,0); DO8(buf,8); 976436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 977436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* The zlib sources recommend this definition of MOD if the 978436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov processor cannot do integer division in hardware. */ 979436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define MOD(a) \ 980436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov do { \ 981436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 16)) a -= (BASE << 16); \ 982436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 15)) a -= (BASE << 15); \ 983436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 14)) a -= (BASE << 14); \ 984436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 13)) a -= (BASE << 13); \ 985436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 12)) a -= (BASE << 12); \ 986436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 11)) a -= (BASE << 11); \ 987436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 10)) a -= (BASE << 10); \ 988436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 9)) a -= (BASE << 9); \ 989436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 8)) a -= (BASE << 8); \ 990436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 7)) a -= (BASE << 7); \ 991436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 6)) a -= (BASE << 6); \ 992436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 5)) a -= (BASE << 5); \ 993436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 4)) a -= (BASE << 4); \ 994436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 3)) a -= (BASE << 3); \ 995436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 2)) a -= (BASE << 2); \ 996436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 1)) a -= (BASE << 1); \ 997436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= BASE) a -= BASE; \ 998436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } while (0) 999436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# define MOD4(a) \ 1000436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov do { \ 1001436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 4)) a -= (BASE << 4); \ 1002436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 3)) a -= (BASE << 3); \ 1003436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 2)) a -= (BASE << 2); \ 1004436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= (BASE << 1)) a -= (BASE << 1); \ 1005436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (a >= BASE) a -= BASE; \ 1006436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } while (0) 1007436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1008436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov UInt sum2; 1009436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov UInt n; 1010436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1011436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* split Adler-32 into component sums */ 1012436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sum2 = (adler >> 16) & 0xffff; 1013436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler &= 0xffff; 1014436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1015436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* in case user likes doing a byte at a time, keep it fast */ 1016436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (len == 1) { 1017436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler += buf[0]; 1018436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (adler >= BASE) 1019436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler -= BASE; 1020436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sum2 += adler; 1021436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (sum2 >= BASE) 1022436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sum2 -= BASE; 1023436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return adler | (sum2 << 16); 1024436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1025436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1026436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* initial Adler-32 value (deferred check for len == 1 speed) */ 1027436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (buf == NULL) 1028436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return 1L; 1029436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1030436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* in case short lengths are provided, keep it somewhat fast */ 1031436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (len < 16) { 1032436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (len--) { 1033436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler += *buf++; 1034436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sum2 += adler; 1035436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1036436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (adler >= BASE) 1037436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler -= BASE; 1038436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov MOD4(sum2); /* only added so many BASE's */ 1039436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return adler | (sum2 << 16); 1040436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1041436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1042436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* do length NMAX blocks -- requires just one modulo operation */ 1043436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (len >= NMAX) { 1044436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov len -= NMAX; 1045436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov n = NMAX / 16; /* NMAX is divisible by 16 */ 1046436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov do { 1047436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov DO16(buf); /* 16 sums unrolled */ 1048436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov buf += 16; 1049436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } while (--n); 1050436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov MOD(adler); 1051436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov MOD(sum2); 1052436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1053436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1054436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* do remaining bytes (less than NMAX, still just one modulo) */ 1055436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (len) { /* avoid modulos if none remaining */ 1056436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (len >= 16) { 1057436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov len -= 16; 1058436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov DO16(buf); 1059436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov buf += 16; 1060436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1061436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov while (len--) { 1062436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov adler += *buf++; 1063436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov sum2 += adler; 1064436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1065436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov MOD(adler); 1066436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov MOD(sum2); 1067436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 1068436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1069436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* return recombined sums */ 1070436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return adler | (sum2 << 16); 1071436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1072436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef MOD4 1073436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef MOD 1074436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef DO16 1075436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef DO8 1076436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef DO4 1077436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef DO2 1078436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef DO1 1079436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef NMAX 1080436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov# undef BASE 1081436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 1082436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 1083ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 1084ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end ---*/ 1085ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 1086ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 1087