Бит-взлом: разворачивание бит

Ответ 1

Перемешивание битов по двоичным номерам магов содержало ключ:

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. Операторы | в первых четырех шагах могут быть заменены операторами ^. Маски также могут быть изменены, поскольку некоторые биты естественно нулевые и их не нужно очищать. На некоторых процессорах короткие маски могут быть включены в машинные инструкции как незамедлительные, уменьшая усилия для конструирования и/или загрузки констант маски. Также может быть полезно увеличить уровень parallelism на уровне инструкций для процессоров без порядка и оптимизировать для тех, у кого есть команды 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;
}

Ответ 2

Самый простой способ сопоставить 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;
}

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

Ответ 3

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

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

Ответ 4

Здесь выполняется рабочая реализация:

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 маскируется и сохраняется.

Этот бит затем сдвигается по его позиции бита и ORed в результат, а затем снова сдвигается по его позиции бита плюс 1 и ORed в результат.

Ответ 5

Простой цикл. Может быть, не слишком взломано?

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(). Представляется, что это будет самое быстрое решение с итерацией цикла.

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;
}

Ответ 6

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

Если эта таблица слишком большая по своему вкусу, вы можете ее разбить. Например, вы можете использовать 8-битную таблицу поиска с 256 элементами по 2 байта каждая. Благодаря этому вы можете выполнить всю операцию всего двумя способами поиска. Бонус заключается в том, что этот подход позволяет использовать трюки типа-punning, чтобы избежать проблем с расщеплением адреса с помощью бит-операций:

//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;
}

В приведенном выше коде строятся правила строгого сглаживания, используя только /from char, что является явным исключением из правил строгих правил псевдонимов. Он также работает с эффектами малого/большого числа байтов, создавая результат в том же порядке, что и вход. Тем не менее, он по-прежнему раскрывает поведение, определенное определением: машина с порядком байтов 1, 0, 3, 2 или другим заказами среднего порядка будет молча производить неправильные результаты (на самом деле были такие процессоры, как PDP11...).

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

Ответ 7

Попробуйте, где 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

Ответ 8

Мое решение предназначено для работы на обычных ПК x86 и быть простым и универсальным. Я не писал этого, чтобы конкурировать за самую быструю и/или самую короткую реализацию. Это просто еще один способ решить проблему, представленную OP.

#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;
}