[m-rev.] for review: add bitwise rotations for uint32s
Julien Fischer
jfischer at opturion.com
Sun Mar 28 02:22:10 AEDT 2021
For review by anyone.
After this diff is reviewed and committed I intend to add these
operations for the other unsigned integer types. I'll update the NEWS
file after that is done.
-----------------------------------
Add bitwise rotations for uint32s.
library/uint32.m:
As above.
tests/hard_coded/Mmakefile:
tests/hard_coded/rotate_uint32.{m,exp}:
Add a test for the new operations.
Julien.
diff --git a/library/uint32.m b/library/uint32.m
index 5824cfb..9c9ca70 100644
--- a/library/uint32.m
+++ b/library/uint32.m
@@ -1,7 +1,7 @@
%---------------------------------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%---------------------------------------------------------------------------%
-% Copyright (C) 2017-2018 The Mercury team.
+% Copyright (C) 2017-2021 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%---------------------------------------------------------------------------%
%
@@ -342,6 +342,34 @@
%
:- func reverse_bits(uint32) = uint32.
+ % 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, 31].
+ %
+:- func rotate_left(uint32, uint) = uint32.
+
+ % unchecked_rotate_left(U, D) = N:
+ %
+ % N is the value obtained by rotating the binary representation of U
+ % left by the lowest 5 bits of D.
+ %
+:- func unchecked_rotate_left(uint32, uint) = uint32.
+
+ % 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, 31].
+ %
+:- func rotate_right(uint32, uint) = uint32.
+
+ % unchecked_rotate_left(U, D) = N:
+ %
+ % N is the value obtained by rotating the binary representation of U
+ % right by the lowest 5 bits of D.
+ %
+:- func unchecked_rotate_right(uint32, uint) = uint32.
+
%---------------------------------------------------------------------------%
%
% Limits.
@@ -873,6 +901,76 @@ reverse_bytes(A) = B :-
%---------------------------------------------------------------------------%
+rotate_left(X, N) =
+ ( if N < 32u then
+ unchecked_rotate_left(X, N)
+ else
+ func_error($pred, "second argument exceeds 31 bits")
+ ).
+
+:- pragma foreign_proc("C",
+ unchecked_rotate_left(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N &= 31;
+ // This implementation is from https://blog.regehr.org/archives/1063.
+ // It is intended to avoid undefined behaviour in C and be recognisable by
+ // C compilers as a rotate operation. (On architectures that have a rotate
+ // instruction some C compilers can recognise this formulation and replace
+ // it with the appropriate machine instruction.)
+ // XXX clang has intrinsics for rotation -- we should use those instead.
+ Result = (X << N) | (X >> (-N & 31));
+").
+
+:- pragma foreign_proc("C#",
+ unchecked_rotate_left(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N &= 31;
+ Result = (X << (int) N) | (X >> (int) (-N & 31));
+").
+
+:- pragma foreign_proc("Java",
+ unchecked_rotate_left(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Result = java.lang.Integer.rotateLeft(X, N);
+").
+
+%---------------------------------------------------------------------------%
+
+rotate_right(X, N) =
+ ( if N < 32u then
+ unchecked_rotate_right(X, N)
+ else
+ func_error($pred, "second argument exceeds 31 bits")
+ ).
+
+:- pragma foreign_proc("C",
+ unchecked_rotate_right(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N &= 31;
+ Result = (X >> N) | (X << (-N & 31));
+").
+
+:- pragma foreign_proc("C#",
+ unchecked_rotate_right(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N &= 31;
+ Result = (X >> (int) N) | (X << (int) (-N & 31));
+").
+
+:- pragma foreign_proc("Java",
+ unchecked_rotate_right(X::in, N::in) = (Result::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Result = java.lang.Integer.rotateRight(X, N);
+").
+
+%---------------------------------------------------------------------------%
+
max_uint32 = 4_294_967_295_u32.
%---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index b1c58c7..ed5e292 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -328,6 +328,7 @@ ORDINARY_PROGS = \
rev_arith \
reverse_arith \
rnd \
+ rotate_uint32 \
rtree_test \
rtti_strings \
sectag_bits \
diff --git a/tests/hard_coded/rotate_uint32.exp b/tests/hard_coded/rotate_uint32.exp
index e69de29..4ff88df 100644
--- a/tests/hard_coded/rotate_uint32.exp
+++ b/tests/hard_coded/rotate_uint32.exp
@@ -0,0 +1,120 @@
+*** Test 'rotate_left' ***
+
+rotate_left(00000000000000000000000000000001, 0) = 00000000000000000000000000000001
+
+rotate_left(00000000000000000000000000000001, 1) = 00000000000000000000000000000010
+
+rotate_left(00000000000000000000000000000001, 2) = 00000000000000000000000000000100
+
+rotate_left(00000000000000000000000000000001, 31) = 10000000000000000000000000000000
+
+rotate_left(00000000000000000000000000000001, 32) = <<exception>>
+
+rotate_left(00000000000000000000000000000001, 63) = <<exception>>
+
+rotate_left(00000000000000000000000000000001, 64) = <<exception>>
+
+rotate_left(00000000000000000000000011111111, 0) = 00000000000000000000000011111111
+
+rotate_left(00000000000000000000000011111111, 1) = 00000000000000000000000111111110
+
+rotate_left(00000000000000000000000011111111, 2) = 00000000000000000000001111111100
+
+rotate_left(00000000000000000000000011111111, 31) = 10000000000000000000000001111111
+
+rotate_left(00000000000000000000000011111111, 32) = <<exception>>
+
+rotate_left(00000000000000000000000011111111, 63) = <<exception>>
+
+rotate_left(00000000000000000000000011111111, 64) = <<exception>>
+
+*** Test 'unchecked_rotate_left' ***
+
+unchecked_rotate_left(00000000000000000000000000000001, 0) = 00000000000000000000000000000001
+
+unchecked_rotate_left(00000000000000000000000000000001, 1) = 00000000000000000000000000000010
+
+unchecked_rotate_left(00000000000000000000000000000001, 2) = 00000000000000000000000000000100
+
+unchecked_rotate_left(00000000000000000000000000000001, 31) = 10000000000000000000000000000000
+
+unchecked_rotate_left(00000000000000000000000000000001, 32) = 00000000000000000000000000000001
+
+unchecked_rotate_left(00000000000000000000000000000001, 63) = 10000000000000000000000000000000
+
+unchecked_rotate_left(00000000000000000000000000000001, 64) = 00000000000000000000000000000001
+
+unchecked_rotate_left(00000000000000000000000011111111, 0) = 00000000000000000000000011111111
+
+unchecked_rotate_left(00000000000000000000000011111111, 1) = 00000000000000000000000111111110
+
+unchecked_rotate_left(00000000000000000000000011111111, 2) = 00000000000000000000001111111100
+
+unchecked_rotate_left(00000000000000000000000011111111, 31) = 10000000000000000000000001111111
+
+unchecked_rotate_left(00000000000000000000000011111111, 32) = 00000000000000000000000011111111
+
+unchecked_rotate_left(00000000000000000000000011111111, 63) = 10000000000000000000000001111111
+
+unchecked_rotate_left(00000000000000000000000011111111, 64) = 00000000000000000000000011111111
+
+*** Test 'rotate_right' ***
+
+rotate_right(00000000000000000000000000000001, 0) = 00000000000000000000000000000001
+
+rotate_right(00000000000000000000000000000001, 1) = 10000000000000000000000000000000
+
+rotate_right(00000000000000000000000000000001, 2) = 01000000000000000000000000000000
+
+rotate_right(00000000000000000000000000000001, 31) = 00000000000000000000000000000010
+
+rotate_right(00000000000000000000000000000001, 32) = <<exception>>
+
+rotate_right(00000000000000000000000000000001, 63) = <<exception>>
+
+rotate_right(00000000000000000000000000000001, 64) = <<exception>>
+
+rotate_right(00000000000000000000000011111111, 0) = 00000000000000000000000011111111
+
+rotate_right(00000000000000000000000011111111, 1) = 10000000000000000000000001111111
+
+rotate_right(00000000000000000000000011111111, 2) = 11000000000000000000000000111111
+
+rotate_right(00000000000000000000000011111111, 31) = 00000000000000000000000111111110
+
+rotate_right(00000000000000000000000011111111, 32) = <<exception>>
+
+rotate_right(00000000000000000000000011111111, 63) = <<exception>>
+
+rotate_right(00000000000000000000000011111111, 64) = <<exception>>
+
+*** Test 'unchecked_rotate_right' ***
+
+unchecked_rotate_right(00000000000000000000000000000001, 0) = 00000000000000000000000000000001
+
+unchecked_rotate_right(00000000000000000000000000000001, 1) = 10000000000000000000000000000000
+
+unchecked_rotate_right(00000000000000000000000000000001, 2) = 01000000000000000000000000000000
+
+unchecked_rotate_right(00000000000000000000000000000001, 31) = 00000000000000000000000000000010
+
+unchecked_rotate_right(00000000000000000000000000000001, 32) = 00000000000000000000000000000001
+
+unchecked_rotate_right(00000000000000000000000000000001, 63) = 00000000000000000000000000000010
+
+unchecked_rotate_right(00000000000000000000000000000001, 64) = 00000000000000000000000000000001
+
+unchecked_rotate_right(00000000000000000000000011111111, 0) = 00000000000000000000000011111111
+
+unchecked_rotate_right(00000000000000000000000011111111, 1) = 10000000000000000000000001111111
+
+unchecked_rotate_right(00000000000000000000000011111111, 2) = 11000000000000000000000000111111
+
+unchecked_rotate_right(00000000000000000000000011111111, 31) = 00000000000000000000000111111110
+
+unchecked_rotate_right(00000000000000000000000011111111, 32) = 00000000000000000000000011111111
+
+unchecked_rotate_right(00000000000000000000000011111111, 63) = 00000000000000000000000111111110
+
+unchecked_rotate_right(00000000000000000000000011111111, 64) = 00000000000000000000000011111111
+
diff --git a/tests/hard_coded/rotate_uint32.m b/tests/hard_coded/rotate_uint32.m
index e69de29..cec8cdf 100644
--- a/tests/hard_coded/rotate_uint32.m
+++ b/tests/hard_coded/rotate_uint32.m
@@ -0,0 +1,114 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+
+:- module rotate_uint32.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is cc_multi.
+
+:- implementation.
+
+:- import_module exception.
+:- import_module list.
+:- import_module uint32.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ run_test(rotate_left, "rotate_left", !IO),
+ run_test(unchecked_rotate_left, "unchecked_rotate_left", !IO),
+ run_test(rotate_right, "rotate_right", !IO),
+ run_test(unchecked_rotate_right, "unchecked_rotate_right", !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred run_test((func(uint32, uint) = uint32)::in, string::in, io::di, io::uo)
+ is cc_multi.
+
+run_test(Func, Desc, !IO) :-
+ io.format("*** Test '%s' ***\n\n", [s(Desc)], !IO),
+ Ns = numbers,
+ Ds = distances,
+ list.foldl(run_test_2(Func, Desc, Ds), Ns, !IO).
+
+:- pred run_test_2((func(uint32, uint) = uint32)::in, string::in,
+ list(uint)::in, uint32::in, io::di, io::uo) is cc_multi.
+
+run_test_2(Func, Desc, Ds, N, !IO) :-
+ list.foldl(run_test_3(Func, Desc, N), Ds, !IO).
+
+:- pred run_test_3((func(uint32, uint) = uint32)::in, string::in, uint32::in,
+ uint::in, io::di, io::uo) is cc_multi.
+
+run_test_3(Func, Desc, N, D, !IO) :-
+ ( try []
+ Result0 = Func(N, D)
+ then
+ ResultStr = to_binary_string_lz(Result0)
+ catch_any _ ->
+ ResultStr = "<<exception>>"
+ ),
+ io.format("%s(%s, %u) = %s\n",
+ [s(Desc), s(to_binary_string_lz(N)), u(D), s(ResultStr)], !IO),
+ io.nl(!IO).
+
+%---------------------------------------------------------------------------%
+
+:- func numbers = list(uint32).
+
+numbers = [
+ 1_u32,
+ 255_u32
+].
+
+:- func distances = list(uint).
+
+distances = [
+ 0_u,
+ 1_u,
+ 2_u,
+ 31_u,
+ 32_u,
+ 63_u,
+ 64_u
+].
+
+%---------------------------------------------------------------------------%
+
+:- func to_binary_string_lz(uint32::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, 32, MR_ALLOC_ID);
+ S[32] = '\\0';
+ for (i = 31; 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(U, 2).PadLeft(32, '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(""%32s"",
+ java.lang.Integer.toBinaryString(U)).replace(' ', '0');
+").
+
+%---------------------------------------------------------------------------%
+:- end_module rotate_uint32.
+%---------------------------------------------------------------------------%
More information about the reviews
mailing list