co89757
8/3/2016 - 5:46 AM

## Redis number-string conversion optimized

Redis number-string conversion optimized

``````/* Return the number of digits of 'v' when converted to string in radix 10.
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):
*
*
* 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];
}

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.
*
* Note that this function demands that the string strictly represents
* a long long: no spaces or other characters before or after the string
* representing the number are accepted, nor zeroes at the start if not
* for the string "0" representing the zero number.
*
* Because of its strictness, it is safe to use this function to check if
* you can convert a string into a long long, and obtain back the string
* from the number without any loss in the string representation. */
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 string into a double. Returns 1 if the string could be parsed
* into a (non-overflowing) double, 0 otherwise. The value will be set to
* the parsed value when appropriate.
*
* Note that this function demands that the string strictly represents
* a double: no spaces or other characters before or after the string
* representing the number are accepted. */
int string2ld(const char *s, size_t slen, long double *dp) {
char buf[256];
long double value;
char *eptr;

if (slen >= sizeof(buf)) return 0;
memcpy(buf,s,slen);
buf[slen] = '\0';

errno = 0;
value = strtold(buf, &eptr);
if (isspace(buf[0]) || eptr[0] != '\0' ||
(errno == ERANGE &&
(value == HUGE_VAL || value == -HUGE_VAL || value == 0)) ||
errno == EINVAL ||
isnan(value))
return 0;

if (dp) *dp = value;
return 1;
}

/* Convert a double to a string representation. Returns the number of bytes
* required. The representation should always be parsable by strtod(3).
* This function does not support human-friendly formatting like ld2string
* does. It is intented mainly to be used inside t_zset.c when writing scores
* into a ziplist representing a sorted set. */
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;
}

/* Convert a long double into a string. If humanfriendly is non-zero
* it does not use exponential format and trims trailing zeroes at the end,
* however this results in loss of precision. Otherwise exp format is used
* and the output of snprintf() is not modified.
*
* The function returns the length of the string or zero if there was not
* enough buffer room to store it. */
int ld2string(char *buf, size_t len, long double value, int humanfriendly) {
size_t l;

if (isinf(value)) {
/* Libc in odd systems (Hi Solaris!) will format infinite in a
* different way, so better to handle it in an explicit way. */
if (len < 5) return 0; /* No room. 5 is "-inf\0" */
if (value > 0) {
memcpy(buf,"inf",3);
l = 3;
} else {
memcpy(buf,"-inf",4);
l = 4;
}
} else if (humanfriendly) {
/* We use 17 digits precision since with 128 bit floats that precision
* after rounding is able to represent most small decimal numbers in a
* way that is "non surprising" for the user (that is, most small
* decimal numbers will be represented in a way that when converted
* back into a string are exactly the same as what the user typed.) */
l = snprintf(buf,len,"%.17Lf", value);
if (l+1 > len) return 0; /* No room. */
/* Now remove trailing zeroes after the '.' */
if (strchr(buf,'.') != NULL) {
char *p = buf+l-1;
while(*p == '0') {
p--;
l--;
}
if (*p == '.') l--;
}
} else {
l = snprintf(buf,len,"%.17Lg", value);
if (l+1 > len) return 0; /* No room. */
}
buf[l] = '\0';
return l;
}``````