Как разветвляться на двоичном

Я хочу разложить двоичные данные, как в следующих примерах:

8 bit to 16 bit: 
     0 0 0 1   0 0 0 1  (0x11)    becomes 
    0000 0011 0000 0011 (0x0303)

8 bit to 32 bit: 
       0    1    0    0    0    1    1    0 (0x46)       becomes 
    0000 1111 0000 0000 0000 1111 1111 0000 (0x0F000FF0)

16 to 32 bit: 
     0 0 0 1   0 0 1 1   0 1 1 1   1 1 1 1  (0x137F)     becomes 
    0000 0011 0000 1111 0011 1111 1111 1111 (0x030F3FFF)

Поскольку этот вопрос помечен тегом bit-manipulation, я ищу компактное решение без каких-либо циклов или дополнительных переменных. Код также должен быть независимым от платформы, поэтому встроенная сборка - это не то, что мне нужно.

Это может быть повторяющийся вопрос, но я не знаю, как его искать. Безусловно, у того, чем я хочу заниматься, есть собственное название, но я его просто не знаю.

Обновлено: Чтобы прояснить некоторые из ваших комментариев, вот список методов, которые решение должно содержать нет:

  • код сборки (зависит от платформы)
  • "сложные" вычисления, такие как циклы (поэтому я пометил этот вопрос с помощью bit-fiddling)
  • дополнительные переменные времени выполнения (например, вспомогательные константы, таблицы поиска и т. д.)

Поскольку вы просили об этом, вот некоторые дополнительные сведения о моем варианте использования: я работаю над встроенными платформами (микроконтроллерами) и хочу замаскировать регистры. Этот конкретный случай касается регистров ввода-вывода, где у меня есть 16 контактных площадок для каждого порта и несколько регистров портов для настройки контактных площадок. Некоторые из этих регистров конфигурации используют 2 бита на контактную площадку, некоторые - 4 бита. Поэтому, если я хочу замаскировать отдельные контактные площадки при доступе к регистрам, мне нужно соответствующим образом замаскировать эти регистры.

Допустим, у меня есть два регистра конфигурации и я хочу получить доступ к площадкам 4 и 8:

uint32_t configreg_2perpad;       // the first configuration register
uint32_t configreg_4perpad_low;   // lower half of the second configuration register
uint32_t configreg_4perpad_high;  // higher half of the second configuration register

uint8_t pad4 = 3;                 // we start counting at 0, of course
uint8_t pad8 = 7;
uint16_t pad_mask = (1 << pad4) |
                    (1 << pad8);  // this is now 0x0088

Итак, сейчас я ищу побитовую манипуляцию с pad_mask, чтобы получить соответствующие маски для регистров, которые были бы

uint32_t configreg_2perpad_mask = 0x0000C0C0;
uint32_t configreg_4perpad_low_mask = 0xF000F000;
uint32_t configreg_4perpad_high_mask = 0x00000000;

Очевидно, поскольку память (как ОЗУ, так и флеш-память) является очень ограниченным ресурсом для микроконтроллеров, я бы предпочел решение без необходимости в дополнительных статических переменных, таких как таблицы поиска (трата ОЗУ) или статические функции (трата флеш-памяти).

Это правильный пример "от 16 до 32 бит"?

Tormund Giantsbane 13.09.2018 18:14

Можете ли вы предоставить ссылку на операцию, которую пытаетесь выполнить? Или как работает трансформация?

njras 13.09.2018 18:25

Я буквально вставлял ответ, когда этот вопрос был закрыт. Мы можем снова открыть?

selbie 13.09.2018 18:30

Чтобы было ясно, хотите ли вы, чтобы каждый бит превращался в несколько битов, как при манипуляции со строкой, которая повторяет каждый символ?

Tim Randall 13.09.2018 18:57

Вы можете использовать ту же идею, что и здесь, для чередования 16-битного int с нулевыми битами. Вам понадобится только часть x: x = (x | (x << S[3])) & B[3]; x = (x | (x << S[2])) & B[2]; x = (x | (x << S[1])) & B[1]; x = (x | (x << S[0])) & B[0];. Затем, чтобы дублировать биты, просто умножьте x на 0b11. Это должно дать правильный ответ. От 8 до 32 бит: дважды чередовать нулевые биты и умножать на 0b1111.

wim 13.09.2018 22:30

Обратите внимание, что на x86 с BMI2 вы можете сделать что-то вроде r = _pdep_u32(x, 0x55555555); r = r * 0b11;, который компилируется только в 2 инструкции. Но, очевидно, это не зависит от платформы, которая вам нужна. Более того, он медленный на AMD (но быстрый на Intel).

wim 13.09.2018 22:43

Хотя для случая с 8 битами на 32 бит более эффективно адаптировать массивы B и S, вместо двойного чередования с нулевыми битами. Для 8 -> 32 необходимы всего три ступени x = (x | (x << S[i])) & B[i];.

wim 13.09.2018 23:01

Вы рассматривали поисковую таблицу?

Ulrich Eckhardt 13.09.2018 23:17

@wim Хороший ответ! Я попробовал, и он отлично справляется со своей задачей. Однако я выбрал метод, предложенный selbie, поскольку в моем случае он немного более эффективен.

Thargon 14.09.2018 14:09

@Thargon Это очень удивительно. Может, на вашей платформе умножение стоит дорого? Этого легко избежать, о чем свидетельствует ответ user3386109's.

wim 15.09.2018 00:13

@wim: Я выбрал решение selbies из-за меньшей таблицы поиска (16 против 20 байт). Однако ответ user3386109, вероятно, будет настолько быстрым, насколько это возможно в моем случае.

Thargon 17.09.2018 13:41
2
11
175
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Предполагая, что 8 бит на байт. 2-х комплементарная арка.

Вот с чего я начал:

uint32_t Eight_To_Sixteen(const uint8_t source)
{

    uint32_t result = (source & 1);
    result |= ((source & 2) << 1);        
    result |= ((source & 4) << 2);
    result |= ((source & 8) << 3);
    result |= ((source & 0x10) << 4);
    result |= ((source & 0x20) << 5);
    result |= ((source & 0x40) << 6);
    result |= ((source & 0x80) << 7);
    return (result | (result << 1));
}

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

А затем я начал сравнивать с подходом поиска по 2-битной таблице:

uint32_t Eight_To_Sixteen(const uint8_t source)
{
    static const int table[] = { 0, 3, 0xc, 0xf };
    uint32_t result = table[(source & 0x03)];
    result |= (table[(source & 0x0c)>>2]) << 4;
    result |= (table[(source & 0x30) >> 4]) << 8;
    result |= (table[(source & 0xc0) >> 6]) << 12;
    return result;
}

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

@ user3386109 - Я думаю, ОП изменил свой вопрос с этим требованием после того, как я написал свой ответ. Во всяком случае, у меня есть несколько уточненных предложений.

selbie 14.09.2018 10:52

Танки за ответ, @selbie! Я немного изменил ваш код (см. coliru.stacked-crooked.com/view?id=492cd5e87c6f1400), чтобы он идеально соответствовал моему варианту использования.

Thargon 14.09.2018 14:07
Ответ принят как подходящий

Преобразование 8 бит в 16 можно выполнить несколькими строками кода:

uint16_t n = 0x11;
n = (n | (n << 4)) & 0x0f0f;
n = (n | (n << 2)) & 0x3333;
n = (n | (n << 1)) & 0x5555;
n = (n | (n << 1));
printf("0x%04x\n", n);  // prints 0x0303

Вот как это работает. Начнем с 8 бит в 16-битной переменной:

0000 0000 abcd efgh     // letters a to h represent the bits of the 8-bit number

Сдвиг влево на 4 бита и ИЛИ: n = n | (n << 4)

0000 abcd ???? efgh     // bits with a '?' are garbage we don't want

Маска от мусора: n = n & 0x0f0f

0000 abcd 0000 efgh

Сдвиг влево на 2 бита и ИЛИ: n = n | (n << 2)

00ab ??cd 00ef ??gh

Маска от мусора: n = n & 0x3333

00ab 00cd 00ef 00gh

Сдвиг влево на 1 бит и ИЛИ: n = n | (n << 1)

0a?b 0c?d 0e?f 0g?h

Маска от мусора: n = n & 0x5555

0a0b 0c0d 0e0f 0g0h

Теперь осталось только скопировать биты: n = n | (n << 1)

aabb ccdd eeff gghh

Это также можно сделать с помощью таблицы поиска. Сама таблица имеет размер ровно 16 байт. Объявление его как static const позволяет компилятору поместить таблицу в ПЗУ. Экономия в размере кода (меньшее количество сдвигов и операций маскирования) обычно компенсирует использование ПЗУ таблицей. И метод поиска должен быть быстрее (2 поиска, 2 смены, 1 маска, 1 ИЛИ) вместо (4 смены, 3 маски, 4 ИЛИ)

static const uint8_t table[16] = {
    0x00, 0x03, 0x0c, 0x0f, 0x30, 0x33, 0x3c, 0x3f,
    0xc0, 0xc3, 0xcc, 0xcf, 0xf0, 0xf3, 0xfc, 0xff
};

uint16_t n = 0x11;
n = (table[n >> 4] << 8) | table[n & 0xf];
printf("0x%04x\n", n);  // prints 0x0303

Развертывание с 8 бит на 32 примерно такое же, как с 8 на 16, но требует большего дублирования в конце:

uint32_t n = 0x46;
n = (n | (n << 12)) & 0x000f000f;
n = (n | (n <<  6)) & 0x03030303;
n = (n | (n <<  3)) & 0x11111111;
n = (n | (n << 1));
n = (n | (n << 2));
printf("0x%08x\n", n);  // prints 0x0f000ff0

При альтернативном способе дублирования битов (предложенном @wim) в комментариях следует заменить

n = (n | (n << 1));
n = (n | (n << 2));

с участием

n = (n << 4) - n;

Разветвление от 16 бит до 32 требует дополнительного шага сдвига и маски:

uint32_t n = 0x137f;
n = (n | (n << 8)) & 0x00ff00ff;
n = (n | (n << 4)) & 0x0f0f0f0f;
n = (n | (n << 2)) & 0x33333333;
n = (n | (n << 1)) & 0x55555555;
n = (n | (n << 1));
printf("0x%08x\n", n);  // prints 0x030f3fff

Это именно то, о чем я подумал :), но у меня не было времени записать это правильно, как это сделали вы. Обратите внимание, что вместо n = (n | (n << 1)); n = (n | (n << 2)); вы можете использовать: n = (n << 4) - n;. Это просто умножение на 15.

wim 15.09.2018 00:09

@wim Верно, похоже, это работает. Мне пришлось немного подумать об этом, потому что (n << 4) сдвигает самый старший бит с конца числа.

user3386109 15.09.2018 00:21

@ user3386109 Это даже более эффективно, чем то, что у меня было раньше. Я выбрал решение с поисковой таблицей, поскольку постоянные значения в любом случае должны храниться в ПЗУ, а lut можно эффективно использовать как для разветвления от 16 до 32, так и от 8 до 32 бит. Если кому-то интересно, взгляните на минимальный пример: coliru.stacked-crooked.com/a/8a94c693e4de82fb

Thargon 17.09.2018 13:39

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