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. Она делала именно то, что хотели эти ребята -- переворачивала биты задом наперёд. В один такт.
Выводы и мораль писать лень.
_/¯
)
