IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> CRC16, CRC8, подсчет контрольной суммы
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Если подсчитать контрольную сумму одного и того же текстового файла разными способами, разве результат не должен получиться одинаковым? По-моему, должен.
И мне кажется, что самый верный результат у первой проги, там она просчитывает контрольную сумму по формуле C = T%(M+1);
А остальные две проги написаны по алгоритму CRC16 (я взяла их из разных источников) и они тоже дают разный результат! Хотя казалось бы, они идентичны. Например, в текстовом файле записано "This is"
первая прога выдает: 148
вторая: 57134
а третья вообще: -23314
Почему так? blink.gif

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

void main (void)
{
clrscr();
int dlina_stroki;
int i,T,C;
int M=255;
FILE *in;
const n=80;
char stroka[n], p[n];
in=fopen("text.txt","rt");
fgets(stroka,n,in);
fclose(in);
dlina_stroki=strlen(stroka);
T=0;
for (i=0; i<=dlina_stroki; i++)
T=T+stroka[i];
C = T%(M+1);
printf("The control sum = %d",C);
getch();
}


=======================
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
int dlina_stroki,START;

unsigned int crc(unsigned char *buf, unsigned int n)
{
unsigned char i,carry;
int crc16=0xFFFF;
while(n)
{
crc16^=*buf;
for (i=0; i<8; i++)
{
carry=crc16&1;
crc16>>=1;
if (carry)crc16^=0xA001;
}
n--;
buf++;
}
return crc16;
}

void main(void)
{START=0; unsigned int temp;
FILE *in;
const n=1008;
unsigned char stroka[n], p[n];
in=fopen("text.txt","rt");
fgets(stroka,n,in);
fclose(in);
dlina_stroki=strlen(stroka);
clrscr();
temp=crc(stroka,dlina_stroki);
printf("%d",temp);
getch();
}


===============================
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
int dlina_stroki,START;

unsigned int crc(unsigned char *buf, int start, int cnt)
{int i,j;
unsigned int temp, flag;
temp=0xFFFF;
for (i=start; i<cnt; i++)
{ temp=temp^buf[i];
for (j=1; j<=8; j++)
{ flag=temp & 0x0001;
temp=temp>>1;
if (flag)temp=temp^0xA001;
}
}
return(temp);
}


void main(void)
{START=0; unsigned int temp;
FILE *in;
const n=1008;
unsigned char stroka[n], p[n];
in=fopen("text.txt","rt");
fgets(stroka,n,in);
fclose(in);
dlina_stroki=strlen(stroka);
clrscr();
temp=crc(stroka,START,dlina_stroki);
printf("%u",temp);
getch();
}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Первая программа - это не CRC, а простая контрольная сумма по модулю 256.

Вторая программа в общем-то идентична третьей, но в ней с ошибкой реализован сдвиг вправо, точнее, переменная crc должна быть беззнаковой, иначе сдвиг "вытягивает" 15-й бит на место ожидаемых справа нулей. Правда, такого эффекта не будет, если int - 32-битный. Правильный результат - 57134.

Кроме того, эти программы не должны компилироваться:
"const n =1008" эквивалентно "const int n = 1008", т. е. n - это переменная, в которую компилятор не даст присваивать стандартными средствами. Объявление "unsigned char stroka[n]" должно вызывать (вызывало у меня) ошибку компиляции, т. к. n - не константа, а переменная. В Си символические константы (аналогичные нетипизированным константам Паскаля) можно определить только с помощью #define или enum.

На Си это должно выглядеть примерно так:
#include <stdio.h>
#include <string.h>

int checksum(const char *buf, unsigned len)
{
int s = 0;
while (len--) s += *buf++;
return s & 0xFF; { можно заменить на "return s % M" для сумм по другому модулю }
}

unsigned crc16(const char *buf, unsigned len)
{
int i;
unsigned crc = 0xFFFF;
while (len--)
{
crc ^= *buf++;
for (i = 8; i--;)
{
int f = crc & 1;
crc >>= 1;
if (f) crc ^= 0xA001;
}
}
return crc;
}

int main()
{
char buf[4096];
int len;

FILE *f = fopen("text.txt", "rt");
fgets(buf, sizeof(buf), f);
len = strlen(buf);

printf("Checksum = %d\n", checksum(buf, len));
printf("CRC-16 = %u\n", crc16(buf, len));
putchar('\n');

fclose(f);
return 0;
}


Сообщение отредактировано: xds -


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


А чем отличается CRC-16 от CRC-8?
Я нашла такой пример реализации CRC-8

void Update_CRC(char in, char *crc)
{
#define POLYNOMIAL 0x1D // x^8 + x^4 + x^3 + x^2 + 1
*crc = *crc ^ in;
for (unsigned char i=0; i<8; i++)
{
*crc = (*crc & 0x80)? (*crc << 1) ^ POLYNOMIAL : (*crc << 1);
}
}


Но не поняла как он работает. Вроде в процедуре должен быть и перевод в двоичную систему счисления, и деление на полином. А здесь все в две строчки и непонятно, что здесь значит char in.

Цитата
Кроме того, эти программы не должны компилироваться

Я компилировала в Turbo C++ . Рабочие. Только результат бредовый!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Цитата(Тёмный Эльф @ 8.05.2007 3:46) *

А чем отличается CRC-16 от CRC-8?
Степенью многочлена-делителя, и, соответственно, максимальной степенью многочлена-остатка, т. е. длиной контрольной суммы. В CRC-8 КС занимает 1 байт, а в CRC-16 - 2 байта.

Цитата
Вроде в процедуре должен быть и перевод в двоичную систему счисления, и деление на полином. А здесь все в две строчки
Всё уже и так в двоичной системе smile.gif А деление полинома на полином - это сдвиги и XOR (Глава 8, вышеуказанного документа, "Прямая реализация CRC").

Цитата
непонятно, что здесь значит char in.
Эта функция должна вызываться в цикле для каждого символа данных и "накапливать" CRC в переменной, адрес которой передан вторым параметром:

#include <stdio.h>
#include <string.h>
...
int main()
{
int i;
const char *str = "Hello";
unsigned char crc = 0;

for (i = 0; i < strlen(str); i++)
Update_CRC(str[i], &crc);

printf("CRC-8 = %u\n", crc);
return 0;
}


Цитата
Я компилировала в Turbo C++ . Рабочие. Только результат бредовый!

Компилируется только в режиме С++ (хотя программа больше похожа на C). Если это C++, то что за "fgets" и "printf", и где же "f.getline()" и "cout"? smile.gif


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Спасибо, xds, ты все доступно объяснил. smile.gif Единственное, у меня еще вопрос остался невыясненным. Вот у меня есть текстовый файл в нем предположим записана такая информация:
1000
0100
0010
0001

Почему в обеих прогах (одна по модулю 256, другая по методу CRC-8) результат контрольной суммы разный? Мне казалось, что неважно каким методом считать, но ответ должен быть одинаковым, или я не права?

по модулую 256:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

void main (void)
{
clrscr();
int dlina_stroki;
unsigned int i,T,C;
int M=255;
FILE *in;

char ch;
in=fopen("text.txt","rt");
T=0;

do {
ch=getc(in);
T=T+ch;
} while (ch!=EOF);

fclose(in);

C = T%(M+1);
printf("The control sum = %u\n",C);
getch();
}


CRC-8:

#include <stdio.h>
#include <string.h>
#include <conio.h>

void Update_CRC(char in, char *crc)
{
#define POLYNOMIAL 0x1D // x^8+x^4+x^3+x^2+1
*crc = *crc^in;

for (unsigned char i=0; i<8; i++)
{
*crc=(*crc & 0x80) ? (*crc << 1) ^POLYNOMIAL: (*crc << 1);

}
}


int main()
{
int i;
unsigned char crc = 0;
FILE *_open;
char ch;
clrscr();

_open=fopen("text.txt","rt");
do {
ch=getc(_open);
Update_CRC(ch,&crc);
} while (ch!=EOF);
fclose(_open);

printf("CRC-8 = %u\n", crc);
getch();
return 0;
}


Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Цитата(Тёмный Эльф @ 9.05.2007 1:06) *
Почему в обеих прогах (одна по модулю 256, другая по методу CRC-8) результат контрольной суммы разный? Мне казалось, что неважно каким методом считать, но ответ должен быть одинаковым, или я не права?

Простое суммирование и CRC - абсолютно разные алгоритмы, и результаты, естественно, совпадать не будут. Видимо я ввёл тебя в заблуждение, назвав результат вычисления CRC контрольной суммой. Это некорректно с теоретической точки зрения (т. к. CRC - это не сумма), но такая терминология сложилась по историческим причинам. Более того, CRC-8 - это не один алгоритм, а целое семейство. Выбор полинома-делителя влияет на результат для одного и того же набора входных данных. Если заменить 0x1D на 0x8D в "#define POLYNOMINAL", то результат поменяется, но это по-прежнему будет CRC-8 (уже соответствующий рекомендации CCITT). Главное условие - чтобы источник (передатчик) и приёмник данных использовали один и тот же полином.

Сообщение отредактировано: xds -


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Еще раз спасибо. Теперь все прояснилось. =)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


И тебе спасибо! У меня тоже многое прояснилось по поводу CRC give_rose.gif В одной из задач, которыми я сейчас занимаюсь, это довольно-таки важный момент.


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






а чему полином равен в CRC-8 в данном случае?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Тёмный Эльф,
более правильным переводом CRC будет не "контрольная сумма", а "контрольный код".
Собственно, контрольная сумма - частный случай контрольного кода, а сам контрольный код представляет собой хеш-функцию от массива данных, предназначенную для детектирования ошибок. В разных случаях ошибки имеют разную природу и, соответственно, различный характер.
контрольная сумма - хороший ваиант для контролья блоков ПЗУ фиксированного размера, для чего она, собственно, и используется. В то же время она нечувствительна к добавлению или пропуску нулевых байтов, к перестановке байтов местами, а также перестановке битов одного и того же разряда между байтами. Поэтому при передаче пакетов, особенно переменной длины, этот алгоритм неоптимален в качестве контрольного кода.
Таким образом, алгоритмы подсчета контрольного кода могут различаться - главное, чтобы конрольный код, посчитанный по конкретному алгоритму детектировал ошибки характерные для того способа передачи, который защищается этим кодом.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Блин! меня наверно за идиота посчитали! в этой программе полином не 1D! А если и 1D то тогда программа не правильная.

Доказываю: вписываем в text.txt таокй текст 12345 - получаем ответ - 30!

идем дальше. Открываем text.txt в HexWorkshop'e заменяем байты на 1D должно получиться СRC=0!!! но так не получается! Что можете сказать по этому поводу?
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 1.10.2020 20:54
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name