marcvs 1.1.5
A little Python basic types serialization library
Requires Python: >=3.6

# MARCVS SERIALIZATION PROTOCOL SPECIFICATION


## 1. Overview

Marcvs is a protocol to represent data as raw bytes, and retrieve it back from raw bytes (that is called "packing" and "unpacking" respectively).

It strives to provide universal means to store data of different datatypes (including capability of storing custom datatypes), at cost of slightly increased overall size of resulting byte sequences.


## 2. Definitions

**Bytecoder** - an entity used to pack/unpack a value of a particular type.

**Element** - a key-value pair, consisting of a name and a value.

**Packages** - a collection of elements.

**Pack** - serialize an element or a package into its' byte representation.

**Unpack** - restore an element or a package from a byte representation.

**Byte representation** - a representation of some value in bytes. The exact method of translation of a value to bytes is always specified in the text. In case of integers, if not specified, it's just the binary value of that integer stored in minimally needed amount of bytes.

**Bytecoded representation** - a specific variant of a byte representation of a value, obtained using the bytecoder corresponding to the type of said value.

**Succinct X** (for example, "succinct length") - a special way to represent an positive integer (for example, the length of a byte sequence that follows). For instance, there's a bytesequence consisting of 79 bytes, and we need to obtain its' succinct length. We first need to encode the length of the sequence (that is, 79) into bytes. Then, we find the minimum amount of bytes needed to represent 79 (since binary of 79 is 01001111, one byte will suffice). This minimum amount is called a "flag". When a parser reads the flag, it understands: the next 1 byte signifies X (in our case, the length of the the upcoming byte sequence); that X is 79, so the next 79 bytes are the byte sequence in question. In short, for X = 79 the succinct X will consist of 2 bytes: 1 (00000001) and 79 (01001111). This method of byte sequence length indication is short, flexible and easy for a parser to handle.


## 3. Bytecoder

A *bytecoder* is an entity (for example, a class), which provides the following:

1. Is tied to a particular type of data (that is, can detect whether data passed to it matches the type the bytecoder is designed to operate);

2. Has a method that returns a bytecoded representation of the data passed to it (if it is of valid type);

3. Has a method to retrieve the original object of that type from a previously packed bytecoded representation of that object.

There are **7 standard types/bytecoders** which **must** be present in every possible implementation of marcvs. The bytecoding rules of these types are strictly codified and must be followed, again, by every implementation, so that the basic datatypes were implementation-agnostic. Below are their names and correspondent numeric codes (type-codes):

* Bytes: 10 

* String: 11

* Integer: 12

* Float: 13

* None: 14

* Boolean: 15

* List: 16

* Dict: 17

Additionally, particular implemetations may provide their own stock types of bytecoders. To differentiate, their type-codes must be at least 3-digit. It is advisable that no implementations have overlapping type-codes for different types. It is also advisable that implementations that provide bytecoders for similar types also share the byte-coders.

For example, the first Python implementation of marcvs provides the following implementation-specific bytecoders:

* Date: 111

* Decimal: 112

* Tuple: 113

* Set: 114

* Datetime: 115

Now that these exist, it is preferrable for other implementations providing the same types to also share the type-code and the method used in this implementation.


## 4. Element

Each *element* is a key-value pair. The key must be a string, while the value can be of any type, recognizable by both packing and unpacking exemplars of the marcvs library.

"Recognizable" means that there must exist a bytecoder tied to the particular type of said value. It can be one of 7 standard types, or one of implementation-specific types, or a custom type with a bytecoder present in a marcvs extension of any kind.

### 4.1. Element packing algorithm

Every element can be packed into a byte sequence (a packed element). The resulting byte sequence must consist of the following values, glued together in direct succession:

1. Succinct length of the bytecoded representation of the element. The byte order here and after is big-endian;

2. The bytecoded representation of the element name using the string bytecoder (type-code 11);

3. 2-byte representation of the type-code;

4. Succinct length value of the bytecoded representation of the element value

5. The bytecoded representation of the element value (obtained through ann appropriate bytecoder).

The byte sequence that results from this algorithm is the byte representation of the element.

Unpacking is done by reversing this algorithm and using the provided succinct lengths to properly parse the byte representation and obtain the name and the bytecoded representation of the value, to then pass it to the bytecoder and obtain the object of a type, represented by the type-code.


## 5. Package

Every marcvs *instance* (called a "marcvs *package*") consists of package elements.

As such, a package is stored as a collection of elements (as an array of elements, or, optimally, as a key-value pair of element names and elements themselves for faster access).

### 5.1. Package packing algorithm

Every package can be packed into a byte sequence. The resulting byte sequence must consist of the following values, glued together in direct succession:

1. Succinct length of all the following byte sequences together;

2. SHA-256 hash of all of the packed elements glued together;

3. Succinct count of the elements of the package;

4. All of the packed elements glued together.

That way, when unpacking the package byte representation, the full length of the byte sequence comes first and it's possible to know in advance how many bytes are needed to unpack the package.

During the unpacking, it is possible to check the hash value of the byte sequence to figure out whether the sequence is broken (in this case the calculated hash value won't match the one stored in the representation itself).


## 6. Constraints

Largest possible type-code is 65535 (representable by 2 bytes).

Maximum length or count indicated by a succinct length or a succinct count is practically unlimited, so is the amount of information packable using marcvs.

Maximum depth level of nested containers in a marcvs element is dependent on the implementation, and is hardly reachable anyway.


## 7. Bytecoder specifications

### 7.1. Byte (type-code 10)

No conversion needed. The value is not converted and passed through this bytecoder as it is.

### 7.2. String (type-code 11)

The provided string is encoded into bytes using the UTF-8 encoding.

### 7.3. Integer (type-code 12)

The provided integer is converted to binary as a signed two's compliment.

### 7.4. Float (type-code 13)

The provided float is converted to binary according to the IEEE 754 standard (double-precision, big-endian byte order).

### 7.5. None (type-code 14)

None/Null values are represented as an empty byte sequence.

### 7.6. Boolean (type-code 15)

True is bytecoded into a 1. False is bytecoded into a 0 (both in binary).

### 7.7. List/Array (type-code 16)

The bytecoded representation of a list or an array consists of the following (consequtively for each list member):

* The type-code of the list member inferred from its' type;

* Succinct length of the bytecoded representation of the list member

* The bytecoded representation of the list member

### 7.8. Dictionary (type-code 17)

The bytecoded representation of a dictionary consists of the following (consequtively for each entry in the dictionary):

* The type-code of the entry key inferred from its' type;

* Succinct length of the bytecoded representation of the entry key

* The bytecoded representation of the entry key

* The type-code of the entry value inferred from its' type;

* Succinct length of the bytecoded representation of the entry value

* The bytecoded representation of the entry value