Packing an Entire Country Record into a Single uint64

An anatomy of the nurago countrycode package: a full ISO 3166 country record packed into one uint64 using a Reversible Numeric Composite Key, decoded with pure bit shifts.

-
Updated:

Table of contents

Country metadata is one of those unglamorous needs that turns up in most backends. Translate US to USA to 840. Find which region a country belongs to. Validate a country top-level domain (TLD). The usual answer is a pile of maps, one per lookup direction, each holding strings, and it works well enough that nobody looks twice at it.

The countrycode package in nurago does something else. Internally, an entire International Organization for Standardization (ISO) 3166 country record is encoded into a single 64-bit integer, and every lookup is a handful of shifts away from that one number.

The surface API

From the outside, the package looks like any other lookup library:

import "github.com/tecnickcom/nurago/pkg/countrycode"

data, err := countrycode.New(nil) // embedded ISO 3166 defaults
if err != nil {
    log.Fatal(err)
}

c, err := data.CountryByAlpha2Code("US")
// c.Alpha3Code == "USA", c.NumericCode == "840",
// c.NameEnglish == "United States of America (the)", c.TLD == "us"

italy, _ := data.CountryByAlpha3Code("ITA")
europe, _ := data.CountriesByRegionName("Europe")

Failures come back as two exported sentinels, ErrInvalidCode for malformed input and ErrNotFound for a miss, both matchable with errors.Is. You can also pass your own []*CountryData to New for private overrides or curated subsets. The returned Data is read-only after construction and safe for concurrent use. Nothing on that surface hints at the representation underneath.

Anatomy of a country key

Internally the package calls this a country key: a uint64 that packs every identifying field of a record into a fixed bit range. This is an application of the Reversible Numeric Composite Key (RNCK) technique, cited in the source itself (N. Asuni, Reversible Numeric Composite Key, arXiv:2306.04353, 2023). The layout is declared as constants, with bitLenChar = 5:

// Binary length of each CountryKey section.
const (
	bitLenTLD       int = 2 * bitLenChar // 2 characters, 5 bit per character.
	bitLenIntRegion int = 5              // max 2^5 = 32 distinct values.
	bitLenSubRegion int = 5              // max 2^5 = 32 distinct values.
	bitLenRegion    int = 5              // max 2^5 = 32 distinct values.
	bitLenNumeric   int = 10             // max 3 numerical digits: log2(999) ~> 10.
	bitLenAlpha3    int = 3 * bitLenChar // 3 characters, 5 bit per character.
	bitLenAlpha2    int = 2 * bitLenChar // 2 characters, 5 bit per character.
	bitLenStatus    int = 3              // max 2^3 = 8 distinct values.
)

Stacked from the least significant bit, that gives the TLD at position 0, intermediate region at 10, sub-region at 15, region at 20, numeric code at 25, alpha-3 at 35, alpha-2 at 50, and the 3-bit assignment status at 60. That is 63 bits, leaving the top bit unused. The status field enumerates the seven ISO 3166 states, from “Unassigned” through “Officially assigned” to “Formerly assigned”. The three region fields do not store United Nations M49 codes directly; they store an index into a small catalogue that maps the index back to its code and name.

A real key makes it concrete. The embedded dataset stores the United States as 0x1ACEB30E903102B3, which unpacks like this:

BitsSliceDecodes to
62-60001status 1, “Officially assigned”
59-5010101 10011letters 21, 19: “US”
49-3510101 10011 00001letters 21, 19, 1: “USA”
34-251101001000numeric code 840
24-2000011region 3: “019”, Americas
19-1500010sub-region 2: “021”, Northern America
14-1000000no intermediate region
9-010101 10011TLD “us”

Encoding is a sequence of shifts and ORs (encodeCountryKey). Decoding is masks and shifts (decodeCountryKey), mirroring it step for step. The same uint64 round-trips back to the record it came from, and every index the package builds is derived from that round trip.

Five bits per letter

Letter codes fit because the alphabet is small. Alpha-2 and alpha-3 codes are drawn from 26 letters, so each letter fits in 5 bits (2^5 = 32) as its 1-based offset from A, with 0 left over to mean “no value here”:

func charOffset(b byte, offset uint16) (uint16, error) {
	c := (uint16(b) - offset)
	if c < 1 || c > 26 { // A-Z or a-z
		return 0, errInvalidCharacter
	}

	return c, nil
}

Two letters make a 10-bit alpha-2, three letters a 15-bit alpha-3, and the two-character TLD is another 10 bits with a lowercase offset. Decoding is the mirror image, three masks and three shifts:

func decodeAlpha3(code uint16) string {
	return string([]byte{
		byte(((code & bitMaskChar2) >> bitPosChar2) + chrOffsetUpper),
		byte(((code & bitMaskChar1) >> bitPosChar1) + chrOffsetUpper),
		byte(((code & bitMaskChar0) >> bitPosChar0) + chrOffsetUpper),
	})
}

The package fuzz-tests this round trip: any string accepted by the encoder must decode back to itself, for alpha-2, alpha-3, and TLD alike.

Why bit-packing beats maps and string tables

For static reference data, the packed form pays for itself in a few places.

One source of truth. All the reverse indexes (alpha-3 to alpha-2, numeric to alpha-2, groupings by region, status, and TLD) are generated at construction time by decoding the packed keys. The “alpha-2 to alpha-3” table and its inverse are derived from the same integer rather than maintained by hand, so they do not drift apart.

Memory. The identifying core of every country is 8 bytes in a map[uint16]uint64. The English and French names live in a separate map keyed by the same 10-bit alpha-2 ID and are only referenced when a record is materialised.

Cheap decoding. Alpha-2 and TLD strings are sliced out of two precomputed 2 KiB tables covering the whole 10-bit code space, and the zero-padded numeric code is sliced from a precomputed "000001...999" string rather than going through fmt.Sprintf. Alpha-3 is the one deliberate exception, since a dense table over its 15-bit space would cost 96 KiB, so those three bytes are computed per call. That leaves exactly two heap allocations per single-country lookup: the returned CountryData and that 3-byte string.

$ go test -run='^$' -bench=. -benchmem ./pkg/countrycode/
goos: linux
goarch: amd64
cpu: 12th Gen Intel(R) Core(TM) i7-1260P
BenchmarkNew-16                   4627   224868 ns/op   114222 B/op   785 allocs/op
BenchmarkCountryByAlpha2Code-16  11000457    109.5 ns/op    227 B/op     2 allocs/op
BenchmarkCountryByAlpha3Code-16   9064006    121.7 ns/op    227 B/op     2 allocs/op
BenchmarkCountryByNumericCode-16  9010614    135.5 ns/op    227 B/op     2 allocs/op

New is the one expensive call, paid once at startup to build every derived index.

Partial records

ISO 3166 is messier than its reputation. The embedded dataset resolves every two-letter combination from AA to ZZ, all 676 of them, but many are reserved or unassigned codes with almost no metadata: EU is “Exceptionally reserved” and carries nothing beyond its status and alpha-2 code, and plain unused combinations come back as “Unassigned”. The decoder handles this by populating each optional field only when it is present in the key, so a record keeps whatever data it actually has instead of being silently reduced to the fields common to every entry.

Absence itself is encoded as zero. Index 0 of each region catalogue is an empty sentinel meaning “no region”, and it is kept strictly internal: the EnumRegion family of methods skips it, and resolving an empty region code or name returns ErrNotFound rather than leaking the sentinel as if it were a valid value.

Custom datasets, same binary form

Passing your own records to New does not switch the package into a slower generic mode. Loading works in two passes: the first collects the region, sub-region, and intermediate-region catalogues from your records (sorted by code, so catalogue indexes are stable across builds), and the second encodes each record into a country key through the same path that produced the embedded defaults. Only Status and Alpha2Code are required; every other field is best-effort, and an absent or malformed optional field encodes to zero rather than failing the record. If two records share an alpha-2 code, the last one wins. After that, custom data and embedded data are indistinguishable, down to the lookup cost.

When it matters

For one occasional lookup you would never notice the difference between this and a naive map. The technique earns its place when country resolution sits on a hot path: validation and enrichment on every inbound request, or geographic joins across a large dataset. At 110 ns and 8 bytes of key per country, it stays out of the profile.

Bit-packing generalises past this use case. The RNCK paper applies the same construction to any set of short, bounded, categorical fields that has to survive a round trip through a single integer.