bin64.h

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