1 #if !defined HAVE_BIT_RLL2_H__ 2 #define HAVE_BIT_RLL2_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2012, 2014 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 #include "fxttypes.h" // ulong 9 #include "bits/bitsperlong.h" 10 11 12 class bit_rll2 13 // Run length limited (RLL) words and Fibonacci words. 14 // The RLL words are in lexicographic order, 15 // the Fibonacci words are in a minimal change order (Gray code). 16 { 17 public: 18 ulong w_; // RLL-word 19 20 public: bit_rll2()21 bit_rll2() { first(); } 22 first()23 void first() 24 { 25 w_ = 1; 26 ulong s = 3; // max run length + 1 27 while ( s <= BITS_PER_LONG ) 28 { 29 w_ |= w_ << s; 30 s <<= 1; 31 } 32 } 33 last()34 void last() 35 { 36 first(); 37 w_ <<= 2; // shift by max run length 38 w_ = ~w_; 39 } 40 middle()41 void middle() 42 // RLL word corresponding to all-zero Fibonacci word 43 { 44 #if BITS_PER_LONG == 64 45 w_ = 0xaaaaaaaaaaaaaaaaUL; 46 #else 47 w_ = 0xaaaaaaaaUL; 48 #endif 49 } 50 51 private: step(ulong x)52 ulong step(ulong x) 53 { 54 x |= ( (x>>1) & (x>>2) ); // max run length 2 55 // ==> Gray code with max 1 successive one (Fibonacci words) 56 57 // x |= ( (x>>1) & (x>>2) & (x>>3) ); // max run length 3 58 // ==> Gray code with max 2 successive ones 59 60 // x |= ( (x>>1) & (x>>2) & (x>>4) ); // max run length 4 61 // ==> Gray code with max 3 successive ones 62 63 x ^= (x+1); 64 w_ ^= x; 65 return w_; 66 } 67 68 public: next()69 ulong next() { return step( w_ ); } prev()70 ulong prev() { return step( ~w_ ); } 71 data()72 ulong data() const 73 // RLL word (lexicographic order) 74 { return w_; } 75 fib()76 ulong fib() const 77 // Fibonacci word (Gray code) 78 { return ~( w_ ^ (w_ >> 1) ); } 79 next_fib()80 ulong next_fib() { next(); return fib(); } prev_fib()81 ulong prev_fib() { prev(); return fib(); } 82 }; 83 // ------------------------- 84 85 86 #endif // !defined HAVE_BIT_RLL2_H__ 87