妖怪道中記のパスワード解析関連のあれこれ
https://twitter.com/4STUDIO4/status/1472415489595174912
yokai_dfs.cpp: シングルスレッドな一方向 DFS 探索 yokai_dfs_threads.cpp: マルチスレッドな一方向 DFS 探索 yokai_bw.cpp & yokai_fw.cpp: マルチスレッドな前方&後方探索による挟み撃ち探索。bw->fw の順に実行する。bw で後方から最大 6 段を展開し、fw ではその結果をメモリに展開して、前方からの探索結果が一致したら出力、という動作 yokai_fw_bw.cpp: 前方・後方探索それぞれを実行してストレージに出力、最後にそれを照合して一致したものを結果出力、という動作するので、前方後方ともに 7 段ずつで動作可能(1.5TB くらいストレージを使うし、メモリはピーク時 360GB くらい使う)。残念ながらバグがあり、14 桁パスワードの約 4700 万件のうち 40 件を見落とす
WASM ってリポジトリ名に入ってるのは最初 Emscripten で Web ブラウザ実行可能にしようと思ってた名残り。やっぱこういう計算はネイティブが強い。