Иногда возникает задача защитить строку-идентификатор от случайных ошибок, сделанных человеком. Например, номер платёжной карты. Для этого к строке добавляется вычисленная специальным образом контрольная цифра, и когда человек вводит этот номер, можно сделать первичную проверку на ошибки без обращения к базе данных. Самый простой вариант — добавить остаток от деления суммы всех цифр на 10, в таком случае искажение любой одной цифры (в том числе контрольной) будет легко обнаружить, и такая строка не пройдёт проверку. Но некоторые другие ошибки такая контрольная сумма пропустит, например, перестановку двух цифр местами, а это тоже довольно распространённая ошибка.
Читать полностью »
Рубрика «контрольная сумма»
Алгоритм Верхуффа для произвольной чётной системы счисления
2019-01-08 в 17:35, admin, рубрики: ECC, алгоритм Верхуффа, Алгоритмы, контрольная сумма, контрольная цифра, математикаНачнем с математики. Векторизация вычислений в реализации технологии RAID-6
2017-04-19 в 9:15, admin, рубрики: raid, raid6, Алгоритмы, Блог компании RAIDIX, высокая производительность, конечные поля, контрольная сумма, математика, поля галуа, системное программирование, системы хранения данных, СХД, хранение данныхМногие помнят публикацию о «Рэйдикс» на Хабре «Как разработчики сидели в Петербурге и тихо ели грибы», в которой партнеры кратко изложили историю появления нашего продукта. Поэтому в первой статье своего Хаброблога мы бы хотели погрузиться в математические основы технологий RAIDIX.
История одного бага: выравнивание данных на x86
2016-12-26 в 12:35, admin, рубрики: C, c++, gcc, sse, x86, выравнивание, заголовки IPv4, Компиляторы, контрольная сумма, обратный код, отладка, слишком умный компилятор, метки: выравниваниеОднажды мне пришлось вычислять сумму векторов целых чисел.
Звучит необычно. Кому понадобится делать это в реальной жизни? Обычно такие вычисления встречаются только в задачках из начальной школы или бенчмарках компилятора. Но сейчас это случилось на самом деле.
В реальности стояла задача проверить контрольную сумму заголовков IPv4, которая является суммой обратных кодов (дополнений до единицы) двухбайтных машинных слов. Проще говоря, это означает сложение всех слов и всех битов переноса, которые производятся в процессе. У этой процедуры есть несколько приятных особенностей:
- её можно эффективно выполнить с помощью процессорной инструкции
ADC
(к сожалению, эта функция недоступна в C); - её можно выполнить на словах любого размера (можете добавить по желанию восьмибайтные значения, только результат следует уменьшить до двух байт и добавить все биты переполнения);
- она нечувствительна к порядку следования байтов (удивительно, но это так).