djbsort 0.1.0

Constant-time sorting network (djbsort) with SIMD optimization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# djbsort

A Rust port of the [Zig implementation](https://github.com/jedisct1/zig-djbsort) of DJB's constant-time sorting network ([sorting.cr.yp.to](https://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:

```rust
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:

```rust
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:

```rust
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:

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