CIDARTHA5

CIDR IP Discrimination And Resolution Trie with Hybrid Algorithms

CIDARTHA5 is the native/C generation of CIDARTHA: a high-performance CIDR membership engine with a mutable IPv4/IPv6 control plane and compiled read-only IPv4 data planes. The hot paths are implemented in C and exposed directly to Python through a CPython extension.

CIDARTHA4 is the previous Python-only generation. Its implementation remains in CIDARTHA4.py as the legacy compatibility/reference backend and differential-test oracle; it is not the identity of the v5 native engine.

Overview

CIDARTHA deliberately uses different structures for different workloads instead of forcing every use case into one trie:

Profile	Families	Mutable	Intended use
Native mutable	IPv4 + IPv6	yes	dynamic firewall/allowlist control plane
Compact snapshot	IPv4	rebuild	low-memory, high-throughput read plane
Balanced snapshot	IPv4	rebuild	adaptive D24 middle Pareto point
Speed snapshot	IPv4	rebuild	maximum packed-batch membership throughput

The immutable snapshots exploit a stronger invariant than ordinary longest-prefix routing: boolean CIDR membership is exactly membership in the union of the CIDRs' integer intervals. CIDARTHA can therefore merge redundant/adjacent ranges during compilation and use direct segmented representations that would not be valid for a conventional LPM router.

Key Features

• Native C core + direct CPython extension: no subprocess, JSON, socket, or ctypes hop in the Python hot path.
• Packed batch APIs: cross Python/C once for thousands or millions of lookups while the GIL is released.
• Mutable IPv4/IPv6 engine: compact 4-bit-stride arena with bitmap-ranked children, unary-child inlining, exact insertion/removal, and reader/writer synchronization.
• Compact IPv4 snapshot: /16 direct directory, adaptive local radix refinement, RUN32/ARRAY16 container selection, and AVX2 small-group search when available.
• Balanced IPv4 snapshot: /24 direct state with 32-bit adaptive micro-container descriptors; common single-run/two-value cases are completely inline.
• Speed IPv4 snapshot: /24 full/partial/empty state plus exact 256-bit residual bitmaps; no predecessor search in the lookup path.
• Correct pure-Python fallback: useful where compiling a native extension is not possible.
• Stable native surface: exported C ABI in native/cidartha_core.h and native/cidartha_snapshot.h.
• Correctness guardrails: randomized differential tests against Python ipaddress, family-isolated wildcards, partial-prefix removal tests, and packed-batch parity tests.

Installation

The source tree is installable as a normal Python package and will compile the native extension:

python -m pip install .

For a local machine where portability is not required, enable native CPU code generation. On PowerShell:

$env:CIDARTHA_NATIVE_CPU = "1"
python -m pip install .

For development on Windows, the repository also provides an explicit clang build using the Visual Studio SDK environment:

powershell -ExecutionPolicy Bypass -File native/build_native.ps1 -NativeCpu -CompactChildren

The historical pure-Python import remains supported:

from CIDARTHA4 import CIDARTHA

Quick Start

Mutable IPv4/IPv6 rules

from CIDARTHA5 import create_mutable

firewall = create_mutable()
firewall.batch_insert([
    "10.0.0.0/8",
    "192.168.1.0/24",
    "2001:db8::/32",
])

assert firewall.check("10.20.30.40")
firewall.remove("10.0.0.0/8")

Immutable IPv4 read planes

from CIDARTHA5 import create_ipv4_snapshot

rules = ["10.0.0.0/8", "192.168.0.0/16", "203.0.113.7/32"]

# smallest high-throughput native representation
compact = create_ipv4_snapshot(rules, profile="compact")

# middle Pareto point: D24 direct dispatch with compressed sparse residuals
balanced = create_ipv4_snapshot(rules, profile="balanced")

# spends more memory to remove local search from the hot path
speed = create_ipv4_snapshot(rules, profile="speed")

assert speed.check("203.0.113.7")

For one-at-a-time IPv4 checks, prefer the compact D16 snapshot and Python's containment operator. The extension implements sq_contains directly in C, so ip in snapshot bypasses bound-method creation/calling overhead:

import ipaddress

compact = create_ipv4_snapshot(rules, profile="compact")

# Convenient scalar string path.
blocked = "203.0.113.7" in compact

# Lower-overhead scalar forms when the caller already has a parsed address.
blocked = int(ipaddress.IPv4Address("203.0.113.7")) in compact
blocked = ipaddress.IPv4Address("203.0.113.7").packed in compact

check(), check_text(), check_u32(), and check_packed() remain available when an explicit method call is more convenient. The containment form is the latency-oriented Python API.

For maximum throughput, pack IPv4 addresses contiguously and cross into C once:

import socket

ips = ["10.1.2.3", "8.8.8.8", "203.0.113.7"]
packed = b"".join(socket.inet_pton(socket.AF_INET, ip) for ip in ips)

hits = speed.count_many_packed(packed)
results = speed.check_many_packed(packed)  # one byte per address

Embedding the C library directly

native/build_native.ps1 also emits native/build/cidartha_core.dll plus its Windows import library. The exported ABI is independent of CPython and includes the mutable engine and all immutable IPv4 snapshot profiles:

#include "cidartha_core.h"
#include "cidartha_snapshot.h"

cidartha_t *rules = cidartha_create();
cidartha_insert_text(rules, "10.0.0.0/8");
int hit = cidartha_check_text(rules, "10.2.3.4");
cidartha_destroy(rules);

For throughput-sensitive callers, prefer the packed batch functions rather than calling the scalar text parser in a loop. examples/c_embed.c demonstrates both the mutable C API and the D24 exact-bitmap snapshot API.

Legacy CIDARTHA4 Python API

The sections below document the original Python-only CIDARTHA4 object API, including its MessagePack persistence and configurable Python caches. They are retained because CIDARTHA5 deliberately keeps v4 available as a reference and fallback. New v5 code should normally use the CIDARTHA5 facade and the native profiles shown above.

CIDARTHA4 usage examples

Basic Operations

from CIDARTHA4 import CIDARTHA

# Initialize
firewall = CIDARTHA()

# Insert individual CIDR blocks
firewall.insert("172.16.0.0/12")
firewall.insert("192.168.0.0/16")

# Check IP addresses
firewall.check("172.16.50.1")     # Returns True
firewall.check("192.168.1.1")     # Returns True
firewall.check("8.8.8.8")         # Returns False

# Remove a CIDR block
firewall.remove("172.16.0.0/12")
firewall.check("172.16.50.1")     # Now returns False

# Clear all entries
firewall.clear()

Batch Operations

# Batch insert for large datasets
cidr_list = [
    "10.0.0.0/8",
    "172.16.0.0/12",
    "192.168.0.0/16",
    "203.0.113.0/24",
    "198.51.100.0/24"
]

firewall.batch_insert(cidr_list)

Serialization and Persistence

# Save firewall state to disk
firewall = CIDARTHA()
firewall.insert("192.168.0.0/16")
firewall.insert("10.0.0.0/8")

# Serialize to bytes
serialized = firewall.dump()

# Save to file
with open("firewall_rules.msgpack", "wb") as f:
    f.write(serialized)

# Load from file
with open("firewall_rules.msgpack", "rb") as f:
    data = f.read()

# Restore firewall state
restored_firewall = CIDARTHA.load(data)
restored_firewall.check("192.168.1.1")  # Returns True

Thread-Safe Concurrent Operations

import threading
from CIDARTHA4 import CIDARTHA

firewall = CIDARTHA()

def worker_insert(cidr_list):
    for cidr in cidr_list:
        firewall.insert(cidr)

def worker_check(ip_list):
    results = [firewall.check(ip) for ip in ip_list]
    return results

# Safe concurrent access
thread1 = threading.Thread(target=worker_insert, args=(["10.0.0.0/8"],))
thread2 = threading.Thread(target=worker_check, args=(["10.0.0.1"],))

thread1.start()
thread2.start()
thread1.join()
thread2.join()

IPv6 Support

firewall = CIDARTHA()

# IPv6 CIDR blocks
firewall.insert("2001:db8::/32")
firewall.insert("fe80::/10")
firewall.insert("::1/128")  # Loopback

# Check IPv6 addresses
firewall.check("2001:db8::1")      # Returns True
firewall.check("fe80::1")          # Returns True
firewall.check("2001:4860::8888")  # Returns False

Wildcard Matching

firewall = CIDARTHA()

# Match all IPv4 addresses
firewall.insert("0.0.0.0/0")

# Now all IPv4 addresses match
firewall.check("1.2.3.4")      # Returns True
firewall.check("192.168.1.1")  # Returns True

CIDARTHA4 legacy configuration

CIDARTHA supports extensive configuration to customize cache sizes, logging behavior, and other operational parameters. Configuration is completely optional - CIDARTHA works with sensible defaults out of the box.

Using Configuration

from CIDARTHA4 import CIDARTHA, configure_global_ip_cache
from config import CIDARTHAConfig
import logging

# Create instance with custom configuration
config = CIDARTHAConfig(
    ip_network_cache_size=8192,      # Cache for ip_network objects
    check_cache_size=8192,            # Cache for IP lookup results
    log_level=logging.DEBUG,          # Logging level
    batch_insert_log_interval=0.1     # Log every 10% during batch insert
)
firewall = CIDARTHA(config=config)

# Or configure global IP cache (shared across all instances)
configure_global_ip_cache(16384)  # Increase global IP cache to 16384

Configuration Options

The CIDARTHAConfig dataclass provides the following options:

• ip_to_bytes_cache_size (int, default: 8192): LRU cache size for IP string to bytes conversion. This cache is global and shared across all CIDARTHA instances. Use configure_global_ip_cache() to adjust it at runtime.

• ip_network_cache_size (int, default: 4096): LRU cache size for ip_network objects used during insertion.

• check_cache_size (int, default: 4096): LRU cache size for IP lookup results. Frequently checked IPs will be served from cache.

• log_level (int, default: logging.INFO): Logging level for the CIDARTHA logger. Options: logging.DEBUG, logging.INFO, logging.WARNING, logging.ERROR.

• batch_insert_log_interval (float, default: 0.05): Progress logging interval for batch inserts as a fraction (0.05 = 5%, meaning log every 5% of entries).

Configuration Examples

Memory-Constrained Environments

# Reduce cache sizes for low-memory systems
config = CIDARTHAConfig(
    ip_network_cache_size=512,
    check_cache_size=512
)
firewall = CIDARTHA(config=config)

High-Performance Environments

# Increase cache sizes for better performance
config = CIDARTHAConfig(
    ip_network_cache_size=16384,
    check_cache_size=16384
)
configure_global_ip_cache(32768)
firewall = CIDARTHA(config=config)

Custom Logging

# Enable debug logging and more frequent progress updates
config = CIDARTHAConfig(
    log_level=logging.DEBUG,
    batch_insert_log_interval=0.1  # Log every 10%
)
firewall = CIDARTHA(config=config)

Global Default Configuration

# Set a global default configuration for all new instances
from config import set_default_config, CIDARTHAConfig

set_default_config(CIDARTHAConfig(
    check_cache_size=8192,
    log_level=logging.WARNING
))

# All new instances will use this configuration
fw1 = CIDARTHA()  # Uses global default
fw2 = CIDARTHA()  # Also uses global default

CIDARTHA4 legacy API reference

CIDARTHA(config=None)

Creates a new CIDARTHA instance.

Parameters:

• config (CIDARTHAConfig, optional): Configuration object. If None, uses global default configuration.

# Default configuration
firewall = CIDARTHA()

# Custom configuration
from config import CIDARTHAConfig
config = CIDARTHAConfig(check_cache_size=8192)
firewall = CIDARTHA(config=config)

configure_global_ip_cache(cache_size: int = 8192)

Configure the global IP to bytes cache size (module-level function).

Parameters:

• cache_size (int): Maximum number of IP addresses to cache

from CIDARTHA4 import configure_global_ip_cache
configure_global_ip_cache(16384)  # Double the default cache size

insert(input_data: str)

Inserts a CIDR block into the trie. Thread-safe.

Parameters:

• input_data (str): CIDR notation string (e.g., "192.168.1.0/24")

Raises:

• ValueError: If the input is not a valid IP or CIDR range

firewall.insert("192.168.1.0/24")

batch_insert(entries: list)

Inserts multiple CIDR blocks efficiently with progress logging.

Parameters:

• entries (list): List of CIDR notation strings

firewall.batch_insert(["10.0.0.0/8", "172.16.0.0/12"])

check(ip) -> bool

Checks if an IP address matches any stored CIDR block. Optimized with LRU caching.

Parameters:

• ip: IP address as string, bytes, int, or IPv4Address/IPv6Address object

Returns:

• bool: True if IP matches a stored CIDR block, False otherwise

is_blocked = firewall.check("192.168.1.100")

remove(cidr: str)

Removes a CIDR block from the trie. Thread-safe.

Parameters:

• cidr (str): CIDR notation string to remove

Raises:

• ValueError: If the input is not a valid CIDR range

firewall.remove("192.168.1.0/24")

clear()

Removes all entries from the trie. Thread-safe.

firewall.clear()

dump() -> bytes

Serializes the entire trie to compact msgpack bytes.

Returns:

• bytes: Serialized trie data

data = firewall.dump()

load(serialized_data: bytes, config=None) -> CIDARTHA

Static method to deserialize a trie from msgpack bytes.

Parameters:

• serialized_data (bytes): Serialized trie data
• config (CIDARTHAConfig, optional): Configuration for the loaded instance

Returns:

• CIDARTHA: New CIDARTHA instance with restored data

# Load with default configuration
firewall = CIDARTHA.load(data)

# Load with custom configuration
config = CIDARTHAConfig(check_cache_size=8192)
firewall = CIDARTHA.load(data, config=config)

Performance Characteristics

Mutable engine

The native mutable index consumes address bits four at a time. IPv4 therefore needs at most 8 nibble transitions and IPv6 at most 32, with early termination whenever a stored prefix matches. The production layout stores only present children, ranks them using a 16-bit bitmap/popcount, and keeps unary children inline.

Immutable IPv4 snapshots

Snapshot compilation first canonicalizes CIDRs into a sorted union of disjoint integer intervals.

The compact profile dispatches on the high 16 address bits. A bucket is immediately empty/full, stores a common one-run/2-3-value/run+singleton case directly in its 8-byte descriptor, or points to a compact RUN32/ARRAY16 payload. Dense payloads get an adaptive radix index that bounds the remaining local candidate group. Accelerator metadata is packed into the same 8-byte descriptor, avoiding a dependent metadata-table load during scalar checks.

The balanced profile also dispatches on the high 24 bits, but compresses each partial /24 into a 32-bit descriptor plus an adaptive ARRAY8/RUN8/BITMAP256 payload only when necessary. On the current FireHOL corpus, most partial segments fit entirely in the descriptor as one run or two exact values.

The speed profile dispatches on the high 24 bits. A /24 is empty, full, or partial; partial segments own an exact 256-bit low-byte bitmap. Lookup therefore contains no binary/predecessor/container search.

Benchmarks

The optimization campaign uses six FireHOL blocklist-ipsets sources, cached locally after download. The current corpus contains 313,598 unique IPv4 CIDRs. Lookup workloads are deterministic and deliberately contain 50% hits / 50% misses; result counts are checked against the corrected Python reference on every run.

Representative measurements from the development machine are:

Engine/profile	Build	Packed batch lookup	Native/accounted structure
Mutable compact C	~8.7 M rules/s	~22 M/s	~15.5 MB arena
Mutable fixed fanout	~4.4 M rules/s	~26 M/s	~73.2 MB arena
Compact D16 snapshot	~20 M rules/s	~80-90 M/s bulk	~1.36 MB
Balanced D24 snapshot	~18.3 M rules/s	~146.5 M/s count / ~144.2 M/s results	~5.25 MB
Speed D24 bitmap snapshot	~23.5 M rules/s	~180.3 M/s count / ~181.3 M/s results	~9.65 MB

Numbers are workload- and CPU-dependent, and Windows scheduling introduces measurable run-to-run noise. Treat them as reproducible local engineering results, not universal guarantees. Benchmark commands write machine-readable local artifacts to the ignored benchmarks/results/ workspace.

Scalar checks are a different Pareto problem from bulk batches. On the same FireHOL corpus, the compact D16 snapshot is the scalar winner despite D24's higher batch throughput. Current pinned runs place ip in compact at roughly 70-76 ns for dotted-quad strings, 55-62 ns for IPv4 integers, and 52-56 ns for prepacked four-byte addresses (about 13-19 M one-at-a-time checks/s at the Python-visible boundary). The exact result varies with Windows scheduling and cache state; use benchmark_scalar_snapshot.py for local data.

Useful benchmark entry points:

python benchmark_matrix.py
python benchmark_native.py
python benchmark_firehol_compare.py
python benchmark_snapshot.py --kind interval
python benchmark_snapshot.py --kind hybrid
python benchmark_snapshot.py --kind bitmap
python benchmark_scalar_snapshot.py --profiles compact

For the methodology, rejected experiments, and derivation of the snapshot structures, see docs/PERFORMANCE-AUDIT-2026-09-13.md.

Architecture

The repository is split into four layers:

CIDARTHA5.py                 explicit v5 public facade
cidartha.py                  lowercase v5 convenience facade
CIDARTHA4.py                 legacy Python-only v4 reference/fallback
native/cidartha_core.*       mutable IPv4/IPv6 C engine + public C ABI
native/cidartha_snapshot.*   immutable D16 and D24 IPv4 compilers/lookups
native/py_cidartha.c         direct CPython extension bindings
cidartha.py                  public Python profile-selection API

The mutable engine and immutable snapshots deliberately do not share one internal representation. Updates need exact prefix identity and pruning semantics; compiled membership only needs the final union of covered addresses. Keeping those information requirements separate is a major source of both the speed and memory gains.

Logging

CIDARTHA includes built-in logging for operations:

import logging

# Configure CIDARTHA logger
logger = logging.getLogger("CIDARTHA")
logger.setLevel(logging.DEBUG)

# Now batch operations will log progress
firewall.batch_insert(large_cidr_list)
# Output:
# INFO:CIDARTHA:Starting batch insert of 1000 entries.
# INFO:CIDARTHA:Inserted 50/1000 (5.0%)
# INFO:CIDARTHA:Inserted 100/1000 (10.0%)
# ...

Thread Safety

The native mutable engine uses a reader/writer lock. CPython scalar lookups use a GIL-aware fast path when no GIL-releasing native batch writer is active; if a batch writer is active they fall back to the fully locked native read path. Native batch operations release the GIL around C work.

Immutable snapshots have no mutation path after construction and therefore need no per-query synchronization between concurrent readers.

The historical pure-Python fallback has different concurrency characteristics. Prefer create_mutable() with the native extension when concurrent mutation and lookup behavior matters.

Use Cases

• Firewall Rules: Fast IP filtering for network security applications
• Rate Limiting: Check if IPs belong to rate-limited ranges
• GeoIP Filtering: Block or allow traffic from specific network ranges
• Security Scanning: Identify IPs within suspicious ranges
• Network Analysis: Efficiently query IP membership across large datasets
• Access Control: Implement IP-based allowlists/blocklists

Limitations

• Immutable snapshots are currently IPv4-only; use the mutable engine for IPv6.
• Snapshots are read-only after compilation. Rebuild a snapshot to publish rule changes.
• Native snapshots do not yet expose a stable binary on-disk persistence format; the corrected pure-Python engine retains versioned MessagePack persistence.
• Mutable remove() removes an exact CIDR rule rather than arbitrary subsets of another rule.
• CIDARTHA is a boolean membership engine, not a longest-prefix-match routing table or a general interval-enumeration API.

License

MIT License - Copyright (c) 2026 Jackson Cummings

See LICENSE file for details.

Contributing

Contributions are welcome! Please feel free to submit issues or pull requests.

Author

Jackson Cummings - The Lab Corner

---

CIDARTHA - Fast, efficient, and thread-safe IP/CIDR management for Python 🚀