バイナリをASCIIで非常に高速にエンコードする #C

ソフトウェアでは、通常、バイナリ値を使用します。つまり、任意のバイトストリームがあります。これらの任意のバイトストリームを電子メール、HTML、XML、JSONなどの標準形式でエンコードするには、多くの場合、base64などの標準形式に変換する必要があります。base64を非常にすばやくエンコードおよびデコードできます。

しかし、標準を気にせず、高速で単純なコードを作成したい場合はどうでしょうか。たぶんあなたが気にするのは文字列がASCIIであるということだけです。つまり、各バイトの最上位ビットがゼロに設定されたバイトのストリームである必要があります。このような場合、7バイトの値を8バイトの値に変換してから元に戻す必要があります。

標準Cでは、双方向で約5つの命令（ストアと移動を数えない）でそれを行うことができます。エンコードする5つの命令と、デコードする5つの命令です。1バイトあたり1命令未満です。私は自分の解決策が最適であると自分自身に納得させることができませんでした。

// converts any value in [0, 2**56) into a value that
// could pass as ASCII (every 8th bit is zero)
// can be inverted with convert_from_ascii
uint64_t convert_to_ascii(uint64_t x) {
  return ((0x2040810204081 * (x & 0x80808080808080)) 
         & 0xff00000000000000) +
         (x & 0x7f7f7f7f7f7f7f);
}
// converts any 8 ASCII chars into an integer in [0, 2**56),
// this inverts convert_to_ascii
uint64_t convert_from_ascii(uint64_t x) {
  return ((0x102040810204080 * (x >> 56)) 
         & 0x8080808080808080) +
         (x & 0xffffffffffffff);
}

最近のIntelプロセッサでは、pdep / pext命令が同じ目的を果たす場合があります。ただし、AMDプロセッサでは低速であり、ARMでは対応するものがありません。

英語原稿：https://lemire.me/blog/2020/05/02/encoding-binary-in-ascii-very-fast/