当用常数编译除法或模时，我的编译器（LLVM GCC）生成一系列我不理解的指令。

编译以下最小示例时：

int mod7(int x) {
    return x % 7;
}

int div7(int x) {
    return x / 7;
}


生成以下代码：
将组装返回到C的最简单方法是什么（对于右侧的任意常数）？
反编译器或分析反汇编器之类的工具如何使该过程自动化？ ？


评论

有时称为倒数乘法。这是简短的解释，并提供了指向更详细资源的链接。我见过Hex-Ray可以毫无问题地消化它。

#1 楼

首先

不幸的是，我们似乎没有在此stackexchange中打开MathJax，因此下面的数学部分格式相当糟糕。我距离数学家也很远，所以在某些地方可能会用不上这个符号。

了解魔术数字和代码

上面代码的目的是重写一个由于除法比乘法要花更多的时钟周期，所以除法成乘法。它的周期大约是两倍，取决于CPU。因此，我们需要找到一种不错的无分支方式。如果我们分支，则很可能会因为简单地进行除法而失败。

一种方法是简单地意识到除法与与数字倒数即的乘法相同。问题在于是一个非常差的数字，无法存储为整数。因此，我们需要将除数和除数都乘以一个数。由于我们在32位数字上运算，并且在64位数字上获得乘法结果，因此使用可获得最佳精度，并且还避免了溢出问题。所以我们基本上得到。现在，小数部分是导致我们出现问题的原因，因为它会导致舍入错误。

所以让我们尝试将其形式化：



是我们的被乘数，例如或任何数量的，但与我们的寄存器大小非常匹配，因为我们可以简单地丢弃较低的32位寄存器。 是必须添加的数字，以使被整除。 是我们希望除的数。

我们可以重写上面的方程，如



这说明了我们的观点股息除以我们的除数，然后除以误差因子。

研究我们的原始方程，很明显，我们影响很小。 必须为2的幂，不能太大，否则我们有溢出风险，也不能太小，因为它对我们的误差因子有直接的负面影响。 直接取决于和。因此，让我们尝试，它给出的最大误差率，的最大值为，因此不幸的是，它不少于，所以我们可以舍入错误。

将的指数增加到，得到，最大误差率小于。这意味着我们的被乘数是，它不小于或等于我们可以存储在32位寄存器（）中的最大有符号值。因此，我们改为制作被乘数。附带说明一下，由于二进制补码的神奇之处，当我们减去时，数字为，当被解释为无符号数时为。但是我们在这里做有符号算术。因此，我们需要通过添加来修复最终表达式。这也只解决了的问题，对于负数，我们将减1，因此如果我们有负数，则需要加1。

这就是乘法常数的解释以及如何到达它。现在让我们看一下代码：

; Load -1840700269
mov    ecx,0x92492493

; Load n
mov    eax,edi

; n * -1840700269
imul   ecx

; add n to compensate for 2^32 subtraction
add    edx,edi

; check the sign bit of our result
mov    ecx,edx
shr    ecx,0x1f

; divide by 2^2 to compensate for us using y=2^34 instead of 2^32
sar    edx,0x2

mov    eax,edx
; add the value of the sign bit to the final result
add    eax,ecx


从幻数和代码计算除数

我还没有数学上证明这一点，但是如果你想从组装转储（如您所示的转储）中恢复除数，我们可以做一些简单的心理练习。首先，我们需要认识到以下条件成立



其中是我们为了将值带入32位值范围而进行的调整。根据代码，我们可以设计出以下内容，即右移两位意味着，，，未知。这意味着我们缺少一个变量来执行完美的解决方案。但是，的影响（如果可以忽略不计）的目的是使除数尽可能接近其整数值。这意味着可以通过求解





来找到解决方案，另一个例子是除数31337，其被乘数为幻数140346763，右边为移位10位。



最后

有关其工作原理的完整数学分解，包括所有适当的证明和算法来计算魔术数字，移位和加法，请参阅《黑客的喜悦》，第10-3章。

评论

问题不仅在于如何计算魔术常数，还在于如何获得除数。

–伊戈尔·斯科钦斯基♦
2013年3月31日12:36


我试图回答。确实没有时间制定证明，所以我不是100％确信它是正确的。

–彼得·安德森（Peter Andersson）
13年3月31日在20:01
在逆向工程的假设下（如果将const除法/模乘与其他运算混合在一起），则可以将整数乘法常数转换为二进制分数，其倒数与除法/模常数运算数有关，直至未知2乘幂的幂。由于与其他操作的混合和优化，有时无法推断2因子的未知幂。

–rwong
15年11月24日在12:59
仅供参考：堆栈交换应用程序的答案看起来不错，因为它为每个站点打开了mathjax

– Ferrybig
17年2月4日在10:00

#2 楼

这是迟来的回应。 Reko反编译器通过使用中位数执行除数和征服搜索来恢复整数除数。

Reko通过识别使用64位乘积的高位字（r * c）的模式开始。常数乘数c被2 ^ 32除以产生介于0.0和1.0之间的双精度浮点数。从有理数0/0和1/1开始，Reko计算一系列中位数，该中位数将浮点数括起来。从此中位数序列中，它选择最接近浮点数的有理数并返回它。

该代码尚未经过充分测试-我还没有机会使用负数数字尚未，但似乎给出了合理的结果。如果您好奇的话，这里的代码是：https://github.com/uxmal/reko/blob/master/src/Decompiler/Analysis/ConstDivisionImplementedByMultiplication.cs

#3 楼

本文可能很有趣：用不变乘法进行除法。

在这里加入。