Yebangyu's Blog

Fond of Concurrency Programming and Machine Learning

Soupen源码解析之itoa实现

写在最前

Soupen是一款高性能的nosql数据库,旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Github请访问这里 ,Python客户端请点击这里

提出问题

如何用C/C++实现正确的、可移植的、高效的、对所有整数都work的itoa函数?

原型如下

int itoa(char *buffer, int64_t value);

将value转为字符串后存在buffer中,返回字符串的长度。

分析问题

这还不容易么?很容易写出这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int itoa(char *buffer, int64_t value)
{
  char *p = buffer;
  int64_t tmp = value;
  do {
    *p = tmp % 10 + '0';
    tmp /= 10;
    ++p;
  } while(tmp);
  if(value < 0) {
    *p++ = '-';
  }
  std::reverse(buffer, p);
  return p - buffer;
}

这个实现,有什么问题?问题是显而易见的:当value为负数时,在第6行,例如value = -123,如果tmp % 10 = -3,而-3 + ‘0’并不是期望的结果。

有些人说,这还不容易吗?把负数都搞成正数,用它的绝对值来计算,不就行了吗?于是很容易写出这样的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int itoa(char *buffer, int64_t value)
{
  char *p = buffer;
  int64_t tmp = value < 0 ? -value : value;
  do {
    *p = tmp % 10 + '0';
    tmp /= 10;
    ++p;
  } while(tmp);
  if(value < 0) {
    *p++ = '-';
  }
  std::reverse(buffer, p);
  return p - buffer;
}

还是有问题,注意第4行。回忆一下本科时候所学的计算机组成原理,我们知道,对于有符号整数,它的最大值和最小值是不对称的,绝对值差1。其中,64位有符号整数的范围为[-9223372036854775808, 9223372036854775807]

因此,在第4行,如果value是INT64_MIN,对它求绝对值-value的结果其实已经超出了64位有符号整数可以表示的范围,这里已经溢出了!!!

哦哦,这好办,对INT64_MIN单独处理行不行?

行,但是代码会非常不优雅了。

Matthew Wilson大神的Efficient Integer to String Conversions文章里,使用如下的trick,来处理这些问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int itoa(char *buffer, int64_t value)
{
  static const char digits[19] = {'9','8','7','6','5','4','3','2','1','0','1','2','3','4','5','6','7','8','9'};
  static const char *zero = digits + 9;
  char *p = buffer;
  int64_t tmp = value;
  do {
    *p = zero[tmp % 10];//下标可能是负数
    tmp /= 10;
    ++p;
  } while(tmp);
  if(value < 0) {
    *p++ = '-';
  }
  std::reverse(buffer, p);
  return p - buffer;
}

这下没问题了吧?有。

问题出在第8、9行。

举个例子,请问,-123 / 10结果是多少?-123 % 10 呢?

因为-123 = (-12) * 10 + (-3) 因此-123 / 10 = -12,同时-123 % 10 = -3

但是!

因为-123 =(-13) * 10 + 7 因此-123 / 10 = -13,同时-123 % 10 = 7

两种可能的结果?事实上,C++98和C++03标准并没有对被除数和除数不都为正数时的情形进行明确的说明,第8、9行的结果是未定义的,是很不可移植的。

如果在某个具体的实现下,-123 / 10 = -13,并且 -123 % 10 = 7 ,那么以上代码结果不对。

解决问题

Soupen中实现了itoa,代码在src/server/soupen_order.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
YEDIS_MUST_INLINE int64_t int2char(char *buffer, int64_t value)
{
  static const char remainder_offset[2][19] = { { '9', '8', '7', '6', '5', '4', '3', '2', '1', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' },//正数

                                                { '9', '8', '7', '6', '5', '4', '3', '2', '1', '0', '9', '8', '7', '6', '5', '4', '3', '2', '1' } };//负数

  static const bool quotient_offset[2][19] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },//正数

                                               { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };//负数								  
  char *p = buffer;
  int64_t tmp = value;
  int flag = (value < 0);
  const char *digit = remainder_offset[flag] + 9;
  const bool *offset = quotient_offset[flag] + 9;
  do {
    int remainder = tmp % 10;
    *p = digit[remainder];
    tmp = tmp / 10 + offset[remainder];
    ++p;
  } while (tmp);
  if(flag) {
    *p++ = '-';
  }
  std::reverse(buffer, p);
  return p - buffer;
}

通过两个二维数组,很巧妙、完美的解决了这个问题。它对于[INT64_MIN, INT64_MAX]中的任何一个数都是正确的。