整数的可变长度编码

Question

什么是在C#中对无符号整数值进行可变长度编码的最佳方法？

---

"实际的意图是将一个可变长度编码的整数(字节)附加到文件头."

例如:"Content-Length" - Http Header

这可以通过以下逻辑中的一些变化来实现.

---

我写了一些代码,这样做....

Answer 1

我使用的一种方法,它使较小的值使用较少的字节,是编码7位数据+ 1位开销pr.字节.

编码仅适用于从零开始的正值,但如果需要也可以修改以处理负值.

编码的工作方式如下:

• 抓取值的最低7位并将它们存储在一个字节中,这就是您要输出的内容
• 将值向右移7位,摆脱刚刚抓取的7位
• 如果该值非零(即,在您向其移开7位之后),请在输出之前设置要输出的字节的高位
• 输出字节
• 如果该值非零(即,导致设置高位的相同检查),请返回并从头开始重复这些步骤

要解码:

• 从位0开始
• 从文件中读取一个字节
• 存储是否设置了高位,并将其屏蔽掉
• 或者在字节的其余部分将OR写入您的最终值,位于您所在的位位置
• 如果设置了高位,则将位位置增加7,然后重复步骤,跳过第一个位(不要重置位位置)

          39    32 31    24 23    16 15     8 7      0
value:            |DDDDDDDD|CCCCCCCC|BBBBBBBB|AAAAAAAA|
encoded: |0000DDDD|xDDDDCCC|xCCCCCBB|xBBBBBBA|xAAAAAAA| (note, stored in reverse order)

如您所见,由于控制位的开销,编码值可能会占用一个仅使用一半的字节.如果将其扩展为64位值,则将完全使用附加字节,因此仍将只有一个字节的额外开销.

注意:由于编码一次存储一个字节的值,因此总是以相同的顺序存储,大端或小端系统不会更改此布局.始终存储最低有效字节,等等.

范围及其编码大小:

          0 -         127 : 1 byte
        128 -      16.383 : 2 bytes
     16.384 -   2.097.151 : 3 bytes
  2.097.152 - 268.435.455 : 4 bytes
268.435.456 -   max-int32 : 5 bytes

以下是两者的C#实现:

void Main()
{
    using (FileStream stream = new FileStream(@"c:\temp\test.dat", FileMode.Create))
    using (BinaryWriter writer = new BinaryWriter(stream))
        writer.EncodeInt32(123456789);

    using (FileStream stream = new FileStream(@"c:\temp\test.dat", FileMode.Open))
    using (BinaryReader reader = new BinaryReader(stream))
        reader.DecodeInt32().Dump();
}

// Define other methods and classes here

public static class Extensions
{
    /// <summary>
    /// Encodes the specified <see cref="Int32"/> value with a variable number of
    /// bytes, and writes the encoded bytes to the specified writer.
    /// </summary>
    /// <param name="writer">
    /// The <see cref="BinaryWriter"/> to write the encoded value to.
    /// </param>
    /// <param name="value">
    /// The <see cref="Int32"/> value to encode and write to the <paramref name="writer"/>.
    /// </param>
    /// <exception cref="ArgumentNullException">
    /// <para><paramref name="writer"/> is <c>null</c>.</para>
    /// </exception>
    /// <exception cref="ArgumentOutOfRangeException">
    /// <para><paramref name="value"/> is less than 0.</para>
    /// </exception>
    /// <remarks>
    /// See <see cref="DecodeInt32"/> for how to decode the value back from
    /// a <see cref="BinaryReader"/>.
    /// </remarks>
    public static void EncodeInt32(this BinaryWriter writer, int value)
    {
        if (writer == null)
            throw new ArgumentNullException("writer");
        if (value < 0)
            throw new ArgumentOutOfRangeException("value", value, "value must be 0 or greater");

        bool first = true;
        while (first || value > 0)
        {
            first = false;
            byte lower7bits = (byte)(value & 0x7f);
            value >>= 7;
            if (value > 0)
                lower7bits |= 128;
            writer.Write(lower7bits);
        }
    }

    /// <summary>
    /// Decodes a <see cref="Int32"/> value from a variable number of
    /// bytes, originally encoded with <see cref="EncodeInt32"/> from the specified reader.
    /// </summary>
    /// <param name="reader">
    /// The <see cref="BinaryReader"/> to read the encoded value from.
    /// </param>
    /// <returns>
    /// The decoded <see cref="Int32"/> value.
    /// </returns>
    /// <exception cref="ArgumentNullException">
    /// <para><paramref name="reader"/> is <c>null</c>.</para>
    /// </exception>
    public static int DecodeInt32(this BinaryReader reader)
    {
        if (reader == null)
            throw new ArgumentNullException("reader");

        bool more = true;
        int value = 0;
        int shift = 0;
        while (more)
        {
            byte lower7bits = reader.ReadByte();
            more = (lower7bits & 128) != 0;
            value |= (lower7bits & 0x7f) << shift;
            shift += 7;
        }
        return value;
    }
}

Answer 2

如果小值比大值更常见，您可以使用哥伦布编码。