Расчет CRC - бит за бит - C++
Мне нужно создать программу, которая вычисляет CRC из файла. Это нужно делать по крупицам.
Как я хотел бы прочитать файл:
unsigned char byte;
ifstream file;
bool result;
int number;
file.open("test.txt", ios::binary);
while(true)
{
byte = file.get();
number = (int)byte;
result = file.good();
if (!result)
break;
}
Однако я не умею читать по крупицам.
Мой делитель CRC (называемый «полиномом») равен 0x04C11DB7, и мне нужно импортировать 1 новый бит из файла каждый раз, когда я вычисляю свой буфер.
Моя идея состоит в том, чтобы добавить первые 4 байта в переменную (скажем, «1234» это будет 0x31323334), а затем удалить последний бит (переместив бит числа 1 влево), но я не знаю, как добавить новый бит из следующего символа.
Учитывая ваше редактирование, я думаю, что вы спрашиваете, как перемещать 4-байтовое «окно» в потоке данных по одному биту за раз. Это твой вопрос?
Вы не можете читать понемногу. Прочтите по одному байту (или больше), затем побитно обработайте эти байты.
Каждый раз, когда я вычисляю буфер, мне нужно удалить последний бит и добавить новый к следующему символу. Для "A", который равен 0x41 = 0100 0001, мне нужно сначала прочитать 0, затем 1, затем 0, затем 0, затем 0, затем и так далее для каждого отдельного символа.
Этот связанный пример довольно жесток. Большинство CRC выполняется на уровне байтов или выше. Чтобы получить то, что вы хотите, вам нужно будет немного замаскировать байты. например: val &0x80, затем val &0x40, а затем val &0x20 и т. д., проходя по проверяемому объекту по одному фрагменту за раз.
Почему бы вам просто не использовать повысить crc?
Моя задача - реализовать таким образом CRC. Я не могу использовать ускорение.
то есть process_byte(my_8_bits)
Так что взгляните на реализацию, это открытый исходный код.
Раньше я создавал свои собственные процедуры CRC, поскольку они мне были нужны для работы. Однако вы должны быть ОЧЕНЬ осторожны со сдвигами (особенно с длиной) и переполнениями, чтобы случайно не наткнуться на UB. Тем не менее, это весело и помогает понять CRC.
Ответы 2
Вы имеете в виду что-то в этом роде? Расчет CRC может отличаться, но здесь основное внимание уделяется получению содержимого файла «по битам».
#include <iostream>
#include <fstream>
int main(int argc, char* argv[])
{
unsigned char next;
unsigned long crc = 0;
if (argc < 2)
return -1;
std::fstream fs(argv[1], std::fstream::in);
while (!fs.bad() && !fs.eof())
{
fs >> next;
for (int i = 0; i < 8; i++)
{
crc += next & 1;
next >>= 1;
}
}
std::cout << "CRC " << crc << std::endl;
return 0;
}
Делитель - это не просто полином называется. Это означает, что каждый бит является коэффициентом многочлена (степени 32) и, таким образом, способ вычисления с многочленом значительно отличается от работы с целыми числами. Вы можете сложить (и вычесть, что в данном случае то же самое) два многочлена с помощью простой операции XOR. Умножение / деление на / на X означает сдвиг. Справа или слева зависит от порядка, в котором написаны коэффициенты многочленов. Это важно знать, потому что оба направления (слева направо и справа налево) действительно существуют. В случае 0x04C11DB7 коэффициент при X ^ 0 - это бит 0, а коэффициент при X ^ 31 - это бит 31. Имейте в виду, что популярная реализация CRC IEEE802.3 имеет противоположный порядок битов. Таким образом, просто скопировать реализацию Ethernet CRC не получится.
Это означает, что следующим битом для обработки всегда является бит 31. Следовательно, вы должны проверить наличие 0x80000000. Если бит установлен, выполните XOR для вашего многочлена. Это означает, что вы вычитаете полином из своего рабочего регистра. В любом случае, потом сдвиньте результат влево. Затем бит 0 сдвигается вправо. Замените его следующим битом для обработки бинарной операцией or (| в C++). Вы получаете этот бит таким же образом: если вы читаете побайтно, ваш следующий бит будет 1 или 0, в зависимости от того, установлен ли 0x80 на вашем входе. Затем сместите ввод влево.
Прочтите байт, а затем обработайте каждый бит в байте один за другим.