c - itoa() c 实现 int min 下溢

Question

我正在针对我的 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] = '\0';
    while (n) {
        len--;
        s[len - 1] = (n % 10) + '0';
        n /= 10;
    }
    return (s);
}

score 10 · Accepted Answer

这一行：

if (x == -2147483648)

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

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

当一个整数被降级为具有较小大小的有符号整数，或者一个无符号整数被转换为其对应的有符号整数时，如果该值不能表示，则结果是实现定义的。

这就是为什么人们说要使用limits.h。不是因为他们很迂腐，而是因为这是一个危险的领域。如果您仔细查看limits.h 包含的内容，您很可能会发现这样一行：

#define INT_MIN (- INT_MAX - 1)

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

除此之外，我在您发布的代码中看不到任何错误。如果这不是问题ft_intlen或者ft_strdup是错误的。或者你在测试错误时调用你的函数（同样的问题适用于 -21... 调用测试时）。

score 2 · Accepted Answer

状态：已解决无效

原因：WORKS_FOR_ME

无论如何，我在某些方面有所改进。

sizeof(char)始终为 1，不需要它。
不要施放malloc
如果您处理特殊情况0，那么只需一次性处理它。
-2147483648非常非常糟糕。这INT_MIN就是为了。
return 不是函数，不要 return (value)，只是 return value。
不要一直，在进入循环之前s[len - 1]最好减少。len或者，由于您len + 1只需要在malloc通话中，只需将其len作为intlen返回并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] = '\0';
        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]\0"
                } else {
                        ++s[l];
                }
        }

        return s;
}

主程序

#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

score 2 · Accepted Answer

你不需要那张支票。而是将其转换为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] = '\0';
    if (negative)
        s[0] = '-';
    do {
        s[--len] = (n % 10) + '0';
        n /= 10;
    } while(n);
    return (s);
}

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

score 0 · Accepted Answer

您的溢出预防机制可能存在问题。您尝试将xtype分配int给ntype long int。但是规范并不能保证该类型long int可以处理大的值范围int。更多信息可以在“Long Vs. Int”中找到。

如果您的编译器支持，请使用long long int类型。n将您的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也不是系统错误号之一。您需要在应用程序中添加更多日志记录，尤其是在由于某种原因无法调试它的情况下。检查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);
}

score 0 · Accepted Answer

潜在的代码失败，以怀疑的顺序：

ft_strdup()因为用“int min value”调用该代码并发生错误。
缺乏各种功能的原型。特别是ft_strdup()/strdup()。
调用/测试代码有问题。
“int min value”大于-2147483648。（更好用INT_MIN。）
ft_intlen(n)编码不正确并返回INT_MAX，然后代码尝试malloc(INT_MIN)。
int/long都是 64 位的。这使第一个s[len - 1] = (n % 10) + '0';与INT_MIN.

否则，如果INT_MIN值为 -2147483648，ft_itoa(int x)则很好。

OP 断言“... strdup 只分配字符串，ft_intlen 只返回字符串的长度，两者都通过了测试用例 – franklinexpress 10 月 8 日 7:52”

通过测试用例并不意味着它在不调用未定义行为的情况下工作。最好发布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)) + \0
#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 = '\0';

  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); 
}

score 0 · Accepted Answer

您提供的这段代码在 OsX 上编译和工作，但使用我自己的ft_stdup和ft_intlen. 因此，您可以向我们展示代码或检查它们是否有错误。我做了一些测试（包括2147483647，-2147483648）。它工作得很好。

无论如何，这些行：

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

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

碰巧在 OsX 上它也适用于long值，但这是非便携式安全的。

score 0 · Accepted Answer

只需使用：

INT_MIN

代替：

-2147483648

在你的测试中：

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

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

标准 C 库limits.h通常将其定义为：

#define INT_MIN  (-INT_MAX - 1)

以避免这个问题。

c - itoa() c 实现 int min 下溢

7 回答 7

Related

Reference