1 /* 2 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are met: 7 * 8 * * Redistributions of source code must retain the above copyright notice, 9 * this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * * Neither the name of Redis nor the names of its contributors may be used 14 * to endorse or promote products derived from this software without 15 * specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30 #include "fmacros.h" 31 #include <stdlib.h> 32 #include <stdio.h> 33 #include <string.h> 34 #include <ctype.h> 35 #include <limits.h> 36 #include <math.h> 37 #include <unistd.h> 38 #include <sys/time.h> 39 #include <float.h> 40 41 #include "util.h" 42 43 /* Glob-style pattern matching. */ 44 int stringmatchlen(const char *pattern, int patternLen, 45 const char *string, int stringLen, int nocase) 46 { 47 while(patternLen) { 48 switch(pattern[0]) { 49 case '*': 50 while (pattern[1] == '*') { 51 pattern++; 52 patternLen--; 53 } 54 if (patternLen == 1) 55 return 1; /* match */ 56 while(stringLen) { 57 if (stringmatchlen(pattern+1, patternLen-1, 58 string, stringLen, nocase)) 59 return 1; /* match */ 60 string++; 61 stringLen--; 62 } 63 return 0; /* no match */ 64 break; 65 case '?': 66 if (stringLen == 0) 67 return 0; /* no match */ 68 string++; 69 stringLen--; 70 break; 71 case '[': 72 { 73 int not, match; 74 75 pattern++; 76 patternLen--; 77 not = pattern[0] == '^'; 78 if (not) { 79 pattern++; 80 patternLen--; 81 } 82 match = 0; 83 while(1) { 84 if (pattern[0] == '\\') { 85 pattern++; 86 patternLen--; 87 if (pattern[0] == string[0]) 88 match = 1; 89 } else if (pattern[0] == ']') { 90 break; 91 } else if (patternLen == 0) { 92 pattern--; 93 patternLen++; 94 break; 95 } else if (pattern[1] == '-' && patternLen >= 3) { 96 int start = pattern[0]; 97 int end = pattern[2]; 98 int c = string[0]; 99 if (start > end) { 100 int t = start; 101 start = end; 102 end = t; 103 } 104 if (nocase) { 105 start = tolower(start); 106 end = tolower(end); 107 c = tolower(c); 108 } 109 pattern += 2; 110 patternLen -= 2; 111 if (c >= start && c <= end) 112 match = 1; 113 } else { 114 if (!nocase) { 115 if (pattern[0] == string[0]) 116 match = 1; 117 } else { 118 if (tolower((int)pattern[0]) == tolower((int)string[0])) 119 match = 1; 120 } 121 } 122 pattern++; 123 patternLen--; 124 } 125 if (not) 126 match = !match; 127 if (!match) 128 return 0; /* no match */ 129 string++; 130 stringLen--; 131 break; 132 } 133 case '\\': 134 if (patternLen >= 2) { 135 pattern++; 136 patternLen--; 137 } 138 /* fall through */ 139 default: 140 if (!nocase) { 141 if (pattern[0] != string[0]) 142 return 0; /* no match */ 143 } else { 144 if (tolower((int)pattern[0]) != tolower((int)string[0])) 145 return 0; /* no match */ 146 } 147 string++; 148 stringLen--; 149 break; 150 } 151 pattern++; 152 patternLen--; 153 if (stringLen == 0) { 154 while(*pattern == '*') { 155 pattern++; 156 patternLen--; 157 } 158 break; 159 } 160 } 161 if (patternLen == 0 && stringLen == 0) 162 return 1; 163 return 0; 164 } 165 166 int stringmatch(const char *pattern, const char *string, int nocase) { 167 return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase); 168 } 169 170 /* Convert a string representing an amount of memory into the number of 171 * bytes, so for instance memtoll("1Gi") will return 1073741824 that is 172 * (1024*1024*1024). 173 * 174 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's 175 * set to 0 */ 176 long long memtoll(const char *p, int *err) { 177 const char *u; 178 char buf[128]; 179 long mul; /* unit multiplier */ 180 long long val; 181 unsigned int digits; 182 183 if (err) *err = 0; 184 /* Search the first non digit character. */ 185 u = p; 186 if (*u == '-') u++; 187 while(*u && isdigit(*u)) u++; 188 if (*u == '\0' || !strcasecmp(u,"b")) { 189 mul = 1; 190 } else if (!strcasecmp(u,"k")) { 191 mul = 1000; 192 } else if (!strcasecmp(u,"kb")) { 193 mul = 1024; 194 } else if (!strcasecmp(u,"m")) { 195 mul = 1000*1000; 196 } else if (!strcasecmp(u,"mb")) { 197 mul = 1024*1024; 198 } else if (!strcasecmp(u,"g")) { 199 mul = 1000L*1000*1000; 200 } else if (!strcasecmp(u,"gb")) { 201 mul = 1024L*1024*1024; 202 } else { 203 if (err) *err = 1; 204 mul = 1; 205 } 206 digits = u-p; 207 if (digits >= sizeof(buf)) { 208 if (err) *err = 1; 209 return LLONG_MAX; 210 } 211 memcpy(buf,p,digits); 212 buf[digits] = '\0'; 213 val = strtoll(buf,NULL,10); 214 return val*mul; 215 } 216 217 /* Convert a long long into a string. Returns the number of 218 * characters needed to represent the number, that can be shorter if passed 219 * buffer length is not enough to store the whole number. */ 220 int ll2string(char *s, size_t len, long long value) { 221 char buf[32], *p; 222 unsigned long long v; 223 size_t l; 224 225 if (len == 0) return 0; 226 v = (value < 0) ? -value : value; 227 p = buf+31; /* point to the last character */ 228 do { 229 *p-- = '0'+(v%10); 230 v /= 10; 231 } while(v); 232 if (value < 0) *p-- = '-'; 233 p++; 234 l = 32-(p-buf); 235 if (l+1 > len) l = len-1; /* Make sure it fits, including the nul term */ 236 memcpy(s,p,l); 237 s[l] = '\0'; 238 return l; 239 } 240 241 /* Convert a string into a long long. Returns 1 if the string could be parsed 242 * into a (non-overflowing) long long, 0 otherwise. The value will be set to 243 * the parsed value when appropriate. */ 244 int string2ll(const char *s, size_t slen, long long *value) { 245 const char *p = s; 246 size_t plen = 0; 247 int negative = 0; 248 unsigned long long v; 249 250 if (plen == slen) 251 return 0; 252 253 /* Special case: first and only digit is 0. */ 254 if (slen == 1 && p[0] == '0') { 255 if (value != NULL) *value = 0; 256 return 1; 257 } 258 259 if (p[0] == '-') { 260 negative = 1; 261 p++; plen++; 262 263 /* Abort on only a negative sign. */ 264 if (plen == slen) 265 return 0; 266 } 267 268 /* First digit should be 1-9, otherwise the string should just be 0. */ 269 if (p[0] >= '1' && p[0] <= '9') { 270 v = p[0]-'0'; 271 p++; plen++; 272 } else if (p[0] == '0' && slen == 1) { 273 *value = 0; 274 return 1; 275 } else { 276 return 0; 277 } 278 279 while (plen < slen && p[0] >= '0' && p[0] <= '9') { 280 if (v > (ULLONG_MAX / 10)) /* Overflow. */ 281 return 0; 282 v *= 10; 283 284 if (v > (ULLONG_MAX - (p[0]-'0'))) /* Overflow. */ 285 return 0; 286 v += p[0]-'0'; 287 288 p++; plen++; 289 } 290 291 /* Return if not all bytes were used. */ 292 if (plen < slen) 293 return 0; 294 295 if (negative) { 296 if (v > ((unsigned long long)(-(LLONG_MIN+1))+1)) /* Overflow. */ 297 return 0; 298 if (value != NULL) *value = -v; 299 } else { 300 if (v > LLONG_MAX) /* Overflow. */ 301 return 0; 302 if (value != NULL) *value = v; 303 } 304 return 1; 305 } 306 307 /* Convert a string into a long. Returns 1 if the string could be parsed into a 308 * (non-overflowing) long, 0 otherwise. The value will be set to the parsed 309 * value when appropriate. */ 310 int string2l(const char *s, size_t slen, long *lval) { 311 long long llval; 312 313 if (!string2ll(s,slen,&llval)) 314 return 0; 315 316 if (llval < LONG_MIN || llval > LONG_MAX) 317 return 0; 318 319 *lval = (long)llval; 320 return 1; 321 } 322 323 /* Convert a double to a string representation. Returns the number of bytes 324 * required. The representation should always be parsable by stdtod(3). */ 325 int d2string(char *buf, size_t len, double value) { 326 if (isnan(value)) { 327 len = snprintf(buf,len,"nan"); 328 } else if (isinf(value)) { 329 if (value < 0) 330 len = snprintf(buf,len,"-inf"); 331 else 332 len = snprintf(buf,len,"inf"); 333 } else if (value == 0) { 334 /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */ 335 if (1.0/value < 0) 336 len = snprintf(buf,len,"-0"); 337 else 338 len = snprintf(buf,len,"0"); 339 } else { 340 #if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL) 341 /* Check if the float is in a safe range to be casted into a 342 * long long. We are assuming that long long is 64 bit here. 343 * Also we are assuming that there are no implementations around where 344 * double has precision < 52 bit. 345 * 346 * Under this assumptions we test if a double is inside an interval 347 * where casting to long long is safe. Then using two castings we 348 * make sure the decimal part is zero. If all this is true we use 349 * integer printing function that is much faster. */ 350 double min = -4503599627370495; /* (2^52)-1 */ 351 double max = 4503599627370496; /* -(2^52) */ 352 if (value > min && value < max && value == ((double)((long long)value))) 353 len = ll2string(buf,len,(long long)value); 354 else 355 #endif 356 len = snprintf(buf,len,"%.17g",value); 357 } 358 359 return len; 360 } 361 362 /* Generate the Redis "Run ID", a SHA1-sized random number that identifies a 363 * given execution of Redis, so that if you are talking with an instance 364 * having run_id == A, and you reconnect and it has run_id == B, you can be 365 * sure that it is either a different instance or it was restarted. */ 366 void getRandomHexChars(char *p, unsigned int len) { 367 FILE *fp = fopen("/dev/urandom","r"); 368 char *charset = "0123456789abcdef"; 369 unsigned int j; 370 371 if (fp == NULL || fread(p,len,1,fp) == 0) { 372 /* If we can't read from /dev/urandom, do some reasonable effort 373 * in order to create some entropy, since this function is used to 374 * generate run_id and cluster instance IDs */ 375 char *x = p; 376 unsigned int l = len; 377 struct timeval tv; 378 pid_t pid = getpid(); 379 380 /* Use time and PID to fill the initial array. */ 381 gettimeofday(&tv,NULL); 382 if (l >= sizeof(tv.tv_usec)) { 383 memcpy(x,&tv.tv_usec,sizeof(tv.tv_usec)); 384 l -= sizeof(tv.tv_usec); 385 x += sizeof(tv.tv_usec); 386 } 387 if (l >= sizeof(tv.tv_sec)) { 388 memcpy(x,&tv.tv_sec,sizeof(tv.tv_sec)); 389 l -= sizeof(tv.tv_sec); 390 x += sizeof(tv.tv_sec); 391 } 392 if (l >= sizeof(pid)) { 393 memcpy(x,&pid,sizeof(pid)); 394 l -= sizeof(pid); 395 x += sizeof(pid); 396 } 397 /* Finally xor it with rand() output, that was already seeded with 398 * time() at startup. */ 399 for (j = 0; j < len; j++) 400 p[j] ^= rand(); 401 } 402 /* Turn it into hex digits taking just 4 bits out of 8 for every byte. */ 403 for (j = 0; j < len; j++) 404 p[j] = charset[p[j] & 0x0F]; 405 fclose(fp); 406 } 407 408 #ifdef UTIL_TEST_MAIN 409 #include <assert.h> 410 411 void test_string2ll(void) { 412 char buf[32]; 413 long long v; 414 415 /* May not start with +. */ 416 strcpy(buf,"+1"); 417 assert(string2ll(buf,strlen(buf),&v) == 0); 418 419 /* Leading space. */ 420 strcpy(buf," 1"); 421 assert(string2ll(buf,strlen(buf),&v) == 0); 422 423 /* Trailing space. */ 424 strcpy(buf,"1 "); 425 assert(string2ll(buf,strlen(buf),&v) == 0); 426 427 /* May not start with 0. */ 428 strcpy(buf,"01"); 429 assert(string2ll(buf,strlen(buf),&v) == 0); 430 431 strcpy(buf,"-1"); 432 assert(string2ll(buf,strlen(buf),&v) == 1); 433 assert(v == -1); 434 435 strcpy(buf,"0"); 436 assert(string2ll(buf,strlen(buf),&v) == 1); 437 assert(v == 0); 438 439 strcpy(buf,"1"); 440 assert(string2ll(buf,strlen(buf),&v) == 1); 441 assert(v == 1); 442 443 strcpy(buf,"99"); 444 assert(string2ll(buf,strlen(buf),&v) == 1); 445 assert(v == 99); 446 447 strcpy(buf,"-99"); 448 assert(string2ll(buf,strlen(buf),&v) == 1); 449 assert(v == -99); 450 451 strcpy(buf,"-9223372036854775808"); 452 assert(string2ll(buf,strlen(buf),&v) == 1); 453 assert(v == LLONG_MIN); 454 455 strcpy(buf,"-9223372036854775809"); /* overflow */ 456 assert(string2ll(buf,strlen(buf),&v) == 0); 457 458 strcpy(buf,"9223372036854775807"); 459 assert(string2ll(buf,strlen(buf),&v) == 1); 460 assert(v == LLONG_MAX); 461 462 strcpy(buf,"9223372036854775808"); /* overflow */ 463 assert(string2ll(buf,strlen(buf),&v) == 0); 464 } 465 466 void test_string2l(void) { 467 char buf[32]; 468 long v; 469 470 /* May not start with +. */ 471 strcpy(buf,"+1"); 472 assert(string2l(buf,strlen(buf),&v) == 0); 473 474 /* May not start with 0. */ 475 strcpy(buf,"01"); 476 assert(string2l(buf,strlen(buf),&v) == 0); 477 478 strcpy(buf,"-1"); 479 assert(string2l(buf,strlen(buf),&v) == 1); 480 assert(v == -1); 481 482 strcpy(buf,"0"); 483 assert(string2l(buf,strlen(buf),&v) == 1); 484 assert(v == 0); 485 486 strcpy(buf,"1"); 487 assert(string2l(buf,strlen(buf),&v) == 1); 488 assert(v == 1); 489 490 strcpy(buf,"99"); 491 assert(string2l(buf,strlen(buf),&v) == 1); 492 assert(v == 99); 493 494 strcpy(buf,"-99"); 495 assert(string2l(buf,strlen(buf),&v) == 1); 496 assert(v == -99); 497 498 #if LONG_MAX != LLONG_MAX 499 strcpy(buf,"-2147483648"); 500 assert(string2l(buf,strlen(buf),&v) == 1); 501 assert(v == LONG_MIN); 502 503 strcpy(buf,"-2147483649"); /* overflow */ 504 assert(string2l(buf,strlen(buf),&v) == 0); 505 506 strcpy(buf,"2147483647"); 507 assert(string2l(buf,strlen(buf),&v) == 1); 508 assert(v == LONG_MAX); 509 510 strcpy(buf,"2147483648"); /* overflow */ 511 assert(string2l(buf,strlen(buf),&v) == 0); 512 #endif 513 } 514 515 int main(int argc, char **argv) { 516 test_string2ll(); 517 test_string2l(); 518 return 0; 519 } 520 #endif 521