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