Soru:
Sabit işlemlerle optimize edilmiş tamsayı bölmesini / moduloyu nasıl tersine çevirebilirim?
Dougall
2013-03-30 12:14:20 UTC
view on stackexchange narkive permalink

Bir bölümü veya moduloyu bir sabitle derlerken, derleyicim (LLVM GCC) anlamadığım bir dizi talimat üretir.

Aşağıdaki minimum örnekleri derlediğimde:

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

Aşağıdaki kod oluşturulur:

  _mod7: rbp mov rbp, rsp mov ecx, 0x92492493 mov eax, edi imul ecx add edx, edi mov eax, edx shr eax, 0x1f sar edx, 0x2 add edx, eax imul ecx, edx, 0x7 mov eax, edi sub eax, ecx pop rbp ret _div7: push rbp mov rbp, rsp mov ecx, 0x92492493 mov eax, edi imul ecx edx, edi mov ecx, edx shr ecx, 0x1 movf sar edx, 0x2 eax , edx add eax, ecx pop rbp ret  
  • Bu matematiksel olarak nasıl eşdeğerdir ve sabitler nereden gelir?
  • Çevirmenin en kolay yolu nedir montaj C'ye geri dönüyor (bir Sağ taraftaki rastgele sabitler)?
  • Derleyici veya analiz eden çözücü gibi bir araç bu süreci nasıl otomatikleştirebilir?
Bu bazen * karşılıklı çarpma * olarak adlandırılır. Daha ayrıntılı kaynaklara bağlantılar içeren [kısa açıklama] (http://www.nynaeve.net/?p=115) burada. Hex-Rays'in bunu sorunsuz bir şekilde sindirdiğini gördüm.
üç yanıtlar:
#1
+39
Peter Andersson
2013-03-31 14:26:13 UTC
view on stackexchange narkive permalink

First

Maalesef, bu yığın değişiminde MathJax'i açmış görünmüyoruz, bu yüzden aşağıdaki matematik bölümleri oldukça korkunç bir şekilde biçimlendirilmiş. Ben de bir matematikçi olmaktan uzağım, bu yüzden bazı yerlerde gösterim yanlış olabilir.

Sihirli sayı ve kodu anlamak

Yukarıdaki kodun amacı, bir bölümü yeniden yazmaktır. çarpma, çünkü bölme, çarpmadan daha fazla saat döngüsü gerektirir. İşlemciye çok bağlı olarak yaklaşık iki kat daha fazla döngü alanı içindedir. Bu yüzden bunu yapmanın güzel bir yolunu bulmalıyız. Dallanırsak, basitçe bölme yaparak kaybetme olasılığımız çok yüksektir.

Bir yol, bölmenin sayının tersiyle çarpma ile aynı şey, yani olduğunu fark etmektir. Sorun şu ki, bir tamsayı olarak saklamak için oldukça zayıf bir sayı. Bu yüzden hem bölen hem de bölüneni bir sayı ile çarpmamız gerekiyor. 32 bitlik sayılar üzerinde çalıştığımız ve çarpım sonuçlarını 64 bit sayılarla aldığımız için ile en iyi hassasiyeti elde ederiz ve ayrıca taşma sorunlarını da önleriz. Yani temelde elde ederiz. Şimdi bu kesirli kısım, yuvarlama hatalarına neden olacağı için sorunlara neden olan şeydir.

Öyleyse, bunu resmileştirmeye çalışalım:

bizim çarpanımızdır, örneğin veya gerçekten herhangi bir sayı , ancak kayıt boyutlarımızla çok iyi çalışır, çünkü daha düşük 32 bitlik kaydı atabiliriz. , 'in ile eşit olarak bölünebilmesi için eklemeniz gereken sayıdır. bölmek istediğimiz sayıdır.

Yukarıdaki denklemi şu şekilde yeniden yazabiliriz:

Bu, sahip olduğumuz noktayı gösterir temettü bölücümüze ve ardından hata faktörüne bölünür.

Orijinal denklemimizi inceleyerek çok az etkileyebileceğimiz açıktır. 'nin 2'nin gücü olması gerekir, çok büyük olamaz veya bir taşma riskini alırız ve hata faktörümüz üzerinde doğrudan olumsuz bir etkisi olduğu için çok küçük olamaz. doğrudan ve 'ye bağlıdır.

Öyleyse, maksimum hata kesri veren 'yi deneyelim ve maksimum değeri , yani , ne yazık ki bu ' den az değil, yuvarlama hataları.

üsünü olarak artıracağız, bu da , 'den küçük maksimum hata kesri verir. Bu, çarpanımızın 32 bitlik bir kayıtta () saklayabileceğimiz maksimum işaretli değerden küçük veya ona eşit olmayan olduğu anlamına gelir. Bu yüzden bunun yerine çarpım ve yaparız. Bir yan not olarak, çıkardığımızda ikinin tamamlayıcısının sihri sayesinde sayısı işaretsiz sayı olarak yorumlandığında olan olur. Ama burada imzalı aritmetik yapıyoruz. Bu yüzden son ifadeyi ekleyerek düzeltmemiz gerekiyor. Bu aynı zamanda için problemi de çözer, negatif sayılar için 1 kadardır, bu yüzden negatif bir sayımız varsa 1 eklememiz gerekir.

Bu, çarpmadaki sabitin açıklamasıdır ve nasıl ulaşılır. Şimdi koda bakalım:

 ; Load -1840700269mov ecx, 0x92492493; Yük nmov eax, edi; n * -1840700269imul ecx; 2 ^ 32 subtractionadd edx, edi'yi telafi etmek için n ekleyin; resultmov ecx, edxshr ecx, 0x1f'nin işaret bitini kontrol edin; 2 ^ 32sar edx, 0x2mov eax, edx yerine y = 2 ^ 34 kullanarak telafi etmek için 2 ^ 2'ye bölün; işaret bitinin değerini nihai sonuca ekle eax, ecx  

Sihirli sayı ve koddan bölen hesaplanıyor

Bunu matematiksel olarak kanıtlamadım, ancak isterseniz bölen kişiyi sizin gösterdiğiniz gibi bir montaj çöplüğünden kurtarmak için bazı basit zihinsel egzersizler yapabiliriz. Öncelikle aşağıdakilerin geçerli olduğunu anlamalıyız

, değeri 32 bitlik bir değer aralığına getirmek için yaptığımız ayarlamadır. Koddan aşağıdakini tasarlayabiliriz, iki yolla sağa kaydırma , , , bilinmemektedir. Bu, mükemmel bir çözüm gerçekleştirmek için bir değişkeni kaçırdığımız anlamına gelir. Bununla birlikte, 'nin amacı önemsiz ise, bölen kişiyi mümkün olduğunca tam sayı değerine yaklaştırmaktır. Bu, çözümün

Çarpımlı ve sihirli numarası 140346763 olan 31337 bölen ile başka bir örnek ve sağa 10 bit kaydırır.

Sonunda

Bunun nasıl çalıştığına dair tam bir matematiksel döküm için, tüm uygun ispatlar ve algoritmalar dahil sihirli sayılar, kaydırmalar ve ekler, bkz. Hacker's Delight, 10-3. bölüm.

Soru sadece sihirli sabitlerin nasıl hesaplanacağı değil, aynı zamanda bölenin nasıl geri alınacağıydı.
Cevap vermeye çalıştım. Bir kanıt oluşturmak için gerçekten zamanım olmadı, bu yüzden doğru olduğundan% 100 emin değilim.
Tersine mühendislik varsayımları altında (çarpma yoluyla sabit bölme / modulo diğer işlemlerle karıştırılırsa), tamsayı çarpma sabitini, tersi bölünme / modulo sabiti operand ile bilinmeyen bir değere kadar ilişkili olan bir ikili kesire dönüştürebilir. 2 çarpan faktörün gücü. 2 faktörün bilinmeyen gücünün çıkarılması, diğer işlemlerle karıştırılması ve optimizasyonu nedeniyle bazen imkansızdır.
Bilginize: Cevap, her site için mathjax'ı etkinleştirdiği için yığın değişim uygulamasıyla iyi görünüyor
#2
+7
John Källén
2016-03-30 23:32:39 UTC
view on stackexchange narkive permalink

İşte geç yanıt. Reko decompiler, medantları kullanarak bir bölme ve fethetme araması yaparak tamsayı bölenleri kurtarır.

Reko, bir 64 bit ürün ( r * c ) kullanılır. c sabit çarpanı 2 ^ 32'ye bölünerek 0,0 ile 1,0 arasında çift kesinlikli bir kayan nokta sayısı elde edilir. 0/0 ve 1/1 rasyonel sayılarından başlayarak Reko, kayan nokta sayısını parantez içine alan bir medantlar dizisi hesaplar. Bu medantlar dizisinden, kayan nokta numarasına en yakın olan rasyonel sayıyı seçer ve onu döndürür.

Kod henüz tam olarak test edilmedi - negatif sayılarla çalışma şansım olmadı birincisi, ancak makul sonuçlar veriyor gibi görünüyor. Merak ediyorsanız kod burada: https://github.com/uxmal/reko/blob/master/src/Decompiler/Analysis/ConstDivisionImplementedByMultiplication.cs

#3
+1
Sebastian Graf
2017-02-21 16:39:42 UTC
view on stackexchange narkive permalink

Bu makale ilginizi çekebilir: Değişmez çarpma ile bölme.

Bunu burada çarptı.



Bu Soru-Cevap, otomatik olarak İngilizce dilinden çevrilmiştir.Orijinal içerik, dağıtıldığı cc by-sa 3.0 lisansı için teşekkür ettiğimiz stackexchange'ta mevcuttur.
Loading...