itoa() c 实现 int min 下溢

itoa() c implementation int min underflow

我 运行 一些针对我的 itoa() 函数的测试用例,但不断得到

did not allocate memory for the int min value

我正在检查,但我在这里缺少它,它是什么?

char *ft_itoa(int x) {
    char *s;
    size_t len;
    long int n;

    n = x;
    if (x == -2147483648)
        return (ft_strdup("-2147483648"));

    len = ft_intlen(n) + 1;
    if (!(s = (char*)malloc(sizeof(char) * len)))
        return (NULL);

    if (n == 0)
        s[0] = '0';

    if (n < 0) {
        s[0] = '-';
        n = -n;
    }
    s[len - 1] = '[=11=]';
    while (n) {
        len--;
        s[len - 1] = (n % 10) + '0';
        n /= 10;
    }
    return (s);
}

状态:已解决无效

原因:WORKS_FOR_ME

总之,我在某些方面有所改进。

  • sizeof(char) 总是 1,不需要它。
  • 不投malloc
  • 如果你处理特殊情况0,那就一次性处理吧。
  • -2147483648 非常非常糟糕。这就是 INT_MIN 的目的。
  • return不是函数,不要return(value),只是returnvalue.
  • 不要一直s[len - 1],最好在进入循环之前递减len。或者,由于您只在 malloc 调用中需要 len + 1,只需将 len 作为 intlen return 并调用 malloc 使用 len + 1

ft_itoa.c

#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <btstr.h>

int ft_intlen(int n) {
        char buffer[8192];
        return snprintf(buffer, sizeof buffer, "%i", n);
}

char * ft_itoa(int n) {
        char * s;
        size_t l, len;
        bool fix_int_min = false;

        if (!n) {
                return mstrcpy("0");
        }

        if (-INT_MAX != INT_MIN && n == INT_MIN) {
                ++n;
                fix_int_min = true;
        }

        len = ft_intlen(n);
        if (!(s = malloc(len + 1))) {
                return NULL;
        }
        if (n < 0) {
                s[0] = '-';
                n = -n;
        }
        s[l = len] = '[=10=]';
        while (n) {
                s[--len] = (n % 10) + '0';
                n /= 10;
        }

        if (fix_int_min) {
                --l;
                while (s[l] == '9') {
                        s[l++] = 0;
                }
                if (s[l] == '-') {
                        // realloc +1 and write "-1[0....0][=10=]"
                } else {
                        ++s[l];
                }
        }

        return s;
}

main.c

#include <limits.h>
#include <stdio.h>

char * ft_itoa(int n);

void check(int n) {
        printf("%i = %s\n", n, ft_itoa(n));
}

int main() {
        check(0);
        check(-1);
        check(1);
        check(23);
        check(42);
        check(4711);
        check(1000);
        check(INT_MAX);
        check(1+INT_MIN);
        check(INT_MIN);
}

结果

$ gcc -W -Wall -Wextra -lBtLinuxLibrary ft_itoa.c main.c -o ft_itoa && ./ft_itoa
0 = 0
-1 = -1
1 = 1
23 = 23
42 = 42
4711 = 4711
1000 = 1000
2147483647 = 2147483647
-2147483647 = -2147483647
-2147483648 = -2147483648

可能是你的防溢出机制出了问题。您尝试将类型 intx 分配给类型 long intn。但是规范并不保证类型 long int 可以处理比 int 大的值范围。可以找到更多信息 "Long Vs. Int"

如果您的编译器支持,请为 n 使用 long long int 类型。将 ft_intlen 函数更新为 int ft_intlen(long long int n)。在这种情况下,您将能够处理整个 int 类型值范围并删除以下行:

if (x == -2147483648)
  return (ft_strdup("-2147483648"));  

另外错误信息 did not allocate memory for the int min value 不是 system error numbers 之一。您需要在您的应用程序中添加更多日志记录,尤其是在由于某种原因无法调试它的情况下。检查每个系统函数调用的 errno,例如:

char* errmsg;
// Other code skipped here 
if (!(s = (char*)malloc(sizeof(char) * len)))
{
  errmsg = strerror(errno);          // Use strerror_s if possible 
  printf("Malloc error: %s\n", errmsg);
  return (NULL);
}

这一行:

if (x == -2147483648)

并不像你想象的那样。 C 没有负整数常量。这是一个值为 2^31 的无符号整型常量,您可以在其上应用一元减号运算符。这意味着表达式 x == -21... 将取决于您的编译器使用的 C 标准。

如果你使用 C99 或 C11,你会没事的。有一个足够大的有符号类型 - long long 保证对这个数字足够大,所以 x 和 -21... 都会转换成 long long 然后比较。但是,如果您使用的是 C89 编译器并且您的机器没有足够长的类型,那么您会在此处遇到实现定义的行为:

When an integer is demoted to a signed integer with smaller size, or an unsigned integer is converted to its corresponding signed integer, if the value cannot be represented the result is implementation-defined.

这就是人们说要使用 limits.h 的原因。不是因为他们学究气,而是因为这是危险的领域。如果您仔细查看 limits.h 包含的内容,您很可能会发现这样一行:

#define INT_MIN (- INT_MAX - 1)

这个表达式实际上具有正确的类型和值。

除此之外,我在您发布的代码中看不到任何错误。如果这不是问题,那么 ft_intlenft_strdup 都是错误的。或者你在测试中调用你的函数是错误的(同样的问题适用于 -21... 调用测试时)。

你不需要那张支票。而是将其转换为 unsigned,这将适合绝对值:

size_t ft_uintlen(unsigned n)
{
    size_t len = 0;
    do {
        ++len;
        n /= 10;
    } while(n);
    return len;
}

char *ft_itoa(int x)
{
    char    *s;
    size_t  len;
    unsigned n;
    int negative;

    negative = x < 0;
    n = negative ? 0-(unsigned)x : (unsigned)x;
    len = ft_uintlen(n) + negative + 1;
    if (!(s = (char*)malloc(len)))
        return (NULL);

    s[--len] = '[=10=]';
    if (negative)
        s[0] = '-';
    do {
        s[--len] = (n % 10) + '0';
        n /= 10;
    } while(n);
    return (s);
}

请注意,这使用了一个适用于 unsigned 个参数的新 size_t ft_uintlen(unsigned) 函数。

潜在的代码错误,按怀疑顺序排列:

  1. ft_strdup() 因为使用 "int min value" 调用该代码并发生错误。
  2. 缺乏各种功能的原型。特别是 ft_strdup()/strdup().
  3. Calling/test 代码错误。
  4. "int min value" 大于 -2147483648。 (最好使用 INT_MIN。)
  5. ft_intlen(n) 编码不正确,returns INT_MAX,然后代码尝试 malloc(INT_MIN).
  6. int/long 均为 64 位。这将第一个 s[len - 1] = (n % 10) + '0';INT_MIN 混淆了。

否则,如果INT_MIN的值为-2147483648,ft_itoa(int x)就可以了。


OP 断言“... strdup 只是分配字符串,ft_intlen 只是 returns 长度的字符串,两者都通过了测试用例 – franklinexpress Oct 8 at 7:52”

通过测试用例并不意味着它在不调用未定义行为的情况下工作。最好 post ft_intlen()ft_strdup() 和测试工具以供审查。


候选便携式实施。不依赖 int/long 大小或 2 的补码。不需要 <limits.h> 除了 CHAR_BIT 代码 可以 假设是 8 而不会牺牲太多的可饮用性。适用于 C89/99/11.

// Buffer size needed to decimal print any `int`
// '-' + Ceiling(value bit size * log10(2)) + [=10=]
#define INT_STR_SIZE (1 + ((CHAR_BIT*sizeof(int) - 1)/3 + 1) + 1)

char *ft_itoa(int x) {
  char buf[INT_STR_SIZE];
  char *s = buf + sizeof buf - 1;  // Set to end of buffer
  *s = '[=10=]';

  int n = x; // no need for wider types like long

  if (n > 0) {
    // fold positive numbers to negative ones
    // This avoids the special code for `INT_MIN` and need for wider types
    n = -n;
  }

  // Using a do loop avoids special code for `x==0`
  do {
    // Use `div()` rather than / % in case we are using C89.
    // / %  has implementation defined results for negative arguments.
    div_t qr = div(n, 10);
    *--s = (char) ('0' - qr.rem);  // Form digit from negative .rem
    n = qr.quot;
  } while (n);

  if (x < 0) {
    *--s = '-';
  }

  // Double check ft_strdup() is coded correctly
  // Insure calling code frees the buffer when done.
  return ft_strdup(s); 
}

您提供的代码片段在 OsX 上编译并运行,但使用我自己的 ft_stdupft_intlen。因此,您可以向我们展示代码或检查它们是否有错误。 我做了一些测试(包括2147483647,-2147483648)。效果很好。

无论如何,行:

if (x == -2147483648) return (ft_strdup("-2147483648"));

只要在对它进行任何操作之前将 x 值复制到 long long 变量 () 中就没有用。所以你不需要包括 types.h(臭名昭著的 moulinette 不会给你 -42)。

碰巧在 OsX 上它也适用于 long 值,但这是不可移植的安全。

只需使用:

INT_MIN

而不是:

-2147483648

在你的测试中:

if (x == INT_MIN)
    return (ft_strdup("-2147483648"));

这是因为某些编译器可能无法理解该数字。

标准C库limits.h通常定义为:

#define INT_MIN  (-INT_MAX - 1)

避免这个问题。