Взлом битов: расширение битов
Я пытаюсь преобразовать uint16_t вход в uint32_t немного маски Один бит на входе переключает два бита в выходной битовой маске. Вот пример преобразования 4-битного ввода в 8-битную маску:
Input Output
ABCDb -> AABB CCDDb
A,B,C,D are individual bits
Example outputs:
0000b -> 0000 0000b
0001b -> 0000 0011b
0010b -> 0000 1100b
0011b -> 0000 1111b
....
1100b -> 1111 0000b
1101b -> 1111 0011b
1110b -> 1111 1100b
1111b -> 1111 1111b
Есть ли хитрый способ добиться такого поведения?
9 ответов
Чередование битов с помощью двоичных магических чисел содержало ключ:
uint32_t expand_bits(uint16_t bits)
{
uint32_t x = bits;
x = (x | (x << 8)) & 0x00FF00FF;
x = (x | (x << 4)) & 0x0F0F0F0F;
x = (x | (x << 2)) & 0x33333333;
x = (x | (x << 1)) & 0x55555555;
return x | (x << 1);
}
Первые четыре шага последовательно чередуют исходные биты в группах по 8, 4, 2, 1 бит с нулевыми битами, что приводит к 00AB00CD после первого шага, 0A0B0C0D после второго шага и тд. Последний шаг затем дублирует каждый четный бит (содержащий исходный бит источника) в соседний нечетный бит, тем самым достигая желаемого расположения битов.
Возможны несколько вариантов. Последний шаг также может быть закодирован как x + (x << 1) или же 3 * x, | операторы в первых четырех шагах могут быть заменены ^ операторы. Маски также могут быть изменены, так как некоторые биты, естественно, равны нулю и не требуют очистки. На некоторых процессорах короткие маски могут быть включены в машинные инструкции как непосредственные, уменьшая трудозатраты на создание и / или загрузку констант маски. Также может быть выгодно увеличить параллелизм на уровне команд для процессоров, вышедших из строя, и оптимизировать их с помощью команд shift-add или integer-multiply-add. Один вариант кода, включающий различные из этих идей:
uint32_t expand_bits (uint16_t bits)
{
uint32_t x = bits;
x = (x ^ (x << 8)) & ~0x0000FF00;
x = (x ^ (x << 4)) & ~0x00F000F0;
x = x ^ (x << 2);
x = ((x & 0x22222222) << 1) + (x & 0x11111111);
x = (x << 1) + x;
return x;
}
Самый простой способ сопоставить 4-битный вход с 8-битным выходом - это 16-элементная таблица. Так что это просто вопрос извлечения 4 бит за раз из uint16_tвыполнение поиска в таблице и вставка 8-битного значения в вывод.
uint32_t expandBits( uint16_t input )
{
uint32_t table[16] = {
0x00, 0x03, 0x0c, 0x0f,
0x30, 0x33, 0x3c, 0x3f,
0xc0, 0xc3, 0xcc, 0xcf,
0xf0, 0xf3, 0xfc, 0xff
};
uint32_t output;
output = table[(input >> 12) & 0xf] << 24;
output |= table[(input >> 8) & 0xf] << 16;
output |= table[(input >> 4) & 0xf] << 8;
output |= table[ input & 0xf];
return output;
}
Это обеспечивает достойный компромисс между производительностью и удобочитаемостью. Он не обладает достаточной производительностью решения для поиска через cmaster, но, безусловно, более понятен, чем решение волшебной загадки thndrwrks. Как таковой, он предоставляет метод, который может быть применен к гораздо большему разнообразию проблем, то есть использовать небольшую справочную таблицу для решения более крупной проблемы.
Если вы хотите получить некоторую оценку относительной скорости, протестируйте код в вики-сообществе. Отрегулируйте по мере необходимости.
void f_cmp(uint32_t (*f1)(uint16_t x), uint32_t (*f2)(uint16_t x)) {
uint16_t x = 0;
do {
uint32_t y1 = (*f1)(x);
uint32_t y2 = (*f2)(x);
if (y1 != y2) {
printf("%4x %8lX %8lX\n", x, (unsigned long) y1, (unsigned long) y2);
}
} while (x++ != 0xFFFF);
}
void f_time(uint32_t (*f1)(uint16_t x)) {
f_cmp(expand_bits, f1);
clock_t t1 = clock();
volatile uint32_t y1 = 0;
unsigned n = 1000;
for (unsigned i = 0; i < n; i++) {
uint16_t x = 0;
do {
y1 += (*f1)(x);
} while (x++ != 0xFFFF);
}
clock_t t2 = clock();
printf("%6llu %6llu: %.6f %lX\n", (unsigned long long) t1,
(unsigned long long) t2, 1.0 * (t2 - t1) / CLOCKS_PER_SEC / n,
(unsigned long) y1);
fflush(stdout);
}
int main(void) {
f_time(expand_bits);
f_time(expandBits);
f_time(remask);
f_time(javey);
f_time(thndrwrks_expand);
// now in the other order
f_time(thndrwrks_expand);
f_time(javey);
f_time(remask);
f_time(expandBits);
f_time(expand_bits);
return 0;
}
Результаты
0 280: 0.000280 FE0C0000 // fast
280 702: 0.000422 FE0C0000
702 1872: 0.001170 FE0C0000
1872 3026: 0.001154 FE0C0000
3026 4399: 0.001373 FE0C0000 // slow
4399 5740: 0.001341 FE0C0000
5740 6879: 0.001139 FE0C0000
6879 8034: 0.001155 FE0C0000
8034 8470: 0.000436 FE0C0000
8486 8751: 0.000265 FE0C0000
Вот рабочая реализация:
uint32_t remask(uint16_t x)
{
uint32_t i;
uint32_t result = 0;
for (i=0;i<16;i++) {
uint32_t mask = (uint32_t)x & (1U << i);
result |= mask << (i);
result |= mask << (i+1);
}
return result;
}
На каждой итерации цикла этот бит из uint16_t маскируется и сохраняется.
Затем этот бит сдвигается на свою битовую позицию и OR в результат, затем снова сдвигается на свою битовую позицию плюс 1 и ORed в результат.
Если вас беспокоит производительность и простота, вам лучше всего использовать большую справочную таблицу (64 тыс. Записей по 4 байта каждая). При этом вы можете в значительной степени использовать любой алгоритм, который вам нравится для генерации таблицы, поиск будет просто доступ к памяти.
Если этот стол слишком большой для вашего вкуса, вы можете разделить его. Например, вы можете использовать 8-битную таблицу поиска с 256 записями по 2 байта каждая. При этом вы можете выполнить всю операцию всего за два поиска. Преимущество состоит в том, что этот подход позволяет использовать хитрости, чтобы избежать проблем с разделением адреса с помощью битовых операций:
//Implementation defined behavior ahead:
//Works correctly for both little and big endian machines,
//however, results will be wrong on a PDP11...
uint32_t getMask(uint16_t input) {
assert(sizeof(uint16_t) == 2);
assert(sizeof(uint32_t) == 4);
static const uint16_t lookupTable[256] = { 0x0000, 0x0003, 0x000c, 0x000f, ... };
unsigned char* inputBytes = (unsigned char*)&input; //legal because we type-pun to char, but the order of the bytes is implementation defined
char outputBytes[4];
uint16_t* outputShorts = (uint16_t*)outputBytes; //legal because we type-pun from char, but the order of the shorts is implementation defined
outputShorts[0] = lookupTable[inputBytes[0]];
outputShorts[1] = lookupTable[inputBytes[1]];
uint32_t output;
memcpy(&output, outputBytes, 4); //can't type-pun directly from uint16 to uint32_t due to strict aliasing rules
return output;
}
Приведенный выше код работает вокруг строгих правил наложения имен, приводя только к / из char, что является явным исключением из строгих правил наложения имен. Он также работает вокруг эффектов порядка байтов little/big-endian, создавая результат в том же порядке, в котором входные данные были разделены. Тем не менее, он по-прежнему предоставляет поведение, определяемое реализацией: машина с порядком байтов 1, 0, 3, 2или другие порядки среднего порядка молча будут давать неправильные результаты (на самом деле были такие процессоры, как PDP11...).
Конечно, вы можете разделить таблицу поиска еще дальше, но я сомневаюсь, что это вам поможет.
Простая петля. Может быть, недостаточно хакерский?
uint32_t thndrwrks_expand(uint16_t x) {
uint32_t mask = 3;
uint32_t y = 0;
while (x) {
if (x&1) y |= mask;
x >>= 1;
mask <<= 2;
}
return y;
}
Пробовал другой, который в два раза быстрее. Все еще 655/272 так медленно, как expand_bits(), Представляется самым быстрым итерационным решением с 16 циклами.
uint32_t thndrwrks_expand(uint16_t x) {
uint32_t y = 0;
for (uint16_t mask = 0x8000; mask; mask >>= 1) {
y <<= 1;
y |= x&mask;
}
y *= 3;
return y;
}
Попробуйте это, где input16 является маской ввода uint16_t:
uint32_t input32 = (uint32_t) input16;
uint32_t result = 0;
uint32_t i;
for(i=0; i<16; i++)
{
uint32_t bit_at_i = (input32 & (((uint32_t)1) << i)) >> i;
result |= ((bit_at_i << (i*2)) | (bit_at_i << ((i*2)+1)));
}
// result is now the 32 bit expanded mask
Мое решение предназначено для работы на обычных компьютерах x86 и должно быть простым и универсальным. Я не писал это, чтобы конкурировать за самую быструю и / или самую короткую реализацию. Это просто еще один способ решить проблему, представленную ОП.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define BITS_TO_EXPAND (4U)
#define SIZE_MAX (256U)
static bool expand_uint(unsigned int *toexpand,unsigned int *expanded);
int main(void)
{
unsigned int in = 12;
unsigned int out = 0;
bool success;
char buff[SIZE_MAX];
success = expand_uint(&in,&out);
if(false == success)
{
(void) puts("Error: expand_uint failed");
return EXIT_FAILURE;
}
(void) snprintf(buff, (size_t) SIZE_MAX,"%u expanded is %u\n",in,out);
(void) fputs(buff,stdout);
return EXIT_SUCCESS;
}
/*
** It expands an unsigned int so that every bit in a nibble is copied twice
** in the resultant number. It returns true on success, false otherwise.
*/
static bool expand_uint(unsigned int *toexpand,unsigned int *expanded)
{
unsigned int i;
unsigned int shifts = 0;
unsigned int mask;
if(NULL == toexpand || NULL == expanded)
{
return false;
}
*expanded = 0;
for(i = 0; i < BIT_TO_EXPAND; i++)
{
mask = (*toexpand >> i) & 1;
*expanded |= (mask << shifts);
++shifts;
*expanded |= (mask << shifts);
++shifts;
}
return true;
}
Я немного опоздал на вечеринку, но вот общий алгоритм расширения битовых масок. Мне нужно было расширить 8-битную маску до 64-битного целого числа... Надеюсь, кто-нибудь найдет этот алгоритм полезным.
Вероятно, это не самый быстрый способ, но он работает для любого произвольного количества битов и коэффициента расширения в пределах аппаратных ограничений.
unsigned long expand_bitmask(unsigned long mask, unsigned nbits_in, unsigned expand_by)
{
unsigned long result, mask_out;
int i, shift;
assert(nbits_in * expand_by <= 8 * sizeof(unsigned));
// mask input
mask &= (unsigned long)(-1) >> ((8 * sizeof(unsigned long)) - nbits_in);
result = 0; // holds results
mask_out = 0;
for (i = 0, shift = 0; i < nbits_in; ++i, shift += expand_by)
{
result |= (mask << (shift - i)); // the shift differential places the bits
// in the right place.
// equivalent to mask << (i * (shift - 1))
mask_out |= (1 << shift); // this will mask the shited bits we want to keep
// equivalent to 1 << (i * shift)
}
result &= mask_out; // wipe out the garbage bits
// multiply by a mask representing the number of wanted bits.
result *= (unsigned long)(-1) >> ((8* sizeof(unsigned long)) - expand_by);
return result;
}
Конечно, поскольку вы обычно знаете количество входящих и выходящих битов, алгоритм может помочь вам предварительно вычислить сдвиги, маску очистки и коэффициент для довольно быстрого времени вычисления: 1 сдвиг на бит + 1 и 1 общее количество операций умножения.
Для исходного вопроса это дает:
input_mask &= 0b11;
result = input_mask;
result |= (input_mask << 1); // 1 * (2 bits out - 1)
result = (result & 0b0101) * 0b0011; // mask has bits set every 2 bits.
// mutiplied by 2 set bits for expansion