Duplicut :scissors:

巨大な単語リストの重複を高速に除去し、順序は変更しません

📖 概要

今日では、パスワード単語リストの作成は通常、複数のデータソースを連結することを意味します。

理想的には、最も可能性の高いパスワードが単語リストの先頭に位置し、最も一般的なパスワードが瞬時に解読されるべきです。

既存の重複除去ツールでは、順序を維持するか巨大な単語リストを扱う**かを選択せざるを得ません。

残念ながら、単語リストの作成には両方が必要です

そこで私は、この非常に特殊なニーズに対応するため、高度に最適化されたC言語で duplicut を作成しました 🤓 💻

💡 クイックスタート

git clone https://github.com/nil0x42/duplicut  # download ...
cd duplicut/ && make                           # compile ...
./duplicut wordlist.txt -o clean-wordlist.txt  # dedupe !!!

🔧 オプション

-o, --outfile <FILE>       結果を <FILE> に書き込む
-t, --threads <NUM>        使用する最大スレッド数 (デフォルトは最大)
-m, --memlimit <VALUE>     使用する最大メモリを制限 (デフォルトは最大)
-l, --line-max-size <NUM>  最大行サイズ (デフォルト 1024, 最大 4095)
-p, --printable            ASCII 表示可能行のみフィルタリング
-c, --lowercase            単語リストを小文字に変換
-C, --uppercase            単語リストを大文字に変換
-D, --dupfile <FILE>       重複を <FILE> に書き込む (duplicut の速度低下)
-h, --help                 このヘルプを表示して終了
-v, --version              バージョン情報を表示して終了

• 機能:

  • 利用可能なRAMを超えるサイズであっても、巨大な単語リストを処理可能
  • --line-max-size オプションで行の最大長でフィルタリング
  • --printable オプションで非表示可能ASCII文字を含む行を除外
  • 見つかった重複を別のファイルに保存 (--dupfile オプション)
  • --lowercase または --uppercase オプションで大文字小文字を無視
  • ETA付きのプログレスバーを表示

• 実装:

  • 高速設計の純粋なCコードで記述
  • 64ビットプラットフォームで圧縮されたハッシュマップ項目
  • マルチスレッド対応

• 制限事項:

  • --line-max-size は 4095 を超えることはできません

📖 技術詳細

🔸 1- メモリ最適化:

ポインタの余分ビット内に size 情報を詰め込むことで、uint64 でハッシュマップ内の行をインデックス化できます:

🔸 2- 大規模ファイル処理:

ファイル全体がメモリに収まらない場合、各チャンクが可能な限り多くのRAMを使用するように、ファイルは 個の仮想チャンクに分割されます。

各チャンクはハッシュマップにロードされ、重複が除去され、後続のチャンクに対してテストされます。

これにより、実行時間は最大で 番目の三角数に減少します:

💡 トラブルシューティング

バグを発見した場合、または期待通りに動作しない場合は、duplicut をデバッグモードでコンパイルし、出力を添付してissueを報告してください:

# デバッグレベルは 1 から 4 まで指定可能
make debug level=1
./duplicut [OPTIONS] 2>&1 | tee /tmp/duplicut-debug.log