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