B-trees & serialization with bencode

2 files changed, 44 insertions, 0 deletions

diff --git a/lib/concepts/Hash.ml b/lib/concepts/Hash.ml
index f467ee7..aac7428 100644
--- a/lib/concepts/Hash.ml
+++ b/lib/concepts/Hash.ml
@@ -2,8 +2,31 @@
 
 type hash = Digestif.SHA256.t
 
+let size = 256/8
+
+let compare h1 h2 = Digestif.SHA256.unsafe_compare h1 h2
+                    |> Ordering.of_int
+
 let hash_of_value (v : Value.value) =
   Representation.(blob_of_value v |> bytes_of_blob) |> Digestif.SHA256.digest_bytes
 
+let hash_of_bytes bytes = Digestif.SHA256.digest_bytes bytes
+
+let hash_of_blob blob = Representation.bytes_of_blob blob |> Digestif.SHA256.digest_bytes
+
+let to_raw_string hash = Digestif.SHA256.to_raw_string hash
+
+let of_raw_string str = Digestif.SHA256.of_raw_string str
+
 let hash_equals = Digestif.SHA256.equal
 let bytes_of_hash (h : hash) = Bytes.of_string (Digestif.SHA256.to_raw_string h)
+
+let power_of_two p =
+  let b = Bytes.make 32 '\x00' in
+  let byte = 31 - (p / 8) in
+  Bytes.set b byte (Char.chr (1 lsl (p mod 8)));
+  Bytes.unsafe_to_string b
+
+let pick n hash =
+  let threshold = Digestif.SHA256.of_raw_string (power_of_two (256 - n)) in
+  compare hash threshold = Ordering.Smaller
diff --git a/lib/concepts/Hash.mli b/lib/concepts/Hash.mli
index b100cd7..44fb3d0 100644
--- a/lib/concepts/Hash.mli
+++ b/lib/concepts/Hash.mli
@@ -1,11 +1,32 @@
 (** an abstract value representing a hash *)
 type hash
 
+(** the size of a hash, in bytes *)
+val size : int
+
 (** given a value, compute it's hash *)
 val hash_of_value : Value.value -> hash
 
+(** given a bag of bytes, compute it's hash *)
+val hash_of_bytes : bytes -> hash
+
+(** given a blob, compute it's hash *)
+val hash_of_blob : Representation.blob -> hash
+
+(** given a hash, return a representation of it as a string (/not/ the usual hex representation!) *)
+val to_raw_string : hash -> string
+
+(** given a string containing a representation of a hash (as per `to_raw_string`), return the corresponding hash *)
+val of_raw_string : string -> hash
+
+(** compare two hashes lexicographically *)
+val compare : hash -> hash -> Ordering.ordering
+
 (** given two hashes, are they the same? *)
 val hash_equals : hash -> hash -> bool
 
 (** given a hash, return a `bytes` representation of it *)
 val bytes_of_hash : hash -> bytes
+
+(** pick one every 1/2^n hashes *)
+val pick : int -> hash -> bool