Redesigning my hex editor backend for flexibility

Overview

I have been working on my hex editor across many years now.

Before ddhx 0.5, there was no data structure. It was as simple as moving a view, reading the file, and rendering data on screen.

But when I restarted my efforts on version 0.5, I was wondering: What can I do to turn my little hex viewer into a full-fledged editor? What would allow me to easily and organically integrate edits into a document with undo/redo support?

I initially thought of accumulating patches. These patches would be saved onto an in-memory list to be applied sequentially to the view buffer when called. However, this approach proved overly cumbersome, slow, and complicated.

After some further reflection, I settled on something.

Current Backend

To help speed up the development process and support undo-redo operations, I had an idea: Hash maps & Buffers.

The current data structure, personally dubbed “cache-chunk”, uses fixed-position chunks to cache modification operations. When viewing, the function finds chunks in memory using memory-aligned positions within the hash map (in D, the term Associative Array is used), containing the list of chunks.

As an example, here is a logical view of a freshly opened document:

+------------------------------------------------+
| DOCUMENT                                       |
+------------------------------------------------+

When an overwrite operation is performed:

1. If the position of the edit does not hold a chunk, allocate a chunk.
   • Chunks are aligned to their size (pagesize, or 4K).
   • If there is a source document, read the document to fill the chunk.
2. If the length surpasses the end of this chunk, allocate another chunk (due to overflow).
   • Read again from document, if there is one.
   • This never happened, because the editor currently only supports 1-byte writes.
3. Create a patch to hold the new data to patch.
   • Save old data from chunk to patch.
4. Apply new data to chunk.
5. Add patch to list, increment patch index.

When applied, the logical view will be updated to:

Patch data ---------+
                    |
+---------------+---v---+---------------------+
| DOCUMENT      | CHUNK | DOCUMENT            |
+---------------+-------+---------------------+
|-------|-------|-------|-------|-------|-------| (Alignment)

To view a section of data:

1. For position P, ask ChunkManager if there is a chunk there.
   • ChunkPosition = aligndown(P, 4K)
   • Has chunk: Read chunk data up to boundary
   • No chunk: Read document up to boundary
2. Add chunksize (typically 4K) to P, and repeat step 1 until view buffer is filled.

View range:         |-------|
+---------------+-------+---------------------+
| DOCUMENT      | CHUNK | DOCUMENT            |
+---------------+-------+---------------------+

ChunkManager ---+ (1st read)
                V
|-------|-------|-------|-------|-------|-------| (Alignment)
+---------------+-------+---------------------+
| DOCUMENT      | CHUNK | DOCUMENT            |
+---------------+-------+---------------------+
Read:               |---|

ChunkManager -----------+ (2nd read)
                        V
|-------|-------|-------|-------|-------|-------| (Alignment)
+---------------+-------+---------------------+
| DOCUMENT      | CHUNK | DOCUMENT            |
+---------------+-------+---------------------+
Read:                   |---|

By itself, viewing and overwrite operations are very fast, and was an acceptable data structure for the moment being. This finally let me call ddhx a hex editor at the moment. My base objective was done.

Limitations

While the cache-chunk structure favours random-access and read speeds, it is too rigid of a structure to do anything else with it.

For demonstration, let’s take this document with these chunks:

             Patch 1 -+              Patch 3 -+
                      |                       |
+-----------------+---v---+-------+-------+---v---+
| DOCUMENT        | CHUNK | CHUNK | DOC   | CHUNK |
+-----------------+-------+---^---+-------+-----^-+
                              |                 |
                     Patch 2 -+        Patch 4 -+

For inserting data, we have two options: (a) Shift data in chunks, or (b) Shift chunks.

For Option A (shift data in chunks):

New insert data --+--+
                  |  |
+-----------------v--v----+-------+-------+-------+
| DOCUMENT        | CHUNK | CHUNK | DOC   | CHUNK |
+-----------------+-------+-------+-------+-------+
                     |> Push data from this point
                        for *all* chunks now overflowing

This has the devastating effect of having to physically copy data for all chunks after the insertion. Meaning, at least creating one or more new chunks (due to data overflowing beyond chunk capacity) and moving all of that using memcpy (per chunk), while keeping a history per chunk.

Frankly put, incredibly unrealistic.

For Option B (shift chunk):

Assuming we just shift chunks for an insertion:

+-----------------+---+-------+-------+-------+-------+
| DOCUMENT        | C | CHUNK | CHUNK | DOC   | CHUNK |
+-----------------^---^-------+-------+-------+-------+
                  |   |
                  +---+- Insertion

Patches depend on absolute positions, all their positions are now all invalid:

                    +- Patch 1 has invalid position
                    |
+-----------------+-X-+-------+-------+-------+-------+
| DOCUMENT        | C | CHUNK | CHUNK | DOC   | CHUNK |
+-----------------+---+-------+-------+-------+-------+

So, let’s shift patches! This would be a separate operation depending on the number of patches, assuming they stay to their respective chunk.

                                +- Patch 2
                                |
+---------------+---+-------+---v---+-------+-------+
| DOCUMENT      | C | CHUNK | CHUNK | DOC   | CHUNK |
+---------------+-^-+---^---+-------+-------+---^-^-+
                  |     |                       | |
         Patch 5 -+     +- Patch 1   Patch 3+4 -+-+

Now, let’s try to view the document with the new insertion:

Expected logical view:
Position -------------+
                      V
+---------------+---+-X-----+-------+-------+-------+
| DOCUMENT      | C | CHUNK | CHUNK | DOC   | CHUNK |
+---------------+---+-------+-------+-------+-------+

ChunkManager's view:
Position -------+         +- Original request
                V         v
|-------|-------|-------|-------|-------|-------|-------| (Alignment)
+---------------+---+   +-X-----+-------+-------+-------+
| DOCUMENT      | C |   | CHUNK | CHUNK | DOC   | CHUNK |
+---------------+---+   +-------+-------+-------+-------+

The chunks are now misaligned, and because the chunk manager expects aligned chunks, these chunks will either collide or have gaps, destroying the purpose of keeping them aligned in the first place.

And you can probably guess the issue when multiple unaligned shifts happen. The same issue arises with deletions.

Worse, for file insertions, chunks would be created to hold the entire file into memory. Meaning, if a 2 GiB file were to be inserted, the entirety of the content would be required being held in memory.

You could keep an array of chunks sequentially instead of a hash map, but now the issues go from positioning chunks to managing variable-sized chunks and wasting time sorting them. Undoing a few operations later would mean keeping track of those sizes for each chunk, individually.

To support insertions and deletion, this is when I knew I needed a new data structure.

A Data Structure for the Modern Day

The new data structure should be able to:

• Perform sparse insertions, overwrites, and deletions in a manageable amount of time.
• Edit large files non-destructively with minimal memory usage.
• Support undo-redo operations.

After looking around in Wikipedia, opening up the page for Gap buffer, seing what Emacs uses… I noticed the Piece Table entry. Curious, I start reading VSCode’s blog post about its implementation. Further intrigued, I read the Data Structures of Text Sequences (1998) paper.

First of all, this is an amazing paper that overviews multiple data structures for a modern text editor, and mind I recall you, this is a paper from 1998.

Interestingly, it mentions of a method using fixed-size buffers, being closest of the current data structure used in ddhx, making remarks about managing buffers:

There are four problems with letting too many buffers accumulate:
• wasted space in the buffers,
• the recursive sequence of descriptors gets too large,
• the probability that an edit will be confined to one buffer is reduced,
• and ItemAt caching is less effective.

Wow, about the same I’ve experienced! The fixed-size buffers (“chunk-cache”) waste quite a bit of memory for single edits (1), and too many of them will lead to Out Of Memory (“oom”) issues.

The paper overviews several structures, from basic (array, linked list) to more complicated data structures (gap buffer, FSB).

And finally, after much reading, the ultimate conclusion leads to the Piece Table data structure (§ 9.2).

Excited, I got to work!

Implementing the Piece Table

The Data Structures for Text Sequences paper suggest using a tree for fast searching (§ 9.1).

So, the choice is simple. I’ve selected the red-black tree for self-balancing, which would automatically position the pieces in ascending order. Thankfully, Phobos provides the std.container.rbtree.RedBlackTree class.

The idea is relatively simple. Let’s start with a document:

+----------------------------------------------+
| DOCUMENT                                     |
+----------------------------------------------+

The document is currently composed of a single piece. This first piece is of type “document”, with its base position to zero (start of the document) and the size of the document.

When inserting new data, a new “buffer” piece will be inserted, slicing up the document:

+----------------+-+------------------------------+
| DOCUMENT       |B| DOCUMENT                     |
+----------------+-+------------------------------+
                 | |
                 +-+- New "buffer" piece

Now, we have three pieces. To view the section of the document requires traversing each piece.

Pieces can be copied and pasted anywhere:

+----------------+-+---------------+---+----------+
| DOCUMENT       |B| DOCUMENT      |DOC| DOC      |
+----------|---|-+-+---------------+---+----------+
Copy-Paste |   |                   ^   ^
Replace    +---+-------------------+---+

Here, we create a new “document” piece that holds the source position of the copy operation.

To help with searching pieces, this is where the red-black tree comes into play. We index pieces by their cumulative size (position + size of each piece):

Cumulative[4] ------------------------------------+
Cumulative[3] -------------------------+          |
Cumulative[2] ---------------------+   |          |
Cumulative[1] -----+               |   |          |
Cumulative[0] ---+ |               |   |          |
                 v v               v   v          v
+----------------+-+---------------+---+----------+
| DOCUMENT       |B| DOCUMENT      |DOC| DOC      |
+----------------+-+---------------+---+----------+

Thanks to the self-balancing nature of the tree, we can expect cumulative sizes to be naturally ascending in O(log n) order by avoiding checking position and size independently:

                          |> Searching here gives us
                          |> the last three pieces
+----------------+-+---------------+---+----------+
| DOCUMENT       |B| DOCUMENT      |DOC| DOC      |
+----------------+-+---------------+---+----------+

The most difficult part being actually cutting up pieces and managing them, since I’m forced to iterate through pieces sequentially.

To help debugging operations, in debug builds, I wrote a function that checks its consistency. On error (size mismatch, gap found, etc.), an exception is thrown, and the table containing the pieces is printed on screen:

-- Example of a list from previous figure
-- Fields: Type, Position, Size, Cumulative
Piece[0](document, P=   0, S= 100, C= 100)
Piece[1](buffer  , P= 100, S=  20, C= 120)
Piece[2](document, P= 120, S= 100, C= 220)
Piece[3](document, P=  50, S=  30, C= 250)
Piece[4](document, P= 250, S=  50, C= 300)

Logging, documentation, comments (notably, intent), and unittesting can greatly help you or anyone willing to contribute. In my case, after a few rounds of bugfixing, I figured that I needed to to track the old cumulative and new cumulative when recreating pieces, to keep track of cumulative positions when creating a snapshot.

Comparison

Of course, we’re trading simplicity for something a lot more flexible and powerful.

Operation	Cache-Chunk	Piece Table
View	O(1) – Fast chunk lookup.	O(log n) – Manageable using a RBTree.
Appending	O(1) – Fast if the chunk exists.	O(n log n)* – Faster with specific position optimizations.
Overwriting	O(1) – Fast direct chunk modification.	O(n log n)* – Manageable.
Inserting	❌ Impractical. Requires shifting great amounts of data.	O(n log n)* – Manageable.
Deleting	❌ Impractical. Same as above.	O(n log n)* – Manageable.
File insertion	❌ Impractical. Need to hold file in memory.	O(n log n)* – Manageable with new piece type. (Lazy loading)
Memory**	Best: 256 chunks (~1 MiB) Worst: ~1M chunks (~4 GiB)	Best: 1 piece (32 B) Worst: ~1M pieces (32 MiB)
Complexity	Low.	Moderate.***

* Due to current limitations, the tree is recreated on each operation, as a new snapshot.
** 1 MiB worth of data assuming chunk sizes of 4 KiB and each piece of 32 B (LP64).
*** This implementation is a little more complex, since it requires tracking logical document positions, physical piece positions, and cumulative positions (for the red-black tree) when handling old and new pieces.

One of the best outcome of using a piece table is the memory consumption. Hex editors are more memory-bound than text editors by the nature of their work.

It’s reasonable to expect people assume it’s possible to cut a large pieces of content, and paste it anywhere within the document, with minimal memory usage, just like they would with any modern text editors (even Microsoft Word, where the Piece Table came to be).

With the new backend, this makes just that possible. We definitively take modern text editors for granted, and that’s okay! It’s a sign that software have evolved to fit needs, and new data structures emerged to respond to these needs.

Future Improvements

There are a few things that would need to be done for improving the current implementation. Notably, experiment with a LRU cache system or copying ranges of nodes directly.

For a hex editor, in any case, the new Piece Table data structure allows flexibility with the reasonable assumption that there will be up to a few hundred edits. If performance problems arise, then I’ll start optimizing again.

To compensate, I have done a few optimizations for the upcoming version (0.7):

• Output buffering: Making a custom buffer increased rendering performance from 5x (VTE) to 10x (conhost).
• Smart reading: Only read the document editor if truly necessary (on edit, on view move, etc.), saving a call from the view function.
• New save function: A new save function have been created. The new temporary file is written in the same directory, then renamed atomically when possible (POSIX move), like most modern editors. (Versus writing it twice, making it faster.)

What else did we learn? Not to be shy and read resources, especially since this analysis was already available for us. Part of the fun in engineering is weighting in your options and evaluating them!

Be sure to check out the ddhx repository when version 0.7 comes out!