| 4710c53d |
1 | #\r |
| 2 | # this is a rather strict implementation of a bit vector class\r |
| 3 | # it is accessed the same way as an array of python-ints, except\r |
| 4 | # the value must be 0 or 1\r |
| 5 | #\r |
| 6 | \r |
| 7 | import sys; rprt = sys.stderr.write #for debugging\r |
| 8 | \r |
| 9 | class error(Exception):\r |
| 10 | pass\r |
| 11 | \r |
| 12 | \r |
| 13 | def _check_value(value):\r |
| 14 | if type(value) != type(0) or not 0 <= value < 2:\r |
| 15 | raise error, 'bitvec() items must have int value 0 or 1'\r |
| 16 | \r |
| 17 | \r |
| 18 | import math\r |
| 19 | \r |
| 20 | def _compute_len(param):\r |
| 21 | mant, l = math.frexp(float(param))\r |
| 22 | bitmask = 1L << l\r |
| 23 | if bitmask <= param:\r |
| 24 | raise RuntimeError('(param, l) = %r' % ((param, l),))\r |
| 25 | while l:\r |
| 26 | bitmask = bitmask >> 1\r |
| 27 | if param & bitmask:\r |
| 28 | break\r |
| 29 | l = l - 1\r |
| 30 | return l\r |
| 31 | \r |
| 32 | \r |
| 33 | def _check_key(len, key):\r |
| 34 | if type(key) != type(0):\r |
| 35 | raise TypeError, 'sequence subscript not int'\r |
| 36 | if key < 0:\r |
| 37 | key = key + len\r |
| 38 | if not 0 <= key < len:\r |
| 39 | raise IndexError, 'list index out of range'\r |
| 40 | return key\r |
| 41 | \r |
| 42 | def _check_slice(len, i, j):\r |
| 43 | #the type is ok, Python already checked that\r |
| 44 | i, j = max(i, 0), min(len, j)\r |
| 45 | if i > j:\r |
| 46 | i = j\r |
| 47 | return i, j\r |
| 48 | \r |
| 49 | \r |
| 50 | class BitVec:\r |
| 51 | \r |
| 52 | def __init__(self, *params):\r |
| 53 | self._data = 0L\r |
| 54 | self._len = 0\r |
| 55 | if not len(params):\r |
| 56 | pass\r |
| 57 | elif len(params) == 1:\r |
| 58 | param, = params\r |
| 59 | if type(param) == type([]):\r |
| 60 | value = 0L\r |
| 61 | bit_mask = 1L\r |
| 62 | for item in param:\r |
| 63 | # strict check\r |
| 64 | #_check_value(item)\r |
| 65 | if item:\r |
| 66 | value = value | bit_mask\r |
| 67 | bit_mask = bit_mask << 1\r |
| 68 | self._data = value\r |
| 69 | self._len = len(param)\r |
| 70 | elif type(param) == type(0L):\r |
| 71 | if param < 0:\r |
| 72 | raise error, 'bitvec() can\'t handle negative longs'\r |
| 73 | self._data = param\r |
| 74 | self._len = _compute_len(param)\r |
| 75 | else:\r |
| 76 | raise error, 'bitvec() requires array or long parameter'\r |
| 77 | elif len(params) == 2:\r |
| 78 | param, length = params\r |
| 79 | if type(param) == type(0L):\r |
| 80 | if param < 0:\r |
| 81 | raise error, \\r |
| 82 | 'can\'t handle negative longs'\r |
| 83 | self._data = param\r |
| 84 | if type(length) != type(0):\r |
| 85 | raise error, 'bitvec()\'s 2nd parameter must be int'\r |
| 86 | computed_length = _compute_len(param)\r |
| 87 | if computed_length > length:\r |
| 88 | print 'warning: bitvec() value is longer than the length indicates, truncating value'\r |
| 89 | self._data = self._data & \\r |
| 90 | ((1L << length) - 1)\r |
| 91 | self._len = length\r |
| 92 | else:\r |
| 93 | raise error, 'bitvec() requires array or long parameter'\r |
| 94 | else:\r |
| 95 | raise error, 'bitvec() requires 0 -- 2 parameter(s)'\r |
| 96 | \r |
| 97 | \r |
| 98 | def append(self, item):\r |
| 99 | #_check_value(item)\r |
| 100 | #self[self._len:self._len] = [item]\r |
| 101 | self[self._len:self._len] = \\r |
| 102 | BitVec(long(not not item), 1)\r |
| 103 | \r |
| 104 | \r |
| 105 | def count(self, value):\r |
| 106 | #_check_value(value)\r |
| 107 | if value:\r |
| 108 | data = self._data\r |
| 109 | else:\r |
| 110 | data = (~self)._data\r |
| 111 | count = 0\r |
| 112 | while data:\r |
| 113 | data, count = data >> 1, count + (data & 1 != 0)\r |
| 114 | return count\r |
| 115 | \r |
| 116 | \r |
| 117 | def index(self, value):\r |
| 118 | #_check_value(value):\r |
| 119 | if value:\r |
| 120 | data = self._data\r |
| 121 | else:\r |
| 122 | data = (~self)._data\r |
| 123 | index = 0\r |
| 124 | if not data:\r |
| 125 | raise ValueError, 'list.index(x): x not in list'\r |
| 126 | while not (data & 1):\r |
| 127 | data, index = data >> 1, index + 1\r |
| 128 | return index\r |
| 129 | \r |
| 130 | \r |
| 131 | def insert(self, index, item):\r |
| 132 | #_check_value(item)\r |
| 133 | #self[index:index] = [item]\r |
| 134 | self[index:index] = BitVec(long(not not item), 1)\r |
| 135 | \r |
| 136 | \r |
| 137 | def remove(self, value):\r |
| 138 | del self[self.index(value)]\r |
| 139 | \r |
| 140 | \r |
| 141 | def reverse(self):\r |
| 142 | #ouch, this one is expensive!\r |
| 143 | #for i in self._len>>1: self[i], self[l-i] = self[l-i], self[i]\r |
| 144 | data, result = self._data, 0L\r |
| 145 | for i in range(self._len):\r |
| 146 | if not data:\r |
| 147 | result = result << (self._len - i)\r |
| 148 | break\r |
| 149 | result, data = (result << 1) | (data & 1), data >> 1\r |
| 150 | self._data = result\r |
| 151 | \r |
| 152 | \r |
| 153 | def sort(self):\r |
| 154 | c = self.count(1)\r |
| 155 | self._data = ((1L << c) - 1) << (self._len - c)\r |
| 156 | \r |
| 157 | \r |
| 158 | def copy(self):\r |
| 159 | return BitVec(self._data, self._len)\r |
| 160 | \r |
| 161 | \r |
| 162 | def seq(self):\r |
| 163 | result = []\r |
| 164 | for i in self:\r |
| 165 | result.append(i)\r |
| 166 | return result\r |
| 167 | \r |
| 168 | \r |
| 169 | def __repr__(self):\r |
| 170 | ##rprt('<bitvec class instance object>.' + '__repr__()\n')\r |
| 171 | return 'bitvec(%r, %r)' % (self._data, self._len)\r |
| 172 | \r |
| 173 | def __cmp__(self, other, *rest):\r |
| 174 | #rprt('%r.__cmp__%r\n' % (self, (other,) + rest))\r |
| 175 | if type(other) != type(self):\r |
| 176 | other = apply(bitvec, (other, ) + rest)\r |
| 177 | #expensive solution... recursive binary, with slicing\r |
| 178 | length = self._len\r |
| 179 | if length == 0 or other._len == 0:\r |
| 180 | return cmp(length, other._len)\r |
| 181 | if length != other._len:\r |
| 182 | min_length = min(length, other._len)\r |
| 183 | return cmp(self[:min_length], other[:min_length]) or \\r |
| 184 | cmp(self[min_length:], other[min_length:])\r |
| 185 | #the lengths are the same now...\r |
| 186 | if self._data == other._data:\r |
| 187 | return 0\r |
| 188 | if length == 1:\r |
| 189 | return cmp(self[0], other[0])\r |
| 190 | else:\r |
| 191 | length = length >> 1\r |
| 192 | return cmp(self[:length], other[:length]) or \\r |
| 193 | cmp(self[length:], other[length:])\r |
| 194 | \r |
| 195 | \r |
| 196 | def __len__(self):\r |
| 197 | #rprt('%r.__len__()\n' % (self,))\r |
| 198 | return self._len\r |
| 199 | \r |
| 200 | def __getitem__(self, key):\r |
| 201 | #rprt('%r.__getitem__(%r)\n' % (self, key))\r |
| 202 | key = _check_key(self._len, key)\r |
| 203 | return self._data & (1L << key) != 0\r |
| 204 | \r |
| 205 | def __setitem__(self, key, value):\r |
| 206 | #rprt('%r.__setitem__(%r, %r)\n' % (self, key, value))\r |
| 207 | key = _check_key(self._len, key)\r |
| 208 | #_check_value(value)\r |
| 209 | if value:\r |
| 210 | self._data = self._data | (1L << key)\r |
| 211 | else:\r |
| 212 | self._data = self._data & ~(1L << key)\r |
| 213 | \r |
| 214 | def __delitem__(self, key):\r |
| 215 | #rprt('%r.__delitem__(%r)\n' % (self, key))\r |
| 216 | key = _check_key(self._len, key)\r |
| 217 | #el cheapo solution...\r |
| 218 | self._data = self[:key]._data | self[key+1:]._data >> key\r |
| 219 | self._len = self._len - 1\r |
| 220 | \r |
| 221 | def __getslice__(self, i, j):\r |
| 222 | #rprt('%r.__getslice__(%r, %r)\n' % (self, i, j))\r |
| 223 | i, j = _check_slice(self._len, i, j)\r |
| 224 | if i >= j:\r |
| 225 | return BitVec(0L, 0)\r |
| 226 | if i:\r |
| 227 | ndata = self._data >> i\r |
| 228 | else:\r |
| 229 | ndata = self._data\r |
| 230 | nlength = j - i\r |
| 231 | if j != self._len:\r |
| 232 | #we'll have to invent faster variants here\r |
| 233 | #e.g. mod_2exp\r |
| 234 | ndata = ndata & ((1L << nlength) - 1)\r |
| 235 | return BitVec(ndata, nlength)\r |
| 236 | \r |
| 237 | def __setslice__(self, i, j, sequence, *rest):\r |
| 238 | #rprt('%s.__setslice__%r\n' % (self, (i, j, sequence) + rest))\r |
| 239 | i, j = _check_slice(self._len, i, j)\r |
| 240 | if type(sequence) != type(self):\r |
| 241 | sequence = apply(bitvec, (sequence, ) + rest)\r |
| 242 | #sequence is now of our own type\r |
| 243 | ls_part = self[:i]\r |
| 244 | ms_part = self[j:]\r |
| 245 | self._data = ls_part._data | \\r |
| 246 | ((sequence._data | \\r |
| 247 | (ms_part._data << sequence._len)) << ls_part._len)\r |
| 248 | self._len = self._len - j + i + sequence._len\r |
| 249 | \r |
| 250 | def __delslice__(self, i, j):\r |
| 251 | #rprt('%r.__delslice__(%r, %r)\n' % (self, i, j))\r |
| 252 | i, j = _check_slice(self._len, i, j)\r |
| 253 | if i == 0 and j == self._len:\r |
| 254 | self._data, self._len = 0L, 0\r |
| 255 | elif i < j:\r |
| 256 | self._data = self[:i]._data | (self[j:]._data >> i)\r |
| 257 | self._len = self._len - j + i\r |
| 258 | \r |
| 259 | def __add__(self, other):\r |
| 260 | #rprt('%r.__add__(%r)\n' % (self, other))\r |
| 261 | retval = self.copy()\r |
| 262 | retval[self._len:self._len] = other\r |
| 263 | return retval\r |
| 264 | \r |
| 265 | def __mul__(self, multiplier):\r |
| 266 | #rprt('%r.__mul__(%r)\n' % (self, multiplier))\r |
| 267 | if type(multiplier) != type(0):\r |
| 268 | raise TypeError, 'sequence subscript not int'\r |
| 269 | if multiplier <= 0:\r |
| 270 | return BitVec(0L, 0)\r |
| 271 | elif multiplier == 1:\r |
| 272 | return self.copy()\r |
| 273 | #handle special cases all 0 or all 1...\r |
| 274 | if self._data == 0L:\r |
| 275 | return BitVec(0L, self._len * multiplier)\r |
| 276 | elif (~self)._data == 0L:\r |
| 277 | return ~BitVec(0L, self._len * multiplier)\r |
| 278 | #otherwise el cheapo again...\r |
| 279 | retval = BitVec(0L, 0)\r |
| 280 | while multiplier:\r |
| 281 | retval, multiplier = retval + self, multiplier - 1\r |
| 282 | return retval\r |
| 283 | \r |
| 284 | def __and__(self, otherseq, *rest):\r |
| 285 | #rprt('%r.__and__%r\n' % (self, (otherseq,) + rest))\r |
| 286 | if type(otherseq) != type(self):\r |
| 287 | otherseq = apply(bitvec, (otherseq, ) + rest)\r |
| 288 | #sequence is now of our own type\r |
| 289 | return BitVec(self._data & otherseq._data, \\r |
| 290 | min(self._len, otherseq._len))\r |
| 291 | \r |
| 292 | \r |
| 293 | def __xor__(self, otherseq, *rest):\r |
| 294 | #rprt('%r.__xor__%r\n' % (self, (otherseq,) + rest))\r |
| 295 | if type(otherseq) != type(self):\r |
| 296 | otherseq = apply(bitvec, (otherseq, ) + rest)\r |
| 297 | #sequence is now of our own type\r |
| 298 | return BitVec(self._data ^ otherseq._data, \\r |
| 299 | max(self._len, otherseq._len))\r |
| 300 | \r |
| 301 | \r |
| 302 | def __or__(self, otherseq, *rest):\r |
| 303 | #rprt('%r.__or__%r\n' % (self, (otherseq,) + rest))\r |
| 304 | if type(otherseq) != type(self):\r |
| 305 | otherseq = apply(bitvec, (otherseq, ) + rest)\r |
| 306 | #sequence is now of our own type\r |
| 307 | return BitVec(self._data | otherseq._data, \\r |
| 308 | max(self._len, otherseq._len))\r |
| 309 | \r |
| 310 | \r |
| 311 | def __invert__(self):\r |
| 312 | #rprt('%r.__invert__()\n' % (self,))\r |
| 313 | return BitVec(~self._data & ((1L << self._len) - 1), \\r |
| 314 | self._len)\r |
| 315 | \r |
| 316 | def __coerce__(self, otherseq, *rest):\r |
| 317 | #needed for *some* of the arithmetic operations\r |
| 318 | #rprt('%r.__coerce__%r\n' % (self, (otherseq,) + rest))\r |
| 319 | if type(otherseq) != type(self):\r |
| 320 | otherseq = apply(bitvec, (otherseq, ) + rest)\r |
| 321 | return self, otherseq\r |
| 322 | \r |
| 323 | def __int__(self):\r |
| 324 | return int(self._data)\r |
| 325 | \r |
| 326 | def __long__(self):\r |
| 327 | return long(self._data)\r |
| 328 | \r |
| 329 | def __float__(self):\r |
| 330 | return float(self._data)\r |
| 331 | \r |
| 332 | \r |
| 333 | bitvec = BitVec\r |
projects / mirror_edk2.git / blame