| « Хороший мануал по пользованию GNU тулчейна для ARM | R3-RTOS люлянский календарь » |
На самом деле операция деления в архитектуре ARM отсутствует. По этой причине везде, где в программе используется деление или остаток от деления компилятор неявно подставляет вызов функции эмулятора деления. Эмуляция деления - это кусок кода, который содержит циклы и и выполняется никак не меньше сотни-двух тактов. Так что, от деления хочется вовсе избавляться, когда есть возможность, и уж точно не заниматься делением при обработке данных. Замена деления...
Продолжение:
Во-первых, деление можно заменить на операцию арифметического сдвига, когда дело касается деления на 2^n. Когда в программе стоит деление на константу 2^n компилятор (GCC) сам догадается, что надо использовать арифметический сдвиг. Использование операции сдвига вместо деления числа без знака (unsigned) корректно. Проблемы могут возникать при делении чисел со знаком, когда операция арифметического сдвига бывает не равносильна операции деления x/2^n. Если применять арифметический сдвиг к числу -1, то получается -1, а если применять деление на 2 к числу -1 получается 0. Требуется процедура коррекции результата сдвиговой операции.
Во-вторых, деление чисел без знака можно заменить на операцию умножения на дробь x/A => ( x*B )>>n, где B - обратное число для A. Если бы точность преобразования не терялась, то B = 1/A*2^n. В таких случаях говорят о числах с фиксированной точкой. Число B представляется ближайшим целым числом, для которого это равенство справедливо. Наши задумались насколько справедлива такая замена, будет ли она давать тот же результат, что и операция деления. Операция, для которой нам потребовалось вводить подобную арифметику -- нахождение результата деления и остатка от деления на 10. Операция применяется для преобразования бинарных в десятичные числа, например в операции printf.
Это один частный случай. В общем случае задача сводится к замене операции деления на константу на операцию умножения на обратное число.
Надо выбрать такие B и n чтобы для всех целых чисел без знака (x) операция ( x*B )>>n давала тот же результат что и x/A. Хочется при этом минимизировать разрядность операции, чтобы операция выполнялась эффективно в системе команд целевого процессора. Наша постановка задачи для ARM сводится к требованию: для представления должна использоваться одна инструкция процессора -умножение и одна инструкция - сдвиг. Умножение 32разрядных чисел приводит к результату 64 бита, который размещается в двух регистрах (старшие 32 бита и младшие 32 бита). Особенно выделим случай когда удается выразить деление как ( x*B )>>32, в этом случае мы берем старшие 32 бита и нужна всего одна инструкция процессора для эмуляции деления.
Результаты экспериментов:
Умножение на 1/10 для всех целых чисел 8 бит:
uint8_t x;
uint8_t y = (x*0xCD)>>11;
Умножение на 1/10 для всех целых чисел 16 бит:
uint16_t x;
uint16_t y = (x*0xCCCD)>>19;
Умножение на 1/10 для всех целых чисел 32 бита:
uint32_t x;
uint32_t y = (x*0xCCCCCCCDULL)>>35;
При этих значениях операция умножения на 1/10 дает те же результаты, что и целочисленное деление на 10 на всем множестве целых чисел. Разрядность константы соответствует разрядности операции и не вызывает переполнения или потери точности при умножении.
Вот ещё пример: для функции системного таймера понадобилось секунды от минут отделять, нужна операция умножения на 1/60.
uint32_t sec;
uint32_t min = (sec*0x88888889ULL)>>37;
Константы для таких операций можно вычислять так: B - максимальное число заданной разрядности, которое находится из уравнения B=(2^n/A)+ошибка. Ошибку операции в некоторых случаях удается компенсировать добавлением единицы к B, а в некоторых случаях путем добавления единицы к результату.
Коррекция операции умножения на 1/7:
v = (n*0x92492492ULL)>>34;
r = n - v*7;
if(r>=7) v++, r-=7;
в примере n- число на входе, r - остаток от деления, v - результат операции деления.
URL трекбека (щелкните правой кнопкой мыши и скопируйте ссылку)