Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.77
ntny
7 / 7 / 0
Регистрация: 17.06.2012
Сообщений: 168
#1

Реализация crc - C++

17.06.2012, 16:50. Просмотров 6416. Ответов 9
Метки нет (Все метки)

Здравствуйте.
Пытаюсь написать алгоритм
Используя полимональную арифметику.

Опишу алогритм как понимаю..
Считываю исходный двоичный файл по одному байту в переменную unsigned int message..
Исходное значение срс задаю нулевым. unsigned int crc = 0;
Насколько я понимаю для байта проще всего использовать 8-и разрядный полином.

C++
1
2
3
4
5
6
7
8
9
10
data = message; переменную использую для проверки старшего бита
while(!EOF) // считываю файл до конца
{ 
if(data & 128) //Проверяю старший бит
 crc^ = ((message << 1)^Polynom); //Сдвигаю считанное сообщение на 1 бит делаю xor с полиномом(полином использую без старшего бита).
data = crc;
else 
message << 1;
data = message;
}
Не понятно следующее.
http://ru.wikipedia.org/wiki/Crc
Во первых почему на вики в алгоритме срс инициализирует значением в 255.
Смотрю "Пример программы расчёта CRC8 на языке"
C++
1
2
3
4
5
6
unsigned char crc = 0xFF;
    unsigned int i;
 
    while (len--)
    {
        crc ^= *pcBlock++;
объясните пожалуйста смысл этого кода.
Насколько я понимаю по указателю содержится считываемый байт.
В чем смысл совершать с ним хор по 0xFF если это не полином?

Заранее извиняюсь за глупые вопросы(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2012, 16:50     Реализация crc
Посмотрите здесь:

C++ реализация cat в с++
C++ Реализация
C++ реализация класса
Подсчитать CRC для файла C++
Как подсчитать CRC! C++
Расчет CRC-16 c Revert: true C++
Алгоритм вычисления CRC-8 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Hrundel
26 / 26 / 2
Регистрация: 27.05.2012
Сообщений: 114
17.06.2012, 20:35     Реализация crc #2
Цитата Сообщение от ntny Посмотреть сообщение
почему на вики в алгоритме сRс инициализирует значением в 255
Наверное потому, что это размер одного байта.

C++
1
unsigned char crc = 0xFF;  // равен как раз одному байту
Кстати, было бы не плох узнать, что это за алгоритм, что он делает, и какова его задача.
А то и впямь трудно понять причем тут XOR.

Добавлено через 4 минуты
Цитата Сообщение от ntny Посмотреть сообщение
по одному байту в переменную unsigned int
а unsigned int бывает по одному байту?
Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
17.06.2012, 20:42     Реализация crc #3
Цитата Сообщение от ntny Посмотреть сообщение
Во первых почему на вики в алгоритме срс инициализирует значением в 255.
crc-8, на сколько я понимаю это 8 бит, 2^8-1=255.
ntny
7 / 7 / 0
Регистрация: 17.06.2012
Сообщений: 168
17.06.2012, 21:07  [ТС]     Реализация crc #4
Hrundel, там же есть ссылка на википедию.
Грубо говоря "алгоритм" делит каждывй байт двоичного файла поочередно(как столбиком на уроке арифметики) на байт именуемый полиномом.
В итоге в конце этой операции остается остаток который служит в качестве контрольной суммы для данного файла.
XOR применяется в качестве замены операции деления(деление тут полимольное, т.е. без переносов)
Т.е. если остаток изменился, то изменился соответственно и сам файл.

В интернете нашел только довольно путанные описания или куски алгоритмов(как на викки) без детального пояснения.


Цитата Сообщение от Hrundel Посмотреть сообщение
а unsigned int бывает по одному байту?
Ну я не пытался еще считывать, пока не разобрался с самой логикой.
А в тип int?
Вообще я даже начинающим себя не могу назвать. Просто для сея тзучаю.
И вот сегодня целый день читал, что нашел, но видимо сам тупой.


ZoRT, и все равно не понимаю.
Если не сложно подробнее.
Что нам дает инициализация переменной 1-м байтом.

Я видимо неправильно что-то понимаю.

Добавлено через 2 минуты
Просто 255 это 8-м единичек.
Они учавствуют в XOR
Естественно влияют на результат.
Я не могу понять смысл этого хора.
Т.к. насколько я понимаю учавствовать должны только содержание считываемого байта и полином(делитель)

Добавлено через 3 минуты
чар я так понимаю используют потому, что он как раз 1 байт и занимает
Hrundel
26 / 26 / 2
Регистрация: 27.05.2012
Сообщений: 114
17.06.2012, 22:50     Реализация crc #5
Цитата Сообщение от ntny Посмотреть сообщение
В чем смысл совершать с ним хор по 0xFF если это не полином?
Начнем с того, что Википедия гласит: "Алгоритм CRC обнаруживает все одиночные ошибки, двойные ошибки и ошибки в нечетном числе битов"

То есть, первое и самое главное, проверяет нечетное число битов. Передача данных в подобном виде настолько нетривиальна, что приходится проверять ее на наличие ошибок. Это раз.


Цитата Сообщение от ntny Посмотреть сообщение
XOR применяется в качестве замены операции деления(деление тут полимольное, т.е. без переносов)
Это очень неправильное высказывание. XOR (исключающий или) это операция совершаемая над числами в двоичном представлении, наряду с логическими операциями UND, OR, NOR, NXOR, NOT.
Об этих операциях необходимо читать раздел Булевой алгебры.

так например при применении операции UND над двумя двоичными чилсами получим следующий результат:

0011 (=3)
UND
0100 (=4)
_________
0000 (=0) вот такой вот ответ!

а при применении оператора OR

0011 (=3)
OR
0110 (=6)
_________
0101 (=5)

0011 (=3)
XOR
0110 (=6)
_________
0111 (=7)

Добавлено через 7 минут
Цитата Сообщение от ntny Посмотреть сообщение
unsigned char crc = 0xFF;
unsigned int i;
while (len--)
{
crc ^= *pcBlock++;
по этому отрывку, лично я, немогу понять, что передается pcBlock.
Поэтому ответить на твой вопрос, нет никакой возможности.

Ну, и вообще, думаю, что не стоит браться за такие алгоритмы без знаний основ информатики. Да и С надо тоже подтянуть.

Добавлено через 1 минуту
Цитата Сообщение от ntny Посмотреть сообщение
И вот сегодня целый день читал, что нашел, но видимо сам тупой.
Да нет, не тупой. Наоборот, молодец, что пробуешь. Но надо основы информатики читать.
ntny
7 / 7 / 0
Регистрация: 17.06.2012
Сообщений: 168
17.06.2012, 22:53  [ТС]     Реализация crc #6
Hrundel, про нечетность понял, спасибо.

Про исключяющее или, и "и" я все же знаю.

Но именно в полимональной арифметике. ХОР используется как аналог деления.
Конечно же "насколько я понимаю"

Нашел более менее понятное.
http://kpe.hww.ru/ASM/Book/Charter9/1.htm

Про булеву алгебру действительно почитаю.

С информатикой я знаком на уровне, циклов, пользовательских типов данных. Собственных алгоритмов.
Около половины книги Страусстрапа.

Но с поразрядными операциями впервые столкнулся
Hrundel
26 / 26 / 2
Регистрация: 27.05.2012
Сообщений: 114
17.06.2012, 22:57     Реализация crc #7
Цитата Сообщение от ntny Посмотреть сообщение
Но с побитовыми операциями впервые столкнулся
Эта одна из самых важных тем, для понимания работы с данными.
ValeryS
Модератор
6482 / 4948 / 455
Регистрация: 14.02.2011
Сообщений: 16,389
17.06.2012, 23:16     Реализация crc #8
Цитата Сообщение от ntny Посмотреть сообщение
одному байту в переменную unsigned int message..
вот здесь лучше и правильней использовать unsigned char
само по себе будет деление по модулю(256) (переполнение)
например есть число 0xFF(255) добавим 0x02
тогда в
unsigned char будет 0x01
а в
unsigned int 0x0101

Добавлено через 8 минут
Цитата Сообщение от ntny Посмотреть сообщение
Просто 255 это 8-м единичек.
Они учавствуют в XOR
Естественно влияют на результат.
Я не могу понять смысл этого хора.
это просто инвертирование бита
смысл "исключающего или" в том что если оба бита равны =0
если нет 1
0 0 = 0
0 1 =1
1 0 =1
1 1 = 0
0xFF(255)^0x0=0x0FF
0xFF ^0xF0= 0x0F
0xFF^ 0xFF =0x00
ну и так далее

Добавлено через 3 минуты
Цитата Сообщение от Hrundel Посмотреть сообщение
а при применении оператора OR
0011 (=3)
OR
0110 (=6)
_________
0101 (=5)
Цитата Сообщение от Hrundel Посмотреть сообщение
0011 (=3)
XOR
0110 (=6)
_________
0111 (=7)
все с точностью до наоборот
0011 (=3)
OR
0110 (=6)
_______
0111 (=7)

0011 (=3)
XOR
0110 (=6)
_________
0101 (=5)
ntny
7 / 7 / 0
Регистрация: 17.06.2012
Сообщений: 168
17.06.2012, 23:38  [ТС]     Реализация crc #9
ValeryS, то, что происходит при хор на 0хff я знаю.
Я не понял смысл этого действия)
Но вернусь к срс потом.
Сначала просто позанимаюсь поразрядными операциями.
Поищю просто более простые задачи.

Добавлено через 6 минут
А почему 0xFF(255)^0x0=0x0FF
Разве это не
11111111

^0000?

----------

11111111
0xFF(255)^0x0 !=0xFF?



Добавлено через 51 секунду
Хотя я туплю.
0xFF 0x0FF
Это ведь одно и тоже число(
степени то у разрядов одинаковые
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.06.2012, 11:18     Реализация crc
Еще ссылки по теме:

Наивный подход CRC-32 C++
C++ Реализация формулы
Реализация k-стеков C++
Реализация шаблонов C++
C++ Убрать реверс в CRC-алгоритме

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
kazak
3031 / 2352 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
18.06.2012, 11:18     Реализация crc #10
Цитата Сообщение от ntny Посмотреть сообщение
Грубо говоря "алгоритм" делит каждывй байт двоичного файла поочередно(как столбиком на уроке арифметики) на байт именуемый полиномом.
Вообще, если разобрать программу и сравнить со словесным описанием алгоритма, можно заметить, что они несколько отличаются.
Yandex
Объявления
18.06.2012, 11:18     Реализация crc
Ответ Создать тему
Опции темы

Текущее время: 20:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru