Soupen源码解析之itoa实现

写在最前

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

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

提出问题

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

原型如下

int itoa(char *buffer, int64_t value);

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

分析问题

这还不容易么？很容易写出这样的代码：

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’并不是期望的结果。

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

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，来处理这些问题。

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

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]中的任何一个数都是正确的。

Yebangyu's Blog

Fond of Concurrency Programming , Distributed System and Machine Learning

Soupen源码解析之itoa实现

写在最前

提出问题

分析问题

解决问题