Domanda:
Come posso invertire la divisione / modulo intero ottimizzato con operazioni costanti?
Dougall
2013-03-30 12:14:20 UTC
view on stackexchange narkive permalink

Quando compilo una divisione o un modulo per una costante, il mio compilatore (LLVM GCC) genera una serie di istruzioni che non capisco.

Quando compilo i seguenti esempi minimi:

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

Viene generato il codice seguente:

  _mod7: push rbp mov rbp, rsp mov ecx, 0x92492493 mov eax, edi imul ecx add edx, edi mov eax, edx shr eax, 0x1f sar edx, 0x2 aggiungi 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 aggiungi edx, edi mov ecx, edx shr ecx, 0x1f sar edx, 0x2 mov eax , edx add eax, ecx pop rbp ret  
  • Come è matematicamente equivalente e da dove vengono le costanti?
  • Qual è il modo più semplice per trasformare il gruppo torna in C (per a rbitrarie costanti sul lato destro)?
  • Come può uno strumento, come un decompilatore o un disassemblatore di analisi, automatizzare questo processo?
Questo a volte è chiamato * moltiplicazione reciproca *. Ecco una [breve spiegazione] (http://www.nynaeve.net/?p=115) con collegamenti a risorse più dettagliate. Ho visto Hex-Rays digerire questo senza problemi.
Tre risposte:
#1
+39
Peter Andersson
2013-03-31 14:26:13 UTC
view on stackexchange narkive permalink

Primo

Sfortunatamente non sembra che MathJax sia attivato in questo scambio di stack, quindi le parti di matematica seguenti sono formattate in modo piuttosto orribile. Sono anche lontano dall'essere un matematico, quindi la notazione potrebbe essere sbagliata in alcuni punti.

Capire il numero e il codice magico

L'obiettivo del codice sopra è riscrivere una divisione in una moltiplicazione perché la divisione richiede più cicli di clock di una moltiplicazione. È nell'area di circa il doppio dei cicli, a seconda della CPU. Quindi dobbiamo trovare un bel modo senza rami per farlo. Se si ramifica è molto probabile che si perda semplicemente facendo la divisione.

Un modo è semplicemente realizzare che la divisione è uguale alla moltiplicazione per l'inverso del numero, cioè . Il problema è che è un numero piuttosto scarso da memorizzare come numero intero. Quindi dobbiamo moltiplicare sia il divisore che il dividendo per un certo numero. Dato che operiamo su numeri a 32 bit e otteniamo risultati di moltiplicazione in numeri a 64 bit, otteniamo la migliore precisione con ed evitiamo anche problemi di overflow. Quindi fondamentalmente otteniamo . Ora quella parte frazionaria è ciò che ci causa problemi perché causerà errori di arrotondamento.

Quindi proviamo a formalizzare questo:

Dove è il nostro moltiplicando, ad esempio , o in realtà qualsiasi numero ma funziona molto bene con le dimensioni dei nostri registri in quanto possiamo semplicemente scartare il registro inferiore a 32 bit. è il numero che devi aggiungere per rendere divisibile in modo uniforme per . è il numero che desideriamo dividere.

Possiamo riscrivere l'equazione precedente, come

che illustra il punto che abbiamo il nostro dividendo diviso per il nostro divisore e quindi un fattore di errore di .

Studiando la nostra equazione originale di è chiaro che possiamo influenzare molto poco. deve essere una potenza di 2, non può essere troppo grande o rischiamo un overflow e non può essere troppo piccolo in quanto ha un effetto negativo diretto sul nostro fattore di errore . dipende direttamente da e .

Quindi proviamo che fornisce una frazione di errore massima di con il valore massimo di essendo , quindi , sfortunatamente non è inferiore a quindi possiamo ottenere errori di arrotondamento.

Aumenteremo l'esponente di a , che dà , la frazione di errore massima che è minore di . Ciò significa che il nostro moltiplicando è che non è inferiore o uguale al valore con segno massimo che possiamo memorizzare in un registro a 32 bit (). Quindi creiamo invece il moltiplicando . Come nota a margine, grazie alla magia del complemento a due quando sottraiamo il numero è che è quando interpretato come un numero senza segno. Ma stiamo facendo aritmetica con segni qui. Quindi dobbiamo correggere l'espressione finale aggiungendo . Questo risolve anche solo il problema per , per i numeri negativi saremo fuori di 1 quindi dobbiamo aggiungere 1 se abbiamo un numero negativo.

Questa è la spiegazione della costante nella moltiplicazione e come arrivarci. Ora guardiamo il codice:

 ; Carica -1840700269mov ecx, 0x92492493; Carica nmov eax, edi; n * -1840700269imul ecx; aggiungi n per compensare la 2 ^ 32 sottrazioneadd edx, edi; controlla il bit di segno del nostro resultmov ecx, edxshr ecx, 0x1f; dividere per 2 ^ 2 per compensare noi usando y = 2 ^ 34 invece di 2 ^ 32sar edx, 0x2mov eax, edx; aggiungi il valore del bit di segno al risultato finale eax, ecx  

Calcolo del divisore dal numero magico e dal codice

Non l'ho dimostrato matematicamente, tuttavia se vuoi per recuperare il divisore da una discarica di montaggio come quella che hai mostrato possiamo fare dei semplici esercizi mentali. Per prima cosa dobbiamo renderci conto che quanto segue vale

Dove è la regolazione che abbiamo effettuato per portare il valore nell'intervallo di un valore a 32 bit. Dal codice possiamo escogitare quanto segue, lo spostamento a destra di due significa che abbiamo , , , è sconosciuto. Ciò significa che manca una variabile per eseguire una soluzione perfetta. Tuttavia l'effetto di se trascurabile in quanto il suo scopo è di portare il divisore il più vicino possibile al suo valore intero. Ciò significa che la soluzione può essere trovata risolvendo

Un altro esempio con divisore 31337 che ha il moltiplicatore e il numero magico 140346763 e a destra si sposta di 10 bit.

Infine

Per un'analisi matematica completa di come funziona, comprese tutte le prove e gli algoritmi appropriati per il calcolo del numeri magici, turni e aggiunte, vedi Hacker's Delight, capitolo 10-3.

La domanda non era solo come calcolare le costanti magiche, ma anche come recuperare il divisore.
Ho provato a rispondere. Non ho davvero avuto il tempo di formulare una dimostrazione, quindi non sono sicuro al 100% che sia corretta.
Sotto i presupposti del reverse engineering (se la divisione const / modulo per moltiplicazione è confusa con altre operazioni), è possibile convertire la costante di moltiplicazione intera in una frazione binaria, il cui reciproco è correlato all'operando costante di divisione / modulo fino a potenza di 2 fattore moltiplicativo. La deduzione della potenza sconosciuta del fattore 2 a volte è impossibile a causa della miscelazione e dell'ottimizzazione con altre operazioni.
Cordiali saluti: la risposta sembra buona con l'app di scambio di stack, poiché ha attivato mathjax per ogni sito
#2
+7
John Källén
2016-03-30 23:32:39 UTC
view on stackexchange narkive permalink

Ecco una risposta in ritardo. Il decompilatore Reko recupera i divisori interi eseguendo una ricerca divide et impera utilizzando medianti.

Reko inizia riconoscendo lo schema in cui la parola alta di un Viene utilizzato un prodotto a 64 bit ( r * c ). Il moltiplicatore di costante c viene diviso per 2 ^ 32 per ottenere un numero in virgola mobile a doppia precisione compreso tra 0,0 e 1,0. Partendo dai numeri razionali 0/0 e 1/1, Reko calcola una sequenza di mediane che racchiude il numero in virgola mobile. Da questa sequenza di mediane sceglie il numero razionale che si avvicina di più al numero in virgola mobile e lo restituisce.

Il codice non è ancora completamente testato - non ho avuto la possibilità di lavorare con numeri negativi tuttavia, per esempio, ma sembra dare risultati ragionevoli. Il codice è qui se sei curioso: 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

Questo documento potrebbe essere interessante: Divisione per moltiplicazione invariante.

Ci siamo imbattuti in questo qui.



Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...