-
Notifications
You must be signed in to change notification settings - Fork 0
/
bitops.go
161 lines (139 loc) · 3.71 KB
/
bitops.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
package bitstring
import (
"math"
"unsafe"
)
const wordsize = 32 << (^uint(0) >> 63) // 32 or 64
// bitmask returns a mask where only the nth bit of a word is set.
func bitmask(n uint64) uint64 { return 1 << n }
// wordoffset returns, for a given bit n of a bit string, the offset
// of the word that contains bit n.
func wordoffset(n uint64) uint64 { return n / 64 }
// bitoffset returns, for a given bit n of a bit string, the offset of that bit
// with respect to the first bit of the word that contains it.
func bitoffset(n uint64) uint64 { return n & (64 - 1) }
// mask returns a mask that keeps the bits in the range [l, h) behavior
// undefined if any argument is greater than the size of a machine word.
func mask(l, h uint64) uint64 { return lomask(h) & himask(l) }
// lomask returns a mask to keep the n LSB (least significant bits). Undefined
// behavior if n is greater than 64.
func lomask(n uint64) uint64 { return math.MaxUint64 >> (64 - n) }
// himask returns a mask to keep the n MSB (most significant bits). Undefined
// behavior if n is greater than 64.
func himask(n uint64) uint64 { return math.MaxUint64 << n }
// transferbits returns the word that results from transferring some bits from
// src to dst, where set bits in mask specify the bits to transfer.
func transferbits(dst, src, mask uint64) uint64 {
return dst&^mask | src&mask
}
// lsb returns the offset of the lowest significant set bit in v. That is, the
// index of the rightmost 1.
//
// Note: lsb(0) is meaningless, it's the caller responsibility to not use the
// result of lsb(0).
func lsb(v uint64) uint64 {
var num uint64
if (v & 0xffffffff) == 0 {
num += 32
v >>= 32
}
if (v & 0xffff) == 0 {
num += 16
v >>= 16
}
if (v & 0xff) == 0 {
num += 8
v >>= 8
}
if (v & 0xf) == 0 {
num += 4
v >>= 4
}
if (v & 0x3) == 0 {
num += 2
v >>= 2
}
if (v & 0x1) == 0 {
num++
}
return num
}
// msb returns the offset of the most significant set bit in v. That is, the
// index of the leftmost 1.
//
// Note: msb(0) is meaningless, it's the caller responsibility to not use the
// result of msb(0).
func msb(v uint64) uint64 {
var num uint64
if (v & 0xffffffff00000000) != 0 {
num += 32
v >>= 32
}
if (v & 0xffff0000) != 0 {
num += 16
v >>= 16
}
if (v & 0xff00) != 0 {
num += 8
v >>= 8
}
if (v & 0xf0) != 0 {
num += 4
v >>= 4
}
if (v & 0xc) != 0 {
num += 2
v >>= 2
}
if (v & 0x2) != 0 {
num++
v >>= 1
}
return num
}
// fastmsbLittleEndian is faster version of msb that only works on little endian
// architectures. About 50% faster than msb on amd64. Rely on the fact that Go
// uses IEEE 754 floating point representation. Converts v to float64, then
// extracts the exponent bits of the IEEE754 representation.
func fastmsbLittleEndian(v uint64) uint64 {
if v == math.MaxUint64 {
return 63
}
f := float64(v)
arr := *(*[2]uint32)(unsafe.Pointer(&f))
return uint64(arr[1]>>20 - 1023)
}
func reverseBytes(buf []byte) []byte {
for i := 0; i < len(buf)/2; i++ {
buf[i], buf[len(buf)-i-1] = buf[len(buf)-i-1], buf[i]
}
return buf
}
// shifts all words of n bits to the right. invariant: 0 <= off <= 64.
func rightShiftBits(words []uint64, n uint64) {
shift := 64 - n
mask := lomask(n)
prev := uint64(0) // bits from previous word
for i := len(words) - 1; i >= 0; i-- {
save := (words[i] & mask) << shift
words[i] >>= n
words[i] |= prev
prev = save
}
}
// if n is a power of 2, ispow2 returns (v, true) such that (1<<v) gives n, or
// (0, false) if n is not a power of 2.
//
// panics if n == 0
func ispow2(n uint64) (uint64, bool) {
if (n & -n) != n {
// n is not a power of 2
return 0, false
}
for i := uint64(0); i < 64; i++ {
if n == 1<<i {
return i, true
}
}
panic("unreachable")
}