[Boost-commit] svn:boost r62959 - in sandbox/SOC/2010/bits_and_ints/boost/integer: . detail

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