Битовое дублирование от 8-битного до 32-битного - PullRequest
Новая
       22

Битовое дублирование от 8-битного до 32-битного

2 голосов
/ 07 марта 2019

Я пытаюсь дублировать 8-битное значение на 32-битное и хотел спросить, возможно ли написать однострочный алгоритм для дублирования битовых значений.

Например: 

1100 1011 -> 1111 1111 0000 0000 1111 0000 1111 1111

Если это возможно, я хотел бы понять, в чем логика этого.

Ответы [ 4 ]

6 голосов
/ 07 марта 2019

Есть только 256 8-битных значений, поэтому простая таблица поиска будет занимать 1 КБ, и поиск будет тривиальным. Трудно поверить, что любой битхак имел бы превосходную производительность.

5 голосов
/ 08 марта 2019

Все просто - решите самый простой случай, затем сделайте более сложные.

Вам просто нужно распределить биты, вставив 3 нулевых бита между ними.Как только это будет сделано, последний шаг: 

x = (x << 0) | (x << 1) | (x << 2) | (x << 3);

Или менее очевидным, но более быстрым способом: 

x = (x << 4) - x;

Случай 1: дублировать 2 бита в 8-битное значение (самый простой). 

+---+---------+---------+
| 0 | _ _ _ _ | _ _ A B |
+---+---------+---------+
| 1 | _ _ _ A | _ _ _ B |
+---+---------+---------+
| 2 | A A A A | B B B B |
+---+---------+---------+

Случай 2: дублировать 4 бита в 16-битное значение.Как?Просто переместите 2 бита в верхнюю часть, чтобы превратить его в корпус 1!Разделяй и властвуй! 

+---+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D |
+---+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D |
+---+---------+---------+---------+---------+
| 2 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D |
+---+---------+---------+---------+---------+
| 3 | A A A A | B B B B | C C C C | D D D D |
+---+---------+---------+---------+---------+

Случай 3: Дублирование 8 битов в 32-битное значение (оригинал). 

+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | _ _ _ _ | _ _ _ _ | _ _ _ _ | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 2 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D | _ _ _ _ | _ _ E F | _ _ _ _ | _ _ G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 3 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D | _ _ _ E | _ _ _ F | _ _ _ G | _ _ _ H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 4 | A A A A | B B B B | C C C C | D D D D | E E E E | F F F F | G G G G | H H H H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+

Может быть достигнуто с помощью кода ниже: 

uint32_t interleave(uint8_t value)
{
    uint32_t x = value;
    x = (x | (x << 12)) /* & 0x000F000F */; // GCC is not able to remove redundant & here
    x = (x | (x <<  6)) & 0x03030303;
    x = (x | (x <<  3)) & 0x11111111;
    x = (x << 4) - x;
    return x;
}

Некоторые тесты для проверки работоспособности: 

TEST_F(test, interleave)
{
    EXPECT_EQ(interleave(0x00), 0x00000000);
    EXPECT_EQ(interleave(0x11), 0x000F000F);
    EXPECT_EQ(interleave(0x22), 0x00F000F0);
    EXPECT_EQ(interleave(0x33), 0x00FF00FF);
    EXPECT_EQ(interleave(0x44), 0x0F000F00);
    EXPECT_EQ(interleave(0x55), 0x0F0F0F0F);
    EXPECT_EQ(interleave(0x66), 0x0FF00FF0);
    EXPECT_EQ(interleave(0x77), 0x0FFF0FFF);
    EXPECT_EQ(interleave(0x88), 0xF000F000);
    EXPECT_EQ(interleave(0x99), 0xF00FF00F);
    EXPECT_EQ(interleave(0xAA), 0xF0F0F0F0);
    EXPECT_EQ(interleave(0xBB), 0xF0FFF0FF);
    EXPECT_EQ(interleave(0xCC), 0xFF00FF00);
    EXPECT_EQ(interleave(0xDD), 0xFF0FFF0F);
    EXPECT_EQ(interleave(0xEE), 0xFFF0FFF0);
    EXPECT_EQ(interleave(0xFF), 0xFFFFFFFF);

    EXPECT_EQ(interleave(0x01), 0x0000000F);
    EXPECT_EQ(interleave(0x23), 0x00F000FF);
    EXPECT_EQ(interleave(0x45), 0x0F000F0F);
    EXPECT_EQ(interleave(0x67), 0x0FF00FFF);
    EXPECT_EQ(interleave(0x89), 0xF000F00F);
    EXPECT_EQ(interleave(0xAB), 0xF0F0F0FF);
    EXPECT_EQ(interleave(0xCD), 0xFF00FF0F);
    EXPECT_EQ(interleave(0xEF), 0xFFF0FFFF);
}
3 голосов
/ 08 марта 2019

Таблица поиска, предложенная в ответе от rici , обеспечит самую высокую производительность на большинстве платформ.Если вы предпочитаете подход с переворотом, оптимальное решение будет зависеть от аппаратных возможностей вашего процессора, например, от того, насколько быстры сдвиги, имеет ли он логические операции с тремя входами (например, мой графический процессор), сколько целочисленных инструкций он может выполнить впараллельно?Одно из решений состоит в том, чтобы перенести каждый бит в lsb его целевого полубайта, а затем заполнить каждый полубайт значением lsb на втором шаге (подсказка к chqrlie для предложения использования lsb вместоmsb): 

#include <stdint.h>
uint32_t expand_bits_to_nibbles (uint8_t x)
{
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = ((((uint32_t)x << (4*0-0)) & (1u << (4*0))) |
         (((uint32_t)x << (4*1-1)) & (1u << (4*1))) |
         (((uint32_t)x << (4*2-2)) & (1u << (4*2))) |
         (((uint32_t)x << (4*3-3)) & (1u << (4*3))) |
         (((uint32_t)x << (4*4-4)) & (1u << (4*4))) |
         (((uint32_t)x << (4*5-5)) & (1u << (4*5))) |
         (((uint32_t)x << (4*6-6)) & (1u << (4*6))) |
         (((uint32_t)x << (4*7-7)) & (1u << (4*7))));
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

Некоторые быстрые эксперименты с Compiler Explorer показывают, что это приводит к особенно эффективному коду , например, в PowerPC64.

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

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul (uint8_t x)
{
    const uint32_t spread3 = (1u <<  6) | (1u <<  3) | (1u <<  0);
    const uint8_t bits_lo3 = (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_md3 = (1u <<  5) | (1u <<  4) | (1u <<  3);
    const uint8_t bits_hi2 = (1u <<  7) | (1u <<  6);
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) | 
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = (((uint32_t)(x & bits_lo3) * (spread3 <<  0)) +
         ((uint32_t)(x & bits_md3) * (spread3 <<  9)) +
         ((uint32_t)(x & bits_hi2) * (spread3 << 18))) & nib_lsb;
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

Другой вариант, использующий целочисленное умножение, который потенциально быстрее на некоторых платформах, использует идею из этот ответ .Мы используем умножение, чтобы распределить четыре бита за раз, так что они попадают в целевой клочок.Однако затем мы должны переместить бит внутри полуба в lsb полубайта, прежде чем мы сможем расширить lsb, чтобы покрыть полубайт.Мы потенциально экономим умножение за счет дополнительной уборки. 

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul2 (uint8_t x)
{
    const uint32_t spread4 = (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t extract = (1u << (3*4+3+16)) | (1u << (2*4+2+16)) | 
                             (1u << (1*4+1+16)) | (1u << (0*4+0+16)) |
                             (1u << (3*4+3+ 0)) | (1u << (2*4+2+ 0)) | 
                             (1u << (1*4+1+ 0)) | (1u << (0*4+0+ 0));
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) |
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t nib_msb = (nib_lsb << 3);
    const uint8_t bits_lo4 = (1u <<  3) | (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_hi4 = (1u <<  7) | (1u <<  6) | (1u <<  5) | (1u <<  4);
    uint32_t r;
    /* spread bits to their target nibbles */
    r = (((uint32_t)(x & bits_lo4) * (spread4 <<  0)) +  
         ((uint32_t)(x & bits_hi4) * (spread4 << 12)));
    /* extract appropriate bit in each nibble and move it into nibble's lsb */
    r = (((r & extract) + (nib_msb - extract)) >> 3) & nib_lsb;
    /* fill in each nibble with its lsb */
    r = (r << 4) - r;
    return r;
}
3 голосов
/ 07 марта 2019

Это будет работать: 

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & 0x80 ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & 0x40 ? 0xf << 24 : 0x0;
    output |= a & 0x20 ? 0xf << 20 : 0x0;
    output |= a & 0x10 ? 0xf << 16 : 0x0;

    output |= a & 0x8 ? 0xf << 12 : 0x0;
    output |= a & 0x4 ? 0xf << 8 : 0x0;
    output |= a & 0x2 ? 0xf << 4 : 0x0;
    output |= a & 0x1 ? 0xf : 0x0;

    return output;
}

или это: 

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & (1 << 7) ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & (1 << 6) ? 0xf << 24 : 0x0;
    output |= a & (1 << 5) ? 0xf << 20 : 0x0;
    output |= a & (1 << 4) ? 0xf << 16 : 0x0;

    output |= a & (1 << 3) ? 0xf << 12 : 0x0;
    output |= a & (1 << 2) ? 0xf << 8 : 0x0;
    output |= a & (1 << 1) ? 0xf << 4 : 0x0;
    output |= a & 1 ? 0xf : 0x0;

    return output;
}

еще одно решение: 

unsigned int eToTW (unsigned char a) {     
    return (a & 1 << 7 ? ((unsigned) 0xf) << 28 : 0x0) | 
           (a & 1 << 6 ? 0xf << 24 : 0x0) | 
           (a & 1 << 5 ? 0xf << 20 : 0x0) | 
           (a & 1 << 4 ? 0xf << 16 : 0x0) | 
           (a & 1 << 3 ? 0xf << 12 : 0x0) |
           (a & 1 << 2 ? 0xf << 8 : 0x0) |
           (a & 1 << 1 ? 0xf << 4 : 0x0) |
           (a & 1 ? 0xf : 0x0);
}
...