模（％）的GCC实现如何工作，为什么不使用div指令？

Question

我想解决如何在程序集中计算模10，所以我在gcc中编译了下面的c代码，看看它出现了什么。

unsigned int i=999; 
unsigned int j=i%10; 

令我惊讶我

movl -4(%ebp), %ecx 
movl $-858993459, %edx 
movl %ecx, %eax 
mull %edx 
shrl $3, %edx 
movl %edx, %eax 
sall $2, %eax 
addl %edx, %eax 
addl %eax, %eax 
movl %ecx, %edx 
subl %eax, %edx 
movl %edx, %eax 
movl %eax, -12(%ebp) 

凡-4（％EBP）或 “I” 是输入和-12（％EBP）或 “J” 就是答案。我已经测试过这个功能，无论你编号为-4（％ebp），它都能正常工作。

我的问题是这个代码是如何工作的，它怎么比使用div操作数更好。

Answer 1

第二个问题第一个问题：div是一个非常慢的指令（超过20个时钟周期）。上面的顺序包含更多指令，但它们都相对较快，所以它在速度方面是一个净赢。

前五条指令（包括shrl）计算i/10（我会在一分钟内解释它的含义）。

接下来的几条指令再次将结果乘以10，但是避免了指令的执行（无论这是否胜利取决于您所选择的确切处理器 - 新的x86具有非常快的乘法器，但是较老的别）。

movl %edx, %eax ; eax=i/10 
sall $2, %eax  ; eax=(i/10)*4 
addl %edx, %eax ; eax=(i/10)*4 + (i/10) = (i/10)*5 
addl %eax, %eax ; eax=(i/10)*5*2 = (i/10)*10 

这然后从i减去再次获得i - (i/10)*10其是i % 10（无符号数）。

最后，在i/10的计算上：基本思想是用1/10乘以10来代替除法。编译器通过乘以（2 ** 35/10 + 1）进行定点逼近 - 这就是加载到edx中的魔法值，虽然它是作为有符号值输出的，尽管它实际上是无符号的 - 并且右移结果为35.这就证明为所有32位整数提供正确的结果。

有算法来确定这种近似的，其保证误差小于1（为整数意味着它是正确的值），GCC明显使用一个:)

最后一句话：如果你想实际请参阅GCC计算一个模，制作除数变量（例如函数参数），以便它不能进行这种优化。无论如何，在x86上，你使用div来计算模数。 div预计在edx:eax（edx中的高32位，eax中的低32位 - 如果使用32位数字清除edx为零）并将其除以您指定的任何操作数（例如，div ebx除以edx:eaxebx）。它返回eax中的商数和其余的edx。 idiv对签名值也是一样。

Answer 2

第一部分，最大为shrl $3, %edx，实现了10的快速整数除法。有几种不同的算法可用于预先知道您分割的数量。请注意，858993459是“0.2 * 2^32”。这样做的原因是因为即使指令集中存在整数除法指令div/idiv，它通常非常慢，比乘法慢数倍。

第二部分通过将除法结果乘以10（以间接方式，通过移位和相加;大概编译器认为它会更快），然后从原始数字中减去余数来计算余数。