SkiaSharp.QrCodeをフルリファクタしてC#最速のQRコード生成ライブラリにした

SkiaSharp.QrCodeはC#でQRコードを生成するためのライブラリです。コードは大きく「QRコードデータの生成処理」と「SkiaSharpによるレンダリング統合」の2要素で成り立っています。今回、QRコードデータ生成部分をフルリファクタリングしてC#で最速のQRコード生成ライブラリに仕上げ、他のQRコード生成ライブラリやシリアライザを参考にレンダリングAPIを見直して使い勝手も改善しました。

本記事は新APIでQRコードを生成する例や、リファクタリングの備忘録です。

リファクタリングの背景
主な改善点
パフォーマンス比較
利用例
- QRコードデータ部分だけを生成する
- Instagram風のカラフルQRコードを生成する
リファクタリング
今後
まとめ

リファクタリングの背景

SkiaSharp.QrCodeは元々、Azure Functions上でQRコードを生成する必要があったために開発しました。当時はC#でQRコードを生成するライブラリが少なく、またAzure Functions上でSystem.Drawingに依存しないQRコード生成ライブラリが必要だったのです。用途的にもパフォーマンスは割とどうでもよく、とにかく動けば良いというスタンスで開発を進めました。

その後、私自身がQRコードを活用する機会が減ったこともありライブラリを半ば放置していたのですが、最近になって使い勝手の面とSkiaSharp最新版でビルド通らなくなった問題が気になり始めました。先日、NuGetのTrusted Publishing対応の一環でメンテをするしない判断をしていて、やる気になったので全面的に見直しました。やる気駆動開発です。

主な改善点

リファクタリングの目的は、QRコード生成のパフォーマンス向上とAPIの使い勝手改善です。特にQRコード生成を最速にし、メモリアロケーションを限りなくゼロに近づけることを目指しました。また、API面ではIDisposableを廃止しユーザーがアロケーションを気にせず済むよう、IBufferWriterを活用してユーザーが任意のメモリ管理をできるようにすることを目指しました。レンダリング回りでも、静的な簡易メソッドと柔軟なBuilder APIの両方を提供することで、様々なユースケースに対応できることを目指しました。

具体的な改善点は以下の通りです。ライブラリは引き続き.NET Standard 2.0, 2.1をサポートしつつ、.NET 8以降でSIMD命令を活用できるようにしています。

QRコードにするデータをバイナリ形式のまま扱えるように変更、QRコードデータの生成過程での変換コストを削除
QRコードデータ生成部分のアルゴリズムを最適化
QRコードデータ生成過程の各処理をパイプライン形式で当てられるように内部APIを整理
内部処理にstruct、Span、ArrayPoolを活用してQRコードデータ生成過程のGCゴミをゼロ化(必要なメモリはQRコードデータのバイナリのみ)
処理量が大きく増える箇所はSIMD命令へ分岐
既存のQRコード生成結果を破壊しないようにユニットテストを整備
NativeAOT対応 (WASMにはもともと対応済み)
IDisposableを廃止し静的メソッドとBuilder APIを提供
入力データに応じたエンコーディングの自動選択を改善

パフォーマンス比較

パフォーマンスやAPI変更は0.9.0で導入しました。0.8.0と0.9.0のパフォーマンスを比較した結果が以下の通りです。0.8.0はパフォーマンスを無考慮だったこともあり、0.9.0で見られる数字になっています。

ケース	速度向上率	メモリ使用の減少率
URL 26文字 (L)	34倍高速化	1/1637
ASCII 53文字 (L)	57倍高速化	1/2182
ASCII 153文字 (Q)	36倍高速化	1/3156

また、C#の他のQRコード生成ライブラリとのパフォーマンス比較も行いました。QRコード生成速度、メモリアロケーション共にSkiaSharp.QrCodeが最速、省メモリです。SkiaSharp.QrCodeのメモリアロケーションは、QRコードの生成過程はゼロアロケーション、最終的なバイナリデータ+クワイエットゾーン分のみメモリアロケートしています。

C#のQRコードライブラリとの比較

0.8.0のパフォーマンス

0.9.0のパフォーマンス

利用例

例えば、URLhttps://example.comをQRコードにしてPNG画像とする場合、以下のように書けます。

var pngBytes = QRCodeImageBuilder.GetPngBytes("https://example.com");

また、より柔軟に設定したい場合はBuilder APIを使うこともできます。

var pngBytes = new QRCodeImageBuilder("https://example.com")
    .WithSize(512, 512)
    .WithErrorCorrection(ECCLevel.H)
    .ToByteArray();

個人的にゴールとしたAPIは次のような書き味です。これはLinqPadでQRコードを生成して表示する例ですが、QrCoderがこのようなAPIを提供しており、SkiaSharp.QrCodeでも同様の使い勝手を提供したいと考えていたものです。

Bitmap.FromStream(new MemoryStream(QRCodeImageBuilder.GetPngBytes("WIFI:T:WPA;S:mynetwork;P:mypass;;"))).Dump();

LINQPadでQRコード表示

QRコードデータ部分だけを生成する

SkiaSharp.QrCodeはQRコードデータ生成部分とSkiaSharpインテグレーション部分を分離しており、QRコードデータ部分だけ利用できます。 QRコードデータ部分を使うことで、他のライブラリでレンダリングしたり、コンソールアプリケーション上でQRコードを表示したりできます。

// サンプルコード: https://github.com/guitarrapc/SkiaSharp.QrCode/blob/d1d95d53354c503d6841491022aa009f84627356/samples/ConsoleApp/Program.cs

// コンソールアプリケーション上でemojiを表示するため出力エンコーディングをUTF-8に設定
Console.OutputEncoding = System.Text.Encoding.UTF8;

// QRコードデータ部分(QuietZoneを含む)を生成
var qrCodeData = QRCodeGenerator.CreateQrCode("https://example.com/foo/bar?path=123", ECCLevel.H);

// qrCodeDataの配列にrow/colでアクセスしてQRコードを任意の文字で表示
for (var row = 0; row < qrCodeData.Size; row++)
{
    for (var col = 0; col < qrCodeData.Size; col++)
    {
        Console.Write(qrCodeData[row, col] ? "🔵" : "  ");
    }
    Console.Write("\n");
}

コンソールアプリケーションでemojiを使ってQRコード表示

QRコードデータにレンダリング情報を含まないため、コンパクトにシリアライズ/デシリアライズも可能です。 QrCodeData.GetRawData(IBufferWriter<byte>)オーバーロードを使うと、ユーザーが用意したバッファに直接書き込んでゼロアロケーションでシリアライズできます。

// QRコードデータ部分(QuietZoneを含む)を生成
var qrCodeData = QRCodeGenerator.CreateQrCode("https://example.com/foo/bar?path=123", ECCLevel.H);

// QRコードデータをバイナリ配列にシリアライズ。
var serialized = qrCodeData.GetRawData();

// バイナリ配列からQRコードデータを復元 (quietzone: 4 はCreateQrCodeのデフォルト値)
var deserialized = new QRCodeData(serialized, quietZoneSize: 4);

Instagram風のカラフルQRコードを生成する

QRコードはアプリケーション同士のユーザー情報や特定のデータを共有するために使われることが多いです。例えばInstagramでは、プロフィールページをQRコードで共有できます。このQRコードはアプリのブランドカラーに沿ってグラデーションカラーが使われていますが、SkiaSharp.QrCodeを使うと、同様のカラフルなQRコードも簡単に生成できます。

以下はInstagram風のグラデーションカラーを使ったQRコード生成例です。細かいことをいうと、InstagramはQRコードのモジュールサイズ(丸部分)をランダムに変化させているため、完全に同じにはなりませんが、近い見た目のQRコードを生成できます。

var content = "https://github.com/guitarrapc/SkiaSharp.QrCode/blob/main/README.md?foo=sample&bar=dummy";
var iconInstaPath = @"./samples/ConsoleApp/samples/insta.png";

// Instagram gradient colors (orange -> pink -> purple)
var instagramGradient = new GradientOptions(
    [
        SKColor.Parse("FCAF45"),  // Orange
        SKColor.Parse("F77737"),  // Orange-Red
        SKColor.Parse("E1306C"),  // Pink
        SKColor.Parse("C13584"),  // Purple
        SKColor.Parse("833AB4")   // Deep Purple
    ],
    GradientDirection.TopLeftToBottomRight,
    [0f, 0.25f, 0.5f, 0.75f, 1f]);

// Load Instagram logo (if you have one)
// For this example, we'll use the test icon
using var logo = SKBitmap.Decode(File.ReadAllBytes(iconInstaPath));
var icon = new IconData
{
    Icon = logo,
    IconSizePercent = 11,
    IconBorderWidth = 20,
};

var qrBuilder = new QRCodeImageBuilder(content)
    .WithSize(1024, 1024)
    .WithErrorCorrection(ECCLevel.H) // IconDataでデータを意図的に欠損しているのでH推奨
    .WithQuietZone(4)
    .WithColors(
        backgroundColor: SKColors.White,
        clearColor: SKColors.White)
    .WithModuleShape(CircleModuleShape.Default, sizePercent: 0.95f)
    .WithGradient(instagramGradient)
    .WithIcon(icon);

var pngBytes = qrBuilder.ToByteArray();
Bitmap.FromStream(new MemoryStream(pngBytes)).Dump();

Instagram風QRコード

リファクタリング

リファクタリング前にデータ整合性とパフォーマンスを測定できるようにします。これだけはリファクタリング前にやっておかないと、リファクタリング後に動作が変わってしまった場合に原因を特定できなくなるためです。具体的には以下の2点を実施しました。

リファクタリング前のコードでQRコードを生成し、生成結果が同一であることを確認するユニットテストを整備 (以前からあったのでデータ回りを中心に拡充)
ベンチマークコードを用意して、パフォーマンスやメモリの使用状況を測定できるようにする

QRコードは究極的にいうとただの0/1バイナリ配列なので、リファクタリング前後で生成されるQRコードデータが完全に同一であれば、リファクタリング前後で動作が変わってしまうことはありません。ユニットテストで生成結果の整合性を確認できるようにした上で、ベンチマークを見ながら少しずつ内部実装を改善していきました。具体的には以下の2つのIssueで改善を進めました。

リファクタリング方針

リファクタリングの方針としては、以下の3点を重視して進めました。パブリックAPIは基本ノータッチ¹で、内部APIを変更し、パフォーマンスとメモリ使用量を削減しています。QRコード生成処理をパイプライン的にあてられるよう整理して、文字列版とバイナリ版の2系統でAPI互換性を保ちながら進めることで、途中段階でも文字列実装とバイナリ実装を比較しつつパフォーマンス測定ができるようにしました。

内部処理をパイプライン形式に整理
内部表現をバイナリ化、文字列変換を排除
QRコードデータ表現をBitArrayベースから1次元配列+インデクサに変更し、メモリ効率やアクセス効率を改善

QRコードの生成処理をパイプライン形式に整理すると、各処理を最適化しやすくできます。QRコードを作るまでに、エンコード処理、マスク処理、ペナルティ計算処理など段階を踏む必要があるのですが、パイプライン化すると個別に最適化でき、SIMD命令を適用可能か判断しやすくなります。全体を見通しつつ個別の課題に集中できるのは、メリットが大きいです。副次的に、テキスト処理の時の処理とバイナリ処理をオーバーロードで分けることもでき、途中段階でパフォーマンス比較がしやすくなりました。

// Encode data
var encodedBits = EncodeData(plainText, config);

// Calculate Error Correction
var codewordBlocks = CalculateErrorCorrection(encodedBits, config.EccInfo);

// Interleave data
var interleavedData = InterleaveCodewords(codewordBlocks, config.Version, config.EccInfo);

// Create QR code matrix
var qrMatrix = CreateQRMatrix(config.Version, interleavedData, config.EccLevel);

// etc...

内部処理は当初テキストで行っていました。これはつまりStringBuilderを使ったりバイナリ表現をわざわざ文字列にしていたということです。そこで上記のパイプライン化をテキスト版で先行導入しておき、バイナリ版は一部実装をバイナリ対応で書き換えて徐々に置き換えるように進めました。これにより、バイナリ版と文字列版の2系統でAPI互換性を保ちながら並列で進めることができます。

public static QRCodeData CreateQrCode(string plainText, ECCLevel eccLevel, bool utf8BOM = false, EciMode eciMode = EciMode.Default, int requestedVersion = -1, int quietZoneSize = 4)
{
    // テキスト版の実装 ...

    // Prepare configuration
    var config = PrepareConfiguration(plainText, eccLevel, utf8BOM, eciMode, requestedVersion);

    // Encode data
    var encodedBits = EncodeData(plainText, config);

    // Calculate Error Correction
    var codewordBlocks = CalculateErrorCorrection(encodedBits, config.EccInfo);

    // Interleave data
    var interleavedData = InterleaveCodewords(codewordBlocks, config.EccInfo, config.Version);

    // Create QR code matrix
    var qrCodeData = CreateQRCodeData(config.Version, interleavedData, config.EccLevel, quietZoneSize);

    return qrCodeData;
}

public static QRCodeData CreateQrCode(ReadOnlySpan<char> textSpan, ECCLevel eccLevel, bool utf8BOM = false, EciMode eciMode = EciMode.Default, int requestedVersion = -1, int quietZoneSize = 4)
{
  // バイナリ版の実装 ...

  // 省略
}

最終的にテキスト版の処理は不要になるので、内部処理の改善がすべて終わりバイナリ版に処理を統一するときはtext.AsSpan()でバイナリ版オーバーロードを呼び出すように切り替えるだけです。

public static QRCodeData CreateQrCode(string plainText, ECCLevel eccLevel, bool utf8BOM = false, EciMode eciMode = EciMode.Default, int requestedVersion = -1, int quietZoneSize = 4)
{
    // バイナリ版オーバーロードを呼び出す
    return CreateQrCode(plainText.AsSpan(), eccLevel, utf8BOM, eciMode, requestedVersion, quietZoneSize);
}

QRコードデータ表現は単純に言うとxy座標でアクセスできる2次元配列です。以前の実装ではList<BitArray>で表現していましたが、これを1次元配列+インデクサに変更しました。1次元配列にすることでメモリ効率が改善し、またインデクサを用いることでアクセス効率も改善します。BitArrayはxy座標の取得が明確なものの、アクセス効率が悪くなりSIMDや各種最適化を施しにくいと常々感じていました。

public class QRCodeData
{
    public List<BitArray> ModuleMatrix { get; set; }
}

List<BitArray>から1次元配列byte[]にするということは、QRコードの折り返しアクセスを自前で実装する必要があります。具体的には各行の幅を保持し、xy座標から1次元配列のインデックスを計算するインデクサを実装しています。簡易的に縦横ともに同サイズ前提(正方形)で実装しているためインデックス計算は非常にシンプルですが、rMQRなど非正方形のQRコードに対応する場合は見直しが必要になる想定です。

public class QRCodeData
{
    // QRコードのモジュールデータを1次元配列で保持
    private byte[] _moduleData;
    // QRコードの1辺のサイズ (モジュール数)
    private int _size;

    // インデックスアクセスできるように
    public bool this[int row, int col]
    {
        get => _moduleData[row * _size + col] != 0;
        internal set => _moduleData[row * _size + col] = value ? (byte)1 : (byte)0;
    }
}

メモリ改善

メモリ改善に最も効果があったのは、次の5点です。最も効果が大きいのはバイナリ化ですが、ゼロアロケーションを目指す上でstruct/Span/stackalloc/ArrayPoolの活用が欠かせません。地味にLINQ排除も効果が大きく、特にQRコードデータは内部の点(モジュール)の数だけループを回す必要があるため、LINQのオーバーヘッドが積み重なっていました。データ構造を1次元配列にビンパックすることで、メモリ使用量とアクセス効率が改善しました。とどめは、ある処理で不用意にリフレクションを行っていたため、switch式ベースに変更してメモリを一気に削除しました。

内部処理はバイナリ直接アクセスに変更し、文字列変換を排除
内部処理にstruct、Span、stackalloc/ArrayPoolを活用してGCゴミを削減
LINQを排除し、ループベースの処理に変更
List<BitArray>の2次元配列を廃止し、1次元配列+インデクサに変更
不要なリフレクションを排除して、switch式ベースでメソッド分岐に変更

classからstructへの変更

LINQの線形探索をルックアップテーブルに変更

QRCode表現をBitArrayから1次元バイナリに変更

マスク処理のリフレクションをswitchベースの分岐に変更

パフォーマンス改善

QRコードは、先ほど説明したようにモジュールアクセスがどうしても必要です。これは仕様にもある通り、8種類のマスクパターンから最適なものを選択するときにも必要ですし、エンコードしたデータをQRコードモジュールに配置するときにも必要です。特に、モジュールアクセスはQRコードのバージョンが上がると指数関数的に増えるため、ここをいかに高速化できるかがパフォーマンス改善の鍵となりました。あとは、ループに関係ないマスク処理のmod/div演算を事前にテーブル化してO(1)にするのも計算量を減らすのに効果的でした。結局計算量を減らすのが一番効果ある。SIMD命令も一部入れていますが、データが大きくないと効果が薄いため、QRコードとSIMD命令の相性はあまり良くない印象です。

モジュールアクセスのペナルティ計算ループを可能な限り減らす
モジュール配置をrectangleを用いたブロックチェックからbitmaskに変更
事前計算できるmod/div演算をテーブル化して高速化
モジュールアクセスをSIMD命令で高速化

モジュールアクセスのペナルティ計算ループを可能な限り減らす

モジュール配置をrectangleを用いたブロックチェックからbitmaskに変更

事前計算できるmod/div演算をテーブル化して高速化

今後

今回の対応から、今後の対応をどうするか考えていることです。

ゼロアロケーション

ゼロアロケーションは何度も検討しましたが、使い勝手と両立する道が見えず見送っています。理屈としては利用者がIBufferWriter<byte>を渡すAPIとすれば設計可能ですが、QuietZoneSizeを利用者が計算してレンダリングさせるのはちょっと厳しい印象です。今は1次元配列にしつつインデックスアクセスを提供することで、メモリ効率と使い勝手のバランスを取っています。将来的にゼロアロケーション版APIを追加する可能性はありますが、現状はアロケーションの小ささから見て優先度が低いと考えています。

QRコードの読み取り

このライブラリでは対応する予定はありません。QRコードの読み取りは画像処理が絡むため、SkiaSharp.QrCodeの責務外と考えています。C#でQRコードを読み取る場合は、ZXing.Netなどの別ライブラリを利用することをオススメします。需要が大きくなったら考えます。

rMQRなどの特殊QRコード

QRコードはDensoが特許を保持している形式(FrameQRとか)とISO/IECで仕様化されている形式(rMQRやMicro QR Code)、産業用途で利用されているGS1 QR Codeなど様々なバリエーションがあります。SkiaSharp.QrCodeはISO/IEC 18004で仕様化されている標準QRコードのみ対応しています。

将来的に需要があれば、ISO化されているrMQRやMicro QR Codeなどの特殊QRコードにも対応してもよいと考えていますが、やるならこれらを読み取れる実機が欲しいです。だれか実機ください。²