Реализации алгоритмов/Циклический избыточный код: различия между версиями

Содержимое удалено Содержимое добавлено
м оформление
Строка 13:
{{Hider hiding
|title=Пример программы, генерирующей массив, предназначенный для табличного способа вычисления CRC4 на языке [[C Sharp|C#]]
|content-style = text-align:left
|content=
<source lang="csharp">
Строка 89 ⟶ 90 :
{{Hider hiding
|title=Итоговый массив для табличного (быстрого) расчёта CRC4 (результат работы вышеприведенного кода)
|content-style = text-align:left
|content=
<source lang="csharp">
Строка 115 ⟶ 117 :
{{Hider hiding
|title=Пример программы расчёта CRC8 на языке [[w:Си (язык программирования)|Си]]
|content-style = text-align:left
|content=
<source lang="c">
Строка 147 ⟶ 150 :
{{Hider hiding
|title=Пример программы табличного (быстрого) расчёта CRC8 на языке Си
|content-style = text-align:left
|content=
<source lang="c">
Строка 159 ⟶ 163 :
одинарных, двойных, тройных и всех нечетных ошибок
*/
 
/* Таблица закоментирована т.к. википедия не отображает её,
для использования алгоритма нужно её убрать из поля комментариев!
const unsigned char Crc8Table[256] = {
0x00, 0x31, 0x62, 0x53, 0xC4, 0xF5, 0xA6, 0x97,
Строка 195 ⟶ 198 :
0x3B, 0x0A, 0x59, 0x68, 0xFF, 0xCE, 0x9D, 0xAC
};
 
*/
unsigned char Crc8(unsigned char *pcBlock, unsigned char len)
{
Строка 210 ⟶ 213 :
{{Hider hiding
|title=Пример проверки CRC-8 для BBHeader стандарта ETSI EN 302 307 V1.2.1
|content-style = text-align:left
|content=
<source lang="c">
Строка 233 ⟶ 237 :
{{Hider hiding
|title=Пример программы табличного расчёта CRC-8 на языке [[C Sharp|C#]]
|content-style = text-align:left
|content=
<source lang="csharp">
Строка 694 ⟶ 699 :
{{Hider hiding
|title=Пример программы расчёта CRC-32 на языке Си
|content-style = text-align:left
|content=
<source lang="c">
Строка 735 ⟶ 741 :
{{Hider hiding
|title=Пример программы табличного (быстрого) расчёта CRC-32 на языке Си
|content-style = text-align:left
|content=
<source lang="c">
Строка 752 ⟶ 759 :
*/
 
/* Таблица закоментирована т.к. википедия не отображает её,
для использования алгоритма нужно её убрать из поля комментариев!
const uint_least32_t Crc32Table[256] = {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
Строка 820 ⟶ 825 :
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
};
*/
 
uint_least32_t Crc32(const unsigned char * buf, size_t len)
Строка 834 ⟶ 838 :
{{Hider hiding
|title=Хороший пример для расчёта CRC-32 файла на языке С++
|content-style = text-align:left
|content=
<source lang="cpp">
Строка 866 ⟶ 871 :
return CRC32_function((unsigned char*)buf, f.gcount());
}
 
 
 
 
</source>
}}
Строка 876 ⟶ 877 :
Получили распространение несколько методов программного расчета CRC:
* оригинальный алгоритм с побитовым вводом данных:
{{Hider hiding
|title=Расчет одного бита CRC8 по оригинальному алгоритму
|content-style = <source lang="c">text-align:left
|content=
<source lang="c">
// _D - входной бит
// _crc - сдвиговый регистр CRC
Строка 893 ⟶ 898 :
}
}
</source>
}}
 
:* Конечно, этот алгоритм может быть записан короче:
{{Hider hiding|title=Расчет одного бита CRC8 по оригинальному алгоритму|content= <source lang="c">
{{Hider hiding
{{Hider hiding|title=Расчет одного бита CRC8 по оригинальному алгоритму|content= <source lang="c">
|content-style = text-align:left
|content=
<source lang="c">
if (_crc & (1<<7)) {
_crc = _crc << 1;
Строка 903 ⟶ 914 :
if (_D) _crc ^= CRC_Polynom;
}
</source>
}}
* Псевдотабличный с побайтовым вводом данных и генерацией требуемого элемента таблицы непосредственно в цикле расчета:
{{Hider hiding
{{Hider hiding|title=Расчет одного байта CRC8 по псевдотабличному алгоритму|content= <source lang="c">
|content-style = text-align:left
|content=
<source lang="c">
// _D - входной байт
// _crc - сдвиговый регистр CRC
Строка 913 ⟶ 929 :
_crc = (_crc & (1<<7)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
</source>
}}
: По объему кода псевдотабличный метод почти не отличается от прямого расчета, но может быть чуть быстрее, поэтому практически вытеснил оригинальный метод.
* Табличный с побайтовым вводом данных и заранее созданной таблицей:
{{Hider hiding
|title=Расчет одного байта CRC8 по табличному алгоритму
|content-style = <source lang="c">text-align:left
|content=
<source lang="c">
// _D - входной байт
// _crc - сдвиговый регистр CRC
Строка 927 ⟶ 948 :
// 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-style = <source lang="c">text-align:left
|content=
<source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
Строка 939 ⟶ 965 :
CRCTable[x] = _crc;
}
</source>
}}
{{Hider hiding
|title=Генерация таблицы CRC32
|content-style = <source lang="c">text-align:left
|content=
<source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
Строка 950 ⟶ 981 :
CRCTable[x] = _crc;
}
</source>
}}
 
== Примечания ==