Loading... # 一、起因 在反汇编查看某个程序时，被其中出现的一个`magic number`所困扰，然后使用IDA的F5插件分析的代码也具有一定欺骗性，就有了这篇文章。 反汇编代码： ```反汇编代码 .text:0000000000406C4E mov r13d, 1374389535 //magic number: 1374389535 .text:0000000000406C5F mov eax, ebx .text:0000000000406C61 mul r13d .text:0000000000406C64 shr edx, 5 .text:0000000000406C67 imul edx, 64h ; 'd' .text:0000000000406C6A cmp ebx, edx ``` IDA的F5插件分析结果： ```c/c++ i == 100 * (i / 100) ``` # 二、问题转化 因为`imul edx, 64h `就是`c`代码中的`100 *`。 因此，问题就转化为了： `i/100`与 ```反汇编 .text:0000000000406C4E mov r13d, 1374389535 //magic number: 1374389535 .text:0000000000406C5F mov eax, ebx .text:0000000000406C61 mul r13d .text:0000000000406C64 shr edx, 5 ``` 的等价，原因何在。 # 三、分析 > 说明：本文讨论对象均为正整数，0和负数不在本文讨论范围内。 ### 1.参考资料 * [C++求余用的“%”有与它效率相同的其它算法吗？](https://www.zhihu.com/question/22747596) * [Labor of Division (Episode I)](https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html) ### 2.试验环境 * 编译工具-1：Visual Studio Community 2019，版本16.9.3 * 编译工具-2：g++ (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609 * 编译选项：-O2 * 体系架构：x64 ### 3.理论分析（成功把自己绕晕~） 对于给定的正整数`d`和正整数变量`n`，满足如下等式变化： $\frac{n}{d}=\frac{n}{d}\times\frac{2^k}{2^k}=\frac{2^k}{d}\times\frac{n}{2^k}$ 令：$m_{exact} = \frac{2^k}{d}$ 有：$\frac{n}{d}=m_{exact}\times\frac{n}{2^k}$ 此时，就将除法运算，转化为了乘法以及位运算，这正是我们所需要的。 因$d$是确定的值，$m_{exact}$的大小，就只与$k$有关了。 令$m_{exact}=\frac{2^k}{d}=f+\frac{e}{d} $，其中，$f$为正整数，$e$满足$0\le e \le d$。 有$\frac{e}{d}<1$。 当$k$足够大的时候，必然有：$\frac{e}{d}\times\frac{n}{2^k}<\frac{1}{d}$， 从而，$\frac{n}{2^k}<\frac{1}{d}$。 对于32位正整数计算，也就是$n\le 2^{32}$，也就是$\frac{2^{32}}{2^k}<\frac{1}{d}$ => $k>d*2^{32}$。 等式两边取$log_2$，有$k>32+log_2d$。 $k=\lceil 32+log_2d\rceil$ 实际验证发现，该$k$值，依旧过大，还需要使得$k$满足：$\frac{2^k}{d}<2^{32}$。 ### 4.验证 Visual Studio Community 2019上测试发现： 当 $d=13$时，$k=34=32+log_28-1$，此时 magic number：$m=2^{32}\div 13=1321528399$ 当$d=33$时，$k=35=32+log_2{32}-2$，此时 magic number：$m=2^{35}\div33=1041204193$ 当$d=266$时，$k=40=32+log_2{256}$，此时 magic number：$m=2^{40}\div266=4133502361$ # 四、当成功把自己搞迷糊以后 上述的分析，和实际上编译器优化的结果，并不是那么吻合。 于是又开始了资料查找... 在[【编译笔记】变量除以常量的优化（一）——无符号除法](https://zhuanlan.zhihu.com/p/151038723)这篇文章中，发现了更细致，更深入的分析： ##### 1.乘法指令介绍 对于 x86 指令集来说： * `mul r/m32`：计算 `eax` 和 `r/m32` 进行无符号乘法的结果，将低32位存入 `eax`，高32位存入 `edx`。 * `imul r/m32`：计算 `eax` 和 `r/m32` 进行有符号乘法的结果，将低32位存入 `eax`，高32位存入 `edx`。 对于 ARM 指令集来说： * `umull RdLo, RdHi, Rm, Rs`：计算 `Rm` 和 `Rs` 进行无符号乘法的结果，将低32位存入 `RdLo`，高32位存入 `RdHi`。 * `smmul Rd, Rm, Rs`：计算 `Rm` 和 `Rs` 进行有符号乘法的结果，将高32位存入 `Rd`。 也就是可以用以下两个函数代表计算过程： ```c/c++ Uint32 muluh(Uint32 a, Uint32 b) { return (Uint64(a) * b) >> 32; } Int32 mulsh(Int32 a, Int32 b) { return (Int64(a) * b) >> 32; } ``` 我们的目标是将 `n / d` 优化为 `muluh(n, m) >> l`，写成数学表达式就是 ![[公式]](https://www.zhihu.com/equation?tex=%5Clfloor+n+%2F+d+%5Crfloor+%3D+%5Clfloor+n+%5Ccdot+m+%2F+2%5E%7BN%2Bl%7D+%5Crfloor) 。 那么，我们应该如何通过 ![[公式]](https://www.zhihu.com/equation?tex=d) 计算出 ![[公式]](https://www.zhihu.com/equation?tex=m) 和 ![[公式]](https://www.zhihu.com/equation?tex=l) 呢？ **定理1** 设 ![[公式]](https://www.zhihu.com/equation?tex=m)，![[公式]](https://www.zhihu.com/equation?tex=d)，![[公式]](https://www.zhihu.com/equation?tex=l) 是非负整数，![[公式]](https://www.zhihu.com/equation?tex=d+%5Cne+0)，且满足 ![[公式]](https://www.zhihu.com/equation?tex=2%5E%7BN%2Bl%7D+%5Cle+m+%5Ccdot+d+%5Cle+2%5E%7BN%2Bl%7D+%2B+2%5El)，则对于 ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+n+%3C+2%5EN) 的所有整数 ![[公式]](https://www.zhihu.com/equation?tex=n)，有 ![[公式]](https://www.zhihu.com/equation?tex=%5Clfloor+n+%2F+d+%5Crfloor+%3D+%5Clfloor+n+%5Ccdot+m+%2F+2%5E%7BN+%2B+l%7D+%5Crfloor)。 **证明** 设 ![[公式]](https://www.zhihu.com/equation?tex=k+%3D+m+%5Ccdot+d+-+2%5E%7BN%2Bl%7D)，则由题设可得 ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+k+%5Cle+2%5El)。 对于 ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+n+%3C+2%5EN)，我们可以将 ![[公式]](https://www.zhihu.com/equation?tex=n) 写成 ![[公式]](https://www.zhihu.com/equation?tex=n+%3D+q+%5Ccdot+d+%2B+r) 的形式，其中 ![[公式]](https://www.zhihu.com/equation?tex=q+%3D+%5Clfloor+n+%2F+d+%5Crfloor)， ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+r+%5Cle+d+-+1)。 也就是说，我们需要证明 ![[公式]](https://www.zhihu.com/equation?tex=q+%3D+%5Clfloor+n+%5Ccdot+m+%2F+2%5E%7BN%2Bl%7D+%5Crfloor)。 ![[公式]](https://www.zhihu.com/equation?tex=%5Cbegin%7Baligned%7D+%5Cfrac%7Bn+%5Ccdot+m%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%26%3D+%5Cfrac%7Bm+%5Ccdot+d%7D%7Bd%7D+%5Ccdot+%5Cfrac%7Bn%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%5C%5C+%26%3D+%5Cfrac%7Bk+%2B+2%5E%7BN%2Bl%7D%7D%7Bd%7D+%5Ccdot+%5Cfrac%7Bn%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%5C%5C+%26%3D+%5Cfrac%7Bk+%5Ccdot+n%7D%7Bd+%5Ccdot+2%5E%7BN%2Bl%7D%7D+%2B+%5Cfrac%7Bn%7D%7Bd%7D+-+%5Cfrac%7Bn-r%7D%7Bd%7D+%5C%5C+%26%3D+%5Cfrac%7Bk%7D%7B2%5El%7D+%5Ccdot+%5Cfrac%7Bn%7D%7B2%5EN%7D+%5Ccdot+%5Cfrac%7B1%7D%7Bd%7D+%2B+%5Cfrac%7Br%7D%7Bd%7D+%5Cend%7Baligned%7D) 因为 ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+k+%5Cle+2%5El)， ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+n+%3C+2%5EN)， ![[公式]](https://www.zhihu.com/equation?tex=0+%5Cle+r+%5Cle+d+-+1)，所以 ![[公式]](https://www.zhihu.com/equation?tex=%5Cbegin%7Baligned%7D+%5Cfrac%7B0%7D%7B2%5El%7D+%5Ccdot+%5Cfrac%7B0%7D%7B2%5EN%7D+%5Ccdot+%5Cfrac%7B1%7D%7Bd%7D+%2B+%5Cfrac%7B0%7D%7Bd%7D+%26%5Cle+%5Cfrac%7Bn+%5Ccdot+m%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%5Cle+%5Cfrac%7B2%5El%7D%7B2%5El%7D+%5Ccdot+%5Cfrac%7B2%5EN+-+1%7D%7B2%5EN%7D+%5Ccdot+%5Cfrac%7B1%7D%7Bd%7D+%2B+%5Cfrac%7Bd-1%7D%7Bd%7D+%5C%5C+0+%26%5Cle+%5Cfrac%7Bn+%5Ccdot+m%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%3C+%5Cfrac%7B1%7D%7Bd%7D+%2B+%5Cfrac%7Bd-1%7D%7Bd%7D+%5C%5C+0+%26%5Cle+%5Cfrac%7Bn+%5Ccdot+m%7D%7B2%5E%7BN%2Bl%7D%7D+-+q+%3C+1+%5Cend%7Baligned%7D) 所以 ![[公式]](https://www.zhihu.com/equation?tex=q+%3D+%5Clfloor+n+%5Ccdot+m+%2F+2%5E%7BN%2Bl%7D+%5Crfloor)，得证。 换而言之，![[公式]](https://www.zhihu.com/equation?tex=m) 的取值范围是 ![[公式]](https://www.zhihu.com/equation?tex=2%5E%7BN%2Bl%7D+%2F+d+%5Cle+m+%5Cle+%282%5E%7BN%2Bl%7D+%2B+2%5El%29+%2F+d)。 我们可以先令 ![[公式]](https://www.zhihu.com/equation?tex=l+%3D+%5Clceil+log_2+d+%5Crceil)，这样可以保证取值范围不为空，然后不断减小 ![[公式]](https://www.zhihu.com/equation?tex=l)，直到取值范围内只有一个整数。 这样可以使得 ![[公式]](https://www.zhihu.com/equation?tex=m) 尽量小，并且在少数情况下可以使得 ![[公式]](https://www.zhihu.com/equation?tex=l) 达到0，从而省略最后的移位。 ``` #include <cassert> #include <initializer_list> #include <iostream> using Uint32 = unsigned int; using Uint64 = unsigned long long; using Int32 = int; using Int64 = long long; inline int clz(Uint32 x) { return __builtin_clz(x); } inline int ctz(Uint32 x) { return __builtin_ctz(x); } Uint32 muluh(Uint32 a, Uint32 b) { return (Uint64(a) * b) >> 32; } Int32 mulsh(Int32 a, Int32 b) { return (Int64(a) * b) >> 32; } constexpr int N = 32; struct Multiplier { Uint64 m; int l; }; Multiplier chooseMultiplier(Uint32 d, int p) { assert(d != 0); assert(p >= 1 && p <= N); // l = ceil(log2(d)) int l = N - clz(d - 1); Uint64 low = (Uint64(1) << (N + l)) / d; Uint64 high = ((Uint64(1) << (N + l)) + (Uint64(1) << (N + l - p))) / d; while((low >> 1) < (high >> 1) && l > 0) low >>= 1, high >>= 1, --l; return {high, l}; } void generateUnsignedDivision(Uint32 d) { assert(d != 0); std::cout << "Uint32 div" << d << "(Uint32 n) {\n"; if(d >= (Uint32(1) << (N - 1))) { std::cout << " return n >= " << d << ";\n"; } else { int s = ctz(d); if(d == (Uint32(1) << s)) { std::cout << " return n"; if(s > 0) std::cout << " >> " << s; std::cout << ";\n"; } else { Multiplier multiplier = chooseMultiplier(d, N); if(multiplier.m < (Uint64(1) << N)) s = 0; else multiplier = chooseMultiplier(d >> s, N - s); if(multiplier.m < (Uint64(1) << N)) { std::cout << " return muluh(n"; if(s > 0) std::cout << " >> " << s; std::cout << ", " << multiplier.m << ")"; if(multiplier.l > 0) std::cout << " >> " << multiplier.l; std::cout << ";\n"; } else { std::cout << " Uint32 t = muluh(n, " << (multiplier.m - (Uint64(1) << N)) << ");\n"; std::cout << " return (((n - t) >> 1) + t) >> " << (multiplier.l - 1) << ";\n"; } } } std::cout << "}\n"; } int main() { for(Uint32 d : std::initializer_list<Uint32>{1, 3, 6, 7, 14, 31, 32, 641, 0x7FFFFFFF, 0x80000000}) generateUnsignedDivision(d); } ``` # 五、说明 第四章节内容，大幅摘抄了[【编译笔记】变量除以常量的优化（一）——无符号除法](https://zhuanlan.zhihu.com/p/151038723)的内容，若有侵权，还请告知。 谢谢！ 最后修改：2021 年 04 月 15 日 11 : 27 PM © 允许规范转载