Как перевернуть байт

Вот фрагмент — он написан для набора инструментов GNU (avr-gcc, binutils, avr-libc и т. д.), но его легко адаптировать:

static inline __attribute__ ((always_inline))
uint8_t avr_reverse_byte (uint8_t x)
{
    x = ((x & 0x55) << 1) | ((x & 0xaa) >> 1);
    x = ((x & 0x33) << 2) | ((x & 0xcc) >> 2);

    /* x = ((x & 0x0f) << 4) | ((x & 0xf0) >> 4); */

    __asm__ ("swap %0" : "=r" (x) : "0" (x)); /* swap nibbles. */

    return x;
}

Таким образом, не так уж много улучшений по сравнению с кодом 'C', за исключением окончательной замены полубайтов hi-lo, реализованной с помощью инструкции swap.

Я не могу предоставить код AVR прямо сейчас. Но общий метод реверсирования битов следующий:

abcd efgh   p
badc fehg   p = ((p and 0AAh) shr 1) or ((p shl 1) and 0AAh)
dcba hgfe   p = ((p and 033h) shr 2) or ((p shl 2) and 033h)
hgfe dcba   p = ((p and 00Fh) shr 4) or ((p shl 4) and 0F0h)

Другой простой способ — использовать флаг переноса:

Повторить 8 раз:

lsl r20 ; shift one bit into the carry flag
ror r0  ; rotate carry flag into result 

(Ввод в r20, вывод в r0, содержимое r20 уничтожено; регистры могут свободно изменяться.)

Это использует 16 инструкций @ 2 байта, 1 цикл каждая = 32 байта программной памяти и 16 циклов, чтобы перевернуть один байт, когда он полностью «развернут». Завернутый в цикл, размер кода может быть уменьшен, но время выполнения увеличится.

4-битная (16 записей) таблица поиска для двух половин байта выглядит как хороший компромисс (как указывает @Aki в комментарии).

Инструкции AVR занимают по 2 байта каждая, поэтому 16-байтовая таблица занимает столько же места, сколько 8 инструкций. (Оказывается, это не стоит того из-за скорости или размера, за исключением, может быть, если вы можете выровнять свой массив по 256 байтам, чтобы сделать индексацию намного дешевле, чем то, что делает gcc.)

Можно было бы упаковать LUT, используя старшую и младшую половину каждого байта. Но это будет стоить больше при индексации (использование ветки на бите 4 индекса для условной перестановки перед маскированием), чем экономит размер таблицы (8 байтов = 4 инструкции).

Давайте сравним, что делает AVR GCC. gcc4.6 имеет на удивление ужасные пропущенные оптимизации при компиляции кода Бретта (фактически продвигаясь к int и не используя все преимущества усечения результата до uint8_t). По иронии судьбы он действительно оптимизирует x<<4 | x>>4 в ротацию с помощью инструкции SWAP. (AVR не имеет команды ротации с несколькими счетчиками, а обычные циклы выполняются с ротацией через перенос. Сдвиги доступны только с одним счетчиком на инструкцию.)

#include <stdint.h>

uint8_t reverse_byte_alu (uint8_t x)
{
    uint8_t xeven = x & 0x55,  xodd = x & 0xaa;
    x = (xeven << 1) | (xodd >> 1);  // swap adjacent bit pairs

    xeven = x & 0x33,  xodd = x & 0xcc;
    x = (xeven << 2) | (xodd >> 2);  // swap adjacent 2-bit chunks

    x = ((x << 4) | (x >> 4));  // 4-bit rotate is recognized as SWAP
    return x;
}

<Сильный> компилируется в этом ассемблере с gcc4.6 -O3 (компилятор исследователя Godbolt) . Я не вижу пропущенных оптимизаций.

reverse_byte_alu:
    mov r25,r24
    andi r25,lo8(85)
    lsl r25
    andi r24,lo8(-86)
    lsr r24
    or r25,r24              # swap of adjacent bits done

    mov r24,r25
    andi r24,lo8(51)
    lsl r24
    lsl r24                 # << 2
    andi r25,lo8(-52)
    lsr r25
    lsr r25                 # >> 2
    or r24,r25              # swap pairs of bits done

    swap r24                # swap nibbles
    ret

16 инструкций по 2 байта, все 1-тактные. (кроме ret) https://www.microchip.com/webdoc/avrassembler/avrassembler.wb_instruction_list.html

Так что это немного лучше, чем ответ @JimmyB, который требует 16 однотактных инструкций, не включая ret. (Но его можно свернуть в небольшую петлю).

Индексация массива в AVR стоит недешево. Единственный выбор режима адресации — постинкрементный или предекрементный, никаких немедленных смещений. Таким образом, 16-битный адрес массива должен быть добавлен к 4-битным значениям полубайта. Если ваш массив находится в нижних 256 байтах адресного пространства, это может быть дешевле. Или, если ваш массив выровнен по 256 байтам, вы можете просто установить старший байт регистра указателя и поместить искомое значение в младший байт. (gcc пропускает эту оптимизацию).

Указание gcc выровнять массив по 16-байтовой границе удешевляет вычисление адреса, но общее количество инструкций составляет 18, и некоторые из них являются многотактными инструкциями.

__attribute__((aligned(16)))  // makes indexing cheaper
static const uint8_t reverse_nibble[16] = {
        0,      0b1000, 0b0100, 0b1100,
        0b0010, 0b1010, 0b0110, 0b1110,
        0b0001, 0b1001, 0b0101, 0b1101,
        0b0011, 0b1011, 0b0111, 0b1111
        };

uint8_t reverse_byte_nibble_LUT (uint8_t x) {
    uint8_t hi = reverse_nibble[x>>4];
    hi = ((hi << 4) | (hi >> 4));  // SWAP instead of SWAP+AND for just a shift
    uint8_t lo = reverse_nibble[x & 0x0f];
    return hi | lo;
}

компилируется в 17 инструкций, а LD представляет собой двухтактную инструкцию при доступе к FLASH с помощью режим адресации без инкремента/декремента. (Это 1 цикл на некоторых процессорах, когда нет доступа к флэш-памяти или внутренней SRAM).

  # gcc4.6 output, not optimal
    mov r26,r24
    swap r26
    andi r26,lo8(15)
    ldi r27,lo8(0)
    subi r26,lo8(-(reverse_nibble))   # AVR doesn't have add-immediate byte, only sub
    sbci r27,hi8(-(reverse_nibble))   # X register = (x>>4) - (-LUT_base)
    ld r25,X
    swap r25
    mov r30,r24
    ldi r31,lo8(0)
    andi r30,lo8(15)
    andi r31,hi8(15)                 # missed opt, this is a double-redundant 0 & 0
    subi r30,lo8(-(reverse_nibble))
    sbci r31,hi8(-(reverse_nibble))
    ld r24,Z
    or r24,r25
    ret

ldi r27, 0 / sbci r27 вероятно пропущенная оптимизация. С 16-байтовой выровненной таблицей перенос в старший байт невозможен. Я думаю, мы можем сделать:

    # generate r30 = x&0x0f
    subi r30,lo8(-(reverse_nibble))   # ORI would work, too.  no-op with 256-byte aligned table
    ldi  r31,hi8(reverse_nibble)      # reuse this for hi and lo

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

С небольшой доработкой можно получить дополнительную производительность из фрагмента кода (моего) в комментариях.

Когда мы убедимся, что LUT выровнен по 16-байтовой границе, мы можем сгенерировать адрес с помощью xoring. Также мы можем сделать XOR таблицы по индексу, позволяя модифицировать аргумент x на месте. Я закомментировал ненужные инструкции, сгенерированные GCC.

__attribute__((aligned(16)))  // makes indexing cheaper
static const uint8_t reverse_nibble_xor[16] = {
        0 ^ 0,  1 ^ 0b1000, 2 ^ 0b0100, 3 ^ 0b1100,
        4 ^ 0b0010, 5 ^ 0b1010, 6 ^ 0b0110, 7 ^ 0b1110,
        8 ^ 0b0001, 9 ^ 0b1001, 10 ^ 0b0101, 11 ^ 0b1101,
        12 ^ 0b0011, 13 ^ 0b1011, 14 ^ 0b0111, 15 ^ 0b1111
        };


uint8_t reverse_ams(uint8_t x)
{
    uint8_t *p = (uint8_t *)((uint16_t)reverse_nibble_xor ^ (x & 15));
    x ^= p[0];
    x = ((x << 4) | (x >> 4));
    uint8_t *q = (uint8_t *)((uint16_t)reverse_nibble_xor ^ (x & 15));
    x ^= q[0];
    return x;
}

reverse_ams:
        ldi r18,lo8(reverse_nibble)
//      ldi r19,hi8(reverse_nibble)
        ldi r31,hi8(reverse_nibble)  // use r31 directly instead of r19
        mov r30,r24
//        ldi r31,lo8(0)
        andi r30,lo8(15)
//        andi r31,hi8(15)
        eor r30,r18
//        eor r31,r19
        ld r25,Z
        eor r25,r24
        swap r25
        mov r30,r25
//        ldi r31,lo8(0)
        andi r30,lo8(15)
//        andi r31,hi8(15)
        eor r30,r18
//        eor r31,r19
        ld r24,Z
        eor r24,r25
        ret