Szybki podział na GCC/ARM

Question

O ile mi wiadomo, większość kompilatorów zrobi szybki podział przez pomnożenie, a następnie przesunięcie bitów w prawo. Na przykład, jeśli sprawdzisz this SO thread, to powiesz, że gdy poprosisz kompilator Microsoftu o dzielenie przez 10, to pomnoży on dywidendę przez 0x1999999A (która jest 2^32/10), a następnie podzieli wynik przez 2^32 (używając 32 zmian w prawo).

Jak dotąd tak dobrze.

Raz przetestowałem ten sam podział przez 10 na ARM przy użyciu GCC, chociaż kompilator zrobił coś nieco innego. Najpierw pomnożył on dywidendę przez 0x66666667 (2^34/10), a następnie podzielił wynik na 2^34. Do tej pory jest taki sam jak Microsoft, z wyjątkiem użycia wyższego mnożnika. Następnie od wyniku odjęto (dywidenda/2^31).

Moje pytanie: dlaczego w wersji ARM jest to dodatkowe odejmowanie? Czy możesz podać przykład liczbowy, gdzie bez tego odejmowania wynik będzie błędny?

Jeśli chcesz sprawdzić wygenerowany kod, to poniżej (z moich komentarzach):

 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

Po tym jednak został odjęty (dywidenda/2^31) od wyniku.

Faktycznie, odejmuje dividend >> 31, który -1 negatywnego dividend i 0 dla nie-ujemnych dywidendy po prawej ujemne przesunięcie liczb całkowitych jest arytmetyczną prawą przesunięcie (a int ma szerokość 32 bitów).

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

Więc dla x < 0 mamy, pisząc x = 10*k + r z -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 

Teraz arytmetyka prawy shift ujemnych liczb całkowitych daje podłogę v/2^n, więc

(0x66666667 * x) >> 34 

Skutkuje

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

Więc musimy zobaczyć, że

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

Prawo nierówność jest łatwe, zarówno k i r są non-dodatnie, a nie oba są 0.

Na lewym nierówności, nieco więcej analiza jest potrzebna.

r >= -9 

więc wartość bezwzględna (2^34+6)*r/10 co najwyżej 2^34+6 - (2^34+6)/10.

|k| <= 2^31/10, 

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

i pozostaje do sprawdzenia, czy

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

Tak, to prawda.

Answer 2

x SAR 31 jest 0xffffffff (-1) dla ujemnych x i 0x00000000 dla wartości dodatnich.

Tak więc rsb odejmuje -1 od wyniku (który jest taki sam jak dodanie 1), jeśli dywidenda była ujemna.

Załóżmy, że Twoja dywidenda to -60. Wystarczy pomnożyć i przesunąć, aby uzyskać wynik -7, więc odejmuje on -1, aby uzyskać oczekiwany wynik -6.