模（％）的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（以間接方式，通過移位和相加;大概編譯器認爲它會更快），然後從原始數字中減去餘數來計算餘數。