str2int.c
text/plain
Filename: str2int.c
Type: text/plain
Part: 0
#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define PG_INT32_MIN (-0x7FFFFFFF-1)
#define PG_INT32_MAX (0x7FFFFFFF)
#define true 1
#define false 0
#ifndef _MSC_VER
#define HAVE__BUILTIN_CLZ
#define HAVE__BUILTIN_OP_OVERFLOW
#define likely(x) __builtin_expect((x) != 0, 1)
#define unlikely(x) __builtin_expect((x) != 0, 0)
#else
#define likely(x) x
#define unlikely(x) x
#endif
typedef char bool;
typedef unsigned int uint32;
typedef int int32;
typedef char int8;
typedef unsigned char uint8;
typedef long long int64;
static inline bool
pg_sub_s32_overflow(int32 a, int32 b, int32 *result)
{
#if defined(HAVE__BUILTIN_OP_OVERFLOW)
return __builtin_sub_overflow(a, b, result);
#else
int64 res = (int64) a - (int64) b;
if (res > PG_INT32_MAX || res < PG_INT32_MIN)
{
*result = 0x5EED; /* to avoid spurious warnings */
return true;
}
*result = (int32) res;
return false;
#endif
}
static inline bool
pg_mul_s32_overflow(int32 a, int32 b, int32 *result)
{
#if defined(HAVE__BUILTIN_OP_OVERFLOW)
return __builtin_mul_overflow(a, b, result);
#else
int64 res = (int64) a * (int64) b;
if (res > PG_INT32_MAX || res < PG_INT32_MIN)
{
*result = 0x5EED; /* to avoid spurious warnings */
return true;
}
*result = (int32) res;
return false;
#endif
}
int32
pg_strtoint32(const char *s)
{
const char *ptr = s;
int32 tmp = 0;
bool neg = false;
/* skip leading spaces */
while (likely(*ptr) && isspace((unsigned char) *ptr))
ptr++;
/* handle sign */
if (*ptr == '-')
{
ptr++;
neg = true;
}
else if (*ptr == '+')
ptr++;
/* require at least one digit */
if (unlikely(!isdigit((unsigned char) *ptr)))
goto invalid_syntax;
while (*ptr && isdigit((unsigned char) *ptr))
{
int8 digit = (*ptr++ - '0');
if (unlikely(pg_mul_s32_overflow(tmp, 10, &tmp)) ||
unlikely(pg_sub_s32_overflow(tmp, digit, &tmp)))
goto out_of_range;
}
/* allow trailing whitespace, but not other trailing chars */
while (*ptr != '\0' && isspace((unsigned char) *ptr))
ptr++;
if (unlikely(*ptr != '\0'))
goto invalid_syntax;
if (!neg)
{
/* could fail if input is most negative number */
if (unlikely(tmp == PG_INT32_MIN))
goto out_of_range;
tmp = -tmp;
}
return tmp;
out_of_range:
fprintf(stderr, "value \"%s\" is out of range for type %s",
s, "integer");
invalid_syntax:
fprintf(stderr, "invalid input syntax for type %s: \"%s\"",
"integer", s);
return 0; /* keep compiler quiet */
}
int32
pg_strtoint32_v2(const char *s)
{
const char *ptr = s;
uint32 tmp = 0;
bool neg = false;
/* skip leading spaces */
while (likely(*ptr) && isspace((unsigned char) *ptr))
ptr++;
/* handle sign */
if (*ptr == '-')
{
ptr++;
neg = true;
}
else if (*ptr == '+')
ptr++;
/* require at least one digit */
if (unlikely(!isdigit((unsigned char) *ptr)))
goto invalid_syntax;
while (*ptr && isdigit((unsigned char) *ptr))
{
// if (unlikely(tmp > (PG_INT32_MAX / 10)))
if (unlikely(tmp >= (1 - PG_INT32_MIN / 10)))
goto out_of_range;
tmp = tmp * 10 + (*ptr++ - '0');
}
/* allow trailing whitespace, but not other trailing chars */
while (*ptr != '\0' && isspace((unsigned char) *ptr))
ptr++;
if (unlikely(*ptr != '\0'))
goto invalid_syntax;
if (neg)
{
if (tmp > (uint32) (-(PG_INT32_MIN + 1)) + 1)
goto out_of_range;
return -((int32) tmp);
}
if (tmp > PG_INT32_MAX)
goto out_of_range;
return (int32) tmp;
out_of_range:
fprintf(stderr, "value \"%s\" is out of range for type %s",
s, "integer");
exit(-1);
invalid_syntax:
fprintf(stderr, "invalid input syntax for type %s: \"%s\"",
"integer", s);
exit(-1);
return 0; /* keep compiler quiet */
}
static const char DIGIT_TABLE[200] =
"00" "01" "02" "03" "04" "05" "06" "07" "08" "09"
"10" "11" "12" "13" "14" "15" "16" "17" "18" "19"
"20" "21" "22" "23" "24" "25" "26" "27" "28" "29"
"30" "31" "32" "33" "34" "35" "36" "37" "38" "39"
"40" "41" "42" "43" "44" "45" "46" "47" "48" "49"
"50" "51" "52" "53" "54" "55" "56" "57" "58" "59"
"60" "61" "62" "63" "64" "65" "66" "67" "68" "69"
"70" "71" "72" "73" "74" "75" "76" "77" "78" "79"
"80" "81" "82" "83" "84" "85" "86" "87" "88" "89"
"90" "91" "92" "93" "94" "95" "96" "97" "98" "99";
const uint8 pg_leftmost_one_pos[256] = {
0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};
static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
return 31 - __builtin_clz(word);
#else
int shift = 32 - 8;
while ((word >> shift) == 0)
shift -= 8;
return shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif /* HAVE__BUILTIN_CLZ */
}
static inline int
decimalLength32(const uint32 v)
{
int t;
static const uint32 PowersOfTen[] = {
1, 10, 100,
1000, 10000, 100000,
1000000, 10000000, 100000000,
1000000000
};
/*
* Compute base-10 logarithm by dividing the base-2 logarithm by a
* good-enough approximation of the base-2 logarithm of 10
*/
t = (pg_leftmost_one_pos32(v) + 1) * 1233 / 4096;
return t + (v >= PowersOfTen[t]);
}
/*
* pg_ultoa_n: converts an unsigned 32-bit integer to its string representation,
* not NUL-terminated, and returns the length of that string representation
*
* Caller must ensure that 'a' points to enough memory to hold the result (at
* least 10 bytes)
*/
int
pg_ultoa_n(uint32 value, char *a)
{
int olength,
i = 0;
/* Degenerate case */
if (value == 0)
{
*a = '0';
return 1;
}
olength = decimalLength32(value);
/* Compute the result string. */
while (value >= 10000)
{
const uint32 c = value - 10000 * (value / 10000);
const uint32 c0 = (c % 100) << 1;
const uint32 c1 = (c / 100) << 1;
char *pos = a + olength - i;
value /= 10000;
memcpy(pos - 2, DIGIT_TABLE + c0, 2);
memcpy(pos - 4, DIGIT_TABLE + c1, 2);
i += 4;
}
if (value >= 100)
{
const uint32 c = (value % 100) << 1;
char *pos = a + olength - i;
value /= 100;
memcpy(pos - 2, DIGIT_TABLE + c, 2);
i += 2;
}
if (value >= 10)
{
const uint32 c = value << 1;
char *pos = a + olength - i;
memcpy(pos - 2, DIGIT_TABLE + c, 2);
}
else
{
*a = (char) ('0' + value);
}
return olength;
}
int
pg_ltoa(int32 value, char *a)
{
uint32 uvalue = (uint32) value;
int len = 0;
if (value < 0)
{
uvalue = (uint32) 0 - uvalue;
a[len++] = '-';
}
len += pg_ultoa_n(uvalue, a + len);
a[len] = '\0';
return len;
}
//#define START -100000000
//#define END 100000000
#define DEFAULT_START PG_INT32_MIN
#define DEFAULT_END PG_INT32_MAX
int main(int argc, char **argv)
{
clock_t start, end;
int64 n, e;
char buff[16];
double v1_time, v2_time;
if (argc < 3)
{
n = DEFAULT_START;
e = DEFAULT_END;
}
else
{
n = pg_strtoint32(argv[1]);
e = pg_strtoint32(argv[2]);
}
printf("n = %lld, e = %lld\n", n, e);
start = clock();
while (n <= e)
{
int64 y;
pg_ltoa((int32) n, buff);
y = pg_strtoint32(buff);
if (n != y)
fprintf(stderr, "%lld != %lld\n", n, y);
n++;
}
end = clock();
v1_time = (double) (end - start) / CLOCKS_PER_SEC;
printf("pg_strtoint32 in %f seconds\n", v1_time);
if (argc < 3)
n = DEFAULT_START;
else
n = pg_strtoint32_v2(argv[1]);
start = clock();
while (n <= e)
{
int64 y;
pg_ltoa((int32) n, buff);
y = pg_strtoint32_v2(buff);
if (n != y)
fprintf(stderr, "%lld != %lld\n", n, y);
n++;
}
end = clock();
v2_time = (double) (end - start) / CLOCKS_PER_SEC;
printf("pg_strtoint32_v2 in %f seconds (%f%% faster)\n", v2_time, v1_time / v2_time * 100.0 - 100.0);
}