Add {Int32,Int64,Nativeint}.unsigned_{compare,div,rem}

1 files changed, 33 insertions, 0 deletions

diff --git a/stdlib/int32.ml b/stdlib/int32.ml
index 9e1eabf5e4..e159851e5a 100644
--- a/stdlib/int32.ml
+++ b/stdlib/int32.ml
@@ -52,6 +52,22 @@ let min_int = 0x80000000l
 let max_int = 0x7FFFFFFFl
 let lognot n = logxor n (-1l)
 
+let unsigned_to_int =
+  match Sys.word_size with
+  | 32 ->
+      let max_int = of_int Stdlib.max_int in
+      fun n ->
+        if compare zero n <= 0 && compare n max_int <= 0 then
+          Some (to_int n)
+        else
+          None
+  | 64 ->
+      (* So that it compiles in 32-bit *)
+      let move = int_of_string "0x1_0000_0000" in
+      fun n -> let i = to_int n in Some (if i < 0 then i + move else i)
+  | _ ->
+      assert false
+
 external format : string -> int32 -> string = "caml_int32_format"
 let to_string n = format "%d" n
 
@@ -66,3 +82,20 @@ type t = int32
 
 let compare (x: t) (y: t) = Stdlib.compare x y
 let equal (x: t) (y: t) = compare x y = 0
+
+let unsigned_compare n m =
+  compare (sub n min_int) (sub m min_int)
+
+(* Unsigned division from signed division of the same
+   bitness. See Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.), Sec 9-3.
+*)
+let unsigned_div n d =
+  if d < zero then
+    if unsigned_compare n d < 0 then zero else one
+  else
+    let q = shift_left (div (shift_right_logical n 1) d) 1 in
+    let r = sub n (mul q d) in
+    if unsigned_compare r d >= 0 then succ q else q
+
+let unsigned_rem n d =
+  sub n (mul (unsigned_div n d) d)