High-Performance Longest Prefix Match Library

A high-performance C library for Longest Prefix Match (LPM) lookups, supporting both a multi-bit trie of 8-bit stride for IPv4 and a wide multi-level 16-bit stride for IPv6, featuring runtime dynamic SIMD dispatching (SSE2, SSE4.2, AVX, AVX2, AVX512F) for optimal performance and throughput on any CPU architecture.

Features

• High Performance: Multi-bit trie with 8-bit stride reduces trie depth and improves cache.
• Dual Stack Support: Native support for both IPv4 (32-bit) and IPv6 (128-bit) addresses.
• SIMD Optimizations: Dynamic dispatching via libdynemit. (SSE2, SSE4.2, AVX, AVX2, AVX512F)
• Batch Processing: Vectorized batch lookup for processing multiple addresses simultaneously.
• Branchless Design: Optimized lookup paths with minimal branch mispredictions.
• Cache-Friendly: Aligned data structures and prefetching for optimal cache utilization.
• C23 Standard: Written in modern C with best practices.

Performance

_{IPv4 and IPv6 single lookup comparison among different CPU architectures}

_{Algorithm rankings showing mean throughput at small prefixes sets}

For detailed benchmarks and methodology, see docs/BENCHMARKS.md.
Browse all benchmark charts in docs/images/.

Install from Package Repository

Ubuntu/Debian

curl -fsSL https://archive.made4it.com.br/apt/gpg.key | sudo gpg --dearmor -o /usr/share/keyrings/liblpm.gpg
echo "deb [signed-by=/usr/share/keyrings/liblpm.gpg] https://archive.made4it.com.br/apt $(lsb_release -cs) main" | sudo tee /etc/apt/sources.list.d/liblpm.list
sudo apt update && sudo apt install liblpm liblpm-dev

Fedora

sudo curl -fsSL https://archive.made4it.com.br/rpm/liblpm-fedora.repo -o /etc/yum.repos.d/liblpm-fedora.repo
sudo dnf install liblpm liblpm-devel

RHEL/Rocky/AlmaLinux

sudo curl -fsSL https://archive.made4it.com.br/rpm/liblpm-fedora.repo -o /etc/yum.repos.d/liblpm-el.repo
sudo dnf install liblpm liblpm-devel

Or Build & Install from Source

Requirements: GCC 13+ or Clang 16+ (for C23 support)

Ubuntu/Debian

# Install build dependencies
apt install build-essential cmake libc6-dev

# Clone with submodules
git clone --recursive https://github.com/MuriloChianfa/liblpm.git
cd liblpm

# Or if already cloned, initialize submodules
git submodule update --init --recursive

# Build
mkdir build && cd build
cmake ..
make -j$(nproc)
sudo make install

Fedora

# Install build dependencies
dnf install gcc gcc-c++ make cmake glibc-devel

# Clone with submodules
git clone --recursive https://github.com/MuriloChianfa/liblpm.git
cd liblpm

# Or if already cloned, initialize submodules
git submodule update --init --recursive

# Build
mkdir build && cd build
cmake ..
make -j$(nproc)
sudo make install

CentOS/RHEL/Rocky Linux

# Install build dependencies
yum install gcc gcc-c++ make cmake3 glibc-devel

# Clone with submodules
git clone --recursive https://github.com/MuriloChianfa/liblpm.git
cd liblpm

# Or if already cloned, initialize submodules
git submodule update --init --recursive

# Build
mkdir build && cd build
cmake ..
make -j$(nproc)
sudo make install

Usage

Basic Example

#include <lpm.h>
int main() {
    lpm_trie_t *trie = lpm_create(LPM_IPV4_MAX_DEPTH);
    
    // 192.168.0.0/16 -> next hop 100
    uint8_t prefix[] = {192, 168, 0, 0};
    lpm_add(trie, prefix, 16, 100);

    uint8_t addr[] = {192, 168, 1, 1};
    uint32_t next_hop = lpm_lookup(trie, addr);
    
    lpm_destroy(trie);
    return 0;
}

API Reference

Core Functions

• lpm_create(max_depth) - Create LPM trie (32 for IPv4, 128 for IPv6)
• lpm_add(trie, prefix, prefix_len, next_hop) - Add prefix to trie
• lpm_delete(trie, prefix, prefix_len) - Remove prefix from trie
• lpm_destroy(trie) - Free all resources

Lookup Functions

• lpm_lookup(trie, addr) - Single address lookup
• lpm_lookup_ipv4(trie, addr) - IPv4-specific lookup
• lpm_lookup_ipv6(trie, addr) - IPv6-specific lookup

Tests and Fuzzing

The library includes some fuzzing tests to ensure robustness and catch edge cases. The fuzzing tests cover memory safety, API robustness, edge cases, and performance under stress.

cd build
ctest --verbose            # Run test suite
./benchmarks/bench_lookup  # Run benchmarks

./tests/fuzz_setup.sh      # Setup fuzzing environment
./build_afl.sh             # Build with AFL instrumentation
./run_fuzz.sh              # Run AFL fuzzing

For detailed information about the fuzzing tests, coverage areas,
and advanced fuzzing techniques, see tests/FUZZING.md.

Containerized Development

Docker Containers

For a reproducible development environment with the latest toolchain (GCC 15.2, Clang 21.1, CMake 4.2), you can use Docker containers:

Quick Start with Docker

# Build all containers
./scripts/docker-build.sh all

# Interactive development
docker run -it --rm -v "$PWD:/workspace" liblpm-dev

# Run tests
docker run --rm liblpm-test

# Run fuzzing
docker run --rm --cpus=4 liblpm-fuzz

Available Containers

• liblpm-dev: Complete development environment
• liblpm-test: Automated testing with valgrind and cppcheck
• liblpm-fuzz: AFL++ fuzzing for security testing
• liblpm-cpp: C++ bindings development and testing
• liblpm-go: Go bindings development and testing
• liblpm-perl: Perl XS bindings development and testing
• liblpm-php: PHP bindings development and testing
• liblpm-python: Python bindings development and testing
• liblpm-benchmark: DPDK rte_lpm performance comparison

For complete documentation, see docs/DOCKER.md.

Verifying Binary Signatures

liblpm binaries are cryptographically signed with GPG for authenticity verification. To verify a downloaded binary:

1. Import the Public Key

Import the maintainer's public key directly from the keyserver using the key fingerprint:

gpg --keyserver keys.openpgp.org --recv-keys 3E1A1F401A1C47BC77D1705612D0D82387FC53B0

Alternative options

Using the shorter key ID:

gpg --keyserver keys.openpgp.org --recv-keys 12D0D82387FC53B0

Alternative keyserver (if keys.openpgp.org is unavailable):

gpg --keyserver hkp://keyserver.ubuntu.com --recv-keys 3E1A1F401A1C47BC77D1705612D0D82387FC53B0

You should see output confirming the key was imported:

gpg: key 12D0D82387FC53B0: public key "MuriloChianfa <murilo.chianfa@outlook.com>" imported
gpg: Total number processed: 1
gpg:               imported: 1

2. Verify the Signature

Assuming you have downloaded both the binary (liblpm.so or liblpm.a) and its signature file (liblpm.so.asc or liblpm.a.asc):

gpg --verify liblpm.so.asc liblpm.so

If the signature is valid, you should see:

gpg: Signature made [date and time]
gpg:                using EDDSA key 3E1A1F401A1C47BC77D1705612D0D82387FC53B0
gpg: Good signature from "MuriloChianfa <murilo.chianfa@outlook.com>"

If you see "BAD signature", do not use the binary - it may have been tampered with or corrupted.

Documentation

Manual Pages

After installation, comprehensive man pages are available:

man liblpm          # Library overview and getting started
man lpm_create      # Trie creation functions
man lpm_lookup      # Lookup functions (single and batch)
man lpm_add         # Adding prefixes
man lpm_delete      # Removing prefixes
man lpm_destroy     # Cleanup and utilities
man lpm_algorithms  # Algorithm-specific APIs

Additional Documentation

• Byte Order and Data Format - Endianness, IP address storage, and integration guide
• C# API Reference - C# P/Invoke bindings documentation
• C++ API Reference - C++ wrapper documentation
• Go API Reference - Go bindings documentation
• Java API Reference - Java JNI bindings documentation
• Lua API Reference - Lua C module documentation
• Perl API Reference - Perl XS bindings documentation
• PHP API Reference - PHP extension documentation
• Python API Reference - Python bindings documentation

Security

If you discover any security vulnerabilities, please DO NOT use or open a public issue or discussion. Instead, read and refer to our Security Policy for instructions on how to report security issues responsibly.

License

This project is licensed under the Boost Software License 1.0, see the LICENSE file for details.

Credits

• Murilo Chianfa
• All Contributors