23:59
Арабский код
Коллегам из дружественной организации как-то раз надо было в микроконтроллерной программе разворачивать числа задом наперёд.
То есть, вот у нас число 183 (0b10110111), а надо было, чтобы число стало 237 (0b11101101). Как это можно сделать?
Ну, можно пробежаться по числу циклом, сдвигая его вправо, брать младший бит и прибавлять к результирующему числу, которое одновременно сдвигать влево.
Но это очень долго. Они хотели быстро! Поэтому они сделали массив, содержащий в себе все возможные варианты конечных чисел. Выбирая число по индексу, можно было получить ответ. В случае с приведённым выше примером, было так:
res=table[183];//res==237
Это был эффективный метод. Только числа были не восьмибитные, а шестнадцатибитные. Посчитаем, сколько занимала такая таблица в памяти?
65536*2=128 KiB
А размер всей прошивки был 512 KiB. То есть, четверть (!) всего места занимала эта таблица. Её можно было бы сгенерировать динамически в оперативной памяти, но оперативной памяти было ещё меньше.
Для их задачи потеря четверти прошивки на такую таблицу была не критична. Но такое решение мне казалось нерациональным. Тем не менее, лучшего я всё равно не знал. Тогда.
Потом я изучил ассемблер того контроллера. А контроллер был архитектуры ARM Cortex-M. По идее, это RISC-контроллер. Однако в его наборе команд есть много полезных штучек, делающих специфичные вещи, которые иначе занимали бы много команд. Это противоречит идеологии RISC, но удобно. Например, есть команда, считающая число ведущих нулей в числе. Или команда, расширяющая знаковое число любой указанной битности до знакового числа стандартной битности (16, 32). И даже команды работы со стеком были!
И вот среди этих команд я нашёл команду RBIT. Она делала именно то, что хотели эти ребята -- переворачивала биты задом наперёд. В один такт.
Выводы и мораль писать лень.
То есть, вот у нас число 183 (0b10110111), а надо было, чтобы число стало 237 (0b11101101). Как это можно сделать?
Ну, можно пробежаться по числу циклом, сдвигая его вправо, брать младший бит и прибавлять к результирующему числу, которое одновременно сдвигать влево.
Но это очень долго. Они хотели быстро! Поэтому они сделали массив, содержащий в себе все возможные варианты конечных чисел. Выбирая число по индексу, можно было получить ответ. В случае с приведённым выше примером, было так:
res=table[183];//res==237
Это был эффективный метод. Только числа были не восьмибитные, а шестнадцатибитные. Посчитаем, сколько занимала такая таблица в памяти?
65536*2=128 KiB
А размер всей прошивки был 512 KiB. То есть, четверть (!) всего места занимала эта таблица. Её можно было бы сгенерировать динамически в оперативной памяти, но оперативной памяти было ещё меньше.
Для их задачи потеря четверти прошивки на такую таблицу была не критична. Но такое решение мне казалось нерациональным. Тем не менее, лучшего я всё равно не знал. Тогда.
Потом я изучил ассемблер того контроллера. А контроллер был архитектуры ARM Cortex-M. По идее, это RISC-контроллер. Однако в его наборе команд есть много полезных штучек, делающих специфичные вещи, которые иначе занимали бы много команд. Это противоречит идеологии RISC, но удобно. Например, есть команда, считающая число ведущих нулей в числе. Или команда, расширяющая знаковое число любой указанной битности до знакового числа стандартной битности (16, 32). И даже команды работы со стеком были!
И вот среди этих команд я нашёл команду RBIT. Она делала именно то, что хотели эти ребята -- переворачивала биты задом наперёд. В один такт.
Выводы и мораль писать лень.
25.10.2018 в 12:43
"Это канал об аниме? - Да - Как пропатчить KDE2 под FreeBSD?"
25.10.2018 в 12:50
25.10.2018 в 14:41
25.10.2018 в 16:10
ЗЫ. Если им надо байт, то одной командой не обойтись, это 32-битная команда. )
25.10.2018 в 16:22
Стороной, ну тут как обычно всё зависит от задачи. Нужен им портируемый код или нет. Делать "лишь бы было портируемо" без необходимости, имхо, смысла нет.
А что команда работает с 32-битными операндами это не проблема, т.к. после неё можно сделать сдвиг на 16/24 бит вправо.
26.10.2018 в 07:09
26.10.2018 в 07:25
27.10.2018 в 15:08
```c
extern unsigned char table[256];
unsigned short reverse(unsigned short input) {
const unsigned char lo = input & 0xff;
const unsigned char hi = (input & 0xff00) >> 8;
// После переворачивания старший байт становится младшим и наоборот
const unsigned short top = table[lo];
const unsigned short bottom = (unsigned short)table[hi] << 8;
const unsigned short result = top | bottom;
return result;
}
```
Не в одну инструкцию, конечно, но тоже достаточно эффективно получается: godbolt.org/z/i1bNle
27.10.2018 в 15:09
27.10.2018 в 15:13