7BitInts

While working on Bastion, I noticed that the BinaryReader and BinaryWriter classes have protected member functions Read7BitEncodedInt and Write7BitEncodedInt respectively and it got me wondering what the heck is a 7BitEncodedInt?

Turns out, it’s a super clever way of variable length encoding an integer.  Google calls them varints and it’s a critical component of ProtocolBuffers.  Finding an implementation back in 2009 was unexpectedly difficult and .NET made them protected members for some reason, so we ended up rolling our own public extension methods.

public static class SystemIOExtensions
{
    public static void Write7BitEncodedInt( this BinaryWriter writer, int value )
    {
        writer.Write7BitEncodedInt( (uint)value );
    }

    public static void Write7BitEncodedInt( this BinaryWriter writer, uint value )
    {
		uint v = value;
		while( v >= 0x80 )
		{
			byte b = (byte)( v | 0x80);
			writer.Write( b );
			v = v >> 7;
		}
		writer.Write( (byte)v );
    }

	public static int Read7BitEncodedInt( this BinaryReader reader )
	{
		int v = 0;
		int shift = 0;

		while( shift < (5 * 7) )
		{
			byte b = reader.ReadByte();
			v |= ((b & 0x7F) << shift);
			shift += 7;
			if( ( b & 0x80 ) == 0 )
				return v;
		}

		throw new FormatException( "Stream corrupted, unable to read 7bit int" );
	}
}