Контрольная сумма Флетчера - это алгоритм для вычисления зависимой от позиции контрольной суммы, разработанный Джоном Г. Флетчером (1934–2012) в лаборатории Лоуренса Ливермора в конце 1970-х годов. Целью контрольной суммы Флетчера было обеспечить свойства обнаружения ошибок, приближающиеся к свойствам циклического контроля избыточности, но с меньшими вычислительными затратами, связанными с методами суммирования.
Как и в случае с более простыми алгоритмами контрольной суммы, контрольная сумма Флетчера включает разделение слова двоичных данных, которое необходимо защитить от ошибок, на короткие «блоки» битов и вычисление модульной суммы этих блоков. (Обратите внимание, что терминология, используемая в этой области, может сбивать с толку. Данные, подлежащие защите, целиком называются «словом», а части, на которые они делятся, называются «блоками».)
В качестве примера данные могут быть сообщением, которое должно быть передано, состоящим из 136 символов, каждый из которых хранится в виде 8-битного байта, что в сумме составляет слово данных из 1088 битов. Удобный размер блока - 8 бит, хотя это и не требуется. Точно так же удобный модуль будет 255, хотя, опять же, можно выбрать другие. Итак, простая контрольная сумма вычисляется путем сложения всех 8-битных байтов сообщения, деления на 255 и сохранения только остатка. (На практике операция по модулю выполняется во время суммирования для управления размером результата.) Значение контрольной суммы передается вместе с сообщением, увеличивая его длину до 137 байтов или 1096 бит. Получатель сообщения может повторно вычислить контрольную сумму и сравнить ее с полученным значением, чтобы определить, было ли сообщение изменено в процессе передачи.
Первая слабость простой контрольной суммы заключается в том, что она нечувствительна к порядку блоков (байтов) в слове данных (сообщении). При изменении порядка значение контрольной суммы будет таким же, и изменение не будет обнаружено. Вторая слабость заключается в том, что совокупность значений контрольной суммы мала и равна выбранному модулю. В нашем примере существует только 255 возможных значений контрольной суммы, поэтому легко увидеть, что даже случайные данные имеют примерно 0,4% вероятности иметь ту же контрольную сумму, что и наше сообщение.
Флетчер устраняет оба этих недостатка, вычисляя второе значение вместе с простой контрольной суммой. Это модульная сумма значений, принимаемых простой контрольной суммой при добавлении к ней каждого блока слова данных. Используемый модуль такой же. Таким образом, для каждого блока слова данных, взятого последовательно, значение блока добавляется к первой сумме, а новое значение первой суммы затем добавляется ко второй сумме. Обе суммы начинаются с нулевого значения (или другого известного значения). В конце слова данных применяется оператор модуля, и два значения объединяются для формирования значения контрольной суммы Флетчера.
Вводится чувствительность к порядку блоков, потому что, как только блок добавляется к первой сумме, он затем многократно добавляется ко второй сумме вместе с каждым блоком после нее. Если, например, происходит обмен двух соседних блоков, то тот, который изначально был первым, будет добавлен ко второй сумме на один меньше раз, а тот, который изначально был вторым, будет добавлен ко второй сумме еще раз. Конечное значение первой суммы будет таким же, но вторая сумма будет другой, обнаружив изменение в сообщении.
Вселенная возможных значений контрольной суммы теперь представляет собой квадрат значения простой контрольной суммы. В нашем примере две суммы, каждая из которых содержит 255 возможных значений, дают 65025 возможных значений для объединенной контрольной суммы.
Хотя существует бесконечное количество параметров, в исходной статье исследуется только случай K = 8 (длина слова) с модулем 255 и 256.
16- и 32-битные версии (Fletcher-32 и -64) были взяты из исходного случая и изучены в последующих спецификациях или статьях.
Когда слово данных делится на 8-битовые блоки, как в приведенном выше примере, получаются две 8-битные суммы, которые объединяются в 16-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 256 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 16-битное слово с простой контрольной суммой в наименее значимом конце. Затем этот алгоритм называется контрольной суммой Флетчера-16. Также обычно подразумевается использование модуля 2 8 - 1 = 255.
Когда слово данных делится на 16-битные блоки, получаются две 16-битные суммы, которые объединяются в 32-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 2 16 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 32-битное слово с простой контрольной суммой в наименее значимом конце. Затем этот алгоритм называется контрольной суммой Флетчера-32. Также обычно подразумевается использование модуля 2 16 - 1 = 65 535. Обоснование этого выбора такое же, как и для Fletcher-16.
Когда слово данных делится на 32-битные блоки, получаются две 32-битные суммы, которые объединяются в 64-битную контрольную сумму Флетчера. Обычно вторая сумма умножается на 2 32 и добавляется к простой контрольной сумме, эффективно складывая суммы бок о бок в 64-битном слове с простой контрольной суммой в наименее значимом конце. Затем этот алгоритм называется контрольной суммой Флетчера-64. Также обычно подразумевается использование модуля 2 32 - 1 = 4 294 967 295. Обоснование этого выбора такое же, как для Fletcher-16 и Fletcher-32.
Контрольная сумма Adler-32 - это специализация контрольной суммы Fletcher-32, разработанной Марком Адлером. Выбранный модуль (для обеих сумм) представляет собой простое число 65 521 (65 535 делится на 3, 5, 17 и 257). Первая сумма также начинается со значения 1. Выбор простого модуля приводит к улучшенному «смешиванию» (шаблоны ошибок обнаруживаются с более равномерной вероятностью, повышая вероятность того, что будут обнаружены наименее обнаруживаемые шаблоны, что имеет тенденцию доминировать в общей производительности.). Однако уменьшение размера совокупности возможных значений контрольной суммы действует против этого и немного снижает производительность. Одно исследование показало, что Fletcher-32 превосходит Adler-32 как по производительности, так и по способности обнаруживать ошибки. Поскольку сложение по модулю 65 535 значительно проще и быстрее в реализации, чем сложение по модулю 65 521, контрольная сумма Fletcher-32, как правило, является более быстрым алгоритмом.
Например, контрольная сумма Fletcher-16 должна быть вычислена и проверена для байтового потока 0x01 0x02.
Байт (B) | C0 = (C0 пред. + B) по модулю 255 | C1 = (C1 пред. + C0) по модулю 255 | Описание |
---|---|---|---|
0x01 | 0x01 | 0x01 | Введен первый байт |
0x02 | 0x03 | 0x04 | Второй байт введен |
Таким образом, контрольная сумма равна 0x0403. Он может быть передан с потоком байтов и проверен как таковой на принимающей стороне. Другой вариант - вычислить на втором этапе пару контрольных байтов, которые могут быть добавлены к байтовому потоку, чтобы результирующий поток имел глобальное значение контрольной суммы Fletcher-16, равное 0.
Значения контрольных байтов вычисляются следующим образом:
где C0 и C1 - результат последнего шага вычисления Fletcher-16.
В нашем случае байты контрольной суммы CB0 = 0xF8 и CB1 = 0x04. Передаваемый поток байтов - 0x01 0x02 0xF8 0x04. Получатель вычисляет контрольную сумму всех четырех байтов и вычисляет проходящую контрольную сумму 0x00 0x00, как показано ниже:
Байт (B) | C0 = (C0 пред. + B) по модулю 255 | C1 = (C1 пред. + C0) по модулю 255 | Описание |
---|---|---|---|
0x01 | 0x01 | 0x01 | Введен первый байт |
0x02 | 0x03 | 0x04 | Второй байт введен |
CB0 = 0xF8 | (0x03 + 0xF8)% 0xFF = 0xFB | (0x04 + 0xFB)% 0xFF = 0x00 | Расчет контрольной суммы - байт 1 |
CB1 = 0x04 | (0xFB + 0x04)% 0xFF = 0x00 | (0x00 + 0x00)% 0xFF = 0x00 | Расчет контрольной суммы - байт 2 |
Контрольная сумма Флетчера не может различить блоки всех 0 битов и блоки всех 1 битов. Например, если 16-битный блок в слове данных изменяется с 0x0000 на 0xFFFF, контрольная сумма Fletcher-32 остается прежней. Это также означает, что последовательность всех байтов 00 имеет ту же контрольную сумму, что и последовательность (того же размера) всех байтов FF.
Эти примеры предполагают арифметику дополнения до двух, поскольку алгоритм Флетчера будет неправильным на машинах с дополнением до двух.
Ниже описано, как вычислить контрольную сумму, включая контрольные байты; т. е. окончательный результат должен быть равен 0 с учетом правильно рассчитанных контрольных байтов. Однако сам по себе код не будет вычислять контрольные байты.
Ниже приводится неэффективная, но простая реализация функции языка C для вычисления контрольной суммы Fletcher-16 для массива 8-битных элементов данных:
uint16_t Fletcher16( uint8_t *data, int count) { uint16_t sum1 = 0; uint16_t sum2 = 0; int index; for ( index = 0; index lt; count; ++index) { sum1 = (sum1 + data[index]) % 255; sum2 = (sum2 + sum1) % 255; } return (sum2 lt;lt; 8) | sum1; }
В строках 3 и 4 суммы представляют собой 16-разрядные переменные, поэтому сложения в строках 9 и 10 не будут переполняться. Операция по модулю применяется к первой сумме в строке 9 и ко второй сумме в строке 10. Здесь это делается после каждого сложения, так что в конце цикла for суммы всегда уменьшаются до 8 бит. В конце входных данных две суммы объединяются в 16-битное значение контрольной суммы Флетчера и возвращаются функцией в строке 13.
Каждая сумма вычисляется по модулю 255 и, таким образом, всегда остается меньше 0xFF. Таким образом, эта реализация никогда не выдаст результаты контрольной суммы 0x ?? FF, 0xFF ?? или 0xFFFF (т. е. 511 из 65536 возможных 16-битных значений никогда не используются). Он может выдать результат контрольной суммы 0x0000, что может быть нежелательно при некоторых обстоятельствах (например, когда это значение было зарезервировано для обозначения «контрольная сумма не была вычислена»).
Пример исходного кода для вычисления контрольных байтов с использованием указанной выше функции выглядит следующим образом. Контрольные байты могут быть добавлены в конец потока данных, причем c0 следует перед c1.
uint16_t csum; uint16_t c0,c1,f0,f1; csum = Fletcher16(data, length); f0 = csum amp; 0xff; f1 = (csum gt;gt; 8) amp; 0xff; c0 = 0xff - ((f0 + f1) % 0xff); c1 = 0xff - ((f0 + c0) % 0xff);
В статье 1988 года Анастасий Накассис обсудил и сравнил различные способы оптимизации алгоритма. Самая важная оптимизация заключается в использовании аккумуляторов большего размера и отложении относительно дорогостоящей операции по модулю до тех пор, пока можно доказать, что переполнения не произойдет. Дополнительную выгоду можно получить, заменив оператор по модулю эквивалентной функцией, адаптированной для этого конкретного случая, например, простым сравнением и вычитанием, поскольку частное никогда не превышает 1.
Вот реализация C, которая применяет первую, но не вторую оптимизацию:
#include lt;stdlib.hgt; /* for size_t */ #include lt;stdint.hgt; /* for uint8_t, uint16_t amp; uint32_t */ uint16_t fletcher16(const uint8_t *data, size_t len) { uint32_t c0, c1; /* Found by solving for c1 overflow: */ /* n gt; 0 and n * (n+1) / 2 * (2^8-1) lt; (2^32-1). */ for (c0 = c1 = 0; len gt; 0;) { size_t blocklen = len; if (blocklen gt; 5002) { blocklen = 5002; } len -= blocklen; do { c0 = c0 + *data++; c1 = c1 + c0; } while (--blocklen); c0 = c0 % 255; c1 = c1 % 255; } return (c1 lt;lt; 8 | c0); } uint32_t fletcher32(const uint16_t *data, size_t len) { uint32_t c0, c1; len = (len + 1) amp; ~1; /* Round up len to words */ /* We similarly solve for n gt; 0 and n * (n+1) / 2 * (2^16-1) lt; (2^32-1) here. */ /* On modern computers, using a 64-bit c0/c1 could allow a group size of 23726746. */ for (c0 = c1 = 0; len gt; 0;) { size_t blocklen = len; if (blocklen gt; 360*2) { blocklen = 360*2; } len -= blocklen; do { c0 = c0 + *data++; c1 = c1 + c0; } while ((blocklen -= 2)); c0 = c0 % 65535; c1 = c1 % 65535; } return (c1 lt;lt; 16 | c0); } // A similar routine could be written for fletcher64. The group size would be 92681.
Вторая оптимизация не используется, потому что предположение «никогда не превышает 1» применимо только тогда, когда модуль вычисляется наивно; применение первой оптимизации сломало бы его. С другой стороны, числа Мерсенна по модулю, такие как 255 и 65535, в любом случае являются быстрой операцией на компьютерах, поскольку существуют уловки, позволяющие сделать их без дорогостоящей операции деления.
8-битная реализация (16-битная контрольная сумма)
"abcde" -gt; 51440 (0xC8F0) "abcdef" -gt; 8279 (0x2057) "abcdefgh" -gt; 1575 (0x0627)
16-битная реализация (32-битная контрольная сумма), с 8-битными значениями ASCII входного слова, собранными в 16-битные блоки в обратном порядке, слово дополняется нулями по мере необходимости до следующего целого блока с использованием модуля 65535 и с результатом, представленным как сумма сумм, сдвинутая влево на 16 бит (умноженная на 65536), плюс простая сумма
"abcde" -gt; 4031760169 (0xF04FC729) "abcdef" -gt; 1448095018 (0x56502D2A) "abcdefgh" -gt; 3957429649 (0xEBE19591)
32-битная реализация (64-битная контрольная сумма)
"abcde" -gt; 14467467625952928454 (0xC8C6C527646362C6) "abcdef" -gt; 14467579776138987718 (0xC8C72B276463C8C6) "abcdefgh" -gt; 3543817411021686982 (0x312E2B28CCCAC8C6)
Как и при любом вычислении, которое делит слово двоичных данных на короткие блоки и обрабатывает блоки как числа, любые две системы, ожидающие получения одного и того же результата, должны сохранять порядок битов в слове данных. В этом отношении контрольная сумма Флетчера не отличается от других алгоритмов контрольной суммы и CRC и не требует специального объяснения.
Проблема упорядочения, которую легко представить, возникает, когда слово данных передается побайтно между системой с прямым порядком байтов и системой с прямым порядком байтов и вычисляется контрольная сумма Fletcher-32. Если блоки извлекаются из слова данных в памяти путем простого чтения 16-разрядного целого числа без знака, то значения блоков будут разными в двух системах из-за обратного порядка байтов 16-разрядных элементов данных. в памяти, и, как следствие, результат контрольной суммы будет другим. В приведенных выше примерах реализации не рассматриваются вопросы упорядочивания, чтобы не затруднять понимание алгоритма контрольной суммы. Поскольку контрольная сумма Fletcher-16 использует 8-битные блоки, на нее не влияет порядок байтов.
|journal=
( помощь )