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

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

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

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

Источник

6 ответов

Решение

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

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

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

Таким образом, целое число 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, чтобы обеспечить работающую реализацию. Но это не очень сложно сделать, основываясь на этом описании.

Источник

По сути, идея 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-м байтом.

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

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

Источник

Мне также пришлось изучить этот 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);
}
Источник 
/*
 * 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;
}
Источник

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

Источник

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

Источник
Другие вопросы по тегам