djbsort

A Rust port of the Zig implementation of DJB's constant-time sorting network (sorting.cr.yp.to).

The sorting network is data-oblivious: the sequence of comparisons and swaps depends only on the array length, never on the values. This makes it immune to timing side-channels, which matters when sorting sensitive data in cryptographic contexts.

Usage

The crate provides three functions.

sort is the fast path for numeric primitives. It uses SIMD vectorization (NEON on aarch64, AVX2 on x86_64) with a scalar fallback:

use djbsort::{sort, Order};

let mut data = [42i32, -7, 13, 0, -99];
sort(&mut data, Order::Asc);
assert_eq!(data, [-99, -7, 0, 13, 42]);

All Rust numeric types are supported: i8 through i128, u8 through u128, isize, usize, f32, and f64.

sort_by handles arbitrary types with a user-supplied comparator. It uses the same network topology but swaps with mem::swap, which is not constant-time:

use djbsort::sort_by;

#[derive(Copy, Clone)]
struct Point { x: i32, y: i32 }

let mut points = [Point { x: 3, y: 1 }, Point { x: 1, y: 2 }];
sort_by(&mut points, |a, b| a.x < b.x);
assert_eq!(points[0].x, 1);

sort_by_ct is the constant-time generic path. It swaps bytes via XOR with an assembly barrier to prevent the compiler from introducing branches. The type must implement CtSwappable (all bit patterns valid, no padding), and the result is timing-safe as long as your comparator is too:

use djbsort::sort_by_ct;

let mut keys = [5u64, 3, 8, 1, 4];
sort_by_ct(&mut keys, |a, b| a < b);
assert_eq!(keys, [1, 3, 4, 5, 8]);

Float ordering

Floats are sorted using a total order: -NaN < -inf < ... < -0.0 < +0.0 < ... < +inf < +NaN. Internally they are bitcast to integers via the "useint" technique, sorted as integers, and bitcast back. This means floats sort at the same speed as same-width integers.

Side-channel mitigations

On most architectures, min/max instructions are already constant-time (cmov on x86, csel on aarch64), so the default build is fine. On other targets, enable the side-channel-mitigations feature to force XOR-masked compare-and-swap:

[dependencies]
djbsort = { version = "0.1", features = ["side-channel-mitigations"] }