4

是否有一些小技巧可以有效地解压缩 16 位压缩 BCD 数字？

以步行方式执行此操作需要 10 次操作（3 个班次、4 个 AND 和 3 个 OR 或 ADD）：

x = (bcd & 0xF000) << 12
  | (bcd & 0x0F00) <<  8
  | (bcd & 0x00F0) <<  4
  | (bcd & 0x000F)

对于多路 ADD/OR，关键路径长度将为 3，但这些操作往往是二进制的，因此大多数 CPU 将查看长度为 4 的关键路径。

这可以更有效地完成吗？

注意：对于某些目的，如果可以特别有效地解包半字节的某些排列，例如如果要解包的单词来自我可以完全控制其创建的查找表（这样我可以将每个数字粘贴到任何地方），它可能同样有用我想）。在这种情况下使用打包而不是解包 BCD 的目的是将内存压力减半并避免超过 L1 缓存的大小，通过增加 CPU 的 ALU 上的负载来减轻过饱和的内存子系统的负载。

例如，如果我对 0x1324 之类的数字进行置换，那么简单的去交错会产生 0x01020304：

x = ((bcd << 12) | bcd) & 0x0F0F0F0F

这只是关键路径长度为 3 的三个操作，比原始版本有了很大的改进......

4

3 回答 3

4

最有效的解决方案将是特定于机器的，因为不同的 ISA 在处理立即常数或将移位与 ALU 操作相结合时具有不同的能力。这是一个具有良好指令级并行性的替代实现，它可能在具有非常快速整数乘法的平台上更胜一筹。通过并行执行多个移位加法运算，整数乘法通常有助于位旋转算法。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/* reference implementation */
uint32_t bcd_spread_1 (uint32_t a)
{
    return (((a & 0xF000) << 12) |
            ((a & 0x0F00) <<  8) |
            ((a & 0x00F0) <<  4) |
            ((a & 0x000F) <<  0));
}

/* alternative implementation */
uint32_t bcd_spread_2 (uint32_t a)
{
    return ((((a & 0xf0f0) * 0x1010) & 0x0f000f00) |
            (((a & 0x0f0f) * 0x0101) & 0x000f000f));
}

/* BCD addition. Knuth TAOCP 4 */
uint32_t median (uint32_t x, uint32_t y, uint32_t z)
{
    return (x & (y | z)) | (y & z);
}

uint32_t bcd_add (uint32_t x, uint32_t y)
{
    uint32_t z, u, t;
    z = y + 0x66666666;
    u = x + z;
    t = median (~x, ~z, u) & 0x88888888;
    return u - t + (t >> 2);
}

int main (void)
{
    uint32_t x, y, bcd = 0;
    do {
        x = bcd_spread_1 (bcd);
        y = bcd_spread_2 (bcd);
        if (x != y) {
            printf ("!!!! bcd=%04x x=%08x y=%08x\n", bcd, x, y);
            return EXIT_FAILURE;
        }
        bcd = bcd_add (bcd, 1);
    } while (bcd < 0x10000);
    return EXIT_SUCCESS;
}
于 2020-01-10T00:09:41.993 回答
4

这是一种替代方法，操作更少但关键路径更长，基于半字节移动距离的二进制分解（移动 8 步或 12 步的半字节一起移动 8 步，移动距离为 4 的移动半字节或 12 加 4）。

x = bcd
x = ((x & 0xFF00) << 8) | (x & 0xFF)
x = ((x & 0x00F000F0) << 4) | (x & 0x000F000F)

例如：

// start
0000ABCD
// move A and B by 8
00AB00CD
// move A and C by 4
0A0B0C0D
于 2020-01-09T21:06:50.820 回答
-1

使用DoubleDabble算法。

于 2020-01-09T19:07:33.237 回答