projects / people / shoehn / ipfire.org.git / blame
| Commit | Line | Data |
|---|---|---|
| 879aa787 MT |
1 | # Written by Bram Cohen, Uoti Urpala, and John Hoffman |
| 2 | # see LICENSE.txt for license information | |
| 3 | ||
| 4 | try: | |
| 5 | True | |
| 6 | except: | |
| 7 | True = 1 | |
| 8 | False = 0 | |
| 9 | bool = lambda x: not not x | |
| 10 | ||
| 11 | try: | |
| 12 | sum([1]) | |
| 13 | negsum = lambda a: len(a)-sum(a) | |
| 14 | except: | |
| 15 | negsum = lambda a: reduce(lambda x,y: x+(not y), a, 0) | |
| 16 | ||
| 17 | def _int_to_booleans(x): | |
| 18 | r = [] | |
| 19 | for i in range(8): | |
| 20 | r.append(bool(x & 0x80)) | |
| 21 | x <<= 1 | |
| 22 | return tuple(r) | |
| 23 | ||
| 24 | lookup_table = [] | |
| 25 | reverse_lookup_table = {} | |
| 26 | for i in xrange(256): | |
| 27 | x = _int_to_booleans(i) | |
| 28 | lookup_table.append(x) | |
| 29 | reverse_lookup_table[x] = chr(i) | |
| 30 | ||
| 31 | ||
| 32 | class Bitfield: | |
| 33 | def __init__(self, length = None, bitstring = None, copyfrom = None): | |
| 34 | if copyfrom is not None: | |
| 35 | self.length = copyfrom.length | |
| 36 | self.array = copyfrom.array[:] | |
| 37 | self.numfalse = copyfrom.numfalse | |
| 38 | return | |
| 39 | if length is None: | |
| 40 | raise ValueError, "length must be provided unless copying from another array" | |
| 41 | self.length = length | |
| 42 | if bitstring is not None: | |
| 43 | extra = len(bitstring) * 8 - length | |
| 44 | if extra < 0 or extra >= 8: | |
| 45 | raise ValueError | |
| 46 | t = lookup_table | |
| 47 | r = [] | |
| 48 | for c in bitstring: | |
| 49 | r.extend(t[ord(c)]) | |
| 50 | if extra > 0: | |
| 51 | if r[-extra:] != [0] * extra: | |
| 52 | raise ValueError | |
| 53 | del r[-extra:] | |
| 54 | self.array = r | |
| 55 | self.numfalse = negsum(r) | |
| 56 | else: | |
| 57 | self.array = [False] * length | |
| 58 | self.numfalse = length | |
| 59 | ||
| 60 | def __setitem__(self, index, val): | |
| 61 | val = bool(val) | |
| 62 | self.numfalse += self.array[index]-val | |
| 63 | self.array[index] = val | |
| 64 | ||
| 65 | def __getitem__(self, index): | |
| 66 | return self.array[index] | |
| 67 | ||
| 68 | def __len__(self): | |
| 69 | return self.length | |
| 70 | ||
| 71 | def tostring(self): | |
| 72 | booleans = self.array | |
| 73 | t = reverse_lookup_table | |
| 74 | s = len(booleans) % 8 | |
| 75 | r = [ t[tuple(booleans[x:x+8])] for x in xrange(0, len(booleans)-s, 8) ] | |
| 76 | if s: | |
| 77 | r += t[tuple(booleans[-s:] + ([0] * (8-s)))] | |
| 78 | return ''.join(r) | |
| 79 | ||
| 80 | def complete(self): | |
| 81 | return not self.numfalse | |
| 82 | ||
| 83 | ||
| 84 | def test_bitfield(): | |
| 85 | try: | |
| 86 | x = Bitfield(7, 'ab') | |
| 87 | assert False | |
| 88 | except ValueError: | |
| 89 | pass | |
| 90 | try: | |
| 91 | x = Bitfield(7, 'ab') | |
| 92 | assert False | |
| 93 | except ValueError: | |
| 94 | pass | |
| 95 | try: | |
| 96 | x = Bitfield(9, 'abc') | |
| 97 | assert False | |
| 98 | except ValueError: | |
| 99 | pass | |
| 100 | try: | |
| 101 | x = Bitfield(0, 'a') | |
| 102 | assert False | |
| 103 | except ValueError: | |
| 104 | pass | |
| 105 | try: | |
| 106 | x = Bitfield(1, '') | |
| 107 | assert False | |
| 108 | except ValueError: | |
| 109 | pass | |
| 110 | try: | |
| 111 | x = Bitfield(7, '') | |
| 112 | assert False | |
| 113 | except ValueError: | |
| 114 | pass | |
| 115 | try: | |
| 116 | x = Bitfield(8, '') | |
| 117 | assert False | |
| 118 | except ValueError: | |
| 119 | pass | |
| 120 | try: | |
| 121 | x = Bitfield(9, 'a') | |
| 122 | assert False | |
| 123 | except ValueError: | |
| 124 | pass | |
| 125 | try: | |
| 126 | x = Bitfield(7, chr(1)) | |
| 127 | assert False | |
| 128 | except ValueError: | |
| 129 | pass | |
| 130 | try: | |
| 131 | x = Bitfield(9, chr(0) + chr(0x40)) | |
| 132 | assert False | |
| 133 | except ValueError: | |
| 134 | pass | |
| 135 | assert Bitfield(0, '').tostring() == '' | |
| 136 | assert Bitfield(1, chr(0x80)).tostring() == chr(0x80) | |
| 137 | assert Bitfield(7, chr(0x02)).tostring() == chr(0x02) | |
| 138 | assert Bitfield(8, chr(0xFF)).tostring() == chr(0xFF) | |
| 139 | assert Bitfield(9, chr(0) + chr(0x80)).tostring() == chr(0) + chr(0x80) | |
| 140 | x = Bitfield(1) | |
| 141 | assert x.numfalse == 1 | |
| 142 | x[0] = 1 | |
| 143 | assert x.numfalse == 0 | |
| 144 | x[0] = 1 | |
| 145 | assert x.numfalse == 0 | |
| 146 | assert x.tostring() == chr(0x80) | |
| 147 | x = Bitfield(7) | |
| 148 | assert len(x) == 7 | |
| 149 | x[6] = 1 | |
| 150 | assert x.numfalse == 6 | |
| 151 | assert x.tostring() == chr(0x02) | |
| 152 | x = Bitfield(8) | |
| 153 | x[7] = 1 | |
| 154 | assert x.tostring() == chr(1) | |
| 155 | x = Bitfield(9) | |
| 156 | x[8] = 1 | |
| 157 | assert x.numfalse == 8 | |
| 158 | assert x.tostring() == chr(0) + chr(0x80) | |
| 159 | x = Bitfield(8, chr(0xC4)) | |
| 160 | assert len(x) == 8 | |
| 161 | assert x.numfalse == 5 | |
| 162 | assert x.tostring() == chr(0xC4) |