Morton encoding in Python
Computes the Z-order index of a point by interleaving the bits of its coordinates, using magic-mask spreading.
- File
morton_encoding.py, 56 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/morton-encoding/. The authors are listed in prov/JEHNP6.jsonl.
MASK64 = (1 << 64) - 1
MASK32 = (1 << 32) - 1
def spread(x: int) -> int:
"""Move bit i of a 32-bit x to bit 2i of a 64-bit word.
Higher bits of x are ignored. Cost: 5 stages of 3 word operations.
"""
x &= MASK32
x = (x | (x << 16)) & 0x0000FFFF0000FFFF # @line L1
x = (x | (x << 8)) & 0x00FF00FF00FF00FF # @line L2
x = (x | (x << 4)) & 0x0F0F0F0F0F0F0F0F # @line L3
x = (x | (x << 2)) & 0x3333333333333333 # @line L4
x = (x | (x << 1)) & 0x5555555555555555 # @line L5
return x # @line L6
def morton_encode(x: int, y: int) -> int:
"""Return the 64-bit Morton code of (x, y): x in the even bits, y in the odd bits."""
return spread(x) | ((spread(y) << 1) & MASK64) # @line L7
def compact(z: int) -> int:
"""Inverse of spread: move bit 2i of a 64-bit z to bit i; odd bits are ignored."""
z &= 0x5555555555555555
z = (z ^ (z >> 1)) & 0x3333333333333333
z = (z ^ (z >> 2)) & 0x0F0F0F0F0F0F0F0F
z = (z ^ (z >> 4)) & 0x00FF00FF00FF00FF
z = (z ^ (z >> 8)) & 0x0000FFFF0000FFFF
z = (z ^ (z >> 16)) & 0x00000000FFFFFFFF
return z
def morton_decode(z: int) -> tuple[int, int]:
"""Return (x, y) with morton_encode(x, y) == z, for 0 <= z < 2**64."""
z &= MASK64
return compact(z), compact(z >> 1)
def spread3(x: int) -> int:
"""Move bit i of a 10-bit x to bit 3i of a 32-bit word."""
x &= 0x3FF
x = (x | (x << 16)) & 0x030000FF
x = (x | (x << 8)) & 0x0300F00F
x = (x | (x << 4)) & 0x030C30C3
x = (x | (x << 2)) & 0x09249249
return x
def morton_encode3(x: int, y: int, z: int) -> int:
"""Return the 30-bit Morton code of three 10-bit coordinates."""
return spread3(x) | (spread3(y) << 1) | (spread3(z) << 2)
test_morton_encoding.py 81 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/morton-encoding/. The authors are listed in prov/JEHNP6.jsonl.
import random
from morton_encoding import (
compact,
morton_decode,
morton_encode,
morton_encode3,
spread,
spread3,
)
def interleave(coords: list[int], b: int) -> int:
"""Oracle: bit i of coordinate j goes to bit d*i + j, one bit at a time."""
d = len(coords)
z = 0
for i in range(b):
for j, c in enumerate(coords):
z |= ((c >> i) & 1) << (d * i + j)
return z
def test_example() -> None:
assert spread(181) == 0x4511
assert spread(90) == 0x1144
assert morton_encode(181, 90) == 0x6799 == 26521
assert morton_decode(0x6799) == (181, 90)
def test_grid_4x4() -> None:
rows = [[morton_encode(x, y) for x in range(4)] for y in range(4)]
assert rows == [[0, 1, 4, 5], [2, 3, 6, 7], [8, 9, 12, 13], [10, 11, 14, 15]]
def test_spread_exhaustive_16_bits() -> None:
for x in range(1 << 16):
s = spread(x)
assert s == interleave([x, 0], 16)
assert compact(s) == x
def test_extremes() -> None:
top = (1 << 32) - 1
assert morton_encode(top, top) == (1 << 64) - 1
assert morton_encode(top, 0) == 0x5555555555555555
assert morton_encode(0, top) == 0xAAAAAAAAAAAAAAAA
assert morton_decode((1 << 64) - 1) == (top, top)
def test_random_against_oracle() -> None:
rng = random.Random(20261104)
for _ in range(20000):
x = rng.getrandbits(32)
y = rng.getrandbits(32)
z = morton_encode(x, y)
assert z == interleave([x, y], 32)
assert morton_decode(z) == (x, y)
for _ in range(20000):
z = rng.getrandbits(64)
x, y = morton_decode(z)
assert morton_encode(x, y) == z
def test_axis_order() -> None:
rng = random.Random(7)
for _ in range(5000):
x, x2, y = rng.getrandbits(32), rng.getrandbits(32), rng.getrandbits(32)
if x < x2:
assert morton_encode(x, y) < morton_encode(x2, y)
def test_three_coordinates_exhaustive_per_axis() -> None:
for x in range(1 << 10):
assert spread3(x) == interleave([x, 0, 0], 10)
rng = random.Random(3)
for _ in range(20000):
c = [rng.getrandbits(10) for _ in range(3)]
assert morton_encode3(*c) == interleave(c, 10)
What the next level needs
- the tests did not run in this build