src/util.c

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