2
\$\begingroup\$

I decided to try make my own way to save normal python data yesterday after coming across the minecraft NBT format, it's more limited than cPickle but appears to produce shorter results and so far works reliably (if a little slower). It works on the type of the input, and is currently compatible with bool, int, str, dict, list, tuple, float, unicode, tuple, complex, long, and I couldn't think of anything else.

It's really easy to add in new types if you use the current things, like I'd forgotten about floats until the end, so I treated it as list(int, str) which worked fine. As the type ID is still stored as float, it sees its a float, so reads it like a list then puts it back together.

I'm not sure how many other similar projects are available, but I'm quite happy with the result.

It works by building a list of 1s and 0s for each item, which is in the format type_id + len_bytes + num_bytes + data. If the item is a list or dict, its num_bytes will refer to how many values it contains, and the code be repeated recursively.
type_id: What type the input is
len_bytes: How many bytes to look at for num_bytes. Because this number will always be quite low, it's stored as a bunch of 0s, ending with a 1.
num_bytes: How long the data is
data: The input stuff

As to why there is both len_bytes and num_bytes, for example, if the input has 255 bytes, the current way would result in 9 bits to say the length is 255, whereas having only 1 value would result in 255 bits to say the same thing.

When reading the data, instead of splitting the string up, it just uses offsets on which part to read. I'm not so happy with writing it but didn't know a better way, as I just store it as a string and basically use += 1 or += 0.

The en/decode functions work with the string of binary numbers, and the save and load functions just get it to and from a human readable form. For the record, I'm planning on having something in __init__, just haven't thought of what yet.

Example:

>>> StoreData().save([(42, -664426655, (55+5.2j)), 'grsg4', True, 46.4, {'key': [-0.0001, 'VALUE']}])
'SDrAhgIqGA0AYGA+QYKCs7k5s5oUDd2luDaBBgIuKAmhwEoG1srykCaBRgMAKCGBgYGJQVWQUxVRQA=='

>>> StoreData().load('SCrAxgIqGCSeaWJ+YE0CDARuUBMGgQYCBSgJkUFZ3JzZzQNoEGAi4oCaHASgbWyvKQJoFGAwAoIYGBgYlBVZBTFVFA==')
[(42, -64), 255000, 'grsg4', 'win', True, 46.4, {'key': [-0.0001, 'VALUE']}]

Code:

from __future__ import division
import math
import base64

def round_up(x):
    return int(x) if float(x) == float(int(x)) else int(x) + 1

def int_to_bin(x, padding=0):
    return ('{' + '0:0{}b'.format(padding) + '}').format(x)

def convert_to_bytes(x):
    x_len = len(x)
    if x_len % 8:
        x += '0' * (8 - x_len % 8)
    as_list = [int(x[i:i + 8], 2) for i in range(0, len(x), 8)]
    return ''.join(chr(i) for i in as_list)

def convert_from_bytes(x):
    return ''.join(int_to_bin(i, 8) for i in x)

class StoreData:
    TYPES = [bool, int, str, dict, list, tuple, float, unicode, tuple, complex]
    _TYPES = {long: int} #Treat the key type as the value type
    TYPE_LEN = round_up(math.log(len(TYPES), 2))

    def save(self, x):
        data = self._encode_value(x)
        data = base64.b64encode(convert_to_bytes(data))
        return data

    def load(self, x):
        x = convert_from_bytes(bytearray(base64.b64decode(x)))
        data, offset = self._decode_value(x)
        return data

    def _encode_value(self, x, _int_force_negative=False):
        item_type = type(x)
        if item_type in self._TYPES:
            item_type = self._TYPES[item_type]

        try:
            type_id = self.TYPES.index(item_type)
        except ValueError:
            raise ValueError("{} is not supported".format(item_type))
        encoded_string = int_to_bin(type_id, self.TYPE_LEN)

        #Get the length of the input
        if item_type == bool:
            item_bin = str(int(bool(x)))
            return encoded_string + '1' + item_bin

        if item_type in (int, str, unicode):
            if item_type == int:
                item_bin = int_to_bin(x).replace('-', '')

            elif item_type in (str, unicode):
                item_bin = ''.join(int_to_bin(ord(i), 8) for i in x)

            item_len = len(item_bin)
            num_bytes_int = (item_len - 1) // 8 + 1

        elif item_type in (float, complex):
            num_bytes_int = 2

        elif item_type in (list, tuple, dict):
            num_bytes_int = len(x)

        #Convert input length into number of bytes
        num_bytes_bin = int_to_bin(num_bytes_int)
        num_bytes_len = len(num_bytes_bin)
        if num_bytes_len % 8:
            num_bytes_bin = '0' * (8 - num_bytes_len % 8) + num_bytes_bin

        num_bytes_len = (len(num_bytes_bin) - 1) // 8 + 1

        encoded_string += '0' * (num_bytes_len - 1) + '1'
        encoded_string += num_bytes_bin

        #Convert input to bytes
        if item_type in (int, str):

            if item_type == int:
                encoded_string += '0' if x > 0 else '1'

            remaining_bits = item_len % 8
            if remaining_bits:
                item_bin = '0' * (8 - item_len % 8) + item_bin

            encoded_string += item_bin

        elif item_type == float:
            x_split = str(x).split('.')
            encoded_string += '0' if x > 0 else '1'
            encoded_string += self._encode_value(int(x_split[0]))
            encoded_string += self._encode_value(x_split[1])

        elif item_type == complex:
            encoded_string += self._encode_value(x.real)
            encoded_string += self._encode_value(x.imag)

        elif item_type in (list, tuple):
            for i in x:
                encoded_string += self._encode_value(i)

        elif item_type == dict:
            for k, v in x.iteritems():
                encoded_string += self._encode_value(k)
                encoded_string += self._encode_value(v)

        return encoded_string


    def _decode_value(self, x, start=0):

        #Find the item type
        start_offset = start
        end_offset = start_offset + self.TYPE_LEN
        type_id = int(x[start_offset:end_offset], 2)
        item_type = self.TYPES[type_id]

        #Find how many bytes the number of bytes is
        byte_length = 0
        while not int(x[end_offset + byte_length]):
            byte_length += 1
        byte_length += 1

        #Calculate the number of bytes
        start_offset = end_offset + byte_length
        end_offset = start_offset + byte_length * 8
        num_bytes = int(x[start_offset:end_offset], 2)

        #Decode the rest
        if item_type in (int, str, unicode):
            start_offset = end_offset

            if item_type == int:
                is_negative = int(x[start_offset])
                start_offset += 1

            end_offset = start_offset + num_bytes * 8
            data = x[start_offset:end_offset]

            if item_type == int:
                data = int(data, 2) * (-1 if is_negative else 1)

            elif item_type in (str, unicode):
                data = ''.join(chr(int(data[i:i + 8], 2)) for i in range(0, len(data), 8))

        elif item_type in (list, tuple):
            data = []
            for i in range(num_bytes):
                value, end_offset = self._decode_value(x, start=end_offset)
                data.append(value)
            if item_type == tuple:
                data = tuple(data)

        elif item_type == dict:
            data = {}
            for i in range(num_bytes):
                k, end_offset = self._decode_value(x, start=end_offset)
                v, end_offset = self._decode_value(x, start=end_offset)
                data[k] = v

        elif item_type == float:
            data = []
            is_negative = int(x[end_offset])
            end_offset += 1
            for i in range(2):
                value, end_offset = self._decode_value(x, start=end_offset)
                data.append(str(value))
            data = float('.'.join(data)) * (-1 if is_negative else 1)

        elif item_type == complex:
            data = []
            for i in range(2):
                value, end_offset = self._decode_value(x, start=end_offset)
                data.append(str(value))
            data = map(float, data)
            data = data[0] + data[1] * 1j

        elif item_type == bool:
            end_offset = start_offset + 1
            data = bool(int(x[start_offset:end_offset]))

        return data, end_offset
\$\endgroup\$
2
\$\begingroup\$

I guess this just for exercise, since there are already quite a number of ways to serialise Python data. And since cPickle is written in C it's unlikely that comparable performance will be achieved by pure (c)Python code.

Since this is Python code, the StoreData class should probably be hidden inside a function, unless you want to mock it for some reason. I.e. if there's no need for a class (and there's none because it's stateless), don't use one.

Also, since it claims to handle list objects, I'd consider the following behaviour a bug:

x = [42]
x[0] = x
StoreData().save(x)

Serialisers usually need to track object identities because of that.


Now for the code as presented:

  • round_up is math.ceil.
  • int_to_bin should probably use this SO answer instead.

There should probably also be a very long lists of tests to make sure that the serialisation works as expected and e.g. on both Python 2 and 3 for that matter.

In general overly long methods like _encode_value should be split into meaningful parts. As a reader it's very hard to keep track of all the different things that happen in both of them.

I'd suggest to splitting out size calculation, headers and any common code into methods.

Also, since this is Python 2, consider xrange and any other generators instead of allocating lists.


For possible extensions, consider the changes you'd need to make to support serialisation of custom classes / objects.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the tips, I was mainly curious if I could do something like this. The idea was for saving game data or something similar, so I'm not so bothered about recursive lists since they won't be used anyway (I'll see if I can get something figured out though), and with xrange and similar, all I'd need to do is figure out how to get the parameters from it, which I currently can't do. I'll see about splitting what I can into separate methods, and with the binary conversion, a while back I speed tested the {0:b}.format(x) vs bin(x)[2:] way and formatting was faster. \$\endgroup\$ – Peter Mar 10 '16 at 23:53
  • 1
    \$\begingroup\$ Since writing the question, I got an idea on how to use the class. I was thinking of having it directly linked with a file, so that its purpose is to initially read then hold the data for reading or editing, and then saves it back to disk with save(). I'm not attempting to do a full serialization thing anyway, I'd have no idea how to go about it for custom classes haha, all the current types have their own custom rules to work properly. \$\endgroup\$ – Peter Mar 10 '16 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.