Frame-based implementation of GMQ binary format

[divanchykhin]

To solve, among others, problems with extendable structure skipping (in particular, vector elements) in case of GMQ, its binary format is to be based on the following principles:

1. Basic units are binary representation of IDL elementary types (such as integers, strings, reals, etc).
2. Basic units are organized in frames; the whole message is a sequence of frames.
   2.1. Frame size must not exceed a predefined value
3. Each frame has its header that tells its size and flags; header encoding allows compact representation (e.g., utf8-like) in case of small sizes, but does not require it (that is, in all cases to continue header parsing it suffices to parse previous bytes). Exact encoding algorithm is TBD.
4. Currently the following flags are seen:
   4.1. frame sequence termination flag
   4.2. frame-size-from-its-content flag (used in case of long strings, blobs, etc that tell their size themselves)
5. When composing,
   5.1. in general, it is Composer's decision to begin and end a frame while writing an entry of elementary type (based on a number of bytes remaining in frame up to its maximal size, number of bytes that might be necessary to write an entry, etc);
   5.2. in particular, it can be terminated base on an caller's request;
   5.2.1. in this case caller may request to add 'frame sequence termination flag' to the frame header.

Important usage point: when an extendable structure has been composed, caller requests to terminate a frame with adding 'frame sequence termination flag' flag; then, while parsing, to skip this structure meand to follow until a frame with 'frame sequence termination flag'

[nobugs-hare]

Proposed formalisms (to supersede logic described above):
. General
.1 Most of the logic described here is NOT specific to byte-oriented GMQ format; whenever we are specifying GMQ-specific implementation details, they are clearly marked with [GMQ]

I. IDL
I.1 IDL allows adding fields while remaining compatible
I.2 Each compatible extension of IDL MUST include FENCE marker before fields-being-added (otherwise new IDL is not compatible with the old one)

II. Composing
II.1 All stream consists from frames following each other; each frame is either an "open frame" or a "field frame"
II.1.1 "open frame" is a frame with a fixed_upper_bound on size ([GMQ]:around 8K); it may contain multiple fields.
II.1.2 "field frame" is used for large fields such as strings and blobs - which otherwise won't fit into "open frame". NB: small-size strings and blobs MAY
II.1.3 Each frame has: (a) flag if it is "open frame" or "field frame"; (b) flag if it is a "first field" (in an EXTENSIBLE IDL struct); (c) flag if it is a "last field" (in an EXTENSIBLE struct).
II.2 Rule 1: whenever a FENCE or end-of-EXTENSIBLE-struct is encountered, composer MUST end current frame.
II.3 Each beginning of EXTENSIBLE struct MUST begin with a frame with "first field" flag set; each end of EXTENSIBLE struct MUST end with a frame with "last field" flag set; as long as Rule 1 is complied with, it is perfectly ok to have the same frame with both "first field" and "last field" flags set
II.4 Implementation-wise, composer has to maintain buffer with size of at least fixed_upper_bound (+ size of open_frame_header field); it also has to be able to rewrite open_frame_header field into the beginning of the buffer.
II.5 If there is an EXTENSIBLE struct is the last field within another EXTENSIBLE struct, composer will need to encode an empty open frame ([GMQ): probably "small" one, see below) merely to specify "last field" flag twice in a row; the same stands for an empty open frame merely to specify "first field" flag twice in a row (in case of EXTENSIBLE struct as the first field within another EXTENSIBLE struct).
II.6 [GMQ]: open_frame_header field has fixed size of 2 bytes - including 3 flags described above (within the 1st byte), and open_field_size; hence the 8K (=2^(16-3)) restriction on the open frame size. Field frames headers are encoded with the first byte having the "field frame" flag - and "first field" and "last field" flags set as appropriate; remaining 5 bits of the 1st byte - and subsequent bytes as necessary - are used to encode frame size in UTF8-like manner. NB: I still prefer explicit frame size to using field-size instead, as (a) we're speaking about REALLY LARGE fields (8K+), so overhead is negligible (2 bytes extra per 8K is 0.025% - I can live with it); but (b) we'll get better layering (frames become independent), and (c) we'll have an ability to add variable-size fields later without breaking compatibility (it is unlikely we'll need it, but it won't hurt to have such potential).

III. Parsing
III.1 whenever parser reaches beginning of an EXTENSIBLE struct, it checks that it corresponds to a frame with "first frame" flag set - otherwise the stream is malformed.
III.2 whenever parser reaches the end of current EXTENSIBLE struct, it does the following:

• checks that it has reached the end of the current frame (if not - it is malformed stream because of Rule 1)
• if the current frame (the one which just ended) is a "last frame" - we're done with parsing current EXTENSIBLE struct, and should proceed to parsing the next field. NB - this rule MAY be handled as a special case within more generic logic described below.
• if the current frame (the one which just ended) is NOT a "last frame" - we have to (a) init variable depth_counter to 1; (b) start skipping frames, adding 1 to depth_counter for frames labeled as "first frame" and deducting 1 from depth_counter for frames labeled as "last frame"; when depth_counter reaches 0 - we're done with parsing current EXTENSIBLE struct, and should proceed to parsing the next field

[nobugs-hare]

Additional proposal for [GMQ] encoding:

• first byte of frame has first 2 bits as "first frame" and "last frame"
• if the 3rd bit of the first byte is 1 - then it is a "small open frame" , with its size (up to 31) encoded in remaining 5 bits of the first byte; these MAY be used to optimize stream in case of really-small chunks (either encoding small single-field chunks, or moving of up-to-31 bytes in the composer buffer, which is still rather cheap)
• if the 3rd bit if the first byte is 0 - then 4th bit indicates if it is a "large open frame" or "field frame"
  • if it is a field frame - then remaining 4 bits - plus whatever bits in subsequent bytes - are used to encode field-frame size in a UTF8-like manner (we can assume that 4 bits and next byte are always present, so "this is last byte" UTF8 flag won't need to be present in the remaining-4-bits)
  • if it is a large open frame - then remaining 4 bits + 8 bits of 2nd byte are used to encode field-frame size (and open-field size limit is 4K then).