On 2/26/2012 11:33 AM, Martin Baldan wrote:

Guys, I find these off_topic comments (as in not strictly about my idst compilation problem) really interesting. Maybe I should start a new thread? Something like «how can a newbie start playing with this technology?». Thanks!

well, ok, hopefully everyone can tolerate my OT-ness here...
(and hopefully, my forays deep into the land of trivia...).

well, ok, I am not personally associated with VPRI though, mostly just lurking and seeing if any interesting topics come up (but, otherwise, am working independently on my own technology, which includes some VM stuff and a 3D engine).

( currently, no code is available online, but parts can be given on request via email or similar if anyone is interested, likewise goes for specs, ... )

recently, I had worked some on adding networking support for my 3D engine, but the protocol is more generic (little about it is particularly specific to 3D gaming, and so could probably have other uses).

internally, the messaging is based on lists / S-Expressions (it isn't really clear which term is better, as "lists" is too generic, and S-Expressions more refers to the syntax, rather than their in-program representation... actually it is a similar terminology problem with XML, where the term may ambiguously either be used for the textual representation, or for alternative non-text representations of the payload, IOW: "Binary XML", and similar).

but, either way, messages are passed point-to-point as lists, typically using a structure sort of like:
(wdelta ... (delta 315 (org 140 63 400) (ang 0 0 120) ...) ...)

the messages are free-form (there is no "schema", as the system will try to handle whatever messages are thrown at it, but with the typical default behavior for handlers of ignoring anything which isn't recognized, and the protocol/codec is agnostic to the types or format of the messages it is passing along, provided as long as they are built from lists or similar...).

as-is, these expressions are not "eval'ed" per-se, although the typical message handling could be itself regarded as a crude evaluator (early versions of my original Scheme interpreter were not actually all that much different). theoretically, things like ASTs or Scheme code or whatever could be easily passed over the connection as well.

in-program, the lists are dynamically typed, and composed primarily of chains of "cons cells", with "symbols", "fixnums", "flonums", "strings", ... comprising most of the structure (these are widely used in my projects, but aren't particularly unique to my project, though seemingly less well-known to most more mainstream programmers).

as-is, currently a small subset of the larger typesystem is handled, and I am currently ignoring the matter of list cycles or object-identity (data is assumed acyclic, and currently everything is passed as a copy).

at the high-level, the process currently mostly looks like:
process A listens on a port, and accepts connections, and then handles any messages which arrive over these connections, and may transmit messages in response.
process B connects to A, and may likewise send and receive messages.

currently, each end basically takes whatever messages are received, and passes them off to message-processing code (walks the message expressions and does whatever). currently, queues are commonly used for both incoming and outgoing messages, and most messages are asynchronous.

neither end currently needs to worry about the "over-the-wire" format of these lists. a system resembling XMPP could probably also be built easily enough (and may end up being done anyways).

lists were chosen over XML mostly for sake of them being more convenient to work with.

actually, I did something similar to all this long ago, but this effort fell into oblivion and similar had not been done again until fairly recently (partly involving me reviving some old forgotten code of mine...).

now, on to the protocol itself:
it is currently built over raw TCP sockets (currently with "nodelay" set);
messages are encoded into "lumps", which are basically tags followed by message data (lumps are also used for stream-control purposes, and may relay other types of messages as well).

currently, a system of tags resembling the one in JPEG is used, except that the tags are 4 bytes (with 3 bytes of "magic" and 1 byte to indicate the tag type, a longer magic was used to reduce the number of times it would need to be escaped in a bitstream). currently, no length is used (instead, one knows a complete message lump has been received because the end-tag is visible). this currently means an 8 byte overhead per-message lump due to tags (there are also Deflate lumps, but these have the added overhead of a decoded-length and a checksum, needed for technical reasons, leading to 16 bytes of overhead).

message lumps are themselves a bitstream, and are currently built out of a collection of "minilumps", currently each indicated via a 4 bit tag (there are no lengths or end markers here). minilumps currently do things like indicate the Huffman tables, and also give the individually-coded messages (there may be multiple physical messages per a given message-lump).

the Huffman tables resemble the format used in Deflate, only using Rice codes to encode the table of symbol lengths (seems to work well enough, Deflate used Huffman coding on the Huffman table), and with a few minor differences in the RLE scheme.

values are encoded using a mix of "command tags" and an MRU+MTF scheme (recently coded values may be reused from a table). strings (strings, symbols, keywords, ...) and data-members (byte arrays, ...) use an LZ77 variant (itself very similar to how data is represented in Deflate).

note that, for data members, the MRU serves a similar role to that of the "sliding window" in LZ77 (I may consider dropping MTF due to various reasons though, and maybe add a data-member analogue of an LZ-run).

currently, 3 Huffman tables are used, one for command-tags, another for literal bytes (in strings and data members), and the 3rd for distances and integers (fixnums, flonums, ...). most integer-like values are coded using a similar prefix+extra-bits scheme to that used in Deflate. floating-point values are encoded as a pair of integers (mantissa+exponent, although the definition is "m*2^e", with the mantissa as an integer rather than a normalized value, so "1,8" will encode "256.0").

all of this leads to lower encoded messages sizes than what I was getting by serializing the lists into textual S-Expression form, and then applying Deflate to the result (and is semantically equivalent).

most of the added compression is most likely due to the ability of the scheme to make use of additional knowledge about the data being compressed, since data members can be encoded directly, rather than the compressor having to deal with them as strings of ASCII characters encoding the data members.

not that Deflate was doing all that poorly either though.

theoretically also possible though (and technically simpler) is to flatten the S-Expressions into a byte-based binary format and then feed this through Deflate (with likely intermediate results).

the main reason for trying to compress the data is mostly so that it has a much lower chance of bogging down the user's internet connection or similar (increasing the risk for network stalls and poor performance).

granted, yes, this is probably overkill.

but, it works...

time to implement support for this (and get networking for my 3D engine to work, in general) was a little over 1 week.

or such...

fonc mailing list

Reply via email to