This project presents an implementation of the Short-Odd Long-Even (SOLE)
encoding scheme presented in \cite{patrascu10trits}. SOLE provides an online,
prefix-free encoding with excellent locality properties.

%\paragraph{Motivation}
Its development was motivated by the problem of representing a vector $A[1\dots
n]$ of elements from some alphabet $\Sigma$, and showed as a result how to
represent $A$ using ``{\itshape $\lceil n\log_2{\Sigma}\rceil$ bits, such that
any element of the vector can be read or written in constant time.}''

%\paragraph{Applications in cryptography}
Given a stream $n$ blocks of $b$ bits, we can output a prefix-free encoding
using at most $n+3$ blocks. Prefix-freeness is useful in cryptographic
applications, since it is a simple counter-measure to extension attacks and
methods like CBC-MAC require the input messages $M$ to be prefix-free in order
to be secure.

%\paragraph{This project}
In \Fref[plain]{sec:overview} we demonstrate how the SOLE encoding scheme works
and discuss some useful observations for implementation. Next, in
\Fref{sec:impl} we examine the requirements for an online encoding and decoding
in C using 128 bit blocks. Finally in \Fref{sec:comp} we conclude with a small
benchmark comparison to a ``naive'' encoding scheme.