SIMD：有符号整数位压缩

Question

SIMD：有符号整数位压缩

ssesimdavxavx2avx512

3

无符号整数可以使用“位打包”技术进行压缩：在一块无符号整数中，仅存储显著位，当块中所有整数都很“小”时，会导致数据压缩。该方法称为 FOR（基准帧）。

有 SIMD 库可以高效执行此操作。

现在我想使用类似 FOR 的技术来编码 带符号 整数，例如来自未排序的无符号整数的差分序列。每个带符号整数的符号需要存储在某个地方，这里有两个选择：

将符号存储在单独的数据块中。这增加了开销。
将符号与每个带符号整数的绝对值一起存储。

我现在正在遵循第二种路径。2 的补数将符号位存储在最高有效位（msb）中，因此对于类似 FOR 的位打包，这不起作用。一种可能性是在最低有效位（lsb）中存储符号。以这种方式存储带符号整数非常不寻常，据我所知没有支持这种方法的指令。现在的问题是：是否可以使用 SIMD 指令高效地编码/解码这些 lsb-带符号-整数？

我认为 AVX-512 的 _mm_testn_epi32_mask 可以用于从每个 uint32 中提取 lsb，然后进行位移，接着两个 mask_extract 之类的操作？相当复杂。

- mcmayer

2

一个常见且可逆的从有符号整数到无符号整数的映射是：(x < 0) ? (-2 * x - 1) : (2 * x)。你能利用它吗？ - njuffa

AVX-512具有32位元素的SIMD旋转功能，如果有帮助的话。因此，您可以将符号位带到底部。但是，您可能希望为负数屏蔽所有其他前导1。也许您可以对负输入进行位翻转或否定，以便最终得到前导零，并且可以使用低位作为解码时是否否定的信号。（在旋转后，“0-x”具有将低位设置为负数的优点，而“x ^ -1”则没有。）我认为这是@njuffa建议的相同映射。 - Peter Cordes

是的，所以使用 vprold zmm, zmm, 1 / vpabsd zmm, zmm 进行编码（32位元素的绝对值）。解码时...如果没有人比我更快，我想到了什么，我会发布一个答案 :P - Peter Cordes

1

10年前曾经有一个相关的问题被提出：https://stackoverflow.com/questions/3557599/whats-the-faster-way-to-implement-the-signed-to-unsigned-map-rx-2x-1-if-x0 - mcmayer

4

为了实现@njuffa的建议，注意到-x-1与~x是相同的，因此(x < 0) ? (-2 * x - 1) : (2 * x)等同于(x>>31) ^ (x+x)。 - chtz

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aqrit · Accepted Answer

SSE2用于64位整数的C语言中未经测试的ZigZag示例：

（注意：SSE2缺少一些64位指令...）

#include <emmintrin.h>


// from comment by Peter-Cordes 
__m128i zigzag_encode_epi64(__m128i v) {
    __m128i signmask = _mm_shuffle_epi32(v, _MM_SHUFFLE(3,3,1,1));
    signmask = _mm_srai_epi32(signmask, 31);
    return _mm_xor_si128(_mm_add_epi64(v, v), signmask);
}


__m128i zigzag_decode_epi64 (__m128i v) {
    __m128i signmask = _mm_and_si128(_mm_set_epi32(0, 1, 0, 1), v);
    signmask = _mm_sub_epi64(_mm_setzero_si128(), signmask);
    return _mm_xor_si128(_mm_srli_epi64(v, 1), signmask);
}


// no constant
__m128i zigzag_decodev3_epi64 (__m128i v) {
    __m128i t = _mm_srli_epi64(v, 1);
    __m128i signmask = _mm_sub_epi64(_mm_slli_epi64(t, 1), v);
    return _mm_xor_si128(t, signmask);
}

Zigzag适合位运算变长整数编码。然而，一个按字节分组的组变长可能希望“从可变位宽进行符号扩展”。

32位示例

我更喜欢使用比较运算符而不是算术移位。假设展开后，比较运算符将具有比算术移位更短的延迟周期。

__m128i zigzag_encode_epi32 (__m128i v) {
    __m128i signmask =_mm_cmpgt_epi32(_mm_setzero_si128(), v);
    return _mm_xor_si128(_mm_add_epi32(v, v), signmask);
}


__m128i zigzag_decode_epi32 (__m128i v) {
    const __m128i m = _mm_set1_epi32(1);
    __m128i signmask =_mm_cmpeq_epi32(_mm_and_si128(m, v), m);
    return _mm_xor_si128(_mm_srli_epi32(v, 1), signmask);
}


__m128i delta_encode_epi32 (__m128i v, __m128i prev) {
    return _mm_sub_epi32(v, _mm_alignr_epi8(v, prev, 12));
}


// prefix sum (see many of answers around stackoverflow...)
__m128i delta_decode_epi32 (__m128i v, __m128i prev) {
    prev = _mm_shuffle_epi32(prev, _MM_SHUFFLE(3,3,3,3)); // [P P P P]
    v = _mm_add_epi32(v, _mm_slli_si128(v, 4)); // [A AB BC CD]
    prev = _mm_add_epi32(prev, v); // [PA PAB PBC PCD]
    v = _mm_slli_si128(v, 8); // [0 0 A AB]
    return _mm_add_epi32(prev, v); // [PA PAB PABC PABCD]
}


__m128i delta_zigzag_encode_epi32 (__m128i v, __m128i prev) {
    return zigzag_encode_epi32(delta_encode_epi32(v, prev));
}


__m128i delta_zigzag_decode_epi32 (__m128i v, __m128i prev) {
    return delta_decode_epi32(zigzag_decode_epi32(v), prev);
}

注意：对于Delta编码而言，为了提高速度（往返/解码），在编码时转置元素，然后在解码时再将它们转置回来会更快；水平前缀和非常慢。然而，确定每个批次中需要转置的最佳元素数量似乎是一个难题。