/
registers.go
123 lines (110 loc) · 2.09 KB
/
registers.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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package hyperloglog
import (
"math"
)
type reg uint8
type tailcuts []reg
type registers struct {
tailcuts
nz uint32
}
func (r *reg) set(offset, val uint8) bool {
var isZero bool
if offset == 0 {
isZero = uint8((*r)>>4) == 0
tmpVal := uint8((*r) << 4 >> 4)
*r = reg(tmpVal | (val << 4))
} else {
isZero = uint8((*r)<<4>>4) == 0
tmpVal := uint8((*r) >> 4)
*r = reg(tmpVal<<4 | val)
}
return isZero
}
func (r *reg) get(offset uint8) uint8 {
if offset == 0 {
return uint8((*r) >> 4)
}
return uint8((*r) << 4 >> 4)
}
func newRegisters(size uint32) *registers {
return ®isters{
tailcuts: make(tailcuts, size/2),
nz: size,
}
}
func (rs *registers) clone() *registers {
if rs == nil {
return nil
}
tc := make([]reg, len(rs.tailcuts))
copy(tc, rs.tailcuts)
return ®isters{
tailcuts: tc,
nz: rs.nz,
}
}
func (rs *registers) rebase(delta uint8) {
nz := uint32(len(rs.tailcuts)) * 2
for i := range rs.tailcuts {
val := rs.tailcuts[i].get(0)
if val >= delta {
rs.tailcuts[i].set(0, val-delta)
if val-delta > 0 {
nz--
}
}
val = rs.tailcuts[i].get(1)
if val >= delta {
rs.tailcuts[i].set(1, val-delta)
if val-delta > 0 {
nz--
}
}
}
rs.nz = nz
}
func (rs *registers) set(i uint32, val uint8) {
offset, index := uint8(i%2), i/2
if rs.tailcuts[index].set(offset, val) {
rs.nz--
}
}
func (rs *registers) get(i uint32) uint8 {
offset, index := uint8(i%2), i/2
return rs.tailcuts[index].get(offset)
}
func (rs *registers) sumAndZeros(base uint8) (res, ez float64) {
for _, r := range rs.tailcuts {
v1 := float64(base + r.get(0))
if v1 == 0 {
ez++
}
res += 1.0 / math.Pow(2.0, v1)
v2 := float64(base + r.get(0))
if v2 == 0 {
ez++
}
res += 1.0 / math.Pow(2.0, float64(base+r.get(1)))
}
rs.nz = uint32(ez)
return res, ez
}
func (rs *registers) min() uint8 {
if rs.nz > 0 {
return 0
}
min := uint8(math.MaxUint8)
for _, r := range rs.tailcuts {
if val := uint8(r << 4 >> 4); val < min {
min = val
}
if val := uint8(r >> 4); val < min {
min = val
}
if min == 0 {
break
}
}
return min
}