-
Notifications
You must be signed in to change notification settings - Fork 3.4k
/
bitmap_generate.go
109 lines (98 loc) · 2.7 KB
/
bitmap_generate.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
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements. See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership. The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package bitutils
import "github.com/apache/arrow/go/v14/arrow/bitutil"
// GenerateBits writes sequential bits to a bitmap. Bits preceding the
// initial start offset are preserved, bits following the bitmap may
// get clobbered.
func GenerateBits(bitmap []byte, start, length int64, g func() bool) {
if length == 0 {
return
}
cur := bitmap[start/8:]
mask := bitutil.BitMask[start%8]
curbyte := cur[0] & bitutil.PrecedingBitmask[start%8]
for i := int64(0); i < length; i++ {
bit := g()
if bit {
curbyte = curbyte | mask
}
mask <<= 1
if mask == 0 {
mask = 1
cur[0] = curbyte
cur = cur[1:]
curbyte = 0
}
}
if mask != 1 {
cur[0] = curbyte
}
}
// GenerateBitsUnrolled is like GenerateBits but unrolls its main loop for
// higher performance.
//
// See the benchmarks for evidence.
func GenerateBitsUnrolled(bitmap []byte, start, length int64, g func() bool) {
if length == 0 {
return
}
var (
curbyte byte
cur = bitmap[start/8:]
startBitOffset uint64 = uint64(start % 8)
mask = bitutil.BitMask[startBitOffset]
remaining = length
)
if mask != 0x01 {
curbyte = cur[0] & bitutil.PrecedingBitmask[startBitOffset]
for mask != 0 && remaining > 0 {
if g() {
curbyte |= mask
}
mask <<= 1
remaining--
}
cur[0] = curbyte
cur = cur[1:]
}
var outResults [8]byte
for remainingBytes := remaining / 8; remainingBytes > 0; remainingBytes-- {
for i := 0; i < 8; i++ {
if g() {
outResults[i] = 1
} else {
outResults[i] = 0
}
}
cur[0] = (outResults[0] | outResults[1]<<1 | outResults[2]<<2 |
outResults[3]<<3 | outResults[4]<<4 | outResults[5]<<5 |
outResults[6]<<6 | outResults[7]<<7)
cur = cur[1:]
}
remainingBits := remaining % 8
if remainingBits > 0 {
curbyte = 0
mask = 0x01
for ; remainingBits > 0; remainingBits-- {
if g() {
curbyte |= mask
}
mask <<= 1
}
cur[0] = curbyte
}
}