1 #!/usr/bin/env python 2 3 """ 4 Data representation functions. 5 6 Copyright (C) 2009, 2010, 2011 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 15 PARTICULAR PURPOSE. See the GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License along 18 with this program. If not, see <http://www.gnu.org/licenses/>. 19 """ 20 21 from array import array 22 import operator 23 24 # High-level representations. 25 26 def convert_sequence(values, op, last_from_preceding): 27 28 """ 29 Convert the given sequence of 'values' either to a sequence of delta values 30 if 'op' is a subtractor of some kind, using the preceding value in the 31 sequence as the basis of the calculation of a delta for the current value 32 (with 'last_from_preceding' set to a true value), or from a sequence of 33 delta values if 'op' is an adder of some kind, using the last result as the 34 basis of the calculation of an absolute value (with 'last_from_preceding' 35 set to a false value). 36 """ 37 38 if values: 39 new_values = list(values) 40 last = new_values[0] 41 i = 1 42 length = len(new_values) 43 while i < length: 44 current = new_values[i] 45 new_values[i] = op(current, last) 46 47 # Subtracting entries requires the old value to be used. 48 # Adding entries requires the new value. 49 50 if last_from_preceding: 51 last = current 52 else: 53 last = new_values[i] 54 55 i += 1 56 57 return new_values 58 else: 59 return values 60 61 # Monotonic operators where an input sequence must always, when combined with an 62 # operand, produce a result whose elements are all greater than or equal to the 63 # values of the input sequence (for addition) or all less than or equal to the 64 # values of the input sequence (for subtraction). 65 # 66 # For example: (1, 2) -> (2, 2) -> (2, 3) -> (3, 4) 67 68 def op_seq_monotonic(x, y, op): 69 return tuple([op(a, b) for a, b in zip(x, y)]) 70 71 def add_seq_monotonic(x, y): 72 return op_seq_monotonic(x, y, operator.add) 73 74 def sub_seq_monotonic(x, y): 75 return op_seq_monotonic(x, y, operator.sub) 76 77 # Operators where an input sequence, when combined with an operand, may produce 78 # a result whose elements generally obey the properties for a monotonic sequence 79 # as described above, but where an element in the result may be reset with 80 # respect to the corresponding element in the input sequence and be less than 81 # that element (for addition) or greater than that element (for subtraction). 82 # 83 # For example: (1, 2) -> (2, 0) -> (2, 3) -> (3, 1) 84 85 def add_seq(delta, input): 86 87 "Add 'delta' to 'input'." 88 89 length = min(len(delta), len(input)) 90 seq = list(delta)[:length] 91 i = 0 92 while i < length: 93 94 # If the delta is not zero, apply it to the input and retain the rest of 95 # the delta sequence as absolute values in the result. 96 97 if delta[i] != 0: 98 seq[i] = delta[i] + input[i] 99 break 100 101 seq[i] = input[i] 102 i += 1 103 return tuple(seq) 104 105 def sub_seq(current, last): 106 107 "Subtract 'current' from 'last'." 108 109 length = min(len(current), len(last)) 110 seq = list(current)[:length] 111 i = 0 112 while i < length: 113 114 # Calculate a suitable delta value. If it is not zero, record it and 115 # retain the rest of the current value to reset the sequence in the 116 # result. 117 118 replacement = current[i] - last[i] 119 if replacement != 0: 120 seq[i] = replacement 121 break 122 123 seq[i] = 0 124 i += 1 125 return tuple(seq) 126 127 # Data inspection functions. 128 129 def is_sequence(value): 130 return isinstance(value, (list, tuple)) 131 132 def sizeof(value): 133 return is_sequence(value) and len(value) or 0 134 135 # Functions returning operators appropriate for the given structure size. 136 137 def get_monotonic_adder(size): 138 return size and add_seq_monotonic or operator.add 139 140 def get_monotonic_subtractor(size): 141 return size and sub_seq_monotonic or operator.sub 142 143 def get_adder(size): 144 return size and add_seq or operator.add 145 146 def get_subtractor(size): 147 return size and sub_seq or operator.sub 148 149 # Low-level representations. 150 # Variable-length integer functions. 151 152 vint_cache = [] 153 vint_bytes_cache = [] 154 155 def vint(number): 156 157 "Write 'number' as a variable-length integer." 158 159 try: 160 return vint_cache[number] 161 except IndexError: 162 if number >= 0: 163 bytes = array('B') 164 _vint_to_array(number, bytes) 165 return bytes.tostring() 166 167 # Negative numbers are not supported. 168 169 else: 170 raise ValueError, "Number %r is negative." % number 171 172 def vint_to_array(number, bytes): 173 174 "Write 'number' as a variable-length integer to 'bytes'." 175 176 try: 177 bytes += vint_bytes_cache[number] 178 except IndexError: 179 if number >= 0: 180 _vint_to_array(number, bytes) 181 182 # Negative numbers are not supported. 183 184 else: 185 raise ValueError, "Number %r is negative." % number 186 187 def _vint_to_array(number, bytes): 188 189 "Write the 'number' to 'bytes' from least to most significant digits." 190 191 while number > 127: 192 bytes.append(number & 127 | 128) 193 number = number >> 7 194 else: 195 bytes.append(number) 196 197 def vint_from_array(bytes): 198 199 "Read a variable-length integer from 'bytes', returning a number." 200 201 number = 0 202 while bytes: 203 number <<= 7 204 number += bytes.pop() & 127 205 return number 206 207 def vint_from_array_start(bytes, start): 208 209 """ 210 Read a variable-length integer from 'bytes', starting at 'start', and 211 returning a tuple containing a number and the first position after the 212 number. 213 """ 214 215 length = len(bytes) 216 if start == length: 217 raise EOFError 218 219 number = 0 220 digit = 0 221 while start < length: 222 x = bytes[start] 223 number += (x & 127) << digit 224 digit += 7 225 start += 1 226 if not (x & 128): 227 break 228 return number, start 229 230 # Sequence serialisation. 231 232 def sequence_to_array(value, size, bytes): 233 234 "Write the given sequence 'value' with the given 'size' to 'bytes'." 235 236 if size: 237 i = 0 238 limit = min(len(value), size) 239 while i < limit: 240 vint_to_array(value[i], bytes) 241 i += 1 242 while i < size: 243 vint_to_array(0, bytes) 244 else: 245 vint_to_array(value, bytes) 246 247 def sequence_from_array(bytes, size, start=0): 248 249 """ 250 Read a sequence from 'bytes' having the given 'size', returning the sequence 251 and the first position after the sequence. 252 """ 253 254 if size: 255 j = 0 256 value = [] 257 while j < size: 258 v, start = vint_from_array_start(bytes, start) 259 value.append(v) 260 j += 1 261 return tuple(value), start 262 else: 263 return vint_from_array_start(bytes, start) 264 265 # Variable-length integer cache initialisation. 266 267 for i in xrange(0, 65536): 268 bytes = array('B') 269 _vint_to_array(i, bytes) 270 vint_bytes_cache.append(bytes) 271 vint_cache.append(bytes.tostring()) 272 273 # vim: tabstop=4 expandtab shiftwidth=4