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 10663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng Copyright (C) 2000-2012 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/* --------------------------------------------------------------------- 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char functions. 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(isspace) ( Char c ) 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (c == ' ' || c == '\n' || c == '\t' || 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c == '\f' || c == '\v' || c == '\r'); 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool VG_(isdigit) ( Char 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 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Bool is_dec_digit(Char 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 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Bool is_hex_digit(Char 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 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownLong VG_(strtoll10) ( Char* str, Char** endptr ) 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool neg = False, converted = False; 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Long n = 0, digit = 0; 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* 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. 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (endptr) *endptr = str; // Record first failing character. 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 92b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovULong VG_(strtoull10) ( Char* str, Char** endptr ) 93b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 94b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Bool converted = False; 95b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov ULong n = 0; 96b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Long digit = 0; 97b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Char* 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. 113b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (endptr) *endptr = str; // Record first failing character. 114b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return n; 115b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 116b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownLong VG_(strtoll16) ( Char* str, Char** endptr ) 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Bool neg = False, converted = False; 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Long n = 0, digit = 0; 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* 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. 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (endptr) *endptr = str; // Record first failing character. 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 150b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovULong VG_(strtoull16) ( Char* str, Char** endptr ) 151b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 152b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Bool converted = False; 153b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov ULong n = 0; 154b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Long digit = 0; 155b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Char* 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. 179b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if (endptr) *endptr = str; // Record first failing character. 180b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return n; 181b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 182b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browndouble VG_(strtod) ( Char* str, Char** 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; 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (endptr) *endptr = str; // Record first failing character. 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return n; 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar VG_(tolower) ( Char 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 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSizeT VG_(strlen) ( const Char* str ) 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i = 0; 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (str[i] != 0) i++; 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return i; 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strcat) ( Char* dest, const Char* src ) 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* 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 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strncat) ( Char* dest, const Char* src, SizeT n ) 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* 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 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strpbrk) ( const Char* s, const Char* accpt ) 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Char* a; 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*s) { 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = accpt; 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*a) 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*a++ == *s) 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (Char *) s; 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s++; 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strcpy) ( Char* dest, const Char* src ) 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* 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. */ 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(strncpy_safely) ( Char* dest, const Char* 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 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strncpy) ( Char* dest, const Char* 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 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(strcmp) ( const Char* s1, const Char* s2 ) 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UChar*)s1 < *(UChar*)s2) return -1; 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UChar*)s1 > *(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 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(strcasecmp) ( const Char* s1, const Char* 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 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(strncmp) ( const Char* s1, const Char* s2, SizeT nmax ) 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT n = 0; 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n >= nmax) return 0; 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UChar*)s1 < *(UChar*)s2) return -1; 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*(UChar*)s1 > *(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 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(strncasecmp) ( const Char* s1, const Char* 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 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strstr) ( const Char* haystack, Char* 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) 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (Char*)haystack; 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown haystack++; 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strcasestr) ( const Char* haystack, Char* 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) 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return (Char*)haystack; 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown haystack++; 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strchr) ( const Char* s, Char c ) 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (True) { 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*s == c) return (Char*)s; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*s == 0) return NULL; 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s++; 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownChar* VG_(strrchr) ( const Char* s, Char c ) 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int n = VG_(strlen)(s); 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (--n > 0) { 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s[n] == c) return (Char*)s + n; 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return NULL; 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 413b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* (code copied from glib then updated to valgrind types) */ 414b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovstatic Char *olds; 415b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovChar * 416b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovVG_(strtok) (Char *s, const Char *delim) 417b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 418b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return VG_(strtok_r) (s, delim, &olds); 419b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 420b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 421b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovChar * 422b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovVG_(strtok_r) (Char* s, const Char* delim, Char** saveptr) 423b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 424b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Char *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 452b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovstatic Bool isHex ( UChar 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 459b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovstatic UInt fromHex ( UChar 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 472b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovBool VG_(parse_Addr) ( UChar** 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 495ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSizeT VG_(strspn) ( const Char* s, const Char* accpt ) 496ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 497ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Char *p, *a; 498ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT count = 0; 499ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (p = s; *p != '\0'; ++p) { 500ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (a = accpt; *a != '\0'; ++a) 501ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*p == *a) 502ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown break; 503ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (*a == '\0') 504ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 505ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 506ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++count; 507ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 508ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 509ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 510ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 511ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownSizeT VG_(strcspn) ( const Char* s, const char* reject ) 512ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 513ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT count = 0; 514ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (*s != '\0') { 515ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_(strchr) (reject, *s++) == NULL) 516ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ++count; 517ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else 518ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 519ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 520ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return count; 521ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 522ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 523ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 524ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 525ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown mem* functions 526ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 527ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 528ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memcpy) ( void *dest, const void *src, SizeT sz ) 529ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 530ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar* s = (const UChar*)src; 531ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar* d = (UChar*)dest; 532ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UInt* sI = (const UInt*)src; 533ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UInt* dI = (UInt*)dest; 534ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 535ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (VG_IS_4_ALIGNED(dI) && VG_IS_4_ALIGNED(sI)) { 536ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 16) { 537ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[0] = sI[0]; 538ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[1] = sI[1]; 539ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[2] = sI[2]; 540ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[3] = sI[3]; 541ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 16; 542ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI += 4; 543ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sI += 4; 544ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 545ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 546ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 547ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 4) { 548ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI[0] = sI[0]; 549ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 4; 550ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown dI += 1; 551ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sI += 1; 552ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 553ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 554ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 555ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = (const UChar*)sI; 556ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d = (UChar*)dI; 557ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 558ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 559ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz--) 560ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *d++ = *s++; 561ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 562ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 563ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 564ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 565ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memmove)(void *dest, const void *src, SizeT sz) 566ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 567ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT i; 568ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 569ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 570ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (dest < src) { 571ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < sz; i++) { 572ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((UChar*)dest)[i] = ((UChar*)src)[i]; 573ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 574ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 575ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else if (dest > src) { 576ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < sz; i++) { 577ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((UChar*)dest)[sz-i-1] = ((UChar*)src)[sz-i-1]; 578ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 579ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 580ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return dest; 581ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 582ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 583ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid* VG_(memset) ( void *destV, Int c, SizeT sz ) 584ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 585ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int c4; 586ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char* d = (Char*)destV; 587ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ((!VG_IS_4_ALIGNED(d)) && sz >= 1) { 588ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d[0] = c; 589ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d++; 590ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz--; 591ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 592ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (sz == 0) 593ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return destV; 594ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 = c & 0xFF; 595ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 |= (c4 << 8); 596ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown c4 |= (c4 << 16); 597ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 16) { 598ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[0] = c4; 599ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[1] = c4; 600ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[2] = c4; 601ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[3] = c4; 602ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d += 16; 603ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 16; 604ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 605ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 4) { 606ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ((Int*)d)[0] = c4; 607ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d += 4; 608ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz -= 4; 609ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 610ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (sz >= 1) { 611ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d[0] = c; 612ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown d++; 613ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sz--; 614ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 615ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return destV; 616ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 617ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 618ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(memcmp) ( const void* s1, const void* s2, SizeT n ) 619ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 620ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int res; 621ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar *p1 = s1; 622ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const UChar *p2 = s2; 623ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar a0; 624ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown UChar b0; 625ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 626ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (n != 0) { 627ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a0 = p1[0]; 628ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown b0 = p2[0]; 629ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p1 += 1; 630ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown p2 += 1; 631ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown res = a0 - b0; 632ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (res != 0) 633ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return res; 634ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n -= 1; 635ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 636ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 637ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 638ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 639ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* --------------------------------------------------------------------- 640ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Misc useful functions 641ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ------------------------------------------------------------------ */ 642ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 643ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 644ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 645ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// begin Bentley-McIlroy style quicksort 646ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// See "Engineering a Sort Function". Jon L Bentley, M. Douglas 647ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// McIlroy. Software Practice and Experience Vol 23(11), Nov 1993. 648ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 649ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_MIN(a, b) \ 650ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (a) < (b) ? a : b 651ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 652ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_SWAPINIT(a, es) \ 653ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swaptype = ((a-(Char*)0) | es) % sizeof(Word) ? 2 \ 654ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : es > (SizeT)sizeof(Word) ? 1 \ 655ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : 0 656ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 657ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_EXCH(a, b, t) \ 658ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown (t = a, a = b, b = t) 659ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 660ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_SWAP(a, b) \ 661ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown swaptype != 0 \ 662ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ? bm_swapfunc(a, b, es, swaptype) \ 663ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : (void)BM_EXCH(*(Word*)(a), *(Word*)(b), t) 664ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 665ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_VECSWAP(a, b, n) \ 666ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 0) bm_swapfunc(a, b, n, swaptype) 667ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 668ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BM_PVINIT(pv, pm) \ 669ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swaptype != 0) \ 670ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = a, BM_SWAP(pv, pm); \ 671ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown else \ 672ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = (Char*)&v, v = *(Word*)pm 673ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 674ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char* bm_med3 ( Char* a, Char* b, Char* c, 675ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int (*cmp)(void*,void*) ) { 676ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return cmp(a, b) < 0 677ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown ? (cmp(b, c) < 0 ? b : cmp(a, c) < 0 ? c : a) 678ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown : (cmp(b, c) > 0 ? b : cmp(a, c) > 0 ? c : a); 679ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 680ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 681ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm_swapfunc ( Char* a, Char* b, SizeT n, Int swaptype ) 682ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 683ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (swaptype <= 1) { 684ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word t; 685ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; n > 0; a += sizeof(Word), b += sizeof(Word), 686ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n -= sizeof(Word)) 687ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_EXCH(*(Word*)a, *(Word*)b, t); 688ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 689ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char t; 690ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for ( ; n > 0; a += 1, b += 1, n -= 1) 691ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_EXCH(*a, *b, t); 692ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 693ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 694ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 695ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void bm_qsort ( Char* a, SizeT n, SizeT es, 696ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int (*cmp)(void*,void*) ) 697ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 698ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Char *pa, *pb, *pc, *pd, *pl, *pm, *pn, *pv; 699ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r, swaptype; 700ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word t, v; 701ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown SizeT s, s1, s2; 702ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown tailcall: 703ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAPINIT(a, es); 704ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n < 7) { 705ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (pm = a + es; pm < a + n*es; pm += es) 706ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es) 707ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAP(pl, pl-es); 708ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return; 709ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 710ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = a + (n/2)*es; 711ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 7) { 712ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pl = a; 713ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = a + (n-1)*es; 714ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (n > 40) { 715ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = (n/8)*es; 716ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pl = bm_med3(pl, pl+s, pl+2*s, cmp); 717ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = bm_med3(pm-s, pm, pm+s, cmp); 718ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = bm_med3(pn-2*s, pn-s, pn, cmp); 719ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 720ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pm = bm_med3(pl, pm, pn, cmp); 721ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 722ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_PVINIT(pv, pm); 723ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pa = pb = a; 724ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc = pd = a + (n-1)*es; 725ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (;;) { 726ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (pb <= pc && (r = cmp(pb, pv)) <= 0) { 727ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (r == 0) { BM_SWAP(pa, pb); pa += es; } 728ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pb += es; 729ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 730ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while (pc >= pb && (r = cmp(pc, pv)) >= 0) { 731ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (r == 0) { BM_SWAP(pc, pd); pd -= es; } 732ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc -= es; 733ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 734ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pb > pc) break; 735ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown BM_SWAP(pb, pc); 736ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pb += es; 737ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pc -= es; 738ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 739ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pn = a + n*es; 740ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = BM_MIN(pa-a, pb-pa ); BM_VECSWAP(a, pb-s, s); 741ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s = BM_MIN(pd-pc, pn-pd-es); BM_VECSWAP(pb, pn-s, s); 742ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Now recurse. Do the smaller partition first with an explicit 743ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown recursion, then do the larger partition using a tail call. 744ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Except we can't rely on gcc to implement a tail call in any sane 745ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown way, so simply jump back to the start. This guarantees stack 746ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown growth can never exceed O(log N) even in the worst case. */ 747ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s1 = pb-pa; 748ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown s2 = pd-pc; 749ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 < s2) { 750ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 > es) { 751ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(a, s1/es, es, cmp); 752ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 753ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s2 > es) { 754ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* bm_qsort(pn-s2, s2/es, es, cmp); */ 755ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = pn-s2; n = s2/es; es = es; cmp = cmp; 756ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto tailcall; 757ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 758ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } else { 759ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s2 > es) { 760ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(pn-s2, s2/es, es, cmp); 761ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 762ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (s1 > es) { 763ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* bm_qsort(a, s1/es, es, cmp); */ 764ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = a; n = s1/es; es = es; cmp = cmp; 765ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown goto tailcall; 766ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 767ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 768ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 769ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 770ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_MIN 771ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_SWAPINIT 772ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_EXCH 773ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_SWAP 774ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_VECSWAP 775ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef BM_PVINIT 776ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 777ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/// end Bentley-McIlroy style quicksort 778ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 779ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown///////////////////////////////////////////////////////////// 780ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 781ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Returns the base-2 logarithm of x. Returns -1 if x is not a power 782ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown of two. */ 783ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownInt VG_(log2) ( UInt x ) 784ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 785ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i; 786ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* Any more than 32 and we overflow anyway... */ 787ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < 32; i++) { 788ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if ((1U << i) == x) return i; 789ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 790ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return -1; 791ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 792ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 793b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* Ditto for 64 bit numbers. */ 794b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy StepanovInt VG_(log2_64) ( ULong x ) 795b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov{ 796b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Int i; 797b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov for (i = 0; i < 64; i++) { 798b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov if ((1ULL << i) == x) return i; 799b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov } 800b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov return -1; 801b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} 802ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 803ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Generic quick sort. 804ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid VG_(ssort)( void* base, SizeT nmemb, SizeT size, 805ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int (*compar)(void*, void*) ) 806ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 807ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown bm_qsort(base,nmemb,size,compar); 808ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 809ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 810ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 811ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This random number generator is based on the one suggested in Kernighan 812ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// and Ritchie's "The C Programming Language". 813ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 814ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// A pseudo-random number generator returning a random UInt. If pSeed 815ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// is NULL, it uses its own seed, which starts at zero. If pSeed is 816ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// non-NULL, it uses and updates whatever pSeed points at. 817ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 818ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt seed = 0; 819ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 820ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUInt VG_(random)( /*MOD*/UInt* pSeed ) 821ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 822ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (pSeed == NULL) 823ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pSeed = &seed; 824ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 825ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *pSeed = (1103515245 * *pSeed + 12345); 826ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return *pSeed; 827ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 828ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 829ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 830ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end ---*/ 831ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 832ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 833