[m-rev.] diff: add more operations on 64-bit integers
Julien Fischer
jfischer at opturion.com
Sun Apr 1 15:22:10 AEST 2018
Add more operations on 64-bit integers.
library/int64.m:
library/uint64.m:
Add num_zeros/1, num_ones/1, num_leading_zeros/1, num_trailing_zeros/1
and reverse_bits/1.
configure.ac:
runtime/mercury_conf.h.in:
Add a new configuration macro that is defined if C's long type
is 64-bit.
tests/hard_coded/Mmakefile:
tests/hard_coded/bit_twiddle_uint64.{m,exp}:
tests/hard_coded/bit_twiddle_int64.{m,exp}:
Add tests of the above.
Julien.
diff --git a/configure.ac b/configure.ac
index c23a6b5..1aebdcf 100644
--- a/configure.ac
+++ b/configure.ac
@@ -2146,6 +2146,22 @@ AC_SUBST(MR_INT_IS_32_BIT)
#-----------------------------------------------------------------------------#
+AC_MSG_CHECKING(whether long is 64-bit)
+AC_CACHE_VAL(mercury_cv_long_is_64_bit,
+ MERCURY_TRY_STATIC_ASSERT(
+ [#include <limits.h>],
+ [sizeof(long) * CHAR_BIT == 64],
+ [mercury_cv_long_is_64_bit=yes],
+ [mercury_cv_long_is_64_bit=no])
+)
+AC_MSG_RESULT($mercury_cv_long_is_64_bit)
+if test "$mercury_cv_long_is_64_bit" = yes; then
+ AC_DEFINE(MR_LONG_IS_64_BIT)
+fi
+AC_SUBST(MR_LONG_IS_64_BIT)
+
+#-----------------------------------------------------------------------------#
+
AC_MSG_CHECKING(whether we can use unboxed floats)
AC_CACHE_VAL(mercury_cv_unboxed_floats,
MERCURY_TRY_STATIC_ASSERT(
diff --git a/library/int64.m b/library/int64.m
index fd0f46c..042afbd 100644
--- a/library/int64.m
+++ b/library/int64.m
@@ -221,12 +221,46 @@
%
:- func \ (int64::in) = (int64::uo) is det.
+%---------------------------------------------------------------------------%
+
+ % num_zeros(I) = N:
+ % N is the number of zeros in the binary representation of I.
+ %
+:- func num_zeros(int64) = int.
+
+ % num_ones(I) = N:
+ % N is the number of ones in the binary representation of I.
+ %
+:- func num_ones(int64) = int.
+
+ % num_leading_zeros(I) = N:
+ % N is the number of leading zeros in the binary representation of I,
+ % starting at the most significant bit position.
+ % Note that num_leading_zeros(0i64) = 64.
+ %
+:- func num_leading_zeros(int64) = int.
+
+ % num_trailing_zeros(I) = N:
+ % N is the number of trailing zeros in the binary representation of I,
+ % starting at the least significant bit position.
+ % Note that num_trailing_zeros(0i64) = 64.
+ %
+:- func num_trailing_zeros(int64) = 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(int64) = int64.
+ % reverse_bits(A) = B:
+ % B is the is value that results from reversing the bits in the binary
+ % representation of A.
+ %
+:- func reverse_bits(int64) = int64.
+
+%---------------------------------------------------------------------------%
+
:- func min_int64 = int64.
:- func max_int64 = int64.
@@ -241,10 +275,12 @@
:- implementation.
:- import_module exception.
+:- import_module int.
:- import_module math.
:- import_module require.
:- import_module string.
:- import_module uint.
+:- import_module uint64.
%---------------------------------------------------------------------------%
@@ -492,6 +528,52 @@ odd(X) :-
%---------------------------------------------------------------------------%
+num_zeros(U) = 64 - num_ones(U).
+
+num_ones(I64) = N :-
+ U64 = uint64.cast_from_int64(I64),
+ N = uint64.num_ones(U64).
+
+:- pragma foreign_proc("Java",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.bitCount(U);
+").
+
+%---------------------------------------------------------------------------%
+
+num_leading_zeros(I64) = N :-
+ U64 = uint64.cast_from_int64(I64),
+ N = uint64.num_leading_zeros(U64).
+
+:- pragma foreign_proc("Java",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.numberOfLeadingZeros(U);
+").
+
+%---------------------------------------------------------------------------%
+
+num_trailing_zeros(I64) = N :-
+ U64 = uint64.cast_from_int64(I64),
+ N = uint64.num_trailing_zeros(U64).
+
+:- pragma foreign_proc("Java",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.numberOfTrailingZeros(U);
+").
+
+%---------------------------------------------------------------------------%
+
+reverse_bytes(I64) = Result :-
+ U64 = uint64.cast_from_int64(I64),
+ Result0 = uint64.reverse_bytes(U64),
+ Result = int64.cast_from_uint64(Result0).
+
:- pragma foreign_proc("C",
reverse_bytes(A::in) = (B::out),
[will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
@@ -499,33 +581,27 @@ odd(X) :-
B = (int64_t) MR_uint64_reverse_bytes((uint64_t)A);
").
-:- pragma foreign_proc("C#",
+:- pragma foreign_proc("Java",
reverse_bytes(A::in) = (B::out),
[will_not_call_mercury, promise_pure, thread_safe],
"
- ulong u_A = (ulong) A;
-
- B = (long) ((u_A & 0x00000000000000ffUL) << 56 |
- (u_A & 0x000000000000ff00UL) << 40 |
- (u_A & 0x0000000000ff0000UL) << 24 |
- (u_A & 0x00000000ff000000UL) << 8 |
- (u_A & 0x000000ff00000000UL) >> 8 |
- (u_A & 0x0000ff0000000000UL) >> 24 |
- (u_A & 0x00ff000000000000UL) >> 40 |
- (u_A & 0xff00000000000000UL) >> 56);
+ B = java.lang.Long.reverseBytes(A);
").
+%---------------------------------------------------------------------------%
+
+reverse_bits(I64) = Result :-
+ U64 = uint64.cast_from_int64(I64),
+ Result0 = uint64.reverse_bits(U64),
+ Result = int64.cast_from_uint64(Result0).
+
:- pragma foreign_proc("Java",
- reverse_bytes(A::in) = (B::out),
+ reverse_bits(A::in) = (B::out),
[will_not_call_mercury, promise_pure, thread_safe],
"
- B = java.lang.Long.reverseBytes(A);
+ B = java.lang.Long.reverse(A);
").
-:- pragma no_determinism_warning(reverse_bytes/1).
-reverse_bytes(_) = _ :-
- sorry($module, "int64.reverse_bytes/1 NYI for Erlang").
-
%---------------------------------------------------------------------------%
min_int64 = -9_223_372_036_854_775_808_i64.
diff --git a/library/uint64.m b/library/uint64.m
index 134da80..6846a60 100644
--- a/library/uint64.m
+++ b/library/uint64.m
@@ -193,12 +193,34 @@
%
:- func \ (uint64::in) = (uint64::uo) is det.
+ % num_zeros(U) = N:
+ % N is the number of zeros in the binary representation of U.
+ %
+:- func num_zeros(uint64) = int.
+
+ % num_ones(U) = N:
+ % N is the number of ones in the binary representation of U.
+ %
+:- func num_ones(uint64) = int.
+
+ % num_leading_zeros(U) = N:
+ % N is the number of leading zeros in the binary representation of U.
+ %
+:- func num_leading_zeros(uint64) = int.
+
+ % num_trailing_zeros(U) = N:
+ % N is the number of trailing zeros in the binary representation of U.
+ %
+:- func num_trailing_zeros(uint64) = 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(uint64) = uint64.
+:- func reverse_bits(uint64) = uint64.
+
:- func max_uint64 = uint64.
% Convert a uint64 to a pretty_printer.doc for formatting.
@@ -211,6 +233,7 @@
:- implementation.
:- import_module exception.
+:- import_module int.
:- import_module math.
:- import_module require.
:- import_module string.
@@ -474,6 +497,152 @@ odd(X) :-
%---------------------------------------------------------------------------%
+% The algorithms in this section are from chapter 5 of ``Hacker's Delight''
+% by Henry S. Warren, Jr.
+% (Java uses the same.)
+
+num_zeros(U) = 64 - 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)) && defined(MR_LONG_IS_64_BIT)
+ N = __builtin_popcountl(U);
+#else
+ U = U - ((U >> 1) & UINT64_C(0x5555555555555555));
+ U = (U & UINT64_C(0x3333333333333333)) + ((U >> 2) & UINT64_C(0x3333333333333333));
+ U = (U + (U >> 4)) & UINT64_C(0x0f0f0f0f0f0f0f0f);
+ U = U + (U >> 8);
+ U = U + (U >> 16);
+ U = U + (U >> 32);
+ N = U & UINT64_C(0x7f);
+#endif
+").
+
+:- pragma foreign_proc("C#",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ U = U - ((U >> 1) & 0x5555555555555555UL);
+ U = (U & 0x3333333333333333UL) + ((U >> 2) & 0x3333333333333333UL);
+ U = (U + (U >> 4)) & 0x0f0f0f0f0f0f0f0fUL;
+ U = U + (U >> 8);
+ U = U + (U >> 16);
+ U = U + (U >> 32);
+ N = (int) (U & 0x7fUL);
+").
+
+:- pragma foreign_proc("Java",
+ num_ones(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.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 = 64;
+ } else {
+ int32_t n = 1;
+ uint32_t x = (uint32_t)(U >> 32);
+ if (x == 0) { n += 32; x = (uint32_t)U; }
+ if (x >> 16 == 0) { n += 16; x <<= 16; }
+ if (x >> 24 == 0) { n += 8; x <<= 8; }
+ if (x >> 28 == 0) { n += 4; x <<= 4; }
+ if (x >> 30 == 0) { n += 2; x <<= 2; }
+ N = n - (x >> 31);
+ }
+").
+
+:- pragma foreign_proc("C#",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ if (U == 0) {
+ N = 64;
+ } else {
+ int n = 1;
+ uint x = (uint)(U >> 32);
+ if (x == 0) { n += 32; x = (uint)U; }
+ if (x >> 16 == 0) { n += 16; x <<= 16; }
+ if (x >> 24 == 0) { n += 8; x <<= 8; }
+ if (x >> 28 == 0) { n += 4; x <<= 4; }
+ if (x >> 30 == 0) { n += 2; x <<= 2; }
+ N = n - (int)(x >> 31);
+ }
+").
+
+:- pragma foreign_proc("Java",
+ num_leading_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.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 = 64;
+ } else {
+ uint32_t x, y;
+ int n = 63;
+ y = (int32_t) U;
+ if (y != 0) {
+ n -= 32; x = y;
+ } else {
+ x = (uint32_t)(U >> 32);
+ }
+ y = x << 16; if (y != 0) { n -= 16; x = y; }
+ y = x << 8; if (y != 0) { n -= 8; x = y; }
+ y = x << 4; if (y != 0) { n -= 4; x = y; }
+ y = x << 2; if (y != 0) { n -= 2; x = y; }
+ N = n - (int)((x << 1) >> 31);
+ }
+").
+
+:- pragma foreign_proc("C#",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ if (U == 0) {
+ N = 64;
+ } else {
+
+ uint x, y;
+ int n = 63;
+ y = (uint) U;
+ if (y != 0) {
+ n = n - 32; x = y;
+ } else {
+ x = (uint)(U >> 32);
+ }
+ y = x << 16; if (y != 0) { n = n -16; x = y; }
+ y = x << 8; if (y != 0) { n = n - 8; x = y; }
+ y = x << 4; if (y != 0) { n = n - 4; x = y; }
+ y = x << 2; if (y != 0) { n = n - 2; x = y; }
+ N = n - (int)((x << 1) >> 31);
+ }
+").
+
+:- pragma foreign_proc("Java",
+ num_trailing_zeros(U::in) = (N::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ N = java.lang.Long.numberOfTrailingZeros(U);
+").
+
+%---------------------------------------------------------------------------%
+
:- pragma foreign_proc("C",
reverse_bytes(A::in) = (B::out),
[will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
@@ -500,6 +669,28 @@ reverse_bytes(A) = B :-
%---------------------------------------------------------------------------%
+reverse_bits(!.A) = B :-
+ !:A = ((!.A /\ 0x_5555_5555_5555_5555_u64) << 1) \/
+ ((!.A >> 1) /\ 0x_5555_5555_5555_5555_u64),
+ !:A = ((!.A /\ 0x_3333_3333_3333_3333_u64) << 2) \/
+ ((!.A >> 2) /\ 0x_3333_3333_3333_3333_u64),
+ !:A = ((!.A /\ 0x_0f0f_0f0f_0f0f_0f0f_u64) << 4) \/
+ ((!.A >> 4) /\ 0x_0f0f_0f0f_0f0f_0f0f_u64),
+ !:A = ((!.A /\ 0x_00ff_00ff_00ff_00ff_u64) << 8) \/
+ ((!.A >> 8) /\ 0x_00ff_00ff_00ff_00ff_u64),
+ !:A = (!.A << 48) \/ ((!.A /\ 0x_ffff_0000_u64) << 16) \/
+ ((!.A >> 16) /\ 0x_ffff_0000_u64) \/ (!.A >> 48),
+ B = !.A.
+
+:- pragma foreign_proc("Java",
+ reverse_bits(A::in) = (B::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ B = java.lang.Long.reverse(A);
+").
+
+%---------------------------------------------------------------------------%
+
max_uint64 = 18_446_744_073_709_551_615_u64.
%---------------------------------------------------------------------------%
diff --git a/runtime/mercury_conf.h.in b/runtime/mercury_conf.h.in
index 864094c..c9e830a 100644
--- a/runtime/mercury_conf.h.in
+++ b/runtime/mercury_conf.h.in
@@ -438,6 +438,10 @@
//
#undef MR_INT_IS_32_BIT
+// MR_LONG_IS_64_BIT is defined if C's long type is exactly 64-bits.
+//
+#undef MR_LONG_IS_64_BIT
+
// The bytecode files represent floats in 64-bit IEEE format.
//
// MR_FLOAT_IS_64_BITS: defined iff the C type `float' is exactly 64 bits.
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index cc4d1bd..e21c478 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -25,8 +25,10 @@ ORDINARY_PROGS = \
binary_stdout \
bit_twiddle_int16 \
bit_twiddle_int32 \
+ bit_twiddle_int64 \
bit_twiddle_uint16 \
bit_twiddle_uint32 \
+ bit_twiddle_uint64 \
boyer \
brace \
bug103 \
diff --git a/tests/hard_coded/bit_twiddle_int64.exp b/tests/hard_coded/bit_twiddle_int64.exp
index e69de29..02da1fc 100644
--- a/tests/hard_coded/bit_twiddle_int64.exp
+++ b/tests/hard_coded/bit_twiddle_int64.exp
@@ -0,0 +1,101 @@
+*** Test function 'num_zeros' ***
+
+num_zeros(1000000000000000000000000000000000000000000000000000000000000000) = 63
+num_zeros(1111111111111111111111111111111110000000000000000000000000000000) = 31
+num_zeros(1111111111111111111111111111111111111111111111111000000000000000) = 15
+num_zeros(1111111111111111111111111111111111111111111111111111111110000000) = 7
+num_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 62
+num_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000001111111) = 57
+num_zeros(0000000000000000000000000000000000000000000000000111111111111111) = 49
+num_zeros(0000000000000000000000000000000001111111111111111111111111111111) = 33
+num_zeros(0111111111111111111111111111111111111111111111111111111111111111) = 1
+
+*** Test function 'num_ones' ***
+
+num_ones(1000000000000000000000000000000000000000000000000000000000000000) = 1
+num_ones(1111111111111111111111111111111110000000000000000000000000000000) = 33
+num_ones(1111111111111111111111111111111111111111111111111000000000000000) = 49
+num_ones(1111111111111111111111111111111111111111111111111111111110000000) = 57
+num_ones(0000000000000000000000000000000000000000000000000000000000000000) = 0
+num_ones(0000000000000000000000000000000000000000000000000000000000000001) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000000010) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000001000) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000001010) = 2
+num_ones(0000000000000000000000000000000000000000000000000000000000010000) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000001111111) = 7
+num_ones(0000000000000000000000000000000000000000000000000111111111111111) = 15
+num_ones(0000000000000000000000000000000001111111111111111111111111111111) = 31
+num_ones(0111111111111111111111111111111111111111111111111111111111111111) = 63
+
+*** Test function 'num_leading_zeros' ***
+
+num_leading_zeros(1000000000000000000000000000000000000000000000000000000000000000) = 0
+num_leading_zeros(1111111111111111111111111111111110000000000000000000000000000000) = 0
+num_leading_zeros(1111111111111111111111111111111111111111111111111000000000000000) = 0
+num_leading_zeros(1111111111111111111111111111111111111111111111111111111110000000) = 0
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 63
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 62
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 60
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 60
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 59
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000001111111) = 57
+num_leading_zeros(0000000000000000000000000000000000000000000000000111111111111111) = 49
+num_leading_zeros(0000000000000000000000000000000001111111111111111111111111111111) = 33
+num_leading_zeros(0111111111111111111111111111111111111111111111111111111111111111) = 1
+
+*** Test function 'num_trailing_zeros' ***
+
+num_trailing_zeros(1000000000000000000000000000000000000000000000000000000000000000) = 63
+num_trailing_zeros(1111111111111111111111111111111110000000000000000000000000000000) = 31
+num_trailing_zeros(1111111111111111111111111111111111111111111111111000000000000000) = 15
+num_trailing_zeros(1111111111111111111111111111111111111111111111111111111110000000) = 7
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 0
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 1
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 3
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 1
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 4
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000001111111) = 0
+num_trailing_zeros(0000000000000000000000000000000000000000000000000111111111111111) = 0
+num_trailing_zeros(0000000000000000000000000000000001111111111111111111111111111111) = 0
+num_trailing_zeros(0111111111111111111111111111111111111111111111111111111111111111) = 0
+
+*** Test function 'reverse_bits' ***
+
+reverse_bits(1000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000000000001
+reverse_bits(1111111111111111111111111111111110000000000000000000000000000000) = 0000000000000000000000000000000111111111111111111111111111111111
+reverse_bits(1111111111111111111111111111111111111111111111111000000000000000) = 0000000000000001111111111111111111111111111111111111111111111111
+reverse_bits(1111111111111111111111111111111111111111111111111111111110000000) = 0000000111111111111111111111111111111111111111111111111111111111
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000001) = 1000000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000010) = 0100000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000001000) = 0001000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000001010) = 0101000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000010000) = 0000100000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000001111111) = 1111111000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000111111111111111) = 1111111111111110000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000001111111111111111111111111111111) = 1111111111111111111111111111111000000000000000000000000000000000
+reverse_bits(0111111111111111111111111111111111111111111111111111111111111111) = 1111111111111111111111111111111111111111111111111111111111111110
+
+*** Test function 'reverse_bytes' ***
+
+reverse_bytes(1000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000010000000
+reverse_bytes(1111111111111111111111111111111110000000000000000000000000000000) = 0000000000000000000000001000000011111111111111111111111111111111
+reverse_bytes(1111111111111111111111111111111111111111111111111000000000000000) = 0000000010000000111111111111111111111111111111111111111111111111
+reverse_bytes(1111111111111111111111111111111111111111111111111111111110000000) = 1000000011111111111111111111111111111111111111111111111111111111
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000001) = 0000000100000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000010) = 0000001000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000001000) = 0000100000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000001010) = 0000101000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000010000) = 0001000000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000001111111) = 0111111100000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000111111111111111) = 1111111101111111000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000001111111111111111111111111111111) = 1111111111111111111111110111111100000000000000000000000000000000
+reverse_bytes(0111111111111111111111111111111111111111111111111111111111111111) = 1111111111111111111111111111111111111111111111111111111101111111
diff --git a/tests/hard_coded/bit_twiddle_int64.m b/tests/hard_coded/bit_twiddle_int64.m
index e69de29..dc44c2f 100644
--- a/tests/hard_coded/bit_twiddle_int64.m
+++ b/tests/hard_coded/bit_twiddle_int64.m
@@ -0,0 +1,136 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+
+% Test bit twiddling operations for signed 64-bit integers.
+
+:- module bit_twiddle_int64.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module int64.
+
+:- import_module list.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ run_twiddle_test(int64.num_zeros, "num_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(int64.num_ones, "num_ones", !IO),
+ io.nl(!IO),
+ run_twiddle_test(int64.num_leading_zeros, "num_leading_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(int64.num_trailing_zeros, "num_trailing_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(int64.reverse_bits, "reverse_bits", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(int64.reverse_bytes, "reverse_bytes", !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred run_twiddle_test((func(int64) = 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(int64) = int)::in, string::in,
+ int64::in, io::di, io::uo) is det.
+
+run_twiddle_test_2(Func, Desc, A, !IO) :-
+ Result = Func(A),
+ int_to_string(Result, ResultStr),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+% Test int64 -> int64 functions.
+
+:- pred run_twiddle_test_b((func(int64) = int64)::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(int64) = int64)::in, string::in,
+ int64::in, io::di, io::uo) is det.
+
+run_twiddle_test_b_2(Func, Desc, A, !IO) :-
+ Result = Func(A),
+ ResultStr = to_binary_string_lz(Result),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- func numbers = list(int64).
+
+numbers = [
+ -9_223_372_036_854_775_808_i64,
+ -2_147_483_648_i64,
+ -32_768_i64,
+ -128_i64,
+ 0_i64,
+ 1_i64,
+ 2_i64,
+ 8_i64,
+ 10_i64,
+ 16_i64,
+ 127_i64,
+ 32_767_i64,
+ 2_147_483_647_i64,
+ 9_223_372_036_854_775_807_i64
+].
+
+%---------------------------------------------------------------------------%
+
+:- func to_binary_string_lz(int64::in) = (string::uo) is det.
+
+:- pragma foreign_proc("C",
+ to_binary_string_lz(I::in) = (S::uo),
+ [will_not_call_mercury, promise_pure, thread_safe, will_not_modify_trail],
+"
+ int i = 64;
+ uint64_t U = 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(I::in) = (S::uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ S = System.Convert.ToString(I, 2).PadLeft(64, '0');
+").
+
+:- pragma foreign_proc("Java",
+ to_binary_string_lz(I::in) = (S::uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ S = java.lang.String.format(""%64s"",
+ java.lang.Long.toBinaryString(I)).replace(' ', '0');
+").
+
+%---------------------------------------------------------------------------%
+:- end_module bit_twiddle_int64.
+%---------------------------------------------------------------------------%
diff --git a/tests/hard_coded/bit_twiddle_uint64.exp b/tests/hard_coded/bit_twiddle_uint64.exp
index e69de29..3ba07d9 100644
--- a/tests/hard_coded/bit_twiddle_uint64.exp
+++ b/tests/hard_coded/bit_twiddle_uint64.exp
@@ -0,0 +1,77 @@
+*** Test function 'num_zeros' ***
+
+num_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 62
+num_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 63
+num_zeros(0000000000000000000000000000000000000000000000000000000011111111) = 56
+num_zeros(0000000000000000000000000000000000000000000000001111111111111111) = 48
+num_zeros(0000000000000000000000000000000011111111111111111111111111111111) = 32
+num_zeros(1111111111111111111111111111111111111111111111111111111111111111) = 0
+
+*** Test function 'num_ones' ***
+
+num_ones(0000000000000000000000000000000000000000000000000000000000000000) = 0
+num_ones(0000000000000000000000000000000000000000000000000000000000000001) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000000010) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000001000) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000000001010) = 2
+num_ones(0000000000000000000000000000000000000000000000000000000000010000) = 1
+num_ones(0000000000000000000000000000000000000000000000000000000011111111) = 8
+num_ones(0000000000000000000000000000000000000000000000001111111111111111) = 16
+num_ones(0000000000000000000000000000000011111111111111111111111111111111) = 32
+num_ones(1111111111111111111111111111111111111111111111111111111111111111) = 64
+
+*** Test function 'num_leading_zeros' ***
+
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 63
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 62
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 60
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 60
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 59
+num_leading_zeros(0000000000000000000000000000000000000000000000000000000011111111) = 56
+num_leading_zeros(0000000000000000000000000000000000000000000000001111111111111111) = 48
+num_leading_zeros(0000000000000000000000000000000011111111111111111111111111111111) = 32
+num_leading_zeros(1111111111111111111111111111111111111111111111111111111111111111) = 0
+
+*** Test function 'num_trailing_zeros' ***
+
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000000) = 64
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000001) = 0
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000000010) = 1
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000001000) = 3
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000001010) = 1
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000000010000) = 4
+num_trailing_zeros(0000000000000000000000000000000000000000000000000000000011111111) = 0
+num_trailing_zeros(0000000000000000000000000000000000000000000000001111111111111111) = 0
+num_trailing_zeros(0000000000000000000000000000000011111111111111111111111111111111) = 0
+num_trailing_zeros(1111111111111111111111111111111111111111111111111111111111111111) = 0
+
+*** Test function 'reverse_bits' ***
+
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000001) = 1000000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000000010) = 0100000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000001000) = 0001000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000001010) = 0101000000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000000010000) = 0000100000000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000000000000011111111) = 1111111100000000000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000000000000000000001111111111111111) = 1111111111111111000000000000000000000000000000000000000000000000
+reverse_bits(0000000000000000000000000000000011111111111111111111111111111111) = 1111111111111111111111111111111100000000000000000000000000000000
+reverse_bits(1111111111111111111111111111111111111111111111111111111111111111) = 1111111111111111111111111111111111111111111111111111111111111111
+
+*** Test function 'reverse_bytes' ***
+
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000000) = 0000000000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000001) = 0000000100000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000000010) = 0000001000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000001000) = 0000100000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000001010) = 0000101000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000000010000) = 0001000000000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000000000000011111111) = 1111111100000000000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000000000000000000001111111111111111) = 1111111111111111000000000000000000000000000000000000000000000000
+reverse_bytes(0000000000000000000000000000000011111111111111111111111111111111) = 1111111111111111111111111111111100000000000000000000000000000000
+reverse_bytes(1111111111111111111111111111111111111111111111111111111111111111) = 1111111111111111111111111111111111111111111111111111111111111111
diff --git a/tests/hard_coded/bit_twiddle_uint64.m b/tests/hard_coded/bit_twiddle_uint64.m
index e69de29..a3a1107 100644
--- a/tests/hard_coded/bit_twiddle_uint64.m
+++ b/tests/hard_coded/bit_twiddle_uint64.m
@@ -0,0 +1,131 @@
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%---------------------------------------------------------------------------%
+
+% Test bit twiddling operations for unsigned 64-bit integers.
+
+:- module bit_twiddle_uint64.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module uint64.
+
+:- import_module list.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+ run_twiddle_test(uint64.num_zeros, "num_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint64.num_ones, "num_ones", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint64.num_leading_zeros, "num_leading_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test(uint64.num_trailing_zeros, "num_trailing_zeros", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(uint64.reverse_bits, "reverse_bits", !IO),
+ io.nl(!IO),
+ run_twiddle_test_b(uint64.reverse_bytes, "reverse_bytes", !IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred run_twiddle_test((func(uint64) = 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(uint64) = int)::in, string::in,
+ uint64::in, io::di, io::uo) is det.
+
+run_twiddle_test_2(Func, Desc, A, !IO) :-
+ Result = Func(A),
+ int_to_string(Result, ResultStr),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+% Test uint64 -> uint64 functions.
+
+:- pred run_twiddle_test_b((func(uint64) = uint64)::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(uint64) = uint64)::in, string::in,
+ uint64::in, io::di, io::uo) is det.
+
+run_twiddle_test_b_2(Func, Desc, A, !IO) :-
+ Result = Func(A),
+ ResultStr = to_binary_string_lz(Result),
+ io.format("%s(%s) = %s\n",
+ [s(Desc), s(to_binary_string_lz(A)), s(ResultStr)], !IO).
+
+%---------------------------------------------------------------------------%
+
+:- func numbers = list(uint64).
+
+numbers = [
+ 0_u64,
+ 1_u64,
+ 2_u64,
+ 8_u64,
+ 10_u64,
+ 16_u64,
+ 255_u64,
+ 65_535_u64,
+ 4_294_967_295_u64,
+ 18_446_744_073_709_551_615_u64
+].
+
+%---------------------------------------------------------------------------%
+
+:- 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 = 64;
+
+ 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 bit_twiddle_uint64.
+%---------------------------------------------------------------------------%
More information about the reviews
mailing list