Изменение порядка вращения долота

StackOverflow https://stackoverflow.com/questions/624538

  •  05-07-2019
  •  | 
  •  

Вопрос

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

Пример:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

Редактировать: Я думал о чем-то вроде это

Просто ради удовольствия и потому, что я был AFTK, я пытаюсь методом перебора найти решения в виде:

((In * C1) >> C2) & 0x7f

Никаких решений не найдено.

Это было полезно?

Решение

Взгляните на выходные данные компилятора вашего "наивного" кода, это может вас удивить.Однажды я сделал что-то подобное, и компилятор (VC ++ 2005) полностью изменил значения всех and и сдвигов для меня, чтобы сделать их более эффективными, например, я уверен, что это удалило бы ваше "(0x001 & In) >> 3".

Но да, если перестановка является фиксированной функцией, то таблица, вероятно, лучше всего.

Обновить

Для смеха я посмотрел на выходные данные компилятора из VC ++ 2005....

Сначала я попробовал использовать постоянное значение для "In", но компилятор ни на йоту не обманулся, он выдал этот код:

mov eax,469h

т. е.это полностью оптимизировало его.

Итак ...Я попробовал ввести правильный ввод и получил это:

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx

Это операции в четыре смены, пять "И", четыре "Или" - неплохо для шести входов.Вероятно, лучше, чем большинство людей могли бы сделать вручную.

Вероятно, он также оптимизирован для выполнения не по порядку, так что это будет меньше тактовых циклов, чем кажется.:-)

Другие советы

Первый шаг, по-видимому, состоит в том, чтобы понять математическое решение и оптимизировать его.

смотрите здесь из немного взломов

Существует множество способов манипулирования битами для обычных операций, т. е.чтобы изменить порядок битов в 32-битном слове (по 10 в каждом из shift, И и ИЛИ, AFAICR).

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

Используйте таблицу подстановки :)

Прежде чем оптимизировать, вы должны убедиться, что ваш "наивный" способ делает то, что вы задумали.Если я превращу ваш код в функцию и запущу этот цикл:

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

Он выдает этот результат, который противоречит комментариям.На самом деле, он теряет биты.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

Чтобы получить перемешивание, которое вы описываете, я бы закодировал его следующим образом:

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top