Реализации алгоритмов/Циклический избыточный код: различия между версиями
Содержимое удалено Содержимое добавлено
Oleg4280 (обсуждение | вклад) |
Maxal (обсуждение | вклад) перенесено из Википедии |
||
Строка 865:
</source>
}}
== Программная реализация на C ==
Получили распространение несколько методов программного расчета CRC:
* оригинальный алгоритм с побитовым вводом данных:
{{Hider hiding|title=Расчет одного бита CRC8 по оригинальному алгоритму|content= <source lang="c">
// _D - входной бит
// _crc - сдвиговый регистр CRC
// CRC_Polynom - значение полинома CRC
if (_crc & (1<<7)) {
if (_D) {
_crc = _crc << 1;
} else {
_crc = (_crc << 1) ^ CRC_Polynom;
}
} else {
if (_D) {
_crc = (_crc << 1) ^ CRC_Polynom;
} else {
_crc = _crc << 1;
}
}
</source>}}
: Конечно, этот алгоритм может быть записан короче:
{{Hider hiding|title=Расчет одного бита CRC8 по оригинальному алгоритму|content= <source lang="c">
if (_crc & (1<<7)) {
_crc = _crc << 1;
if (0 == _D) _crc ^= CRC_Polynom;
} else {
_crc = _crc << 1;
if (_D) _crc ^= CRC_Polynom;
}
</source>}}
* Псевдотабличный с побайтовым вводом данных и генерацией требуемого элемента таблицы непосредственно в цикле расчета:
{{Hider hiding|title=Расчет одного байта CRC8 по псевдотабличному алгоритму|content= <source lang="c">
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CRC_Polynom - значение полинома CRC
_crc ^= _D;
for (i = 0; i < 8; i++) {
_crc = (_crc & (1<<7)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
</source>}}
: По объему кода псевдотабличный метод почти не отличается от прямого расчета, но может быть чуть быстрее, поэтому практически вытеснил оригинальный метод.
* Табличный с побайтовым вводом данных и заранее созданной таблицей:
{{Hider hiding|title=Расчет одного байта CRC8 по табличному алгоритму|content= <source lang="c">
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CrcTable - таблица, здесь не показана ввиду значительного объема
_crc = CrcTable[_crc ^ _D];
</source>}}
{{Hider hiding|title=Расчет одного байта CRC32 по табличному алгоритму|content= <source lang="c">
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CrcTable - таблица, здесь не показана ввиду значительного объема
_crc = CrcTable[(_crc ^ _D) & 0xFF] ^ (_crc << 8);
</source>}}
: Таблица может быть задана константой (создаваться до компиляции) или генерироваться непосредственно перед выполнением расчета. Табличный метод основан на том что одинаковые последовательности входных данных дают одинаковые изменения регистра сдвига, поэтому за один цикл можно рассчитать больше чем один бит входных данных. Табличный метод требует значительных затрат памяти под таблицы. Размер элемента таблицы равен размеру выбранного полинома. Длина таблицы равна <math>2^D</math>, где D - выбранная длина входных данных в битах для одного цикла расчета (например, для однобайтового варианта это 8 бит). Например, для 32-битной CRC с побайтовым расчетом длина таблицы будет 256 слов по 32 бита, т.е. 1024 байта. Алгоритм генерации таблицы:
{{Hider hiding|title=Генерация таблицы CRC8|content= <source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x;
for (y = 0; y < 8; y++) {
_crc = (_crc & (1<<7)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
CRCTable[x] = _crc;
}
</source>}}
{{Hider hiding|title=Генерация таблицы CRC32|content= <source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x;
for (y = 0; y < 8; y++) {
_crc = (_crc & (1<<31)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
CRCTable[x] = _crc;
}
</source>}}
== Примечания ==
| |||