整数溢出的处理方式 • Hack Your Heart

在做 pwnable.kr 的 horcruxes 时候，遇到整数溢出的问题，导致脚本不稳定。这里打算写一下计算机处理整数溢出的方法，以及以后写脚本如何处理溢出。也研究一下一些算法的原理。

计算机组成基础#

本来想从数学原理，原码、反码、补码详细阐述，并且加上数学证明。没想到知乎大佬写得太棒了。甚至没有什么可删减的，我全部复制也没什么意义。把链接放在这里，作为前置知识，本篇就只讲代码手动处理溢出的方式与原理。

二进制的原码、反码、补码——狂风吹我心 ↗ ：这些码产生的原因，以及如何运算，举例丰富。一文读懂二进制补码 - 从计数原理开始说起 ——红色的红 ↗ ：完整的数学证明，各种情况的举例证明，非常详细的论证。

计算机中均采用补码进行加减运算，有符号整数溢出，采用补码 $2^{32}$ 回绕的方式。

简单原理#

补码的字面是无符号的，只不过我们把左起第一位比特定义为符号位无符号范围：0 ~ 4294967295，有符号范围：-2147483648 ~ 2147483647

10x00000000 ~ 0x7FFFFFFF  => 0 到 2147483647
20x80000000 ~ 0xFFFFFFFF  => 负数

text

正数很明显是和补码字面对应的，无需操作，而要处理的就是负数。后半段被映射成负数：

补码字面（HEX表达）	无符号	有符号
0x7FFFFFFF	2147483647	2147483647
0x80000000	2147483648	-2147483648
0xFFFFFFFF	4294967295	-1

规则就是：如果值 >= $2^{31}$ ，有符号值 = 无符号值 - $2^{32}$

后面的例子都用9993111111111和9992111111111来解释。首先太长了需要先截断到32位再进行回绕。

例子	HEX	截断后HEX	截断后BIN	正负
9993111111111	0x916b3d685c7	0xb3d685c7	10110011110101101000010111000111	负
9992111111111	0x916783bbbc7	0x783bbbc7	01111000001110111011101111000111	正

所以我们要求有符号值，上面例子中：负数 = 0xb3d685c7 - $2^{32}$ = -1277786681 正数在有效范围内，保留。

代码处理#

C语言#

C语言是固定长度寄存器运算的，对于无符号整数天然就有截断，天然回绕，要注意的是有符号整数：

 1#include <stdio.h>
 2#include <limits.h>
 3
 4int main() {
 5    int a = INT_MAX;
 6    int b = INT_MIN;
 7    int c = 9993111111111; // int型 默认就是32位的
 8
 9    printf("%d\n", a + 1);
10    printf("%d\n", b - 1);
11    printf("%d\n", c);
12    
13    char str[20];
14    strcpy(str, "9993111111111");
15    int val = atoi(str);
16    printf("%d\n", val);
17}

输出

1-2147483648
22147483647
3-1277786681
4-1277786681

text

Python#

由于Python是无限精度，导致机器计算出具体值后，与程序存的值不一致，因为程序存的是溢出后的。这里写一下手动把值转换成32位溢出情况下的值。

Python有三种方式处理溢出：

1、ctypes自动处理：#

1
2import ctypes
3
4arr = 9993111111111
5res = ctypes.c_int32(arr).value
6print(res)
7
8# 输出：-1277786681

python

2、位运算（最快）#

1arr = 9993111111111
2res = arr & 0xFFFFFFFF # 截断
3if res > 0x7FFFFFFF: # 判断正负
4    res -= 0x100000000 # 减去2^32
5print(res)
6
7# 输出：-1277786681

python

3、区间折叠#

1arr = 9993111111111
2res = ((arr + 2**31) % 2**32) - 2**31
3print(res)
4
5# 输出：-1277786681

python

32位有符号范围是 $[-2^{31}, 2^{31}-1]$ ，即[-2147483648, 2147483647] 但 % 2**32 的结果范围是： $[0, 2^{32}-1]$ ，也就是无符号范围。怎么把无符号区间重新“折叠”回有符号区间？

整体右移 $2^{31}$ ，原本 $[-2^{31}, 2^{31}-1]$ 变成 $[0, 2^{32}-1]$ ，这样两区间就对齐了。
取模，通过% 2**32强制限制在 $[0, 2^{32}-1]$ ，做这一步是因为代码里没有截断，等价于保留低 32 位，如果有截断，就不需要这一步。
再平移回来，通过 $- 2^{31}$ ，把区间平移回： $[-2^{31}, 2^{31}-1]$ ，于是得到了有符号整数