# Micro-optimize variable byte encoding/decoding

Disclaimer: This question was originally asked on Stack Overflow but the community advised to post it here.

I have written routines to encode and decode signed 32-bit-integers into variable byte code:

public class VariableByteCoder
{
public static byte[] Encode(int n)
{
if (n >= 0 && n <= 63) return new byte[] { (byte)(0b01000000 + n) };
if (n < 0 && n >= -63) return new byte[] { (byte)(0b00000000 - n) };
if (n == -2147483648) return new byte[] { 0b10001000, 0b10000000, 0b10000000, 0b10000000, 0b00000000 };

bool isPositive = n >= 0;
if (n < 0) n = -n;
byte[] bytes = new byte[5];
int shift = n;
bool last = true;
int i = 4;
while (shift > 63)
{
byte b = (byte)(shift & 0b01111111);
if (last) last = false; else b |= 0b10000000;
bytes[i] = b;
shift = shift >> 7;
i--;
}
byte head;
head = (byte)((isPositive ? 0b11000000 : 0b10000000) + shift);
bytes[i] = head;
byte[] result = new byte[5 - i];
for (int j = i; j < 5; j++) result[j - i] = bytes[j];
return result;
}

public static int Decode(byte[] bytes)
{
if (bytes.Length == 5 && bytes[0] == 0b10001000 && bytes[1] == 0b10000000 && bytes[2] == 0b10000000 && bytes[3] == 0b10000000 && bytes[4] == 0b00000000) return -2147483648;
int n = 0;
for (int i = bytes.Length - 1; i > 0; i--)
{
n |= ((bytes[i] & 0b01111111) << 7 * (bytes.Length - i - 1));
}
n |= ((bytes[0] & 0b00111111) << 7 * (bytes.Length - 1));
if ((bytes[0] & 0b01000000) == 0) n = -n;
return n;
}
}


On my machine encoding and decoding the entire integer range takes 236 seconds, measured using the following code:

Stopwatch sw = new Stopwatch();
sw.Start();
for (int i = -2147483648; i < 2147483647; i++)
{
byte[] compressed = VariableByteCoder.Encode(i);
int decompressed = VariableByteCoder.Decode(compressed);
if (decompressed != i) throw new Exception(string.Format("a problem occured during encoding or decoding of integer-value {0}, decoding gave {1}", i, decompressed));
}
sw.Stop();
Console.WriteLine(string.Format("Total duration: {0}ms", sw.ElapsedMilliseconds));


I already tuned it a little but from now on it's black magic to me.

Can anyone help me optimizing the code for more speed?

• Welcome to Code Review, and thanks for declaring your cross-post. Could you give us more context about how this code is going to be called, and what it is used for? – 200_success Jul 15 '17 at 23:47
• Could you also explain how the encoding works? – t3chb0t Jul 16 '17 at 7:21
• +1 to @t3chb0t . Is this something like ZigZag used in protobuf? – Bogdan Mart Jul 16 '17 at 12:44
• I wyoud suggest using stackalloc for initialization of bytes variable. see: docs.microsoft.com/en-us/dotnet/csharp/language-reference/… – Bogdan Mart Jul 16 '17 at 12:53
• Here's another optimization : ask yourself if you really need that VS storing the value as it is :) – Aybe Jul 16 '17 at 22:47