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

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

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

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

17.06.2012, 16:50. Просмотров 6927. Ответов 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++):

Как подсчитать CRC! - C++
Уважаемые Форумчане! Как подсчитать CRC. Есть файл чтения EEProm. - :10000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00 ...

Алгоритм вычисления CRC-8 - C++
unsigned short crc8 (unsigned short *ptr, unsigned short size ) { unsigned short sum=0; while(size&gt;0) { sum+=ptr; sum += (sum...

Наивный подход CRC-32 - C++
Объясните пожалуйста что делает каждая строчка функции в наивном подходе CRC-32. static uint32_t crc32_naive(uint8_t *buf) { ...

Расчет CRC-16 c Revert: true - C++
Добрый день. Прошу помочи с такой проблемой: сделал быстрый (т.е. с таблицей) расчет CRC для полинома 0х1021. Считает верно. Теперь...

Убрать реверс в CRC-алгоритме - C++
Господа, помогите ньюфагу. Нашел такую реализацию CRC32. Если проверить здесь www.zorc.breitbandkatze.de/crc.html, видно что она выдает...

Подсчитать CRC для файла - C++
Здравствуйте! Есть имя файла. Как для этого файла подсчитать CRC? Проблема не в понимании алгоритма, а в том, что на данном языке я не...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Hrundel
26 / 26 / 2
Регистрация: 27.05.2012
Сообщений: 114
17.06.2012, 20:35 #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 #3
Цитата Сообщение от ntny Посмотреть сообщение
Во первых почему на вики в алгоритме срс инициализирует значением в 255.
crc-8, на сколько я понимаю это 8 бит, 2^8-1=255.
ntny
7 / 7 / 0
Регистрация: 17.06.2012
Сообщений: 168
17.06.2012, 21:07  [ТС] #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 #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  [ТС] #6
Hrundel, про нечетность понял, спасибо.

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

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

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

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

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

Но с поразрядными операциями впервые столкнулся
Hrundel
26 / 26 / 2
Регистрация: 27.05.2012
Сообщений: 114
17.06.2012, 22:57 #7
Цитата Сообщение от ntny Посмотреть сообщение
Но с побитовыми операциями впервые столкнулся
Эта одна из самых важных тем, для понимания работы с данными.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
17.06.2012, 23:16 #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  [ТС] #9
ValeryS, то, что происходит при хор на 0хff я знаю.
Я не понял смысл этого действия)
Но вернусь к срс потом.
Сначала просто позанимаюсь поразрядными операциями.
Поищю просто более простые задачи.

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

^0000?

----------

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



Добавлено через 51 секунду
Хотя я туплю.
0xFF 0x0FF
Это ведь одно и тоже число(
степени то у разрядов одинаковые
kazak
3034 / 2355 / 155
Регистрация: 11.03.2009
Сообщений: 5,402
Завершенные тесты: 1
18.06.2012, 11:18 #10
Цитата Сообщение от ntny Посмотреть сообщение
Грубо говоря "алгоритм" делит каждывй байт двоичного файла поочередно(как столбиком на уроке арифметики) на байт именуемый полиномом.
Вообще, если разобрать программу и сравнить со словесным описанием алгоритма, можно заметить, что они несколько отличаются.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.06.2012, 11:18
Привет! Вот еще темы с ответами:

Реализация - C++
Кто может помочь с одним моментом в курсовике , курсовик сделан почти весь, но там буквально 5-7 строчек кода нужно чтобы всё заработало. ...

Собственно реализация - C++
Помогите реальзовать программу... Нужно,при запуске был текст приветствия. После нужно ввести команду &quot;text1&quot; Появляется сообщение. ...

Своя реализация new - C++
Приведите пожалуйста пример своей реализации operator new и его последующее применение в виде работающей программы, просто хотелось бы...

Реализация 2-3 дерева - C++
Помогите пожалуйста реализовать 2-3 дерево


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.06.2012, 11:18
Ответ Создать тему
Опции темы

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