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!!! но так не получается! Что можете сказать по этому поводу?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Le Viagra Pas Cher En Montauban
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Cialis Esperienza Personale
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Бывалый
***

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

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


Why not settling on games that is fun and at the same time your earning. Well itll make suspense because of the game as well but dude just try it and it gave me hope while pandemic is real rn. Top Baccarat Players in the History
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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