= Bithenge =

[[PageOutline(2-3)]]

Bithenge consists of a library and tools that make working with structured
binary data easier. The project was started by Sean Bartell as part of
[wiki:GSOC Google Summer of Code 2012] to address #317. The code is at
[https://code.launchpad.net/~wtachi/helenos/bithenge lp:~wtachi/helenos/bithenge]
and periodic updates are posted to
[http://lists.modry.cz/cgi-bin/listinfo/helenos-devel HelenOS-devel].

Bithenge is intended to be a general‐purpose library with a variety of uses,
but only one tool has been implemented so far. It is a program that reads a
script file describing a binary format, applies it to binary data, and prints
the decoded result.

== Quick start ==

The Bithenge source code is in `uspace/app/bithenge` and `uspace/lib/bithenge`
in the bithenge branch. It is automatically built in HelenOS to create the
`bithenge` application. For Linux, it can be built by running
`make -f Makefile.linux`, first in `uspace/lib/bithenge` and then in
`uspace/app/bithenge`.

The program can be run with `bithenge <script file> <binary file>` to decode a
file. There are some example files in
[https://bazaar.launchpad.net/~wtachi/helenos/bithenge/files/head:/uspace/dist/src/bithenge uspace/dist/src/bithenge];
see the [Bithenge/Syntax syntax documentation].

== Overview ==

=== Trees ===

Bithenge represents all data in the form of a data structure called a “tree,”
similar to the data structure represented by JSON. A tree consists of a boolean
node, integer node, string node, or blob node, or an internal node with
children. A boolean node holds a boolean value, an integer node holds a signed
integer, and a string holds a Unicode string.

A blob node represents an arbitrary sequence of raw bytes or bits. Blob nodes
are polymorphic, allowing any source of raw binary data to be used. Bithenge
includes blob node implementations for in‐memory buffers, files, and block
devices. An implementation has also been written that reads another task’s
virtual memory, but it hasn’t been committed because it’s unclear whether it
will be useful in its current form.

An internal node has an arbitrary number of children, each with a unique key.
The key can be any node other than an internal node. Arrays can be represented
by internal nodes with integer keys starting at 0. The tree node can provide
children in an arbitrary order; the order will be used when displaying the
tree, but should have no semantic significance. Internal nodes are polymorphic
and can delay creation of child nodes until necessary, so keeping the whole
tree in memory can be avoided.

Internal nodes are currently responsible for freeing their own children. In the
future, it should be possible for there to be multiple references to the same
node, but it isn’t clear whether this should be implemented with symbolic
links, an acyclic graph with reference counting, or a full graph.

Note that all interpreted data is represented in Bithenge with nodes.
Therefore, the word “blob” usually refers to a blob node, and so on.

A decoded tree for a FAT filesystem might look something like this:
{{{
○───bits─▶16
│
├───fat──▶○
│         ├───0───▶0xfff0
│         ├───1───▶0xffff
│         └───2───▶0x0000
│
└───root──▶○
           ├───0───▶○
           │        ├───name───▶README.TXT
           │        └───size───▶0x1351
           │
           └───1───▶○
                    ├───name───▶KERNEL.ELF
                    └───size───▶0x38e9a2
}}}

=== Transforms ===

A transform is a function from an input tree and zero or more argument trees to
an output tree. One example is `uint32le`, which takes a 4‐byte blob node as
the input tree and provides an integer node as the output tree. Another example
is `uint_le(len)`, which takes a bit blob node as the input tree and an integer
node as an argument tree, and produces an integer node as the output tree.

Several transforms, including `uint32le` and `uint_le(len)`, are built in to
Bithenge. More complicated transforms can be created by a format provider, as
explained below. For instance, the
[https://bazaar.launchpad.net/~wtachi/helenos/bithenge/view/head:/uspace/dist/src/bithenge/fat.bh fat.bh]
file contains a `fat_filesystem` transform that takes a byte node as the input
tree and produces a complex output tree with various decoded information about
the filesystem.

=== Data providers ===

Generally speaking, a data provider is anything that provides data from outside
Bithenge in the form of a tree. The Bithenge library includes functions for
various data providers, and can automatically create a tree from a prefixed
string:

||= Prefix =||= Tree Type =||= Example =||= Description =||
|| `file:`  || Byte blob node || `file:/textdemo` || Read the contents of a file. This is the default if no prefix is used. ||
|| `block:` || Byte blob node || `block:bd/initrd` || Read the contents of a block device. (HelenOS only.) ||
|| `hex:`   || Byte blob node || `hex:01000000` || Use a string of hexadecimal characters to create a blob node. ||

These prefixes can also be used with the `bithenge` program.

=== Format providers ===

A format provider creates transforms based on external data, or vice versa.
The only implemented format provider is the script parser, which creates a
transform from a file written in the
[Bithenge/Syntax Bithenge scripting language]. A future idea is the DWARF
format provider, which would read DWARF information from an executable and
create a transform that could be applied to a task memory dump.

=== Library ===

The Bithenge library includes APIs for working with trees and creating and
applying transforms. It also contains the built‐in transforms, data providers,
and format providers. The [Bithenge/Library library overview] describes the API
and conventions used; detailed documentation is included in Doxygen comments in
the source.

=== Clients ===

A client is any program that provides a user interface to the Bithenge library.
The only implemented client is the simple `bithenge` program described above.
In the future, there could be an interactive browser for decoded trees, or a
program to generate C code based on a script file.

== New design ==

I am currently working on a new constraint‐based design, where the format
specification consists of statements that must be true about the raw and
interpreted data, and the program figures out how to solve these constraints.
This design should make a number of things possible, particularly editing and
bidirectional encoding/decoding. As of December 2012, I have a proof‐of‐concept
that generates Python code to encode or decode a trivial structure, and I’m
working on improving it.

== More information ==

* Bithenge/Syntax: the syntax of Bithenge scripts.
* Bithenge/Library: the library API, conventions, and internals.
* Bithenge/Design: design decisions, limitations, ideas, and inspirations.