util.c

/*
 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "fmacros.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <unistd.h>
#include <sys/time.h>
#include <float.h>
#include <stdint.h>
#include <errno.h>

#include "util.h"

/* Glob-style pattern matching. */
int stringmatchlen(const char* pattern, int patternLen, const char* string, int stringLen, int nocase)
{
    while (patternLen) {
        switch (pattern[0]) {
        case '*':
            while (pattern[1] == '*') {
                pattern++;
                patternLen--;
            }
            if (patternLen == 1)
                return 1; /* match */
            while (stringLen) {
                if (stringmatchlen(pattern + 1, patternLen - 1, string, stringLen, nocase))
                    return 1; /* match */
                string++;
                stringLen--;
            }
            return 0; /* no match */
            break;
        case '?':
            if (stringLen == 0)
                return 0; /* no match */
            string++;
            stringLen--;
            break;
        case '[': {
            int not, match;

            pattern++;
            patternLen--;
            not = pattern[0] == '^';
            if (not) {
                pattern++;
                patternLen--;
            }
            match = 0;
            while (1) {
                if (pattern[0] == '\\') {
                    pattern++;
                    patternLen--;
                    if (pattern[0] == string[0])
                        match = 1;
                }
                else if (pattern[0] == ']') {
                    break;
                }
                else if (patternLen == 0) {
                    pattern--;
                    patternLen++;
                    break;
                }
                else if (pattern[1] == '-' && patternLen >= 3) {
                    int start = pattern[0];
                    int end = pattern[2];
                    int c = string[0];
                    if (start > end) {
                        int t = start;
                        start = end;
                        end = t;
                    }
                    if (nocase) {
                        start = tolower(start);
                        end = tolower(end);
                        c = tolower(c);
                    }
                    pattern += 2;
                    patternLen -= 2;
                    if (c >= start && c <= end)
                        match = 1;
                }
                else {
                    if (!nocase) {
                        if (pattern[0] == string[0])
                            match = 1;
                    }
                    else {
                        if (tolower((int)pattern[0]) == tolower((int)string[0]))
                            match = 1;
                    }
                }
                pattern++;
                patternLen--;
            }
            if (not)
                match = !match;
            if (!match)
                return 0; /* no match */
            string++;
            stringLen--;
            break;
        }
        case '\\':
            if (patternLen >= 2) {
                pattern++;
                patternLen--;
            }
        /* fall through */
        default:
            if (!nocase) {
                if (pattern[0] != string[0])
                    return 0; /* no match */
            }
            else {
                if (tolower((int)pattern[0]) != tolower((int)string[0]))
                    return 0; /* no match */
            }
            string++;
            stringLen--;
            break;
        }
        pattern++;
        patternLen--;
        if (stringLen == 0) {
            while (*pattern == '*') {
                pattern++;
                patternLen--;
            }
            break;
        }
    }
    if (patternLen == 0 && stringLen == 0)
        return 1;
    return 0;
}

int stringmatch(const char* pattern, const char* string, int nocase) { return stringmatchlen(pattern, strlen(pattern), string, strlen(string), nocase); }

/* Convert a string representing an amount of memory into the number of
 * bytes, so for instance memtoll("1Gb") will return 1073741824 that is
 * (1024*1024*1024).
 *
 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
 * set to 0. On error the function return value is 0, regardless of the
 * fact 'err' is NULL or not. */
long long memtoll(const char* p, int* err)
{
    const char* u;
    char buf[128];
    long mul; /* unit multiplier */
    long long val;
    unsigned int digits;

    if (err)
        *err = 0;

    /* Search the first non digit character. */
    u = p;
    if (*u == '-')
        u++;
    while (*u && isdigit(*u))
        u++;
    if (*u == '\0' || !strcasecmp(u, "b")) {
        mul = 1;
    }
    else if (!strcasecmp(u, "k")) {
        mul = 1000;
    }
    else if (!strcasecmp(u, "kb")) {
        mul = 1024;
    }
    else if (!strcasecmp(u, "m")) {
        mul = 1000 * 1000;
    }
    else if (!strcasecmp(u, "mb")) {
        mul = 1024 * 1024;
    }
    else if (!strcasecmp(u, "g")) {
        mul = 1000L * 1000 * 1000;
    }
    else if (!strcasecmp(u, "gb")) {
        mul = 1024L * 1024 * 1024;
    }
    else {
        if (err)
            *err = 1;
        return 0;
    }

    /* Copy the digits into a buffer, we'll use strtoll() to convert
     * the digit (without the unit) into a number. */
    digits = u - p;
    if (digits >= sizeof(buf)) {
        if (err)
            *err = 1;
        return 0;
    }
    memcpy(buf, p, digits);
    buf[digits] = '\0';

    char* endptr;
    errno = 0;
    val = strtoll(buf, &endptr, 10);
    if ((val == 0 && errno == EINVAL) || *endptr != '\0') {
        if (err)
            *err = 1;
        return 0;
    }
    return val * mul;
}

/* Return the number of digits of 'v' when converted to string in radix 10.
 * See ll2string() for more information. */
uint32_t digits10(uint64_t v)
{
    if (v < 10)
        return 1;
    if (v < 100)
        return 2;
    if (v < 1000)
        return 3;
    if (v < 1000000000000UL) {
        if (v < 100000000UL) {
            if (v < 1000000) {
                if (v < 10000)
                    return 4;
                return 5 + (v >= 100000);
            }
            return 7 + (v >= 10000000UL);
        }
        if (v < 10000000000UL) {
            return 9 + (v >= 1000000000UL);
        }
        return 11 + (v >= 100000000000UL);
    }
    return 12 + digits10(v / 1000000000000UL);
}

/* Like digits10() but for signed values. */
uint32_t sdigits10(int64_t v)
{
    if (v < 0) {
        /* Abs value of LLONG_MIN requires special handling. */
        uint64_t uv = (v != LLONG_MIN) ? (uint64_t)-v : ((uint64_t)LLONG_MAX) + 1;
        return digits10(uv) + 1; /* +1 for the minus. */
    }
    else {
        return digits10(v);
    }
}

/* Convert a long long into a string. Returns the number of
 * characters needed to represent the number.
 * If the buffer is not big enough to store the string, 0 is returned.
 *
 * Based on the following article (that apparently does not provide a
 * novel approach but only publicizes an already used technique):
 *
 * https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
 *
 * Modified in order to handle signed integers since the original code was
 * designed for unsigned integers. */
int ll2string(char* dst, size_t dstlen, long long svalue)
{
    static const char digits[201] = "0001020304050607080910111213141516171819"
                                    "2021222324252627282930313233343536373839"
                                    "4041424344454647484950515253545556575859"
                                    "6061626364656667686970717273747576777879"
                                    "8081828384858687888990919293949596979899";
    int negative;
    unsigned long long value;

    /* The main loop works with 64bit unsigned integers for simplicity, so
     * we convert the number here and remember if it is negative. */
    if (svalue < 0) {
        if (svalue != LLONG_MIN) {
            value = -svalue;
        }
        else {
            value = ((unsigned long long)LLONG_MAX) + 1;
        }
        negative = 1;
    }
    else {
        value = svalue;
        negative = 0;
    }

    /* Check length. */
    uint32_t const length = digits10(value) + negative;
    if (length >= dstlen)
        return 0;

    /* Null term. */
    uint32_t next = length;
    dst[next] = '\0';
    next--;
    while (value >= 100) {
        int const i = (value % 100) * 2;
        value /= 100;
        dst[next] = digits[i + 1];
        dst[next - 1] = digits[i];
        next -= 2;
    }

    /* Handle last 1-2 digits. */
    if (value < 10) {
        dst[next] = '0' + (uint32_t)value;
    }
    else {
        int i = (uint32_t)value * 2;
        dst[next] = digits[i + 1];
        dst[next - 1] = digits[i];
    }

    /* Add sign. */
    if (negative)
        dst[0] = '-';
    return length;
}

/* Convert a string into a long long. Returns 1 if the string could be parsed
 * into a (non-overflowing) long long, 0 otherwise. The value will be set to
 * the parsed value when appropriate. */
int string2ll(const char* s, size_t slen, long long* value)
{
    const char* p = s;
    size_t plen = 0;
    int negative = 0;
    unsigned long long v;

    if (plen == slen)
        return 0;

    /* Special case: first and only digit is 0. */
    if (slen == 1 && p[0] == '0') {
        if (value != NULL)
            *value = 0;
        return 1;
    }

    if (p[0] == '-') {
        negative = 1;
        p++;
        plen++;

        /* Abort on only a negative sign. */
        if (plen == slen)
            return 0;
    }

    /* First digit should be 1-9, otherwise the string should just be 0. */
    if (p[0] >= '1' && p[0] <= '9') {
        v = p[0] - '0';
        p++;
        plen++;
    }
    else if (p[0] == '0' && slen == 1) {
        *value = 0;
        return 1;
    }
    else {
        return 0;
    }

    while (plen < slen && p[0] >= '0' && p[0] <= '9') {
        if (v > (ULLONG_MAX / 10)) /* Overflow. */
            return 0;
        v *= 10;

        if (v > (ULLONG_MAX - (p[0] - '0'))) /* Overflow. */
            return 0;
        v += p[0] - '0';

        p++;
        plen++;
    }

    /* Return if not all bytes were used. */
    if (plen < slen)
        return 0;

    if (negative) {
        if (v > ((unsigned long long)(-(LLONG_MIN + 1)) + 1)) /* Overflow. */
            return 0;
        if (value != NULL)
            *value = -v;
    }
    else {
        if (v > LLONG_MAX) /* Overflow. */
            return 0;
        if (value != NULL)
            *value = v;
    }
    return 1;
}

/* Convert a string into a long. Returns 1 if the string could be parsed into a
 * (non-overflowing) long, 0 otherwise. The value will be set to the parsed
 * value when appropriate. */
int string2l(const char* s, size_t slen, long* lval)
{
    long long llval;

    if (!string2ll(s, slen, &llval))
        return 0;

    if (llval < LONG_MIN || llval > LONG_MAX)
        return 0;

    *lval = (long)llval;
    return 1;
}

/* Convert a double to a string representation. Returns the number of bytes
 * required. The representation should always be parsable by strtod(3). */
int d2string(char* buf, size_t len, double value)
{
    if (isnan(value)) {
        len = snprintf(buf, len, "nan");
    }
    else if (isinf(value)) {
        if (value < 0)
            len = snprintf(buf, len, "-inf");
        else
            len = snprintf(buf, len, "inf");
    }
    else if (value == 0) {
        /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
        if (1.0 / value < 0)
            len = snprintf(buf, len, "-0");
        else
            len = snprintf(buf, len, "0");
    }
    else {
#if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
        /* Check if the float is in a safe range to be casted into a
         * long long. We are assuming that long long is 64 bit here.
         * Also we are assuming that there are no implementations around where
         * double has precision < 52 bit.
         *
         * Under this assumptions we test if a double is inside an interval
         * where casting to long long is safe. Then using two castings we
         * make sure the decimal part is zero. If all this is true we use
         * integer printing function that is much faster. */
        double min = -4503599627370495; /* (2^52)-1 */
        double max = 4503599627370496;  /* -(2^52) */
        if (value > min && value < max && value == ((double)((long long)value)))
            len = ll2string(buf, len, (long long)value);
        else
#endif
            len = snprintf(buf, len, "%.17g", value);
    }

    return len;
}

/* Return true if the specified path is just a file basename without any
 * relative or absolute path. This function just checks that no / or \
 * character exists inside the specified path, that's enough in the
 * environments where Redis runs. */
int pathIsBaseName(char* path) { return strchr(path, '/') == NULL && strchr(path, '\\') == NULL; }

#ifdef REDIS_TEST
#include <assert.h>

static void test_string2ll(void)
{
    char buf[32];
    long long v;

    /* May not start with +. */
    strcpy(buf, "+1");
    assert(string2ll(buf, strlen(buf), &v) == 0);

    /* Leading space. */
    strcpy(buf, " 1");
    assert(string2ll(buf, strlen(buf), &v) == 0);

    /* Trailing space. */
    strcpy(buf, "1 ");
    assert(string2ll(buf, strlen(buf), &v) == 0);

    /* May not start with 0. */
    strcpy(buf, "01");
    assert(string2ll(buf, strlen(buf), &v) == 0);

    strcpy(buf, "-1");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == -1);

    strcpy(buf, "0");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == 0);

    strcpy(buf, "1");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == 1);

    strcpy(buf, "99");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == 99);

    strcpy(buf, "-99");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == -99);

    strcpy(buf, "-9223372036854775808");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == LLONG_MIN);

    strcpy(buf, "-9223372036854775809"); /* overflow */
    assert(string2ll(buf, strlen(buf), &v) == 0);

    strcpy(buf, "9223372036854775807");
    assert(string2ll(buf, strlen(buf), &v) == 1);
    assert(v == LLONG_MAX);

    strcpy(buf, "9223372036854775808"); /* overflow */
    assert(string2ll(buf, strlen(buf), &v) == 0);
}

static void test_string2l(void)
{
    char buf[32];
    long v;

    /* May not start with +. */
    strcpy(buf, "+1");
    assert(string2l(buf, strlen(buf), &v) == 0);

    /* May not start with 0. */
    strcpy(buf, "01");
    assert(string2l(buf, strlen(buf), &v) == 0);

    strcpy(buf, "-1");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == -1);

    strcpy(buf, "0");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == 0);

    strcpy(buf, "1");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == 1);

    strcpy(buf, "99");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == 99);

    strcpy(buf, "-99");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == -99);

#if LONG_MAX != LLONG_MAX
    strcpy(buf, "-2147483648");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == LONG_MIN);

    strcpy(buf, "-2147483649"); /* overflow */
    assert(string2l(buf, strlen(buf), &v) == 0);

    strcpy(buf, "2147483647");
    assert(string2l(buf, strlen(buf), &v) == 1);
    assert(v == LONG_MAX);

    strcpy(buf, "2147483648"); /* overflow */
    assert(string2l(buf, strlen(buf), &v) == 0);
#endif
}

static void test_ll2string(void)
{
    char buf[32];
    long long v;
    int sz;

    v = 0;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 1);
    assert(!strcmp(buf, "0"));

    v = -1;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 2);
    assert(!strcmp(buf, "-1"));

    v = 99;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 2);
    assert(!strcmp(buf, "99"));

    v = -99;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 3);
    assert(!strcmp(buf, "-99"));

    v = -2147483648;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 11);
    assert(!strcmp(buf, "-2147483648"));

    v = LLONG_MIN;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 20);
    assert(!strcmp(buf, "-9223372036854775808"));

    v = LLONG_MAX;
    sz = ll2string(buf, sizeof buf, v);
    assert(sz == 19);
    assert(!strcmp(buf, "9223372036854775807"));
}

#define UNUSED(x) (void)(x)
int utilTest(int argc, char** argv)
{
    UNUSED(argc);
    UNUSED(argv);

    test_string2ll();
    test_string2l();
    test_ll2string();
    return 0;
}
#endif