Random-access Decoder

Message ID
DKIM signature
Download raw message
Hello ERIS,

The Guile (https://codeberg.org/eris/guile-eris/) and OCaml
(https://codeberg.org/eris/ocaml-eris/) implementations now support
random-access decoding. That means that users can read specific
bytes at given offsets from some encoded content while de-referencing
only a minimal amount of blocks.

Applications include seeking in audio/video or detecting file-type with
some magic bytes at fixed position. See also an initial draft of ERIS-FS
(https://codeberg.org/eris/eer/pulls/2) - an encoding of a file system
that is optimized for ERIS (allows de-duplication of files) which
requires such random-access.

The exposed API includes following functions:

- Position(): Return the current position in encoded content
- Seek(p): Move decoder to given position
- Read(n): Read n bytes from current position
- Lenghth(): Return lenght of encoded content

The first three functions allow random-access. The `Length` function
computes the length of the encoded content by descending the tree at the
right-most nodes. This is something that requires access to the ERIS
tree, so it should implemented and exposed in an ERIS library API. If
such a functionality is not exposed, computing the length of encoded
content is very inefficient (read until end-of-content is reached).

I have added similar notes to the specification document [0].

Both implementations (Guile and OCaml) are based on Zippers (as
previously described [1]). These are purely functional/immutable data
structures. One very cool thing about this is that it is very easy to
implement concurrent look-ahead readers that de-reference blocks ahead
of the main reader. The only thing that needs to be done is to
cache/memoize block dereferences.

Implementing a random-access decoder is probably the most
challenging/interesting part of implementing ERIS and I hope to have
piqued your interest to implement a random-access decoder in your
favorite language! I very much look forward to your thoughts, ideas and
implementations. In particular, I would be very interested in how an
implementation would look in a more imperative language.

Happy Hacking,

[0] https://codeberg.org/eris/spec/commit/80083e4fc77c89a5d9b216c7fcb0cd740f67f2c1
[1] https://lists.sr.ht/~pukkamustard/eris/%3C86fsqjmtuq.fsf%40posteo.net%3E
Reply to thread Export thread (mbox)