Заголовок<boost/crc.hpp>содержит два шаблона классов в пространстве имен<boost>. Эти шаблоны определяют объекты, которые могут вычислятьCRCили циклический код избыточности (или проверку) заданного потока данных. Заголовок также предоставляет шаблоны функций для вычисления CRC за один шаг.
Тип реализацииimpl_defозначает самый быстрый в управлении встроенный неподписанный интегральный тип, который может представлять по меньшей меребитовбитов.
Распространенным методом обнаружения ошибок, особенно в электронных коммуникациях, является дополнительная контрольная сумма. Передатчик отправляет свои биты данных, за которыми следуют биты контрольной суммы. Контрольная сумма основана на операциях, выполняемых на потоке битов данных. Приемник применяет те же операции на битах, которые он получает, а затем получает контрольную сумму. Если вычисленная контрольная сумма не соответствует полученной контрольной сумме, то в передаче произошла ошибка. Есть небольшой шанс, что ошибка только в контрольной сумме, и фактически правильный поток данных отклоняется. Существует также вероятность возникновения ошибки, которая не изменяет контрольную сумму, делая эту ошибку невидимой. CRC является распространенным типом контрольной суммы, используемым для обнаружения ошибок для аппаратных интерфейсов и форматов кодирования.
CRC работают, вычисляя оставшуюся часть полиномиального деления модуля-2. Сообщение рассматривается как (двоичные) эффективность длинного полиноминала для дивиденда, а более ранние биты сообщения подаются сначала как самые высокие эффективности полиноминала. У конкретного алгоритма CRC есть еще один полиноминал, связанный с ним для использования в качестве делителя. Коэффициент игнорируется. Остальная часть дивизиона рассмотрела контрольную сумму. Тем не менее, в подразделении используются правила modulo-2 (без переноски) для эффективности.
The divisor polynominal has a degree one bit larger than the
checksum (remainder) size. That highest bit is always one, so
it is ignored when describing a particular CRC type. Excluding
this bit makes the divisor fit in the same data type as the
checksum.
Initial remainder
The interim CRC remainder changes as each bit is processed.
Usually, the interim remainder starts at zero, but some CRCs use
a different initial value to avoid "blind spots." A
blind spot is when a common sequence of message bits does not
change certain interim remainder values.
Final XOR value
A CRC remainder can be combined with a defined value, via
a bitwise exclusive-or operation, before being returned to the
user. The value is usually zero, meaning the interim remainder
is returned unchanged. The other common value is an all-ones
value, meaning that the bitwise complement of the interim
remainder is returned.
Reflected input
A message's bits are usually fed a byte at a time, with the
highest bits of the byte treated as the higher bits of the
dividend polynominal. Some CRCs reflect the bits (about the
byte's center, so the first and last bits are switched,
etc.) before feeding.
Reflected (remainder) output
Some CRCs return the reflection of the interim remainder (taking
place before the final XOR value stage).
<value_type>является наименьшим встроенным типом, который может содержать указанное (по<Bits>) количество битов. Это должно быть<boost::uint_t<Bits>::least>, см. документациюдля целочисленного выбора типадля деталей.
Эта реализация медленная, поскольку она вычисляет свой CRC так же, как и в теории. Оптимизация не проводится. Он теряет пространство, так как большинство параметров CRC определяются во время выполнения в качестве параметров конструктора.
<value_type>является самым быстрым для манипулирования встроенным типом, который может содержать по меньшей мере указанное (по<Bits>) количество битов. Это должно быть<boost::uint_t<Bits>::fast>. Подробную информацию см. вцелочисленной документации по выбору типа.<TruncPoly>,<InitRem>и<FinalXor>параметры шаблона также этого типа.
Эта реализация является быстрой, поскольку она использует столько оптимизаций, сколько практично. Все параметры CRC указываются во время компиляции в качестве параметров шаблона. Отдельные биты не рассматриваются, передаются только целые байты. Таблица промежуточных значений CRC против значений байта предварительно вычисляется, когда обрабатывается первый объект с использованием определенного размера бита, усеченного полиномиального и состояния отражения ввода.
Два шаблона классов имеют разные политики в отношении параметров CRC. Оба шаблона класса используют количество битов в CRC в качестве первого параметра шаблона. Теоретический шаблон компьютерного класса имеет счетчик битов в качестве единственного параметра шаблона, все остальные параметры CRC вводятся через конструктор. Оптимизированный шаблон класса компьютера получает все свои параметры CRC в качестве параметров шаблона, а инстанцированные объекты обычно строятся по умолчанию.
Параметры CRC могут быть проверены во время выполнения со следующими функциями:<get_truncated_polynominal>,<get_initial_remainder>,<get_final_xor_value>,<get_reflect_input>и<get_reflect_remainder>. Быстрый компьютер также предоставляет константы времени компиляции для своих параметров CRC.
Функция<get_interim_remainder>возвращает внутреннее состояние CRC. Он представляет собой неотраженный остаток последнего деления. Экономия промежуточного остатка позволяет заморозить обработку CRC, если сохранены другие параметры CRC и текущее положение битового потока. Перезапуск замороженного потока предполагает создание нового компьютера с большинством параметров старого компьютера. Единственное изменение заключается в использовании замороженного остатка в качестве первоначального остатка нового компьютера. Затем прерванный битовый поток можно подавать так, как будто ничего не произошло. Быстрый компьютер CRC имеет специальный конструктор, который принимает один аргумент, промежуточный остаток, для этой цели (преобладающий первоначальный остаток параметра CRC).
Функции члена<reset>сбрасывают внутреннее состояние остатка CRC на заданное значение. Если значение не дано, то внутренний остаток устанавливается на начальное оставшееся значение при создании объекта. Остальное должно быть не отражено. Когда расчет CRC завершен, вызов<reset>позволяет повторно использовать объект для нового сеанса.
После любой конструкции оба компьютера CRC работают одинаково. Подача новых данных на компьютер осуществляется отдельной операцией (операциями) по извлечению текущего значения CRC с компьютера. В следующей таблице перечислены операции по кормлению и извлечению.
Regular CRC Operations
Operation
Description
<void process_bit( bool bit );>
Подает одиночныйбитна компьютер, обновляя промежуточный CRC. Он предназначен только для медленного компьютера CRC.
Действует как применение<process_bit>к наименьшемубитубиту, приведенному вбите, наиболее значимому соответствующему биту первым. Результаты не определены, еслибит_счетпревышает количество бит на байт. Он предназначен только для медленного компьютера CRC.
<void process_byte( unsigned char byte );>
Применяется<process_bit>для всех битовбайт. Если отражение не желательно, биты подаются от наиболее до наименее значимых. Биты подаются в противоположном порядке, если требуется отражение.
Действует как приложение<process_byte>к каждому байту в данном блоке памяти. Этот блок памяти начинается сбайт_началаи заканчивается добайт_конца. Байты обрабатываются в таком порядке.
Действует как приложение<process_byte>к каждому байту в данном блоке памяти. Этот блок памяти начинается сбуфераи длится длябайт_счетабайтов. Байты обрабатываются в порядке возрастания.
<value_type checksum() const;>
Возвращает контрольную сумму CRC данных, переданных до сих пор, возможно, после применения остаточных отражений и исключительных операций.
<void operator ()( unsigned char byte );>
Звонки<process_byte>. Эта функция позволяет своему объекту действовать как (состоятельный) объект функции. Он предназначен только для быстрого компьютера CRC.
<value_type operator ()() const;>
Звонки<checksum>. Эта функция позволяет своему объекту действовать как объекту функции генератора. Он предназначен только для быстрого компьютера CRC.
Вы можете использовать их так:
#include <boost/crc.hpp> // for boost::crc_basic, boost::crc_optimal
#include <boost/cstdint.hpp> // for boost::uint16_t
#include <algorithm> // for std::for_each
#include <cassert> // for assert
#include <cstddef> // for std::size_t
#include <iostream> // for std::cout
#include <ostream> // for std::endl
// Main function
int
main ()
{
// This is "123456789" in ASCII
unsigned char const data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
0x38, 0x39 };
std::size_t const data_len = sizeof( data ) / sizeof( data[0] );
// The expected CRC for the given data
boost::uint16_t const expected = 0x29B1;
// Simulate CRC-CCITT
boost::crc_basic<16> crc_ccitt1( 0x1021, 0xFFFF, 0, false, false );
crc_ccitt1.process_bytes( data, data_len );
assert( crc_ccitt1.checksum() == expected );
// Repeat with the optimal version (assuming a 16-bit type exists)
boost::crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt2;
crc_ccitt2 = std::for_each( data, data + data_len, crc_ccitt2 );
assert( crc_ccitt2() == expected );
std::cout << "All tests passed." << std::endl;
return 0;
}
Шаблон функции<boost::crc>вычисляет CRC данного блока данных. Блок данных начинается по адресу, указанному буфером, и продолжается длябайт_счетабайтов. Параметры CRC передаются через шаблонные аргументы, идентичные оптимизированному компьютеру CRC (см. выше). По сути, для реализации этой функции используется такой компьютер.
Все остальные CRC-вычислительные функции или шаблоны классов работают, предполагая, что этапы деления начинаются немедленно на первых битах сообщения. Два<boost::augmented_crc>шаблона функций имеют различный порядок деления. Вместо того, чтобы комбинировать (78) черезбит эксклюзивного бита текущего сообщения с самым высоким битом отдельного остатка, эти шаблоны перемещают новый бит сообщения в низкий бит регистра остатка, поскольку самый высокий бит смещается. Новый метод означает, что биты в исходном остаточном значении обрабатываются до обработки любого из фактических битов сообщения. Чтобы компенсировать это, реальный CRC может быть извлечен только после подачи достаточного количества нулевых битов (то же количество, что и размер регистра) после битов сообщения.
Параметрами шаблона обеих версий шаблона функций являются размер бита CRC<Bits>и усеченный полиномиальный<TruncPoly>. Версия шаблона функции, которая принимает два аргумента, называет версию с тремя аргументами с параметромinitial_remainderзаполненным как ноль. Обе версии работают на блоке данных, начинающемся по адресубуфердлябайт_счетабайтов.
Эти шаблоны функций полезны, если байты CRC непосредственно следуют байтам сообщения. Во-первых, установите байты, где CRC будет идти к нулю. Затем используйте<augmented_crc>над дополненным сообщением,то естьбайтами сообщения и прилагаемыми байтами CRC. Затем присвоить результат КПР. Для последующей проверки принятого сообщения либо используйте<augmented_crc>(с теми же параметрами, что и передача, конечно) на принятомне дополненномсообщении и проверьте, равен ли результат CRC, либо используйте<augmented_crc>на принятомдополненномсообщении и проверьте, равен ли результат нулю. Обратите внимание, что CRC должен сначала храниться с более значительными байтами (биг-эндиан).
Перерывы в данных CRC могут быть обработаны путем подачи результата<augmented_crc>предыдущего блока данных в качествеinitial_remainderпри вызове<augmented_crc>на следующем блоке данных. Помните, что фактический CRC можно определить только после подачи дополненных байтов. Поскольку этот метод использует модуль-2 полиномиальное деление в самом сыром виде, ни конечные значения XOR, ни отражение не могут быть использованы.
Обратите внимание, что для той же системы CRC начальный остаток для метода дополненного сообщения будет отличаться от метода не дополненного сообщения. Основным исключением является ноль; если алгоритм дополненного CRC использует нулевой начальный остаток, эквивалентный алгоритм не дополненного CRC также будет использовать нулевой начальный остаток. Учитывая первоначальный остаток для алгоритма с расширенным CRC, результат обработки только нулевых байтов CRC без байтов сообщений является эквивалентным исходным остатком для алгоритма с не дополненным CRC. Ниже приводится пример:
#include <boost/crc.hpp> // for boost::crc_basic, boost::augmented_crc
#include <boost/cstdint.hpp> // for boost::uint16_t
#include <cassert> // for assert
#include <iostream> // for std::cout
#include <ostream> // for std::endl
// Main function
int
main ()
{
using boost::uint16_t;
using boost::augmented_crc;
uint16_t data[6] = { 2, 4, 31, 67, 98, 0 };
uint16_t const init_rem = 0x123;
uint16_t crc1 = augmented_crc<16, 0x8005>( data, sizeof(data), init_rem );
uint16_t const zero = 0;
uint16_t const new_init_rem = augmented_crc<16, 0x8005>( &zero, sizeof(zero) );
boost::crc_basic<16> crc2( 0x8005, new_init_rem );
crc2.process_block( data, &data[5] ); // don't include CRC
assert( crc2.checksum() == crc1 );
std::cout << "All tests passed." << std::endl;
return 0;
}
Приведены четыре типа выборки CRC, представляющие несколько общих алгоритмов CRC. Например, вычисления из<boost::crc_32_type>могут быть использованы для реализации стандарта PKZip. Обратите внимание, что в целом эта библиотека занимается реализацией CRC, а не определением наборов параметров CRC.
Common CRCs
Algorithm
Example Protocols
<crc_16_type>
Бисинч, Арч
<crc_ccitt_type>
CCITT (Comité Consultatif International Télégraphique et Téléphonique)
Авторское право 2001, 2003 Дэрил Уокер. Использование, модификация и распространение регулируются Лицензией на программное обеспечение Boost версии 1.0. (См. сопроводительный файлLICENSE_1_0.txtили копию по адресу<) http://www.boost.org/LICENSE_1_0.txt>
Статья Boost CRC Library Documentation раздела может быть полезна для разработчиков на c++ и boost.
