powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм CRC32
23 сообщений из 23, страница 1 из 1
Алгоритм CRC32
    #37284572
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Доброго времени суток. Нашел следующую реализацию алгоритма CRC32:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
class crc32
{
protected:
	unsigned table[ 256 ];
public:
	unsigned m_crc32;
	crc32();
	void ProcessCRC(void *pData,int Len);
};

crc32::crc32()
{
	const unsigned POLY = 0xEDB88320;
	unsigned i,j,r;
	for(i= 0 ;i< 256 ;i++)
	{
		for(r=i, j= 8 ; j; j--)
			r=r &  1 ? (r>> 1 )^POLY : r>> 1 ;
		table[i]=r;
	}
	m_crc32 =  0 ;
};

void crc32::ProcessCRC(void *pData, register int Len)
{
  const unsigned MASK = 0xD202EF8D;
  register unsigned char *pdata = reinterpret_cast<unsigned char *>(pData);
  register unsigned crc = m_crc32;
  while (Len--)
  {
        crc = table[static_cast<unsigned char>(crc) ^ *pdata++] ^ crc>> 8 ;
	crc ^= MASK;
  }
  m_crc32 = crc;
}
Классический алгоритм понимаю хорошо, но в этом никак не могу въехать откуда берется маска и для чего она нужна. Перерыл весь интернет, везде пишут про маску, но нигде не поясняется что она такое.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37284612
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunito,

table[]
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37284676
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargldaunito,

table[]
Что table[]?
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37284677
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я имею ввиду, что такое
Код: plaintext
const unsigned MASK = 0xD202EF8D;
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37284822
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunito,

начало расчета полинома. Подробнее в вике
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37284898
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[не активирован]
[не одобрен]
Siemargldaunito,

начало расчета полинома. Подробнее в вике Но в вики другие цифры :)
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37286092
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargldaunito,

начало расчета полинома. Подробнее в вике
Что значит "начало расчета полинома"? Полином уже есть, его не надо рассчитывать. Xor'иться сообщение должно с полиномом, а тут оно везде ксорится с маской. Если в педии есть рассказ про маску, кинь ссылку, плиз.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37286197
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunitoЯ имею ввиду, что такое
Код: plaintext
const unsigned MASK = 0xD202EF8D;
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37286334
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37286513
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SiemargldaunitoЯ имею ввиду, что такое
Код: plaintext
const unsigned MASK = 0xD202EF8D;
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
Глюк, не глюк, а работает.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37286515
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonАлгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37287108
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunitoSiemarglпропущено...
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
Глюк, не глюк, а работает.Чего бы не работал, просто можно потерять в качестве хэширования. Результат вычисления совпадает с другими расчетами?
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37287309
refreg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunitoНеужели никто в CRC не шарит? Я не шарю... но заинтересовался.
Короче, как я понял, смысл в том, что
table[1] ^ table[254] = Mask
table[2] ^ table[253] = Mask

Идет просто подмена значений таблицы, и эта подмена корректируется маской.
Код из wiki эквивалентен коду из поста 1:
Код: plaintext
1.
2.
3.
4.
5.
crc = 0xFFFFFFFFUL;
 
    while (len--) 
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >>  8 );
 
    return crc ^ 0xFFFFFFFFUL;
Обрати внимание на & 0xFF . Эта добавка инвертирует начальный 0xFFFFFFFFUL;
Дальше, писать не буду разобраться можно, если представить, что пришел первый байт, равный 0х1, и прокрутить оба алгоритма по шагам.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37287371
refreg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
refregОбрати внимание на & 0xFF . Эта добавка инвертирует начальный 0xFFFFFFFFUL;Бред, конечно, написал.
Имел ввиду, начальный crc разный, с точностью до инверсии, и поэтому выбирается из таблицы с разных концов. Все остальное в силе
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37287381
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
daunitomaytonАлгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
Если ты пришёл спрашивать - то спрашивай. Если считаешь себя шарящим то
можешь сам ответить на вопрос "откуда берется маска и для чего она нужна".
В противном случае создаётся впечатление что за тебя пишут два разных
человека.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37288201
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytondaunitoпропущено...

Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
Если ты пришёл спрашивать - то спрашивай. Если считаешь себя шарящим то
можешь сам ответить на вопрос "откуда берется маска и для чего она нужна".
В противном случае создаётся впечатление что за тебя пишут два разных
человека.Я не имел ввиду, что я сильно в нем шарю. Просто мне нужен конкретный ответ, типа нужно для того-то и того-то, от человека, который понимает алгоритм и конкретно эту реализацию.
SiemarglЧего бы не работал, просто можно потерять в качестве хэширования. Результат вычисления совпадает с другими расчетами?
Результат полностью совпадает с расчетами WinRAR и TotalCommander. Скорость даже чуть выше, хотя может из-за буферизации показалось (проверял на одном и том же файле сначала вышеуказанными прогами, потом кодом в сабже)
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37288305
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
0xEDB88320 = 1110 1101 1011 1000 1000 0011 0010 0000 (bin) - переворачиваем
наоборот и получаем 00000100110000010001110110110111 = 0x4C11DB7 весовые
коэффициенты членов полинома. Если-бы ты прочитал ссылку которую я привёл
внимательно то увидел-бы фразу "зеркальное отображение".
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290052
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton0xEDB88320 = 1110 1101 1011 1000 1000 0011 0010 0000 (bin) - переворачиваем
наоборот и получаем 00000100110000010001110110110111 = 0x4C11DB7 весовые
коэффициенты членов полинома. Если-бы ты прочитал ссылку которую я привёл
внимательно то увидел-бы фразу "зеркальное отображение".
Спасибо за ссылку, но я ее прочитал еще до того как на форуме писать. Да, EDB88320 - это зеркальная реализация, тут все понятно. Но вопрос-то про маску не раскрыт. Маска такая откуда взялась?
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290094
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
refregrefregОбрати внимание на & 0xFF . Эта добавка инвертирует начальный 0xFFFFFFFFUL;Бред, конечно, написал.
Имел ввиду, начальный crc разный, с точностью до инверсии, и поэтому выбирается из таблицы с разных концов. Все остальное в силеЧто ты имеешь ввиду, под разным crc с точностью до инверсии? Действительно как ты писал, xor с маской переворачивает зеркально таблицу, т.е. последнее значение становится первым. Я только не пойму, таблица же рассчитывалась с уже зеркальным полиномом, зачем ее еще и переворачивать?
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290104
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давай сравним реализации алгоритма с wiki и твоего

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
void crc32::ProcessCRC(void *pData, register int Len)
{
  const unsigned MASK = 0xD202EF8D;
  register unsigned char *pdata = reinterpret_cast<unsigned char *>(pData);
  register unsigned crc = m_crc32;
  while (Len--)
  {
        crc = table[static_cast<unsigned char>(crc) ^ *pdata++] ^ crc>> 8 ;
	crc ^= MASK;
  }
  m_crc32 = crc;
}

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
#include <stddef.h>
#include <stdint.h>
/*
  Name  : CRC-32
  Poly  : 0x04C11DB7    x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 
                       + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
  Init  : 0xFFFFFFFF
  Revert: true
  XorOut: 0xFFFFFFFF
  Check : 0xCBF43926 ("123456789")
  MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение
   одинарных, двойных, пакетных и всех нечетных ошибок
*/
uint_least32_t Crc32(unsigned char *buf, size_t len)
{
    uint_least32_t crc_table[ 256 ];
    uint_least32_t crc; int i, j;
 
    for (i =  0 ; i <  256 ; i++)
    {
        crc = i;
        for (j =  0 ; j <  8 ; j++)
            crc = crc &  1  ? (crc >>  1 ) ^ 0xEDB88320UL : crc >>  1 ;
 
        crc_table[i] = crc;
    };
 
    crc = 0xFFFFFFFFUL;
 
    while (len--) 
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >>  8 );
 
    return crc ^ 0xFFFFFFFFUL;
}

Они отличаются инициализацией и телом цикла. Константа всплыла скорее всего как поправка
на инициализацию.

Я-бы лучше не плавил себе мозг этой проблемой (лучше подумать над Гильбертом ). А просто взял
имплементацию которая короче и делает внутри цикла меньше операций. (Естественно, проведя
хотя-бы по 1 testcase для каждого исходника).
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290110
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
refreg, спасибо. Сам спросил и сам же потом понял )
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290123
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, да реализацию я уже взял, все нормально работает. Но вот объяснить ее не мог в связи с неполным пониманием работы сего чуда. Да и самому как-то стремно пользоваться кодом, которого не понимаешь.
...
Рейтинг: 0 / 0
Алгоритм CRC32
    #37290503
refreg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
refregКороче, как я понял, смысл в том, что
table[1] ^ table[254] = Mask
table[2] ^ table[253] = MaskПодправлюсь, на самом деле:
Код: plaintext
table[i] ^ 0xFF000000 = table[255-i] ^ Mask
0xFF000000 - опять же из-за инверсии начального CRC.
---
Возникает, вопрос - почему при формировании таблицы сразу не проXORили с маской. Тогда бы в цикле было бы на одну операцию меньше...
...
Рейтинг: 0 / 0
23 сообщений из 23, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм CRC32
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]