Секреты оптимизации. Часть 2

Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)

Часть 1. Реализация оператора "case of" на ассемблере

Часть 2. Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)

Порой возникают ситуации, когда необходимо преобразовать байт таким образом, чтобы биты в нём располагались в обратном порядке. Сегодня я покажу несколько алгоритмов, позволяющих реализовать подобное преобразование.

Способ 1. Самый медленный.

Первое, что приходит на ум при возникновении подобной задачи, - это решить задачу в лоб. Создать цикл на 8 шагов и далее на каждом шаге, используя сдвиги и проверки переписывать биты из одного регистра в другой, но в обратном порядке. Схематично этот алгоритм показан на рисунке справа.

На ассемблере для AVR подобный способ мог бы быть реализован, например, так:

; Пусть у нас R16 - регистр счётчик,
; R17 - регистр-источник (его биты нужно перевернуть),
; R18 - регистр-приёмник (здесь будет результат)
     ldi     R16,8    ; инициализируем счётчик на 8 шагов
Next:
     lsr     R18      ; сдвигаем приёмник вправо, в 7-й бит записывается 0
     sbrc    R17,7    ; если 7-й бит источника равен 0 - пропускаем команду
     sbr     R18,0x80 ; устанавливаем 7-й бит приёмника в единицу
     lsl     R17      ; сдвигаем источник влево
     dec     R16      ; уменьшаем счётчик на единицу
     brne    Next     ; если не установился флаг Z - переходим на начало цикла
	

Как видите, этот способ обошёлся нам в 7 команд, 3 регистра и займёт порядка 50-60 машинных циклов (лень считать точно), что очень и очень много, особенно по времени.

Простой алгоритм инвертирования порядка бит в байте

Способ 2. Быстрее и сравнимый по ресурсам.

Основной недостаток предыдущего алгоритма в том, что каждый бит мы проверяли отдельно (поэтому по времени и получились особенно жуткие затраты), однако существует алгоритм, позволяющий переставлять сразу группы битов (сначала полубайты, потом соседние пары битов и, наконец, соседние биты).

Для реализации этого способа нам придётся выделять в чистом виде группы, содержащие по 4 бита подряд, по 2 бита подряд и содержащие биты через 1. Такие группы легко выделить, применяя к исходному байту операцию "логическое И" с числами 0xF0, 0x0F, 0xCC, 0x33, 0xAA и 0x55. Суть алгоритма показана на рисунке справа.

На картинке этот алгоритм выглядит более "массивно", чем первый. Давайте посмотрим, что получится в коде:

     swap    R17      ; меняем местами полубайты
     mov     R18,R17  ; копируем регистр-источник
     andi    R17,0xCC ; убираем лишнее
     lsr     R17      ; сдвигаем 2 раза вправо
     lsr     R17
     andi    R18,0x33 ; убираем лишнее
     lsl     R18      ; сдвигаем 2 раза влево
     lsl     R18
     and     R17,R18  ; складываем по И
     mov     R18,R17  ; копируем промежуточный результат
     andi    R17,0xAA ; убираем лишнее
     lsr     R17      ; сдвигаем вправо
     andi    R18,0x55 ; убираем лишнее
     lsl     R18      ; сдвигаем влево
     andi    R18,R17
	

Итак, для реализации нам потребовалось в 2 раза больше команд (15), 2 регистра (вместо 3-х, как было в первом случае). Но, главное, наш алгоритм теперь выполняется в 4 раза быстрее (за 15 машинных циклов).

Средний по времени и ресурсам алгоритм инвертирования порядка бит в байте

Способ 3. Самый быстрый, но самый ресурсозатратный.

Ну и, наконец, есть ещё один способ, являющийся самым быстрым. Для его реализации необходимо заранее составить таблицу из 256 элементов, причём каждый элемент этой таблицы должен представлять собой смещение от начала таблицы (номер элемента), но с инвертированным порядком битов. В этом случае для решения задачи нам просто нужно запросить из таблицы элемент, порядковый номер которого соответствует байту, для которого мы хотим найти обратный порядок бит. Опять же, чтобы понять как это работает - лучше посмотреть на рисунок (справа).

В коде это выглядит так:

; в регистрах XH:XL - адрес начала таблицы
     add     XL, R17 ; вычисляем адрес ячейки, которая содержит
     brcc    Next    ; если при сложении не было переполнения,
     inc     XH      ; пропускаем эту команду
Next:
     ld      R18,X   ; загружаем значение из таблицы
	
Самый быстрый алгоритм инвертирования порядка бит в байте

Как видите, для решения задачи по этому методу требуется всего 4 команды, 4 регистра и 4 машинных цикла. При этом, если начальный адрес таблицы выровнен на начало сегмента (младшие 8 бит адреса равны нулю), то средние две команды кода становятся ненужными (первую, при этом, нужно заменить на mov), код сокращается всего до 2-х команд и, соответственно, двух машинных циклов.

Нужно понимать, что метод требует значительных накладных расходов, поскольку для его реализации требуется заполнить и постоянно хранить в памяти таблицу всех возможных решений.

На сегодня, пожалуй, всё.

Часть 1. Реализация оператора "case of" на ассемблере

Часть 2. Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)

radiohlam.ruтеорияконтроллеры и программирование

Понравилась статья? Поделись с друзьями!

Обсудить эту статью на форуме

 
Rambler's Top100 © 2009 - Материалы сайта охраняются законом об авторском праве