caxapa.ru :: Объясните выгоду табличной реализации подсчета CRC32!

Argon (09.08.2007 07:47, просмотров: 8758)

Объясните выгоду табличной реализации подсчета CRC32! В теории объясняется бОльшая скорость табличного варианта, т.к. в нетабличном варианте происходят побитовые сдвиги (как я понял): сдвиг на 1 бит влево регистра CRC сдвиг на 1 бит влево байта сообщения с задвиганием бита в регистр CRC и так 8 раз для каждого байта сообщения. В то время как в табличном варианте: взятие индекса таблицы по старшему байту регистра CRC (сдвиг на 24 бита вправо регистра) сдвиг на 8 бит влево регистра CRC и загон туда нового байта сообщения и так для каждого байта сообщения. Как-то пока прямой выгоды не вижу...

- Напомню ещё ссылку на программу генерации VHDL/Verilog кода для CRC - vmp(13.08.2007 11:08, ссылка)
- Написал программку на Builder для тестирования 3х алгоритмов. Argon(478 знак., 10.08.2007 10:07, )
  - Попробуй ещё побайтовый без таблички. Полином может оказаться другой, но время от этого мало зависит. ReAl(342 знак., 10.08.2007 11:27)
    - Проверил, Ваш алгоритм 1200 мсек. Т.е. находится между байтовотабличным и потетраднотабличным. Похоже, оптимальнее уже некуда? ;-) - Argon(13.08.2007 06:39)
      - Вот именно :-) Только он не мой, я просто о нём напомнил :-) - ReAl(13.08.2007 12:29)
    - Ок, но только в понедельник, у нас День Строителя начинается! - Argon(10.08.2007 11:38)
- Может, кто знает достоверно, какой из полиномов прямой, а какой зеркальный? Argon(424 знак., 09.08.2007 12:04, )
- Смотрю реализации зеркальных табличных CRC алгоритмов, там как будто нет больших сдвигов на 24 бита... - Argon(09.08.2007 09:55, )
  - А всё равно - сдвиг на 24 бита это или ровно столько же времени, сколько сдвиг на 1 бит ReAl(320 знак., 09.08.2007 10:33)
    - Ага, понял, пасиба! - Argon(09.08.2007 11:16, )
- ИМХО У табличного метода есть еще один недостаток, VJO(106 знак., 09.08.2007 08:42, )
  - Это не так страшно, если держать таблицу в ОЗУ, процедура пересчета - 3-4 строчки. Argon(142 знак., 09.08.2007 09:54, )
    - Кстати, а для CRC32 есть "убыстрённые" алгоритмы - как для CRC16, или они выходят слишком задумчивые и теряют смысл? В духе: ReAl(351 знак., 09.08.2007 10:41)
      - По той инфе, что нашел, таблица для CRC32 не будет меньше чем 1024 байта, если обрабатывать побайтно. - Argon(09.08.2007 11:23, )
        
        512 байт - это для CRC16 (256 слов размером в CRC). А приведенный алгоритм для одной из 16-битных CRC (для других есть аналогичные) и без цикла по битам, и без таблички. - ReAl(09.08.2007 15:28, )
        
        Сорри, не так понял Ваше сообщение. А как приведенный алгоритм вписывается в теорию CRC? Полинома в нем не вижу... - Argon(10.08.2007 08:40, )
        
        А в таблице, если не знать, как она сделана - тоже не видно полинома :-) Т.е. этот алгоритм - просто развёрнутый в линию и соптимизированный битовый цикл (а в таблице он вообще предвычислен). ReAl(316 знак., 10.08.2007 11:15, ссылка)

Микроконтроллеры