Как оптимизировать обратный порядок групп битов

Вы можете улучшить конвейер (если вы кодируете на C, компилятор сделает это за вас) и использовать интервал задержки инструкции bne. Это улучшит ваш параллелизм на уровне команд .

Предполагая, что у вас есть что-то вроде процессора Mips с 1 слотом задержки и 5-ступенчатым конвейером (извлечение инструкций, декодирование, выполнение, память, обратная запись).

Этот конвейер вводит Read After Write Опасности, связанные с зависимостью от данных, больше всего были в $3 регистре.

Атака RaW приводит к остановке вашего трубопровода.

# Reverse the order of data in Reference and store it in $02
Loop:   and     $03, $01, $06       # mask out one piece ($03 = Reference & $06)
        addi    $04, $04, -1        # decrement Loop counter (RaW on $3)
        sllv    $03, $03, $05       # shift piece to new position ($03 <<= $05)
        sllv    $06, $06, $05       # shift mask for next piece
        or      $02, $02, $03       # put piece into $02 ($02 |= $03)
        and     $03, $01, $06       # mask out next piece (#03 = Reference & $06)
        srlv    $06, $06, $05       # shift mask back
        srlv    $03, $03, $05       # shift piece to new position ($03 >>= $05)
        addi    $05, $05, -4        # decrease shift amount by 4
        or      $02, $02, $03       # put new piece into $02 ($02 |= $03)
        bne     $04, [110], Loop      # keep looping while $04 != 0
        sll     $06, $06, 2         # shift mask for next loop

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

Чтобы изменить ваши биты, вы можете использовать следующий код.

static int rev(int v){
  // swap adjacent pairs of bits
  v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
  // swap nibbles
  v = ((v >> 4) & 0x0f0f) | ((v & 0x0f0f) << 4);
  // swap bytes
  v = ((v >> 8) & 0x00ff) | ((v & 0x00ff) << 8);
  return v;
}

Реализация MIPS состоит из 15 инструкций.

rev: # value to reverse in $01
     # uses $02 reg
   srli $02, $01, 2
   andi $02, $02, 0x3333
   andi $01, $01, 0x3333
   slli $01, $01, 2
   or   $01, $01, $02
   srli $02, $01, 4
   andi $02, $02, 0x0f0f
   andi $01, $01, 0x0f0f
   slli $01, $01, 4
   or   $01, $01, $02
   srli $02, $01, 8
   andi $02, $02, 0xff
   andi $01, $01, 0xff
   slli $01, $01, 8
   or   $01, $01, $02
   # result in $01

Обратите внимание, что вы можете одновременно обратить 2x16 бит, просто удвоив константы (и даже 4 на 64-битных машинах). Но я не уверен, что это полезно в вашем случае.

Для очень простого и эффективного подхода используйте 256-байтовую таблицу поиска и выполните 2 поиска:

extern unsigned char const xtable[256];

unsigned int ref = 4149;
unsigned int rev = (xtable[ref & 0xFF] << 8) | xtable[ref >> 8];

Массив xtable можно статически инициализировать с помощью набора макросов:

#define S(x)  ((((x) & 0x0003) << 14) | (((x) & 0x000C) << 10) | \
               (((x) & 0x0030) <<  6) | (((x) & 0x00C0) <<  2) | \
               (((x) & 0xC000) >> 14) | (((x) & 0x3000) >> 10) | \
               (((x) & 0x0C00) >>  6) | (((x) & 0x0300) >>  2))
#define X8(m,n)   m((n)+0), m((n)+1), m((n)+2), m((n)+3), \
                  m((n)+4), m((n)+5), m((n)+6), m((n)+7)
#define X32(m,n)  X8(m,(n)), X8(m,(n)+8), X8(m,(n)+16), X8(m,(n)+24)

unsigned char const xtable[256] = {
    X32(S,   0), X32(S,  32), X32(S,  64), X32(S,  96),
    X32(S, 128), X32(S, 160), X32(S, 192), X32(S, 224),
};

#undef S
#undef X8
#undef X32

Если пространство не дорого, вы можете использовать один просмотр таблицы размером 128 КБ, которую вы будете вычислять во время запуска или генерировать с помощью скрипта и включать во время компиляции, но это несколько расточительно и не очень кэш удобно.