This is an automated email from the ASF dual-hosted git repository.
zeroshade pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-go.git
The following commit(s) were added to refs/heads/main by this push:
new c0d4c354 perf(bitutil): add ARM64 NEON bitmap operations (#1264)
c0d4c354 is described below
commit c0d4c35489b3de934f0ce30f5de5a387a09402d6
Author: Minh Vu <[email protected]>
AuthorDate: Wed Sep 2 19:05:12 2026 +0200
perf(bitutil): add ARM64 NEON bitmap operations (#1264)
This adds an ARM64 NEON fast path for aligned bitmap operations.
**What changed**
- Add NEON implementations for AND, OR, ANDNOT, XOR, and XNOR.
- Process 64 bytes per vector loop and keep scalar tails.
- Use the SIMD path only when ARM64 ASIMD is available.
- Keep the existing fallbacks for noasm and other architectures.
- Add aligned, unaligned, tail, and large-input correctness coverage.
- Add benchmarks for all five operations.
**Benchmark**
- **Machine:** Apple M1 Pro, arm64
- **Go:** 1.26.3
- **Method:** median of 5 runs, scalar `-tags noasm` compared with the
default NEON path
- **Command:** `go test -run '^$' -bench
'^BenchmarkBitmapAlignedOps/(32768|131072)/(and|or|and-not|xor|xnor)$'
-benchmem -benchtime=300ms -count=5 ./arrow/bitutil`
- **Lower is better:** values are ns/op
| Size | Operation | Scalar | NEON | Speedup |
| --- | --- | ---: | ---: | ---: |
| 32 KiB | AND | 2,000 | 689 | 2.9x |
| 32 KiB | OR | 2,001 | 744 | 2.7x |
| 32 KiB | ANDNOT | 2,020 | 741 | 2.7x |
| 32 KiB | XOR | 2,012 | 741 | 2.7x |
| 32 KiB | XNOR | 2,009 | 793 | 2.5x |
| 128 KiB | AND | 8,051 | 3,652 | 2.2x |
| 128 KiB | OR | 8,093 | 3,602 | 2.2x |
| 128 KiB | ANDNOT | 8,041 | 3,670 | 2.2x |
| 128 KiB | XOR | 8,039 | 3,643 | 2.2x |
| 128 KiB | XNOR | 8,118 | 3,630 | 2.2x |
Both paths use zero allocations.
**Checks**
- `go test -count=1 ./arrow/bitutil`
- `go test -count=1 -tags noasm ./arrow/bitutil`
- `go test -race -count=1 ./arrow/bitutil`
- `go test -count=1 ./arrow/compute/...`
- `go vet -composites=false ./arrow/bitutil`
- Linux amd64 and arm64 test-package cross-builds
---
arrow/bitutil/bitmap_ops_arm64.go | 99 ++++++++-
arrow/bitutil/bitmap_ops_benchmark_test.go | 54 +++++
arrow/bitutil/bitmap_ops_neon_arm64.s | 271 +++++++++++++++++++++++++
arrow/bitutil/bitmap_ops_overlap_arm64_test.go | 86 ++++++++
arrow/bitutil/bitmaps.go | 2 +-
arrow/bitutil/bitmaps_test.go | 113 +++++++++++
6 files changed, 618 insertions(+), 7 deletions(-)
diff --git a/arrow/bitutil/bitmap_ops_arm64.go
b/arrow/bitutil/bitmap_ops_arm64.go
index 28d95d84..fdfc54f7 100644
--- a/arrow/bitutil/bitmap_ops_arm64.go
+++ b/arrow/bitutil/bitmap_ops_arm64.go
@@ -14,14 +14,101 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-//go:build !noasm
-// +build !noasm
+//go:build !noasm && !appengine
+// +build !noasm,!appengine
package bitutil
+import (
+ "unsafe"
+
+ "golang.org/x/sys/cpu"
+)
+
+//go:noescape
+func _bitmap_aligned_and_neon(left, right, out unsafe.Pointer, length int64)
+
+//go:noescape
+func _bitmap_aligned_or_neon(left, right, out unsafe.Pointer, length int64)
+
+//go:noescape
+func _bitmap_aligned_and_not_neon(left, right, out unsafe.Pointer, length
int64)
+
+//go:noescape
+func _bitmap_aligned_xor_neon(left, right, out unsafe.Pointer, length int64)
+
+//go:noescape
+func _bitmap_aligned_xnor_neon(left, right, out unsafe.Pointer, length int64)
+
+func bitmapSlicesOverlap(left, right []byte) bool {
+ if len(left) == 0 || len(right) == 0 {
+ return false
+ }
+
+ leftStart := uintptr(unsafe.Pointer(&left[0]))
+ rightStart := uintptr(unsafe.Pointer(&right[0]))
+ if leftStart < rightStart {
+ return rightStart-leftStart < uintptr(len(left))
+ }
+ return leftStart-rightStart < uintptr(len(right))
+}
+
+func bitmapAlignedNEONHasOverlap(left, right, out []byte) bool {
+ return bitmapSlicesOverlap(left, out) || bitmapSlicesOverlap(right, out)
+}
+
+func bitmapAlignedAndNEON(left, right, out []byte) {
+ if bitmapAlignedNEONHasOverlap(left, right, out) {
+ alignedBitAndGo(left, right, out)
+ return
+ }
+ _bitmap_aligned_and_neon(unsafe.Pointer(&left[0]),
unsafe.Pointer(&right[0]), unsafe.Pointer(&out[0]), int64(len(out)))
+}
+
+func bitmapAlignedOrNEON(left, right, out []byte) {
+ if bitmapAlignedNEONHasOverlap(left, right, out) {
+ alignedBitOrGo(left, right, out)
+ return
+ }
+ _bitmap_aligned_or_neon(unsafe.Pointer(&left[0]),
unsafe.Pointer(&right[0]), unsafe.Pointer(&out[0]), int64(len(out)))
+}
+
+func bitmapAlignedAndNotNEON(left, right, out []byte) {
+ if bitmapAlignedNEONHasOverlap(left, right, out) {
+ alignedBitAndNotGo(left, right, out)
+ return
+ }
+ _bitmap_aligned_and_not_neon(unsafe.Pointer(&left[0]),
unsafe.Pointer(&right[0]), unsafe.Pointer(&out[0]), int64(len(out)))
+}
+
+func bitmapAlignedXorNEON(left, right, out []byte) {
+ if bitmapAlignedNEONHasOverlap(left, right, out) {
+ alignedBitXorGo(left, right, out)
+ return
+ }
+ _bitmap_aligned_xor_neon(unsafe.Pointer(&left[0]),
unsafe.Pointer(&right[0]), unsafe.Pointer(&out[0]), int64(len(out)))
+}
+
+func bitmapAlignedXnorNEON(left, right, out []byte) {
+ if bitmapAlignedNEONHasOverlap(left, right, out) {
+ alignedBitXnorGo(left, right, out)
+ return
+ }
+ _bitmap_aligned_xnor_neon(unsafe.Pointer(&left[0]),
unsafe.Pointer(&right[0]), unsafe.Pointer(&out[0]), int64(len(out)))
+}
+
func init() {
- bitAndOp.opAligned = alignedBitAndGo
- bitOrOp.opAligned = alignedBitOrGo
- bitAndNotOp.opAligned = alignedBitAndNotGo
- bitXorOp.opAligned = alignedBitXorGo
+ if cpu.ARM64.HasASIMD {
+ bitAndOp.opAligned = bitmapAlignedAndNEON
+ bitOrOp.opAligned = bitmapAlignedOrNEON
+ bitAndNotOp.opAligned = bitmapAlignedAndNotNEON
+ bitXorOp.opAligned = bitmapAlignedXorNEON
+ bitXnorOp.opAligned = bitmapAlignedXnorNEON
+ } else {
+ bitAndOp.opAligned = alignedBitAndGo
+ bitOrOp.opAligned = alignedBitOrGo
+ bitAndNotOp.opAligned = alignedBitAndNotGo
+ bitXorOp.opAligned = alignedBitXorGo
+ bitXnorOp.opAligned = alignedBitXnorGo
+ }
}
diff --git a/arrow/bitutil/bitmap_ops_benchmark_test.go
b/arrow/bitutil/bitmap_ops_benchmark_test.go
new file mode 100644
index 00000000..0588c2be
--- /dev/null
+++ b/arrow/bitutil/bitmap_ops_benchmark_test.go
@@ -0,0 +1,54 @@
+// 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 bitutil_test
+
+import (
+ "strconv"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+)
+
+func BenchmarkBitmapAlignedOps(b *testing.B) {
+ for _, nbytes := range []int{8, 32, 64, 128, 1024, bufferSize * 4,
bufferSize * 16} {
+ b.Run(strconv.Itoa(nbytes), func(b *testing.B) {
+ left := randomBuffer(int64(nbytes))
+ right := randomBuffer(int64(nbytes))
+ out := make([]byte, nbytes)
+ length := int64(nbytes * 8)
+
+ for _, op := range []struct {
+ name string
+ fn noAllocFn
+ }{
+ {name: "and", fn: bitutil.BitmapAnd},
+ {name: "or", fn: bitutil.BitmapOr},
+ {name: "and-not", fn: bitutil.BitmapAndNot},
+ {name: "xor", fn: bitutil.BitmapXor},
+ {name: "xnor", fn: bitutil.BitmapXnor},
+ } {
+ b.Run(op.name, func(b *testing.B) {
+ b.SetBytes(int64(2 * nbytes))
+ b.ReportAllocs()
+ for i := 0; i < b.N; i++ {
+ op.fn(left, right, 0, 0, out,
0, length)
+ }
+ })
+ }
+ })
+ }
+}
diff --git a/arrow/bitutil/bitmap_ops_neon_arm64.s
b/arrow/bitutil/bitmap_ops_neon_arm64.s
new file mode 100644
index 00000000..8370f65f
--- /dev/null
+++ b/arrow/bitutil/bitmap_ops_neon_arm64.s
@@ -0,0 +1,271 @@
+//go:build !noasm && !appengine
+// +build !noasm,!appengine
+
+// 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.
+
+TEXT ·_bitmap_aligned_and_neon(SB), $0-32
+ MOVD left+0(FP), R0
+ MOVD right+8(FP), R1
+ MOVD out+16(FP), R2
+ MOVD length+24(FP), R3
+
+and_loop:
+ CMP $64, R3
+ BLO and_tail
+ VLD1.P 64(R0), [V0.B16, V1.B16, V2.B16, V3.B16]
+ VLD1.P 64(R1), [V4.B16, V5.B16, V6.B16, V7.B16]
+ VAND V0.B16, V4.B16, V0.B16
+ VAND V1.B16, V5.B16, V1.B16
+ VAND V2.B16, V6.B16, V2.B16
+ VAND V3.B16, V7.B16, V3.B16
+ VST1.P [V0.B16, V1.B16, V2.B16, V3.B16], 64(R2)
+ SUB $64, R3
+ B and_loop
+
+and_tail:
+ CMP $8, R3
+ BLO and_byte_tail
+ MOVD (R0), R4
+ MOVD (R1), R5
+ AND R5, R4, R4
+ MOVD R4, (R2)
+ ADD $8, R0
+ ADD $8, R1
+ ADD $8, R2
+ SUB $8, R3
+ B and_tail
+
+and_byte_tail:
+ CBZ R3, and_done
+
+and_tail_loop:
+ MOVBU (R0), R4
+ MOVBU (R1), R5
+ AND R5, R4, R4
+ MOVB R4, (R2)
+ ADD $1, R0
+ ADD $1, R1
+ ADD $1, R2
+ SUBS $1, R3
+ BNE and_tail_loop
+
+and_done:
+ RET
+
+TEXT ·_bitmap_aligned_or_neon(SB), $0-32
+ MOVD left+0(FP), R0
+ MOVD right+8(FP), R1
+ MOVD out+16(FP), R2
+ MOVD length+24(FP), R3
+
+or_loop:
+ CMP $64, R3
+ BLO or_tail
+ VLD1.P 64(R0), [V0.B16, V1.B16, V2.B16, V3.B16]
+ VLD1.P 64(R1), [V4.B16, V5.B16, V6.B16, V7.B16]
+ VORR V0.B16, V4.B16, V0.B16
+ VORR V1.B16, V5.B16, V1.B16
+ VORR V2.B16, V6.B16, V2.B16
+ VORR V3.B16, V7.B16, V3.B16
+ VST1.P [V0.B16, V1.B16, V2.B16, V3.B16], 64(R2)
+ SUB $64, R3
+ B or_loop
+
+or_tail:
+ CMP $8, R3
+ BLO or_byte_tail
+ MOVD (R0), R4
+ MOVD (R1), R5
+ ORR R5, R4, R4
+ MOVD R4, (R2)
+ ADD $8, R0
+ ADD $8, R1
+ ADD $8, R2
+ SUB $8, R3
+ B or_tail
+
+or_byte_tail:
+ CBZ R3, or_done
+
+or_tail_loop:
+ MOVBU (R0), R4
+ MOVBU (R1), R5
+ ORR R5, R4, R4
+ MOVB R4, (R2)
+ ADD $1, R0
+ ADD $1, R1
+ ADD $1, R2
+ SUBS $1, R3
+ BNE or_tail_loop
+
+or_done:
+ RET
+
+TEXT ·_bitmap_aligned_and_not_neon(SB), $0-32
+ MOVD left+0(FP), R0
+ MOVD right+8(FP), R1
+ MOVD out+16(FP), R2
+ MOVD length+24(FP), R3
+ VEOR V31.B16, V31.B16, V31.B16
+
+and_not_loop:
+ CMP $64, R3
+ BLO and_not_tail
+ VLD1.P 64(R0), [V0.B16, V1.B16, V2.B16, V3.B16]
+ VLD1.P 64(R1), [V4.B16, V5.B16, V6.B16, V7.B16]
+ VBSL V0.B16, V31.B16, V4.B16
+ VBSL V1.B16, V31.B16, V5.B16
+ VBSL V2.B16, V31.B16, V6.B16
+ VBSL V3.B16, V31.B16, V7.B16
+ VST1.P [V4.B16, V5.B16, V6.B16, V7.B16], 64(R2)
+ SUB $64, R3
+ B and_not_loop
+
+and_not_tail:
+ CMP $8, R3
+ BLO and_not_byte_tail
+ MOVD (R0), R4
+ MOVD (R1), R5
+ BIC R5, R4, R4
+ MOVD R4, (R2)
+ ADD $8, R0
+ ADD $8, R1
+ ADD $8, R2
+ SUB $8, R3
+ B and_not_tail
+
+and_not_byte_tail:
+ CBZ R3, and_not_done
+
+and_not_tail_loop:
+ MOVBU (R0), R4
+ MOVBU (R1), R5
+ BIC R5, R4, R4
+ MOVB R4, (R2)
+ ADD $1, R0
+ ADD $1, R1
+ ADD $1, R2
+ SUBS $1, R3
+ BNE and_not_tail_loop
+
+and_not_done:
+ RET
+
+TEXT ·_bitmap_aligned_xor_neon(SB), $0-32
+ MOVD left+0(FP), R0
+ MOVD right+8(FP), R1
+ MOVD out+16(FP), R2
+ MOVD length+24(FP), R3
+
+xor_loop:
+ CMP $64, R3
+ BLO xor_tail
+ VLD1.P 64(R0), [V0.B16, V1.B16, V2.B16, V3.B16]
+ VLD1.P 64(R1), [V4.B16, V5.B16, V6.B16, V7.B16]
+ VEOR V0.B16, V4.B16, V0.B16
+ VEOR V1.B16, V5.B16, V1.B16
+ VEOR V2.B16, V6.B16, V2.B16
+ VEOR V3.B16, V7.B16, V3.B16
+ VST1.P [V0.B16, V1.B16, V2.B16, V3.B16], 64(R2)
+ SUB $64, R3
+ B xor_loop
+
+xor_tail:
+ CMP $8, R3
+ BLO xor_byte_tail
+ MOVD (R0), R4
+ MOVD (R1), R5
+ EOR R5, R4, R4
+ MOVD R4, (R2)
+ ADD $8, R0
+ ADD $8, R1
+ ADD $8, R2
+ SUB $8, R3
+ B xor_tail
+
+xor_byte_tail:
+ CBZ R3, xor_done
+
+xor_tail_loop:
+ MOVBU (R0), R4
+ MOVBU (R1), R5
+ EOR R5, R4, R4
+ MOVB R4, (R2)
+ ADD $1, R0
+ ADD $1, R1
+ ADD $1, R2
+ SUBS $1, R3
+ BNE xor_tail_loop
+
+xor_done:
+ RET
+
+TEXT ·_bitmap_aligned_xnor_neon(SB), $0-32
+ MOVD left+0(FP), R0
+ MOVD right+8(FP), R1
+ MOVD out+16(FP), R2
+ MOVD length+24(FP), R3
+ VMOVI $0xff, V31.B16
+
+xnor_loop:
+ CMP $64, R3
+ BLO xnor_tail
+ VLD1.P 64(R0), [V0.B16, V1.B16, V2.B16, V3.B16]
+ VLD1.P 64(R1), [V4.B16, V5.B16, V6.B16, V7.B16]
+ VEOR V0.B16, V4.B16, V0.B16
+ VEOR V31.B16, V0.B16, V0.B16
+ VEOR V1.B16, V5.B16, V1.B16
+ VEOR V31.B16, V1.B16, V1.B16
+ VEOR V2.B16, V6.B16, V2.B16
+ VEOR V31.B16, V2.B16, V2.B16
+ VEOR V3.B16, V7.B16, V3.B16
+ VEOR V31.B16, V3.B16, V3.B16
+ VST1.P [V0.B16, V1.B16, V2.B16, V3.B16], 64(R2)
+ SUB $64, R3
+ B xnor_loop
+
+xnor_tail:
+ CMP $8, R3
+ BLO xnor_byte_tail
+ MOVD (R0), R4
+ MOVD (R1), R5
+ EOR R5, R4, R4
+ MVN R4, R4
+ MOVD R4, (R2)
+ ADD $8, R0
+ ADD $8, R1
+ ADD $8, R2
+ SUB $8, R3
+ B xnor_tail
+
+xnor_byte_tail:
+ CBZ R3, xnor_done
+
+xnor_tail_loop:
+ MOVBU (R0), R4
+ MOVBU (R1), R5
+ EOR R5, R4, R4
+ MVN R4, R4
+ MOVB R4, (R2)
+ ADD $1, R0
+ ADD $1, R1
+ ADD $1, R2
+ SUBS $1, R3
+ BNE xnor_tail_loop
+
+xnor_done:
+ RET
diff --git a/arrow/bitutil/bitmap_ops_overlap_arm64_test.go
b/arrow/bitutil/bitmap_ops_overlap_arm64_test.go
new file mode 100644
index 00000000..b22dc53d
--- /dev/null
+++ b/arrow/bitutil/bitmap_ops_overlap_arm64_test.go
@@ -0,0 +1,86 @@
+// 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.
+
+//go:build arm64
+// +build arm64
+
+package bitutil_test
+
+import (
+ "math/rand"
+ "testing"
+
+ "github.com/apache/arrow-go/v18/arrow/bitutil"
+ "github.com/stretchr/testify/assert"
+)
+
+func TestBitmapOpsPartialOverlap(t *testing.T) {
+ const nbytes = 256
+
+ rng := rand.New(rand.NewSource(18))
+ leftInput := make([]byte, nbytes)
+ rightInput := make([]byte, nbytes)
+ _, _ = rng.Read(leftInput)
+ _, _ = rng.Read(rightInput)
+
+ for _, op := range []struct {
+ name string
+ fn noAllocFn
+ want func(byte, byte) byte
+ }{
+ {name: "and", fn: bitutil.BitmapAnd, want: func(left, right
byte) byte { return left & right }},
+ {name: "or", fn: bitutil.BitmapOr, want: func(left, right byte)
byte { return left | right }},
+ {name: "and-not", fn: bitutil.BitmapAndNot, want: func(left,
right byte) byte { return left &^ right }},
+ {name: "xor", fn: bitutil.BitmapXor, want: func(left, right
byte) byte { return left ^ right }},
+ {name: "xnor", fn: bitutil.BitmapXnor, want: func(left, right
byte) byte { return ^(left ^ right) }},
+ } {
+ for _, input := range []string{"left", "right"} {
+ t.Run(op.name+"/"+input, func(t *testing.T) {
+ backing := make([]byte, nbytes+1)
+ _, _ = rng.Read(backing)
+ wantBacking := append([]byte(nil), backing...)
+ left, right := append([]byte(nil),
leftInput...), append([]byte(nil), rightInput...)
+ wantLeft, wantRight := left, right
+ if input == "left" {
+ left = backing[:nbytes]
+ wantLeft = wantBacking[:nbytes]
+ } else {
+ right = backing[:nbytes]
+ wantRight = wantBacking[:nbytes]
+ }
+
+ wantOut := wantBacking[1:]
+ wantOut[0] = op.want(wantLeft[0], wantRight[0])
+ wordEnd := 1 + (len(wantOut)-2)/8*8
+ for i := 1; i < wordEnd; i += 8 {
+ end := i + 8
+ var expected [8]byte
+ for j := i; j < end; j++ {
+ expected[j-i] =
op.want(wantLeft[j], wantRight[j])
+ }
+ copy(wantOut[i:end], expected[:end-i])
+ }
+ for i := wordEnd; i < len(wantOut)-1; i++ {
+ wantOut[i] = op.want(wantLeft[i],
wantRight[i])
+ }
+ wantOut[len(wantOut)-1] =
op.want(wantLeft[len(wantOut)-1], wantRight[len(wantOut)-1])
+
+ op.fn(left, right, 0, 0, backing[1:], 0,
nbytes*8)
+ assert.Equal(t, wantBacking, backing)
+ })
+ }
+ }
+}
diff --git a/arrow/bitutil/bitmaps.go b/arrow/bitutil/bitmaps.go
index eb8cf908..c4cef33a 100644
--- a/arrow/bitutil/bitmaps.go
+++ b/arrow/bitutil/bitmaps.go
@@ -532,7 +532,7 @@ func alignedBitmapOp(op bitOp, left, right []byte, lOffset,
rOffset int64, out [
left = left[lOffset/8:]
right = right[rOffset/8:]
out = out[outOffset/8:]
- endMask := (lOffset + length%8)
+ endMask := (lOffset + length) % 8
switch nbytes {
case 0:
return
diff --git a/arrow/bitutil/bitmaps_test.go b/arrow/bitutil/bitmaps_test.go
index 3d76f105..0f836837 100644
--- a/arrow/bitutil/bitmaps_test.go
+++ b/arrow/bitutil/bitmaps_test.go
@@ -517,6 +517,42 @@ func (s *BitmapOpSuite) TestBitmapOr() {
})
}
+func (s *BitmapOpSuite) TestBitmapAndNot() {
+ op := bitmapOp{
+ noAlloc: bitutil.BitmapAndNot,
+ alloc: bitutil.BitmapAndNotAlloc,
+ }
+
+ leftBits := []int{0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1}
+ rightBits := []int{0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0}
+ resultBits := []bool{false, true, false, true, false, false, false,
true, false, false, false, true, false, true}
+
+ s.Run("aligned", func() {
+ s.testAligned(op, leftBits, rightBits, resultBits)
+ })
+ s.Run("unaligned", func() {
+ s.testUnaligned(op, leftBits, rightBits, resultBits)
+ })
+}
+
+func (s *BitmapOpSuite) TestBitmapXor() {
+ op := bitmapOp{
+ noAlloc: bitutil.BitmapXor,
+ alloc: bitutil.BitmapXorAlloc,
+ }
+
+ leftBits := []int{0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1}
+ rightBits := []int{0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0}
+ resultBits := []bool{false, true, false, true, true, true, false, true,
true, false, true, true, true, true}
+
+ s.Run("aligned", func() {
+ s.testAligned(op, leftBits, rightBits, resultBits)
+ })
+ s.Run("unaligned", func() {
+ s.testUnaligned(op, leftBits, rightBits, resultBits)
+ })
+}
+
func (s *BitmapOpSuite) TestBitmapXnor() {
op := bitmapOp{
noAlloc: bitutil.BitmapXnor,
@@ -555,6 +591,39 @@ func TestSmallBitmapOp(t *testing.T) {
assert.Equal(t, results, out)
}
+func TestBitmapOpsLargeAligned(t *testing.T) {
+ const nbytes = 257
+
+ rng := rand.New(rand.NewSource(0))
+ left := make([]byte, nbytes)
+ right := make([]byte, nbytes)
+ _, _ = rng.Read(left)
+ _, _ = rng.Read(right)
+
+ for _, op := range []struct {
+ name string
+ fn noAllocFn
+ want func(byte, byte) byte
+ }{
+ {name: "and", fn: bitutil.BitmapAnd, want: func(left, right
byte) byte { return left & right }},
+ {name: "or", fn: bitutil.BitmapOr, want: func(left, right byte)
byte { return left | right }},
+ {name: "and-not", fn: bitutil.BitmapAndNot, want: func(left,
right byte) byte { return left &^ right }},
+ {name: "xor", fn: bitutil.BitmapXor, want: func(left, right
byte) byte { return left ^ right }},
+ {name: "xnor", fn: bitutil.BitmapXnor, want: func(left, right
byte) byte { return ^(left ^ right) }},
+ } {
+ t.Run(op.name, func(t *testing.T) {
+ out := make([]byte, nbytes)
+ op.fn(left, right, 0, 0, out, 0, nbytes*8)
+
+ expected := make([]byte, nbytes)
+ for i := range expected {
+ expected[i] = op.want(left[i], right[i])
+ }
+ assert.Equal(t, expected, out)
+ })
+ }
+}
+
func createRandomBuffer(mem memory.Allocator, src *rand.Rand, nbytes int)
[]byte {
buf := mem.Allocate(nbytes)
src.Read(buf)
@@ -726,3 +795,47 @@ func TestBitmapWriterAppendBitmapLarge(t *testing.T) {
assert.Equal(t, expected, actual, "bit mismatch at position
%d", i)
}
}
+
+func TestBitmapOpsBoundaries(t *testing.T) {
+ rng := rand.New(rand.NewSource(17))
+ left, right := make([]byte, 260), make([]byte, 260)
+ _, _ = rng.Read(left)
+ _, _ = rng.Read(right)
+ for _, op := range []struct {
+ name string
+ fn noAllocFn
+ want func(bool, bool) bool
+ }{
+ {"and", bitutil.BitmapAnd, func(l, r bool) bool { return l && r
}},
+ {"or", bitutil.BitmapOr, func(l, r bool) bool { return l || r
}},
+ {"and-not", bitutil.BitmapAndNot, func(l, r bool) bool { return
l && !r }},
+ {"xor", bitutil.BitmapXor, func(l, r bool) bool { return l != r
}},
+ {"xnor", bitutil.BitmapXnor, func(l, r bool) bool { return l ==
r }},
+ } {
+ t.Run(op.name, func(t *testing.T) {
+ for _, length := range []int{0, 1, 7, 8, 9, 15, 16, 17,
24, 32, 56, 64, 72, 120, 128, 136, 504, 512, 520, 528, 536, 1016, 1024, 1032,
1040, 2056} {
+ for _, offset := range []int{0, 1, 7, 8, 15} {
+ for _, alias := range []string{"none",
"left", "right"} {
+ l, r := append([]byte(nil),
left...), append([]byte(nil), right...)
+ out := make([]byte, len(left))
+ for i := range out {
+ out[i] = 0xa5
+ }
+ switch alias {
+ case "left":
+ out = l
+ case "right":
+ out = r
+ }
+ expected := append([]byte(nil),
out...)
+ for i := offset; i <
offset+length; i++ {
+
bitutil.SetBitTo(expected, i, op.want(bitutil.BitIsSet(left, i),
bitutil.BitIsSet(right, i)))
+ }
+ op.fn(l, r, int64(offset),
int64(offset), out, int64(offset), int64(length))
+ assert.Equal(t, expected, out,
"length=%d offset=%d alias=%s", length, offset, alias)
+ }
+ }
+ }
+ })
+ }
+}
