bitpattern

bitpattern provides BDDSet, a set type for values that can be encoded as fixed-width integers: for instance, IEEE floats and twos-complement integers, unicode codepoints, network addresses, UUIDs, dates and times, enums and tuples of any of these. BDDSets can efficiently represent sets far too large to list and still support the usual set operations, counting, uniform sampling and even indexing.

Consider for example 64 bit floats. How many finite normal floats are there? Can we sample them directly? These sets are huge and noncontiguous, so you can't express them in traditional data structures.

>>> from bitpattern.codecs import float64
>>> normal = float64.finite - float64.subnormal - float64.zeros
>>> normal
BDDSet(float64, [2.2250738585072014e-308, 2.225073858507202e-308, 2.2250738585072024e-308, 2.225073858507203e-308, ..., -1.7976931348623155e+308, -1.7976931348623157e+308], size=18428729675200069632)
>>> 0.25 in normal
True
>>> list(normal[:3])
[2.2250738585072014e-308, 2.225073858507202e-308, 2.2250738585072024e-308]
>>> normal.choice()
2.3171912436506225e+167
>>> float64.range(1.0, 2.0).size
4503599627370496

float64 is the codec that tells bitpattern how to encode float64 values as integers.

Tour

Here's a quick tour, with sampling seeded so it's repeatable:

>>> import random, uuid
>>> from datetime import UTC, date, datetime
>>> from enum import Flag
>>> from bitpattern.codecs import (
...     Flags, char, dates, datetimes, float8_e4m3fn, ipv4, project, uint16, uuid128,
... )
>>> rng = random.Random(0)

>>> # fp8
>>> float8_e4m3fn.finite.size
254
>>> float8_e4m3fn.positive[-1]
448.0
>>> float8_e4m3fn.decode(float8_e4m3fn.encode(0.3))
0.3125
>>> list(float8_e4m3fn.range(1.0, 2.0))
[1.0, 1.125, 1.25, 1.375, 1.5, 1.625, 1.75, 1.875]

>>> # Unicode characters
>>> "É" in char.category("Lu")
True
>>> "".join(char.category("Sm") & char.range("\0", "\x80"))
'+<=>|~'
>>> char.range("a", "{") == char.category("Ll") & char.range("\0", "\x80")
True

>>> # `a * b` is the set of pairs, ie. the cartesian product
>>> networks = ipv4.cidr("10.0.0.0/8") | ipv4.cidr("192.168.0.0/16")
>>> private = networks * uint16.range(1024, 65536)
>>> private.size
1086559617024
>>> ("10.1.2.3", 8080) in private
True
>>> private.choice(rng=rng)
(IPv4Address('10.100.105.211'), 22477)
>>> project(private, 1) == uint16.range(1024, 65536)
True

>>> # UUIDs
>>> uuid128.version(4).size == 2**122
True
>>> uuid.uuid4() in uuid128.version(4)
True
>>> uuid128.version(7).choice(rng=rng)
UUID('14ba5e5a-eaa5-7157-a3e7-0682c2094cac')

>>> # Dates and datetimes
>>> dates.range(date(2024, 1, 1), date(2025, 1, 1)).size
366
>>> new_year = datetime(2024, 1, 1, tzinfo=UTC)
>>> datetimes.range(new_year, datetime(2024, 1, 2, tzinfo=UTC)).size
86400000000

>>> # Flags
>>> class Permission(Flag):
...     READ = 4
...     WRITE = 2
...     EXECUTE = 1
>>> permissions = Flags(Permission)
>>> list(permissions.having(Permission.READ))
[<Permission.READ: 4>, <Permission.READ|EXECUTE: 5>, <Permission.READ|WRITE: 6>, <Permission.READ|WRITE|EXECUTE: 7>]
>>> permissions.pattern("?1?") == permissions.having(Permission.WRITE)
True

Very large sets

bitpattern uses a data structure called a Binary Decision Diagram to encode extremely large sets. Whereas set operations are typically described in terms of the size of the set, bitpattern sets support most operations in O(#bits) of the largest member of the set. #bits is called the width of the set.

Here's how bitpattern's sets compare to other ways of storing a set. n and m are set sizes, w is the width (number of bits of the largest member), and |a| is the number of nodes in a's diagram. |a| is at most n * w and usually much smaller. A set written as a single pattern has |a| <= w, since only its fixed bits need nodes. For most use cases w is a constant and may be read as O(1).

a == b is O(1) between sets of the same codec. Between IntSets of different widths it's O(w).

Hypothesis

bitpattern's sets are particularly useful with hypothesis.

Hypothesis really likes you to express and sample from the true domain of your input data. Rejection sampling (in hypothesis literally sampling from the whole range and then calling reject on inputs that don't match your criteria) frequently eliminates too much data. By default hypothesis will fail tests that reject more than ~80% of inputs, but for instance subnormals are well under 1% of floats, so this isn't practical.

bitpattern.strategies turns these sets into hypothesis strategies:

from hypothesis import given

from bitpattern.codecs import float64
from bitpattern.strategies import from_set


@given(from_set(float64.finite - float64.subnormal))
def test_kernel_matches_reference(x: float): ...

Patterns

The pattern syntax follows normal glob rules. Patterns are expressed as quartets of 4 bits separated by ., most significant to least significant, with 0 and 1 representing a fixed bit, ? can be either, and * is shorthand for multiple ?. The leading quartet can be shorter for widths that aren't a multiple of 4.

Patterns are sets, and work with normal set operations.

>>> from bitpattern import Pattern
>>> Pattern("*1.0000")
Pattern('???1.0000')
>>> Pattern("0000") | Pattern("0001")
Pattern('000?')
>>> ~Pattern("00??")
Pattern('01??') | Pattern('1???')

Codecs accept patterns too and match them against the bits of their encoding. A float64 is a sign bit, 11 exponent bits and 52 mantissa bits. Quiet NaNs have every exponent bit and the top mantissa bit set:

>>> quiet = float64.pattern("?111.1111.1111.1*.*.*.*.*.*.*.*.*.*.*.*.*")
>>> quiet <= float64.nan
True

Codecs

A Codec encodes values of a type as fixed-width integers and decodes them back. Its sets are BDDSets. To write one, subclass Codec and implement encode and decode:

>>> from bitpattern import Codec
>>> class Ascii(Codec[str]):
...     def encode(self, value: object) -> int:
...         if not isinstance(value, str):
...             raise TypeError(f"{value!r} isn't a string")
...         if len(value) != 1 or not value.isascii():
...             raise ValueError(f"{value!r} isn't an ASCII character")
...         return ord(value)
...
...     def decode(self, bits: int) -> str:
...         return chr(bits)
>>> ascii = Ascii(7, "ascii")
>>> ascii.set("hello")
BDDSet(ascii, ['e', 'h', 'l', 'o'])
>>> ascii.pattern("1?0.0001")  # case only changes bit 5
BDDSet(ascii, ['A', 'a'])

encode should raise TypeError for a value of the wrong type and ValueError for a value it can't encode. decode may raise IndexError for bits that aren't a value. If some bit patterns aren't values, override all with the ones that are. ~ and pattern then leave the others out. If encodings sort the same as their values, subclass OrderedCodec instead for min, max and range(start, stop).

bitpattern.codecs includes:

• float16, float32 and float64 as their IEEE 754 bits, and the ML formats bfloat16, float8_e5m2 and float8_e4m3fn. They have sets like finite, nan, infinities, subnormal and zeros.
• int8 through int128 in two's complement, and uint8 through uint128.
• char, Unicode scalar values as one-character strings, with category(name) for general categories like "Lu" or "L".
• ipv4 and ipv6, with cidr("10.0.0.0/8"). networks(addresses) finds the fewest CIDR blocks that make up a set.
• mac, MAC addresses like 01:23:45:67:89:ab, with multicast, unicast, local, universal, broadcast and oui(prefix).
• uuid128, uuid.UUIDs, with version(n) for RFC 9562's versions 1 to 8 and rfc9562 for its variant.
• dates and datetimes. datetimes holds timezone-aware datetimes and decodes them into UTC. DateTime(tz) decodes into tz instead, and naive_datetimes holds naive datetimes.
• Members(SomeEnum) for an Enum's members, and Flags(SomeFlag) for a Flag's combinations, with having(flags) and lacking(flags).

All of these but the enums and flags are ordered, with min, max and range(start, stop). A bound of None leaves that end unbounded.

product(a, b, c) is the set of tuples itertools.product(a, b, c) would give, and a * b is product(a, b). Their codec is a Tuple, with the first field's bits on top. A product has about as many nodes as its sets combined. project gets the values of one field.

IntSet

IntSet backs BDDSets and patterns, and works on its own too. An IntSet is an immutable set of non-negative integers below 2 ** width. It's a collections.abc.Set and a Sequence of its members in sorted order. Slicing gives back a set.

An IntSet is a reduced, ordered binary decision diagram, or BDD (Bryant, 1986). bitpattern.BDD is the diagram itself, implemented in Mojo.

>>> from bitpattern import IntSet
>>> s = IntSet.range(3, 17)
>>> s
IntSet([3, 4, 5, 6, ..., 15, 16], size=14, width=5)
>>> s[2]
5
>>> s[2:5]
IntSet([5, 6, 7], width=5)
>>> s & IntSet([1, 2, 3, 4])
IntSet([3, 4], width=5)
>>> ~IntSet([1, 3], width=2)
IntSet([0, 2], width=2)

IntSets and BDDSets support DLPack, so numpy.from_dlpack copies a set's members into an array. An IntSet exports as the narrowest unsigned int that fits its width (rows of bytes past 64 bits), and a BDDSet as its codec's dtype().

>>> import numpy as np
>>> from bitpattern.codecs import float32
>>> np.from_dlpack(IntSet([300, 1, 20]))
array([  1,  20, 300], dtype=uint16)
>>> np.from_dlpack(float32.set([0.5, 0.25, 1.0]))
array([0.25, 0.5 , 1.  ], dtype=float32)

R. E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, 35(8):677–691, 1986.