[m-rev.] for review: add more operations on 32-bit unsigned integers
Julien Fischer
jfischer at opturion.com
Fri Mar 9 23:37:37 AEDT 2018
For review by anyone.
Note that I have versions of these for all the integer types; after
this change has been reviewed and the names of the operations agreed
on then I will add the others.
Julien.
----------------------
Add more operations 32-bit unsigned integers.
library/uint32.m:
Add num_zeros/1, num_ones/1, num_leading_zeros/1, num_trailing_zeros/1
and reverse_bits/1.
tests/hard_coded/Mmakefile:
tests/hard_coded/bit_twiddle_uint32.{m,exp}:
Add tests of the above operations.
diff --git a/library/uint32.m b/library/uint32.m
index 3adccd2..e855864 100644
--- a/library/uint32.m
+++ b/library/uint32.m
@@ -1,7 +1,7 @@
%---------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%---------------------------------------------------------------------------%
-% Copyright (C) 2017 The Mercury team.
+% Copyright (C) 2017-2018 The Mercury team.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%---------------------------------------------------------------------------%
@@ -191,12 +191,44 @@
%
:- func \ (uint32::in) = (uint32::uo) is det.
+%---------------------------------------------------------------------------%
+
+ % num_zeros(U) = N:
+ % N is the number of zeros in the binary representation of U.
+ %
+:- func num_zeros(uint32) = int.
+
+ % num_ones(U) = N:
+ % N is the number of ones in the binary representation of U.
+ %
+:- func num_ones(uint32) = int.
+
+ % num_leading_zeros(U) = N:
+ % N is the number of leading zeros in the binary representation of U.
+ % Note that num_leading_zeros(0u32) = 32.
+ %
+:- func num_leading_zeros(uint32) = int.
+
+ % num_trailing_zeros(U) = N:
+ % N is the number of trailing zeros in the binary representation of U.
+ % Note that num_trailing_zeros(0u32) = 32.
+ %
+:- func num_trailing_zeros(uint32) = int.
+
% reverse_bytes(A) = B:
- % B is the value that results from reversing the bytes in the
+ % B is the value that results from reversing the bytes in the binary
% representation of A.
%
:- func reverse_bytes(uint32) = uint32.
+ % reverse_bits(A) = B:
+ % B is the is value that results from reversing the bits in the binary
+ % representation of A.
+ %
+:- func reverse_bits(uint32) = uint32.
+
+%---------------------------------------------------------------------------%
+
:- func max_uint32 = uint32.
% Convert a uint32 to a pretty_printer.doc for formatting.
@@ -209,6 +241,7 @@
:- implementation.
:- import_module exception.
+:- import_module int.
:- import_module math.
:- import_module require.
:- import_module string.
@@ -449,6 +482,143 @@ odd(X) :-
%---------------------------------------------------------------------------%
+% The algorithms in this section are adapted from chapter 5 of
+% ``Hacker's Delight'' by Henry S. Warren, Jr.
+
+num_zeros(U) = 32 - num_ones(U).
+
+:- pragma foreign_proc("C",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+#if (defined(MR_GNUC) || defined(MR_CLANG))
+ N = __builtin_popcount(U);
+#else
+ U = U - ((U >> 1) & UINT32_C(0x55555555));
+ U = (U & UINT32_C(0x33333333)) + ((U >> 2) & UINT32_C(0x33333333));
+ U = (U + (U >> 4)) & UINT32_C(0x0f0f0f0f);
+ U = U + (U >> 8);
+ U = U + (U >> 16);
+ N = (MR_Integer) (U & UINT32_C(0x3f));
+#endif
+").
+
+:- pragma foreign_proc("C#",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ U = U - ((U >> 1) & 0x55555555);
+ U = (U & 0x33333333) + ((U >> 2) & 0x33333333);
+ U = (U + (U >> 4)) & 0x0f0f0f0f;
+ U = U + (U >> 8);
+ U = U + (U >> 16);
+ N = (int) (U & 0x3f);
+").
+
+:- pragma foreign_proc("Java",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Integer.bitCount(U);
+").
+
+%---------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+ if (U == 0) {
+ N = 32;
+ } else {
+ #if defined(MR_GNUC) || defined(MR_CLANG)
+ // Note that __builtin_clz(0) is undefined.
+ N = __builtin_clz(U);
+ #else
+ int32_t n = 1;
+ if ((U >> 16) == 0) { n += 16; U <<= 16; }
+ if ((U >> 24) == 0) { n += 8; U <<= 8; }
+ if ((U >> 28) == 0) { n += 4; U <<= 4; }
+ if ((U >> 30) == 0) { n += 2; U <<= 2; }
+ N = n - (U >> 31);
+ #endif
+ }
+").
+
+:- pragma foreign_proc("C#",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ if (U == 0) {
+ N = 32;
+ } else {
+ int n = 1;
+ if ((U >> 16) == 0) { n = n + 16; U = U << 16; }
+ if ((U >> 24) == 0) { n = n + 8; U = U << 8; }
+ if ((U >> 28) == 0) { n = n + 4; U = U << 4; }
+ if ((U >> 30) == 0) { n = n + 2; U = U << 2; }
+ N = n - (int)(U >> 31);
+ }
+").
+
+:- pragma foreign_proc("Java",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Integer.numberOfLeadingZeros(U);
+").
+
+%---------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+ if (U == 0) {
+ N = 32;
+ } else {
+ #if defined(MR_GNUC) || defined(MR_CLANG)
+ N = __builtin_ctz(U);
+ #else
+ int32_t n = 31;
+ uint32_t y;
+ y = U << 16; if (y != 0) { n -= 16; U = y; }
+ y = U << 8; if (y != 0) { n -= 8; U = y; }
+ y = U << 4; if (y != 0) { n -= 4; U = y; }
+ y = U << 2; if (y != 0) { n -= 2; U = y; }
+ y = U << 1; if (y != 0) { n -= 1; }
+ N = n;
+ #endif
+ }
+").
+
+:- pragma foreign_proc("C#",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ if (U == 0) {
+ N = 32;
+ } else {
+ int n = 31;
+ uint y;
+ y = U << 16; if (y != 0) { n = n -16; U = y; }
+ y = U << 8; if (y != 0) { n = n - 8; U = y; }
+ y = U << 4; if (y != 0) { n = n - 4; U = y; }
+ y = U << 2; if (y != 0) { n = n - 2; U = y; }
+ y = U << 1; if (y != 0) { n = n - 1; }
+ N = n;
+ }
+").
+
+:- pragma foreign_proc("Java",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Integer.numberOfTrailingZeros(U);
+").
+
+%---------------------------------------------------------------------------%
+
:- pragma foreign_proc("C",
reverse_bytes(A::in) = (B::out),
[will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
@@ -471,6 +641,38 @@ reverse_bytes(A) = B :-
%---------------------------------------------------------------------------%
+:- pragma foreign_proc("C",
+ reverse_bits(A::in) = (B::out),
+ [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+ A = (A & UINT32_C(0x55555555)) << 1 | (A >> 1) & UINT32_C(0x55555555);
+ A = (A & UINT32_C(0x33333333)) << 2 | (A >> 2) & UINT32_C(0x33333333);
+ A = (A & UINT32_C(0x0f0f0f0f)) << 4 | (A >> 4) & UINT32_C(0x0f0f0f0f);
+ A = (A << 24) | ((A & UINT32_C(0xff00)) << 8) |
+ ((A >> 8) & UINT32_C(0xff00)) | (A >> 24);
+ B = A;
+").
+
+:- pragma foreign_proc("C#",
+ reverse_bits(A::in) = (B::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ A = (A & 0x55555555) << 1 | (A >> 1) & 0x55555555;
+ A = (A & 0x33333333) << 2 | (A >> 2) & 0x33333333;
+ A = (A & 0x0f0f0f0f) << 4 | (A >> 4) & 0x0f0f0f0f;
+ A = (A << 24) | ((A & 0xff00) << 8) | ((A >> 8) & 0xff00) | (A >> 24);
+ B = A;
+").
+
+:- pragma foreign_proc("Java",
+ reverse_bits(A::in) = (B::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ B = java.lang.Integer.reverse(A);
+").
+
+%---------------------------------------------------------------------------%
+
max_uint32 = 4_294_967_295_u32.
%---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index 5881ce1..4ace268 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -23,6 +23,7 @@ ORDINARY_PROGS = \
bigtest \
binary_stdin \
binary_stdout \
+ bit_twiddle_uint32 \
boyer \
brace \
bug103 \
diff --git a/tests/hard_coded/bit_twiddle_uint32.exp b/tests/hard_coded/bit_twiddle_uint32.exp
index e69de29..3b1854c 100644
--- a/tests/hard_coded/bit_twiddle_uint32.exp
+++ b/tests/hard_coded/bit_twiddle_uint32.exp
@@ -0,0 +1,71 @@
+*** Test function 'num_zeros' ***
+
+num_zeros(00000000000000000000000000000000) = 32
+num_zeros(00000000000000000000000000000001) = 31
+num_zeros(00000000000000000000000000000010) = 31
+num_zeros(00000000000000000000000000001000) = 31
+num_zeros(00000000000000000000000000001010) = 30
+num_zeros(00000000000000000000000000010000) = 31
+num_zeros(00000000000000000000000011111111) = 24
+num_zeros(00000000000000001111111111111111) = 16
+num_zeros(11111111111111111111111111111111) = 0
+
+*** Test function 'num_ones' ***
+
+num_ones(00000000000000000000000000000000) = 0
+num_ones(00000000000000000000000000000001) = 1
+num_ones(00000000000000000000000000000010) = 1
+num_ones(00000000000000000000000000001000) = 1
+num_ones(00000000000000000000000000001010) = 2
+num_ones(00000000000000000000000000010000) = 1
+num_ones(00000000000000000000000011111111) = 8
+num_ones(00000000000000001111111111111111) = 16
+num_ones(11111111111111111111111111111111) = 32
+
+*** Test function 'num_leading_zeros' ***
+
+num_leading_zeros(00000000000000000000000000000000) = 32
+num_leading_zeros(00000000000000000000000000000001) = 31
+num_leading_zeros(00000000000000000000000000000010) = 30
+num_leading_zeros(00000000000000000000000000001000) = 28
+num_leading_zeros(00000000000000000000000000001010) = 28
+num_leading_zeros(00000000000000000000000000010000) = 27
+num_leading_zeros(00000000000000000000000011111111) = 24
+num_leading_zeros(00000000000000001111111111111111) = 16
+num_leading_zeros(11111111111111111111111111111111) = 0
+
+*** Test function 'num_trailing_zeros' ***
+
+num_trailing_zeros(00000000000000000000000000000000) = 32
+num_trailing_zeros(00000000000000000000000000000001) = 0
+num_trailing_zeros(00000000000000000000000000000010) = 1
+num_trailing_zeros(00000000000000000000000000001000) = 3
+num_trailing_zeros(00000000000000000000000000001010) = 1
+num_trailing_zeros(00000000000000000000000000010000) = 4
+num_trailing_zeros(00000000000000000000000011111111) = 0
+num_trailing_zeros(00000000000000001111111111111111) = 0
+num_trailing_zeros(11111111111111111111111111111111) = 0
+
+*** Test function 'reverse_bits' ***
+
+reverse_bits(00000000000000000000000000000000) = 00000000000000000000000000000000
+reverse_bits(00000000000000000000000000000001) = 10000000000000000000000000000000
+reverse_bits(00000000000000000000000000000010) = 01000000000000000000000000000000
+reverse_bits(00000000000000000000000000001000) = 00010000000000000000000000000000
+reverse_bits(00000000000000000000000000001010) = 01010000000000000000000000000000
+reverse_bits(00000000000000000000000000010000) = 00001000000000000000000000000000
+reverse_bits(00000000000000000000000011111111) = 11111111000000000000000000000000
+reverse_bits(00000000000000001111111111111111) = 11111111111111110000000000000000
+reverse_bits(11111111111111111111111111111111) = 11111111111111111111111111111111
+
+*** Test function 'reverse_bytes' ***
+
+reverse_bytes(00000000000000000000000000000000) = 00000000000000000000000000000000
+reverse_bytes(00000000000000000000000000000001) = 00000001000000000000000000000000
+reverse_bytes(00000000000000000000000000000010) = 00000010000000000000000000000000
+reverse_bytes(00000000000000000000000000001000) = 00001000000000000000000000000000
+reverse_bytes(00000000000000000000000000001010) = 00001010000000000000000000000000
+reverse_bytes(00000000000000000000000000010000) = 00010000000000000000000000000000
+reverse_bytes(00000000000000000000000011111111) = 11111111000000000000000000000000
+reverse_bytes(00000000000000001111111111111111) = 11111111111111110000000000000000
+reverse_bytes(11111111111111111111111111111111) = 11111111111111111111111111111111
diff --git a/tests/hard_coded/bit_twiddle_uint32.m b/tests/hard_coded/bit_twiddle_uint32.m
index e69de29..056770c 100644
--- a/tests/hard_coded/bit_twiddle_uint32.m
+++ b/tests/hard_coded/bit_twiddle_uint32.m
@@ -0,0 +1,133 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+
+% Test bit twiddling operations for unsigned 32-bit integers.
+
+:- module bit_twiddle_uint32.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module uint32.
+
+:- import_module list.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ run_twiddle_test(uint32.num_zeros, "num_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint32.num_ones, "num_ones", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint32.num_leading_zeros, "num_leading_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint32.num_trailing_zeros, "num_trailing_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(uint32.reverse_bits, "reverse_bits", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(uint32.reverse_bytes, "reverse_bytes", !IO).
+
+%---------------------------------------------------------------------------%
+
+% Test uint32 -> int functions.
+
+:- pred run_twiddle_test((func(uint32) = int)::in, string::in,
+ io::di, io::uo) is det.
+
+run_twiddle_test(Func, Desc, !IO) :-
+ io.format("*** Test function '%s' ***\n\n", [s(Desc)], !IO),
+ As = numbers,
+ list.foldl(run_twiddle_test_2(Func, Desc), As, !IO).
+
+:- pred run_twiddle_test_2((func(uint32) = int)::in, string::in,
+ uint32::in, io::di, io::uo) is det.
+
+run_twiddle_test_2(Func, Desc, A, !IO) :-
+ Result0 = Func(A),
+ int_to_string(Result0, ResultStr),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+% Test uint32 -> uint32 functions.
+
+:- pred run_twiddle_test_b((func(uint32) = uint32)::in, string::in,
+ io::di, io::uo) is det.
+
+run_twiddle_test_b(Func, Desc, !IO) :-
+ io.format("*** Test function '%s' ***\n\n", [s(Desc)], !IO),
+ As = numbers,
+ list.foldl(run_twiddle_test_b_2(Func, Desc), As, !IO).
+
+:- pred run_twiddle_test_b_2((func(uint32) = uint32)::in, string::in,
+ uint32::in, io::di, io::uo) is det.
+
+run_twiddle_test_b_2(Func, Desc, A, !IO) :-
+ Result0 = Func(A),
+ ResultStr = to_binary_string_lz(Result0),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- func numbers = list(uint32).
+
+numbers = [
+ 0_u32,
+ 1_u32,
+ 2_u32,
+ 8_u32,
+ 10_u32,
+ 16_u32,
+ 255_u32,
+ 65_535_u32,
+ 4_294_967_295_u32
+].
+
+%---------------------------------------------------------------------------%
+
+:- 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 = 32;
+
+ MR_allocate_aligned_string_msg(S, 32, MR_ALLOC_ID);
+ S[32] = '\\0';
+ while (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 bit_twiddle_uint32.
+%---------------------------------------------------------------------------%
More information about the reviews
mailing list