Как преобразовать последовательность из 32 символов (0/1) в 32 бита (uint32_t)? - PullRequest
Новая
       55

Как преобразовать последовательность из 32 символов (0/1) в 32 бита (uint32_t)?

0 голосов
/ 03 декабря 2018

У меня есть массив символов (обычно длиной в тысячи байтов), считанных из файла, все они состоят из 0 и 1 (не '0' и '1', в этом случае я мог бы использовать strtoul).Я хочу упаковать их в отдельные биты, таким образом конвертируя каждый 32 символа в один uint32_t.Должен ли я написать операцию сдвига битов с 32 частями, или есть более разумный способ? 

out[i/32] = 
    data[i] << 31 |
    data[i+1] << 30 |
    data[i+2] << 29 |
    data[i+3] << 28 |
    data[i+4] << 27 |
    data[i+5] << 26 |
    data[i+6] << 25 |
    data[i+7] << 24 |
    data[i+8] << 23 |
    data[i+9] << 22 |
    data[i+10] << 21 |
    data[i+11] << 20 |
    data[i+12] << 19 |
    data[i+13] << 18 |
    data[i+14] << 17 |
    data[i+15] << 16 |
    data[i+16] << 15 |
    data[i+17] << 14 |
    data[i+18] << 13 |
    data[i+19] << 12 |
    data[i+20] << 11 |
    data[i+21] << 10 |
    data[i+22] << 9 |
    data[i+23] << 8 |
    data[i+24] << 7 |
    data[i+25] << 6 |
    data[i+26] << 5 |
    data[i+27] << 4 |
    data[i+28] << 3 |
    data[i+29] << 2 |
    data[i+30] << 1 |
    data[i+31];

Если этот чудовищный сдвиг битов является самым быстрым во время выполнения, то мне придется придерживаться его.

Ответы [ 3 ]

0 голосов
/ 03 декабря 2018

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

Итак, вы хотите что-то вроде этого: 

char bits[32];
// populate bits
uint32_t value = 0;
for (int i=0; i<32; i++) {
    value |= (uint32_t)(bits[i] & 1) << i;
}
0 голосов
/ 03 декабря 2018

Если вам не нужно, чтобы выходные биты отображались точно в том же порядке, что и входные байты, но если вместо этого они могут «чередоваться» определенным образом, то быстрый и переносимый способ сделать это состоит в том, чтобы8 блоков по 8 байтов (всего 64 байта) и объединить все младшие биты в одно 8-байтовое значение.

Что-то вроде: 

uint32_t extract_lsbs2(uint8_t (&input)[32]) {
  uint32_t t0, t1, t2, t3, t4, t5, t6, t7;
  memcpy(&t0, input + 0 * 4, 4);
  memcpy(&t1, input + 1 * 4, 4);
  memcpy(&t2, input + 2 * 4, 4);
  memcpy(&t3, input + 3 * 4, 4);
  memcpy(&t4, input + 4 * 4, 4);
  memcpy(&t5, input + 5 * 4, 4);
  memcpy(&t6, input + 6 * 4, 4);
  memcpy(&t7, input + 7 * 4, 4);

  return 
    (t0 << 0) |
    (t1 << 1) |
    (t2 << 2) |
    (t3 << 3) |
    (t4 << 4) |
    (t5 << 5) |
    (t6 << 6) |
    (t7 << 7);
}

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

Если вы используете uint64_tвместо uint32_t это обычно будет в два раза быстрее (при условии, что у вас есть более 32 байтов для преобразования) на 64-битной платформе.

С SIMD вы можете легко векторизовать всю операцию за что-то вроде двухинструкции (для AVX2, но подойдет любой x86 SIMD ISA): сравните и pmovmskb.

0 голосов
/ 03 декабря 2018

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

Используйте 32-битные инструкции в строке, а затем объедините результаты в одно значение со сдвигами.

Это, вероятно, оптимальный подход для процессоров Intel, но недостатком является то, что эта инструкция медленна для AMD Ryzen.

...