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" );
	}
}

Removing items from a list during iteration

Standard practice is to iterate over the list backwards like so:

for( int i = items.Count - 1; i >= 0; --i )
{
    if( shouldRemove( items[i] ) )
        item.RemoveAt( i );
}

This approach doesn’t use any extra memory which is nice, but it’s
O((n/2)2) run time (assuming RemoveAt() is O(n)) is less so.

A clever approach I found from Abe Pralle that is O(n) is to fill the gaps as you remove and iterate and then finally truncate the list at the end. Another way to think about it is bubbling the items that need removal to the end of the list.

int gap = 0;
for( int i = 0; i < items.Count; ++i )
{
    if( !shouldRemove( items[i] ) )
    {
        items[gap] = items[i];
        ++gap;
    }
}

items.RemoveRange( gap, items.Count - gap );

Pretty cool!