# Creates a git repo with 2^N files. N is the only arg. Creates a
# bare repo called "files".

require 'digest/sha1'
require 'zlib'

def filename(id)
  "objects/#{id[0...2]}/#{id[2..-1]}"
end

def read_object(id)
  Zlib::Inflate.inflate(File.read(filename(id)))
end

def write_object(id, bytes)
  `mkdir -p objects/#{id[0...2]}` # boo
  File.open(filename(id),'w') do |f|
    f.write(Zlib::Deflate.deflate(bytes))
  end
end

def hexsha(s); Digest::SHA1.hexdigest(s); end
def hex2bin(s)
  s2 = ""
  while(s.length > 0)
    s3 = s[0...2]
    s2[s2.length]=s3.to_i(16).chr
    s = s[2..-1]
  end
  return s2
end

# keys are filenames, vals are [hash, :dir or :file]
def write_tree(entries)
  s = ""
  entries.each do |filename, (hash, type)|
    s += (type == :dir ? "40000" : "100644")
    s += (" #{filename}\0#{hex2bin(hash)}")
  end
  s = "tree #{s.length}\0#{s}"
  sha = hexsha(s)
  write_object(hexsha(s), s)
  return sha
end

def write_dense_tree(depth, base_entry)
  entry = (depth == 0 ? base_entry : write_dense_tree(depth - 1, base_entry))
  type = (depth == 0 ? :file : :dir)
  suffix = (depth == 0 ? ".txt" : "")

  h = {}
  (0...16).each{|i|h[("%04b#{suffix}" % [i])]=[entry, type]}
  write_tree(h)
end

n = ARGV[0].to_i

`mkdir files`
Dir.chdir 'files'
`git init --bare`

file_blob = "blob 5\0file\n"
file_sha = hexsha(file_blob)
write_object(file_sha, file_blob)

depth = (n >> 2) - 1
tree_sha = write_dense_tree(depth ,file_sha)
commit = `echo 'add files' | git commit-tree #{tree_sha}`
File.write("refs/heads/master", commit)
puts "Done"