pwned-passwords-search2.rb

#!/usr/bin/env ruby
# pv -cN Input pwned-passwords-2.0.txt | cut -b 1-32 | sort -S 8G | xxd -r -p | pv -cN Output >pwned-passwords-2.0.trunc.bin

require 'digest/sha1'

def interposearch(io, key)
  rs = key.size
  lo = 0
  hi = (io.size / rs) - 1

  pread = Hash.new do |h,k|
    io.pos = k * rs
    h[k] = io.read(rs)
  end

  as_int = Hash.new do |h,k|
    h[k] = k.unpack('N').first
  end

  while hi != lo && key >= pread[lo] && key <= pread[hi]
    mid = lo + ((as_int[key] - as_int[pread[lo]]) * (hi - lo) / (as_int[pread[hi]] - as_int[pread[lo]]))

    case key <=> pread[mid]
    when  0 then return mid * rs
    when  1 then lo = mid + 1
    when -1 then hi = mid - 1
    end
  end

  if key == pread[lo]
    return lo * rs
  else
    return false
  end
end

db = File.new('pwned-passwords-2.0.trunc.bin', 'rb')

loop do
  print "Password: "
  pass = $stdin.gets&.chomp
  exit if pass.nil? || pass.empty?

  a = Time.new
  hash = Digest::SHA1.digest(pass)[0,16]
  puts "Found: %s in %.2f ms" % [interposearch(db, hash), (Time.new - a) * 1000]
end