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