diff options
Diffstat (limited to 'chilbert')
| -rw-r--r-- | chilbert/Algorithm.hpp | 403 | ||||
| -rw-r--r-- | chilbert/BigBitVec.hpp | 12 | ||||
| -rw-r--r-- | chilbert/GetBits.hpp | 13 | ||||
| -rw-r--r-- | chilbert/GrayCodeRank.hpp | 293 | ||||
| -rw-r--r-- | chilbert/Hilbert.hpp | 105 | ||||
| -rw-r--r-- | chilbert/SetBits.hpp | 13 |
6 files changed, 409 insertions, 430 deletions
diff --git a/chilbert/Algorithm.hpp b/chilbert/Algorithm.hpp index cdf76a8..d4896ec 100644 --- a/chilbert/Algorithm.hpp +++ b/chilbert/Algorithm.hpp @@ -19,9 +19,8 @@ #ifndef CHILBERT_ALGORITHM_HPP #define CHILBERT_ALGORITHM_HPP - -#include "chilbert/FixBitVec.hpp" #include "chilbert/BigBitVec.hpp" +#include "chilbert/FixBitVec.hpp" #include "chilbert/GetBits.hpp" #include "chilbert/GetLocation.hpp" #include "chilbert/GrayCodeRank.hpp" @@ -30,7 +29,6 @@ #include <cassert> - // Templated Hilbert functions. // P - is the class used to represent each dimension // of a multidimensional point. @@ -44,146 +42,125 @@ // Whatever you use, they must all be of consistent underlying // storage types. - // The dimension across which the Hilbert curve travels // principally. // D0 is d + 1, where d is the actual dimension you want to // walk across. // MUST HAVE 0 <= D0 < n -#define D0 1 +#define D0 1 + +namespace chilbert { -namespace chilbert -{ // 'Transforms' a point. -template<class I> -inline -void -transform( - const I &e, - int d, - int n, - I &a - ) +template <class I> +inline void +transform(const I& e, int d, int n, I& a) { a ^= e; - a.rotr( d, n );//#D d+1, n ); + a.rotr(d, n); //#D d+1, n ); } // Inverse 'transforms' a point. -template<class I> -inline -void -transformInv( - const I &e, - int d, - int n, - I &a - ) +template <class I> +inline void +transformInv(const I& e, int d, int n, I& a) { - a.rotl( d, n );//#D d+1, n ); + a.rotl(d, n); //#D d+1, n ); a ^= e; } // Update for method 1 (GrayCodeInv in the loop) -template<class I> -inline -void -update1( - const I &l, - const I &t, - const I &w, - int n, - I &e, - int &d - ) +template <class I> +inline void +update1(const I& l, const I& t, const I& w, int n, I& e, int& d) { - assert( 0 <= d && d < n ); + assert(0 <= d && d < n); e = l; - e.toggle( d ); //#D d == n-1 ? 0 : d+1 ); - + e.toggle(d); //#D d == n-1 ? 0 : d+1 ); + // Update direction d += 1 + t.fsb(); - if ( d >= n ) d -= n; - if ( d >= n ) d -= n; - assert( 0 <= d && d < n ); + if (d >= n) { + d -= n; + } + if (d >= n) { + d -= n; + } + assert(0 <= d && d < n); - if ( ! (w.rack() & 1) ) - e.toggle( d == 0 ? n-1 : d-1 ); //#D d ); + if (!(w.rack() & 1)) { + e.toggle(d == 0 ? n - 1 : d - 1); //#D d ); + } } // Update for method 2 (GrayCodeInv out of loop) -template<class I> -inline -void -update2( - const I &l, - const I &t, - const I &w, - int n, - I &e, - int &d - ) +template <class I> +inline void +update2(const I& l, const I& t, const I& w, int n, I& e, int& d) { - assert( 0 <= d && d < n ); + assert(0 <= d && d < n); e = l; - e.toggle( d );//#D d == n-1 ? 0 : d+1 ); - + e.toggle(d); //#D d == n-1 ? 0 : d+1 ); + // Update direction d += 1 + t.fsb(); - if ( d >= n ) d -= n; - if ( d >= n ) d -= n; - assert( 0 <= d && d < n ); + if (d >= n) { + d -= n; + } + if (d >= n) { + d -= n; + } + assert(0 <= d && d < n); } -template <class P,class H,class I> -inline -void -_coordsToIndex( - const P *p, - int m, - int n, - H &h, - I&& scratch, - int *ds = nullptr // #HACK - ) +template <class P, class H, class I> +inline void +_coordsToIndex(const P* p, + int m, + int n, + H& h, + I&& scratch, + int* ds = nullptr // #HACK +) { I e{std::move(scratch)}; I l{e}; I t{e}; I w{e}; - int d, i; - int ho = m*n; // Initialize e.reset(); - d = D0; l.reset(); h = 0U; // Work from MSB to LSB - for ( i = m-1; i >= 0; i-- ) - { + int d = D0; + int ho = m * n; + for (int i = m - 1; i >= 0; i--) { // #HACK - if ( ds ) ds[i] = d; - + if (ds) { + ds[i] = d; + } + // Get corner of sub-hypercube where point lies. - getLocation<P,I>(p,n,i,l); + getLocation<P, I>(p, n, i, l); // Mirror and reflect the location. // t = T_{(e,d)}(l) t = l; - transform<I>(e,d,n,t); + transform<I>(e, d, n, t); w = t; - if ( i < m-1 ) + if (i < m - 1) { w.toggle(n - 1); + } // Concatenate to the index. ho -= n; - setBits<H,I>(h,n,ho,w); + setBits<H, I>(h, n, ho, w); // Update the entry point and direction. - update2<I>(l,t,w,n,e,d); + update2<I>(l, t, w, n, e, d); } grayCodeInv(h); @@ -195,58 +172,46 @@ _coordsToIndex( // number of dimensions, it will use the most efficient // representation for interim variables. // Assumes h is big enough for the output (n*m bits!) -template<class P,class H> -inline -void -coordsToIndex( - const P *p, // [in ] point - int m, // [in ] precision of each dimension in bits - int n, // [in ] number of dimensions - H &h // [out] Hilbert index - ) +template <class P, class H> +inline void +coordsToIndex(const P* p, // [in ] point + int m, // [in ] precision of each dimension in bits + int n, // [in ] number of dimensions + H& h // [out] Hilbert index +) { - if ( n <= FBV_BITS ) { + if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - _coordsToIndex<P,H,CFixBitVec>(p,m,n,h, CFixBitVec{}); + _coordsToIndex<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{}); } else { // Otherwise, they must be BigBitVecs - _coordsToIndex<P,H,CBigBitVec>(p,m,n,h, CBigBitVec(n)); + _coordsToIndex<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n)); } } - -template <class P,class H,class I> -inline -void -_indexToCoords( - P *p, - int m, - int n, - const H &h, - I&& scratch - ) +template <class P, class H, class I> +inline void +_indexToCoords(P* p, int m, int n, const H& h, I&& scratch) { I e{std::move(scratch)}; I l{e}; I t{e}; I w{e}; - int d, i, j, ho; // Initialize e.reset(); - d = D0; l.reset(); - for ( j = 0; j < n; j++ ) + for (int j = 0; j < n; j++) { p[j] = 0U; + } - ho = m*n; - // Work from MSB to LSB - for ( i = m-1; i >= 0; i-- ) - { + int d = D0; + int ho = m * n; + for (int i = m - 1; i >= 0; i--) { // Get the Hilbert index bits ho -= n; - getBits<H,I>(h,n,ho,w); + getBits<H, I>(h, n, ho, w); // t = GrayCode(w) t = w; @@ -255,14 +220,14 @@ _indexToCoords( // Reverse the transform // l = T^{-1}_{(e,d)}(t) l = t; - transformInv<I>(e,d,n,l); + transformInv<I>(e, d, n, l); // Distribute these bits // to the coordinates. - setLocation<P,I>(p,n,i,l); + setLocation<P, I>(p, n, i, l); // Update the entry point and direction. - update1<I>(l,t,w,n,e,d); + update1<I>(l, t, w, n, e, d); } } @@ -273,74 +238,62 @@ _indexToCoords( // representation for interim variables. // Assumes each entry of p is big enough to hold the // appropriate variable. -template<class P,class H> -inline -void -indexToCoords( - P *p, // [out] point - int m, // [in ] precision of each dimension in bits - int n, // [in ] number of dimensions - const H &h // [out] Hilbert index - ) +template <class P, class H> +inline void +indexToCoords(P* p, // [out] point + int m, // [in ] precision of each dimension in bits + int n, // [in ] number of dimensions + const H& h // [out] Hilbert index +) { - if ( n <= FBV_BITS ) { + if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width - _indexToCoords<P,H,CFixBitVec>(p,m,n,h,CFixBitVec{}); + _indexToCoords<P, H, CFixBitVec>(p, m, n, h, CFixBitVec{}); } else { // Otherwise, they must be BigBitVecs - _indexToCoords<P,H,CBigBitVec>(p,m,n,h,CBigBitVec(n)); + _indexToCoords<P, H, CBigBitVec>(p, m, n, h, CBigBitVec(n)); } } -template <class P,class HC,class I> -inline -void -_coordsToCompactIndex( - const P *p, - const int *ms, - int n, - HC &hc, - I&& scratch, - int M = 0, - int m = 0 - ) +template <class P, class HC, class I> +inline void +_coordsToCompactIndex(const P* p, + const int* ms, + int n, + HC& hc, + I&& scratch, + int M = 0, + int m = 0) { - int i, mn; - int *ds; - - // Get total precision and max precision - // if not supplied - if ( M == 0 || m == 0 ) - { + // Get total precision and max precision if not supplied + if (M == 0 || m == 0) { M = m = 0; - for ( i = 0; i < n; i++ ) - { - if ( ms[i] > m ) m = ms[i]; + for (int i = 0; i < n; i++) { + if (ms[i] > m) { + m = ms[i]; + } M += ms[i]; } } - mn = m*n; + const int mn = m * n; // If we could avoid allocation altogether (ie: have a // fixed buffer allocated on the stack) then this increases // speed by a bit (4% when n=4, m=20) - ds = new int [ m ]; + int* const ds = new int[m]; - if ( mn > FBV_BITS ) - { + if (mn > FBV_BITS) { CBigBitVec h(mn); - _coordsToIndex<P,CBigBitVec,I>(p,m,n,h,std::move(scratch),ds); - compactIndex<CBigBitVec,HC>(ms,ds,n,m,h,hc); - } - else - { + _coordsToIndex<P, CBigBitVec, I>(p, m, n, h, std::move(scratch), ds); + compactIndex<CBigBitVec, HC>(ms, ds, n, m, h, hc); + } else { CFixBitVec h; - _coordsToIndex<P,CFixBitVec,I>(p,m,n,h,std::move(scratch),ds); - compactIndex<CFixBitVec,HC>(ms,ds,n,m,h,hc); + _coordsToIndex<P, CFixBitVec, I>(p, m, n, h, std::move(scratch), ds); + compactIndex<CFixBitVec, HC>(ms, ds, n, m, h, hc); } - delete [] ds; + delete[] ds; } // This is wrapper to the basic Hilbert curve index @@ -349,39 +302,35 @@ _coordsToCompactIndex( // number of dimensions, it will use the most efficient // representation for interim variables. // Assumes h is big enough for the output (n*m bits!) -template<class P,class HC> -inline -void -coordsToCompactIndex( - const P *p, // [in ] point - const int *ms,// [in ] precision of each dimension in bits - int n, // [in ] number of dimensions - HC &hc, // [out] Hilbert index - int M = 0, - int m = 0 - ) +template <class P, class HC> +inline void +coordsToCompactIndex(const P* p, // [in ] point + const int* ms, // [in ] precision of each dimension in bits + int n, // [in ] number of dimensions + HC& hc, // [out] Hilbert index + int M = 0, + int m = 0) { - if ( n <= FBV_BITS ) { + if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width? - _coordsToCompactIndex<P,HC,CFixBitVec>(p,ms,n,hc,CFixBitVec{},M,m); + _coordsToCompactIndex<P, HC, CFixBitVec>( + p, ms, n, hc, CFixBitVec{}, M, m); } else { // Otherwise, they must be BigBitVecs. - _coordsToCompactIndex<P,HC,CBigBitVec>(p,ms,n,hc,CBigBitVec(n),M,m); + _coordsToCompactIndex<P, HC, CBigBitVec>( + p, ms, n, hc, CBigBitVec(n), M, m); } } -template <class P,class HC,class I> -inline -void -_compactIndexToCoords( - P *p, - const int *ms, - int n, - const HC &hc, - I&& scratch, - int M = 0, - int m = 0 - ) +template <class P, class HC, class I> +inline void +_compactIndexToCoords(P* p, + const int* ms, + int n, + const HC& hc, + I&& scratch, + int M = 0, + int m = 0) { I e{std::move(scratch)}; I l{e}; @@ -391,55 +340,55 @@ _compactIndexToCoords( I mask{e}; I ptrn{e}; - int d, i, j, b; - // Get total precision and max precision // if not supplied - if ( M == 0 || m == 0 ) - { + if (M == 0 || m == 0) { M = m = 0; - for ( i = 0; i < n; i++ ) - { - if ( ms[i] > m ) m = ms[i]; + for (int i = 0; i < n; i++) { + if (ms[i] > m) { + m = ms[i]; + } M += ms[i]; } } - + // Initialize e.reset(); - d = D0; l.reset(); - for ( j = 0; j < n; j++ ) + for (int j = 0; j < n; j++) { p[j] = 0; - + } + // Work from MSB to LSB - for ( i = m-1; i >= 0; i-- ) - { + int d = D0; + + for (int i = m - 1; i >= 0; i--) { // Get the mask and ptrn - extractMask<I>(ms,n,d,i,mask,b); + int b = 0; + extractMask<I>(ms, n, d, i, mask, b); ptrn = e; - ptrn.rotr(d,n);//#D ptrn.Rotr(d+1,n); + ptrn.rotr(d, n); //#D ptrn.Rotr(d+1,n); // Get the Hilbert index bits M -= b; r.reset(); // GetBits doesn't do this - getBits<HC,I>(hc,b,M,r); + getBits<HC, I>(hc, b, M, r); // w = GrayCodeRankInv(r) // t = GrayCode(w) - grayCodeRankInv<I>(mask,ptrn,r,n,b,t,w); + grayCodeRankInv<I>(mask, ptrn, r, n, b, t, w); // Reverse the transform // l = T^{-1}_{(e,d)}(t) l = t; - transformInv<I>(e,d,n,l); + transformInv<I>(e, d, n, l); // Distribute these bits // to the coordinates. - setLocation<P,I>(p,n,i,l); + setLocation<P, I>(p, n, i, l); // Update the entry point and direction. - update1<I>(l,t,w,n,e,d); + update1<I>(l, t, w, n, e, d); } } @@ -450,30 +399,28 @@ _compactIndexToCoords( // representation for interim variables. // Assumes each entry of p is big enough to hold the // appropriate variable. -template<class P,class HC> -inline -void -compactIndexToCoords( - P *p, // [out] point - const int *ms,// [in ] precision of each dimension in bits - int n, // [in ] number of dimensions - const HC &hc, // [out] Hilbert index - int M = 0, - int m = 0 - ) +template <class P, class HC> +inline void +compactIndexToCoords(P* p, // [out] point + const int* ms, // [in ] precision of each dimension in bits + int n, // [in ] number of dimensions + const HC& hc, // [out] Hilbert index + int M = 0, + int m = 0) { - if ( n <= FBV_BITS ) { + if (n <= FBV_BITS) { // Intermediate variables will fit in fixed width CFixBitVec scratch; - _compactIndexToCoords<P,HC,CFixBitVec>(p,ms,n,hc,CFixBitVec{},M,m); + _compactIndexToCoords<P, HC, CFixBitVec>( + p, ms, n, hc, CFixBitVec{}, M, m); } else { // Otherwise, they must be BigBitVecs CBigBitVec scratch(n); - _compactIndexToCoords<P,HC,CBigBitVec>(p,ms,n,hc,std::move(scratch),M,m); + _compactIndexToCoords<P, HC, CBigBitVec>( + p, ms, n, hc, std::move(scratch), M, m); } } -} - +} // namespace chilbert #endif diff --git a/chilbert/BigBitVec.hpp b/chilbert/BigBitVec.hpp index c5ade5d..5053b1a 100644 --- a/chilbert/BigBitVec.hpp +++ b/chilbert/BigBitVec.hpp @@ -40,14 +40,14 @@ class CBigBitVec { public: CBigBitVec(const int bits = 0) - : m_pcRacks{new FBV_UINT[bits == 0 ? 0 : FBVS_NEEDED(bits)]} - , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)} + : m_pcRacks{new FBV_UINT[bits == 0 ? 0 : FBVS_NEEDED(bits)]} + , m_iRacks{bits == 0 ? 0 : FBVS_NEEDED(bits)} { } CBigBitVec(const CBigBitVec& vec) - : m_pcRacks{new FBV_UINT[vec.m_iRacks]} - , m_iRacks{vec.m_iRacks} + : m_pcRacks{new FBV_UINT[vec.m_iRacks]} + , m_iRacks{vec.m_iRacks} { if (vec.m_pcRacks) { memcpy(m_pcRacks.get(), @@ -59,8 +59,8 @@ public: CBigBitVec(CBigBitVec&& vec) = default; CBigBitVec(const CFixBitVec& vec) - : m_pcRacks{new FBV_UINT[1]} - , m_iRacks{1} + : m_pcRacks{new FBV_UINT[1]} + , m_iRacks{1} { m_pcRacks[0] = vec.rack(); } diff --git a/chilbert/GetBits.hpp b/chilbert/GetBits.hpp index 9a6d5ec..66f6f32 100644 --- a/chilbert/GetBits.hpp +++ b/chilbert/GetBits.hpp @@ -23,11 +23,16 @@ namespace chilbert { +/** Copy a range of bits from one field to the start of another. + * + * @param h Source bit field + * @param n Number of bits + * @param i Start bit index in source + * @param w Destination bit field + */ template <class H, class I> -inline void getBits(const H& h, // bits to read - const int n, // number of bits - const int i, // bit index - I& w) // destination +inline void +getBits(const H& h, const int n, const int i, I& w) { for (int j = 0; j < n; j++) { setBit(w, j, testBit(h, i + j)); diff --git a/chilbert/GrayCodeRank.hpp b/chilbert/GrayCodeRank.hpp index cff8dfc..3083489 100644 --- a/chilbert/GrayCodeRank.hpp +++ b/chilbert/GrayCodeRank.hpp @@ -19,179 +19,170 @@ #ifndef CHILBERT_GRAYCODERANK_HPP #define CHILBERT_GRAYCODERANK_HPP - -#include "chilbert/FixBitVec.hpp" #include "chilbert/BigBitVec.hpp" +#include "chilbert/FixBitVec.hpp" #include <cassert> -namespace chilbert +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) { - // 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 - ) - { - hc = 0; - - int hi = 0; - int hci = 0; - - // Run through the levels of precision - for ( int i = 0; i < m; i++ ) - { - // Run through the dimensions - int j = ds[i]; - do - { - // This dimension contributes a bit? - if ( ms[j] > i ) - { - if (testBit(h, hi)) { - setBit(hc, hci); - } - ++hci; + hc = 0; + + int hi = 0; + int hci = 0; + + // Run through the levels of precision + for (int i = 0; i < m; i++) { + // Run through the dimensions + int j = ds[i]; + do { + // This dimension contributes a bit? + if (ms[j] > i) { + if (testBit(h, hi)) { + setBit(hc, hci); } + ++hci; + } - if ( ++j == n ) j = 0; - ++hi; + if (++j == n) { + j = 0; } - while ( j != ds[i] ); - } + ++hi; + } while (j != ds[i]); } +} - 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; } +template <class I> +inline void +grayCodeRank(const I& mask, const I& gi, int n, I& r) +{ + r.reset(); + + int jr = 0; + FBV_UINT jm = 1; + int ir = 0; + FBV_UINT im = 1; + for (int 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; } } - } + im <<= 1; + if (im == 0) { + im = 1; + ++ir; + } + } +} - 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; } +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 ir, jr; + FBV_UINT im, jm; + + int i = n - 1; + BBV_MODSPLIT(ir, im, i); + im = (FBV1 << im); + + int 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; + } 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; } + im >>= 1; + if (im == 0) { + im = ((FBV_UINT)1) << (FBV_BITS - 1); + --ir; } } +} - - 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; +template <class I> +inline void +extractMask(const int* ms, int n, int d, int i, I& mask, int& b) +{ + assert(0 <= d && d < n); + + mask.reset(); + b = 0; + + FBV_UINT jm = 1; + int jr = 0; + int j = d; // #D j = (d==n-1) ? 0 : d+1; + do { + if (ms[j] > i) { + mask.racks()[jr] |= jm; + ++b; } - while ( j != d ); - } + + jm <<= 1; + if (jm == 0) { + jm = 1; + ++jr; + } + if (++j == n) { + j = 0; + } + } while (j != d); } +} // namespace chilbert #endif diff --git a/chilbert/Hilbert.hpp b/chilbert/Hilbert.hpp index 7ff0a78..34279ae 100644 --- a/chilbert/Hilbert.hpp +++ b/chilbert/Hilbert.hpp @@ -19,7 +19,6 @@ #ifndef CHILBERT_HILBERT_HPP #define CHILBERT_HILBERT_HPP - #include "chilbert/Algorithm.hpp" #include "chilbert/BigBitVec.hpp" #include "chilbert/FixBitVec.hpp" @@ -58,84 +57,116 @@ // Largest precision value (max_i { ms[i] }). If not provided, defaults // to zero and will be calculated by the function, - -namespace chilbert -{ +namespace chilbert { // fix -> fix -inline void coordsToIndex( const CFixBitVec *p, int m, int n, CFixBitVec &h ) +inline void +coordsToIndex(const CFixBitVec* p, int m, int n, CFixBitVec& h) { - coordsToIndex<CFixBitVec,CFixBitVec>(p,m,n,h); + coordsToIndex<CFixBitVec, CFixBitVec>(p, m, n, h); } -inline void indexToCoords( CFixBitVec *p, int m, int n, const CFixBitVec &h ) +inline void +indexToCoords(CFixBitVec* p, int m, int n, const CFixBitVec& h) { - indexToCoords<CFixBitVec,CFixBitVec>(p,m,n,h); + indexToCoords<CFixBitVec, CFixBitVec>(p, m, n, h); } -inline void coordsToCompactIndex( const CFixBitVec *p, const int *ms, int n, - CFixBitVec &hc, int M, int m ) +inline void +coordsToCompactIndex(const CFixBitVec* p, + const int* ms, + int n, + CFixBitVec& hc, + int M, + int m) { - coordsToCompactIndex<CFixBitVec,CFixBitVec>(p,ms,n,hc,M,m); + coordsToCompactIndex<CFixBitVec, CFixBitVec>(p, ms, n, hc, M, m); } -inline void compactIndexToCoords( CFixBitVec *p, const int *ms, int n, - const CFixBitVec &hc, int M, int m ) +inline void +compactIndexToCoords(CFixBitVec* p, + const int* ms, + int n, + const CFixBitVec& hc, + int M, + int m) { - compactIndexToCoords<CFixBitVec,CFixBitVec>(p,ms,n,hc,M,m); + compactIndexToCoords<CFixBitVec, CFixBitVec>(p, ms, n, hc, M, m); } // fix -> big -inline void coordsToIndex( const CFixBitVec *p, int m, int n, CBigBitVec &h ) +inline void +coordsToIndex(const CFixBitVec* p, int m, int n, CBigBitVec& h) { - coordsToIndex<CFixBitVec,CBigBitVec>(p,m,n,h); + coordsToIndex<CFixBitVec, CBigBitVec>(p, m, n, h); } -inline void indexToCoords( CFixBitVec *p, int m, int n, const CBigBitVec &h ) +inline void +indexToCoords(CFixBitVec* p, int m, int n, const CBigBitVec& h) { - indexToCoords<CFixBitVec,CBigBitVec>(p,m,n,h); + indexToCoords<CFixBitVec, CBigBitVec>(p, m, n, h); } -inline void coordsToCompactIndex( const CFixBitVec *p, const int *ms, int n, - CBigBitVec &hc, int M, int m ) +inline void +coordsToCompactIndex(const CFixBitVec* p, + const int* ms, + int n, + CBigBitVec& hc, + int M, + int m) { - coordsToCompactIndex<CFixBitVec,CBigBitVec>(p,ms,n,hc,M,m); + coordsToCompactIndex<CFixBitVec, CBigBitVec>(p, ms, n, hc, M, m); } -inline void compactIndexToCoords( CFixBitVec *p, const int *ms, int n, - const CBigBitVec &hc, int M, int m ) +inline void +compactIndexToCoords(CFixBitVec* p, + const int* ms, + int n, + const CBigBitVec& hc, + int M, + int m) { - compactIndexToCoords<CFixBitVec,CBigBitVec>(p,ms,n,hc,M,m); + compactIndexToCoords<CFixBitVec, CBigBitVec>(p, ms, n, hc, M, m); } // big -> big -inline void coordsToIndex( const CBigBitVec *p, int m, int n, CBigBitVec &h ) +inline void +coordsToIndex(const CBigBitVec* p, int m, int n, CBigBitVec& h) { - coordsToIndex<CBigBitVec,CBigBitVec>(p,m,n,h); + coordsToIndex<CBigBitVec, CBigBitVec>(p, m, n, h); } -inline void indexToCoords( CBigBitVec *p, int m, int n, const CBigBitVec &h ) +inline void +indexToCoords(CBigBitVec* p, int m, int n, const CBigBitVec& h) { - indexToCoords<CBigBitVec,CBigBitVec>(p,m,n,h); + indexToCoords<CBigBitVec, CBigBitVec>(p, m, n, h); } -inline void coordsToCompactIndex( const CBigBitVec *p, const int *ms, int n, - CBigBitVec &hc, int M, int m ) +inline void +coordsToCompactIndex(const CBigBitVec* p, + const int* ms, + int n, + CBigBitVec& hc, + int M, + int m) { - coordsToCompactIndex<CBigBitVec,CBigBitVec>(p,ms,n,hc,M,m); + coordsToCompactIndex<CBigBitVec, CBigBitVec>(p, ms, n, hc, M, m); } -inline void compactIndexToCoords( CBigBitVec *p, const int *ms, int n, - const CBigBitVec &hc, int M, int m ) +inline void +compactIndexToCoords(CBigBitVec* p, + const int* ms, + int n, + const CBigBitVec& hc, + int M, + int m) { - compactIndexToCoords<CBigBitVec,CBigBitVec>(p,ms,n,hc,M,m); -} - + compactIndexToCoords<CBigBitVec, CBigBitVec>(p, ms, n, hc, M, m); } +} // namespace chilbert #endif - diff --git a/chilbert/SetBits.hpp b/chilbert/SetBits.hpp index 6b2cd24..1a4874b 100644 --- a/chilbert/SetBits.hpp +++ b/chilbert/SetBits.hpp @@ -23,11 +23,16 @@ namespace chilbert { +/** Set a range of bits in one field from the start of another. + * + * @param h Destination bit field + * @param n Number of bits + * @param i Start bit index in destination + * @param w Source bit field + */ template <class H, class I> -inline void setBits(H& h, // destination - const int n, // number of bits - const int i, // bit position - const I& w) // bits to place +inline void +setBits(H& h, const int n, const int i, const I& w) { for (int j = 0; j < n; j++) { setBit(h, i + j, testBit(w, j)); |