如何对像素数据进行位条带化处理？
我有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 > bit) <> bit) <> 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); } }
如果您可以节省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操作，这应该提供可接受的加速。
如果你有更多的空间，你可以使用三个查找表来消除变化（虽然这可能导致更糟糕的缓存性能，所以总是要检查配置文件！）
您可以使用乘以“魔法”常量来复制这些位。 然后使用位移来提取所需的位，并使用逐位屏蔽来组合它们。 “魔法”常量是一个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
- 按位AND：12
- 按位OR：11
您可以使用大小为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];
与按位运算符交错
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); }
它的工作方式是这样的
- 第一步将输入位从
abcdefgh扩展到a0000000 b0000000 c0000000 d0000000 e0000000 f0000000 g0000000 h0000000并存储在expand8bits - 然后我们通过在下一步中进行乘法和屏蔽来将那些间隔开的位靠近在一起。 之后该
result包含a00b00c00d00e00f000000000000000000000000000000000000h000000000000并准备合并为单个值
使这些位更接近的神奇数字就像这样计算
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个bool值创建一个字节（反之亦然）？
- 在不使用BMI2的情况下便携式有效替代PDEP？