SIMD を使ってバイト列を 16 進数文字列に変換する

^{諸事情あり、本年度から Zenn に移行することとなりました。暫くはマルチポストご容赦ください。}
 

昨日のハッシュ値の 16 進数表現からオリジナルのバイト列を復元するという処理。

実装としては問題ないのですが、勢いで作ったものを冷静に眺めてみると少し頭が固かったように思います。

元のデータを復元しなくても良い

ユーザー認証におけるパスワードがそうですが、サーバーにはハッシュ化されたパスワードが保存されていて、ユーザーは認証の際に入力したパスワードをハッシュ化してサーバーに送ります。

後はサーバー上で「元のパスワード」ではなく「ハッシュ化されたパスワードの文字列」が一致するかを検証します。検証において「元のデータ」を用いないことでセキュリティを高めるのが狙いの手法です。

アセットデータ等の真正を確認する為のハッシュ値の検証も同様に、ハッシュ値の 16 進数表現から元のバイト列を復元する必要はなく「ハッシュ値を 16 進数表現にした UTF-8 のバイト列」を正式なハッシュ値として扱い、検証対象にしても構わない訳です。

※ ゲームの DLC 等とは違い、サーバー上でハッシュを検証する場合は不変の UTF-8 を正式なハッシュとしてしまった方が無駄な処理が省けそうです。

ハッシュ値の検証ではあまり必要とはなりませんが、CryptographicOperations.FixedTimeEquals なんてものもあります。

https://learn.microsoft.com/ja-jp/dotnet/api/system.security.cryptography.cryptographicoperations.fixedtimeequals?view=netstandard-2.1

追記）SIMD について

以下の Vector64 を使ったコードは正常に動きますが、結果として処理速度が上がっているかは微妙です。（遅い可能性が高いです）

※ @radian-jp さんのコメントと提供の参考 URL を確認してみてください。

x86/x64 SIMD命令一覧表　（SSE～AVX2）
https://www.officedaytime.com/tips/simd.html

ふわっとした SIMD の歴史

始まりは Intel の SSE（Streaming SIMD Extensions）

• SSE v1: 完全に浮動小数点の演算向け
• SSE v2: バージョンアップで整数演算がサポートされた
• SSE v3~

後継の AVX（Intel Advanced Vector Extensions）

• AVX v1: 浮動小数点関連の拡張がなされる（SSE時代に実装された整数演算も可能）
• AVX v2: 整数演算の対応が拡充

SIMD において整数演算は不遇職という事ですね。加えて今回のようなケースではデータのサイズも小さいのでデメリットの方が大きい。

所謂ループのアンロールをした方がパフォーマンス面では有利だった気がします。（未検証）

SIMD が効果的なケース（AI談）

一般的なアプリケーションでSSEやAVXの恩恵を実感できるデータセットの目安としては、

• 数バイト〜数十バイト程度: SIMDの恩恵は限定的、あるいはむしろ遅くなる可能性もあります。
• 数百バイト〜数キロバイト程度: キャッシュに収まるサイズであれば、SIMDの恩恵を受けやすいです。
• 数キロバイト〜数メガバイト、それ以上: データ量が大きくなるとキャッシュミスが増える可能性もありますが、繰り返し処理を行うことでSIMDの並列処理能力が活かされ、スループットが向上します。

結論として、SSEやAVXが効果を発揮するのは、データセットのサイズが小さくても、同じ演算を何度も繰り返すようなデータ並列性の高い処理です。特に、配列や行列の要素ごとの演算、画像や音声のフィルタリング、物理シミュレーションなど、浮動小数点演算や整数演算を大量に行う場合に、その真価が発揮されます。

epi8 とは？

SIMD、SSE、AVXの文脈における「epi8」は、以下の略語として使用されます。

• e: Extended (拡張) - これは、MMX命令セットで導入された64ビットのパックデータ型（pi8など）よりも幅広いベクトル（通常は128ビット、256ビット、512ビット）を指すことを意味します。
• p: Packed (パックされた) - 複数のデータ要素が1つのSIMDレジスタにまとめられている状態を指します。
• i: Integer (整数) - 処理されるデータが整数であることを示します。
• 8: 8-bit (8ビット) - 各整数が8ビット幅であることを示します。これは、-128から127、または0から255までの範囲の値を扱います。

したがって、epi8 は、「拡張されたパックされた8ビット整数」を意味し、SSEやAVXなどのSIMD命令セットで、複数の8ビット整数データを並行して処理するためのデータ型や命令を表す際に用いられます。例えば、_mm_add_epi8 のような組み込み関数は、8ビット整数がパックされたデータを要素ごとに加算する操作に対応しています。

SIMD を使ってバイト列を変換する

よってバイト配列を高速で 16 進数文字列にすることが出来ると良い、という事になります。

👇 結果の期待値は 0189abef89abef01 です。

using System;
using System.Runtime.Intrinsics;
using System.Text;
using System.Runtime.InteropServices;

public class Program
{
    public static void Main()
    {
        var val = new byte[] { 1, 137, 171, 239, 137, 171, 239, 1 };
        SIMD(val);
        Console.WriteLine(Convert.ToHexString(val).ToLower());
    }

    public static void SIMD(ReadOnlySpan<byte> bytes)
    {
        unchecked
        {
            var numberOffset = Vector64.Create((byte)'0');
            var letterOffset = Vector64.Create((byte)('a' - 10));
            var boundary = Vector64.Create((byte)9);
            var takeLowerBits = Vector64.Create((byte)0x0F);
            
            var takeFirst = Vector64.Create((byte)0, 0, 1, 1, 2, 2, 3, 3);
            var takeSecond = Vector64.Create((byte)4, 4, 5, 5, 6, 6, 7, 7);
            var mergeMask = Vector64.Create((byte)0xFF, 0, 0xFF, 0, 0xFF, 0, 0xFF, 0);

            var result = (stackalloc byte[16]);

            for (int i = 0; i < bytes.Length; i += 8)
            {
                var s = bytes.Slice(i, 8);
                ref var p = ref MemoryMarshal.GetReference(s);
                var upper = Vector64.LoadUnsafe<byte>(ref p);
                var lower = Vector64.LoadUnsafe<byte>(ref p);

                upper = Vector64.ShiftRightLogical(upper, 4);
                lower = Vector64.BitwiseAnd(lower, takeLowerBits);

                var firstUpper = Vector64.Shuffle(upper, takeFirst);
                var firstLower = Vector64.Shuffle(lower, takeFirst);
                var firstValues = Vector64.ConditionalSelect(mergeMask, firstUpper, firstLower);
                Console.WriteLine(firstValues);

                var mask = Vector64.GreaterThan(firstValues, boundary);
                var offset = Vector64.ConditionalSelect(mask, letterOffset, numberOffset);
                var resultValues = Vector64.Add(firstValues, offset);

                Vector64.TryCopyTo(resultValues, result.Slice(i * 2));
                
                var secondUpper = Vector64.Shuffle(upper, takeSecond);
                var secondLower = Vector64.Shuffle(lower, takeSecond);
                var secondValues = Vector64.ConditionalSelect(mergeMask, secondUpper, secondLower);
                Console.WriteLine(secondValues);

                mask = Vector64.GreaterThan(secondValues, boundary);
                offset = Vector64.ConditionalSelect(mask, letterOffset, numberOffset);
                resultValues = Vector64.Add(secondValues, offset);

                Vector64.TryCopyTo(resultValues, result.Slice(i * 2 + 8));

                Console.WriteLine();
                Console.WriteLine(Encoding.UTF8.GetString(result));
                
            }
        }
    }
}

👇

<0, 1, 8, 9, 10, 11, 14, 15>
<8, 9, 10, 11, 14, 15, 0, 1>

0189abef89abef01
0189abef89abef01

４バイト単位で処理する効率悪そうな旧版

👇 結果の期待値は 0189abef です。次項で標準ライブラリを使った出力結果を確認できます。

※ ベクトル化は Load、データの取り出しには TryCopyTo を（使えるなら）使った方が良いです。逆に言えばそれらのメソッドを使えるようにデータを並べるべきです。

using System;
using System.Runtime.Intrinsics;
using System.Text;

public class Program
{
    public static void Main()
    {
        SIMD(new byte[] { 1, 137, 171, 239 });
    }

    public static void SIMD(ReadOnlySpan<byte> bytes)
    {
        unchecked
        {
            var numberOffset = Vector64.Create((byte)'0');
            var letterOffset = Vector64.Create((byte)('a' - 10));
            var boundary = Vector64.Create((byte)9);
            
            var result = (stackalloc byte[8]);

            for (int i = 0; i < bytes.Length; i += 4)
            {
                var upper = Vector64.Create(
                    (ushort)(bytes[i]),
                    (ushort)(bytes[i + 1]),
                    (ushort)(bytes[i + 2]),
                    (ushort)(bytes[i + 3]));

                upper = Vector64.ShiftRightLogical(upper, 4);

                var lower = Vector64.Create(
                    (byte)0,
                    bytes[i],
                    (byte)0,
                    bytes[i + 1],
                    (byte)0,
                    bytes[i + 2],
                    (byte)0,
                    bytes[i + 3]);
                
                lower = Vector64.BitwiseAnd(lower, Vector64.Create((byte)0x0F));
                
                var vec = Vector64.Add(upper.AsByte(), lower);
                Console.WriteLine(vec);

                var mask = Vector64.GreaterThan(vec, boundary);
                var offset = Vector64.ConditionalSelect(mask, letterOffset, numberOffset);
                var values = Vector64.Add(vec, offset);
                Console.WriteLine(values);

                result[0] = values[0];
                result[1] = values[1];
                result[2] = values[2];
                result[3] = values[3];
                result[4] = values[4];
                result[5] = values[5];
                result[6] = values[6];
                result[7] = values[7];

                Console.WriteLine();
                Console.WriteLine(Encoding.UTF8.GetString(result));
                
            }
        }
    }
}

👇

<0, 1, 8, 9, 10, 11, 14, 15>
<48, 49, 56, 57, 97, 98, 101, 102>

0189abef

Unity

Unity では Vector64 が使えませんので、地道にビット演算でデータを作ります。

標準ライブラリと違って大文字か小文字か選べるようになっています。

using System;
using System.Text;
using System.Linq;

public class Program
{
    public static void UnsafeConvertBytesToHexString(ReadOnlySpan<byte> bytes, Span<byte> result, out int bytesWritten, bool uppercase = true)
    {
        int resultIndex = 0;

        unchecked
        {
            const byte UPPERCASE = (byte)'A' - 10;
            const byte LOWERCASE = (byte)'a' - 10;
            
            byte offset = uppercase ? UPPERCASE : LOWERCASE;

            for (int i = 0; i < bytes.Length; i++)
            {
                byte b = (byte)(bytes[i]);
                byte upper = (byte)(b >> 4);
                byte lower = (byte)(b & 0x0F);

                if (upper <= 9)
                    upper += (byte)'0';
                else
                    upper += offset;

                if (lower <= 9)
                    lower += (byte)'0';
                else
                    lower += offset;

                result[resultIndex] = upper;
                result[resultIndex + 1] = lower;
                resultIndex += 2;
            }
        }

        bytesWritten = resultIndex;
    }

    public static void Main()
    {
        var UTF8 = new byte[] { 1, 137, 171, 239 };
        var expected = Encoding.UTF8.GetBytes(Convert.ToHexString(UTF8));
        
        var test = (stackalloc byte[UTF8.Length * 2]);
        UnsafeConvertBytesToHexString(UTF8, test, out var len);

        Console.WriteLine(test.SequenceEqual(expected));
        Console.WriteLine(Encoding.UTF8.GetString(expected));
        Console.WriteLine(Encoding.UTF8.GetString(test));
    }
}

👇 どちらも上手く行きました！

True
0189ABEF
0189ABEF

おわりに

昨日初めて使ったんですが、SIMD はビット演算をバイト単位に拡張しただけって感じで思いのほか簡単ですね。何より Vector64 は低級言語の cmpgt_（Compare Greater Than）とか sl_（Shift Left?）に比べ特に分かりやすいです。

ちなみに SIMD を使った結果として処理が速くなっているかどうかは未検証です。

--

以上です。お疲れ様でした。