2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – 200_success Jul 15 '17 at 23:47
  • \$\begingroup\$ Could you also explain how the encoding works? \$\endgroup\$ – t3chb0t Jul 16 '17 at 7:21
  • 1
    \$\begingroup\$ +1 to @t3chb0t . Is this something like ZigZag used in protobuf? \$\endgroup\$ – Bogdan Mart Jul 16 '17 at 12:44
  • \$\begingroup\$ I wyoud suggest using stackalloc for initialization of bytes variable. see: docs.microsoft.com/en-us/dotnet/csharp/language-reference/… \$\endgroup\$ – Bogdan Mart Jul 16 '17 at 12:53
  • \$\begingroup\$ Here's another optimization : ask yourself if you really need that VS storing the value as it is :) \$\endgroup\$ – Aybe Jul 16 '17 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.