External Publication
Visit Post

`BitSlice` or a sound way to implement one

Rust Internals [Unofficial] April 23, 2026
Source

The basic idea is this: if &[u8] is a fat pointer to a byte slice which consists of two parts: a *const u8 pointer and what's effectively a usize containing a length in bytes, could you have an equivalent fat pointer type which stores the length in bits instead, where the number of bits may be up to 7 fewer than the equivalently sized byte slice, and also support this as a reference-to-reference conversion such that the type itself is used as &BitSlice as opposed to BitSlice<'a> such that it works with Borrow/ToOwned/Cow patterns?

The goal would be to get the same &[u8] back out but also get those 3 additional length bits which give you the sub-byte bit-level length granularity, all in a reference type that fits in the same space as any other fat pointer, where we can recompute the original byte-level length of the byte slice as div_ceil(8).

This matters to me in particular because ASN.1 BIT STRING just so happens to be one of the most core fundamental data structures for cryptography formats, as it's the type used to represent public keys in X.509 SubjectPublicKeyInfo (a.k.a. SPKI), which in addition to its use in X.509 is used in other cryptographic formats like PKCS#8 for private key storage (see OneAsymmetricKey). It would be really nice to be able to implement a zero copy type for representing BIT STRING which itself is a fat pointer that can be Cow-d.

Such a type exists today in third party libraries: bitvec::slice::BitSlice. I have also attempted to implement the same pattern: a trick which involves constructing [Zst] using slice::from_raw_parts which carries the original pointer and lifetime for the &[u8] but carries the bit length rather than the byte length as the length component.

It seems this approach has been somewhat problematic from a soundness perspective though, with code being accidentally deleted in release builds as of LLVM 16 and a suggested workaround being unsound under stacked borrows (but accepted by -Zmiri-tree-borrows).

With code that's considered unsound under any model of the language making a particular approach seem scary for use in cryptographic applications (and particularly ones dealing with serialization formats for untrusted data at the network's edge), I had an idea that would make me a lot more confident: what if the BitSlice type were simply built into the language? Then its implementation just needs to be as sound as whatever the current model of soundness du jour happens to be, can leverage internal compiler magic, etc.

Alternatively, if there were unsafe APIs that could take apart a fat pointer and put it back together while preserving provenance, but allow the caller to carry along some additional data in the length field, kind of like the addr/with_addr/map_addr APIs for tagged pointers work, that could also do the trick.

Discussion in the ATmosphere

Loading comments...