bv.go

Documentation: cmd/compile/internal/bitvec

     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  	if int64(int32(size*4)) != size*4 {
    40  		base.Fatalf("NewBulk too big: nbit=%d count=%d nword=%d size=%d", nbit, count, nword, size)
    41  	}
    42  	return Bulk{
    43  		words: make([]uint32, size),
    44  		nbit:  nbit,
    45  		nword: nword,
    46  	}
    47  }
    48  
    49  func (b *Bulk) Next() BitVec {
    50  	out := BitVec{b.nbit, b.words[:b.nword]}
    51  	b.words = b.words[b.nword:]
    52  	return out
    53  }
    54  
    55  func (bv1 BitVec) Eq(bv2 BitVec) bool {
    56  	if bv1.N != bv2.N {
    57  		base.Fatalf("bvequal: lengths %d and %d are not equal", bv1.N, bv2.N)
    58  	}
    59  	for i, x := range bv1.B {
    60  		if x != bv2.B[i] {
    61  			return false
    62  		}
    63  	}
    64  	return true
    65  }
    66  
    67  func (dst BitVec) Copy(src BitVec) {
    68  	copy(dst.B, src.B)
    69  }
    70  
    71  func (bv BitVec) Get(i int32) bool {
    72  	if i < 0 || i >= bv.N {
    73  		base.Fatalf("bvget: index %d is out of bounds with length %d\n", i, bv.N)
    74  	}
    75  	mask := uint32(1 << uint(i%wordBits))
    76  	return bv.B[i>>wordShift]&mask != 0
    77  }
    78  
    79  func (bv BitVec) Set(i int32) {
    80  	if i < 0 || i >= bv.N {
    81  		base.Fatalf("bvset: index %d is out of bounds with length %d\n", i, bv.N)
    82  	}
    83  	mask := uint32(1 << uint(i%wordBits))
    84  	bv.B[i/wordBits] |= mask
    85  }
    86  
    87  func (bv BitVec) Unset(i int32) {
    88  	if i < 0 || i >= bv.N {
    89  		base.Fatalf("bvunset: index %d is out of bounds with length %d\n", i, bv.N)
    90  	}
    91  	mask := uint32(1 << uint(i%wordBits))
    92  	bv.B[i/wordBits] &^= mask
    93  }
    94  
    95  // bvnext returns the smallest index >= i for which bvget(bv, i) == 1.
    96  // If there is no such index, bvnext returns -1.
    97  func (bv BitVec) Next(i int32) int32 {
    98  	if i >= bv.N {
    99  		return -1
   100  	}
   101  
   102  	// Jump i ahead to next word with bits.
   103  	if bv.B[i>>wordShift]>>uint(i&wordMask) == 0 {
   104  		i &^= wordMask
   105  		i += wordBits
   106  		for i < bv.N && bv.B[i>>wordShift] == 0 {
   107  			i += wordBits
   108  		}
   109  	}
   110  
   111  	if i >= bv.N {
   112  		return -1
   113  	}
   114  
   115  	// Find 1 bit.
   116  	w := bv.B[i>>wordShift] >> uint(i&wordMask)
   117  	i += int32(bits.TrailingZeros32(w))
   118  
   119  	return i
   120  }
   121  
   122  func (bv BitVec) IsEmpty() bool {
   123  	for _, x := range bv.B {
   124  		if x != 0 {
   125  			return false
   126  		}
   127  	}
   128  	return true
   129  }
   130  
   131  func (bv BitVec) Not() {
   132  	for i, x := range bv.B {
   133  		bv.B[i] = ^x
   134  	}
   135  }
   136  
   137  // union
   138  func (dst BitVec) Or(src1, src2 BitVec) {
   139  	if len(src1.B) == 0 {
   140  		return
   141  	}
   142  	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
   143  
   144  	for i, x := range src1.B {
   145  		dst.B[i] = x | src2.B[i]
   146  	}
   147  }
   148  
   149  // intersection
   150  func (dst BitVec) And(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  // difference
   162  func (dst BitVec) AndNot(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  func (bv BitVec) String() string {
   174  	s := make([]byte, 2+bv.N)
   175  	copy(s, "#*")
   176  	for i := int32(0); i < bv.N; i++ {
   177  		ch := byte('0')
   178  		if bv.Get(i) {
   179  			ch = '1'
   180  		}
   181  		s[2+i] = ch
   182  	}
   183  	return string(s)
   184  }
   185  
   186  func (bv BitVec) Clear() {
   187  	for i := range bv.B {
   188  		bv.B[i] = 0
   189  	}
   190  }
   191
View as plain text