src/util.c

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