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