c - 如何对像素数据进行位条带化？

Question

我有 3 个缓冲区，其中包含在 32 位处理器上运行的 R、G、B 位数据。

我需要按以下方式组合三个字节：

R[0] = 0b r1r2r3r4r5r6r7r8
G[0] = 0b g1g2g3g4g5g6g7g8
B[0] = 0b b1b2b3b4b5b6b7b8

int32_t Out = 0b r1g1b1r2g2b2r3g3 b3r4g4b4r5g5b5r6 g6b6r7g7b7r8g8b8 xxxxxxxx

其中 xxxxxxxx 继续到缓冲区中的每个下一个字节。

我正在寻找一种将它们结合起来的最佳方式。我的方法绝对没有效率。

这是我的方法

static void rgbcombineline(uint8_t line)
{
    uint32_t i, bit;
    uint8_t bitMask, rByte, gByte, bByte;
    uint32_t ByteExp, rgbByte;
    uint8_t *strPtr = (uint8_t*)&ByteExp;

    for (i = 0; i < (LCDpixelsCol / 8); i++)
    {
        rByte = rDispbuff[line][i];
        gByte = gDispbuff[line][i];
        bByte = bDispbuff[line][i];

        bitMask = 0b00000001;
        ByteExp = 0;
        for(bit = 0; bit < 8; bit++)
        {
            rgbByte = 0;
            rgbByte |= ((rByte & bitMask) >> bit) << 2;
            rgbByte |= ((gByte & bitMask) >> bit) << 1;
            rgbByte |= ((bByte & bitMask) >> bit);
            ByteExp |= (rgbByte << 3*bit);
            bitMask <<= 1;
        }
        TempLinebuff[((i*3)+0) +2] = *(strPtr + 2);
        TempLinebuff[((i*3)+1) +2] = *(strPtr + 1);
        TempLinebuff[((i*3)+2) +2] = *(strPtr + 0);
    }
}

Answer 1

如果您可以节省 1024 字节，则可以使用单个 256 元素查找表来获得所需的结果：

uint32_t lookup[256] = {
    0, 1, 8, 9, 64, 65, ...
    /* map abcdefgh to a00b00c00d00e00f00g00h */
};

uint32_t result = (lookup[rByte] << 2) | (lookup[gByte] << 1) | lookup[bByte];

这仅使用 3 次查找、2 次轮班和 2 次or操作，这应该可以提供可接受的加速。

如果您有更多空间，您也可以使用三个查找表来消除移位（尽管这可能会导致缓存性能变差，因此请始终进行配置文件检查！）

Answer 2

您可以使用乘以“神奇”常数来复制位。然后使用位移来提取所需的位，并使用逐位掩码来组合它们。“神奇”常数是一个 17 位二进制 10000000100000001。乘以它时，任何 8 位数字都会与自身连接 3 次。

r1r2r3r4r5r6r7r8 * M = r1 r2r3r4r5r6r7r8r1r2r3r4 r5 r6r7r8r1r2r3r4r5r6r7r8
r1r2r3r4r5r6r7r8 * M shr 2 = 0 0 r1 r2 r3r4r5r6r7r8r1r2r3r4r5 r6 r7r8r1r2r3r4r5r6
r1r2r3r4r5r6r7r8 * M shr 4 = 0 0 0 0 r1r2 r3 r4r5r6r7r8r1r2r3r4r5r6 r7 r8r1r2r3r4
r1r2r3r4r5r6r7r8 * M shr 6 = 0 0 0 0 0 0 r1r2r3 r4 r5r6r7r8r1r2r3r4r5r6r7 r8 r1r2

以粗体标记的位是位于正确位置的位。

如果您使用此屏蔽代码

R * M        & 0b100000000000100000000000 |
(R * M >> 2) & 0b000100000000000100000000 |
(R * M >> 4) & 0b000000100000000000100000 |
(R * M >> 6) & 0b000000000100000000000100

您将以正确的方式组合“红色”位：

r1 0 0 r2 0 0 r3 0 0 r4 0 0 r5 0 0 r6 0 0 r7 0 0 r8 0 0

然后以类似的方式组合“蓝色”和“绿色”位。

---

粗略估计操作次数：

• 乘法：3
• 位移：9
• 按位与：12
• 按位或：11

Answer 3

您可以使用大小为 64 的表，其中包含 6 位的位剥离值，然后从 r、g 和 b 中分别获取 2 位，并使用表进行更快的查找。使用大小为 512 或 4096 的查找可能更有效。

/* Converts bits abcdefghijkl to adgjbehkcfil */
static const uint32_t bitStripLookUp[4096] = {
  /* Hard coded values, can be generate with some script */
  ...
};

...

rByte = rDispbuff[line][i];  // rByte, gByte, bByte should be unit32
gByte = gDispbuff[line][i];
bByte = bDispbuff[line][i];

uMSB = ((rByte << 4) & 0x0F00) | (gByte & 0x00F0) | ((bByte >> 4) & 0x000F);  // r7r6r5r4g7g6g5g4b7b6b5b4
uLSB = ((rByte << 8) & 0x0F00) | ((gByte << 4) & 0x00F0) | (bByte & 0x000F);  // r3r2r1r0g3g2g1g0b3b2b1b0
stuffed_value = (bitStripLookUp[uMSB] << 12) | bitStripLookUp[uLSB];

Answer 4

与位运算符交错

inline unsigned interleave(unsigned n)
{
    n = ((n << 18) | (n << 9) | n) & 0007007007; // 000000111 000000111 000000111
    n =  ((n << 6) | (n << 3) | n) & 0444444444; // 100100100 100100100 100100100
    return n;
}

unsigned r = interleave(rByte);
unsigned g = interleave(gByte);
unsigned b = interleave(bByte);

unsigned rgb = r | (g >> 1) | (b >> 2);

TempLinebuff[((i*3)+0) +2] = rgb >> 16;
TempLinebuff[((i*3)+1) +2] = rgb >>  8;
TempLinebuff[((i*3)+2) +2] = rgb;

---

查找表解决方案

#define EXPANDBIT(x, n) (((x) & (1 << (n))) << (3*(n))))
#define EXPAND8BIT(a) (EXPANDBIT(a, 0) | EXPANDBIT(a, 1) | EXPANDBIT(a, 2) | EXPANDBIT(a, 3) | \
                       EXPANDBIT(a, 4) | EXPANDBIT(a, 5) | EXPANDBIT(a, 6) | EXPANDBIT(a, 7))
#define EXPAND16(A) EXPAND8BIT(16*(A)+ 0), EXPAND8BIT(16*(A)+ 1), EXPAND8BIT(16*(A)+ 2), EXPAND8BIT(16*(A)+ 3), \
                    EXPAND8BIT(16*(A)+ 4), EXPAND8BIT(16*(A)+ 5), EXPAND8BIT(16*(A)+ 6), EXPAND8BIT(16*(A)+ 7), \
                    EXPAND8BIT(16*(A)+ 8), EXPAND8BIT(16*(A)+ 9), EXPAND8BIT(16*(A)+10), EXPAND8BIT(16*(A)+11), \
                    EXPAND8BIT(16*(A)+12), EXPAND8BIT(16*(A)+13), EXPAND8BIT(16*(A)+14), EXPAND8BIT(16*(A)+15)

const uint32_t LUT[256] = {
    EXPAND16( 0), EXPAND16( 1), EXPAND16( 2), EXPAND16( 3),
    EXPAND16( 4), EXPAND16( 5), EXPAND16( 6), EXPAND16( 7),
    EXPAND16( 8), EXPAND16( 9), EXPAND16(10), EXPAND16(11),
    EXPAND16(12), EXPAND16(13), EXPAND16(14), EXPAND16(15)
};
    
output = LUT[rByte] | LUT[gByte] << 1 | LUT[bByte] << 2;

如果需要，可以增加查找表的大小

---

在带有BMI2的x86 上，有PDEP指令的硬件支持，可以通过内在的_pdep_u32. 解决方案现在要简单得多

output = _pdep_u32(rByte, 044444444U << 8)
       | _pdep_u32(gByte, 022222222U << 8)
       | _pdep_u32(bByte, 011111111U << 8);

---

另一种方法是

使用这种打包技术使用乘法和掩码进行交错

这适用于没有硬件位存储指令但具有快速乘法器的架构

uint32_t expand8bits(uint8_t b)
{
    uint64_t MAGIC = 0x8040201008040201;
    uint64_t MASK  = 0x8080808080808080;
    uint64_t expanded8bits = htobe64((MAGIC*b) & MASK);
    uint64_t result = expanded8bits*0x2108421 & 0x9249000000009000;
    // no need to shift if you want to get the bits in the high part
    return ((result | (result << 30)) & (044444444ULL << 8)) >> 32;
}

uint32_t stripeBits(uint8_t rByte, uint8_t gByte, uint8_t bByte)
{
    return expand8bits(rByte) | (expand8bits(gByte) >> 1) | (expand8bits(bByte) >> 2);
}

它的工作方式是这样的

• 第一步将输入位从a0000000 b0000000 c0000000 d0000000 e0000000 f0000000 g0000000 h0000000扩展abcdefgh到expand8bits
• 然后我们在下一步中通过乘法和掩码将这些间隔的位靠近在一起。之后result包含a00b00c00d00e00f000000000000000000000000000000000g00h000000000000并将准备合并为单个值

使位更接近的幻数是这样计算的

  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000
×                                       10000100001000010000100001 (0x2108421)
  ────────────────────────────────────────────────────────────────
  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000
  000b0000000c0000000d0000000e0000000f0000000g0000000h0000000
+ 000000c0000000d0000000e0000000f0000000g0000000h0000000
  0c0000000d0000000e0000000f0000000g0000000h0000000
  0000d0000000e0000000f0000000g0000000h0000000
  0000000e0000000f0000000g0000000h0000000
  ────────────────────────────────────────────────────────────────
  ac0bd0cebd0ce0dfce0df0egdf0eg0fheg0fh0g0fh0g00h0g00h0000h0000000
& 1001001001001001000000000000000000000000000000001001000000000000 (0x9249000000009000)
  ────────────────────────────────────────────────────────────────
  a00b00c00d00e00f00000000000000000000000000000000g00h000000000000

或者expand8bits可以像这样仅使用 32 位幻数乘法来实现，这可能更简单

uint32_t expand8bits(uint8_t b)
{
    const uint8_t  RMASK_1458   = 0b10011001;
    const uint32_t MAGIC_1458   = 0b00000001000001010000010000000000U;
    const uint32_t MAGIC_2367   = 0b00000000010100000101000000000000U;
    const uint32_t MASK_BIT1458 = 0b10000000010010000000010000000000U;
    const uint32_t MASK_BIT2367 = 0b00010010000000010010000000000000U;
    
    return (((b &  RMASK_1458) * MAGIC_1458) & MASK_BIT1458)
         | (((b & ~RMASK_1458) * MAGIC_2367) & MASK_BIT2367);
}

这里我们将 8 位数字拆分为两个 4 位部分，一个为 1、4、5、8 位，其余为 2、3、6、7 位。幻数是这样的

                          a00de00h                                0bc00fg0
× 00000001000001010000010000000000      × 00000000010100000101000000000000
  ────────────────────────────────        ────────────────────────────────
                a00de00h                              0bc00fg0
+         a00de00h                      +           0bc00fg0
        a00de00h                              0bc00fg0
  a00de00h                                  0bc00fg0
  ────────────────────────────────        ────────────────────────────────
  a00de0ahadedehah0de00h0000000000        000bcbcfgfgbcbcfgfg0000000000000
& 10000000010010000000010000000000      & 00010010000000010010000000000000
  ────────────────────────────────        ────────────────────────────────
  a00000000d00e00000000h0000000000        000b00c00000000f00g0000000000000

看

• 什么是在一个单词中分隔位的快速方法？
• 如何从 8 个布尔值中创建一个字节（反之亦然）？
• 不使用 BMI2 的便携式高效替代 PDEP？