Nested Encoding Efficency
Tags: serialization
Published: 2023-01-09 19:55:35

---
title: Nested Encoding Efficency
published: true
date: 2022-12-26 18:50:00 UTC
tags: Serialization
canonical_url: https://kevincox.ca/2022/12/26/nested-encoding-efficency/
---

<main style="--width:min(36em,100%);display:grid;grid-template-columns:1fr var(--width) 1fr;overflow:auto;padding:0;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">It’s relatively common that you want to send data over a restricted channel. For example a URL path can’t contain a <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">?</code> or a null byte. A common solution is using some encoding format to convert your data into an acceptable string.</p>
<h2 id="base64" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#base64" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Base64</a></h2>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em"><a href="https://www.rfc-editor.org/rfc/rfc4648.html" style="box-sizing:border-box;margin:0;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray">Base64</a> is a very common format. It can convert arbitrary binary data into an alphabet of 64 characters (plus an extra character for padding if desired).</p>
<div style="background:#222;border-bottom:1px solid #444;border-top:1px solid #444;box-sizing:border-box;display:grid;grid-column:2;grid-column:1/4;grid-template-columns:1fr var(--width) 1fr;margin:0 0 .8em;overflow-x:auto;padding:0"><pre style="box-sizing:border-box;grid-column:2;margin:.4em 1rem"><code style="background:none!important;box-sizing:border-box;color:#fff;margin:0;white-space:pre-wrap;white-space:pre"><span style="box-sizing:border-box;margin:0;padding:0">b64_encode</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">([</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'a'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'?'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'b'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">' '</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0xFF</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">])</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">==</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">"YT8AYiD/"</span>
</code></pre></div>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">With Base64 the output is always longer than the input (other than the empty string). In fact the output length is very easy to predict.</p>
<div style="background:#222;border-bottom:1px solid #444;border-top:1px solid #444;box-sizing:border-box;display:grid;grid-column:2;grid-column:1/4;grid-template-columns:1fr var(--width) 1fr;margin:0 0 .8em;overflow-x:auto;padding:0"><pre style="box-sizing:border-box;grid-column:2;margin:.4em 1rem"><code style="background:none!important;box-sizing:border-box;color:#fff;margin:0;white-space:pre-wrap;white-space:pre"><span style="box-sizing:border-box;color:#ccc;font-style:italic;margin:0;padding:0;white-space:pre-wrap"># Assumes no padding.
</span><span style="box-sizing:border-box;color:#8585e0;font-weight:700;margin:0;padding:0">def</span> <span style="box-sizing:border-box;margin:0;padding:0">b64_length</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">(</span><span style="box-sizing:border-box;margin:0;padding:0">in</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">:</span> <span style="box-sizing:border-box;margin:0;padding:0">bytes</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">)</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">-&gt;</span> <span style="box-sizing:border-box;margin:0;padding:0">int</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">:</span>
	<span style="box-sizing:border-box;margin:0;padding:0">complete_chunks</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">=</span> <span style="box-sizing:border-box;margin:0;padding:0">len</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">(</span><span style="box-sizing:border-box;margin:0;padding:0">in</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">)</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">//</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">3</span>
	<span style="box-sizing:border-box;margin:0;padding:0">remainder</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">=</span> <span style="box-sizing:border-box;margin:0;padding:0">len</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">(</span><span style="box-sizing:border-box;margin:0;padding:0">in</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">)</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">%</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">3</span>

	<span style="box-sizing:border-box;margin:0;padding:0">complete_encoded</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">=</span> <span style="box-sizing:border-box;margin:0;padding:0">complete_chunks</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">*</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">4</span>
	<span style="box-sizing:border-box;margin:0;padding:0">remainder_encoded</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">=</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0</span> <span style="box-sizing:border-box;color:#8585e0;font-weight:700;margin:0;padding:0">if</span> <span style="box-sizing:border-box;margin:0;padding:0">remainder</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">==</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0</span> <span style="box-sizing:border-box;color:#8585e0;font-weight:700;margin:0;padding:0">else</span> <span style="box-sizing:border-box;margin:0;padding:0">remainder</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">+</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">1</span>

	<span style="box-sizing:border-box;color:#8585e0;font-weight:700;margin:0;padding:0">return</span> <span style="box-sizing:border-box;margin:0;padding:0">complete_encoded</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">+</span> <span style="box-sizing:border-box;margin:0;padding:0">remainder_encoded</span>
</code></pre></div>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">The remainder is at most 3 bytes, so we can say that as the input data gets bigger the ratio approaches 4/3. Therefore, encoding data as Base64 will make it more or less 1/3 larger.</p>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Base64 takes a very simple approach to encoding, it takes 3 input bytes and maps that to 4 output bytes. Rinse and repeat until you are done (with a little special logic for any remainder that doesn’t fit into a 3 byte chunk). This is simple, quick and predictable, but the output looks like nonsense <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">cat</code> becomes <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">Y2F0</code> and <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">hello</code> becomes <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">aGVsbG8</code>. What if you want human-readable strings to remain human-readable?</p>
<h2 id="c-string-escaping" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#c-string-escaping" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">C String Escaping</a></h2>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">C-style string escaping is very simple. You have some set of “allowed” characters which are input literally, and anything else needs to be “escaped”.</p>
<div style="background:#222;border-bottom:1px solid #444;border-top:1px solid #444;box-sizing:border-box;display:grid;grid-column:2;grid-column:1/4;grid-template-columns:1fr var(--width) 1fr;margin:0 0 .8em;overflow-x:auto;padding:0"><pre style="box-sizing:border-box;grid-column:2;margin:.4em 1rem"><code style="background:none!important;box-sizing:border-box;color:#fff;margin:0;white-space:pre-wrap;white-space:pre"><span style="box-sizing:border-box;margin:0;padding:0">c_encode</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">([</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'a'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'?'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'b'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">' '</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0xFF</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">])</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">==</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">"a?</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">\x00b</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0"> </span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">\xFF</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">"</span>
</code></pre></div>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Any non-allowed bytes are replaced by a backslash-x (<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\x</code>) then the hex representation of the byte. In practice most implementations have shortcuts for common characters. For example <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\</code> for a backslash and <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\0</code> for a null byte. It is easy enough to read and write by hand.</p>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">So what is the efficiency of this encoding? Well… it depends. If you encode only allowed characters it has a ratio of 1, if you encode only characters with shortcuts it is 2, but if you encode only disallowed characters with no shortcuts it is 4! Unlike Base64 the encoding efficiency is data-dependant.</p>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">But what I find interesting is the scaling of nested encoding. For example imagine that I want to encode a single null byte then encode the result, then encode the result again…</p>
<ol style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\0</code> (2 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\0</code> (3 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\\\0</code> (5 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\\\\\\\0</code> (9 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\\\\\\\\\\\\\\\0</code> (17 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\0</code> (33 bytes)</li>
</ol>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Repeated encoding tends toward doubling in size! That doesn’t seem optimal. You would hope this case is rare but if I had $1 for every time I saw JSON encoded inside a JSON string I could buy myself something nice.</p>
<h2 id="percent-encoding" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#percent-encoding" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Percent Encoding</a></h2>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em"><a href="https://www.rfc-editor.org/rfc/rfc3986.html#section-2.1" style="box-sizing:border-box;margin:0;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray">Percent Encoding</a> is most commonly used in URLs. It is similar to C string escaping except that it doesn’t have a shortcut for the metacharacter itself.</p>
<div style="background:#222;border-bottom:1px solid #444;border-top:1px solid #444;box-sizing:border-box;display:grid;grid-column:2;grid-column:1/4;grid-template-columns:1fr var(--width) 1fr;margin:0 0 .8em;overflow-x:auto;padding:0"><pre style="box-sizing:border-box;grid-column:2;margin:.4em 1rem"><code style="background:none!important;box-sizing:border-box;color:#fff;margin:0;white-space:pre-wrap;white-space:pre"><span style="box-sizing:border-box;margin:0;padding:0">percent_encode</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">([</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'a'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'?'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'b'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">' '</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">,</span> <span style="box-sizing:border-box;color:#ffb433;margin:0;padding:0">0xFF</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">])</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">==</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">"a?%00b %FF"</span>
<span style="box-sizing:border-box;margin:0;padding:0">percent_encode</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">([</span><span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">'%'</span><span style="box-sizing:border-box;color:#999;margin:0;padding:0">])</span> <span style="box-sizing:border-box;color:#f5a3a3;font-weight:700;margin:0;padding:0">==</span> <span style="box-sizing:border-box;color:#b3d733;margin:0;padding:0">"%25"</span>
</code></pre></div>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">It is also data-dependant. Its size ratio varies between 1 and 3. However, it doesn’t have as big of a problem with nested encoding.</p>
<ol style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%00</code> (3 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%2500</code> (5 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%252500</code> (7 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%25252500</code> (9 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%2525252500</code> (11 bytes)</li>
<li style="box-sizing:border-box;margin:0">
<code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%252525252500</code> (13 bytes)</li>
</ol>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Since the encoding doesn’t add additional characters that need escaping the growth on every iteration the growth is a constant factor based on the number of characters in the <strong style="box-sizing:border-box;margin:0">initial</strong> string that require encoding instead of doubling each time.</p>
<h2 id="can-we-do-better" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#can-we-do-better" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Can we do better?</a></h2>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">It is easy to make a minor improvement. In C-style encoding using <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\.</code> instead of <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\\</code> to represent <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\</code> would avoid the problem. Percent Encoding could be slightly optimized by adding shortcuts for common characters (for example <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%p</code> instead of <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">%25</code>) at the cost of complexity and performance.</p>
<h3 id="metacharacter-switching" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#metacharacter-switching" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Metacharacter switching</a></h3>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">One idea is a variable metacharacter. For example imagine encoding <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">"'\</code> as <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\"\'\\</code>. Imagine that we could then do <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\1\"\'\\</code> to say that the metacharacter is now <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">1</code> instead of <code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">\</code>. This would avoid adding characters to the rest of the string, in this example it already saves one character.</p>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">The main downside is that you need to pick one of the following evils:</p>
<ol style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">
<li style="box-sizing:border-box;margin:0">Give up streaming support.</li>
<li style="box-sizing:border-box;margin:0">Allow the metacharacter switch to occur anywhere in the stream.</li>
<li style="box-sizing:border-box;margin:0">Accept that you may not pick the best metacharacter.</li>
</ol>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Not terrible but not great and not pretty.</p>
<h3 id="encoding-level" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#encoding-level" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Encoding Level</a></h3>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">Another idea is declaring the “encoding level” at the start of the message. Upon encountering this the decoder just decrements the counter and passes though the data unchanged.</p>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">For example imagine a modification of base64.</p>
<ol style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">
<li style="box-sizing:border-box;margin:0"><code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">Y2F0</code></li>
<li style="box-sizing:border-box;margin:0"><code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">=1=Y2F0</code></li>
<li style="box-sizing:border-box;margin:0"><code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">=2=Y2F0</code></li>
<li style="box-sizing:border-box;margin:0"><code style="background:#000;border:1px solid #555;border-radius:.3em;box-sizing:border-box;color:#fff;margin:0;padding:.1em;white-space:pre-wrap">=3=Y2F0</code></li>
</ol>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">This has basically the same problems as the first approach and requires you to add another character to your alphabet or require that the nesting level is always declared (which adds overhead for non-nested encodings).</p>
<h3 id="research" style="box-sizing:border-box;grid-column:2;margin:.4em 1rem .8em"><a href="https://kevincox.ca/2022/12/26/nested-encoding-efficency/#research" style="box-sizing:border-box;color:inherit!important;margin:0;text-decoration:inherit;text-decoration:underline;-webkit-text-decoration-color:gray;text-decoration-color:gray;text-shadow:inherit!important">Research?</a></h3>
<p style="box-sizing:border-box;grid-column:2;margin:0 1rem .8em">I tried looking around for a bit but couldn’t find any other discussion on this. I’m probably using the wrong keywords. If you are aware of any encoding systems that have considered this problem please let me know.</p></main>