ハッシュ値の検証と UTF-8 と SIMD

ハッシュ値の検証を行う場合、何かしらの方法でハッシュのバイト列を取得する必要があります。^[1]

方法としては主に２つ、

• 16進数文字列からバイト列を復元
• Base64文字列からバイト列を復元

があります。

生の UTF-8 が渡せない問題

.NET には Convert.FromHexString という、そのものズバリのメソッドがあるんですが、コレは ReadOnlySpan<char> を渡す必要があります。

つまり生の UTF-8 バイト列を渡せないという事です。そして Unity ではこのメソッド自体が使えません。

Base64 向けに Convert.TryFromBase64Chars という API もありコチラは Unity でも使えますが、やはり生の UTF-8 バイト列を渡せません。

直接渡せるようにしよう！

👇 入力バイト列は検証済みで正しい16進数文字列という前提です。

検証環境： https://dotnetfiddle.net/

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

public class Program
{
    public static void UnsafeConvertHexAsciiStringToBytes(ReadOnlySpan<byte> utf8, Span<byte> result, out int bytesWritten)
    {
        int resultIndex = 0;

        unchecked  // believe!!
        {
            for (int i = 0; i < utf8.Length; i += 2)
            {
                var upper = utf8[i];
                var lower = utf8[i + 1];

                const byte ALPHABET_OFFSET = (byte)'a' - 10;

                if (upper <= (byte)'9')
                    upper -= (byte)'0';
                else
                    upper = (byte)((upper | 0x20) - ALPHABET_OFFSET);

                if (lower <= (byte)'9')
                    lower -= (byte)'0';
                else
                    lower = (byte)((lower | 0x20) - ALPHABET_OFFSET);

                result[resultIndex] = (byte)((upper << 4) | lower);
                resultIndex++;
            }
        }

        bytesWritten = resultIndex;
    }

    public static void Main()
    {
        // アルファベットは大文字小文字どっちでもおｋ
        const string HASH = "9F86D081884C7d659a2feAa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08";
        var expected = Convert.FromHexString(HASH);
        
        var test = (stackalloc byte[HASH.Length / 2]);
        UnsafeConvertHexAsciiStringToBytes(Encoding.UTF8.GetBytes(HASH), test, out var len);

        Console.WriteLine(test.SequenceEqual(expected));
        Console.WriteLine(string.Join(" ", expected.Select(x => x.ToString("x2")).ToArray()));
        Console.WriteLine(string.Join(" ", test.ToArray().Select(x => x.ToString("x2")).ToArray()));
    }
}

👇 出来ました！

True
9f 86 d0 81 88 4c 7d 65 9a 2f ea a0 c5 5a d0 15 a3 bf 4f 1b 2b 0b 82 2c d1 5d 6c 15 b0 f0 0a 08
9f 86 d0 81 88 4c 7d 65 9a 2f ea a0 c5 5a d0 15 a3 bf 4f 1b 2b 0b 82 2c d1 5d 6c 15 b0 f0 0a 08

解説

入力は全て正しい前提なので (byte)'9' 以下なら 0-9 のハズ、という事で 0 のアスキーコード分を減算して文字列から数値に変換しています。良くあるやつですね。

そして数字以外の場合は A-F a-f のどれかなので c | 0x20 します。コレを行うと大文字を小文字に変換でき、数字や小文字の場合は何も起きません。ASCII コード表は良くできています。

後はビット演算の結果から (byte)'a' - 10 を減算すれば文字 a-f を数値 10-15 に変換できます。

ちなみに c & ~0x20 は数字に影響が出ます。なので 0-F 22 文字のルックアップテーブルが作れそうで作れない。

最後の (upper << 4) | lower は upper * Math.Pow(2, 4) + lower と同じです。１文字目が上位４ビットで２文字目が下位４ビットを表している、とも言えます。

SIMD 対応

ベクトル化できそうな匂いがプンプンしますね。やってみます。※ .NET 7+

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

using System;
using System.Runtime.Intrinsics;

public class Program
{
    public static void Main()
    {
        SIMD(new byte[] { (byte)'0', (byte)'1', (byte)'8', (byte)'9', (byte)'a', (byte)'B', (byte)'E', (byte)'f' });
    }

    public static void SIMD(ReadOnlySpan<byte> bytes)
    {
        unchecked
        {
            var makeNumbersNegative = Vector64.Create((sbyte)('9' + 1));
            var makeLettersLowercase = Vector64.Create((sbyte)0x20);
            var numberOffset = Vector64.Create((sbyte)'0');
            var letterOffset = Vector64.Create((sbyte)('a' - 10));
            var zero = Vector64.Create((sbyte)0);
            // リトルエンディアンの ushort として解釈出来るように（意味ある？）
            const sbyte ZEROFILL = (sbyte)0x80;
            var takeUpper = Vector64.Create((sbyte)0, ZEROFILL, 2, ZEROFILL, 4, ZEROFILL, 6, ZEROFILL);
            var takeLower = Vector64.Create((sbyte)1, ZEROFILL, 3, ZEROFILL, 5, ZEROFILL, 7, ZEROFILL);

            for (int i = 0; i < bytes.Length; i += 8)
            {
                var vec = Vector64.Create(
                    (sbyte)(bytes[i/**/]),
                    (sbyte)(bytes[i + 1]),
                    (sbyte)(bytes[i + 2]),
                    (sbyte)(bytes[i + 3]),
                    (sbyte)(bytes[i + 4]),
                    (sbyte)(bytes[i + 5]),
                    (sbyte)(bytes[i + 6]),
                    (sbyte)(bytes[i + 7]));

                vec = Vector64.BitwiseOr(vec, makeLettersLowercase);

                var cond = Vector64.GreaterThan<sbyte>(zero, Vector64.Subtract(vec, makeNumbersNegative));
                var offset = Vector64.ConditionalSelect(cond, numberOffset, letterOffset);
                var values = Vector64.Subtract<sbyte>(vec, offset);
                Console.WriteLine(values);

                // ココから ushort x4
                var upper = Vector64.ShiftLeft(Vector64.Shuffle(values, takeUpper).AsUInt16(), 4);
                Console.WriteLine(upper);

                var result = Vector64.Add(upper, Vector64.Shuffle(values, takeLower).AsUInt16());

                Console.WriteLine();
                Console.WriteLine(result);
            }
        }
    }
}

👇 上手くできたようです！

SIMD(new byte[] { (byte)'0', (byte)'1', (byte)'8', (byte)'9', (byte)'a', (byte)'B', (byte)'E', (byte)'f' });

<0, 1, 8, 9, 10, 11, 14, 15>
<0, 128, 160, 224>

<1, 137, 171, 239>

解説

解説もベクトル化してみました。

1	2	3	4	5	6	7	8
全ての入力値に 0x20 を OR する	アルファベットのみ正の値になるように '9' + 1 を減算	数字は負、アルファベットは正なので Greater Than でマスクを作る	Conditional Select で数字とアルファベットそれぞれに適したオフセットを取得	0x20 を OR した結果からオフセットを減算する	オフセットした結果の上位４ビットを Shuffle で ushort x4 に変換して左シフト	シフト結果に Shuffle で ushort x4 に変換した下位４ビットを加算	結果をバイト配列に詰める

Unity

Unity では残念ながら Vector64 が使えません。

Burst パッケージには Unity.Burst.Intrinsics という SIMD 関連のアレコレが入っていますが、パッと見た感じ byte/sbyte をビットシフトしたり乗算する方法が無さそうな？（浮動小数点とか short/int は対応してそう）

byte/sbyte で出来ることは加算・減算程度のようです。ただ、未対応という訳じゃなく BurstCompile 属性を付ければコンパイル時に良きようにやってくれるようです。が！ 任意のタイミングで実行することは出来ないようです。うーん。。。

Base64

Base64 の変換は Unity にも存在する既存の API を使うのが良いと思います。6 ビット区切りとか面倒なので自前実装は秒で諦めましたｗ

👇

var chars = (stackalloc char[sourceBytes.Length]);

for (int i = 0; i < sourceBytes.Length; i++)
{
    chars[i] = (char)sourceBytes[i];
}

return Convert...

全て ASCII 文字だから

MemoryMarshal.Cast<byte, char>(utf8Bytes) すればいいだけの筈なのに失敗する！ なんで！？！？ でしばらく悩みましたｗ

正しくは

var charBytes = (stackalloc byte[sourceBytes.Length * 2]);

for (int i = 0; i < sourceBytes.Length; i++)
{
    charBytes[i * 2 /* ビッグエンディアンなら +1 */] = sourceBytes[i];
}

var chars = MemoryMarshal.Cast<byte, char>(charBytes);

ですね。C# の char は２バイトです。

Base64 か16進数か

一瞬、Unity で使える API あるし文字列として短くできるし Base64 の方が良いのでは？ と思いましたが、ハッシュ値のような小さなデータで Base64 を使うのはダメです。圧縮率は高いですが面倒すぎます。なぜ .NET 黎明期に 16 進数表記をバイト列に変換する API が無かった？ って話です。

16 進数表記は単純でベクトル化との相性も抜群（データが小さすぎて意味ないかも？）ハッシュ値は 16 進数表記一択です。

AI も概ね想像通りの返答

ハッシュ値が一般的に Base64 ではなく 16 進数 (hex) 表記で表示されるのには、いくつかの理由があります。

1. 可読性とデバッグの容易さ:

• 人間にとっての理解: 16 進数は 0-9 と A-F の 16 種類の文字で構成されており、各桁が 4 ビットに対応しています。これにより、ハッシュ値をバイト列に変換したり、ビット操作を追跡したりする際に、人間が比較的容易に理解しやすくなります。例えば、2 桁の 16 進数は 1 バイト (8 ビット) を表します。
• デバッグの利便性: プログラミングやシステム開発の現場では、ハッシュ値をログに出力したり、エラーメッセージに含めたりする機会が多くあります。16 進数表記は、Base64 に比べて視覚的に区切りやすく、コピー&ペーストの際にも誤りが起こりにくいという利点があります。

2. 伝統と標準:

• 歴史的な経緯: 暗号技術やハッシュ関数の黎明期から、ハッシュ値やバイナリデータを 16 進数で表現する方法が広く用いられてきました。多くのツールやライブラリが 16 進数での出力をデフォルトとしているため、その慣習が現在まで引き継がれています。
• 互換性: 多くのシステムやプロトコルが、ハッシュ値を 16 進数でやり取りすることを前提としています。Base64 を使用すると、これらのシステムとの互換性を保つために追加の変換が必要になる場合があります。

3. 簡潔さと効率性:

• バイト境界の明確さ: 16 進数表記は、2 文字で 1 バイトを表現するため、バイト境界が明確です。これは、バイナリデータを扱う上で直感的であり、プログラミング処理も容易になります。
• エンコード・デコードの単純さ: 16 進数とバイト列の変換は、Base64 のような複雑なルックアップテーブルやパディング処理を必要とせず、比較的単純な処理で実現できます。

Base64 の利用が少ない理由:

• 非 URL セーフな文字: Base64 には / や + などの URL で特別な意味を持つ文字が含まれており、URL に直接含める際にはエンコードが必要になる場合があります。
• 視覚的な紛らわしさ: Base64 の文字セットには、1、l、I や 0、O など、視覚的に紛らわしい文字が含まれているため、人間が手作業で比較したり転記したりする際に誤りが発生しやすい可能性があります。
• パディングの存在: Base64 は、入力データの長さが 3 バイトの倍数でない場合にパディング (=) を使用するため、ハッシュ値の長さにばらつきが生じることがあります。

ただし、Base64 が全く利用されないわけではありません。例えば、バイナリデータをテキスト形式で安全に伝送する必要がある場合や、データ量を削減したい場合には Base64 が用いられることがあります。

結論として、ハッシュ値が一般的に 16 進数で表記されるのは、可読性、デバッグの容易さ、歴史的な経緯、既存のシステムとの互換性、そしてバイト境界の明確さといった実用的な理由に基づいています。

おわりに

最新の .NET 環境でも生の UTF-8 を渡せません。ん？ って感じですね。そんなにレアなケースでしょうか。

今回の UnsafeConvertHexAsciiStringToBytes もそうですが、Encoding.UTF8.GetBytes みたいな API って呼び出し側で stackalloc char[] しなきゃいけないから使い勝手悪いんですよねー。拡張メソッド限定で内部で確保したスパンを返せるようにならないですかね。

戻り値に scoped を付けて呼び出し側に制約を与えれば行けそうなイメージをずっと持ってるんですが、scoped 属性は受け取り側の挙動を変えるだけのようで、まったく使いどころが分かんないですね？

--

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

脚注

1. 必ずしも元のバイト列を復元しなければならない訳ではありません。https://zenn.dev/sator_imaging/articles/2808a60f9ee64e