Как вставить нули между битами в растровом изображении?

Question

У меня есть код с высокой производительностью, который выполняет битовые манипуляции.Это может быть сведено к следующей четко определенной задаче:

Учитывая 13-битное растровое изображение, создайте 26-разрядное растровое изображение, которое содержит исходные биты, разнесенные на четные позиции .

Для иллюстрации:

0000000000000000000abcdefghijklm (input, 32 bits)
0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits)

В настоящее время он реализован следующим образом в C:

if (input & (1 << 12))
    output |= 1 << 24;
if (input & (1 << 11))
    output |= 1 << 22;
if (input & (1 << 10))
    output |= 1 << 20;
...

Мой компилятор (MS Visual Studio) превратил это в следующее:

test        eax,1000h
jne         0064F5EC
or          edx,1000000h
... (repeated 13 times with minor differences in constants)

Интересно, смогу ли я сделать это быстрее?Я хотел бы, чтобы мой код был написан на C, но возможно переключение на ассемблер.

• Могу ли я использовать некоторые инструкции MMX / SSE для обработки всех битов одновременно?
• Может бытья могу использовать умножение?(умножьте на 0x11111111 или какую-нибудь другую магическую константу)
• Было бы лучше использовать инструкцию набора условий (SETcc) вместо инструкции условного перехода?Если да, как я могу заставить компилятор создавать такой код для меня?
• Любая другая идея, как сделать это быстрее?
• Любая идея, как сделать обратное преобразование растрового изображения (я должен реализоватьэто тоже немного менее критично)?

Answer 1

Есть умный способ сделать это, который может быть полезен здесь. Это на самом деле решает немного более общую проблему бит-тасования. Ваша проблема имеет ввод:

+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+

.... но давайте рассмотрим все биты:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+

и попытаться чередовать их все так:

+---------------+---------------+---------------+---------------+
|A Q B R C S D a|E b F c G d H e|I f J g K h L i|M j N k O l P m|
+---------------+---------------+---------------+---------------+

Для первого шага рассмотрим среднюю половину ввода:

bit 31        24              16               8               0
 v             v               v               v               v
+---------------+---------------+---------------+---------------+
|               |I J K L M N O P|Q R S a b c d e|               |
+---------------+---------------+---------------+---------------+

Создайте 8-битное значение: {I^Q, J^R, K^S, L^a, M^b, N^c, O^d, P^e}.

Если мы исключаем-ИЛИ это 8-битное значение с битами [15: 8], а также исключаем-ИЛИ то же самое 8-битное значение с битами [23:16], мы поменяем средние два байта: для Например, бит 23 (изначально I) станет I ^ (I^Q) = Q, а бит 15 (первоначально Q) станет Q ^ (I^Q) = I.

Для этого: tmp = (input ^ (input >> 8)) & 0x0000ff00;:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m| input
+---------------+---------------+---------------+---------------+
                            exclusive-OR with:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|A B C D E F G H|I J K L M N O P|Q R S a b c d e| input >> 8
+---------------+---------------+---------------+---------------+

                             -->|want these bits|<--

 mask (bitwise AND) with 0x0000ff00:
+---------------+---------------+---------------+---------------+
|0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1|0 0 0 0 0 0 0 0| 0x0000ff00
+---------------+---------------+---------------+---------------+

Теперь 8-битное значение, которое нам нужно, находится в битах [15: 8], а все остальные биты равны 0. Теперь мы можем сделать обмен с

input ^= (tmp ^ (tmp << 8));

в результате:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m| input
+---------------+---------------+---------------+---------------+

Для следующего шага, разделяй и властвуй ... выполните аналогичный обмен середины биты обеих левой половины:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|               |               |
+---------------+---------------+---------------+---------------+
             becomes
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e|               |               |
+---------------+---------------+---------------+---------------+

... и правая половина:

+---------------+---------------+---------------+---------------+
|               |               |I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
                                             becomes
+---------------+---------------+---------------+---------------+
|               |               |I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+

Мы можем использовать точно такой же трюк, что и на первом шаге, и потому что мы хотим выполнить точно такую ​​же операцию на обеих 16-битных половинах 32-битного слова, мы можем сделать их параллельно:

tmp = (input ^ (input >> 4)) & 0x00f000f0;

создает две пары из 4 битов, которые мы будем использовать для обмена, а затем

input ^= (tmp ^ (tmp << 4));

на самом деле делает своп.

Мы можем продолжать применять тот же принцип, пока обмен не будет завершен. Биты, которые участвуют в обмене в каждой точке, отмечены #:

+---------------+---------------+---------------+---------------+
|A B C D E F G H|I J K L M N O P|Q R S a b c d e|f g h i j k l m|
+---------------+---------------+---------------+---------------+
                 ###############/###############
+---------------+---------------+---------------+---------------+
|A B C D E F G H|Q R S a b c d e|I J K L M N O P|f g h i j k l m|
+---------------+---------------+---------------+---------------+
         #######/#######                 #######/#######
+---------------+---------------+---------------+---------------+
|A B C D Q R S a|E F G H b c d e|I J K L f g h i|M N O P j k l m|
+---------------+---------------+---------------+---------------+
     ###/###         ###/###         ###/###         ###/###
+---------------+---------------+---------------+---------------+
|A B Q R C D S a|E F b c G H d e|I J f g K L h i|M N j k O P l m|
+---------------+---------------+---------------+---------------+
   #/#     #/#     #/#     #/#       #/#   #/#     #/#     #/#
+---------------+---------------+---------------+---------------+
|A Q B R C S D a|E b F c G d G e|I f J g K h L i|M j N k O l P m|
+---------------+---------------+---------------+---------------+

Код:

tmp = (input ^ (input >> 8)) & 0x0000ff00;
input ^= (tmp ^ (tmp << 8));
tmp = (input ^ (input >> 4)) & 0x00f000f0;
input ^= (tmp ^ (tmp << 4));
tmp = (input ^ (input >> 2)) & 0x0c0c0c0c;
input ^= (tmp ^ (tmp << 2));
tmp = (input ^ (input >> 1)) & 0x22222222;
input ^= (tmp ^ (tmp << 1));                    /* = output */

---

Обратную операцию можно выполнить, выполнив 4 шага назад:

tmp = (input ^ (input >> 1)) & 0x22222222;
input ^= (tmp ^ (tmp << 1));                    /* = output */
tmp = (input ^ (input >> 2)) & 0x0c0c0c0c;
input ^= (tmp ^ (tmp << 2));
tmp = (input ^ (input >> 4)) & 0x00f000f0;
input ^= (tmp ^ (tmp << 4));
tmp = (input ^ (input >> 8)) & 0x0000ff00;
input ^= (tmp ^ (tmp << 8));

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

---

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

Answer 2

Сделайте это с помощью справочной таблицы.2 ^ 13 звучат как много записей, но они легко помещаются в кэш процессора.

О, и если в остальных 19 битах есть мусор, сначала нужно их замаскировать.

Answer 3

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

Вот код C для 13 битов. Ниже приведена иллюстрация того, как метод работает с 3 битами, и, надеюсь, обобщение будет ясным.

(Примечание: код развернут циклом. Хороший компилятор сделает это за вас, так что вы можете просто сжать его в цикл.)

</p> <pre><code>unsigned mask, output; unsigned x = input; mask = ((1<<13)-1) << 13; x = (x + mask) & ~mask; mask = ((1<<12)-1) << 12; x = (x + mask) & ~mask; ... mask = ((1<<3)-1) << 3; x = (x + mask) & ~mask; mask = ((1<<2)-1) << 2; x = (x + mask) & ~mask; mask = ((1<<1)-1) << 1; x = (x + mask) & ~mask; output = x;

Теперь вот объяснение метода для 3 битов. Начальное состояние - «00abc». Начните с перемещения 'a' на два места влево, добавив 01100, а затем AND с 10011 (что является битовым НЕ предыдущего номера). Вот как это работает для a = 0,1 (первая стрелка - это сложение, вторая стрелка - это AND):

a = 0: 00abc = 000bc -> 011bc -> 000bc = a00bc
a = 1: 00abc = 001bc -> 100bc -> 100bc = a00bc

Затем переместите 'b' на одну позицию влево, добавив 00010, а затем ANDing с 10101:

b = 0: a00bc = a000c -> a001c -> a000c = a0b0c
b = 1: a00bc = a001c -> a010c -> a010c = a0b0c

Вот и все.

Answer 4

Вы можете сделать:

; eax = input bits
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,2
shr eax,1
shrd edx,eax,8
and edx,0x01555555
; edx = output

Answer 5

Не используйте ветвления:

output =
   (input & 1)
   | ((input & 2) << 1)
   | ((input & 4) << 2)
   | ((input & 8) << 3)
   | ((input & 16) << 4)
   /* etc. */

Вот, возможно, более легкая для чтения / понимания версия того же самого:

output =
     ((input & (1 <<  0)) <<  0)
   | ((input & (1 <<  1)) <<  1)
   | ((input & (1 <<  2)) <<  2)
   | ((input & (1 <<  3)) <<  3)
   | ((input & (1 <<  4)) <<  4)
   | ((input & (1 <<  5)) <<  5)
   | ((input & (1 <<  6)) <<  6)
   | ((input & (1 <<  7)) <<  7)
   | ((input & (1 <<  8)) <<  8)
   | ((input & (1 <<  9)) <<  9)
   | ((input & (1 << 10)) << 10)
   | ((input & (1 << 11)) << 11)
   | ((input & (1 << 12)) << 12);

Answer 6

На процессорах Intel x86, начиная с Haswell, вы можете использовать одну инструкцию pdep из набора BMI2, чтобы сделать это:

uint32_t interleave_zero_bits(uint32_t x) {
    return _pdep_u32(x, 0x55555555U);
}

Answer 7

Во-первых, для ваших «26-битных» значений старший бит всегда должен быть чистым, поэтому на самом деле это 25-битное значение.

1) MMX (и / или SSE) не помогут, так как основная проблема заключается в том, что нет простой серии арифметических или логических операций, которая дает желаемые результаты, и все поддерживает те же арифметические и логические операции.

2) Я не мог придумать или найти магическую константу для умножения.

3) Я не вижу метода использования какой-либо инструкции по набору условий (например, SETcc), которая имеет какие-либо преимущества по сравнению с командами shift / add.

4) jdv и пол (сверху) правы. Если вам нужно делать это преобразование достаточно часто, чтобы производительность имела значение, тогда таблица поиска будет лучшим / быстрым вариантом на современных процессорах. Таблица поиска для «от 13-бит до 26-бит» будет 2 ** 13 слов или 32 КиБ. На старых процессорах (с небольшими кэшами L1) относительная разница между скоростью процессора и оперативной памятью не так плоха, как сейчас.

Если вы не можете сэкономить 32 КиБ для справочной таблицы «от 13 до 25 бит», вы можете разделить 13-битное значение на пару значений (одно 6-битное значение и одно 7-битное значение). ) и затем используйте таблицу соответствия для каждого из этих значений, прежде чем объединять результаты, например:

mov ebx,eax                    ;ebx = 13-bit value
shr eax,6                      ;eax = highest 7 bits of value
and ebx,0x003F                 ;ebx = lowest 6 bits of value
mov eax,[lookup_table + eax*2] ;eax = highest 14-bits of result
mov ebx,[lookup_table + ebx*2] ;eax = lowest 12-bits of result
shl eax,12
or eax,ebx                     ;eax = 25-bit result

В этом случае таблица поиска содержит 128 записей (по 2 байта на запись), поэтому это всего 256 байтов.

5) Для обратной операции простая справочная таблица обойдется вам в 64 МБ (2 ** 25 * 2), так что это не очень хорошая идея. Тем не менее, вы можете разделить 25-битное значение на 13-битное и 11-битное (12-битное значение, где старший бит всегда чист) и использовать таблицу ввода 8192 с одним байтом на запись (всего стоимость 8 КиБ). Нет никакой причины, по которой вы не могли бы разбить 25-битные значения на более / меньшие части (и использовать намного меньшую таблицу).

Answer 8

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

Большинство платформ имеют отдельные инструкции по перемещению и повороту. Почти всегда есть инструкция, которая включает флаги переноса / переполнения, так что вы можете «сдвинуться» немного по своему усмотрению. Допустим, у нас есть эти инструкции: * SHIFTLEFT: делает левое смещение и заполняет младший бит нулем. * ROTATELEFT: выполняет левое смещение, устанавливает младший бит из предыдущего значения в флаге переноса и устанавливает перенос из бита, который был сдвинут «наружу» слева.

псевдокод:

LOAD value into register A;
LOAD 0 into register B;
SHIFT register A (registerwidth-13) times; 
ROTATELEFT A
ROTATELEFT B
SHIFTLEFT  B

... повторить 13 раз. Разворачивай как хочешь.

Первая смена должна установить самый верхний бит прямо перед переносом. ROTATELEFT A вставит MSB в перенос, ROTATELEFT B вставит бит в младший бит B, а SHIFTLEFT B введет 0 в. Сделайте это для всех бит.

---

Редактировать / Добавлено:

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

ЗАГРУЗИТЬ значение в регистр A; ЗАГРУЗИТЬ 0 в регистр B;

ROTATELEFT A; ROTATELEFT A; ROTATELEFT B; ... повторить 13 раз а потом SHIFTLEFT B; для (registerwidth-13) раз.

LSB для переноски; Забудьте об этом, следующий LSB в переносе, поместите это в целевой регистр, повторите для всех битов, затем выровняйте результат.

Answer 9

Я думаю это может быть актуально, но я не совсем уверен.Я знаю инструкции MMX для чередования байтов 32/64 битных значений, но не отдельных битов.

Answer 10

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