Rename library "chilbert"

1 files changed, 205 insertions, 0 deletions

diff --git a/chilbert/GrayCodeRank.hpp b/chilbert/GrayCodeRank.hpp
new file mode 100644
index 0000000..13c169c
--- /dev/null
+++ b/chilbert/GrayCodeRank.hpp
@@ -0,0 +1,205 @@
+/*
+  Copyright (C) 2018 David Robillard <d@drobilla.net>
+  Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>
+
+  This program is free software: you can redistribute it and/or modify it under
+  the terms of the GNU General Public License as published by the Free Software
+  Foundation, either version 2 of the License, or (at your option) any later
+  version.
+
+  This program is distributed in the hope that it will be useful, but WITHOUT
+  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+  FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+  details.
+
+  You should have received a copy of the GNU General Public License along with
+  this program.  If not, see <https://www.gnu.org/licenses/>.
+*/
+
+#ifndef _GRAYCODERANK_HPP_
+#define _GRAYCODERANK_HPP_
+
+
+#include "chilbert/BigBitVec.hpp"
+
+
+namespace chilbert
+{
+	// This is the bulk of the cost in calculating
+	// a Compact Hilbert Index.  It compresses a previously
+	// calculated index when provided the rotation
+	// at each level of precision.
+	template<class H,class HC>
+	inline
+	void
+	compactIndex(
+		const int *ms,
+		const int *ds,
+		int n,
+		int m,
+		H &h,
+		HC &hc
+		)
+	{
+		int i, j, hr, hcr;
+		FBV_UINT hm, hcm;
+
+		hc.reset();
+
+		hr = hcr = 0;
+		hm = hcm = 1;
+
+		// Run through the levels of precision
+		for ( i = 0; i < m; i++ )
+		{
+			// Run through the dimensions
+			j = ds[i];
+			do
+			{
+				// This dimension contributes a bit?
+				if ( ms[j] > i )
+				{
+					if ( h.racks()[hr] & hm )
+						hc.racks()[hcr] |= hcm;
+					hcm<<=1; if (hcm==0) {hcm=1;++hcr;}
+				}
+
+				if ( ++j == n ) j = 0;
+				hm<<=1; if (hm==0) {hm=1;++hr;}
+			}
+			while ( j != ds[i] );
+		}
+
+		return;
+	}
+
+	template<class I>
+	inline
+	void
+	grayCodeRank(
+		const I &mask,
+		const I &gi,
+		int n,
+		I &r
+		)
+	{
+		r.reset();
+		int i, ir, jr;
+		FBV_UINT im, jm;
+
+		jr = 0; jm = 1;
+		ir = 0; im = 1;
+		for ( i = 0; i < n; ++i )
+		{
+			if ( mask.racks()[ir] & im )
+			{
+				if ( gi.racks()[ir] & im )
+					r.racks()[jr] |= jm;
+				jm<<=1; if ( jm == 0 ) { jm = 1; ++jr; }
+			}
+			
+			im<<=1; if ( im == 0 ) { im = 1; ++ir; }
+		}
+
+		return;
+	}
+
+
+	template<class I>
+	inline
+	void
+	grayCodeRankInv(
+		const I &mask,
+		const I &ptrn,
+		const I &r,
+		int n,
+		int b,
+		I &g,
+		I &gi
+		)
+	{
+		g.reset();
+		gi.reset();
+
+		int i, j, ir, jr;
+		FBV_UINT im, jm;
+
+		i = n-1;
+		BBV_MODSPLIT(ir,im,i);
+		im = (FBV1<<im);
+
+		j = b-1;
+		BBV_MODSPLIT(jr,jm,j);
+		jm = (FBV1<<jm);
+
+		FBV_UINT gi0, gi1, g0;
+		gi1 = gi0 = g0 = 0;
+
+		for ( ; i >= 0; --i )
+		{
+			// Unconstrained bit?
+			if ( mask.racks()[ir] & im )
+			{
+				gi1 = gi0;
+				gi0 = (r.racks()[jr] & jm) > 0;
+				g0 = gi0 ^ gi1;
+				if ( gi0 ) gi.racks()[ir] |= im;
+				if ( g0 ) g.racks()[ir] |= im;
+				jm>>=1; if ( jm == 0 ) { jm=((FBV_UINT)1)<<(FBV_BITS-1); --jr; }
+			}
+			else
+			{
+				g0 = (ptrn.racks()[ir] & im) > 0;
+				gi1 = gi0;
+				gi0 = g0 ^ gi1;
+				if ( gi0 ) gi.racks()[ir] |= im;
+				if ( g0 ) g.racks()[ir] |= im;
+			}
+
+			im>>=1; if ( im == 0 ) { im=((FBV_UINT)1)<<(FBV_BITS-1); --ir; }
+		}
+
+		return;
+	}
+
+	
+	template <class I>
+	inline
+	void
+	extractMask(
+		const int *ms,
+		int n,
+		int d,
+		int i,
+		I &mask,
+		int &b
+		)
+	{
+		assert( 0 <= d && d < n );
+		int j, jr;
+		FBV_UINT jm;
+
+		mask.reset();
+		b = 0;
+		
+		jm = 1; jr = 0;
+		j = d; // #D j = (d==n-1) ? 0 : d+1;
+		do
+		{
+			if ( ms[j] > i )
+			{
+				mask.racks()[jr] |= jm;
+				++b;
+			}
+		
+			jm <<= 1; if ( jm == 0 ) { jm=1; ++jr; }
+			if ( ++j == n ) j = 0;
+		}
+		while ( j != d );
+
+		return;
+	}
+};
+
+
+#endif