Encode integer as variable-length big-endian byte-array

Question

I need to write an integer to a byte array such that leading zeros are omitted and the bytes are written in big endian order.

Example:

int    original = 0x00123456;

byte[] encoded  = Encode(original);  //  == new byte[] { 0x12, 0x34, 0x56 };

int    decoded  = Decode(encoded);   //  == 0x123456

My Decode method:

private static int Decode(byte[] buffer, int index, int length)
{
    int result = 0;
    while (length > 0)
    {
        result = (result << 8) | buffer[index];
        index++;
        length--;
    }
    return result;
}

I'm struggling to come up with an Encode method that doesn't require a temporary buffer or reverses the bytes after writing them in little endian order. Can anyone help?

private static int Encode(int value, byte[] buffer, int index)
{

}

Answer 1

private static int Encode(int value, byte[] buffer, int index)
{
    int length = 0;
    int valueCopy = value;
    while (valueCopy != 0)
    {
        valueCopy >>= 8;
        length++;
    }
    for (int i = 0; i < length; i++)
    {
        buffer[index + length - i - 1] = (byte)value;
        value >>= 8;
    }
    return length;
}

Answer 2

Note that you are saving the value to a variable Length byte array. If you save these byteArray, you need save also the length.

You can see the protected Functions Write7BitEncodedInt from BinaryWriter and Read7BitEncodedInt from BinaryReader.

These functions save storage on disk for positive numbers. A number 0-128 needs only one byte.

Microsoft uses these functions to store/retrieve the String length prefix when save to Stream.

To use these Functions, you can create own Class derived from BinaryReader / BinaryWriter.

Answer 3

As per OP's request, here is a version without loops for a 32-bit number:

private static int Encode(int value, byte[] buffer, int index)
{
    byte temp;
    bool leading = true;

    temp = (value >> 24) & 0xFF;
    if (temp > 0) {
      buffer[index++] = temp;
      leading = false;
    }

    temp = (value >> 16) & 0xFF;
    if (temp > 0 || leading == false) {
      buffer[index++] = temp;
      leading = false;
    }

    temp = (value >> 8) & 0xFF;
    if (temp > 0 || leading == false) {
      buffer[index++] = temp;
      leading = false;
    }

    temp = value & 0xFF;
    buffer[index++] = temp;

    return index;
}

Version using a loop for 32-bit numbers:

private static int Encode(int value, byte[] buffer, int index)
{
    int length = 0;

    for (int i = 3; i >= 0; i++) {
      byte temp = (byte)(value >> (8 * i));
      if (temp > 0 || length > 0) {
        buffer[index++] = temp;
        length++;
      }
    }

    return length;
}

Note that this version doesn't write anything if the input is just 0.