atoi をスクラッチ実装してみた
2024-01-24
azblob://2024/01/24/eyecatch/2024-01-23-atoi-scratch-000.jpg
C言語で標準ライブラリに用意されている atoi の再実装に関してまとめました。
実装時、特に注意する点はLONG_MAX または LONG_MIN を超えたかどうかを判定する必要があることです。

atoi とは

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の実装

atoi を再実装しましたが、今回は上記 3 ~ 7 の手順とオーバーロードとアンダーフローのエラーハンドリングの部分を記述します。
 
C#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"
tag C