package bstr

Bstr, Slice & Bin

This small set of libraries offers a homogeneous API between 2 types and their derivations with the slice type, as well as a small DSL for decoding "packets" (such as ARP or DNS) without too much difficulty.

The aim is to homogenize the 2 types bytes and bigstring and to derive them with a slice type, giving the user all the levers needed to manipulate byte sequences, whether in the form of a bigstring or bytes. The slice view avoids copying when it comes to decoding a packet and extracting a sub-part. The slice also applies to bigstrings, whose Bigarray.Array1.sub is more expensive.

This set of libraries is a synthesis of astring (which offers a range of useful functions as well as slice), cstruct (which offers a similar API for bigstrings), bigstringaf (which offers some other useful functions), the standard OCaml library and repr for decoding/encoding these values into OCaml records/variants.

About API

Here is an overview of the functions offered by bstr compared to other libraries:

Fast sub

sub is perhaps the most useful operation for a bigarray. In fact, unlike bytes and strings, sub offers a view (equivalent or smaller) of a bigarray without making a copy. If, for example, you need to decode^1 a large sequence of bytes (without having the notion of a "stream"), it may be useful to use the sub operation to decode the information byte by byte and avoid copying throughout the decoding process.

The implementation of sub proposed by Bstr is a little different from that of the standard OCaml library. In fact, it is specialized for a bigarray of dimension 1 containing bytes. In fact, the Bigarray.Array1.sub function is a little more generic and Bstr takes the opportunity to "specialize" the function according to our type.

However, according to the representation proposed by Cstruct, Cstruct.sub remains the fastest operation compared to Bstr and Bigstringaf. If you want to have the same performance as Cstruct, the specialized Slice module for Bstr.t values is equivalent.

Here is a comparative table of the sub function between all implementations (AMD Ryzen 9 7950X 16-Core Processor):

Fast blit

blit from a string or a bytes is a little faster than Bigstringaf and Cstruct. The difference basically lies in the fact that Bstr.t uses other "tags" to describe the FFI with the C memcpy function (specifically the [@untagged] tag).

Here is a comparative table of the blit_from_string function between all the implementations:

mmaped or not? (GC lock)

There are 2 ways to copy bytes between two bigarrays:

• the "mmaped" version ({memcpy,memmove}_mmaped)
• the simple version ({memcpy,memmove})

The first is quite specific because it releases the GC lock after a certain number of bytes (4096) have been copied. This can be advantageous if you want to make a large copy between two bigarrays in parallel in a Thread.

If we specify mmaped, it is because the copy between two bigarrays, one of which may come from Unix.map_file, can also take time (and we may want to do it in parallel in a Thread) since it involves reading/writing on the disk.

let copy_to_file bstr filename () =
  let len = Bstr.length bstr in
  let fd = Unix.openfile filename Unix.[ O_WRONLY ] 0o644 in
  let dst = Unix.map_file fd Bigarray.char Bigarray.c_layout false [| len |] in
  let dst = Bigarray.array1_of_genarray dst in
  Bstr.memcpy_mmaped bstr ~src_off:0 dst ~dst_off:0 ~len

let () =
  let th = Thread.create (copy_to_file bstr filename) () in
  (* do something else in true parallel of [copy_to_file]. *)
  (* the GC will not interrupt [th] during the copy. *)
  Thread.join th

The simple version does not release the GC lock and only applies the desired function (memmove or memcpy).

memmove or memcpy?

Bstr.blit always uses the memmove function. However, it can be advantageous to use memcpy in a fairly specific case: when you know that the source refers to a memory area that is not shared with the destination.

To find out, you can use the Bstr.overlap function, which checks whether or not the two bigarrays given have a common memory area.

Fast decoder

The bin package is a package that allows binary data to be encoded and decoded according to a format that can be described in OCaml. For example, here is how an IPv4 packet can be described:

type ipv4 =
  { version: int
  ; ihl: int
  ; tos: int
  ; total_length: int
  ; id: int
  ; flags: int
  ; offset: int
  ; ttl: int
  ; protocol: int
  ; chk: int
  ; src: int32
  ; dst: int32 }

let ipv4 =
  let fn vihl tos total_length id ff ttl protocol chk src dst =
    let version = vihl lsr 4 in
    let ihl = vihl land 0x0f in
    let flags = ff lsr 13 in
    let offset = ff land 0x1fff in
    { version; ihl; tos; total_length; id; flags; offset; ttl; protocol; chk; src; dst }
  in
  let open Bin in
  record ~name:"ipv4" fn
  |+ field ~name:"vihl" uint8 (fun t -> (t.version lsl 4) lor t.ihl)
  |+ field ~name:"tos" uint8 (fun t -> t.tos)
  |+ field ~name:"total_length" beuint16 (fun t -> t.total_length)
  |+ field ~name:"id" beuint16 (fun t -> t.id)
  |+ field ~name:"flags_and_offset" beuint16 (fun t -> (t.flags lsl 13) lor t.offset)
  |+ field ~name:"ttl" uint8 (fun t -> t.ttl)
  |+ field ~name:"protocol" uint8 (fun t -> t.protocol)
  |+ field ~name:"checksum" beuint16 (fun t -> t.chk)
  |+ field ~name:"src" beint32 (fun t -> t.src)
  |+ field ~name:"dst" beint32 (fun t -> t.dst)
  |> sealr

The advantage of such an approach is that offsets and bound checks can be verified automatically rather than using a manual approach. However, deriving such a description incurs costs that we would not incur if we were to perform the decoding manually (at the very least, OCaml optimises manual code better than the decoder generated from such a description).

This is an approach found in repr, data-encoding and ocaml-wire. In particular, bin is based on the approach taken by repr. However, bin aims to be highly efficient and relies on two optimisations:

1. avoiding caml_apply when constructing user values
2. performing fusion^2 for values of type {,u}int8, {,u}int16{be,le,ne} and int{32,64}{be,le,ne}.

Here are the results when decoding an IPv4 packet: