[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