c# - 整数的可变长度编码

Question

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

---

“实际意图是将可变长度编码整数(字节)附加到文件头。”

例如:"Content-Length"- Http Header

这是否可以通过对以下逻辑进行一些更改来实现。

---

我已经写了一些代码来做到这一点....

Answer 1

我使用过的一种方法，可以使较小的值使用较少的字节，即对 7 位数据 + 1 位开销 pr 进行编码。字节。

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

编码的工作方式是这样的:

• 获取你的值的最低 7 位并将它们存储在一个字节中，这就是你要输出的内容
• 将值向右移动 7 位，去掉刚刚抓取的那 7 位
• 如果该值不为零(即在你从它移开 7 位之后)，在输出之前设置你要输出的字节的高位
• 输出字节
• 如果该值不为零(即导致设置高位的相同检查)，返回并从头开始重复这些步骤

解码:

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

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

As you can see, the encoded value might occupy one additional byte that is just half-way used, due to the overhead of the control bits. If you expand this to a 64-bit value, the additional byte will be completely used, so there will still only be one byte of extra overhead.

Note: Since the encoding stores values one byte at a time, always in the same order, big- or little-endian systems will not change the layout of this. The least significant byte is always stored first, etc.

Ranges and their encoded size:

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

Here's C# implementations for both:

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

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

    /// <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;
    }
}