Subject: [Boost-commit] svn:boost r62959 - in sandbox/SOC/2010/bits_and_ints/boost/integer: . detail
From: muriloufg_at_[hidden]
Date: 2010-06-14 20:22:41
Author: murilov
Date: 2010-06-14 20:22:40 EDT (Mon, 14 Jun 2010)
New Revision: 62959
URL: http://svn.boost.org/trac/boost/changeset/62959
Log:
Interleave functions reduced to one generic interleave function.
Added integer/morton.hpp and integer/detail/morton.hpp files wich declares morton types.
Added:
sandbox/SOC/2010/bits_and_ints/boost/integer/detail/morton.hpp (contents, props changed)
sandbox/SOC/2010/bits_and_ints/boost/integer/morton.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/bits_and_ints/boost/integer/interleave.hpp | 203 +++++++++++----------------------------
1 files changed, 56 insertions(+), 147 deletions(-)
Added: sandbox/SOC/2010/bits_and_ints/boost/integer/detail/morton.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/bits_and_ints/boost/integer/detail/morton.hpp 2010-06-14 20:22:40 EDT (Mon, 14 Jun 2010)
@@ -0,0 +1,55 @@
+// Boost integer/detail/morton.hpp header file ------------------------------//
+
+// (C) Copyright Murilo Adriano Vasconcelos 2010.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_DETAIL_MORTON_INCLUDED
+#define BOOST_DETAIL_MORTON_INCLUDED
+
+#include <boost/cstdint.hpp>
+
+/*
+ * Some inner types used by morton type.
+ */
+namespace boost {
+namespace integer_detail {
+
+/*
+ * The parameter size must be equal to 8, 16, 32 or 64.
+ */
+template <std::size_t size>
+struct morton_type
+{};
+
+template <>
+struct morton_type<8>
+{
+ typedef uint8_t type;
+};
+
+template <>
+struct morton_type<16>
+{
+ typedef uint16_t type;
+};
+
+template <>
+struct morton_type<32>
+{
+ typedef uint32_t type;
+};
+
+template <>
+struct morton_type<64>
+{
+ typedef uint64_t type;
+};
+
+} // integer_detail
+} // boost
+
+#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/bits_and_ints/boost/integer/interleave.hpp
==============================================================================
--- sandbox/SOC/2010/bits_and_ints/boost/integer/interleave.hpp (original)
+++ sandbox/SOC/2010/bits_and_ints/boost/integer/interleave.hpp 2010-06-14 20:22:40 EDT (Mon, 14 Jun 2010)
@@ -12,177 +12,86 @@
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_integral.hpp>
-#include <boost/cstdint.hpp>
+#include <boost/integer/morton.hpp>
#include <utility>
-#include <iostream>
-
/*
* Bit interleaving functions.
*
- * Interleave the bits of two integers in one integer.
+ * Interleave the bits of two integers in one morton<> type.
* For example:
- * a = 5; // 0000 0101
- * b = 10; // 0000 1010
- * z = interleave(a, b); // z = 102
+ * uint8_t a = 5; // 0000 0101
+ * uint8_t b = 10; // 0000 1010
+ * morton<16> z = interleave(a, b); // z = 102
*
- * a = 0 0 0 0 0 1 0 1
- * b = 0 0 0 0 1 0 1 0
- * z = 0000000001100110
+ * a = 0 0 0 0 0 1 0 1
+ * b = 0 0 0 0 1 0 1 0
+ * z.value = 0000000001100110
*/
namespace boost
{
-
-/*
- * The morton<Size> types holds an unsigned integer with `Size' bytes.
- * These types are used by interleave functions.
- */
-template <std::size_t Size>
-struct morton
-{
-};
-
-template <>
-struct morton<8>
-{
- typedef morton<8> type;
- typedef uint8_t value_type;
-
- morton() : value(0) {}
- morton(uint8_t val) : value(val) {}
-
- value_type value;
-};
-
-template <>
-struct morton<16>
-{
- typedef morton<16> type;
- typedef uint16_t value_type;
-
- morton() : value(0) {}
- morton(uint16_t val) : value(val) {}
-
- value_type value;
-};
-
-template <>
-struct morton<32> {
- typedef morton<32> type;
- typedef uint32_t value_type;
- morton() : value(0) {}
- morton(uint32_t val) : value(val) {}
-
- value_type value;
-};
-
-template <>
-struct morton<64> {
- typedef morton<64> type;
- typedef uint64_t value_type;
-
- morton() : value(0) {}
- morton(uint64_t val) : value(val) {}
-
- value_type value;
-};
-
/*
- * Interleave two 16-bit integral types and returns the bits interleaved in an
- * morton<32>.
+ * Interleave two integrals of 8, 16 or 32 bits and returns
+ * one morton<S> with S equal to the double of the size of bits of `x' or `y'.
*/
template <typename T>
-inline typename enable_if_c<is_integral<T>::type::value && sizeof(T) == 2, morton<32> >::type
+inline typename enable_if_c<is_integral<T>::type::value
+ && (sizeof(T) == 1 || sizeof(T) == 2 || sizeof(T) == 4) , morton<sizeof(T) * 16> >::type
interleave(T x, T y)
{
- uint32_t a(x), b(y);
+ static const uintmax_t
+ interleave_mask[3][5] = {
+ {0x5555, 0x3333, 0x0F0F, 0xFFFF, 0xFFFF},
+ {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0xFFFFFFFF},
+#ifndef BOOST_NO_INT64_T
+ {0x5555555555555555, 0x3333333333333333, 0x0F0F0F0F0F0F0F0F, 0x00FF00FF00FF00FF, 0x0000FFFF0000FFF }
+#else
+ {0x0, 0x0, 0x0, 0x0, 0x0}
+#endif
+ };
+
+ static const std::size_t
+ interleave_shift[3][5] = {
+ {0, 0, 4, 2, 1},
+ {0, 8, 4, 2, 1},
+ {16, 8, 4, 2, 1}
+ };
+
+ const std::size_t bytes = sizeof(T);
+ typedef typename integer_detail::morton_type<bytes * 16>::type value_type;
+
+ value_type a(x), b(y);
+
+ a = (a | (a << interleave_shift[bytes/2][0])) & value_type(interleave_mask[bytes/2][4]);
// puts the byte 2 in the byte 4 and the byte 3 in the byte 5
- a = (a | (a << 8)) & 0x00FF00FF;
+ a = (a | (a << interleave_shift[bytes/2][1])) & value_type(interleave_mask[bytes/2][3]);
// now the original bytes of x are in alternate bytes
- a = (a | (a << 4)) & 0x0F0F0F0F;
+ a = (a | (a << interleave_shift[bytes/2][2])) & value_type(interleave_mask[bytes/2][2]);
// now the original bits of x are in the lowest 2 bits of the nibbles
- a = (a | (a << 2)) & 0x33333333;
+ a = (a | (a << interleave_shift[bytes/2][3])) & value_type(interleave_mask[bytes/2][1]);
// now the original bits are in the even bits
- a = (a | (a << 1)) & 0x55555555;
+ a = (a | (a << interleave_shift[bytes/2][4])) & value_type(interleave_mask[bytes/2][0]);
// do the same with b
- b = (b | (b << 8)) & 0x00FF00FF;
- b = (b | (b << 4)) & 0x0F0F0F0F;
- b = (b | (b << 2)) & 0x33333333;
- b = (b | (b << 1)) & 0x55555555;
+ b = (b | (b << interleave_shift[bytes/2][0])) & value_type(interleave_mask[bytes/2][4]);
+ b = (b | (b << interleave_shift[bytes/2][1])) & value_type(interleave_mask[bytes/2][3]);
+ b = (b | (b << interleave_shift[bytes/2][2])) & value_type(interleave_mask[bytes/2][2]);
+ b = (b | (b << interleave_shift[bytes/2][3])) & value_type(interleave_mask[bytes/2][1]);
+ b = (b | (b << interleave_shift[bytes/2][4])) & value_type(interleave_mask[bytes/2][0]);
// now the original bits are in the odd bits
b <<= 1;
// the result is the union of a and b bits
return (a | b);
-}
-
-/*
- * Interleave two 8-bit integral types and returns the bits interleaved in an
- * morton<16>.
- */
-template <typename T>
-inline typename enable_if_c<is_integral<T>::type::value && sizeof(T) == 1, morton<16> >::type
-interleave(T x, T y)
-{
- uint16_t a(x), b(y);
- // now the original bytes are in alternate bytes
- a = (a | (a << 4)) & 0x0F0F;
-
- // now the original bits are in the lowest 2 bits of the nibbles
- a = (a | (a << 2)) & 0x3333;
-
- // now the original bits are in the even bits
- a = (a | (a << 1)) & 0x5555;
-
- // do the same with b
- b = (b | (b << 4)) & 0x0F0F;
- b = (b | (b << 2)) & 0x3333;
- b = (b | (b << 1)) & 0x5555;
-
- // now the original bits are inthe odd bits
- b <<= 1;
-
- // the result is the union of a and b bits
- return (a | b);
-}
-
-/*
- * Interleave two morton<8> and returns the bits interleaved in an
- * morton<16>.
- */
-inline morton<16> interleave(const morton<8>& x, const morton<8>& y)
-{
- uint16_t a(x.value), b(y.value);
-
- // now the original bytes are in alternate bytes
- a = (a | (a << 4)) & 0x0F0F;
-
- // now the original bits are in the lowest 2 bits of the nibbles
- a = (a | (a << 2)) & 0x3333;
-
- // now the original bits are in the even bits
- a = (a | (a << 1)) & 0x5555;
-
- // do the same with b
- b = (b | (b << 4)) & 0x0F0F;
- b = (b | (b << 2)) & 0x3333;
- b = (b | (b << 1)) & 0x5555;
-
- // now the original bits are inthe odd bits
- b <<= 1;
-
- return (a | b);
-}
-
+} // interleave
/*
* This function "uninterleaves" a morton number into two morton number with
@@ -190,20 +99,20 @@
*
* The parameter number must be an morton<S> with S equal 16, 32 or 64.
*/
-template <std::size_t Bits>
-inline typename enable_if_c<Bits == 16 || Bits == 32 || Bits == 64,
- std::pair<morton<Bits/2>, morton<Bits/2> > >::type
-uninterleave(const morton<Bits>& number)
+template <std::size_t bits>
+inline typename enable_if_c<bits == 16 || bits == 32 || bits == 64,
+ std::pair<morton<bits/2>, morton<bits/2> > >::type
+uninterleave(const morton<bits>& number)
{
- morton<Bits/2> a, b;
+ morton<bits/2> a, b;
- for (int i = 0; i < Bits; i += 2) {
+ for (int i = 0; i < bits; i += 2) {
a.value |= ((number.value & (1 << i))) >> (i >> 1);
- b.value |= ((number.value & (1 << (i + 1)))) >> (i >> 1);
+ b.value |= ((number.value & (1 << (i + 1)))) >> ((i >> 1) + 1);
}
-
+
return make_pair(a, b);
-}
+} // uninterleave
-}
+} // boost
#endif
\ No newline at end of file
Added: sandbox/SOC/2010/bits_and_ints/boost/integer/morton.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/bits_and_ints/boost/integer/morton.hpp 2010-06-14 20:22:40 EDT (Mon, 14 Jun 2010)
@@ -0,0 +1,38 @@
+// Boost integer/morton.hpp header file ------------------------------//
+
+// (C) Copyright Murilo Adriano Vasconcelos 2010.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_MORTON_INCLUDED
+#define BOOST_MORTON_INCLUDED
+
+#include <boost/integer/detail/morton.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/cstdint.hpp>
+
+namespace boost {
+/*
+ * The morton<size> types holds an unsigned integer with `size' bytes.
+ * These types are used by interleave functions.
+ */
+template <std::size_t size, class Enable = typename enable_if_c<size == 8 || size == 16 || size == 32 || size == 64, int>::type>
+struct morton
+{
+ typedef morton<size> type;
+ typedef typename integer_detail::morton_type<size>::type value_type;
+ static const std::size_t bits = size;
+
+ morton<size, Enable>() : value(0) {}
+ morton<size, Enable>(const value_type& val) : value(val) {}
+ morton<size, Enable>(const morton<size, Enable>& copy) : value(copy.value) {}
+
+ value_type value;
+};
+
+}
+
+#endif