1.1 --- a/iixr/data.py Thu Feb 03 01:26:35 2011 +0100
1.2 +++ b/iixr/data.py Mon Feb 07 02:05:38 2011 +0100
1.3 @@ -1,7 +1,7 @@
1.4 #!/usr/bin/env python
1.5
1.6 """
1.7 -Variable-length integer functions.
1.8 +Data representation functions.
1.9
1.10 Copyright (C) 2009, 2010, 2011 Paul Boddie <paul@boddie.org.uk>
1.11
1.12 @@ -19,9 +19,76 @@
1.13 """
1.14
1.15 from array import array
1.16 +import operator
1.17
1.18 -vint_cache = {}
1.19 -vint_bytes_cache = {}
1.20 +# High-level representations.
1.21 +
1.22 +def convert_sequence(values, op):
1.23 + if values:
1.24 + new_values = list(values)
1.25 + last = new_values[0]
1.26 + i = 1
1.27 + length = len(new_values)
1.28 + while i < length:
1.29 + current = new_values[i]
1.30 + new_values[i] = op(new_values[i], last)
1.31 + last = current
1.32 + i += 1
1.33 +
1.34 +def add_seq_monotonic(x, y):
1.35 + return op_seq_monotonic(x, y, operator.add)
1.36 +
1.37 +def sub_seq_monotonic(x, y):
1.38 + return op_seq_monotonic(x, y, operator.sub)
1.39 +
1.40 +def op_seq_monotonic(x, y, op):
1.41 + return tuple([op(a, b) for a, b in zip(x, y)])
1.42 +
1.43 +def add_seq(x, y):
1.44 + length = min(len(x), len(y))
1.45 + seq = list(x)[:length]
1.46 + i = 0
1.47 + while i < length:
1.48 + if x[i] != 0:
1.49 + seq[i] = x[i] + y[i]
1.50 + break
1.51 + seq[i] = y[i]
1.52 + i += 1
1.53 + return tuple(seq)
1.54 +
1.55 +def sub_seq(x, y):
1.56 + length = min(len(x), len(y))
1.57 + seq = list(x)[:length]
1.58 + i = 0
1.59 + while i < length:
1.60 + replacement = x[i] - y[i]
1.61 + if replacement != 0:
1.62 + seq[i] = replacement
1.63 + break
1.64 + seq[i] = 0
1.65 + i += 1
1.66 + return tuple(seq)
1.67 +
1.68 +def is_sequence(value):
1.69 + return isinstance(value, (list, tuple))
1.70 +
1.71 +def get_monotonic_adder(value):
1.72 + return is_sequence(value) and add_seq_monotonic or operator.add
1.73 +
1.74 +def get_monotonic_subtractor(value):
1.75 + return is_sequence(value) and sub_seq_monotonic or operator.sub
1.76 +
1.77 +def get_adder(value):
1.78 + return is_sequence(value) and add_seq or operator.add
1.79 +
1.80 +def get_subtractor(value):
1.81 + return is_sequence(value) and sub_seq or operator.sub
1.82 +
1.83 +# Low-level representations.
1.84 +# Variable-length integer functions.
1.85 +
1.86 +vint_cache = []
1.87 +vint_bytes_cache = []
1.88
1.89 def vint(number):
1.90
1.91 @@ -29,7 +96,7 @@
1.92
1.93 try:
1.94 return vint_cache[number]
1.95 - except KeyError:
1.96 + except IndexError:
1.97 if number >= 0:
1.98 bytes = array('B')
1.99 _vint_to_array(number, bytes)
1.100 @@ -46,7 +113,7 @@
1.101
1.102 try:
1.103 bytes += vint_bytes_cache[number]
1.104 - except KeyError:
1.105 + except IndexError:
1.106 if number >= 0:
1.107 _vint_to_array(number, bytes)
1.108
1.109 @@ -75,6 +142,28 @@
1.110 number += bytes.pop() & 127
1.111 return number
1.112
1.113 +def vint_from_array_start(bytes, start):
1.114 +
1.115 + """
1.116 + Read a variable-length integer from 'bytes', starting at 'start', and
1.117 + returning a tuple containing a number and the first position after the
1.118 + number.
1.119 + """
1.120 +
1.121 + number = 0
1.122 + length = len(bytes)
1.123 + digit = 0
1.124 + while start < length:
1.125 + x = bytes[start]
1.126 + number += (x & 127) << digit
1.127 + digit += 7
1.128 + start += 1
1.129 + if not (x & 128):
1.130 + break
1.131 + return number, start
1.132 +
1.133 +# String serialisation.
1.134 +
1.135 def string_to_array(s, bytes):
1.136
1.137 "Write the given string 's' to 'bytes'."
1.138 @@ -82,10 +171,45 @@
1.139 vint_to_array(len(s), bytes)
1.140 bytes.fromstring(s.encode("utf-8"))
1.141
1.142 +# Sequence serialisation.
1.143 +
1.144 +def sequence_to_array(value, bytes):
1.145 +
1.146 + "Write the given sequence 'value' to 'bytes'."
1.147 +
1.148 + size = is_sequence(value) and len(value) or 0
1.149 + vint_to_array(size, bytes)
1.150 + if size:
1.151 + for a in value:
1.152 + vint_to_array(a, bytes)
1.153 + else:
1.154 + vint_to_array(value, bytes)
1.155 +
1.156 +def sequence_from_array(bytes, start=0):
1.157 +
1.158 + """
1.159 + Read a sequence from 'bytes', returning the sequence and the first position
1.160 + after the sequence.
1.161 + """
1.162 +
1.163 + size, start = vint_from_array_start(bytes, start)
1.164 + if size:
1.165 + j = 0
1.166 + value = []
1.167 + while j < size:
1.168 + v, start = vint_from_array_start(bytes, start)
1.169 + value.append(v)
1.170 + j += 1
1.171 + return tuple(value), start
1.172 + else:
1.173 + return vint_from_array_start(bytes, start)
1.174 +
1.175 +# Variable-length integer cache initialisation.
1.176 +
1.177 for i in xrange(0, 65536):
1.178 bytes = array('B')
1.179 _vint_to_array(i, bytes)
1.180 - vint_bytes_cache[i] = bytes
1.181 - vint_cache[i] = bytes.tostring()
1.182 + vint_bytes_cache.append(bytes)
1.183 + vint_cache.append(bytes.tostring())
1.184
1.185 # vim: tabstop=4 expandtab shiftwidth=4