summaryrefslogtreecommitdiffhomepage
path: root/pkg/bits
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/bits')
-rw-r--r--pkg/bits/BUILD55
-rw-r--r--pkg/bits/bits.go16
-rw-r--r--pkg/bits/bits_template.go44
-rw-r--r--pkg/bits/uint64_arch_amd64.go36
-rw-r--r--pkg/bits/uint64_arch_amd64_asm.s31
-rw-r--r--pkg/bits/uint64_arch_generic.go55
-rw-r--r--pkg/bits/uint64_test.go116
7 files changed, 353 insertions, 0 deletions
diff --git a/pkg/bits/BUILD b/pkg/bits/BUILD
new file mode 100644
index 000000000..9897e5dc3
--- /dev/null
+++ b/pkg/bits/BUILD
@@ -0,0 +1,55 @@
+package(licenses = ["notice"]) # Apache 2.0
+
+load("@io_bazel_rules_go//go:def.bzl", "go_library", "go_test")
+load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance")
+
+go_library(
+ name = "bits",
+ srcs = [
+ "bits.go",
+ "bits32.go",
+ "bits64.go",
+ "uint64_arch_amd64.go",
+ "uint64_arch_amd64_asm.s",
+ "uint64_arch_generic.go",
+ ],
+ importpath = "gvisor.googlesource.com/gvisor/pkg/bits",
+ visibility = ["//:sandbox"],
+)
+
+go_template(
+ name = "bits_template",
+ srcs = ["bits_template.go"],
+ types = [
+ "T",
+ ],
+)
+
+go_template_instance(
+ name = "bits64",
+ out = "bits64.go",
+ package = "bits",
+ suffix = "64",
+ template = ":bits_template",
+ types = {
+ "T": "uint64",
+ },
+)
+
+go_template_instance(
+ name = "bits32",
+ out = "bits32.go",
+ package = "bits",
+ suffix = "32",
+ template = ":bits_template",
+ types = {
+ "T": "uint32",
+ },
+)
+
+go_test(
+ name = "bits_test",
+ size = "small",
+ srcs = ["uint64_test.go"],
+ embed = [":bits"],
+)
diff --git a/pkg/bits/bits.go b/pkg/bits/bits.go
new file mode 100644
index 000000000..50ca4bff7
--- /dev/null
+++ b/pkg/bits/bits.go
@@ -0,0 +1,16 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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 bits includes all bit related types and operations.
+package bits
diff --git a/pkg/bits/bits_template.go b/pkg/bits/bits_template.go
new file mode 100644
index 000000000..0a01f29c2
--- /dev/null
+++ b/pkg/bits/bits_template.go
@@ -0,0 +1,44 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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 bits
+
+// Non-atomic bit operations on a template type T.
+
+// T is a required type parameter that must be an integral type.
+type T uint64
+
+// IsOn returns true if *all* bits set in 'bits' are set in 'mask'.
+func IsOn(mask, bits T) bool {
+ return mask&bits == bits
+}
+
+// IsAnyOn returns true if *any* bit set in 'bits' is set in 'mask'.
+func IsAnyOn(mask, bits T) bool {
+ return mask&bits != 0
+}
+
+// Mask returns a T with all of the given bits set.
+func Mask(is ...int) T {
+ ret := T(0)
+ for _, i := range is {
+ ret |= MaskOf(i)
+ }
+ return ret
+}
+
+// MaskOf is like Mask, but sets only a single bit (more efficiently).
+func MaskOf(i int) T {
+ return T(1) << T(i)
+}
diff --git a/pkg/bits/uint64_arch_amd64.go b/pkg/bits/uint64_arch_amd64.go
new file mode 100644
index 000000000..068597f68
--- /dev/null
+++ b/pkg/bits/uint64_arch_amd64.go
@@ -0,0 +1,36 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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.
+
+// +build amd64
+
+package bits
+
+// TrailingZeros64 returns the number of bits before the least significant 1
+// bit in x; in other words, it returns the index of the least significant 1
+// bit in x. If x is 0, TrailingZeros64 returns 64.
+func TrailingZeros64(x uint64) int
+
+// MostSignificantOne64 returns the index of the most significant 1 bit in
+// x. If x is 0, MostSignificantOne64 returns 64.
+func MostSignificantOne64(x uint64) int
+
+// ForEachSetBit64 calls f once for each set bit in x, with argument i equal to
+// the set bit's index.
+func ForEachSetBit64(x uint64, f func(i int)) {
+ for x != 0 {
+ i := TrailingZeros64(x)
+ f(i)
+ x &^= MaskOf64(i)
+ }
+}
diff --git a/pkg/bits/uint64_arch_amd64_asm.s b/pkg/bits/uint64_arch_amd64_asm.s
new file mode 100644
index 000000000..33885641a
--- /dev/null
+++ b/pkg/bits/uint64_arch_amd64_asm.s
@@ -0,0 +1,31 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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.
+
+// +build amd64
+
+TEXT ·TrailingZeros64(SB),$0-16
+ BSFQ x+0(FP), AX
+ JNZ end
+ MOVQ $64, AX
+end:
+ MOVQ AX, ret+8(FP)
+ RET
+
+TEXT ·MostSignificantOne64(SB),$0-16
+ BSRQ x+0(FP), AX
+ JNZ end
+ MOVQ $64, AX
+end:
+ MOVQ AX, ret+8(FP)
+ RET
diff --git a/pkg/bits/uint64_arch_generic.go b/pkg/bits/uint64_arch_generic.go
new file mode 100644
index 000000000..862033a4b
--- /dev/null
+++ b/pkg/bits/uint64_arch_generic.go
@@ -0,0 +1,55 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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.
+
+// +build !amd64
+
+package bits
+
+// TrailingZeros64 returns the number of bits before the least significant 1
+// bit in x; in other words, it returns the index of the least significant 1
+// bit in x. If x is 0, TrailingZeros64 returns 64.
+func TrailingZeros64(x uint64) int {
+ if x == 0 {
+ return 64
+ }
+ i := 0
+ for ; x&1 == 0; i++ {
+ x >>= 1
+ }
+ return i
+}
+
+// MostSignificantOne64 returns the index of the most significant 1 bit in
+// x. If x is 0, MostSignificantOne64 returns 64.
+func MostSignificantOne64(x uint64) int {
+ if x == 0 {
+ return 64
+ }
+ i := 63
+ for ; x&(1<<63) == 0; i-- {
+ x <<= 1
+ }
+ return i
+}
+
+// ForEachSetBit64 calls f once for each set bit in x, with argument i equal to
+// the set bit's index.
+func ForEachSetBit64(x uint64, f func(i int)) {
+ for i := 0; x != 0; i++ {
+ if x&1 != 0 {
+ f(i)
+ }
+ x >>= 1
+ }
+}
diff --git a/pkg/bits/uint64_test.go b/pkg/bits/uint64_test.go
new file mode 100644
index 000000000..906017e1a
--- /dev/null
+++ b/pkg/bits/uint64_test.go
@@ -0,0 +1,116 @@
+// Copyright 2018 Google Inc.
+//
+// Licensed 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 bits
+
+import (
+ "reflect"
+ "testing"
+)
+
+func TestTrailingZeros64(t *testing.T) {
+ for i := 0; i <= 64; i++ {
+ n := uint64(1) << uint(i)
+ if got, want := TrailingZeros64(n), i; got != want {
+ t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+
+ for i := 0; i < 64; i++ {
+ n := ^uint64(0) << uint(i)
+ if got, want := TrailingZeros64(n), i; got != want {
+ t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+
+ for i := 0; i < 64; i++ {
+ n := ^uint64(0) >> uint(i)
+ if got, want := TrailingZeros64(n), 0; got != want {
+ t.Errorf("TrailingZeros64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+}
+
+func TestMostSignificantOne64(t *testing.T) {
+ for i := 0; i <= 64; i++ {
+ n := uint64(1) << uint(i)
+ if got, want := MostSignificantOne64(n), i; got != want {
+ t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+
+ for i := 0; i < 64; i++ {
+ n := ^uint64(0) >> uint(i)
+ if got, want := MostSignificantOne64(n), 63-i; got != want {
+ t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+
+ for i := 0; i < 64; i++ {
+ n := ^uint64(0) << uint(i)
+ if got, want := MostSignificantOne64(n), 63; got != want {
+ t.Errorf("MostSignificantOne64(%#x): got %d, wanted %d", n, got, want)
+ }
+ }
+}
+
+func TestForEachSetBit64(t *testing.T) {
+ for _, want := range [][]int{
+ {},
+ {0},
+ {1},
+ {63},
+ {0, 1},
+ {1, 3, 5},
+ {0, 63},
+ } {
+ n := Mask64(want...)
+ // "Slice values are deeply equal when ... they are both nil or both
+ // non-nil ..."
+ got := make([]int, 0)
+ ForEachSetBit64(n, func(i int) {
+ got = append(got, i)
+ })
+ if !reflect.DeepEqual(got, want) {
+ t.Errorf("ForEachSetBit64(%#x): iterated bits %v, wanted %v", n, got, want)
+ }
+ }
+}
+
+func TestIsOn(t *testing.T) {
+ type spec struct {
+ mask uint64
+ bits uint64
+ any bool
+ all bool
+ }
+ for _, s := range []spec{
+ {Mask64(0), Mask64(0), true, true},
+ {Mask64(63), Mask64(63), true, true},
+ {Mask64(0), Mask64(1), false, false},
+ {Mask64(0), Mask64(0, 1), true, false},
+
+ {Mask64(1, 63), Mask64(1), true, true},
+ {Mask64(1, 63), Mask64(1, 63), true, true},
+ {Mask64(1, 63), Mask64(0, 1, 63), true, false},
+ {Mask64(1, 63), Mask64(0, 62), false, false},
+ } {
+ if ok := IsAnyOn64(s.mask, s.bits); ok != s.any {
+ t.Errorf("IsAnyOn(%#x, %#x) = %v, wanted: %v", s.mask, s.bits, ok, s.any)
+ }
+ if ok := IsOn64(s.mask, s.bits); ok != s.all {
+ t.Errorf("IsOn(%#x, %#x) = %v, wanted: %v", s.mask, s.bits, ok, s.all)
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-18 14:50:16 +0000