Fast Division on GCC/ARM

Question

Насколько я знаю, большинство компиляторов будет выполнять быстрое деление путем умножения и последующего смещения вправо. Например, если вы отметите this SO thread, в нем говорится, что когда вы попросите компилятор Microsoft выполнить деление на 10, он умножит дивиденд на 0x1999999A (что составляет 2^32/10), а затем разделит результат на 2^32 (используя 32 смены направо).

Пока все хорошо.

Как только я протестировал одно и то же деление на 10 на ARM, используя GCC, компилятор сделал что-то немного другое. Сначала он умножил дивиденд на 0x66666667 (2^34/10), затем разделил результат на 2^34. До сих пор это то же самое, что и Microsoft, за исключением использования более высокого множителя. После этого, однако, он вычитал (дивиденд/2^31) из результата.

Мой вопрос: почему в версии ARM есть дополнительное вычитание? Можете ли вы дать мне числовой пример, где без этого вычитания результат будет неправильным?

Если вы хотите, чтобы проверить сгенерированный код, это ниже (с моими комментариями):

 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

После этого, однако, он вычитал (дивиденд/2^31) из результата.

На самом деле, это вычитает dividend >> 31, который -1 для отрицательного dividend, и 0 для неотрицательных дивидендов, когда сдвиг вправо отрицательных чисел является арифметическим сдвигом вправо (и int составляет 32 бита).

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

Так x < 0, у нас есть, писать x = 10*k + r с -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 

Теперь арифметика сдвиг вправо отрицательных чисел дает пол v/2^n, так

(0x66666667 * x) >> 34 

результаты в

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

Таким образом, мы должны видеть, что

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

Право неравенство легко, как и kr не являются положительными, а не оба равны 0.

Для левого неравенства, немного больше необходим анализ.

r >= -9 

так, абсолютное значение (2^34+6)*r/10 составляет не более 2^34+6 - (2^34+6)/10.

|k| <= 2^31/10, 

так |6*k| <= 3*2^31/5.

И остается проверить, что

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

Да, верно.

Answer 2

x SAR 31 является 0xffffffff (-1) для отрицательных значений x и 0x00000000 для положительных значений.

Так что rsb вычитает -1 из результата (что совпадает с добавлением 1), если дивиденд был отрицательным.

Предположим, что ваш дивиденд -60. Только с умножением и сдвигом вы получите результат -7, поэтому он вычитает -1, чтобы получить ожидаемый результат от -6.