From d02b74a5dcfed4bfc8f2f8e545bca4d2afabb296 Mon Sep 17 00:00:00 2001 From: Googler Date: Fri, 27 Apr 2018 10:37:02 -0700 Subject: Check in gVisor. PiperOrigin-RevId: 194583126 Change-Id: Ica1d8821a90f74e7e745962d71801c598c652463 --- pkg/bits/BUILD | 55 +++++++++++++++++++ pkg/bits/bits.go | 16 ++++++ pkg/bits/bits_template.go | 44 +++++++++++++++ pkg/bits/uint64_arch_amd64.go | 36 ++++++++++++ pkg/bits/uint64_arch_amd64_asm.s | 31 +++++++++++ pkg/bits/uint64_arch_generic.go | 55 +++++++++++++++++++ pkg/bits/uint64_test.go | 116 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 353 insertions(+) create mode 100644 pkg/bits/BUILD create mode 100644 pkg/bits/bits.go create mode 100644 pkg/bits/bits_template.go create mode 100644 pkg/bits/uint64_arch_amd64.go create mode 100644 pkg/bits/uint64_arch_amd64_asm.s create mode 100644 pkg/bits/uint64_arch_generic.go create mode 100644 pkg/bits/uint64_test.go (limited to 'pkg/bits') 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) + } + } +} -- cgit v1.2.3