bin64.h

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