src/util.c

   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