SSE图像算法优化系列三十一:Base64编码和解码算法的指令集优化(C#自带函数的3到4倍速度)。

    一、基础原理

         Base64是一种用64个Ascii字符来表示任意二进制数据的方法。主要用于将不可打印的字符转换成可打印字符,或者简单的说是将二进制数据编码成Ascii字符。Base64也是网络上最常用的传输8bit字节数据的编码方式之一。

        标准的Base64编码方式过程可简单描述如下:

        第一步,将每三个字节作为一组,一共是24个二进制位。

        第二步,将这24个二进制位分为四组,每个组有6个二进制位。

        第三步,在每组前面加两个00,扩展成32个二进制位,即四个字节。

        第四步,根据下表,得到扩展后的每个字节的对应符号,这就是Base64的编码值。

       SSE图像算法优化系列三十一:Base64编码和解码算法的指令集优化(C#自带函数的3到4倍速度)。

        复制一段别人的文件对这个算法进行了后续的描述了,我们以英语单词Man如何转成Base64编码。

Text content M a n
ASCII 77 97 110
Bit pattern 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 1 0
Index 19 22 5 46
Base64-Encoded T W F u

       第一步,"M"、"a"、"n"的ASCII值分别是77、97、110,对应的二进制值是01001101、01100001、01101110,将它们连成一个24位的二进制字符串010011010110000101101110。

       第二步,将这个24位的二进制字符串分成4组,每组6个二进制位:010011、010110、000101、101110。

       第三步,在每组前面加两个00,扩展成32个二进制位,即四个字节:00010011、00010110、00000101、00101110。它们的十进制值分别是19、22、5、46。

       第四步,根据上表,得到每个值对应Base64编码,即T、W、F、u。

       如果字节数不足三,则这样处理:

       a)二个字节的情况:将这二个字节的一共16个二进制位,按照上面的规则,转成三组,最后一组除了前面加两个0以外,后面也要加两个0。这样得到一个三位的Base64编码,再在末尾补上一个"="号。

     比如,"Ma"这个字符串是两个字节,可以转化成三组00010011、00010110、00010000以后,对应Base64值分别为T、W、E,再补上一个"="号,因此"Ma"的Base64编码就是TWE=。

     b)一个字节的情况:将这一个字节的8个二进制位,按照上面的规则转成二组,最后一组除了前面加二个0以外,后面再加4个0。这样得到一个二位的Base64编码,再在末尾补上两个"="号。

     比如,"M"这个字母是一个字节,可以转化为二组00010011、00010000,对应的Base64值分别为T、Q,再补上二个"="号,因此"M"的Base64编码就是TQ==。

   基本就是这个简单的过程。

   由以上过程可以看到,Base64编码不是一个压缩过程(反而是个膨胀的过程,处理后体积是增加了1/3的),也不是一个加密过程(没任何密钥)。

二、C语言实现

  由上述描述可见这是一个比较简单的过程,通过移位和一些查找表可以快速的写出一个简单的版本。

int IM_ToBase64CharArray_C(unsigned char *Input, int Length, unsigned char* Output)
{
    static const char* LookUpTable = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    int CurrentIndex = 0, ValidLen = (Length / 3) * 3;
    for (int Y = 0; Y < ValidLen; Y += 3, CurrentIndex += 4)
    {
        int Temp = ((Input[Y]) << 24) + (Input[Y + 1] << 16) + (Input[Y + 2] << 8);    //    注意C++是Little-Endian布局的
        int V0 = (Temp >> 26) & 0x3f;
        int V1 = (Temp >> 20) & 0x3f;
        int V2 = (Temp >> 14) & 0x3f;
        int V3 = (Temp >> 8) & 0x3f;
        Output[CurrentIndex + 0] = LookUpTable[V0];
        Output[CurrentIndex + 1] = LookUpTable[V1];
        Output[CurrentIndex + 2] = LookUpTable[V2];
        Output[CurrentIndex + 3] = LookUpTable[V3];
    }
    //    如果字节数不足三
    int Remainder = Length - ValidLen;
    if (Remainder == 2)
    {        
    }
    else if (Remainder == 1)
    { 
    }
    return IM_STATUS_OK;
}

 

  一个简单的版本如上所示,注意由于C++的数据在内存中Little-Endian布局的,因此,低字节在高位,可以通过向上面的移位方式组合成一个int型的Temp变量。然后在提取出各自的6位数据,最后通过查找表来获得最后的结果。

      当输入的长度不是3字节的整数倍数时,需要独立的写相关代码,如上面的Remainder == 2和Remainder == 1所示,这部分可以自行添加代码。

      上面的代码,我们用 10000 * 10000  * 3 = 3亿长度的数据量进行测试, 纯算法部分的耗时约为 440ms。我们用C#的Convert.ToBase64CharArray方法做同样的事情,发现C#居然需要640ms。这个有点诧异。

       在PC上,我们可以对上述代码进行适当的改动,使得效率更加优秀。

       在PC上,有_byteswap_ulong一个指令,这个指令可以直接对int数据进行大小端的转换,而且我们反编译后看到这个内建函数其实就对应了一条汇编指令bswap,改指令的解释如下:

              BSWAP是汇编指令指令作用是:32位寄存器内的字节次序变反。比如:(EAX)=9668 8368H,执行指令:BSWAP EAX ,则(EAX)=6883 6896H。

     新的代码如下所示:

int IM_ToBase64CharArray_C(unsigned char *Input, int Length, unsigned char* Output)
{
    static const char* LookUpTable = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    int CurrentIndex = 0, ValidLen = (Length / 3) * 3;
    for (int Y = 0; Y < ValidLen; Y += 3, CurrentIndex += 4)
    {
        int Temp = _byteswap_ulong(*(int *)(Input + Y));        //    这个的效率还是高很多的,注意C++是Little-Endian布局的
        int V0 = (Temp >> 26) & 0x3f;
        int V1 = (Temp >> 20) & 0x3f;
        int V2 = (Temp >> 14) & 0x3f;
        int V3 = (Temp >> 8) & 0x3f;
        Output[CurrentIndex + 0] = LookUpTable[V0];
        Output[CurrentIndex + 1] = LookUpTable[V1];
        Output[CurrentIndex + 2] = LookUpTable[V2];
        Output[CurrentIndex + 3] = LookUpTable[V3];
    }
    //    如果字节数不足三
    int Remainder = Length - ValidLen;
    if (Remainder == 2)
    {
    }
    else if (Remainder == 1)
    {
    }
    return IM_STATUS_OK;
}

      反编译部分代码如下所示:  

             SSE图像算法优化系列三十一:Base64编码和解码算法的指令集优化(C#自带函数的3到4倍速度)。

       可以看到明显bswap指令。

       同样的3亿数据量,上述代码编译后执行的耗时约为350ms

       但是上述代码是有个小小的问题的,我们知道 

              int Temp = _byteswap_ulong(*(int *)(Input + Y)); 

  这句代码实际上是从内存 Input + Y 处加载4个字节,如果在数据的末尾,恰好还剩3个字节时,此时的加载指令实际就会访问野内存,造成内存错误。所以实际编码时这个位置还是要做适当的修改的。

 三、SSE优化实现

      上述C的代码也是非常简单的,但是由于有一个查表的过程,要把他翻译成SIMD指令,还是要做一番特备的处理的。 这里我们找到一个非常优异的国外朋友的博客,基本上把这个算法分析的特别透彻。详见:http://0x80.pl/notesen/2016-01-12-sse-base64-encoding.html

       该文的作者对Base64的解码和编码做了特备全面的解读,包括普通的scalar优化、SSE、AVX256、AVX512、Neon等代码都有实现,我这里只分析下SSE的实现,基本也就是翻译的过程。

       1、数据加载

       我们知道,在Base64的过程中,原始数据的3个字节处理完成后变为4个字节,因此,为了适应SSE的需求,我们应该只加载连续的12个字节数据,然后把他们扩展到16个字节。

       加载12字节数据,有多重方法,一个是直接用_mm_loadu_si128指令,然后把最后四个舍弃掉,这样的话同样要注意类似_byteswap_ulong的问题,不要访问越界的内存。另外还可以自定一个这样的函数:

//    从指针p处加载12个字节数据到XMM寄存器中,寄存器最高32位清0
inline __m128i _mm_loadu_epi96(const __m128i * p)
{
    return _mm_unpacklo_epi64(_mm_loadl_epi64(p), _mm_cvtsi32_si128(((int *)p)[2]));
}

  还有一个方式就是使用 _mm_maskload_epi32指令,把最后一个高位的mask设置为0。

    当加载完数据到SSE寄存器后,我们可以按照上述C的代码进行算法的移位和位运算,得到一个重新组合的数据,但是也可以根据观察采用下面的一种方式

    //  Base64以3个字节为一组,对于任意一个三元组合,其在内存二进制位布局如下
    //      [????????|ccdddddd|bbbbcccc|aaaaaabb]
    //        byte 3   byte 2   byte 1   byte 0    -- byte 3  是冗余的
    __m128i In = _mm_loadu_epi96((__m128i*)(Input + Y));
    //      [bbbbcccc|ccdddddd|aaaaaabb|bbbbcccc]
    //           ^^^^ ^^^^^^^^ ^^^^^^^^ ^^^^                ^表示有效位,这样的好处是中心对称了
    In = _mm_shuffle_epi8(In, _mm_set_epi8(10, 11, 9, 10, 7, 8, 6, 7, 4, 5, 3, 4, 1, 2, 0 ,1));

  通过shuffle混洗后,我们的需要的4个6个位的数据在分布上都相邻了,这个时候移位操作就方便了很多。那么最直接的实现方式如下所示:

    // Index_a = packed_dword([00000000|00000000|00000000|00aaaaaa] x 4)
    __m128i Index_a = _mm_and_si128(_mm_srli_epi32(In, 10), _mm_set1_epi32(0x0000003f));

    // Index_a = packed_dword([00000000|00000000|00BBbbbb|00000000] x 4)
    __m128i Index_b = _mm_and_si128(_mm_slli_epi32(In, 4), _mm_set1_epi32(0x00003f00));

    // Index_a = packed_dword([00000000|00ccccCC|00000000|00000000] x 4)
    __m128i Index_c = _mm_and_si128(_mm_srli_epi32(In, 6), _mm_set1_epi32(0x003f0000));

    // Index_a = packed_dword([00dddddd|00000000|00000000|00000000] x 4)
    __m128i Index_d = _mm_and_si128(_mm_slli_epi32(In, 8), _mm_set1_epi32(0x3f000000));

     //     [00dddddd|00cccccc|00bbbbbb|00aaaaaa]
    //          byte 3   byte 2   byte 1   byte 0  
    __m128i Indices = _mm_or_si128(_mm_or_si128(_mm_or_si128(Index_a, Index_b), Index_c), Index_d);

  一共有4次移位,4次and运算,以及3次or运算。

       直接的这样实现其实效率也相当的高,因为都是一些位运算,但是还有一种更为精妙的实现方式,虽然效率上实际没有提高多少,但是实现方式看起来确实让人觉得不错,一般人还真是想不到。核心代码如下所示:

// T0   = [0000cccc|cc000000|aaaaaa00|00000000]
    __m128i T0 = _mm_and_si128(In, _mm_set1_epi32(0x0fc0fc00));
    // T0    = [00000000|00cccccc|00000000|00aaaaaa]   (c * (1 << 10), a * (1 << 6)) >> 16 (注意是无符号的乘法, 借用16位的乘法实现不同位置的移位,这个技巧很好)
    T0 = _mm_mulhi_epu16(T0, _mm_set1_epi32(0x04000040));
        
    // T1    = [00000000|00dddddd|000000bb|bbbb0000]
    __m128i T1 = _mm_and_si128(In, _mm_set1_epi32(0x003f03f0));
    // T1    = [00dddddd|00000000|00bbbbbb|00000000]     (d * (1 << 8), b * (1 << 4))
    T1 = _mm_mullo_epi16(T1, _mm_set1_epi32(0x01000010));

    // res   = [00dddddd|00cccccc|00bbbbbb|00aaaaaa] 
    __m128i Indices = _mm_or_si128(T0, T1);

       这里的核心技巧是借用16的乘法来实现一个32位内两个16位部分的不同移位,而且在一个指令内。感觉无法解释,还是自己看指令吧。

       二、数据查表

       其实查表,如果是16字节的查表,而且是表的范围也是0到15,那么是可以直接使用_mm_shuffle_epi8指令的,这个其实我在前面有个文章的优化里是用到的,但是Base64是64字节的查表,这个如果查表的数据没啥特殊性,那SSE指令还真的没有用于之地的。

       但是,Base64的表就是有特殊性,我们看到表的输入是连续的0到63的值,表的输出可以分成四类:

       第一类: ABCDEFGHIJKLMNOPQRSTUVWXYZ        ASCII值连续

       第二类: abcdefghijklmnopqrstuvwxyz                        ASCII值连续

       第三类: 0123456789                ASCII值连续,且只有10个数据

       第四类: +      

       第五类: /  

       那么对于某个输入索引 X,我们首先有一些比较指令把输入数据区分为某一类,然后每一类可以有对应的结果偏移量,这里只有5个类,完全在SSE的16个字节的范围内。同时我们注意观察,如果把第三类认为他是10个类,同时这1个类都对应一个相同的偏移量,那么总共的内别数也还只有14类,没有超过16的,这样是更有利于编程的。

      那么怎么说呢,我感觉这个过程无论用什么语言表达,可能都还没有代码本身意义大。一个可选的优化方式如下所示:

    //           0..51 -> 0
    //        52..61 -> 1 .. 10
    //            62 -> 11
    //            63 -> 12
    __m128i Shift = _mm_subs_epu8(Indices, _mm_set1_epi8(51));

    // 接着在区分 0..25 和 26..51两组数据:
    //         0 .. 25 -> 仍然保持0 
    //        26 .. 51 -> 变为 13
    const __m128i Less = _mm_cmpgt_epi8(_mm_set1_epi8(26), Indices);
    //          0..26 -> 0
    //         26..51 -> 13
    //       52..61 -> 1 .. 10
    //           62 -> 11
    //           63 -> 12
    Shift = _mm_or_si128(Shift, _mm_and_si128(Less, _mm_set1_epi8(13)));

    const __m128i shift_LUT = _mm_setr_epi8('a' - 26, '0' - 52, '0' - 52, '0' - 52, '0' - 52, '0' - 52,'0' - 52, '0' - 52, '0' - 52, '0' - 52, '0' - 52, '+' - 62,'/' - 63, 'A', 0, 0);

    //    按照Shift的数据这读取偏移量
    Shift = _mm_shuffle_epi8(shift_LUT, Shift);

  很简单的代码,但是也是很优美的文字。却能迸发出惊人的效率。我们同样的测试发现,对于相同的3亿数据量,SSE优化编码后的速度大概是210ms,比优化后的C++代码块约70%,比原生的C#函数快了近4倍。

       在同样的作者的较新的一篇文章《Base64 encoding and decoding at almost the speed of a memory copy》中,使用最新的AVX512指令集,获得了速度比肩memcpy的Base64编解码实现,这是因为使用AVX512,可以只用2条指令实现相关的过程,而AVX512一次性可以读取64个字节的特性,让这个BASE64的64字节查找表可以直接实现也是这个极速的关键所在。

SSE图像算法优化系列三十一:Base64编码和解码算法的指令集优化(C#自带函数的3到4倍速度)。

       上面这个表没有SSE的数据,SSE速度大概是AVX2的0.8倍左右。

四、关于解码

      Base64的解码是编码的相反过程,就是先进行查找表,然后在进行移位合并。但是不同的地方是,解码的时候一般是需要进行一些合理性判断的,如果输入的数据不在前述的64位范围内,说明这个是数据是无效的。作为SSE实现来说,其核心还是在于查表和移位合并,当然这里查表的方式也有很多优化技巧,这里可以参考http://0x80.pl/notesen/2016-01-17-sse-base64-decoding.html 一文,那个作者写的是真的很好。直接阅读英文版的,可能会受益更多,这里不进行过多的讲解。

      但是那个代码真的值得学习,尤其是其中的数据组合部分。

      关于解码的速度,如果不考虑错误判断和处理,其实基本上和解码是一个档次的。测试表面,解码同样的比C#自带的函数也要快很多。

      如果想时刻关注本人的最新文章,也可关注公众号:

                             SSE图像算法优化系列三十一:Base64编码和解码算法的指令集优化(C#自带函数的3到4倍速度)。

上一篇:windows驱动开发-进程结构体初探


下一篇:java精度损失