Skip to content

Instantly share code, notes, and snippets.

@Plecra
Created June 1, 2020 20:48
Show Gist options
  • Save Plecra/9f9da519c484cfb0a829e12464c78d77 to your computer and use it in GitHub Desktop.
Save Plecra/9f9da519c484cfb0a829e12464c78d77 to your computer and use it in GitHub Desktop.
LEB128 VarInt decoding
const HIGH_BIT: u8 = 0b10000000;
fn hi_bit_set(byte: u8) -> bool {
byte & HIGH_BIT != 0
}
pub fn naive(buf: &mut &[u8]) -> Result<u64, ()> {
let mut value = 0;
let mut iter = buf.iter();
for (count, &byte) in (&mut iter).enumerate().take(10) {
value += u64::from(byte & !HIGH_BIT) << (count * 7);
if !hi_bit_set(byte) {
*buf = iter.as_slice();
return Ok(value);
}
}
Err(())
}
@Plecra
Copy link
Author

Plecra commented Jun 1, 2020

Typical implementations will optimize the algorithm, generally making up 40% in performance. Common tricks check the first byte for the HIGH_BIT, and elide bounds checks by checking the length up front

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment