Порой возникают ситуации, когда необходимо преобразовать байт таким образом, чтобы биты в нём располагались в обратном порядке. Сегодня я покажу несколько алгоритмов, позволяющих реализовать подобное преобразование.
Способ 1. Самый медленный.
Первое, что приходит на ум при возникновении подобной задачи, — это решить задачу в лоб. Создать цикл на 8 шагов и далее на каждом шаге, используя сдвиги и проверки переписывать биты из одного регистра в другой, но в обратном порядке. Схематично этот алгоритм показан на рисунке справа. На ассемблере для AVR подобный способ мог бы быть реализован, например, так:
Как видите, этот способ обошёлся нам в 7 команд, 3 регистра и займёт порядка 50-60 машинных циклов (лень считать точно), что очень и очень много, особенно по времени. |
Способ 2. Быстрее и сравнимый по ресурсам.
Основной недостаток предыдущего алгоритма в том, что каждый бит мы проверяли отдельно (поэтому по времени и получились особенно жуткие затраты), однако существует алгоритм, позволяющий переставлять сразу группы битов (сначала полубайты, потом соседние пары битов и, наконец, соседние биты). Для реализации этого способа нам придётся выделять в чистом виде группы, содержащие по 4 бита подряд, по 2 бита подряд и содержащие биты через 1. Такие группы легко выделить, применяя к исходному байту операцию «логическое И» с числами 0xF0, 0x0F, 0xCC, 0x33, 0xAA и 0x55. Суть алгоритма показана на рисунке справа. На картинке этот алгоритм выглядит более «массивно», чем первый. Давайте посмотрим, что получится в коде:
Итак, для реализации нам потребовалось в 2 раза больше команд (15), 2 регистра (вместо 3-х, как было в первом случае). Но, главное, наш алгоритм теперь выполняется в 4 раза быстрее (за 15 машинных циклов). |
Способ 3. Самый быстрый, но самый ресурсозатратный.
Ну и, наконец, есть ещё один способ, являющийся самым быстрым. Для его реализации необходимо заранее составить таблицу из 256 элементов, причём каждый элемент этой таблицы должен представлять собой смещение от начала таблицы (номер элемента), но с инвертированным порядком битов. В этом случае для решения задачи нам просто нужно запросить из таблицы элемент, порядковый номер которого соответствует байту, для которого мы хотим найти обратный порядок бит. Опять же, чтобы понять как это работает — лучше посмотреть на рисунок (справа). В коде это выглядит так:
|
Как видите, для решения задачи по этому методу требуется всего 4 команды, 4 регистра и 4 машинных цикла. При этом, если начальный адрес таблицы выровнен на начало сегмента (младшие 8 бит адреса равны нулю), то средние две команды кода становятся ненужными (первую, при этом, нужно заменить на mov), код сокращается всего до 2-х команд и, соответственно, двух машинных циклов.
Нужно понимать, что метод требует значительных накладных расходов, поскольку для его реализации требуется заполнить и постоянно хранить в памяти таблицу всех возможных решений.
На сегодня, пожалуй, всё.
- Часть 1. Реализация оператора «case of» на ассемблере
- Часть 2. Как инвертировать порядок бит в байте (алгоритмы и примеры на ассемблере)