=begin

    Given:
        1. a hash
        2. a hashing algorithm
        3. the length of the original message
        4. the alphabet of the original message

    Bruteforce the original message by randomly iterating through the search space.
    To take advantage of a multicore CPU, execute this script using JRuby.

    As an example, this script searches for a randomly generated password.

=end

# perform an in-place Fisher-Yates shuffle
class Array
    def shuffle!
        j = length
        i = 0
        while j > 1
            r = i + rand(j)
            self[i], self[r] = self[r], self[i]
            i += 1
            j -= 1
        end
        self
    end
end

# map an integer to a string
def dec2base(int)
    ret = ""
    while int > 0
        ret = "#{ALPHABET[int % ALPHA_SIZE]}#{ret}"
        int /= ALPHA_SIZE
    end
    ret.rjust(PW_LEN, ALPHABET[0])
end

# example hash function
def hash(str)
    str.crypt("..")
end

# check if a string maps to the target hash
def check(int)
    str = dec2base(int)
    if hash(str) == $target
        puts "match:   #{str}  =>  #{hash(str)}"
        $found = true
        exit
    end
end

# partition a range into an array of N equal-sized ranges
def partition(range, n)
    ranges = []
    first = range.first
    last = range.last
    length = last - first + 1
    step = length / n # integer division
    ((first + step - 1)..last).step(step) { |i|
        ranges << (first..i)
        first = i + 1
    }
    # append any extra onto the last element
    ranges[-1] = (ranges[-1].first)..last if last > step * ranges.length
    ranges
end

# recursively search a range
def search(range)
    if range.last - range.first < BLOCK_SIZE
        # range is small enough to check
        a = range.to_a
        a.shuffle!
        a.each { |i| check(i) }
    else
        # range is too large; subdivide it
        a = partition(range, NUM_PARTS)
        a.shuffle!
        a.each { |r| search(r) }
    end
end

# options
Thread.abort_on_exception = true
NUM_THREADS = 8
PW_LEN = 4

# constants
ALPHABET = ("0".."9").to_a + ("a".."z").to_a
ALPHA_SIZE = ALPHABET.length
BLOCK_SIZE = 2 ** 16
NUM_PARTS = 4
COMPLEXITY = ALPHA_SIZE ** PW_LEN

# variables
pw = Array.new(PW_LEN) { ALPHABET[rand(ALPHA_SIZE)] }.join
$target = hash(pw)
$found = false
puts "target:  #{pw}  =>  #{$target}"
puts "search:  #{COMPLEXITY} keys"

# partition and assign each search space to a thread
threads = []
partition(0..(COMPLEXITY-1), NUM_THREADS).each { |r| threads << Thread.new { search(r) } }

# wait until a match is found, or all threads are dead
sleep(5) until $found || threads.all? { |t| !t.alive? }