Fast Division su GCC/ARM

Question

Per quanto ne so, molti compilatori eseguiranno una divisione rapida moltiplicando e spostando i bit verso destra. Ad esempio, se si controlla this SO thread si dice che quando si chiede al compilatore Microsoft di eseguire la divisione per 10 moltiplicherà il dividendo di 0x1999999A (che è 2^32/10) e quindi dividerà il risultato per 2^32 (utilizzando 32 turni a destra).

Fin qui tutto bene.

Dopo aver testato la stessa divisione per 10 su ARM utilizzando GCC, il compilatore ha fatto qualcosa di leggermente diverso. In primo luogo ha moltiplicato il dividendo di 0x66666667 (2^34/10), quindi ha diviso il risultato per 2^34. Finora è lo stesso di Microsoft, tranne che con un moltiplicatore più alto. Successivamente, tuttavia, è stato sottratto (dividendo/2^31) dal risultato.

La mia domanda: perché sulla versione ARM c'è quella sottrazione extra? Puoi darmi un esempio numerico in cui senza quella sottrazione il risultato sarà sbagliato?

Se si desidera controllare il codice generato, è al di sotto (con i miei commenti):

 ldr  r2, [r7, #4] @--this loads the dividend from memory into r2 
     movw r3, #:lower16:1717986919 @--moves the lower 16 bits of the constant 
     movt r3, #:upper16:1717986919 @--moves the upper 16 bits of the constant 
     smull r1, r3, r3, r2 @--multiply long, put lower 32 bits in r1, higher 32 in r3 
     asr  r1, r3, #2 @--r3>>2, then store in r1 (effectively >>34, since r3 was higher 32 bits of multiplication) 
     asr  r3, r2, #31 @--dividend>>31, then store in r3 
     rsb  r3, r3, r1 @--r1 - r3, store in r3 
     str  r3, [r7, #0] @--this stores the result in memory (from r3) 

Answer 1

In seguito, tuttavia, è stato sottratto (dividendo/2^31) dal risultato.

realtà, sottrae dividend >> 31, che è -1 per negativo dividend, e 0 per dividendo non negativo, quando destra-shifting interi negativi è aritmetica spostamento a destra (e int è largo 32 bit).

0x6666667 = (2^34 + 6)/10 

Quindi per x < 0, abbiamo, scrivendo x = 10*k + r con -10 < r <= 0,

0x66666667 * (10*k+r) = (2^34+6)*k + (2^34 + 6)*r/10 = 2^34*k + 6*k + (2^34+6)*r/10 

Ora, aritmetica spostamento a destra di numeri interi negativi cede il pavimento della v/2^n, così

(0x66666667 * x) >> 34 

risultati in

k + floor((6*k + (2^34+6)*r/10)/2^34) 

così abbiamo bisogno di vedere che

-2^34 < 6*k + (2^34+6)*r/10 < 0 

La disuguaglianza giusta è facile, sia k e r sono non positivi, e non entrambi sono 0.

Per la disuguaglianza di sinistra, un po 'di più l'analisi è necessaria

r >= -9 

modo che il valore assoluto di (2^34+6)*r/10 è al massimo 2^34+6 - (2^34+6)/10.

|k| <= 2^31/10, 

quindi |6*k| <= 3*2^31/5.

E resta da verificare che

6 + 3*2^31/5 < (2^34+6)/10 
1288490194 < 1717986919 

Yup, è vero.

Answer 2

x SAR 31 è 0xffffffff (-1) per i valori negativi di x e 0x00000000 per i valori positivi.

Quindi il rsb sta sottrarre -1 dal risultato (che è lo stesso di aggiungere 1) se il dividendo era negativo.

Diciamo che il dividendo è -60. Con il solo moltiplicare e spostare otterresti il ​​risultato -7, quindi sottrae -1 per ottenere il risultato previsto di -6.