我需要解压存储的12位数据,2个以24位存储的无符号12位字段.我想将它们存储在byte[]中,按小端uint16的顺序.

压缩格式有点奇数;byte[0]是第一个12位数字的高8个有效位,byte[2]是第二个12位数字的高8个有效位.中间byte[1]具有两者的低4位;第一值在较低的半字节中,第二值在较高的半字节中.

Here's a visual: the full boxes are bytes, letters represent nibbles. Lower addresses on the left, so SIMD bit-shift left will actually move data to the right across boxes but left within boxes.
Image

我已经用C#编写了两个工作版本.

        private byte[] Unpack12b2(byte[] input) //slower
        {
            int eod = input.Length / 3 * 3; //protect against file sizes that aren't a multiple of 3
            byte[] output = new byte[eod * 3 / 2];
            int j = 0;
            int loop = 0;

            for (int i = 0; i < eod; i+=3)
            {
                j = i + loop++;
                output[j] = (byte)((input[i] << 4) | (input[i + 1] & 0xf));
                output[j + 1] = (byte)(input[i] >> 4);
                output[j + 2] = (byte)((input[i + 2] << 4) | (input[i + 1] >> 4));
                output[j + 3] = (byte)(input[i + 2] >> 4);
            }
            return output;
        }

        private ushort[] Unpack12b(byte[] input) //slightly faster
        {
            int outputIndex = 0;
            int byte1, byte2, byte3;

            int eod = input.Length / 3 * 3; //protect against file sizes that aren't a multiple of 3
            ushort[] output = new ushort[eod / 3 * 2];

            for (int i = 0; i < eod; i += 3)
            {
                byte1 = input[i];
                byte2 = input[i + 1];
                byte3 = input[i + 2];

                output[outputIndex++] = (ushort)((byte1 << 4) | (byte2 & 0xf));
                output[outputIndex++] = (ushort)((byte3 << 4) | (byte2 >> 4));
            }
            return output;
        }

这是我找到的最接近的答案,但问题中的压缩格式更容易处理. SIMD unpack 12-bit fields to 16-bit

我真的很想加快速度.输出是一个200多万字节的数组,所以它有很多循环,这个函数被重复调用.

任何关于如何加快这一进程的 idea 都将不胜感激.理想情况下,我希望用AVX2在C++中实现一些东西,但我迷失在如何以半字节而不是字节的方式进行混洗.

推荐答案

如果你不能在C#中使用C#System.Runtime.Intrinsics.X86来做这件事,那么是的,调用一个由C++编译器创建的函数可能很好.为了在编组开销和缓存未命中之间取得平衡,您可能希望在进入下一个块之前,以产生85K输出的64K输入数据块为单位,在二级缓存中读取这些数据.但是,如果您需要随机访问未打包的输出,您可能会被迫一次完成所有操作,并获得最好的L3缓存命中,甚至一直未命中DRAM.


SIMD unpack 12-bit fields to 16-bit开始的大多数技术都是适用的,比如执行32字节的加载,将两个12字节的一半拆分为两个中间,设置为vpshufb,它将获得我们想要的每个4字节块中的3个字节.

Moving nibbles around requires bit-shifts(或AVX-512指令,如vpmultishiftqb,位字段提取).遗憾的是,x86 SIMD只有16位和更宽的移位,没有8位元素大小.(左移1位可以通过自身相加来完成,否则您可以使用更宽的移位和与掩码来清除跨字节边界移位的任何位.)

diagram where shift-left is left表示左移位或右移位如何在字节之间移位要容易得多,人们可以称之为"大端",它是左边最高的字节,就像英特尔在他们的SIMD随机指令手册中使用的那样(例如punpcklbw).就像我在回答链接的12到16位解包问题时对普通位布局的 comments 一样,这种布局使其看起来像是两个连续的12位字段(不像这里,它确实很奇怪).我通常使用以A开头的字母,但为了避免与您的图表混淆,我 Select 了不同的字母.(在本例中,我将前面的字母用于更重要的半字节;有时我会反过来,以匹配用于改组的元素编号,其中0是从最低地址加载/存储的最右边的元素,因此图中的D C B A是有意义的.)

high       low address
QR    ST    UV        # input format

QR ST  |  ST UV       # after a byte-shuffle replicates the middle byte while expanding

0Q RS  |  0U VT       # desired output.

 (QR<<4) | (ST>>4) in the high half.   Or QRSx>>4 in terms of 16-bit ops
 (UV<<4) | (ST&0x0F) in the low half.  Or xxUV<<4 merge with (STxx>>8)&0x0F

最初的字节混洗(vpshufb)将12个字节扩展到16个字节(在每个通道中),可以在每个32位块内提供我们想要的任何排列,比如ST ST UV QRUV ST QR UV,如果其中任何一个是用于32位或16位移位(AND/OR)的有用设置

例如,如果我们在高u16中有ST QR,那么我们想要的(0QRS)可以通过16位STQR的4位左移来获得,以将T向下移到底部,并将UV部分左移.然后屏蔽以清除高位半字节中的垃圾(T).但我们没有SIMD旋转,直到AVX-512,甚至到了only in 32 and 64-bit element size.对于另一个16位字,我们需要一些不同的东西.

(x<<4) | (x>>12)可以旋转一次.但如果我们无论如何都要效仿它,我们可以从两个不同的输入开始,和/或移动不到16的数量.

简单的右移4比特(_mm256_srli_epi16(v, 4))将把QR ST变成我们在每个u32双字元素的高位u16(字)中想要的0Q RS.因此,如果我们能想出在32位元素的底部生成0UVT的东西,就像在旧的Q&A;A中一样,这已经准备好到_mm256_blend_epi16了.

0UVT更复杂:两个字节顺序(UV、ST或ST、UV)都没有我们想要的彼此连续的位.

但是对于UV ST,我们想要的高半部的右移位也将UV个半字节放在正确的位置,只留下用T个半字节替换低4位(S)的问题.在最初的v(在移位之前),我们有一个T的副本,所以3次按位操作可以将其"混合"进go .

一百零二

只需一次移位和3次按位运算:

 QR ST | UV ST        # after vpshufb
 0Q RS | 0U VS        # after vpsrlw by 4

这两个向量之间的与/或可以产生0Q RS | 0U VT,只需要替换低位字中的低位半字节.(否则将所有内容从移位结果中保留).

 __m256i v = _mm256_shuffle_epi8(in, c);        // QR ST | UV ST

 __m256i shifted = _mm256_srli_epi16(v, 4);     // 0Q RS | 0U VS
 __m256i t = _mm256_and_si256   (_mm256_set1_epi32(0x0000000F), v);  // 00 00 | 00 0T
 shifted   = _mm256_andnot_si256(_mm256_set1_epi32(0x0000000F), shifted); // 0Q RS | 0U V0
 __m256i output = _mm256_or_si256(shifted, t); // 0Q RS | 0U VT

将其放入一个函数中,该函数加载24个字节并返回32个字节(准备好让调用者存储在循环中),borrow 我对SIMD unpack 12-bit fields to 16-bit的回答中的代码.我通过交换每个4字节块中的低2个字节来调整随机控制向量,而不是那个答案. (setr以小端顺序接受args).这使我们在每个双字的低位字中有UV ST个,而在高位字中仍然有QR ST个字.

// loads from before the first byte we actually want; beware of using at the start of a buffer
/* static */ inline
__m256i unpack12to16_weird_bitorder(const char *p)
{
    __m256i v = _mm256_loadu_si256( (const __m256i*)(p-4) );
   // v= [ x H G F E | D C B A x ]   where each letter is a 3-byte pair of two 12-bit fields, and x is 4 bytes of garbage we load but ignore

    const __m256i bytegrouping =
        _mm256_setr_epi8(5,4, 5,6,  8,7, 8,9,  11,10, 11,12,  14,13, 14,15, // low half uses last 12B
                         1,0, 1,2,  4,3, 4,5,   7, 6,  7, 8,  10,9, 10,11); // high half uses first 12B
    v = _mm256_shuffle_epi8(v, bytegrouping);   // vpshufb
    // each 16-bit chunk has the bits it needs, but not in the right position
    // in each chunk of 8 nibbles (4 bytes): [ q r  s t | u v  s t ]

    __m256i shifted = _mm256_srli_epi16(v, 4);     // 0Q RS | 0U VS
    __m256i t = _mm256_and_si256   (_mm256_set1_epi32(0x0000000F), v);       // 00 00 | 00 0T
    shifted   = _mm256_andnot_si256(_mm256_set1_epi32(0x0000000F), shifted); // 0Q RS | 0U V0
    return _mm256_or_si256(shifted, t);            // 0Q RS | 0U VT
}

This is only 4 instructions after 101, and three of them are cheap bitwise booleans可以在最新的Intel/AMD CPU上的任何向量执行端口上运行,甚至是哈斯韦尔.(https://uops.info/).因此,在前端吞吐量方面,比更简单的数据安排多了一个uop.此外,在vpshufb控制向量之外只有一个额外的向量常量.

一个AVX-512 vpternlogd可以替换三个AND/AND NOT/OR指令,使用相同的常量与位粒度混合.(如果您使用-march=skylake-avx512znver4或其他任何语言进行编译,编译器将为您完成此操作;Godbolt)

具有字节或更宽粒度的混合可以使用带有控制向量的SSE4/AVX2 vpblendvb,该控制向量在Intel上为2 uop(在AMD上为1),或者对于SSE版本仅为1.


用于在单微运算中移动+组合的乘法-加法指令

移动半字节的另一种可能性是乘以2的幂,即pmaddubsw(_mm256_maddubs_epi16,将一个输入视为有符号的,另一个视为无符号的,并将水平字节对添加到16位结果中).使用无符号输入作为我们想要组合的数据(因此它被零扩展到16位),我们可以使用1<<4=16作为有符号乘数.

在屏蔽输入以清除每个16位字中不想要的半字节后,我们可以用一个vpmaddubsw做所有事情吗?不,因为作为乘法,它只能左移.所以我们不能得到从ST到我们想要的0QRS输出的底部的S.(我们不能生成QRSx和右移位,因为我们的8位乘数常量不能容纳256.)

我们可以在QR ST | UV STvpsrlw乘4之间加vpblendw来产生0Q RS | UV ST...但作为vpmaddubsw的输入,这也不是很有效.Q需要乘以256.但0QRS是我们已经想要的元素,所以我们可以在它和移位之间混合after vpmaddwd,这无论如何都是更好的指令级并行,因为它们可以并行发生.

UV ST分得0UVT分的细节:掩饰S分,给UV 0T分.然后作为两个U8整数UV0T,做UV*16 + 0T*1得到UVT.因此,该元素的pmaddubsw的另一个输入应该是10 01(十六进制).

与更简单位顺序的版本相比,这只需要多花一条指令(8位乘加运算).

...
    v = _mm256_shuffle_epi8(v, bytegrouping);

    // in each chunk of 8 nibbles (4 bytes): [ q r  s t | u v  s t ]
    __m256i lo = _mm256_srli_epi16(v, 4);                                   // [ 0 q  r s | xxxx ]
    __m256i hi = _mm256_and_si256(v, _mm256_set1_epi32(0x0000'ff0f));       // [  0000 | u v  0 t ]
    hi         = _mm256_maddubs_epi16(hi, _mm256_set1_epi32(0x0000'10'01)); // [  0000 | 0 u  v t ]

    return _mm256_blend_epi16(lo, hi, 0b10101010);
      // nibbles in each pair of epi16: [ 0 q r s | 0 u v t ] 

vpmaddubsw是一个乘法,所以它不是最高效的指令,但现代主流x86内核对它有很好的吞吐量.(自从Skylake和Zen 3之后是2个时钟,在Zen 2上至少是1个时钟:在Intel上,它与向量移位竞争吞吐量,但Skylake和更高版本可以在端口0或1上运行这些移位.它的延迟不是问题:无序执行隐藏了这一点,我们只对每个向量做了一个短的运算链.)希望它不会浪费太多功率并降低加速频率.

This is strictly worse than the shift/and/andnot/or version,,它使用相同数量的uop,但更多的uop更便宜,并且它要加载的矢量常量更少,以供设置.我首先想到了这个pmaddubsw版本;我把它留在答案中,作为比特移动技术的一个例子,这种技术有时在其他问题中很有用.如果我们不需要在最后用混合液来区别对待两个u16的一半,madd版本可能会更好.

请注意,madd可以与QR ST | ST UV字节的顺序一起工作:您只需将0x10乘数与另一个字节对齐即可.与16位或32位移位不同,在这些移位中,位跨字节边界连续很重要.

Csharp相关问答推荐

获取Windows和Linux上的下载文件夹

为什么.Equals(SS,StringComparison. ClientCultureIgnoreCase)在Net 4.8和6.0之间不同?

FromServices不使用WebAppliationFactory程序>

禁用AutoSuggestBox项目更改时的动画?

C++/C#HostFXR通过std::tuple传递参数

如何定义EFCore中的多个穿透

将现有字段映射到EFCore中的复杂类型

ASP.NET Core AutoMapper:如何解决错误 CS0121调用在以下方法或属性之间不明确

C#-VS2022:全局使用和保存时的代码清理

BlockingCollection T引发意外InvalidOperationException

EF核心区分大小写的主键

记录类型';==运算符是否与实现IEquatable<;T&>;的类中的';equals&>方法执行等价比较?

我可以查看我们向应用程序洞察发送了多少数据吗?

将J数组转换为列表,只保留一个嵌套的JToken

当我手动停止和关闭系统并打开时,Windows服务未启动

数据库操作预计影响1行,但实际影响0行; after _dbContext.SaveChanges();

NETSDK1201:对于面向.NET 8.0和更高版本的项目,默认情况下,指定RUNTIME标识符将不再生成自包含的应用程序

如何保存具有多个重叠图片框的图片框?

反序列化我以前使用System.Text.Json序列化的文件时出现异常

这是T自身的布尔表达式是什么意思?