[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