Vec<u8> is kind of special in that it's considered the de-facto Rust variable-length buffer type. For example, std::io::Read contains a method to read directly into a Vec<u8>: std::io::Read::read_to_end.

Result type is cheap, so you should use it if you can (from what I understand, the overhead is about the same as the cost of passing back an additional boolean return value, and having the caller check it). If the caller is reading from a file, they will be using io::Result all over the place anyway.

Use the error-chain crate to define errors easily.

decode should take a slice (&[u8]) so that it can decode from within any buffer. Vec<u8> can decay automatically to &[u8] depending on context anyway.

The trouble with returning Vec<u8> is that requires a new Vec to be allocated for every u64, which is pretty expensive - and the chances are the caller won't be able to use it directly in that form.

It would be better to use the Write trait which generalizes over a stream of output - as @mbthomas mentioned, Vec<u8> implements this (along with Read) so it's still easy for callers. The only downside is that it can fail with io::Result so you need to propagate that up, even if a write to - say - Vec<u8> can never actually fail.

For example:

use std::io::{self, Write};

pub fn encode<W: Write>(value: u64, out: &mut W) -> io::Result<()> {
...
}

A more common signature for this would be:

pub fn decode(buf: &[u8]) -> Result<(u64, &[u8]), E> {
...
}

ie, successful result returns the value and a slice representing the remaining input.

It would also be possible to use std::io::Cursor, but that's probably overkill here.

The error type E would need to represent at least too-short input (we ran out of input before seeing the high bit set) and overflow (the number overflowed before we saw the high bit).

This is fairly inefficient because buf[*pos] will do an array bounds check for each byte.

I'd do something like:

const MAX: usize = 10;
struct Bad;
pub fn decode(input: &[u8]) -> Result<(u64, &[u8]), Bad> {
    let mut res = 0;
    let buf = &input[..cmp::min(MAX, input.len())];
    for (idx, x) in buf.iter().enumerate() {
        res |= ((x & 127) as u64) << (idx * 7);
        if x & 128 == 0 {
            return Ok((res, &input[idx+1..]));
        }
    }
    Err(Bad)
}

where MAX is the max possible encoding length of u64. This doesn't distinguish the short input from overflow.

(There's probably something fancier using more combinators, but this will be fine.)

I would use quickcheck to generate these kinds of round-trip test cases (perhaps in addition to the hand-picked ones).

Agreed.

This is looking pretty unpleasant. I was thinking more along the lines of having a helper function to implement this for u64, and then just manually implement it for each type:

pub fn encode_u64<W: Write>(v: u64, out: &mut W) -> Result<()> {
...
}

impl VLQEncode for u64 {
    fn write_vlq(&self, writer: &mut W) -> Result<()> {
        encode_u64(*self, writer)
    }
}

impl VLQEncode for u32 {
    fn write_vlq(&self, writer: &mut W) -> Result<()> {
        encode_u64(*self as u64, writer)
    }
}

//...

It's a bit cut'n'paste, but I think it's cleaner overall (and it would be a simple macro). It also makes implementing zigzag versions for i64/i32/... much more straightforward.

Also, since all the interesting types for this are Copy, you can make the trait take self (rather than &self) as it would be cleaner to just pass in values by value than reference. If you later want to implement it for a complex type, then you can implement impl<'a> VLQEncode for &'a ComplexType later on.

Having an iterator of indexes like this is pretty much an antipattern in Rust. It's possible the compiler could work out that the range is bounded and eliminate the array bounds check below, but if it doesn't it makes this pretty inefficient.

nit: I think this is called zig-zag.

I don't think this works for the most negative integer values. e.g. for i8, -128 is encoded as 255u8. (255u8 >> 1) + 1 is 128, which will cause overflow (and panic in debug) if you try to convert it to i8 and then negate it.

You can use:

((n >> 1) as $T) ^ -((n & 1) as $T)

which also has the advantage of working for both positive and negative numbers, so it doesn't need the if block.

I'd like to see tests for limits (in particular i{8,16,32,64}::min_value(), after my comments above).