为每个 int8_t 元素添加两个具有饱和度的向量（uint64_t 类型）

Question

我最近面临一个给定的问题：

\n

\n

向量中有8个元素，每个元素都用int8_t表示。

\n

在 x86_64 中实现一个算法，将两个向量（uint64_t 类型）相加。

\n

添加元素时应考虑饱和算术。

\n

例如：

\n

80 + 60 = 127

\n

(\xe2\x88\x9240) + (\xe2\x88\x92100) = \xe2\x88\x92128

\n

\n

最大的挑战是施加的限制：

\n

\n
• 除ret外无条件指令；没有跳跃、cmove、set 等。
\n
• 该解不能长于 48 条指令（存在短于 37 条指令的解）
\n

\n

我想不出任何符合这些限制的解决方案。\n有人能给我一些提示吗？欢迎使用 C 语言的示例。

\n

我只能使用“标准”、传输、算术、逻辑指令和标准寄存器：

\n

\n
• mov cbw/cwde/cdqe cwd/cdq/cqo movzx movsx
\n
• 添加 sub imul mul idiv div inc dec neg
\n
• 和或异或非 sar sarx shr shrx shl shlx ror rol
\n
• 雷雷
\n

\n

Answer 1

这是一个版本（经过测试，不需要 imul），使用 clang-16 编译时需要 22 条指令。

uint64_t add(uint64_t x, uint64_t y) {
    uint64_t eq, xv, yv, satmask, satbits, satadd, t0, t1;
    uint64_t signmask = 0x8080808080808080ULL;

    eq = (x ^ ~y) & signmask;
    xv = x & ~signmask;
    yv = y & ~signmask;
    xv += yv;
    satbits = (xv ^ y) & eq;
    satadd = satbits >> 7;
    satmask = (satbits << 1) - satadd;
    xv ^= eq;
    t0 = (xv & ~satmask) ^ signmask;
    t1 = satadd & ~(xv >> 7);
    return t0 - t1;
}

集会：

mov     rdx, rsi
xor     rdx, rdi
not     rdx
movabs  r8, -9187201950435737472
and     rdx, r8
movabs  rcx, 9187201950435737471
and     rdi, rcx
and     rcx, rsi
add     rcx, rdi
xor     rsi, rcx
and     rsi, rdx
lea     rax, [rsi + rsi]
shr     rsi, 7
xor     rcx, rdx
not     rax
add     rax, rsi
and     rax, rcx
xor     rax, r8
shr     rcx, 7
not     rcx
and     rcx, rsi
sub     rax, rcx