Zenn
⛳

atoi をスクラッチ実装してみた

2024/02/23に公開
C
tech

C言語で標準ライブラリに用意されている atoi の再実装に関してまとめました。
実装時、特に注意する点はLONG_MAX または LONG_MIN を超えたかどうかを判定する必要があることです。

atoi とは

FreeBSD

The atoi() function converts the initial portion of the string pointed to by nptr to int representation.

簡単にいうと、string 型の値を int 型の値 123 に変換する関数です。
例えば "123"(string 型) を 123(int 型) に変換します。

また、atoi の FreeBSD マニュアルには以下のように記述されています。

It is equivalent to: (int)strtol(str, (char **)NULL, 10);
これは atoi が C 言語の標準ライブラリで用意されている strtol 関数を (int)strtol(str, (char **)NULL, 10); として使用する場合と同等の挙動をすると記述されています。

ここで 1 点、注意することがあります。
それは、atoi が受け取った値を変換する時に、アンダーフローやオーバーフローが発生した場合の返り値です。

その内容は strtol の FreeBSD マニュアルの RETURN VALUE の内容に記述されています。

では、確認してみます。

The strtol() function returns the result of the conversion, unless the value would underflow or overflow. If an underflow occurs, strtol() returns LONG_MIN. If an overflow occurs, strtol() returns LONG_MAX. In both cases, errno is set to ERANGE. Precisely the same holds for strtoll() (with LLONG_MIN and LLONG_MAX instead of LONG_MIN and LONG_MAX).

strtol() では、アンダーフローが発生すれば LONG_MIN を、オーバーフローが発生すれば LONG_MAX を返すと定義されています。
つまり、atoi() では、アンダーフローまたはオーバーフローが発生した場合、それぞれ int でキャストした LONG_MIN, LONG_MAX を返すとのことですね。

具体的にオーバーフローが発生する入力値

long の取りうる値が、-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 の範囲であるので、例えば以下のような入力値がアンダーフローとオーバーフローの候補になります。

  • "9223372036854775811"
  • "-92233720368547758090000"

atoiの実装方針

概ね以下の通りになります。

  1. 入力された文字列に対して、先頭文字のアドレスから isspace(3) で定義されている空白文字に該当する場合、'+' か '-' または '0' ~ '9' の文字が出現するまでアドレスを進める。
  2. 1 で詰めた先のアドレスが '+' または '-' であれば、符号の情報を保持して次のアドレスに進める。
  3. 最終的な結果を返す値を格納する変数を用意して、0 で初期化する。
  4. 最終的な結果を返す値を格納する変数の値を 10 倍する。
  5. 現在のアドレスに char 型の '0' ~ '9' に該当する値が格納されていれば、char 型の '0' ~ '9' を int 型の 0 ~ 9 に変換する。
  6. 3 で用意した変数に 5 で変換した値を足して次のアドレスに進む。
  7. null 文字まで 4 ~ 6 を繰り返す。
    ※atol を int にキャストしたものを返せば atoi になりますが、今回は意図的にその方法を使用していません。

ただし、これだけでは不十分でオーバーロードとアンダーフローのエラーハンドリングが必要です。
今回は、5 と 6 の処理の間にオーバーロードとアンダーフローのエラーハンドリングを加えて実装してみました。

atoiの部分的な実装

実際に上記 3 ~ 7 の手順とオーバーロードとアンダーフローのエラーハンドリングを実装してみます。

#include <errno.h>
#include <limits.h>

static int	ft_isdigit(int c)
{
	return ('0' <= c && c <= '9');
}

static int	is_overflow(int sign, unsigned long num, unsigned long x)
{
	unsigned long	cutoff;

	if (sign > 0)
		cutoff = LONG_MAX;
	else
		cutoff = (unsigned long)LONG_MAX + 1;
	return (cutoff / 10 < num || cutoff - num * 10 < x);
}

int	ft_atoi(const char *str)
{
	int				sign;
    unsigned long	temp;
	unsigned long	res;

    ...

	res = 0;
	while (*str && ft_isdigit(*str))
	{
		temp = *str++ - '0';
        // For positive numbers, SIGN is assigned 1. For negative numbers. SIGN is assigned -1.
		if (is_overflow(sign, res, temp))
		{
			errno = ERANGE;
			if (sign > 0)
				return ((int)LONG_MAX);
			return ((int)LONG_MIN);
		}
		res = res * 10 + temp;
	}
	return ((int)(sign * res));
}

オーバフローとアンダーフローの判定は is_overflow で行っています。
こちらの関数内のオーバフローとアンダーフローの判定条件について少し解説すると、以下の通りとなります。

  • num が cutoff / 10 より大きい値であれば、次の ft_atoi 内のループで num は 10 倍されるため、オーバフローまたはアンダーフローが発生します。
  • cutoff - num * 10 < x の条件を満たさない場合、ft_atoi 内の res = res * 10 + temp; の処理でオーバーフローまたはアンダーフローが発生します。

オーバーフローであると判定される具体的な値は以下が挙げられます。(アンダーフローを除く)
1 つ目の条件で、"9223372036854775810", "9223372036854775811", "9223372036854775812" ...
2 つ目の条件で、"9223372036854775808", "9223372036854775809"

Discussion