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