bitpattern

bitpattern is a library for describing and working with very large sets of structured data. It can sample and count sets much larger than would ordinarily fit in memory.

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
>>> supported = float64.finite - float64.subnormal
>>> supported.size
18428729675200069634
>>> 0.25 in supported
True
>>> list(supported[:3])
[0.0, 2.2250738585072014e-308, 2.225073858507202e-308]
>>> supported.choice()
2.3171912436506223e+167
>>> float64.range(1.0, 2.0).size
4503599627370496

supported is a BDDSet[float], a set of floats backed by the IntSet of their bits, supported.storage. float64 is the codec that encodes them. BDDSets work with the normal set operations, and are also sequences of their values, in the order of their bits.

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.

This becomes particularly useful for use cases like 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 take patterns too, which match the bits of their encoding. A float64 is a sign bit, 11 exponent bits and 52 mantissa bits, and 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, so patterns match the bits of the encoding. 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 isinstance(value, str) and len(value) == 1 and value.isascii():
...             return ord(value)
...         raise ValueError(f"{value!r} isn't an ASCII character")
...
...     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 ValueError for anything it can't encode. If some bit patterns aren't values, override all with the ones that are, so that ~ leaves the others out.

bitpattern.codecs includes:

• float16, float32 and float64, which are IEEE 754 floats as their raw bits. They have sets like finite, nan, infinities, subnormal and zeros, and range(low, high).
• ipv4 and ipv6, with cidr("10.0.0.0/8") and range(low, high). networks(addresses) finds the fewest CIDR blocks that make up a set of addresses.

IntSet

IntSet is the backing abstraction for BDDSets and patterns, and is provided directly. An IntSet is an immutable set of non-negative integers below 2 ** width. It's a collections.abc.Set, and also 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). The BDD abstraction is also provided directly, as bitpattern.BDD.

>>> 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)

Here's how IntSet compares 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 is usually much smaller. Notably, 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 width, and O(w) between different widths.

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