POSIX準拠のシェルスクリプトでハッシュ値を計算する（FNV-1 / FNV-1a実装） #Bash

はじめに

POSIX 準拠のシェルスクリプトでハッシュ値を計算したかったため FNV-1 / FNV-1a を実装しました。FNV-1 / FNV-1a は乗算と XOR だけを使ったシンプルなハッシュ関数です（参考 Fowler–Noll–Vo hash function）。一応断っておくとシェルスクリプトでの実装は計算速度が遅いので、特に理由がないなら md5sum や sha1sum 等を使用したほうが良いです（補足1参照）。なぜ実装したかと言うとこれらのコマンドは私が欲しかった用途には適していなかったからです。一応 POSIX 準拠でもハッシュを求めるコマンドとして cksum があり、今回実装した FNV-1 / FNV-1a も 32 bit なので衝突率も大差ないらしく、使えるには使えるのですがハッシュ値を 1 つ計算するたびに外部コマンドを呼びださなくてはなりません（補足2参照）。今回欲しかったのはファイルに対してハッシュ値を求めるのではなく、大量の文字列に対して個別にハッシュ値を計算したかったので、そのような場合にはコマンド呼び出しで時間がかかってしまいます。（またなるべく外部コマンドには依存したくないという理由もありました。）

補足1 今回の目的はセキュリティ目的ではなくハッシュの衝突率はさほど重要ではありません。これらが重要な場合は MD5 や SHA1 でも能力不足です。
補足2 cksum コマンド等は引数で複数のファイルを指定できるので、それぞれの文字列をそれぞれのテンポラリファイルに書き出して処理させればコマンド呼び出しは一回ですみますが、ファイル書き込みで遅くなるかもしれないし、流石にハッシュ値計算程度で大量にファイルを作成するのはなぁという感じです。

Go 版の実装

まず自分で実装したコードが正しいかの検証用として Go ではライブラリがあるようなのでそれを使って実装しています。

fnv.go

package main

import (
  "os"
  "fmt"
  "hash/fnv"
  "io/ioutil"
)

func fnv1(b []byte) uint32 {
  h := fnv.New32()
  h.Write(b)
  return h.Sum32()
}

func fnv1a(b []byte) uint32 {
  h := fnv.New32a()
  h.Write(b)
  return h.Sum32()
}

func main() {
  data, err := ioutil.ReadAll(os.Stdin)

  if err != nil {
    fmt.Println("err", err)
    os.Exit(1)
  }

  fmt.Printf("%x\n", fnv1(data))
  fmt.Printf("%x\n", fnv1a(data))
}

$ cat data.dat | hexdump -C
00000000  48 65 6c 6c 6f 20 57 6f  72 6c 64 0a              |Hello World.|
0000000c

$ go build fnv.go
$ fnv < data.dat
12a9a437
d8ea85d7
# 上がfnv1、下がfnv1a

バイナリデータの扱い

シェルスクリプトからバイナリデータを扱う方法については長くなったので別記事にまとめました。以下の部分に関する説明は省略します。

[ $((010)) -eq 8 ] && OCT="0" || OCT="8#"

if od -A n -t o1 -v /dev/null >/dev/null 2>&1; then
  od_command() { od -A n -t o1 -v; }
elif hexdump -e '16/1 " %03o" "\n"' -v /dev/null >/dev/null 2>&1; then
  od_command() { hexdump -e '16/1 " %03o" "\n"' -v; }
elif od -b -v /dev/null >/dev/null 2>&1; then
  od_command() { od -b -v | while IFS=" " read -r o o; do echo "$o"; done; }
else
  echo "od command not found" >&2
  exit 1
fi

read_as_binary() {
  od_command | {
    while IFS= read -r line; do
      eval "$1 $line"
    done
    "$2"
  }
}

シェルスクリプト実装（手抜き版）

ひとまずだいたいのシェルで動作する一番単純な実装です。シェルスクリプトでは計算結果が 32 bit とは限らないので 0xFFFFFFFF でマスクしている所が違う程度でアルゴリズムは同じです。乗算と XOR （そして追加の AND ）からなる実にシンプルなアルゴリズムですね。

# 詳細は「バイナリデータの扱い」参照
[ $((010)) -eq 8 ] && OCT="0" HEX="0x" || OCT="8#" HEX="16#"

fnv1() {
  for oct; do
    hash=$(( ( ($hash * $FNV_PRIME_32) & ${HEX}FFFFFFFF) ^ ${OCT}$oct ));
  done
}

fnv1a() {
  for oct; do
    hash=$(( ( ($hash ^ ${OCT}$oct) * $FNV_PRIME_32) & ${HEX}FFFFFFFF ))
  done
}

finished() {
  printf "%8x\n" $hash
}

FNV_OFFSET_BASIS_32=2166136261
FNV_PRIME_32=16777619

hash=$FNV_OFFSET_BASIS_32
read_as_binary fnv1 finished < data.dat
# => 12a9a437

hash=$FNV_OFFSET_BASIS_32
read_as_binary fnv1a finished < data.dat
# => d8ea85d7

# 注意 zsh を除く シェルは NULL 文字 (\0) を変数に入れられないのでデータ(data.dat)に
# NULL 文字が含まれていないと保証できない場合はデータを変数に入れることは出来ません
# data.dat を 2 回読み込んでるのはそのためです

符号付き32bit整数対応

アルゴリズム的には上記のコードで良いのですが、動作しないシェルがあります。mksh と 32bit 環境の dash、posh、pdksh です。これらのシェルでは d8ea85d7 ではなく ffffffffd8ea85d7 と出力されてしまいます。

これらのシェルで数値が符号付き32bit整数として扱われているため上位ビットが 1 の場合にマイナス値と認識されこの様な結果となっています。対応は簡単でマイナスであれば（下位）32bit を2つに分けて出力するだけです。

finished() {
  if [ "$hash" -lt 0 ]; then
    printf "%4x%4x\n" $(( ($hash >> 16) & ${HEX}FFFF )) $(( $hash & ${HEX}FFFF ))
  else
    printf "%8x\n" $hash
  fi
}

古い ksh のバグ対応

debian 3.1/4.0　時代の ksh 93q/93r の話なので通常は対応する必要はないでしょう。なぜか ${HEX}FFFFFFFF 書くと xFFFFFFFF: parameter not set などとエラーが表示されてしまいます。いずれも固定値なので 10 進数表記にすることにします。

ksh の浮動小数点演算の精度問題

さて実はここからが問題です。ksh だけ全く異なる計算結果になりました。計算途中の値を詳しく見ていくと途中で計算した値がわずかにずれています。（ハッシュ値の性質上、途中で少し値が異なれば、その後は全く違ったものとなります。）次のコードはそれを再現する簡単なコードです。

# 値が変わっている
ksh -c 'echo $((111111111111111111))'
111111111111111104

# 変数に入れればいけるか思いきや計算するとだめ
ksh -c 'a=111111111111111111; echo $((a))'
111111111111111111
ksh -c 'a=111111111111111111; echo $((a+0))' 
111111111111111104

# typeset -iで整数型にしてもだめ
$ ksh -c 'typeset -i a=123456789012345; typeset i=10; typeset -i a=$((a*i)); echo $a'
-2147483648
$ mksh -c 'typeset -i a=123456789012345; typeset i=10; typeset -i a=$((a*i)); echo $a'
1015724730

ですがこれ WSL1 だけなんですよね・・・。Linux や Windows 上の Docker などでは再現しません。詳しくないのですがおそらくFPUの浮動小数点数の精度のモード（変更可能）が違っているのだと思います。

インテル(R) C++ コンパイラ Linux* と Windows* システムでの浮動小数点ユニット (FPU) 精度の違い

Linux* 上では、デフォルトの FPU 精度は 64 ビットです。これは、-pc80 オプションと同じです。Windows* 上では、デフォルトの FPU 精度は 53 ビットで、対応するオプションは -Qpc64 です。この違いにより、同じプログラムまたはアルゴリズムを Linux と Windows 上で実行すると、結果が異なる場合があります。
これらの処理は OS レベルで行われ、コンパイラが処理することはありません。

数値が 53 bit 以内に収まっているなら誤差は発生しないので計算式を工夫し、53 bit を超えないようにします。53bit を超える可能性があるのは以下の部分です。

fnv1: $hash * $FNV_PRIME_32
fnv1a: ($hash ^ ${OCT}$oct) * $FNV_PRIME_32)

FNV_PRIME_32 の値が 16777619 と大きな数値になっているため、被乗数が大きな数値（例 0xFFFFFFFF）だと計算結果が 0x16777618E98889E7（16桁）となり、53 bitで表せる最大値の 0x1fffffffffffff（14桁）を超えてしまいます。そのため上位 16 bitと下位 16 bitに分けて計算します。0xFFFF * 16777619 であれば、最大 0x1000092FE6D（11桁）にしかならないので 53 bit に収まります。

シェルスクリプト実装（完成版）

これで終わりなので最終的なコードとしてまとめます。（余談途中変なところで継続行にしてるのはシンタックスハイライトが << でおかしくなるため）

[ $((010)) -eq 8 ] && OCT="0" || OCT="8#"

if od -A n -t o1 -v /dev/null >/dev/null 2>&1; then
  od_command() { od -A n -t o1 -v; }
elif hexdump -e '16/1 " %03o" "\n"' -v /dev/null >/dev/null 2>&1; then
  od_command() { hexdump -e '16/1 " %03o" "\n"' -v; }
elif od -b -v /dev/null >/dev/null 2>&1; then
  od_command() { od -b -v | while IFS=" " read -r o o; do echo "$o"; done; }
else
  echo "od command not found" >&2
  exit 1
fi

read_as_binary() {
  od_command | {
    while IFS= read -r line; do
      eval "$1 $line"
    done
    "$2"
  }
}

fnv1() {
  for oct; do
    hash=$(( ( (((($hash >> 16) * $FNV_PRIME_32) & 65535) << \ 
      16) + (($hash & 65535) * $FNV_PRIME_32 ) ) & 4294967295 ))
    hash=$(($hash ^ ${OCT}$oct))
  done
}

fnv1a() {
  for oct; do
    hash=$(($hash ^ ${OCT}$oct))
    hash=$(( ( (((($hash >> 16) * $FNV_PRIME_32) & 65535) << \
      16) + (($hash & 65535) * $FNV_PRIME_32 ) ) & 4294967295 ))
  done
}

finished() {
  if [ $hash -lt 0 ]; then
    printf "%4x%4x\n" $(( ($hash >> 16) & 65535 )) $(( $hash & 65535 ))
  else
    printf "%8x\n" $hash
  fi
}

FNV_OFFSET_BASIS_32=2166136261
FNV_PRIME_32=16777619

hash=$FNV_OFFSET_BASIS_32
read_as_binary fnv1 finished < data.dat
# => 12a9a437

hash=$FNV_OFFSET_BASIS_32
read_as_binary fnv1a finished < data.dat
# => d8ea85d7

さいごに

今回ハッシュアルゴリズムとして FNV-1 / FNV-1a を選んだ理由はシェルスクリプトでもシンプルに実装できて計算コストも低いだろうと思ってのことだったのですが浮動小数点演算の精度問題で少し想定外なコードになってしまいました。実は FNV-1a を使ったコードはすでに使用していてるのですが記事にまとめているうちに気づいたので、つまり今使っている実装はバグが有るということです。クリティカルな所ではないのでそんなに問題はないのが救いですが、そのうちバグを修正するか他のハッシュアルゴリズムに変更すると思います。ElfHashなんかアルゴリズム的に今回の問題は発生しなさそうなんで良いんじゃないかなーって思っています。