atoi函数的实现二: 测试各实现的正确性

相关文章:

linux内核的atoi测试

v_JULY_v君的问题非常好(请见文章的评论)! 每次都让我思考. 现将linux内核的atoi测试代码贴出来, 为了区别了C标准库的atoi函数, 我把测试的函数名改为matoi:

  1. #include 
  2. #include 
  3. #include 
  4.  
  5. /*http://lxr.free-electrons.com/source/lib/kstrtox.h#L4*/
  6. #define KSTRTOX_OVERFLOW        (1U << 31)
  7. const char *_parse_integer_fixup_radix(const char *s, unsigned int *base);
  8. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *res);
  9.  
  10. /*http://lxr.free-electrons.com/source/arch/powerpc/boot/types.h#L12*/
  11. typedef int                     s32;
  12. typedef unsigned int            u32;
  13. typedef unsigned long long      u64;
  14.  
  15. /*http://lxr.free-electrons.com/source/drivers/media/pci/ngene/ngene-dvb.c#L127*/
  16. static u32 overflow;
  17.  
  18. /*http://lxr.free-electrons.com/source/include/linux/kernel.h#L29*/
  19. #define ULLONG_MAX      (~0ULL)
  20.  
  21. #define unlikely(cond) (cond)
  22.  
  23. /*http://lxr.free-electrons.com/source/lib/kstrtox.c#L23*/
  24. const char *_parse_integer_fixup_radix(const char *s, unsigned int *base)
  25. {
  26.         if (*base == 0) {
  27.                 if (s[0] == '0') {
  28.                         if (_tolower(s[1]) == 'x' && isxdigit(s[2]))
  29.                                 *base = 16;
  30.                         else
  31.                                 *base = 8;
  32.                 } else
  33.                         *base = 10;
  34.         }
  35.         if (*base == 16 && s[0] == '0' && _tolower(s[1]) == 'x')
  36.                 s += 2;
  37.         return s;
  38. }
  39.  
  40. /*http://lxr.free-electrons.com/source/lib/kstrtox.c#L47*/
  41. /*
  42.  * Convert non-negative integer string representation in explicitly given radix
  43.  * to an integer.
  44.  * Return number of characters consumed maybe or-ed with overflow bit.
  45.  * If overflow occurs, result integer (incorrect) is still returned.
  46.  *
  47.  * Don't you dare use this function.
  48.  */
  49. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *p)
  50. {
  51.         unsigned long long res;
  52.         unsigned int rv;
  53.         int overflow;
  54.  
  55.         res = 0;
  56.         rv = 0;
  57.         overflow = 0;
  58.         while (*s) {
  59.                 unsigned int val;
  60.  
  61.                 if ('0' <= *s && *s <= '9')
  62.                         val = *s - '0';
  63.                 else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
  64.                         val = _tolower(*s) - 'a' + 10;
  65.                 else
  66.                         break;
  67.  
  68.                 if (val >= base)
  69.                         break;
  70.                 /*
  71.                  * Check for overflow only if we are within range of
  72.                  * it in the max base we support (16)
  73.                  */
  74.                 if (unlikely(res & (~0ull << 60))) {
  75.                         if (res > ULLONG_MAX - val/base)
  76.                                 overflow = 1;
  77.                 }
  78.                 res = res * base + val;
  79.                 rv++;
  80.                 s++;
  81.         }
  82.         *p = res;
  83.         if (overflow)
  84.                 rv |= KSTRTOX_OVERFLOW;
  85.         return rv;
  86. }
  87.  
  88. /*http://lxr.free-electrons.com/source/lib/vsprintf.c#L44*/
  89. /**
  90.  * simple_strtoull - convert a string to an unsigned long long
  91.  * @cp: The start of the string
  92.  * @endp: A pointer to the end of the parsed string will be placed here
  93.  * @base: The number base to use
  94.  *
  95.  * This function is obsolete. Please use kstrtoull instead.
  96.  */
  97. unsigned long long simple_strtoull(const char *cp, char **endp, unsigned int base)
  98. {
  99.         unsigned long long result;
  100.         unsigned int rv;
  101.  
  102.         cp = _parse_integer_fixup_radix(cp, &base);
  103.         rv = _parse_integer(cp, base, &result);
  104.         /* FIXME */
  105.         cp += (rv & ~KSTRTOX_OVERFLOW);
  106.  
  107.         if (endp)
  108.                 *endp = (char *)cp;
  109.  
  110.         return result;
  111. }
  112.  
  113. /*http://lxr.free-electrons.com/source/lib/vsprintf.c#L83*/
  114. /**
  115.  * simple_strtoul - convert a string to an unsigned long
  116.  * @cp: The start of the string
  117.  * @endp: A pointer to the end of the parsed string will be placed here
  118.  * @base: The number base to use
  119.  *
  120.  * This function is obsolete. Please use kstrtoul instead.
  121.  */
  122. unsigned long simple_strtoul(const char *cp, char **endp, unsigned int base)
  123. {
  124.         return simple_strtoull(cp, endp, base);
  125. }
  126.  
  127. /*http://lxr.free-electrons.com/source/drivers/staging/tidspbridge/rmgr/dbdcd.c#L950*/
  128. /*
  129.  *  ======== atoi ========
  130.  *  Purpose:
  131.  *      This function converts strings in decimal or hex format to integers.
  132.  */
  133. static s32 matoi(const char *psz_buf)
  134. {
  135.         char *pch = psz_buf;
  136.         s32 base = 0;
  137.  
  138.         while (isspace(*pch))
  139.                 pch++;
  140.  
  141.         if (*pch == '-' || *pch == '+') {
  142.                 base = 10;
  143.                 pch++;
  144.         } else if (*pch && tolower(pch[strlen(pch) - 1]) == 'h') {
  145.                 base = 16;
  146.         }
  147.  
  148.         return simple_strtoul(pch, NULL, base);
  149. }
  150.  
  151. void test(const char* str) {
  152.     printf("%s : %d\n", str, matoi(str));
  153. }
  154.  
  155. int main() {
  156.     test("2147483647");
  157.     test("2147483648");
  158.     test("-2147483648");
  159.     test("-2147483649");
  160.     test("10522545459");
  161.     test("-10522545459");
  162.  
  163.     return 0;
  164. }

修改的地方在第75行, 原来的代码为:

if (res > div_u64(ULLONG_MAX - val, base))

而div_u64调用的div_u64_rem函数中包含汇编代码编译不过(原因尚未可知, 有待进一步研究), 所以我把这段程序去掉了.

程序的输出结果(很显然, 对于溢出的情况, 程序没有处理):

2147483647 : 2147483647
2147483648 : -2147483648
10522545459 : 1932610867
-2147483648 : -2147483648
-2147483649 : -2147483647
-10522545459 : 1932610867

Nut/OS的atoi测试

以下是测试代码(在ubuntu 10.4.1, gcc 4.4.3上编译通过, 为了区别于C标准库的函数, 函数名strtol更改为mstrtol, atoi更改为matoi2):

  1. #include 
  2. #include 
  3. #include 
  4. #include 
  5.  
  6. #define CONST      const
  7.  
  8. long mstrtol(CONST char *nptr, char **endptr, int base)
  9. {
  10.     register CONST char *s;
  11.     register long acc, cutoff;
  12.     register int c;
  13.     register int neg, any, cutlim;
  14.  
  15.     /*
  16.      * Skip white space and pick up leading +/- sign if any.
  17.      * If base is 0, allow 0x for hex and 0 for octal, else
  18.      * assume decimal; if base is already 16, allow 0x.
  19.      */
  20.     s = nptr;
  21.     do {
  22.         c = (unsigned char) *s++;
  23.     } while (isspace(c));
  24.     if (c == '-') {
  25.         neg = 1;
  26.         c = *s++;
  27.     } else {
  28.         neg = 0;
  29.         if (c == '+')
  30.             c = *s++;
  31.     }
  32.     if ((base == 0 || base == 16) && c == '0' && (*s == 'x' || *s == 'X')) {
  33.         c = s[1];
  34.         s += 2;
  35.         base = 16;
  36.     }
  37.     if (base == 0)
  38.         base = c == '0' ? 8 : 10;
  39.  
  40.     /*
  41.      * Compute the cutoff value between legal numbers and illegal
  42.      * numbers.  That is the largest legal value, divided by the
  43.      * base.  An input number that is greater than this value, if
  44.      * followed by a legal input character, is too big.  One that
  45.      * is equal to this value may be valid or not; the limit
  46.      * between valid and invalid numbers is then based on the last
  47.      * digit.  For instance, if the range for longs is
  48.      * [-2147483648..2147483647] and the input base is 10,
  49.      * cutoff will be set to 214748364 and cutlim to either
  50.      * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
  51.      * a value > 214748364, or equal but the next digit is > 7 (or 8),
  52.      * the number is too big, and we will return a range error.
  53.      *
  54.      * Set any if any `digits' consumed; make it negative to indicate
  55.      * overflow.
  56.      */
  57.     cutoff = neg ? LONG_MIN : LONG_MAX;
  58.     cutlim = cutoff % base;
  59.     cutoff /= base;
  60.     if (neg) {
  61.         if (cutlim > 0) {
  62.             cutlim -= base;
  63.             cutoff += 1;
  64.         }
  65.         cutlim = -cutlim;
  66.     }
  67.     for (acc = 0, any = 0;; c = (unsigned char) *s++) {
  68.         if (isdigit(c))
  69.             c -= '0';
  70.         else if (isalpha(c))
  71.             c -= isupper(c) ? 'A' - 10 : 'a' - 10;
  72.         else
  73.             break;
  74.         if (c >= base)
  75.             break;
  76.         if (any < 0)
  77.             continue;
  78.         if (neg) {
  79.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {
  80.                 any = -1;
  81.                 acc = LONG_MIN;
  82.                 errno = ERANGE;
  83.             } else {
  84.                 any = 1;
  85.                 acc *= base;
  86.                 acc -= c;
  87.             }
  88.         } else {
  89.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {
  90.                 any = -1;
  91.                 acc = LONG_MAX;
  92.                 errno = ERANGE;
  93.             } else {
  94.                 any = 1;
  95.                 acc *= base;
  96.                 acc += c;
  97.             }
  98.         }
  99.     }
  100.     if (endptr != 0)
  101.         *endptr = (char *) (any ? s - 1 : nptr);
  102.     return (acc);
  103. }
  104.  
  105. int matoi2(CONST char *str)
  106. {
  107.     return ((int) mstrtol(str, (char **) NULL, 10));
  108. }
  109.  
  110. int mgetline(char* buf, size_t n) {
  111.   size_t idx = 0;
  112.   int c;
  113.   
  114.   while (--n > 0 && (c = getchar()) != EOF && c != '\n') {
  115.     buf[idx++] = c;
  116.   }
  117.   buf[idx] = '\0';
  118.   return idx;
  119. }
  120.  
  121. #define MAX_LINE 200
  122.  
  123. int main() {
  124.     char buf[MAX_LINE];
  125.     while (mgetline(buf, MAX_LINE) >= 0) {
  126.         if (strcmp(buf, "quit") == 0) break;
  127.         printf("matoi2=%d\n", matoi2(buf));
  128.     }
  129.     return 0;
  130. }

程序的测试结果:

10522545459
matoi2=2147483647
-10522545459
matoi2=-2147483648

程序貌似对溢出的处理是正确的, 真的吗? 请注意代码的第79和第89行. 现在我把测试数据换成"10522545454", 与"10522545459"区别在于最后一个字符.

10522545454
matoi2=1932610862
-10522545454
matoi2=-1932610862

bingo! 正中下怀! 对于字串"10522545454", 在读取最后的数字字符'4'时, 整数1052254545已经大于2147483647/10了, 说明已经溢出, 不应该再判断字串的最后一位4是否大于2147483647%10, 所以第79行应该改为(89行修改方法类似):

            if (acc < cutoff || (acc == cutoff && c > cutlim)) {

修改过后的代码测试正常:

10522545459
matoi2=2147483647
-10522545459\
matoi2=-2147483648
10522545454
matoi2=2147483647
-10522545454
matoi2=-2147483648
quit

关于此bug, 我已经邮件通知En-Nut-Discussion.

以下为邮件回复的截图, Uwe Bonnes说: 可以打个补丁到分支. 不过他把单词reasonable给拼错了.


References:

Linux Cross Reference

Nut/OS API

文章知识点与官方知识档案匹配，可进一步学习相关知识
C技能树函数与程序结构函数的声明与定义156665 人正在系统学习中
注：本文转载自blog.csdn.net的MJN的文章"http://blog.csdn.net/njnu_mjn/article/details/9104143"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！