bv.go

     1  // Copyright 2013 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package bitvec
     6  
     7  import (
     8  	"math/bits"
     9  
    10  	"cmd/compile/internal/base"
    11  )
    12  
    13  const (
    14  	wordBits  = 32
    15  	wordMask  = wordBits - 1
    16  	wordShift = 5
    17  )
    18  
    19  // A BitVec is a bit vector.
    20  type BitVec struct {
    21  	N int32    // number of bits in vector
    22  	B []uint32 // words holding bits
    23  }
    24  
    25  func New(n int32) BitVec {
    26  	nword := (n + wordBits - 1) / wordBits
    27  	return BitVec{n, make([]uint32, nword)}
    28  }
    29  
    30  type Bulk struct {
    31  	words []uint32
    32  	nbit  int32
    33  	nword int32
    34  }
    35  
    36  func NewBulk(nbit int32, count int32) Bulk {
    37  	nword := (nbit + wordBits - 1) / wordBits
    38  	size := int64(nword) * int64(count)
    39  	return Bulk{
    40  		words: make([]uint32, size),
    41  		nbit:  nbit,
    42  		nword: nword,
    43  	}
    44  }
    45  
    46  func (b *Bulk) Next() BitVec {
    47  	out := BitVec{b.nbit, b.words[:b.nword]}
    48  	b.words = b.words[b.nword:]
    49  	return out
    50  }
    51  
    52  func (bv1 BitVec) Eq(bv2 BitVec) bool {
    53  	if bv1.N != bv2.N {
    54  		base.Fatalf("bvequal: lengths %d and %d are not equal", bv1.N, bv2.N)
    55  	}
    56  	for i, x := range bv1.B {
    57  		if x != bv2.B[i] {
    58  			return false
    59  		}
    60  	}
    61  	return true
    62  }
    63  
    64  func (dst BitVec) Copy(src BitVec) {
    65  	copy(dst.B, src.B)
    66  }
    67  
    68  func (bv BitVec) Get(i int32) bool {
    69  	if i < 0 || i >= bv.N {
    70  		base.Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.N)
    71  	}
    72  	mask := uint32(1 << uint(i%wordBits))
    73  	return bv.B[i>>wordShift]&mask != 0
    74  }
    75  
    76  func (bv BitVec) Set(i int32) {
    77  	if i < 0 || i >= bv.N {
    78  		base.Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.N)
    79  	}
    80  	mask := uint32(1 << uint(i%wordBits))
    81  	bv.B[i/wordBits] |= mask
    82  }
    83  
    84  func (bv BitVec) Unset(i int32) {
    85  	if i < 0 || i >= bv.N {
    86  		base.Fatalf("bvunset: index %d is out of bounds with length %d\n", i, bv.N)
    87  	}
    88  	mask := uint32(1 << uint(i%wordBits))
    89  	bv.B[i/wordBits] &^= mask
    90  }
    91  
    92  // Next returns the smallest index >= i for which bvget(bv, i) == 1.
    93  // If there is no such index, bvnext returns -1.
    94  func (bv BitVec) Next(i int32) int32 {
    95  	if i >= bv.N {
    96  		return -1
    97  	}
    98  
    99  	// Jump i ahead to next word with bits.
   100  	if bv.B[i>>wordShift]>>uint(i&wordMask) == 0 {
   101  		i &^= wordMask
   102  		i += wordBits
   103  		for i < bv.N && bv.B[i>>wordShift] == 0 {
   104  			i += wordBits
   105  		}
   106  	}
   107  
   108  	if i >= bv.N {
   109  		return -1
   110  	}
   111  
   112  	// Find 1 bit.
   113  	w := bv.B[i>>wordShift] >> uint(i&wordMask)
   114  	i += int32(bits.TrailingZeros32(w))
   115  
   116  	return i
   117  }
   118  
   119  func (bv BitVec) IsEmpty() bool {
   120  	for _, x := range bv.B {
   121  		if x != 0 {
   122  			return false
   123  		}
   124  	}
   125  	return true
   126  }
   127  
   128  func (bv BitVec) Count() int {
   129  	n := 0
   130  	for _, x := range bv.B {
   131  		n += bits.OnesCount32(x)
   132  	}
   133  	return n
   134  }
   135  
   136  func (bv BitVec) Not() {
   137  	for i, x := range bv.B {
   138  		bv.B[i] = ^x
   139  	}
   140  	if bv.N%wordBits != 0 {
   141  		bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1 // clear bits past N in the last word
   142  	}
   143  }
   144  
   145  // union
   146  func (dst BitVec) Or(src1, src2 BitVec) {
   147  	if len(src1.B) == 0 {
   148  		return
   149  	}
   150  	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
   151  
   152  	for i, x := range src1.B {
   153  		dst.B[i] = x | src2.B[i]
   154  	}
   155  }
   156  
   157  // intersection
   158  func (dst BitVec) And(src1, src2 BitVec) {
   159  	if len(src1.B) == 0 {
   160  		return
   161  	}
   162  	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
   163  
   164  	for i, x := range src1.B {
   165  		dst.B[i] = x & src2.B[i]
   166  	}
   167  }
   168  
   169  // difference
   170  func (dst BitVec) AndNot(src1, src2 BitVec) {
   171  	if len(src1.B) == 0 {
   172  		return
   173  	}
   174  	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
   175  
   176  	for i, x := range src1.B {
   177  		dst.B[i] = x &^ src2.B[i]
   178  	}
   179  }
   180  
   181  func (bv BitVec) String() string {
   182  	s := make([]byte, 2+bv.N)
   183  	copy(s, "#*")
   184  	for i := int32(0); i < bv.N; i++ {
   185  		ch := byte('0')
   186  		if bv.Get(i) {
   187  			ch = '1'
   188  		}
   189  		s[2+i] = ch
   190  	}
   191  	return string(s)
   192  }
   193  
   194  func (bv BitVec) Clear() {
   195  	clear(bv.B)
   196  }
   197
View as plain text