So you want to serialize some DER?
(Editor’s Note: My day job is at Anthropic.)
This story starts where all good stories start, with ASN.1. ASN.1 is… I guess you’d call it a meta-serialization format? It’s a syntax for describing data abstractly (a notation, you might say), and then there’s a bunch of different actual encodings that you can use to turn data into bytes. There’s only one encoding I choose to acknowledge, which is DER (the Distinguished Encoding Representation, it’s got a monocle and tophat). DER and ASN.1 are often used as synonyms, even though they’re technically not – it’s fine. I maintain a Rust library for doing DER parsing and serialization, rust-asn1 (yes, I’m contributing to the naming confusion).
DER is a type-length-value (TLV) binary format. Which means serialized data is all of the form [type code][length][value] , where value is always length bytes long. (Let’s Encrypt has a great introduction to DER if you’re interested.) The way length is encoded is itself variable length, if length is 8, its encoded as a single [0x08] byte. If length is 100, its encoded two bytes [0x81, 0x64] . If you’re serializing some data, and you’re just filling in your buffer from left to right, this gives you an interesting challenge: either you need to know how long each value is going to be when you start serializing, or you have to do some tricks.
When I started this adventure, rust-asn1 did tricks. Specifically, what it did is that when you went to serialize some value into a TLV, it reserved 1 byte of space for the length in the buffer, and then asked the value to write itself to the buffer. Then it compared the length of the buffer before and after, to see how long the value was. If the length fit in the 1 byte we reserved, we’d write it and be done. If not, we expand our buffer, copy the data to make space for the length , and then write the length in. The basic theory is that most TLVs are short, so this is fine in practice. If you’ve got a lot of larger TLVs, this will incur a whole bunch of extra copying, which is too bad.
So I went to do the obvious optimization: allow the value we’re encoding to tell rust-asn1 how long its value will be, so that rust-asn1 can just write out the length correctly the first time. Not rocket science. I wrote up a benchmark, then a PR ( claude-code did the first draft of both), and admired my handiwork.
And then I started ruminating on how we pre-compute a value’s length. For lots of types its trivial, for an OCTET STRING its just the length of the data in bytes, for a BOOLEAN its always 1. What about INTEGER ? Those are a variable length encoding. (It’s not the same encoding as we use for length , that would be too easy.) Here’s what the original implementation (which predated this optimization work) looked like, its inside of a macro which generates implementations for each integer width, hence the ugliness:
let mut num_bytes = 1 ; let mut v: $t = * self; #[allow(unused_comparisons)] while v > 127 || ( $signed && v < ( - 128 i64 ) as $t ) { num_bytes += 1 ; v = v.checked_shr( 8 ).unwrap_or( 0 ); } num_bytes
Something about this implementation bothered me. There was an intuitive wastefulness to need to loop over the bytes to know how long the integer was. Surely we could do better? I was feeling a bit lazy so I asked Claude for improvements (I also looked at the implementation in another library). After some back and forth with Claude, I landed on:
let num_bytes = if * self == 0 { 1 } else { #[allow(unused_comparisons)] let bits_needed = if $signed && * self < 0 { // For negative numbers, count significant bits // including sign bit < $t > ::BITS - self.leading_ones() + 1 } else { // For positive numbers, count all significant bits < $t > ::BITS - self.leading_zeros() }; let bytes_needed = bits_needed.div_ceil( 8 ); // Check if we need an extra byte for ASN.1 encoding let shift = (bytes_needed - 1 ) * 8 ; let most_significant_byte = ( * self >> shift) as u8 ; #[allow(unused_comparisons)] let needs_extra_byte = if $signed && * self < 0 { false } else { most_significant_byte >= 0x80 }; bytes_needed + needs_extra_byte as u32 };
... continue reading