bin64.h

   1 #ifndef BIN64_H
   2 #define BIN64_H
   3 #include <assert.h>
   4 #include <stdint.h>
   5
   6
   7
   8 /** Numbering for (aligned) logarithmical bins.
   9     Each number stands for an interval
  10     [o*2^l,(o+1)*2^l), where l is the layer and o
  11     is the offset.
  12     Bin numbers in the tail111 encoding: meaningless
  13     bits in the tail are set to 0111...11, while the
  14     head denotes the offset. Thus, 1101 is the bin
  15     at layer 1, offset 3 (i.e. fourth). */
  16 struct bin64_t {
  17     uint64_t v;
  18     static const uint64_t NONE;
  19     static const uint64_t ALL;
  20
  21     bin64_t() : v(NONE) {}
  22     bin64_t(const bin64_t&b) : v(b.v) {}
  23     bin64_t(const uint64_t val) : v(val) {}
  24     bin64_t(uint8_t layer, uint64_t offset) :
  25         v( (offset<<(layer+1)) | ((1ULL<<layer)-1) ) {}
  26     operator uint64_t () const { return v; }
  27     bool operator == (bin64_t& b) const { return v==b.v; }
  28
  29     static bin64_t none () { return NONE; }
  30     static bin64_t all () { return ALL; }
  31
  32     uint64_t tail_bits () const {
  33         return v ^ (v+1);
  34     }
  35
  36     uint64_t tail_bit () const {
  37         return (tail_bits()+1)>>1;
  38     }
  39
  40     bin64_t sibling () const {
  41         // if (v==ALL) return NONE;
  42         return bin64_t(v^(tail_bit()<<1));
  43     }
  44
  45     int layer () const {
  46         int r = 0;
  47         uint64_t tail = ((v^(v+1))+1)>>1;
  48         if (tail>0xffffffffULL) {
  49             r = 32;
  50             tail>>=32;
  51         }
  52         // courtesy of Sean Eron Anderson
  53         // http://graphics.stanford.edu/~seander/bithacks.html
  54         static const int DeBRUIJN[32] = {
  55           0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  56           31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  57         };
  58         r += DeBRUIJN[((uint32_t)(tail*0x077CB531U))>>27];
  59         return r;
  60     }
  61
  62     uint64_t base_offset () const {
  63         return (v&~(tail_bits()))>>1;
  64     }
  65
  66     uint64_t offset () const {
  67         return v >> (layer()+1);
  68     }
  69
  70     bin64_t to (bool right) const {
  71         if (!(v&1))
  72             return NONE;
  73         uint64_t tb = tail_bit()>>1;
  74         if (right)
  75             tb |= (tb<<1);
  76         return bin64_t(v^tb);
  77     }
  78
  79     bin64_t left () const {
  80         return to(false);
  81     }
  82
  83     bin64_t right () const {
  84         return to(true);
  85     }
  86
  87     bool    within (bin64_t maybe_asc) {
  88         uint64_t short_tail = maybe_asc.tail_bits();
  89         if (tail_bits()>short_tail)
  90             return false;
  91         return (v&~short_tail) == (maybe_asc.v&~short_tail) ;
  92     }
  93
  94     /** Left or right, depending whether the destination is. */
  95     bin64_t towards (bin64_t dest) const {
  96         if (!dest.within(*this))
  97             return NONE;
  98         if (dest.within(left()))
  99             return left();
 100         else
 101             return right();
 102     }
 103
 104     bin64_t parent () const {
 105         uint64_t tbs = tail_bits(), ntbs = (tbs+1)|tbs;
 106         return bin64_t( (v&~ntbs) | tbs );
 107     }
 108
 109     bool is_left () const {
 110         uint64_t tb = tail_bit();
 111         return !(v&(tb<<1));
 112     }
 113     bool is_right() const { return !is_left(); }
 114
 115     bin64_t left_foot () const {
 116         return bin64_t(0,base_offset());
 117     }
 118
 119     /** Whether layer is 0. */
 120     bool    is_base () const {
 121         return !(v & 1);
 122     }
 123
 124     /** Depth-first in-order binary tree traversal. */
 125     bin64_t next_dfsio (uint8_t floor);
 126
 127     bin64_t width () const {
 128         return (tail_bits()+1)>>1;
 129     }
 130
 131     /** The array must have 64 cells, as it is the max
 132      number of peaks possible +1 (and there are no reason
 133      to assume there will be less in any given case. */
 134     static int peaks (uint64_t length, bin64_t* peaks) ;
 135
 136 };
 137
 138
 139 #endif
 140
 141 /**
 142                  00111
 143        0011                    1011
 144   001      101         1001          1101
 145 0   10  100  110    1000  1010   1100   1110
 146
 147                   7
 148       3                         11
 149   1        5             9             13
 150 0   2    4    6       8    10      12     14
 151
 152 once we have peak hashes, this struture is more natural than bin-v1
 153
 154 */