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