整数溢出的处理方式
在做pwnable.kr的horcruxes时候，遇到整数溢出的问题，导致脚本不稳定。
这里打算写一下计算机处理整数溢出的方法，以及以后写脚本如何处理溢出。也研究一下一些算法的原理。
计算机组成基础
本来想从数学原理，原码、反码、补码详细阐述，并且加上数学证明。没想到知乎大佬写得太棒了。甚至没有什么可删减的，我全部复制也没什么意义。
把链接放在这里，作为前置知识，本篇就只讲代码手动处理溢出的方式与原理。
二进制的原码、反码、补码——狂风吹我心：这些码产生的原因，以及如何运算，举例丰富。
一文读懂二进制补码 - 从计数原理开始说起 ——红色的红：完整的数学证明，各种情况的举例证明，非常详细的论证。
计算机中均采用补码进行加减运算，有符号整数溢出，采用补码 $2^{32}$ 回绕的方式。
简单原理
补码的字面是无符号的，只不过我们把左起第一位比特定义为符号位 无符号范围：0 ~ 4294967295，有符号范围：-2147483648 ~ 2147483647
1
2
0x00000000 ~ 0x7FFFFFFF => 0 到 2147483647
0x80000000 ~ 0xFFFFFFFF => 负数
正数很明显是和补码字面对应的，无需操作，而要处理的就是负数。 后半段被映射成负数：
| 二进制 | 无符号 | 有符号 | | :——–: | :——–: | :———: | | 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <limits.h>
int main() {
int a = INT_MAX;
int b = INT_MIN;
int c = 9993111111111; // int型 默认就是32位的
printf("%d\n", a + 1);
printf("%d\n", b - 1);
printf("%d\n", c);
char str[20];
strcpy(str, "9993111111111");
int val = atoi(str);
printf("%d\n", val);
}
输出
1
2
3
4
-2147483648
2147483647
-1277786681
-1277786681
Python
由于Python是无限精度，导致机器计算出具体值后，与程序存的值不一致，因为程序存的是溢出后的。这里写一下手动把值转换成32位溢出情况下的值。
Python有三种方式处理溢出：
1、ctypes自动处理：
1
2
3
4
5
6
7
8
import ctypes
arr = 9993111111111
res = ctypes.c_int32(arr).value
print(res)
# 输出：-1277786681
2、位运算（最快）
1
2
3
4
5
6
7
arr = 9993111111111
res = arr & 0xFFFFFFFF # 截断
if res > 0x7FFFFFFF: # 判断正负
res -= 0x100000000 # 减去2^32
print(res)
# 输出：-1277786681
3、区间折叠
1
2
3
4
5
arr = 9993111111111
res = ((arr + 2**31) % 2**32) - 2**31
print(res)
# 输出：-1277786681
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]$，于是得到了有符号整数