task_3_1.ml

open Batteries_uni;;

let get_hash x = let s = Cryptokit.Hash.sha256 () in
                 begin
                   s#add_string x;
                   s#result
                 end;;

let lsb x n =
  let complete_bytes_count = n / 8 in
  let mod_bits = n mod 8 in
  let rev = String.backwards x in
  let last_bytes = Enum.take complete_bytes_count rev in
  let last_byte = Enum.take 1 rev |> Enum.get |> Option.get in
  let last_bits = (int_of_char last_byte) land (0xff lsr (8-mod_bits)) |> char_of_int in
  if 0 == mod_bits then
    String.of_backwards last_bytes
  else
    (string_of_char last_bits) ^ (String.of_backwards last_bytes);;

let get_random_string l =
  let f c = Random.int 256 |> char_of_int in
  String.init l f;;

let get_collision sz =
  let tbl = (256.0 ** (float_of_int (1 lsl (sz / 16)))) |> int_of_float |> Hashtbl.create  in
  let rec try_next () =
    let s = get_random_string (sz / 4) in
    let h = (lsb (get_hash s) sz) in
    try
      (s, Hashtbl.find tbl h)
    with
      | Not_found -> ((Hashtbl.replace tbl h s); try_next()) in
  try_next ();;

let print_hashed x =
  let print_x x = x |> int_of_char |> (Printf.printf "%x") in
  String.iter print_x x;;

let x,y = get_collision 50 in
begin
  print_hashed x;
  print_char ',';
  print_hashed y;
  print_endline ""
end;;