diff --git a/configure.ac b/configure.ac
index 4b11215..86522b3 100644
--- a/configure.ac
+++ b/configure.ac
@@ -208,7 +208,7 @@ AC_CHECK_FUNCS([ceil floor round])
 
 # Search for the required modules.
 
-VTE_PKGS="glib-2.0 >= $GLIB_REQUIRED gobject-2.0 pango >= $PANGO_REQUIRED gtk+-$GTK_API_VERSION >= $GTK_REQUIRED gobject-2.0 gio-2.0 gio-unix-2.0"
+VTE_PKGS="glib-2.0 >= $GLIB_REQUIRED gobject-2.0 pango >= $PANGO_REQUIRED gtk+-$GTK_API_VERSION >= $GTK_REQUIRED gobject-2.0 gio-2.0 gio-unix-2.0 zlib"
 PKG_CHECK_MODULES([VTE],[$VTE_PKGS])
 AC_SUBST([VTE_PKGS])
 
diff --git a/src/vtestream-file.h b/src/vtestream-file.h
index 15bcacc..78d3cd0 100644
--- a/src/vtestream-file.h
+++ b/src/vtestream-file.h
@@ -22,7 +22,7 @@
  */
 
 /*
- * VteFileStream is implemented as two layers above each other.
+ * VteFileStream is implemented as three layers above each other.
  *
  * o The bottom layer is VteSnake. It provides a mapping from logical offsets
  *   to physical file offsets, storing the stream in at most 3 continuous
@@ -32,7 +32,9 @@
  *   random-access-read of a single block, random-access-overwrite of a single
  *   block within the stream, write (append) a single block right after the
  *   current head, advancing the tail by arbitrary number of blocks, and
- *   resetting.
+ *   resetting. The appended block can be shorter, in that case we still
+ *   advance by 64kB and let the operating system leave a gap (sparse blocks)
+ *   in the file which is crucial for compression.
  *
  *   (Random-access-overwrite within the existing area is a rare event, occurs
  *   only when the terminal window size changes. We use it to redo differently
@@ -45,13 +47,24 @@
  *   the tail is kinda like a snake, and the mapping to file offsets reminds
  *   me of the well-known game on old mobile phones.
  *
+ * o The middle layer is called VteBoa. It does compression, and is planned to
+ *   do encryption along with integrity check. It has (almost) the same API as
+ *   the snake, but the blocksize is a bit smaller to leave room for the
+ *   required overhead.
+ *
+ *   The name was chosen because the world of encryption is full of three
+ *   letter abbreviations. At this moment we're planning use GNU TLS's method
+ *   for doing AES GCM. Also, because grown-ups might think it's a hat, when
+ *   actually it's a boa constrictor digesting an elephant :)
+ *
  * o The top layer is VteFileStream. Its basic goal is to do buffering and
  *   caching. As opposed to the previous layers, this one provides methods on
  *   arbitrary amount of data. It doesn't offer random-access-writes, instead,
  *   it offers appending data, and truncating the head (undoing the latest
  *   appends). Write requests are batched up until there's a complete block to
- *   be written to disk. Read requests are answered by reading possibly more
- *   underlying blocks, and sped up by caching the most recently read block.
+ *   be compressed and written to disk. Read requests are answered by reading
+ *   and uncompressing possibly more underlying blocks, and sped up by caching
+ *   the most recently read and uncompressed block.
  *
  * Design discussions: https://bugzilla.gnome.org/show_bug.cgi?id=738601
  */
@@ -61,6 +74,7 @@
 #include <stdio.h>
 #include <string.h>
 #include <unistd.h>
+#include <zlib.h>
 
 #include "vteutils.h"
 
@@ -69,12 +83,16 @@
 
 #ifndef VTESTREAM_MAIN
 #define VTE_SNAKE_BLOCKSIZE 65536
+/* Subtract compression overhead */
+#define VTE_BOA_BLOCKSIZE   (VTE_SNAKE_BLOCKSIZE - 4)
 #else
 #define VTE_SNAKE_BLOCKSIZE 4  /* Small block size for unit testing */
+#define VTE_BOA_BLOCKSIZE   3
 #endif
 
-#define ALIGN_SNAKE(x) ALIGN_FLOOR((x), VTE_SNAKE_BLOCKSIZE)
-#define MOD_SNAKE(x)   ((x) % VTE_SNAKE_BLOCKSIZE)
+#define OFFSET_BOA_TO_SNAKE(x) ((x) / VTE_BOA_BLOCKSIZE * VTE_SNAKE_BLOCKSIZE)
+#define ALIGN_BOA(x) ALIGN_FLOOR((x), VTE_BOA_BLOCKSIZE)
+#define MOD_BOA(x)   ((x) % VTE_BOA_BLOCKSIZE)
 
 /******************************************************************************************/
 
@@ -294,7 +312,7 @@ typedef struct _VteSnakeClass {
         GObjectClass parent_class;
 
         void (*reset) (VteSnake *snake, gsize offset);
-        void (*write) (VteSnake *snake, gsize offset, const char *data);
+        void (*write) (VteSnake *snake, gsize offset, const char *data, gsize len);
         gboolean (*read) (VteSnake *snake, gsize offset, char *data);
         void (*advance_tail) (VteSnake *snake, gsize offset);
         gsize (*tail) (VteSnake *snake);
@@ -374,12 +392,12 @@ _vte_snake_offset_map (VteSnake *snake, gsize offset)
 
 /*
  * offset is either within the stream (overwrite data), or at its head (append data).
- * data is VTE_SNAKE_BLOCKSIZE bytes large.
+ * data is at most VTE_SNAKE_BLOCKSIZE bytes large; if shorter then the remaining amount is skipped.
  * When appending, the following state transfers can occur:
  * 1->2, 2->3.
  */
 static void
-_vte_snake_write (VteSnake *snake, gsize offset, const char *data)
+_vte_snake_write (VteSnake *snake, gsize offset, const char *data, gsize len)
 {
         gsize fd_offset;
 
@@ -412,12 +430,21 @@ _vte_snake_write (VteSnake *snake, gsize offset, const char *data)
                         snake->segment[last_segment].st_head += VTE_SNAKE_BLOCKSIZE;
                         snake->segment[last_segment].fd_head += VTE_SNAKE_BLOCKSIZE;
                 }
+                if (snake->state != 2) {
+                        /* Grow the file with sparse blocks to make sure that later pread() can
+                         * read back a whole block, even if we are about to write a shorter one. */
+                        _file_try_truncate (snake->fd, fd_offset + VTE_SNAKE_BLOCKSIZE);
+#ifdef VTESTREAM_MAIN
+                        /* For unit testing only: fill with underscores. */
+                        _file_try_punch_hole (snake->fd, fd_offset, VTE_SNAKE_BLOCKSIZE);
+#endif
+                }
                 snake->head = offset + VTE_SNAKE_BLOCKSIZE;
         } else {
                 /* Overwriting an existing block. */
                 fd_offset = _vte_snake_offset_map(snake, offset);
         }
-        _file_write (snake->fd, data, VTE_SNAKE_BLOCKSIZE, fd_offset);
+        _file_write (snake->fd, data, len, fd_offset);
 }
 
 /* Place VTE_SNAKE_BLOCKSIZE bytes at data */
@@ -522,13 +549,181 @@ _vte_snake_class_init (VteSnakeClass *klass)
 /******************************************************************************************/
 
 /*
- * VteFileStream: Implement buffering/caching on top of VteSnake.
+ * VteBoa: Compress the data
+ *
+ * The data is stored as 4 bytes denoting the length of the compressed block,
+ * followed by the compressed data. The data is stored uncompressed if compression
+ * didn't result in a smaller size.
+ */
+
+typedef struct _VteBoa {
+        VteSnake parent;
+        gsize tail, head;
+
+        char *buf;
+        uLong compressBound;
+} VteBoa;
+
+typedef struct _VteBoaClass {
+        GObjectClass parent_class;
+
+        void (*reset) (VteBoa *boa, gsize offset);
+        void (*write) (VteBoa *boa, gsize offset, const char *data);
+        gboolean (*read) (VteBoa *boa, gsize offset, char *data);
+        void (*advance_tail) (VteBoa *boa, gsize offset);
+        gsize (*tail) (VteBoa *boa);
+        gsize (*head) (VteBoa *boa);
+} VteBoaClass;
+
+static GType _vte_boa_get_type (void);
+#define VTE_TYPE_BOA _vte_boa_get_type ()
+#define VTE_BOA_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), VTE_TYPE_BOA, VteBoaClass))
+
+G_DEFINE_TYPE (VteBoa, _vte_boa, VTE_TYPE_SNAKE)
+
+static void
+_vte_boa_init (VteBoa *boa)
+{
+        boa->compressBound = compressBound(VTE_BOA_BLOCKSIZE);
+        boa->buf = g_malloc(MAX(VTE_SNAKE_BLOCKSIZE, 4 + boa->compressBound));
+}
+
+static void
+_vte_boa_finalize (GObject *object)
+{
+        VteBoa *boa = (VteBoa *) object;
+
+        g_free(boa->buf);
+
+        G_OBJECT_CLASS (_vte_boa_parent_class)->finalize(object);
+}
+
+static void
+_vte_boa_reset (VteBoa *boa, gsize offset)
+{
+        g_assert_cmpuint (offset % VTE_BOA_BLOCKSIZE, ==, 0);
+
+        _vte_snake_reset (&boa->parent, OFFSET_BOA_TO_SNAKE(offset));
+
+        boa->tail = boa->head = offset;
+}
+
+/*
+ * offset is either within the stream (overwrite data), or at its head (append data).
+ * data is VTE_BOA_BLOCKSIZE bytes large.
+ */
+static void
+_vte_boa_write (VteBoa *boa, gsize offset, const char *data)
+{
+        uLongf destLen = boa->compressBound;
+
+        g_assert_cmpuint (offset, >=, boa->tail);
+        g_assert_cmpuint (offset, <=, boa->head);
+        g_assert_cmpuint (offset % VTE_BOA_BLOCKSIZE, ==, 0);
+
+#ifndef VTESTREAM_MAIN
+        g_assert (compress2 ((Bytef *) (boa->buf + 4), &destLen, (Bytef *) data, VTE_BOA_BLOCKSIZE, 1) == Z_OK);
+        if (G_UNLIKELY (destLen >= VTE_BOA_BLOCKSIZE)) {
+                /* Could not compress, store the original. */
+                memcpy (boa->buf + 4, data, VTE_BOA_BLOCKSIZE);
+                destLen = VTE_BOA_BLOCKSIZE;
+        }
+        *((guint32 *) boa->buf) = (guint32) destLen;
+        destLen += 4;
+#else
+        /* Fake compression+encryption for unit testing */
+        boa->buf[0] = data[0] ^ 0x20;
+        boa->buf[1] = data[1] ^ 0x20;
+        boa->buf[2] = data[2] ^ 0x20;
+        destLen = 3;
+#endif
+        _vte_snake_write (&boa->parent, OFFSET_BOA_TO_SNAKE(offset), boa->buf, destLen);
+
+        if (G_LIKELY (offset == boa->head)) {
+                boa->head += VTE_BOA_BLOCKSIZE;
+        }
+}
+
+/* Place VTE_BOA_BLOCKSIZE bytes at data */
+static gboolean
+_vte_boa_read (VteBoa *boa, gsize offset, char *data)
+{
+        uLongf destLen = VTE_BOA_BLOCKSIZE;
+        guint32 sourceLen;
+
+        g_assert_cmpuint (offset % VTE_BOA_BLOCKSIZE, ==, 0);
+
+        if (!_vte_snake_read (&boa->parent, OFFSET_BOA_TO_SNAKE(offset), boa->buf))
+                return FALSE;
+
+#ifndef VTESTREAM_MAIN
+        sourceLen = *((guint32 *) boa->buf);
+
+        if (G_LIKELY (sourceLen < VTE_BOA_BLOCKSIZE)) {
+                g_assert (uncompress ((Bytef *) data, &destLen, (Bytef *) (boa->buf + 4), sourceLen) == Z_OK);
+                g_assert (destLen == VTE_BOA_BLOCKSIZE);
+        } else {
+                memcpy (data, boa->buf + 4, VTE_BOA_BLOCKSIZE);
+        }
+#else
+        /* Fake decryption+decompression for unit testing */
+        data[0] = boa->buf[0] ^ 0x20;
+        data[1] = boa->buf[1] ^ 0x20;
+        data[2] = boa->buf[2] ^ 0x20;
+        (void) destLen; (void) sourceLen;  /* silence gcc */
+#endif
+        return TRUE;
+}
+
+static void
+_vte_boa_advance_tail (VteBoa *boa, gsize offset)
+{
+        g_assert_cmpuint (offset, >=, boa->tail);
+        g_assert_cmpuint (offset, <=, boa->head);
+        g_assert_cmpuint (offset % VTE_BOA_BLOCKSIZE, ==, 0);
+
+        _vte_snake_advance_tail (&boa->parent, OFFSET_BOA_TO_SNAKE(offset));
+
+        boa->tail = offset;
+}
+
+static gsize
+_vte_boa_tail (VteBoa *boa)
+{
+        return boa->tail;
+}
+
+static gsize
+_vte_boa_head (VteBoa *boa)
+{
+        return boa->head;
+}
+
+static void
+_vte_boa_class_init (VteBoaClass *klass)
+{
+        GObjectClass *gobject_class = G_OBJECT_CLASS (klass);
+
+        gobject_class->finalize = _vte_boa_finalize;
+
+        klass->reset = _vte_boa_reset;
+        klass->write = _vte_boa_write;
+        klass->read = _vte_boa_read;
+        klass->advance_tail = _vte_boa_advance_tail;
+        klass->tail = _vte_boa_tail;
+        klass->head = _vte_boa_head;
+}
+
+/******************************************************************************************/
+
+/*
+ * VteFileStream: Implement buffering/caching on top of VteBoa.
  */
 
 typedef struct _VteFileStream {
         GObject parent;
 
-        VteSnake *snake;
+        VteBoa *boa;
 
         char *rbuf;
         /* Offset of the cached record, always a multiple of block size.
@@ -558,11 +753,11 @@ _vte_file_stream_new (void)
 static void
 _vte_file_stream_init (VteFileStream *stream)
 {
-        stream->snake = g_object_new (VTE_TYPE_SNAKE, NULL);
-        _vte_snake_init (stream->snake);
+        stream->boa = g_object_new (VTE_TYPE_BOA, NULL);
+        _vte_boa_init (stream->boa);
 
-        stream->rbuf = g_malloc(VTE_SNAKE_BLOCKSIZE);
-        stream->wbuf = g_malloc(VTE_SNAKE_BLOCKSIZE);
+        stream->rbuf = g_malloc(VTE_BOA_BLOCKSIZE);
+        stream->wbuf = g_malloc(VTE_BOA_BLOCKSIZE);
         stream->rbuf_offset = 1;  /* Invalidate the read cache. */
 }
 
@@ -573,7 +768,7 @@ _vte_file_stream_finalize (GObject *object)
 
         g_free(stream->rbuf);
         g_free(stream->wbuf);
-        g_object_unref (stream->snake);
+        g_object_unref (stream->boa);
 
         G_OBJECT_CLASS (_vte_file_stream_parent_class)->finalize(object);
 }
@@ -582,23 +777,22 @@ static void
 _vte_file_stream_reset (VteStream *astream, gsize offset)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
-        gsize offset_aligned = ALIGN_SNAKE(offset);
+        gsize offset_aligned = ALIGN_BOA(offset);
 
-        _vte_snake_reset (stream->snake, offset_aligned);
+        _vte_boa_reset (stream->boa, offset_aligned);
         stream->tail = stream->head = offset;
 
         /* When resetting at a non-aligned offset, initial bytes of the write buffer
          * will eventually be written to disk, although doesn't contain useful information.
          * Rather than leaving garbage there, fill it with zeros.
          * For unittesting, fill it with 1s for convenient testing. */
-
 #ifndef VTESTREAM_MAIN
-        memset(stream->wbuf, 0, MOD_SNAKE(offset));
+        memset(stream->wbuf, 0, MOD_BOA(offset));
 #else
-        memset(stream->wbuf, 1, MOD_SNAKE(offset));
+        memset(stream->wbuf, 1, MOD_BOA(offset));
 #endif
 
-        stream->wbuf_len = MOD_SNAKE(offset);
+        stream->wbuf_len = MOD_BOA(offset);
         stream->rbuf_offset = 1;  /* Invalidate the read cache. */
 }
 
@@ -608,11 +802,11 @@ _vte_file_stream_append (VteStream *astream, const char *data, gsize len)
 	VteFileStream *stream = (VteFileStream *) astream;
 
         while (len) {
-                gsize l = MIN(VTE_SNAKE_BLOCKSIZE - stream->wbuf_len, len);
+                gsize l = MIN(VTE_BOA_BLOCKSIZE - stream->wbuf_len, len);
                 memcpy(stream->wbuf + stream->wbuf_len, data, l);
                 stream->wbuf_len += l; data += l; len -= l;
-                if (stream->wbuf_len == VTE_SNAKE_BLOCKSIZE) {
-                        _vte_snake_write (stream->snake, ALIGN_SNAKE(stream->head), stream->wbuf);
+                if (stream->wbuf_len == VTE_BOA_BLOCKSIZE) {
+                        _vte_boa_write (stream->boa, ALIGN_BOA(stream->head), stream->wbuf);
                         stream->wbuf_len = 0;
                 }
                 stream->head += l;
@@ -639,20 +833,20 @@ _vte_file_stream_read (VteStream *astream, gsize offset, char *data, gsize len)
                 g_assert_not_reached();
         }
 
-        while (len && offset < ALIGN_SNAKE(stream->head)) {
-                gsize l = MIN(VTE_SNAKE_BLOCKSIZE - MOD_SNAKE(offset), len);
-                gsize offset_aligned = ALIGN_SNAKE(offset);
+        while (len && offset < ALIGN_BOA(stream->head)) {
+                gsize l = MIN(VTE_BOA_BLOCKSIZE - MOD_BOA(offset), len);
+                gsize offset_aligned = ALIGN_BOA(offset);
                 if (offset_aligned != stream->rbuf_offset) {
-                        if (!_vte_snake_read (stream->snake, offset_aligned, stream->rbuf))
+                        if (!_vte_boa_read (stream->boa, offset_aligned, stream->rbuf))
                                 return FALSE;
                         stream->rbuf_offset = offset_aligned;
                 }
-                memcpy(data, stream->rbuf + MOD_SNAKE(offset), l);
+                memcpy(data, stream->rbuf + MOD_BOA(offset), l);
                 offset += l; data += l; len -= l;
         }
         if (len) {
-                g_assert_cmpuint(MOD_SNAKE(offset) + len, <=, stream->wbuf_len);
-                memcpy(data, stream->wbuf + MOD_SNAKE(offset), len);
+                g_assert_cmpuint(MOD_BOA(offset) + len, <=, stream->wbuf_len);
+                memcpy(data, stream->wbuf + MOD_BOA(offset), len);
         }
         return TRUE;
 }
@@ -665,24 +859,24 @@ _vte_file_stream_truncate (VteStream *astream, gsize offset)
         g_assert_cmpuint (offset, >=, stream->tail);
         g_assert_cmpuint (offset, <=, stream->head);
 
-        if (offset < ALIGN_SNAKE(stream->head)) {
+        if (offset < ALIGN_BOA(stream->head)) {
                 /* Truncating goes back to the part that we've written to the
                  * file. For simplicity (since this is a very rare, user
                  * initiated event - the window is made taller) go for the
                  * simplest local hack here that allows to leave the rest of
                  * the code intact, that is, read back the new partial last
                  * block to the write cache. */
-                gsize offset_aligned = ALIGN_SNAKE(offset);
-                if (!_vte_snake_read (stream->snake, offset_aligned, stream->wbuf)) {
+                gsize offset_aligned = ALIGN_BOA(offset);
+                if (!_vte_boa_read (stream->boa, offset_aligned, stream->wbuf)) {
                         /* what now? */
-                        memset(stream->wbuf, 0, VTE_SNAKE_BLOCKSIZE);
+                        memset(stream->wbuf, 0, VTE_BOA_BLOCKSIZE);
                 }
 
                 if (stream->rbuf_offset >= offset_aligned) {
                         stream->rbuf_offset = 1;  /* Invalidate the read cache. */
                 }
         }
-        stream->wbuf_len = MOD_SNAKE(offset);
+        stream->wbuf_len = MOD_BOA(offset);
 	stream->head = offset;
 }
 
@@ -694,8 +888,8 @@ _vte_file_stream_advance_tail (VteStream *astream, gsize offset)
         g_assert_cmpuint (offset, >=, stream->tail);
         g_assert_cmpuint (offset, <=, stream->head);
 
-        if (ALIGN_SNAKE(offset) > ALIGN_SNAKE(stream->tail))
-                _vte_snake_advance_tail (stream->snake, ALIGN_SNAKE(offset));
+        if (ALIGN_BOA(offset) > ALIGN_BOA(stream->tail))
+                _vte_boa_advance_tail (stream->boa, ALIGN_BOA(offset));
 
         stream->tail = offset;
 }
@@ -768,6 +962,19 @@ _vte_file_stream_class_init (VteFileStreamClass *klass)
         } \
 } while (0)
 
+/* Check for the boa's tail, head and contents */
+#define assert_boa(__boa, __tail, __head, __contents) do { \
+        char __buf[VTE_BOA_BLOCKSIZE]; \
+        int __i; \
+        g_assert_cmpuint (boa->tail, ==, __tail); \
+        g_assert_cmpuint (boa->head, ==, __head); \
+        g_assert_cmpuint (strlen(__contents), ==, __head - __tail); \
+        for (__i = __tail; __i < __head; __i += VTE_BOA_BLOCKSIZE) { \
+                g_assert (_vte_boa_read (boa, __i, __buf)); \
+                g_assert (memcmp(__buf, __contents + __i - __tail, VTE_BOA_BLOCKSIZE) == 0); \
+        } \
+} while (0)
+
 /* Check for the stream's tail, head and contents */
 #define assert_stream(__astream, __tail, __head, __contents) do { \
         char __buf[100]; \
@@ -778,28 +985,30 @@ _vte_file_stream_class_init (VteFileStreamClass *klass)
         g_assert (memcmp(__buf, __contents, __head - __tail) == 0); \
 } while (0)
 
+#define snake_write(snake, offset, str) _vte_snake_write((snake), (offset), (str), strlen(str))
+
 static void
 test_snake (void)
 {
         VteSnake *snake = g_object_new (VTE_TYPE_SNAKE, NULL);
 
         /* Test overwriting data */
-        _vte_snake_write (snake, 0, "aaaa");
+        snake_write (snake, 0, "aaaa");
         assert_snake (snake, 1, 0, 4, "aaaa");
 
-        _vte_snake_write (snake, 4, "bbbb");
+        snake_write (snake, 4, "bbbb");
         assert_file (snake->fd, "aaaabbbb");
         assert_snake (snake, 1, 0, 8, "aaaabbbb");
 
-        _vte_snake_write (snake, 4, "cccc");
+        snake_write (snake, 4, "cccc");
         assert_file (snake->fd, "aaaacccc");
         assert_snake (snake, 1, 0, 8, "aaaacccc");
 
-        _vte_snake_write (snake, 0, "dddd");
+        snake_write (snake, 0, "dddd");
         assert_file (snake->fd, "ddddcccc");
         assert_snake (snake, 1, 0, 8, "ddddcccc");
 
-        _vte_snake_write (snake, 8, "eeee");
+        snake_write (snake, 8, "eeee");
         assert_file (snake->fd, "ddddcccceeee");
         assert_snake (snake, 1, 0, 12, "ddddcccceeee");
 
@@ -808,30 +1017,30 @@ test_snake (void)
         assert_snake (snake, 1, 0, 0, "");
 
         /* State 1 */
-        _vte_snake_write (snake, 0, "aaaa");
-        _vte_snake_write (snake, 4, "bbbb");
+        snake_write (snake, 0, "aaaa");
+        snake_write (snake, 4, "bbbb");
         assert_file_starts_with (snake->fd, "aaaabbbb");
         assert_snake (snake, 1, 0, 8, "aaaabbbb");
 
         /* Stay in state 1 */
         _vte_snake_advance_tail (snake, 4);
-        _vte_snake_write (snake, 8, "cccc");
+        snake_write (snake, 8, "cccc");
         assert_file (snake->fd, "____bbbbcccc");
         assert_snake (snake, 1, 4, 12, "bbbbcccc");
 
         /* State 1 -> 2 */
         _vte_snake_advance_tail (snake, 8);
-        _vte_snake_write (snake, 12, "dddd");
+        snake_write (snake, 12, "dddd");
         assert_file (snake->fd, "dddd____cccc");
         assert_snake (snake, 2, 8, 16, "ccccdddd");
 
         /* Stay in state 2 */
-        _vte_snake_write (snake, 16, "eeee");
+        snake_write (snake, 16, "eeee");
         assert_file (snake->fd, "ddddeeeecccc");
         assert_snake (snake, 2, 8, 20, "ccccddddeeee");
 
         /* State 2 -> 3 */
-        _vte_snake_write (snake, 20, "ffff");
+        snake_write (snake, 20, "ffff");
         assert_file (snake->fd, "ddddeeeeccccffff");
         assert_snake (snake, 3, 8, 24, "ccccddddeeeeffff");
 
@@ -851,7 +1060,7 @@ test_snake (void)
         assert_snake (snake, 1, 20, 24, "ffff");
 
         /* State 1 -> 2 */
-        _vte_snake_write (snake, 24, "gggg");
+        snake_write (snake, 24, "gggg");
         assert_file (snake->fd, "gggg________ffff");
         assert_snake (snake, 2, 20, 28, "ffffgggg");
 
@@ -860,165 +1069,231 @@ test_snake (void)
         assert_snake (snake, 1, 100, 100, "");
 
         /* Stay in state 1 */
-        _vte_snake_write (snake, 100, "zzzz");
+        snake_write (snake, 100, "zzzz");
         assert_file_starts_with (snake->fd, "zzzz");
         assert_snake (snake, 1, 100, 104, "zzzz");
 
         g_object_unref (snake);
 }
 
+static void
+test_boa (void)
+{
+        VteBoa *boa = g_object_new (VTE_TYPE_BOA, NULL);
+        VteSnake *snake = (VteSnake *) &boa->parent;
+
+        /* State 1 */
+        _vte_boa_write (boa, 0, "aaa");
+        _vte_boa_write (boa, 3, "bbb");
+        assert_snake (snake, 1, 0, 8, "AAA_BBB_");
+        assert_boa (boa, 0, 6, "aaabbb");
+
+        /* Stay in state 1 */
+        _vte_boa_advance_tail (boa, 3);
+        _vte_boa_write (boa, 6, "ccc");
+        assert_snake (snake, 1, 4, 12, "BBB_CCC_");
+        assert_boa (boa, 3, 9, "bbbccc");
+
+        /* State 1 -> 2 */
+        _vte_boa_advance_tail (boa, 6);
+        _vte_boa_write (boa, 9, "ddd");
+        assert_file (snake->fd, "DDD_____CCC_");
+        assert_snake (snake, 2, 8, 16, "CCC_DDD_");
+        assert_boa (boa, 6, 12, "cccddd");
+
+        /* Skip some state changes that we tested in test_snake_state_changes() */
+
+        /* Reset */
+        _vte_boa_reset (boa, 75);
+        assert_snake (snake, 1, 100, 100, "");
+        assert_boa (boa, 75, 75, "");
+
+        /* Stay in state 1 */
+        _vte_boa_write (boa, 75, "zzz");
+        assert_file_starts_with (snake->fd, "ZZZ_");
+        assert_snake (snake, 1, 100, 104, "ZZZ_");
+        assert_boa (boa, 75, 78, "zzz");
+
+        g_object_unref (boa);
+}
+
 #define stream_append(as, str) _vte_stream_append((as), (str), strlen(str))
 
 static void
 test_stream (void)
 {
+        VteBoa *boa;
         VteSnake *snake;
-        char buf[5];
+        char buf[4];
 
         VteStream *astream = _vte_file_stream_new();
         VteFileStream *stream = (VteFileStream *) astream;
         _vte_file_stream_init (stream);
-        snake = stream->snake;
+        boa = stream->boa;
+        snake = (VteSnake *) &boa->parent;
 
         /* Append */
         stream_append (astream, "ab");
         g_assert (snake->fd == -1);
+        assert_boa (boa, 0, 0, "");
         assert_stream (astream, 0, 2, "ab");
 
-        stream_append (astream, "c#");
-        assert_file (snake->fd, "abc#");
-        assert_snake (snake, 1, 0, 4, "abc#");
-        assert_stream (astream, 0, 4, "abc#");
+        stream_append (astream, "c");
+        assert_file (snake->fd, "ABC_");
+        assert_snake (snake, 1, 0, 4, "ABC_");
+        assert_boa (boa, 0, 3, "abc");
+        assert_stream (astream, 0, 3, "abc");
 
         stream_append (astream, "d");
-        assert_file (snake->fd, "abc#");
-        assert_snake (snake, 1, 0, 4, "abc#");
-        assert_stream (astream, 0, 5, "abc#d");
+        assert_file (snake->fd, "ABC_");
+        assert_snake (snake, 1, 0, 4, "ABC_");
+        assert_boa (boa, 0, 3, "abc");
+        assert_stream (astream, 0, 4, "abcd");
 
-        stream_append (astream, "ef#ghi#j");
-        assert_file (snake->fd, "abc#def#ghi#");
-        assert_snake (snake, 1, 0, 12, "abc#def#ghi#");
-        assert_stream (astream, 0, 13, "abc#def#ghi#j");
+        stream_append (astream, "efghij");
+        assert_file (snake->fd, "ABC_DEF_GHI_");
+        assert_snake (snake, 1, 0, 12, "ABC_DEF_GHI_");
+        assert_boa (boa, 0, 9, "abcdefghi");
+        assert_stream (astream, 0, 10, "abcdefghij");
 
         /* Truncate */
-        _vte_stream_truncate (astream, 12);
-        assert_file (snake->fd, "abc#def#ghi#");
-        assert_snake (snake, 1, 0, 12, "abc#def#ghi#");
-        assert_stream (astream, 0, 12, "abc#def#ghi#");
-
-        _vte_stream_truncate (astream, 10);
-        assert_file (snake->fd, "abc#def#ghi#");
-        assert_snake (snake, 1, 0, 12, "abc#def#ghi#");
-        assert_stream (astream, 0, 10, "abc#def#gh");
+        _vte_stream_truncate (astream, 9);
+        assert_file (snake->fd, "ABC_DEF_GHI_");
+        assert_snake (snake, 1, 0, 12, "ABC_DEF_GHI_");
+        assert_boa (boa, 0, 9, "abcdefghi");
+        assert_stream (astream, 0, 9, "abcdefghi");
+
+        _vte_stream_truncate (astream, 8);
+        assert_file (snake->fd, "ABC_DEF_GHI_");
+        assert_snake (snake, 1, 0, 12, "ABC_DEF_GHI_");
+        assert_boa (boa, 0, 9, "abcdefghi");
+        assert_stream (astream, 0, 8, "abcdefgh");
 
         /* Test that the read cache is invalidated on truncate */
-        _vte_stream_read (astream, 6, buf, 3);
-        g_assert_cmpuint (stream->rbuf_offset, ==, 4);
-        _vte_stream_truncate (astream, 6);
+        _vte_stream_read (astream, 5, buf, 2);
+        g_assert_cmpuint (stream->rbuf_offset, ==, 3);
+        _vte_stream_truncate (astream, 5);
         g_assert_cmpuint (stream->rbuf_offset, ==, 1);
-        stream_append (astream, "k#l");
-        _vte_stream_read (astream, 4, buf, 4);
-        g_assert_cmpuint (stream->rbuf_offset, ==, 4);
-        buf[4] = '\0';
-        g_assert_cmpstr (buf, ==, "dek#");
-        assert_file (snake->fd, "abc#dek#ghi#");
-        assert_snake (snake, 1, 0, 12, "abc#dek#ghi#");
-        assert_stream (astream, 0, 9, "abc#dek#l");
+        stream_append (astream, "kl");
+        _vte_stream_read (astream, 3, buf, 3);
+        g_assert_cmpuint (stream->rbuf_offset, ==, 3);
+        buf[3] = '\0';
+        g_assert_cmpstr (buf, ==, "dek");
+        assert_file (snake->fd, "ABC_DEK_GHI_");
+        assert_snake (snake, 1, 0, 12, "ABC_DEK_GHI_");
+        assert_boa (boa, 0, 9, "abcdekghi");
+        assert_stream (astream, 0, 7, "abcdekl");
 
         /* Advance_tail */
         _vte_stream_advance_tail (astream, 2);
-        assert_file (snake->fd, "abc#dek#ghi#");
-        assert_snake (snake, 1, 0, 12, "abc#dek#ghi#");
-        assert_stream (astream, 2, 9, "c#dek#l");
+        assert_file (snake->fd, "ABC_DEK_GHI_");
+        assert_snake (snake, 1, 0, 12, "ABC_DEK_GHI_");
+        assert_boa (boa, 0, 9, "abcdekghi");
+        assert_stream (astream, 2, 7, "cdekl");
 
-        _vte_stream_advance_tail (astream, 4);
-        assert_file (snake->fd, "____dek#ghi#");
-        assert_snake (snake, 1, 4, 12, "dek#ghi#");
-        assert_stream (astream, 4, 9, "dek#l");
+        _vte_stream_advance_tail (astream, 3);
+        assert_file (snake->fd, "____DEK_GHI_");
+        assert_snake (snake, 1, 4, 12, "DEK_GHI_");
+        assert_boa (boa, 3, 9, "dekghi");
+        assert_stream (astream, 3, 7, "dekl");
 
         stream_append (astream, "m");
-        assert_file (snake->fd, "____dek#ghi#");
-        assert_snake (snake, 1, 4, 12, "dek#ghi#");
-        assert_stream (astream, 4, 10, "dek#lm");
+        assert_file (snake->fd, "____DEK_GHI_");
+        assert_snake (snake, 1, 4, 12, "DEK_GHI_");
+        assert_boa (boa, 3, 9, "dekghi");
+        assert_stream (astream, 3, 8, "deklm");
 
         /* Tail and head within the same block in the stream,
          * but not in underlying layers (due to a previous truncate).
          * Nothing special. */
-        _vte_stream_advance_tail (astream, 9);
-        assert_file (snake->fd, "________ghi#");
-        assert_snake (snake, 1, 8, 12, "ghi#");
-        assert_stream (astream, 9, 10, "m");
+        _vte_stream_advance_tail (astream, 7);
+        assert_file (snake->fd, "________GHI_");
+        assert_snake (snake, 1, 8, 12, "GHI_");
+        assert_boa (boa, 6, 9, "ghi");
+        assert_stream (astream, 7, 8, "m");
 
         /* Tail reaches head. Still nothing special. */
-        _vte_stream_advance_tail (astream, 10);
-        assert_file (snake->fd, "________ghi#");
-        assert_snake (snake, 1, 8, 12, "ghi#");
-        assert_stream (astream, 10, 10, "");
+        _vte_stream_advance_tail (astream, 8);
+        assert_file (snake->fd, "________GHI_");
+        assert_snake (snake, 1, 8, 12, "GHI_");
+        assert_boa (boa, 6, 9, "ghi");
+        assert_stream (astream, 8, 8, "");
 
         /* Snake state 2 */
-        stream_append (astream, "n#opq#rst#uv");
-        assert_file (snake->fd, "opq#rst#lmn#");
-        assert_snake (snake, 2, 8, 20, "lmn#opq#rst#");
-        assert_stream (astream, 10, 22, "n#opq#rst#uv");
+        stream_append (astream, "nopqrstuv");
+        assert_file (snake->fd, "OPQ_RST_LMN_");
+        assert_snake (snake, 2, 8, 20, "LMN_OPQ_RST_");
+        assert_boa (boa, 6, 15, "lmnopqrst");
+        assert_stream (astream, 8, 17, "nopqrstuv");
 
         /* Tail and head within the same block.
          * The snake resets itself to state 1, ... */
-        _vte_stream_advance_tail (astream, 21);
+        _vte_stream_advance_tail (astream, 16);
         assert_snake (snake, 1, 20, 20, "");
-        assert_stream (astream, 21, 22, "v");
+        assert_boa (boa, 15, 15, "");
+        assert_stream (astream, 16, 17, "v");
 
         /* ... and the next write goes to beginning of the file */
-        stream_append (astream, "w#x");
-        assert_file_starts_with (snake->fd, "uvw#");
-        assert_snake (snake, 1, 20, 24, "uvw#");
-        assert_stream (astream, 21, 25, "vw#x");
+        stream_append (astream, "wx");
+        assert_file_starts_with (snake->fd, "UVW_");
+        assert_snake (snake, 1, 20, 24, "UVW_");
+        assert_boa (boa, 15, 18, "uvw");
+        assert_stream (astream, 16, 19, "vwx");
 
         /* Test a bit what happens when "accidentally" writing aligned blocks. */
-        stream_append (astream, "yz#");
-        assert_file_starts_with (snake->fd, "uvw#xyz#");
-        assert_snake (snake, 1, 20, 28, "uvw#xyz#");
-        assert_stream (astream, 21, 28, "vw#xyz#");
+        stream_append (astream, "yz");
+        assert_file_starts_with (snake->fd, "UVW_XYZ_");
+        assert_snake (snake, 1, 20, 28, "UVW_XYZ_");
+        assert_boa (boa, 15, 21, "uvwxyz");
+        assert_stream (astream, 16, 21, "vwxyz");
+
+        stream_append (astream, "abc");
+        assert_file (snake->fd, "UVW_XYZ_ABC_");
+        assert_snake (snake, 1, 20, 32, "UVW_XYZ_ABC_");
+        assert_boa (boa, 15, 24, "uvwxyzabc");
+        assert_stream (astream, 16, 24, "vwxyzabc");
 
-        stream_append (astream, "abc#");
-        assert_file (snake->fd, "uvw#xyz#abc#");
-        assert_snake (snake, 1, 20, 32, "uvw#xyz#abc#");
-        assert_stream (astream, 21, 32, "vw#xyz#abc#");
-
-        _vte_stream_advance_tail (astream, 28);
-        assert_file (snake->fd, "________abc#");
-        assert_snake (snake, 1, 28, 32, "abc#");
-        assert_stream (astream, 28, 32, "abc#");
+        _vte_stream_advance_tail (astream, 21);
+        assert_file (snake->fd, "________ABC_");
+        assert_snake (snake, 1, 28, 32, "ABC_");
+        assert_boa (boa, 21, 24, "abc");
+        assert_stream (astream, 21, 24, "abc");
 
         /* State 2 */
-        stream_append (astream, "def#");
-        assert_file (snake->fd, "def#____abc#");
-        assert_snake (snake, 2, 28, 36, "abc#def#");
-        assert_stream (astream, 28, 36, "abc#def#");
-
-        stream_append (astream, "ghi#");
-        assert_file (snake->fd, "def#ghi#abc#");
-        assert_snake (snake, 2, 28, 40, "abc#def#ghi#");
-        assert_stream (astream, 28, 40, "abc#def#ghi#");
+        stream_append (astream, "def");
+        assert_file (snake->fd, "DEF_____ABC_");
+        assert_snake (snake, 2, 28, 36, "ABC_DEF_");
+        assert_boa (boa, 21, 27, "abcdef");
+        assert_stream (astream, 21, 27, "abcdef");
+
+        stream_append (astream, "ghi");
+        assert_file (snake->fd, "DEF_GHI_ABC_");
+        assert_snake (snake, 2, 28, 40, "ABC_DEF_GHI_");
+        assert_boa (boa, 21, 30, "abcdefghi");
+        assert_stream (astream, 21, 30, "abcdefghi");
 
         /* State 3 */
-        stream_append (astream, "jkl#");
-        assert_file (snake->fd, "def#ghi#abc#jkl#");
-        assert_snake (snake, 3, 28, 44, "abc#def#ghi#jkl#");
-        assert_stream (astream, 28, 44, "abc#def#ghi#jkl#");
+        stream_append (astream, "jkl");
+        assert_file (snake->fd, "DEF_GHI_ABC_JKL_");
+        assert_snake (snake, 3, 28, 44, "ABC_DEF_GHI_JKL_");
+        assert_boa (boa, 21, 33, "abcdefghijkl");
+        assert_stream (astream, 21, 33, "abcdefghijkl");
 
         /* State 4 */
-        _vte_stream_advance_tail (astream, 32);
-        assert_file (snake->fd, "def#ghi#____jkl#");
-        assert_snake (snake, 4, 32, 44, "def#ghi#jkl#");
-        assert_stream (astream, 32, 44, "def#ghi#jkl#");
+        _vte_stream_advance_tail (astream, 24);
+        assert_file (snake->fd, "DEF_GHI_____JKL_");
+        assert_snake (snake, 4, 32, 44, "DEF_GHI_JKL_");
+        assert_boa (boa, 24, 33, "defghijkl");
+        assert_stream (astream, 24, 33, "defghijkl");
 
         /* Explicit reset */
-        _vte_stream_reset (astream, 102);
-        stream_append (astream, "y#z");
-        /* Unused leading blocks are filled with '\x01' */
-        assert_file_starts_with (snake->fd, "\x01\x01y#");
-        assert_snake (snake, 1, 100, 104, "\x01\x01y#");
-        assert_stream (astream, 102, 105, "y#z");
+        _vte_stream_reset (astream, 77);
+        stream_append (astream, "yz");
+        /* Unused leading blocks are filled with '\x01', fake compressed+encrypted to '!' */
+        assert_file_starts_with (snake->fd, "!!Y_");
+        assert_snake (snake, 1, 100, 104, "!!Y_");
+        assert_boa (boa, 75, 78, "\x01\x01y");
+        assert_stream (astream, 77, 79, "yz");
 
         g_object_unref (astream);
 }
@@ -1027,6 +1302,7 @@ int
 main (int argc, char **argv)
 {
         test_snake();
+        test_boa();
         test_stream();
 
         printf("vtestream-file tests passed :)\n");
