Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм CRC32 / 23 сообщений из 23, страница 1 из 1
29.05.2011, 22:54
    #37284572
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
Доброго времени суток. Нашел следующую реализацию алгоритма 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
29.05.2011, 23:41
    #37284612
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
daunito,

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

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

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

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

начало расчета полинома. Подробнее в вике
Что значит "начало расчета полинома"? Полином уже есть, его не надо рассчитывать. Xor'иться сообщение должно с полиномом, а тут оно везде ксорится с маской. Если в педии есть рассказ про маску, кинь ссылку, плиз.
...
Рейтинг: 0 / 0
30.05.2011, 19:42
    #37286197
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
daunitoЯ имею ввиду, что такое
Код: plaintext
const unsigned MASK = 0xD202EF8D;
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
...
Рейтинг: 0 / 0
30.05.2011, 21:48
    #37286334
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
Алгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
...
Рейтинг: 0 / 0
31.05.2011, 03:12
    #37286513
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
SiemargldaunitoЯ имею ввиду, что такое
Код: plaintext
const unsigned MASK = 0xD202EF8D;
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
Глюк, не глюк, а работает.
...
Рейтинг: 0 / 0
31.05.2011, 03:17
    #37286515
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
maytonАлгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
...
Рейтинг: 0 / 0
31.05.2011, 13:18
    #37287108
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
daunitoSiemarglпропущено...
Это глюк в твоем найденном на болоте коде )
В оригинале нету такого.
Глюк, не глюк, а работает.Чего бы не работал, просто можно потерять в качестве хэширования. Результат вычисления совпадает с другими расчетами?
...
Рейтинг: 0 / 0
31.05.2011, 14:31
    #37287309
refreg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
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
31.05.2011, 14:50
    #37287371
refreg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
refregОбрати внимание на & 0xFF . Эта добавка инвертирует начальный 0xFFFFFFFFUL;Бред, конечно, написал.
Имел ввиду, начальный crc разный, с точностью до инверсии, и поэтому выбирается из таблицы с разных концов. Все остальное в силе
...
Рейтинг: 0 / 0
31.05.2011, 14:54
    #37287381
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
daunitomaytonАлгоритм CRC32 - это слишком общее название. Наверное речь
идёт о методе или типе полинома. Здесь аж 5 штук описано. Какой у автора - Х.З.
Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
Если ты пришёл спрашивать - то спрашивай. Если считаешь себя шарящим то
можешь сам ответить на вопрос "откуда берется маска и для чего она нужна".
В противном случае создаётся впечатление что за тебя пишут два разных
человека.
...
Рейтинг: 0 / 0
31.05.2011, 20:58
    #37288201
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
maytondaunitoпропущено...

Почему это Х.З.? Полином же в коде написан. Стандартный 0хEDB88320, по которому считает WinRAR. Неужели никто в CRC не шарит?
Если ты пришёл спрашивать - то спрашивай. Если считаешь себя шарящим то
можешь сам ответить на вопрос "откуда берется маска и для чего она нужна".
В противном случае создаётся впечатление что за тебя пишут два разных
человека.Я не имел ввиду, что я сильно в нем шарю. Просто мне нужен конкретный ответ, типа нужно для того-то и того-то, от человека, который понимает алгоритм и конкретно эту реализацию.
SiemarglЧего бы не работал, просто можно потерять в качестве хэширования. Результат вычисления совпадает с другими расчетами?
Результат полностью совпадает с расчетами WinRAR и TotalCommander. Скорость даже чуть выше, хотя может из-за буферизации показалось (проверял на одном и том же файле сначала вышеуказанными прогами, потом кодом в сабже)
...
Рейтинг: 0 / 0
31.05.2011, 22:00
    #37288305
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
0xEDB88320 = 1110 1101 1011 1000 1000 0011 0010 0000 (bin) - переворачиваем
наоборот и получаем 00000100110000010001110110110111 = 0x4C11DB7 весовые
коэффициенты членов полинома. Если-бы ты прочитал ссылку которую я привёл
внимательно то увидел-бы фразу "зеркальное отображение".
...
Рейтинг: 0 / 0
01.06.2011, 19:19
    #37290052
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
mayton0xEDB88320 = 1110 1101 1011 1000 1000 0011 0010 0000 (bin) - переворачиваем
наоборот и получаем 00000100110000010001110110110111 = 0x4C11DB7 весовые
коэффициенты членов полинома. Если-бы ты прочитал ссылку которую я привёл
внимательно то увидел-бы фразу "зеркальное отображение".
Спасибо за ссылку, но я ее прочитал еще до того как на форуме писать. Да, EDB88320 - это зеркальная реализация, тут все понятно. Но вопрос-то про маску не раскрыт. Маска такая откуда взялась?
...
Рейтинг: 0 / 0
01.06.2011, 19:52
    #37290094
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
refregrefregОбрати внимание на & 0xFF . Эта добавка инвертирует начальный 0xFFFFFFFFUL;Бред, конечно, написал.
Имел ввиду, начальный crc разный, с точностью до инверсии, и поэтому выбирается из таблицы с разных концов. Все остальное в силеЧто ты имеешь ввиду, под разным crc с точностью до инверсии? Действительно как ты писал, xor с маской переворачивает зеркально таблицу, т.е. последнее значение становится первым. Я только не пойму, таблица же рассчитывалась с уже зеркальным полиномом, зачем ее еще и переворачивать?
...
Рейтинг: 0 / 0
01.06.2011, 19:58
    #37290104
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
Давай сравним реализации алгоритма с 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
01.06.2011, 20:00
    #37290110
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
refreg, спасибо. Сам спросил и сам же потом понял )
...
Рейтинг: 0 / 0
01.06.2011, 20:07
    #37290123
daunito
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
mayton, да реализацию я уже взял, все нормально работает. Но вот объяснить ее не мог в связи с неполным пониманием работы сего чуда. Да и самому как-то стремно пользоваться кодом, которого не понимаешь.
...
Рейтинг: 0 / 0
02.06.2011, 08:46
    #37290503
refreg
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм CRC32
refregКороче, как я понял, смысл в том, что
table[1] ^ table[254] = Mask
table[2] ^ table[253] = MaskПодправлюсь, на самом деле:
Код: plaintext
table[i] ^ 0xFF000000 = table[255-i] ^ Mask
0xFF000000 - опять же из-за инверсии начального CRC.
---
Возникает, вопрос - почему при формировании таблицы сразу не проXORили с маской. Тогда бы в цикле было бы на одну операцию меньше...
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм CRC32 / 23 сообщений из 23, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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