-
Notifications
You must be signed in to change notification settings - Fork 4
/
prefix_calc.go
105 lines (87 loc) · 2.41 KB
/
prefix_calc.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package jetalloc
import (
"io"
"github.com/insolar/assured-ledger/ledger-core/ledger/jet"
"github.com/insolar/assured-ledger/ledger-core/vanilla/throw"
)
const SplitMedian = 7 // makes 0 vs 1 ratio like [0..6] vs [7..15]
// this enables left branches of jets to be ~23% less loaded
//
// Default prefix calculator, requires 12 bytes for 16 bit prefix and uses SplitMedian const for mis-balancing.
//
// Recommended use:
// bitPrefix := NewPrefixCalc().FromXXX(prefixTree.MaxDepth(), reference)
// or
// bitPrefix := NewPrefixCalc().FromXXX(16, reference)
// ...
// bitPrefix, bitPrefixLen = prefixTree.GetPrefix(bitPrefix)
//
func NewPrefixCalc() PrefixCalc {
return PrefixCalc{4, SplitMedian}
}
//
// Converts a byte sequence into a bit prefix for PrefixTree.
//
// Must set OverlapOfs>0 when a structured header is present within a byte sequence.
// When OverlapOfs !=0, then the calculator will mix b[n]^b[n + OverlapOfs]
//
type PrefixCalc struct {
OverlapOfs uint8
SplitMedian uint8
}
// Converts data[:OverlapOfs + (prefixLen)/2] into prefixLen bits.
func (p PrefixCalc) FromSlice(prefixLen int, data []byte) jet.Prefix {
switch {
case prefixLen < 0 || prefixLen > 32:
panic(throw.IllegalValue())
case prefixLen == 0:
return 0
}
return p.fromSlice(prefixLen, data)
}
// Converts data[:OverlapOfs + (prefixLen)/2] into prefixLen bits.
func (p PrefixCalc) FromReader(prefixLen int, data io.Reader) (jet.Prefix, error) {
switch {
case prefixLen < 0 || prefixLen > 32:
panic(throw.IllegalValue())
case data == nil:
panic(throw.IllegalValue())
case prefixLen == 0:
return 0, nil
}
dataBuf := make([]byte, int(p.OverlapOfs)+(prefixLen+1)>>1)
switch n, err := data.Read(dataBuf); {
case err != nil:
return 0, err
case n != len(dataBuf):
return 0, throw.FailHere("insufficient data length")
}
return p.fromSlice(prefixLen, dataBuf), nil
}
func (p PrefixCalc) fromSlice(prefixLen int, data []byte) jet.Prefix {
result := jet.Prefix(0)
bit := jet.Prefix(1)
for i, d := range data {
if p.OverlapOfs > 0 {
// TODO check quality of distribution because of XOR
d ^= data[i+int(p.OverlapOfs)]
}
if d&0xF >= p.SplitMedian {
result |= bit
}
if prefixLen == 1 {
// odd length
return result
}
bit <<= 1
if (d >> 4) >= p.SplitMedian {
result |= bit
}
prefixLen -= 2
if prefixLen == 0 {
return result
}
bit <<= 1
}
panic(throw.FailHere("insufficient data length"))
}