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 gc 6 7 import "fmt" 8 9 const ( 10 WORDSIZE = 4 11 WORDBITS = 32 12 WORDMASK = WORDBITS - 1 13 WORDSHIFT = 5 14 ) 15 16 // A Bvec is a bit vector. 17 type Bvec struct { 18 n int32 // number of bits in vector 19 b []uint32 // words holding bits 20 } 21 22 func bvsize(n uint32) uint32 { 23 return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE 24 } 25 26 func bvbits(bv Bvec) int32 { 27 return bv.n 28 } 29 30 func bvwords(bv Bvec) int32 { 31 return (bv.n + WORDBITS - 1) / WORDBITS 32 } 33 34 func bvalloc(n int32) Bvec { 35 return Bvec{n, make([]uint32, bvsize(uint32(n))/4)} 36 } 37 38 type bulkBvec struct { 39 words []uint32 40 nbit int32 41 nword int32 42 } 43 44 func bvbulkalloc(nbit int32, count int32) bulkBvec { 45 nword := (nbit + WORDBITS - 1) / WORDBITS 46 return bulkBvec{ 47 words: make([]uint32, nword*count), 48 nbit: nbit, 49 nword: nword, 50 } 51 } 52 53 func (b *bulkBvec) next() Bvec { 54 out := Bvec{b.nbit, b.words[:b.nword]} 55 b.words = b.words[b.nword:] 56 return out 57 } 58 59 /* difference */ 60 func bvandnot(dst Bvec, src1 Bvec, src2 Bvec) { 61 for i, x := range src1.b { 62 dst.b[i] = x &^ src2.b[i] 63 } 64 } 65 66 func bvcmp(bv1 Bvec, bv2 Bvec) int { 67 if bv1.n != bv2.n { 68 Fatal("bvequal: lengths %d and %d are not equal", bv1.n, bv2.n) 69 } 70 for i, x := range bv1.b { 71 if x != bv2.b[i] { 72 return 1 73 } 74 } 75 return 0 76 } 77 78 func bvcopy(dst Bvec, src Bvec) { 79 for i, x := range src.b { 80 dst.b[i] = x 81 } 82 } 83 84 func bvconcat(src1 Bvec, src2 Bvec) Bvec { 85 dst := bvalloc(src1.n + src2.n) 86 for i := int32(0); i < src1.n; i++ { 87 if bvget(src1, i) != 0 { 88 bvset(dst, i) 89 } 90 } 91 for i := int32(0); i < src2.n; i++ { 92 if bvget(src2, i) != 0 { 93 bvset(dst, i+src1.n) 94 } 95 } 96 return dst 97 } 98 99 func bvget(bv Bvec, i int32) int { 100 if i < 0 || i >= bv.n { 101 Fatal("bvget: index %d is out of bounds with length %d\n", i, bv.n) 102 } 103 return int((bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK)) & 1) 104 } 105 106 // bvnext returns the smallest index >= i for which bvget(bv, i) == 1. 107 // If there is no such index, bvnext returns -1. 108 func bvnext(bv Bvec, i int32) int { 109 if i >= bv.n { 110 return -1 111 } 112 113 // Jump i ahead to next word with bits. 114 if bv.b[i>>WORDSHIFT]>>uint(i&WORDMASK) == 0 { 115 i &^= WORDMASK 116 i += WORDBITS 117 for i < bv.n && bv.b[i>>WORDSHIFT] == 0 { 118 i += WORDBITS 119 } 120 } 121 122 if i >= bv.n { 123 return -1 124 } 125 126 // Find 1 bit. 127 w := bv.b[i>>WORDSHIFT] >> uint(i&WORDMASK) 128 129 for w&1 == 0 { 130 w >>= 1 131 i++ 132 } 133 134 return int(i) 135 } 136 137 func bvisempty(bv Bvec) bool { 138 for i := int32(0); i < bv.n; i += WORDBITS { 139 if bv.b[i>>WORDSHIFT] != 0 { 140 return false 141 } 142 } 143 return true 144 } 145 146 func bvnot(bv Bvec) { 147 i := int32(0) 148 w := int32(0) 149 for ; i < bv.n; i, w = i+WORDBITS, w+1 { 150 bv.b[w] = ^bv.b[w] 151 } 152 } 153 154 /* union */ 155 func bvor(dst Bvec, src1 Bvec, src2 Bvec) { 156 for i, x := range src1.b { 157 dst.b[i] = x | src2.b[i] 158 } 159 } 160 161 /* intersection */ 162 func bvand(dst Bvec, src1 Bvec, src2 Bvec) { 163 for i, x := range src1.b { 164 dst.b[i] = x & src2.b[i] 165 } 166 } 167 168 func bvprint(bv Bvec) { 169 fmt.Printf("#*") 170 for i := int32(0); i < bv.n; i++ { 171 fmt.Printf("%d", bvget(bv, i)) 172 } 173 } 174 175 func bvreset(bv Bvec, i int32) { 176 if i < 0 || i >= bv.n { 177 Fatal("bvreset: index %d is out of bounds with length %d\n", i, bv.n) 178 } 179 mask := uint32(^(1 << uint(i%WORDBITS))) 180 bv.b[i/WORDBITS] &= mask 181 } 182 183 func bvresetall(bv Bvec) { 184 for i := range bv.b { 185 bv.b[i] = 0 186 } 187 } 188 189 func bvset(bv Bvec, i int32) { 190 if i < 0 || i >= bv.n { 191 Fatal("bvset: index %d is out of bounds with length %d\n", i, bv.n) 192 } 193 mask := uint32(1 << uint(i%WORDBITS)) 194 bv.b[i/WORDBITS] |= mask 195 } 196
