[m-rev.] diff: add bitwise rotations for uint64s

Julien Fischer jfischer at opturion.com
Sun Mar 28 19:59:40 AEDT 2021


Add bitwise rotations for uint64s.

library/uint64.m:
     As above.

tests/hard_coded/Mmakefile:
tests/hard_coded/rotate_uint64.{m,exp}:
     Add a test for the new operations.

Julien.

diff --git a/library/uint64.m b/library/uint64.m
index 5c40cbb..d276018 100644
--- a/library/uint64.m
+++ b/library/uint64.m
@@ -1,7 +1,7 @@
  %---------------------------------------------------------------------------%
  % vim: ts=4 sw=4 et ft=mercury
  %---------------------------------------------------------------------------%
-% Copyright (C) 2018 The Mercury team.
+% Copyright (C) 2018-2021 The Mercury team.
  % This file is distributed under the terms specified in COPYING.LIB.
  %---------------------------------------------------------------------------%
  %
@@ -310,6 +310,34 @@
      %
  :- func reverse_bits(uint64) = uint64.

+    % rotate_left(U, D) = N:
+    %
+    % N is the value obtained by rotating the binary representation of U
+    % left by D bits. Throws an exception if D is not in [0, 63].
+    %
+:- func rotate_left(uint64, uint) = uint64.
+
+    % unchecked_rotate_left(U, D) = N:
+    %
+    % N is the value obtained by rotating the binary representation of U
+    % left by an amount given by the lowest 6 bits of D.
+    %
+:- func unchecked_rotate_left(uint64, uint) = uint64.
+
+    % rotate_right(U, D) = N:
+    %
+    % N is the value obtained by rotating the binary representation of U
+    % right by D bits. Throws an exception if D is not in [0, 63].
+    %
+:- func rotate_right(uint64, uint) = uint64.
+
+    % unchecked_rotate_left(U, D) = N:
+    %
+    % N is the value obtained by rotating the binary representation of U
+    % right by an amount given by the lowest 6 bits of D.
+    %
+:- func unchecked_rotate_right(uint64, uint) = uint64.
+
  %---------------------------------------------------------------------------%
  %
  % Limits.
@@ -799,6 +827,71 @@ reverse_bits(!.A) = B :-

  %---------------------------------------------------------------------------%

+rotate_left(X, N) =
+    ( if N < 64u then
+        unchecked_rotate_left(X, N)
+    else
+        func_error($pred, "rotate amount exceeds 63 bits")
+    ).
+
+:- pragma foreign_proc("C",
+    unchecked_rotate_left(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    N &= 63;
+    // XXX clang has intrinsics for rotation -- we should use those instead.
+    Result = (X << N) | (X >> (-N & 63));
+").
+
+:- pragma foreign_proc("C#",
+    unchecked_rotate_left(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    N &= 63;
+    Result = (X << (int) N) | (X >> (int) (-N & 63));
+").
+
+:- pragma foreign_proc("Java",
+    unchecked_rotate_left(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    Result = java.lang.Long.rotateLeft(X, N);
+").
+
+%---------------------------------------------------------------------------%
+
+rotate_right(X, N) =
+    ( if N < 64u then
+        unchecked_rotate_right(X, N)
+    else
+        func_error($pred, "rotate amount exceeds 63 bits")
+    ).
+
+:- pragma foreign_proc("C",
+    unchecked_rotate_right(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    N &= 63;
+    Result = (X >> N) | (X << (-N & 63));
+").
+
+:- pragma foreign_proc("C#",
+    unchecked_rotate_right(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    N &= 63;
+    Result = (X >> (int) N) | (X << (int) (-N & 63));
+").
+
+:- pragma foreign_proc("Java",
+    unchecked_rotate_right(X::in, N::in) = (Result::out),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    Result = java.lang.Long.rotateRight(X, N);
+").
+
+%---------------------------------------------------------------------------%
+
  max_uint64 = 18_446_744_073_709_551_615_u64.

  %---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index ed5e292..11c2a46 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -329,6 +329,7 @@ ORDINARY_PROGS = \
  	reverse_arith \
  	rnd \
  	rotate_uint32 \
+	rotate_uint64 \
  	rtree_test \
  	rtti_strings \
  	sectag_bits \
diff --git a/tests/hard_coded/rotate_uint64.exp b/tests/hard_coded/rotate_uint64.exp
index e69de29..554fae4 100644
--- a/tests/hard_coded/rotate_uint64.exp
+++ b/tests/hard_coded/rotate_uint64.exp
@@ -0,0 +1,88 @@
+*** Test 'rotate_left' ***
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 0) = 0000000000000000000000000000000000000000000000000000000000000001
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 0) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 1) = 0000000000000000000000000000000000000000000000000000000000000010
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 1) = 0000000000000000000000000000000000000000000000000000000000000010
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 2) = 0000000000000000000000000000000000000000000000000000000000000100
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 2) = 0000000000000000000000000000000000000000000000000000000000000100
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 63) = 1000000000000000000000000000000000000000000000000000000000000000
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 63) = 1000000000000000000000000000000000000000000000000000000000000000
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 64) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 64) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 127) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 127) = 1000000000000000000000000000000000000000000000000000000000000000
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 128) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000000000001, 128) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 0) = 0000000000000000000000000000000000000000000000000000000011111111
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 0) = 0000000000000000000000000000000000000000000000000000000011111111
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 1) = 0000000000000000000000000000000000000000000000000000000111111110
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 1) = 0000000000000000000000000000000000000000000000000000000111111110
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 2) = 0000000000000000000000000000000000000000000000000000001111111100
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 2) = 0000000000000000000000000000000000000000000000000000001111111100
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 63) = 1000000000000000000000000000000000000000000000000000000001111111
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 63) = 1000000000000000000000000000000000000000000000000000000001111111
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 64) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 64) = 0000000000000000000000000000000000000000000000000000000011111111
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 127) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 127) = 1000000000000000000000000000000000000000000000000000000001111111
+
+          rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 128) = <<exception>>
+unchecked_rotate_left(0000000000000000000000000000000000000000000000000000000011111111, 128) = 0000000000000000000000000000000000000000000000000000000011111111
+
+*** Test 'rotate_right' ***
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 0) = 0000000000000000000000000000000000000000000000000000000000000001
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 0) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 1) = 1000000000000000000000000000000000000000000000000000000000000000
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 1) = 1000000000000000000000000000000000000000000000000000000000000000
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 2) = 0100000000000000000000000000000000000000000000000000000000000000
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 2) = 0100000000000000000000000000000000000000000000000000000000000000
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 63) = 0000000000000000000000000000000000000000000000000000000000000010
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 63) = 0000000000000000000000000000000000000000000000000000000000000010
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 64) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 64) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 127) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 127) = 0000000000000000000000000000000000000000000000000000000000000010
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 128) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000000000001, 128) = 0000000000000000000000000000000000000000000000000000000000000001
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 0) = 0000000000000000000000000000000000000000000000000000000011111111
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 0) = 0000000000000000000000000000000000000000000000000000000011111111
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 1) = 1000000000000000000000000000000000000000000000000000000001111111
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 1) = 1000000000000000000000000000000000000000000000000000000001111111
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 2) = 1100000000000000000000000000000000000000000000000000000000111111
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 2) = 1100000000000000000000000000000000000000000000000000000000111111
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 63) = 0000000000000000000000000000000000000000000000000000000111111110
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 63) = 0000000000000000000000000000000000000000000000000000000111111110
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 64) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 64) = 0000000000000000000000000000000000000000000000000000000011111111
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 127) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 127) = 0000000000000000000000000000000000000000000000000000000111111110
+
+          rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 128) = <<exception>>
+unchecked_rotate_right(0000000000000000000000000000000000000000000000000000000011111111, 128) = 0000000000000000000000000000000000000000000000000000000011111111
+
diff --git a/tests/hard_coded/rotate_uint64.m b/tests/hard_coded/rotate_uint64.m
index e69de29..bc260e1 100644
--- a/tests/hard_coded/rotate_uint64.m
+++ b/tests/hard_coded/rotate_uint64.m
@@ -0,0 +1,124 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+
+:- module rotate_uint64.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+:- implementation.
+
+:- import_module exception.
+:- import_module list.
+:- import_module uint64.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+    run_test(rotate_left, unchecked_rotate_left, "rotate_left", !IO),
+    run_test(rotate_right,unchecked_rotate_right,  "rotate_right", !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred run_test((func(uint64, uint) = uint64)::in,
+    (func(uint64, uint) = uint64)::in,
+    string::in, io::di, io::uo) is cc_multi.
+
+run_test(CheckedFunc, UncheckedFunc, Desc, !IO) :-
+    io.format("*** Test '%s' ***\n\n", [s(Desc)], !IO),
+    Ns = numbers,
+    Ds = distances,
+    list.foldl(run_test_2(CheckedFunc, UncheckedFunc, Desc, Ds), Ns, !IO).
+
+:- pred run_test_2((func(uint64, uint) = uint64)::in,
+    (func(uint64, uint) = uint64)::in, string::in,
+    list(uint)::in, uint64::in, io::di, io::uo) is cc_multi.
+
+run_test_2(CheckedFunc, UncheckedFunc, Desc, Ds, N, !IO) :-
+    list.foldl(run_test_3(CheckedFunc, UncheckedFunc, Desc, N), Ds, !IO).
+
+:- pred run_test_3((func(uint64, uint) = uint64)::in,
+    (func(uint64, uint) = uint64)::in, string::in, uint64::in,
+    uint::in, io::di, io::uo) is cc_multi.
+
+run_test_3(CheckedFunc, UncheckedFunc, Desc, N, D, !IO) :-
+    do_eval(CheckedFunc, N, D, CheckedResult),
+    io.format("          %s(%s, %u) = %s\n",
+        [s(Desc), s(to_binary_string_lz(N)), u(D), s(CheckedResult)], !IO),
+    do_eval(UncheckedFunc, N, D, UncheckedResult),
+    io.format("unchecked_%s(%s, %u) = %s\n",
+        [s(Desc), s(to_binary_string_lz(N)), u(D), s(UncheckedResult)], !IO),
+    io.nl(!IO).
+
+:- pred do_eval((func(uint64, uint) = uint64)::in, uint64::in, uint::in,
+    string::out) is cc_multi.
+
+do_eval(Func, N, D, ResultStr) :-
+    ( try []
+        Result0 = Func(N, D)
+    then
+        ResultStr = to_binary_string_lz(Result0)
+    catch_any _ ->
+        ResultStr = "<<exception>>"
+    ).
+
+%---------------------------------------------------------------------------%
+
+:- func numbers = list(uint64).
+
+numbers = [
+    1_u64,
+    255_u64
+].
+
+:- func distances = list(uint).
+
+distances = [
+    0_u,
+    1_u,
+    2_u,
+    63_u,
+    64_u,
+    127_u,
+    128_u
+].
+
+%---------------------------------------------------------------------------%
+
+:- func to_binary_string_lz(uint64::in) = (string::uo) is det.
+
+:- pragma foreign_proc("C",
+    to_binary_string_lz(U::in) = (S::uo),
+    [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+    int i;
+
+    MR_allocate_aligned_string_msg(S, 64, MR_ALLOC_ID);
+    S[64] = '\\0';
+    for (i = 63; i >= 0; i--) {
+        S[i] = (U & 1) ? '1' : '0';
+        U = U >> 1;
+    }
+").
+
+:- pragma foreign_proc("C#",
+    to_binary_string_lz(U::in) = (S::uo),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    S = System.Convert.ToString((long) U, 2).PadLeft(64, '0');
+").
+
+:- pragma foreign_proc("Java",
+    to_binary_string_lz(U::in) = (S::uo),
+    [will_not_call_mercury, promise_pure, thread_safe],
+"
+    S = java.lang.String.format(""%64s"",
+        java.lang.Long.toBinaryString(U)).replace(' ', '0');
+").
+
+%---------------------------------------------------------------------------%
+:- end_module rotate_uint64.
+%---------------------------------------------------------------------------%


More information about the reviews mailing list