README: library "Bin_prot" ************************** Copyright (C) 2008 Jane Street Holding, LLC (1) ===================================================== Author: Markus Mottl ====================== New York, 2007-10-12 ==================== 1 Directory contents *=*=*=*=*=*=*=*=*=*=* ------------------------------------------------------------------------------ - | CHANGES | History of code changes | ------------------------------------------------------------------------------ - | COPYRIGHT | Notes on copyright | ------------------------------------------------------------------------------ - | INSTALL | Short notes on compiling and | | | installing the library | ------------------------------------------------------------------------------ - | LICENSE | "GNU LESSER GENERAL PUBLIC LICENSE" | ------------------------------------------------------------------------------ - | LICENSE.Tywith | License of Tywith, from which Sexplib is derived | ------------------------------------------------------------------------------ - | Makefile | Top Makefile | ------------------------------------------------------------------------------ - | OCamlMakefile | Generic Makefile for OCaml-projects | ------------------------------------------------------------------------------ - | OMakefile | Ignore this file | ------------------------------------------------------------------------------ - | README.txt | This file | ------------------------------------------------------------------------------ - | lib/ | OCaml-library for type-safe binary protocol conversions| ------------------------------------------------------------------------------ - | lib_test/ | Test applications for the Bin_prot-library | ------------------------------------------------------------------------------ - 2 What is "Bin_prot" *=*=*=*=*=*=*=*=*=*=* This library contains functionality for reading and writing OCaml-values in a type-safe binary protocol. These functions are extremely efficient and provide users with a convenient and safe way of performing I/O on any extensionally defined data type. This means that functions, objects, and values whose type is bound through a polymorphic record field are not supported, but everything else is. As of now, there is no support for cyclic or shared values. Cyclic values will lead to non-termination whereas shared values, besides requiring significantly more space when encoded, may lead to a substantial increase in memory footprint when they are read back in. Currently only little endian (2) computer architectures are supported. Some architectures may potentially also suffer from data alignment issues with this library. Only Intel architectures are currently well-tested. Both 32bit and 64bit architectures are fully supported. 3 How can you use it? *=*=*=*=*=*=*=*=*=*=*= The API (.mli-files) in the library directory is fully documented. Module 'Common' defines some globally used types, functions, exceptions, and values. 'Nat0' implements natural numbers including zero. Modules 'Read_ml' and 'Write_ml' contain read and write functions respectively for all basic types and are implemented in OCaml as far as reasonable. If you only want to read or write single, basic, unstructured values, this module is probably the most efficient and convenient for doing this. Otherwise you should annotate your type definitions to generate type converters automatically (see below). The preprocessor in 'pa_bin_prot.ml' will then generate highly optimized functions for converting your OCaml-values to and from the binary representation. This automatically generated code will use functions in 'unsafe_common', 'unsafe_read_c' and 'unsafe_write_c', which handle the basic types with very low-level representations for efficiency. The module 'Size' allows you to compute the size of basic OCaml-values in the binary representations before writing them to a buffer. The code generator will also provide you with functions for your user-defined types. The modules 'Read_c' and 'Write_c' wrap the low-level converters for basic values to ones accessible easily in OCaml and vice versa, and export functions for wrapping user-defined converters. This should make it easy to add user-defined converters that interact with a specific representation, but you want to make them available to the other one quickly. The test applications in the distribution make use of these wrappers to verify the correctness of implementations for low-level (C) and high-level (OCaml) representations. The module 'Type_class' contains some extra definitions for type classes of basic values. These definitions can be passed to the function 'bin_dump' in module 'Utils' to marshal values into buffers of exact size using the binary protocol. However, if bounds on the size of values are known, it is usually more efficient to write them directly into preallocated buffers and just catch exceptions if the buffer limits are hit. That way one does not have to compute the size of the value, which can sometimes be almost as expensive as writing the value in the first place. The module 'Utils.ReadBuf' can be used to very efficiently read size-prefixed values as written by 'bin_dump' with the 'header_size' flag. This works even in the presence of partial data, e.g. when reading from streaming data coming from sockets, etc. In most cases, when a whole value fits into a buffer, this module will parse directly from the original buffer and only copy data to an internal one on partial reads. 3.1 Examples ============= E.g. given the following type definition: << type t = A | B with bin_io >> The above will generate the functions 'bin_size_t', 'bin_write_t', 'bin_read_t', and the type class values 'bin_writer_t', 'bin_reader_t' and 'bin_rw_t' . If you use the annotation 'bin_write' instead of 'bin_io', then only the write and size functions and their type class will be generated. Specifying 'bin_read' will generate the read functions and associated type class only. 'bin_type_class' will generate the combined type class only, thus allowing the user to easily define their own reader and writer type classes. The code generator may also generate low-level entry points used for efficiency or backtracking. The preprocessor can also generate signatures for conversion functions. Just add the wanted annotation to the type in a module signature for that purpose. 4 Specification of the Binary Protocol *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* The binary protocol does not contain any data other than the minimum needed to decode written out values. This means that the user is responsible for e.g. writing out the size of messages themselves if they want to be able to preallocate sufficiently sized buffers before reading. The basic OCaml-values are written out character-wise as described below using hex codes for the character encoding. Some of these values require size/length information to be written out before the value (e.g. for lists, hash tables, strings, etc.). Size information is always encoded as natural numbers ('Nat0.t'). The following definitions will be used in the encoding specifications below: - 'CODE_NEG_INT8' -> '0xff' - 'CODE_INT16' -> '0xfe' - 'CODE_INT32' -> '0xfd' - 'CODE_INT64' -> '0xfc' 4.1 Nat0.t =========== If the value is: - < '0x000000080' -> lower 8 bit of the integer. - < '0x000010000' -> 'CODE_INT16' followed by lower 16 bits of integer. - < '0x100000000' -> 'CODE_INT32' followed by lower 32 bits of integer. - >= '0x100000000' -> 'CODE_INT64' followed by all 64 bits of integer (3). Appropriate exceptions will be raised if there is an overflow, e.g. if a 64 bit encoding is read on a 32 bit platform, or if the 32 bit or 64 bit encoding overflowed the 30 bit or 62 bit capacity (4) of natural numbers on their respective platforms. 4.2 Unit values ================ - '()' -> '0x00' 4.3 Booleans ============= - 'false' -> '0x00' - 'true' -> '0x01' 4.4 Strings ============ First the length of the string is written out as a 'Nat0.t'. Then the contents of the string is copied verbatim. 4.5 Characters =============== Characters are written out verbatim. 4.6 Integers ============= This includes all integer types: 'int, int32, int64, nativeint'. If the value is positive (including zero) and if it is: - < '0x00000080' -> lower 8 bit of the integer. - < '0x00008000' -> 'CODE_INT16' followed by lower 16 bits of integer. - < '0x80000000' -> 'CODE_INT32' followed by lower 32 bits of integer. - >= '0x80000000' -> 'CODE_INT64' followed by all 64 bits of integer. If the value is negative and if it is: - >= '-0x00000080' -> 'CODE_NEG_INT8' followed by lower 8 bit of integer. - >= '-0x00008000' -> 'CODE_INT16' followed by lower 16 bits of integer. - >= '-0x80000000' -> 'CODE_INT32' followed by lower 32 bits of integer. - < '-0x80000000' -> 'CODE_INT64' followed by all 64 bits of integer. All of the above branches will be considered when converting values of type 'int64'. The case for 'CODE_INT64' will only be considered with types 'int' and 'nativeint' if the architecture supports it. 'int32' will never be encoded as a 'CODE_INT64'. Appropriate exceptions will be raised if the architecture of or the type requested by the reader does not support some encoding, or if there is an overflow (5). 4.7 Floats =========== Floats are written out according to the 64 bit IEEE 754 floating point standard, i.e. their memory representation is copied verbatim. 4.8 References and lazy values =============================== Same as the binary encoding of the value in the reference or of the value calculated lazily. 4.9 Option values ================== If the value is: - 'None' -> '0x00' - 'Some v' -> '0x01' followed by the encoding of 'v'. 4.10 Tuples and records ======================== Values in tuples and records are written out one after the other in the order as specified in the type specification without any extra information. Polymorphic record fields are supported unless a value of the type bound by the field were accessed, which would lead to an exception. 4.11 Sum types =============== Each tag is assigned an integer from 0 to n - 1 in exactly the same order as they occur in the type, where n is the number of sum tags in the type. If a value of this type needs to be written out, then if: - n <= 256 -> the integer associated with the tag is written out as one character (lower 8 bits). - n <= 65536 -> the integer associated with the tag is written out as two characters (lower 16 bits). Arguments to the tag are written out in the order of occurrence without any extra information. 4.12 Polymorphic variants ========================== The tags of these values are written out as four characters, more precisely as the 32 bit hash value computed by OCaml for the given tag. Any arguments associated with the tag are written out afterwards in the order of occurrence without any extra information. When polymorphic variants are being read, they will be matched in order of occurrence (left-to-right) in the type and depth-first in the case of included polymorphic types. The first type containing a match for the variant will be used for reading. 4.13 Lists and arrays ====================== For lists and arrays the length is written out as a 'Nat0.t' first, followed by all values in the same order as in the datastructure without any extra information. 4.14 Hash tables ================= First the size of the hash table is written out as 'Nat0.t'. Then the writer iterates over each binding in the hash table and writes out the key followed by the value without any extra information. 4.15 Bigarrays =============== First the dimension(s) are written out as 'Nat0.t'. Then the contents is copied verbatim. 4.16 Polymorphic values ======================== There is nothing special about polymorphic values as long as there are conversion functions for the type parameters. E.g.: << type 'a t = A | B of 'a with bin_io type foo = int t with bin_io >> In the above case the conversion functions will behave as if 'foo' had been defined as a monomorphic version of 't' with ''a' replaced by 'int' on the right hand side. 4.17 Abstract datatypes ======================== If you want to convert an abstract datatype, you will have to roll your own conversion functions. Use the functions in module 'Read_c' and 'Write_c' to map between low-level and high-level representations, or implement those manually for maximum efficiency. 5 Contact information *=*=*=*=*=*=*=*=*=*=*= In the case of bugs, feature requests and similar, you can contact us here: mmottl@janestcapital.com Up-to-date information concerning this library should be available here: http://www.janestcapital.com/ocaml Enjoy!! ----------------------------------------------------------------------------- This document was translated from LaTeX by HeVeA (6). -------------------------------------- (1) http://www.janestcapital.com (2) Endianness defines the byte order in which machine representations for integers and floating point numbers are written to main memory (3) Only supported on 64 bit platforms. (4) One bit is reserved by OCaml for GC-tagging, and the sign bit is lost. (5) An overflow can only happen with int values: one bit is reserved by OCaml for the GC-tag. (6) http://hevea.inria.fr/index.html