forked from kelindar/bitmap
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bitmap.go
356 lines (311 loc) · 8.14 KB
/
bitmap.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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
// Copyright (c) Roman Atachiants and contributors. All rights reserved.
// Licensed under the MIT license. See LICENSE file in the project root for details.
package bitmap
import (
"math"
"math/bits"
"unsafe"
"github.com/klauspost/cpuid/v2"
)
const (
isUnsupported = iota
isAccelerated
isAVX512
)
// Hardware contains the resolved acceleration level
var hardware = levelOf(cpuid.CPU)
// levelOf returns the hardware acceleration level
func levelOf(cpu cpuid.CPUInfo) int {
switch {
case cpu.Supports(cpuid.AVX512F) && cpu.Supports(cpuid.AVX512DQ) && cpu.Supports(cpuid.AVX512BW):
return isAVX512
case cpu.Supports(cpuid.AVX2) && cpu.Supports(cpuid.FMA3):
return isAccelerated
case cpu.Supports(cpuid.ASIMD):
return isAccelerated
default:
return isUnsupported
}
}
// Bitmap represents a scalar-backed bitmap index
type Bitmap []uint64
// Set sets the bit x in the bitmap and grows it if necessary.
func (dst *Bitmap) Set(x uint32) {
blkAt := int(x >> 6)
bitAt := int(x % 64)
if size := len(*dst); blkAt >= size {
dst.grow(blkAt)
}
(*dst)[blkAt] |= (1 << bitAt)
}
func (dst *Bitmap) SetRange(from, to uint32) {
if from > to {
return
}
blkAt, bitAt := location(from)
blkEndAt, bitEndAt := location(to)
if size := len(*dst); blkEndAt >= size {
dst.grow(blkEndAt)
}
negaAll := uint64(math.MaxUint64)
negaTo := uint64(negaAll >> (63 - bitEndAt))
negaFrom := uint64(negaAll << bitAt)
if blkAt == blkEndAt {
(*dst)[blkAt] = negaFrom & negaTo
return
}
(*dst)[blkAt] = negaFrom
for blkAt < blkEndAt {
(*dst)[blkAt] = negaAll
blkAt++
}
(*dst)[blkEndAt] = negaTo
}
// Remove removes the bit x from the bitmap, but does not shrink it.
func (dst *Bitmap) Remove(x uint32) {
if blkAt := int(x >> 6); blkAt < len(*dst) {
bitAt := int(x % 64)
(*dst)[blkAt] &^= (1 << bitAt)
}
}
// Contains checks whether a value is contained in the bitmap or not.
func (dst Bitmap) Contains(x uint32) bool {
blkAt := int(x >> 6)
if size := len(dst); blkAt >= size {
return false
}
bitAt := int(x % 64)
return (dst[blkAt] & (1 << bitAt)) > 0
}
// ContainsAny checks whether a value in a range is contained in the bitmap or not.
func (dst Bitmap) ContainsAnyInRange(from, to uint32) bool {
if from > to {
return false
}
blkAt, bitAt := location(from)
if size := len(dst); blkAt < size {
blkEndAt, bitEndAt := location(to)
negaAll := uint64(math.MaxUint64)
negaTo := uint64(negaAll >> (63 - bitEndAt))
negaFrom := uint64(negaAll << bitAt)
if blkAt == blkEndAt {
negaFrom = negaFrom & negaTo
}
if (dst[blkAt])&negaFrom > 0 {
return true
}
blkAt++
if blkEndAt >= size {
blkEndAt = size - 1
}
if blkAt > blkEndAt || blkAt >= size {
return false
}
for blkAt < blkEndAt {
if (dst[blkAt])&negaAll > 0 {
return true
}
blkAt++
}
if (dst[blkEndAt])&negaTo > 0 {
return true
}
}
return false
}
// ContainsRange checks whether all values in a range is contained in the bitmap or not.
func (dst Bitmap) ContainsAllInRange(from, to uint32) bool {
if from > to {
return false
}
blkAt, bitAt := location(from)
if size := len(dst); blkAt < size {
blkEndAt, bitEndAt := location(to)
negaAll := uint64(math.MaxUint64)
negaTo := uint64(negaAll >> (63 - bitEndAt))
negaFrom := uint64(negaAll << bitAt)
if blkAt == blkEndAt {
negaFrom = negaFrom & negaTo
}
if (dst[blkAt])&negaFrom != negaFrom {
return false
}
blkAt++
if blkEndAt >= size {
blkEndAt = size - 1
}
if blkAt > blkEndAt || blkAt >= size {
return true
}
for blkAt < blkEndAt {
if (dst[blkAt]) != negaAll {
return false
}
blkAt++
}
if (dst[blkEndAt])&negaTo == negaTo {
return true
}
}
return false
}
// Ones sets the entire bitmap to one.
func (dst Bitmap) Ones() {
for i := 0; i < len(dst); i++ {
dst[i] = 0xffffffffffffffff
}
}
// Min get the smallest value stored in this bitmap, assuming the bitmap is not empty.
func (dst Bitmap) Min() (uint32, bool) {
for blkAt, blk := range dst {
if blk != 0x0 {
return uint32(blkAt<<6 + bits.TrailingZeros64(blk)), true
}
}
return 0, false
}
// Max get the largest value stored in this bitmap, assuming the bitmap is not empty.
func (dst Bitmap) Max() (uint32, bool) {
var blk uint64
for blkAt := len(dst) - 1; blkAt >= 0; blkAt-- {
if blk = dst[blkAt]; blk != 0x0 {
return uint32(blkAt<<6 + (63 - bits.LeadingZeros64(blk))), true
}
}
return 0, false
}
// MinZero finds the first zero bit and returns its index, assuming the bitmap is not empty.
func (dst Bitmap) MinZero() (uint32, bool) {
for blkAt, blk := range dst {
if blk != 0xffffffffffffffff {
return uint32(blkAt<<6 + bits.TrailingZeros64(^blk)), true
}
}
return 0, false
}
// MaxZero get the last zero bit and return its index, assuming bitmap is not empty
func (dst Bitmap) MaxZero() (uint32, bool) {
var blk uint64
for blkAt := len(dst) - 1; blkAt >= 0; blkAt-- {
if blk = dst[blkAt]; blk != 0xffffffffffffffff {
return uint32(blkAt<<6 + (63 - bits.LeadingZeros64(^blk))), true
}
}
return 0, false
}
// CountTo counts the number of elements in the bitmap up until the specified index. If until
// is math.MaxUint32, it will return the count. The count is non-inclusive of the index.
func (dst Bitmap) CountTo(until uint32) int {
if len(dst) == 0 {
return 0
}
// Figure out the index of the last block
blkUntil := int(until >> 6)
bitUntil := int(until % 64)
if blkUntil >= len(dst) {
blkUntil = len(dst) - 1
}
// Count the bits right before the last block
sum := dst[:blkUntil].Count()
// Count the bits at the end
sum += bits.OnesCount64(dst[blkUntil] << (64 - uint64(bitUntil)))
return sum
}
// Grow grows the bitmap size until we reach the desired bit.
func (dst *Bitmap) Grow(desiredBit uint32) {
dst.grow(int(desiredBit >> 6))
}
// grow grows the size of the bitmap until we reach the desired block offset
func (dst *Bitmap) grow(blkAt int) {
if len(*dst) > blkAt {
return
}
// If there's space, resize the slice without copying.
if cap(*dst) > blkAt {
*dst = (*dst)[:blkAt+1]
return
}
old := *dst
*dst = make(Bitmap, blkAt+1, resize(cap(old), blkAt+1))
copy(*dst, old)
}
// shrink shrinks the size of the bitmap and resets to zero
func (dst *Bitmap) shrink(length int) {
until := len(*dst)
for i := length; i < until; i++ {
(*dst)[i] = 0
}
// Trim without reallocating
*dst = (*dst)[:length]
}
// minlen calculates the minimum length of all of the bitmaps
func minlen(a, b Bitmap, extra []Bitmap) int {
size := minint(len(a), len(b))
for _, v := range extra {
if m := minint(len(a), len(v)); m < size {
size = m
}
}
return size
}
// maxlen calculates the maximum length of all of the bitmaps
func maxlen(a, b Bitmap, extra []Bitmap) int {
size := maxint(len(a), len(b))
for _, v := range extra {
if m := maxint(len(a), len(v)); m > size {
size = m
}
}
return size
}
// maxint returns a maximum of two integers without branches.
func maxint(v1, v2 int) int {
return v1 - ((v1 - v2) & ((v1 - v2) >> 31))
}
// minint returns a minimum of two integers without branches.
func minint(v1, v2 int) int {
return v2 + ((v1 - v2) & ((v1 - v2) >> 31))
}
// resize calculates the new required capacity and a new index
func resize(capacity, v int) int {
const threshold = 256
if v < threshold {
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
v++
return int(v)
}
if capacity < threshold {
capacity = threshold
}
for 0 < capacity && capacity < (v+1) {
capacity += (capacity + 3*threshold) / 4
}
return capacity
}
// dimensionsOf returns a uint64 containing the packed dimensions
func dimensionsOf(n, m int) uint64 {
return uint64(n) | (uint64(m) << 32)
}
// pointersOf returns a pointer to an array containing pointers to the
// first element of each bitmap and the maximum length of all bitmaps
func pointersOf(other Bitmap, extra []Bitmap) (unsafe.Pointer, int) {
out := make([]unsafe.Pointer, len(extra)+1)
out[0] = unsafe.Pointer(&other[0])
max := 0
for i := range extra {
out[i+1] = unsafe.Pointer(&extra[i][0])
if len(extra[i]) > max {
max = len(extra[i])
}
}
return unsafe.Pointer(&out[0]), max
}
func location(x uint32) (int, int) {
blkAt := int(x >> 6)
bitAt := int(x & uint32(63))
return blkAt, bitAt
}