yohhoyの日記

技術的メモをしていきたい日記

atoi関数のかしこい実装

C標準ライブラリ Muslのatoi関数実装 では、符号付き整数オーバーフロー回避のため負数範囲で10進数値を減算してゆき最後に符号反転を行っている。

int atoi(const char *s)
{
  int n=0, neg=0;
  while (isspace(*s)) s++;
  switch (*s) {
  case '-': neg=1;
  case '+': s++;
  }
  /* Compute n as a negative number to avoid overflow on INT_MIN */
  while (isdigit(*s))
    n = 10 * n - (*s++ - '0');
  return neg ? n : -n;
}

C言語の符号付き整数型(int)では “2の補数” 表現が用いられるため*1、最大値INT_MAXより最小値INT_MINの絶対値が 1 だけ大きくなり(例:16bit幅ならINT_MAX = 32767, INT_MIN = -32768)、正数範囲の累積計算では値-INT_MINを表現できず未定義動作(undefined behavior)を引き起こしてしまう。*2

その他のC標準ライブラリ実装(glibc, BSD libc, Newlib)では、単純にstrtol関数へ実装移譲している。

int atoi (const char *s)
{
  return (int) strtol (s, NULL, 10);
}

ノート:int型よりlong型の値域が広い場合strtol関数戻り値キャストで未定義動作(undefined behavior)となるが、そもそもC標準ライブラリatoi関数仕様では「戻り値がint型の値域外となる場合の動作は未定義(the behavior is undefined)」とされるため何ら問題はない。いいね?

C99 3.4.3/p3, 7.20.1/p1, 7.20.1.4/p8より引用(下線部は強調)。

EXAMPLE An example of undefined behavior is the behavior on integer overflow.

The functions atof, atoi, atol, and atoll need not affect the value of the integer expression errno on an error. If the value of the result cannot be represented, the behavior is undefined.

The strtol, strtoll, strtoul, and strtoull functions return the converted value, if any. If no conversion could be performed, zero is returned. If the correct value is outside the range of representable values, LONG_MIN, LONG_MAX, LLONG_MIN, LLONG_MAX, ULONG_MAX, or ULLONG_MAX is returned (according to the return type and sign of the value, if any), and the value of the macro ERANGE is stored in errno.

関連URL

*1:C17現在は “1の補数(ones' complement)” または “符号と絶対値(sign and magnitude)” 表現も許容されるが、次期規格C2xでは “2の補数(two's complement)” のみ許容と改定される。提案文書(PDF)N2412参照。

*2:符号付き整数オーバーフローは、標準規格での明示的な定義が無いことをもって未定義動作とされる(C99 4/p2)