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@96 | 26 | def convert_sequence(values, op, last_from_old): |
paul@89 | 27 | if values: |
paul@89 | 28 | new_values = list(values) |
paul@89 | 29 | last = new_values[0] |
paul@89 | 30 | i = 1 |
paul@89 | 31 | length = len(new_values) |
paul@89 | 32 | while i < length: |
paul@89 | 33 | current = new_values[i] |
paul@96 | 34 | new_values[i] = op(current, last) |
paul@96 | 35 | |
paul@96 | 36 | # Subtracting entries requires the old value to be used. |
paul@96 | 37 | # Adding entries requires the new value. |
paul@96 | 38 | |
paul@96 | 39 | if last_from_old: |
paul@96 | 40 | last = current |
paul@96 | 41 | else: |
paul@96 | 42 | last = new_values[i] |
paul@96 | 43 | |
paul@89 | 44 | i += 1 |
paul@89 | 45 | |
paul@96 | 46 | return new_values |
paul@96 | 47 | else: |
paul@96 | 48 | return values |
paul@96 | 49 | |
paul@91 | 50 | def op_seq_monotonic(x, y, op): |
paul@91 | 51 | return tuple([op(a, b) for a, b in zip(x, y)]) |
paul@91 | 52 | |
paul@89 | 53 | def add_seq_monotonic(x, y): |
paul@89 | 54 | return op_seq_monotonic(x, y, operator.add) |
paul@89 | 55 | |
paul@89 | 56 | def sub_seq_monotonic(x, y): |
paul@89 | 57 | return op_seq_monotonic(x, y, operator.sub) |
paul@89 | 58 | |
paul@89 | 59 | def add_seq(x, y): |
paul@89 | 60 | length = min(len(x), len(y)) |
paul@89 | 61 | seq = list(x)[:length] |
paul@89 | 62 | i = 0 |
paul@89 | 63 | while i < length: |
paul@89 | 64 | if x[i] != 0: |
paul@89 | 65 | seq[i] = x[i] + y[i] |
paul@89 | 66 | break |
paul@89 | 67 | seq[i] = y[i] |
paul@89 | 68 | i += 1 |
paul@89 | 69 | return tuple(seq) |
paul@89 | 70 | |
paul@89 | 71 | def sub_seq(x, y): |
paul@89 | 72 | length = min(len(x), len(y)) |
paul@89 | 73 | seq = list(x)[:length] |
paul@89 | 74 | i = 0 |
paul@89 | 75 | while i < length: |
paul@89 | 76 | replacement = x[i] - y[i] |
paul@89 | 77 | if replacement != 0: |
paul@89 | 78 | seq[i] = replacement |
paul@89 | 79 | break |
paul@89 | 80 | seq[i] = 0 |
paul@89 | 81 | i += 1 |
paul@89 | 82 | return tuple(seq) |
paul@89 | 83 | |
paul@89 | 84 | def is_sequence(value): |
paul@89 | 85 | return isinstance(value, (list, tuple)) |
paul@89 | 86 | |
paul@91 | 87 | def sizeof(value): |
paul@91 | 88 | return is_sequence(value) and len(value) or 0 |
paul@91 | 89 | |
paul@96 | 90 | def get_monotonic_adder(size): |
paul@96 | 91 | return size and add_seq_monotonic or operator.add |
paul@89 | 92 | |
paul@96 | 93 | def get_monotonic_subtractor(size): |
paul@96 | 94 | return size and sub_seq_monotonic or operator.sub |
paul@89 | 95 | |
paul@96 | 96 | def get_adder(size): |
paul@96 | 97 | return size and add_seq or operator.add |
paul@89 | 98 | |
paul@96 | 99 | def get_subtractor(size): |
paul@96 | 100 | return size and sub_seq or operator.sub |
paul@89 | 101 | |
paul@89 | 102 | # Low-level representations. |
paul@89 | 103 | # Variable-length integer functions. |
paul@89 | 104 | |
paul@89 | 105 | vint_cache = [] |
paul@89 | 106 | vint_bytes_cache = [] |
paul@44 | 107 | |
paul@51 | 108 | def vint(number): |
paul@44 | 109 | |
paul@51 | 110 | "Write 'number' as a variable-length integer." |
paul@44 | 111 | |
paul@51 | 112 | try: |
paul@51 | 113 | return vint_cache[number] |
paul@89 | 114 | except IndexError: |
paul@44 | 115 | if number >= 0: |
paul@55 | 116 | bytes = array('B') |
paul@56 | 117 | _vint_to_array(number, bytes) |
paul@55 | 118 | return bytes.tostring() |
paul@44 | 119 | |
paul@44 | 120 | # Negative numbers are not supported. |
paul@44 | 121 | |
paul@44 | 122 | else: |
paul@44 | 123 | raise ValueError, "Number %r is negative." % number |
paul@44 | 124 | |
paul@56 | 125 | def vint_to_array(number, bytes): |
paul@56 | 126 | |
paul@56 | 127 | "Write 'number' as a variable-length integer to 'bytes'." |
paul@56 | 128 | |
paul@56 | 129 | try: |
paul@56 | 130 | bytes += vint_bytes_cache[number] |
paul@89 | 131 | except IndexError: |
paul@56 | 132 | if number >= 0: |
paul@56 | 133 | _vint_to_array(number, bytes) |
paul@56 | 134 | |
paul@56 | 135 | # Negative numbers are not supported. |
paul@56 | 136 | |
paul@56 | 137 | else: |
paul@56 | 138 | raise ValueError, "Number %r is negative." % number |
paul@56 | 139 | |
paul@56 | 140 | def _vint_to_array(number, bytes): |
paul@56 | 141 | |
paul@56 | 142 | "Write the 'number' to 'bytes' from least to most significant digits." |
paul@56 | 143 | |
paul@56 | 144 | while number > 127: |
paul@56 | 145 | bytes.append(number & 127 | 128) |
paul@56 | 146 | number = number >> 7 |
paul@56 | 147 | else: |
paul@56 | 148 | bytes.append(number) |
paul@56 | 149 | |
paul@86 | 150 | def vint_from_array(bytes): |
paul@86 | 151 | |
paul@86 | 152 | "Read a variable-length integer from 'bytes', returning a number." |
paul@86 | 153 | |
paul@86 | 154 | number = 0 |
paul@86 | 155 | while bytes: |
paul@86 | 156 | number <<= 7 |
paul@86 | 157 | number += bytes.pop() & 127 |
paul@86 | 158 | return number |
paul@86 | 159 | |
paul@89 | 160 | def vint_from_array_start(bytes, start): |
paul@89 | 161 | |
paul@89 | 162 | """ |
paul@89 | 163 | Read a variable-length integer from 'bytes', starting at 'start', and |
paul@89 | 164 | returning a tuple containing a number and the first position after the |
paul@89 | 165 | number. |
paul@89 | 166 | """ |
paul@89 | 167 | |
paul@90 | 168 | length = len(bytes) |
paul@90 | 169 | if start == length: |
paul@90 | 170 | raise EOFError |
paul@90 | 171 | |
paul@89 | 172 | number = 0 |
paul@89 | 173 | digit = 0 |
paul@89 | 174 | while start < length: |
paul@89 | 175 | x = bytes[start] |
paul@89 | 176 | number += (x & 127) << digit |
paul@89 | 177 | digit += 7 |
paul@89 | 178 | start += 1 |
paul@89 | 179 | if not (x & 128): |
paul@89 | 180 | break |
paul@89 | 181 | return number, start |
paul@89 | 182 | |
paul@89 | 183 | # Sequence serialisation. |
paul@89 | 184 | |
paul@91 | 185 | def sequence_to_array(value, size, bytes): |
paul@89 | 186 | |
paul@91 | 187 | "Write the given sequence 'value' with the given 'size' to 'bytes'." |
paul@89 | 188 | |
paul@89 | 189 | if size: |
paul@91 | 190 | i = 0 |
paul@91 | 191 | limit = min(len(value), size) |
paul@91 | 192 | while i < limit: |
paul@91 | 193 | vint_to_array(value[i], bytes) |
paul@91 | 194 | i += 1 |
paul@91 | 195 | while i < size: |
paul@91 | 196 | vint_to_array(0, bytes) |
paul@89 | 197 | else: |
paul@89 | 198 | vint_to_array(value, bytes) |
paul@89 | 199 | |
paul@91 | 200 | def sequence_from_array(bytes, size, start=0): |
paul@89 | 201 | |
paul@89 | 202 | """ |
paul@91 | 203 | Read a sequence from 'bytes' having the given 'size', returning the sequence |
paul@91 | 204 | and the first position after the sequence. |
paul@89 | 205 | """ |
paul@89 | 206 | |
paul@89 | 207 | if size: |
paul@89 | 208 | j = 0 |
paul@89 | 209 | value = [] |
paul@89 | 210 | while j < size: |
paul@89 | 211 | v, start = vint_from_array_start(bytes, start) |
paul@89 | 212 | value.append(v) |
paul@89 | 213 | j += 1 |
paul@89 | 214 | return tuple(value), start |
paul@89 | 215 | else: |
paul@89 | 216 | return vint_from_array_start(bytes, start) |
paul@89 | 217 | |
paul@89 | 218 | # Variable-length integer cache initialisation. |
paul@89 | 219 | |
paul@55 | 220 | for i in xrange(0, 65536): |
paul@56 | 221 | bytes = array('B') |
paul@56 | 222 | _vint_to_array(i, bytes) |
paul@89 | 223 | vint_bytes_cache.append(bytes) |
paul@89 | 224 | vint_cache.append(bytes.tostring()) |
paul@51 | 225 | |
paul@44 | 226 | # vim: tabstop=4 expandtab shiftwidth=4 |