Кодирование целого числа в 7-битном формате C # BinaryReader.ReadString

Question

C# BinaryReader имеет функцию, которая в соответствии с MSDN читает целое число, закодированное как «семибитовое целое число», а затем читает строку с длиной этого целого числа.

Есть ли четкая документация для семибитового целочисленного формата (у меня есть четкое понимание того, что MSB или LSB отмечает, есть ли еще байты для чтения, а остальные биты - данные, но я буду рад за что-то более точное).

Еще лучше, есть ли C реализация для чтения и записи чисел в этом формате?

Answer 1

Что ж, документация для BinaryReader.Read7BitEncodedInt уже говорит, что она ожидает, что значение будет записано с помощью BinaryWriter.Write7BitEncodedInt , а документация этого метода подробно описывает формат:

Целое число параметра значения записывается по семь бит за раз, начиная с семи младших битов. Старший бит байта указывает, есть ли еще байты для записи после этого.

Если значение помещается в семь битов, оно занимает только один байт. Если значение не помещается в семь битов, старший бит устанавливается на первый байт и записывается. Затем значение сдвигается на семь битов и записывается следующий байт. Этот процесс повторяется до тех пор, пока не будет записано все целое число.

Таким образом, целое число 1259551277 в двоичном коде 1001011000100110011101000101101 будет преобразовано в этот 7-битный формат следующим образом:

Remaining integer                 encoded bytes
1001011000100110011101000101101
100101100010011001110100          00101101
10010110001001100                 10101101 01110100
1001011000                        10101101 11110100 01001100
100                               10101101 11110100 11001100 01011000
0                                 10101101 11110100 11001100 11011000 00000100

Однако я не настолько уверен в своих навыках C, чтобы обеспечить работающую реализацию. Но это не очень сложно сделать, основываясь на этом описании.

Answer 2

По сути, идея 7-битного кодированного Int32 состоит в том, чтобы уменьшить количество байтов, необходимых для небольших значений. Это работает так:

1. Берутся первые 7 младших значащих битов исходного значения.
2. Если это значение превышает то, что может поместиться в эти 7 битов, 8-й бит устанавливается в 1, указывая, что должен быть прочитан другой байт. В противном случае этот бит равен 0, и чтение заканчивается здесь.
3. Следующий байт считывается, его значение сдвигается влево на 7 битов и устанавливается на ранее прочитанное значение, чтобы объединить их вместе. Опять же, 8-й бит этого байта указывает, должен ли считываться другой байт (сдвигая значение чтения еще 7 раз).
4. Это продолжается до тех пор, пока не будет прочитано максимум 5 байтов (потому что даже Int32.MaxValue не потребует более 5 байтов, когда из каждого байта украден только 1 бит). Если старший бит 5-го байта все еще установлен, вы прочитали что-то, что не является 7-битным кодированным Int32.

Обратите внимание, что поскольку он записывается побайтово, для этих значений порядковый номер не имеет значения вообще. Следующее количество байтов требуется для данного диапазона значений:

• 1 байт: от 0 до 127
• 2 байта: от 128 до 16 383
• 3 байта: от 16 384 до 2 097 151
• 4 байта: от 2 097 152 до 268 435 455
• 5 байтов: от 268 435 456 до 2 147 483 647 (Int32.MaxValue) и от 2 147 483 648 (Int32.MinValue) до -1

Как видите, реализация довольно тупая и всегда требует 5 байтов для отрицательных значений, поскольку знаковый бит - это 32-й бит исходного значения, всегда заканчивающийся 5-м байтом.

Таким образом, я не рекомендую его для отрицательных значений или значений больше ~ 250 000 000. Я видел только то, что он использовался внутренне для префикса длины строки строк .NET (тех, которые вы можете читать / писать с помощью BinaryReader.ReadString и BinaryReader.WriteString), описывая количество символов, за которыми следует строка, только с положительными значениями .

Хотя вы можете искать оригинальный источник .NET , я использую разные реализации в моей библиотеке BinaryData .

Answer 3

/*
 * Parameters:  plOutput[out] - The decoded integer
 *              pbyInput[in]  - Buffer containing encoded integer
 * Returns:     Number of bytes used to encode the integer
 */
int SevenBitEncodingToInteger(int *plOutput, char *pbyInput)
{
    int lSize = 0;
    int lTemp = 0;
    while(true)
    {
        lTemp += pbyInput[lSize] & 0x7F;
        if(pbyInput[lSize++] > 127)
            lTemp <<= 7;
        else
            break;
    }
    *plOutput = lTemp;
    return lSize;
}

Answer 4

Мне также пришлось изучить этот 7-битный формат. В одном из моих проектов я упаковываю некоторые данные в файлы, используя BinaryWriter в C #, а затем снова распаковываю их с помощью BinaryReader, который прекрасно работает.

Позже мне понадобилось реализовать ридер для упакованных файлов этого проекта и для Java. У Java есть класс с именем DataInputStream (в пакете java.io), который имеет несколько похожих методов. К сожалению, интерпретация данных в DataInputStream сильно отличается от интерпретации в C #.

Чтобы решить мою проблему, я сам портировал BinaryReader C # на Java, написав класс, расширяющий java.io.DataInputStream. Вот метод, который я написал, который делает то же самое, что и B # BinaryReader.readString ():

public String csReadString() throws IOException {
    int stringLength = 0;
    boolean stringLengthParsed = false;
    int step = 0;
    while(!stringLengthParsed) {
        byte part = csReadByte();
        stringLengthParsed = (((int)part >> 7) == 0);
        int partCutter = part & 127;
        part = (byte)partCutter;
        int toAdd = (int)part << (step*7);
        stringLength += toAdd;
        step++;
    }
    char[] chars = new char[stringLength];
    for(int i = 0; i < stringLength; i++) {
        chars[i] = csReadChar();
    }
    return new String(chars);
}

Answer 5

Формат описан здесь: http://msdn.microsoft.com/en-us/library/system.io.binarywriter.write7bitencodedint.aspx

Answer 6

Метод Write7BitEncodedInt содержит описание: младшие 7 битов каждого байта кодируют следующие 7 битов числа. Наибольший бит устанавливается, когда следующий байт следующий.