M. J. Fromberger creachadair

Self-Framing Packed Binary Lengths

We describe a variable-width binary encoding format for unsigned integer lengths that handles values up to 1073741823 $(2^{30} - 1)$ and does not require complex bit manipulation to pack and unpack.

In summary: The input is encoded as little-endian, with the excess length of the encoding packed into the lowest-order 2 bits of the value. This makes the encoding self-framing, as the decoder can consume the first byte and immediately know how many additional bytes must be read to recover the original value. The only operations required are integer addition, multiplication, and division/remainder by powers of 2 (specificially, 4 and 256).

The algorithm below is described for 32-bit unsigned integers, but it can be extended trivially to 64-bit integers by using the lowest-order 3 bits instead of 2, or contracted to 16-bit integers using the lowest-order 1 bit.

A Go implementation

GitHub renders Markdown in its UI according to the [GitHub Flavored Markdown (GFM)][gfm] spec. In addition, it adds generated link anchors for document headers. For example, a Markdown heading like:

## Fee Fie Fo Fum

is rendered with a link anchor of #fee-fie-fo-fum in the GitHub UI. Knowing this, you may wish to add links in other Markdown documents in your repository that point to those anchor targets. There are various descriptions floating around about how to do this, but all the ones I found contain subtle errors. This document attempts to clarify the rule.

Definitions

Option Plumbing in Go

This gist outlines my current preferred library package organization style in Go. There are a few explanatory comments, but for the most part it's just an extended example.

// Package thing is named for the concept it implements.
package thing

// Thing is the principal type that implements the concept.
// Although this does stutter a little with the package name,

Constructing Pointers to Type Parameters

I wanted to have a function that could construct a value satisfying an interface, do some setup on that value, and then pass the constructed value to some other operation. Schematically:

func doAThing(fn func(*Input) (Output, error)) (Output, error) {
    in := new(Input)
    in.Setup()
    return fn(in)
}

Checking Type Parameters for Optional Interface Satisfaction

With Go generics, it is not permitted to check whether a value whose type comes from a type parameter satisfies some optional interface. For example, the following code will not compile (as of Go 1.20):

type Q interface{ Q() }

func G[T any](t T) {
	if q, ok := t.(Q); ok {
 q.Q()

Go library: https://pkg.go.dev/github.com/icza/mjpeg

Wikipedia: https://en.wikipedia.org/wiki/Motion_JPEG

Thinking maybe read the frames from the GIF and render them to MJPEG.

Use of Underlying Types in Go Generics

When specifying the type parameters for a generic structure in Go, you can use the notation ~T to mean "any type whose underlying structure is equivalent to T". For example, given:

func F[X ~string](x X) {}

the type parameter X can be instantiated with any type whose underlying representation is string. That includes string itself, of course, along with types like type Foo string which are based on it.

Links to various Go playground examples

	package main_test

	import (
	"fmt"
	"testing"
	)

	func BenchmarkBuf(b *testing.B) {
	for _, bs := range []int{0, 1, 2, 10, 32} {
	b.Run(fmt.Sprint(bs), func(b *testing.B) {