给定一个32位数字，按特定因子缩放每个字节的有效方法是什么？

Question

给定uint32数字0x12345678（例如RGBW颜色值），我如何高效且动态地缩放其中的每个字节（给定缩放因子0 <= f <= 1（或等效的整数除数））？

我知道我可以做得更长一些（可以通过一个结构将数字分解为各个部分，然后循环依次操作每个部分），但是有没有办法更快地完成而不循环？（静态值映射是另一种方法，但是动态方法更可取。）

编辑：C ++（C思想也很有趣），嵌入式，数百或数千个像素（而不是数百万个）。专门缩放RGBW led。

接下来出现的另一件事-这是gcc，所以允许类型为punning（我已经将其用于类似的事情-我只是想看看是否有比这更好的方法）。

再次编辑：这适用于嵌入式平台（微控制器）。虽然我一直在寻求可以帮助更广泛受众的答案，但我还是故意在语言和算法的背景下询问此问题，而不是针对特定平台和指令集进行优化，因为如果存在平台特定的优化可能会有所不同。

Answer 1

可以通过在多个“满”位上一次更有效地使用乘法来减少乘法次数，而不会在空度上浪费那么多的位。仍然需要一些填充位，以确保一个通道的乘积不会破坏另一通道的结果。使用8位定点标度，并且由于每个通道有8位，因此输出为每个通道16位，因此其中两个uint32_t并排放置。这需要8位填充。因此，R和B（它们之间有8个零）可以一起乘以一个缩放比例，与G和W相同。结果是每个通道16位结果的高8位。所以像这样（未经测试）：

uint32_t RB = RGBW & 0x00FF00FF;
uint32_t GW = (RGBW >> 8) & 0x00FF00FF;
RB *= scale;
GW *= scale;
uint32_t out = ((RB >> 8) & 0x00FF00FF) | (GW & 0xFF00FF00);

的scale是从0..256一个数，其被解释为0..1，在1/256步骤。因此scale = 128相当于将通道值减半，依此类推。

只需在相乘后添加适当的偏差，就可以添加舍入步骤。

乘法执行此操作，其中x不使用结果：

这是一个快速台架，用于比较Timo的注释中的各种缩放方法。

Answer 2

您可以使用移位和掩码直接计算输入值的二乘幂：

unsigned long src_2 = ((src >> 1) & 0x7f7f7f7fUL) + (src & 0x01010101UL);
unsigned long src_4 = ((src >> 2) & 0x3f3f3f3fUL) + ((src >> 1) & 0x01010101UL);
unsigned long src_8 = ((src >> 3) & 0x1f1f1f1fUL) + ((src >> 2) & 0x01010101UL);
unsigned long src_16 = ((src >> 4) & 0x0f0f0f0fUL) + ((src >> 3) & 0x01010101UL);
unsigned long src_32 = ((src >> 5) & 0x07070707UL) + ((src >> 4) & 0x01010101UL);
unsigned long src_64 = ((src >> 6) & 0x03030303UL) + ((src >> 5) & 0x01010101UL);
unsigned long src_128 = ((src >> 7) & 0x01010101UL) + ((src >> 6) & 0x01010101UL);
unsigned long src_256 = ((src >> 7) & 0x01010101UL);

（在这里src_2是src与每个字段由2各自独立划分，src_4是src与每个字段由4分割单独等）。

从0/256到255/256的任何其他分数都可以通过可选地将每个值相加来得出（例如0.75是src_2 + src_4）。如果您的嵌入式系统没有快速乘数（您可以在处理所有像素之前从比例因子预先计算出必要的遮罩），或者如果您确实只需要有限的比例因子集（可以仅对您需要将两个分数的幂组合成一组专门的缩放函数）。

例如，在其内部循环中使用专门的scale-by-0.75功能可以做到：

dest = ((src >> 1) & 0x7f7f7f7fUL) + (src & 0x01010101UL) +
    ((src >> 2) & 0x3f3f3f3fUL) + ((src >> 1) & 0x01010101UL);

尽管不适用于您的用例，但该方法也可以用于预先计算将不同比例因子也应用于矢量每个分量的蒙版。

Answer 3

在讨论中已经提到，最佳解决方案可以\n特定于体系结构。有人还建议在汇编中对其进行编码。\n汇编在可移植性方面有一定的成本，但它也引出了一个\n问题：你是否（以及在多大程度上）可以击败编译器的\n优化器。

\n\n

我在 Arduino 上做了一个实验，它基于 AVR\n微控制器。这是一个非常有限的 8 位哈佛 RISC MCU，带有\nan 8 \xc3\x97 8 \xe2\x86\x92 16 位硬件乘法器。

\n\n

这是简单的实现，使用类型双关来乘以各个字节：

\n\n

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)\n{\n    union {\n        uint32_t value;\n        uint8_t bytes[4];\n    } x = { .value = rgbw };\n    x.bytes[0] = x.bytes[0] * scale >> 8;\n    x.bytes[1] = x.bytes[1] * scale >> 8;\n    x.bytes[2] = x.bytes[2] * scale >> 8;\n    x.bytes[3] = x.bytes[3] * scale >> 8;\n    return x.value;\n}\n

\n\n

使用 gcc 进行编译-Os（通常在这些内存受限的设备中）\n这需要 28 个 CPU 周期来执行，即每个字节 7 个周期。\n编译器足够智能，可以将rgbw和分配x给相同的 CPU\n寄存器，从而避免复制。

\n\n

这是基于哈罗德的回答的版本：

\n\n

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)\n{\n    uint32_t rb = rgbw & 0x00FF00FF;\n    uint32_t gw = (rgbw >> 8) & 0x00FF00FF;\n    rb *= scale;\n    gw *= scale;\n    uint32_t out = ((rb >> 8) & 0x00FF00FF) | (gw & 0xFF00FF00);\n    return out;\n}\n

\n\n

这是一项非常智能的优化，可能会在 32 位\nMCU 上获得回报。然而，在这个小型 8 位处理器上，执行需要 176 个 CPU 周期！生成的程序集具有对库函数的两次调用，\n该函数实现了完整的 32 位乘法，以及许多移动和\n清除寄存器。

\n\n

最后，这是我的内联汇编版本：

\n\n

static inline uint32_t scale_pixel(uint32_t rgbw, uint16_t scale)\n{\n    asm(\n        "tst %B[scale]           \\n\\t"  // test high byte of scale\n        "brne 0f                 \\n\\t"  // if non zero, we are done\n        "mul %A[rgbw], %A[scale] \\n\\t"  // multiply LSB\n        "mov %A[rgbw], r1        \\n\\t"  // move result into place\n        "mul %B[rgbw], %A[scale] \\n\\t"  // same with three other bytes\n        "mov %B[rgbw], r1        \\n\\t"  // ...\n        "mul %C[rgbw], %A[scale] \\n\\t"\n        "mov %C[rgbw], r1        \\n\\t"\n        "mul %D[rgbw], %A[scale] \\n\\t"\n        "mov %D[rgbw], r1        \\n"\n        "0:"\n        : [rgbw] "+r" (rgbw)   // output\n        : [scale] "r" (scale)  // input\n        : "r0", "r1"  // clobbers\n    );\n    return rgbw;\n}\n

\n\n

该函数利用了比例因子不能大于 256 的事实。\n事实上，任何大于 256 的因子都被视为 256，\n这可以被视为一个特征。执行需要 14 个周期，如果规模为 256，则只需\n3 个周期。

\n\n

概括：

\n\n

\n
• 针对 32 位内核优化的版本为 176 个周期
\n
• 天真的类型双关版本的 28 个周期
\n
• 装配版本 14 个周期
\n

\n\n

我从这个实验中得出的结论是，您在这里看到的是架构真正重要的\n那种微优化。如果不假设\n它将运行的架构，你就不能\n认真地尝试在 C 级别对其进行优化。另外，如果速度因素 2 对您来说很重要，那么值得尝试在汇编中实现。使用条件编译在目标体系结构中启用 asm 实现，并在任何其他体系结构中回退到通用 C 实现。

\n