Могущество кодов Рида-Соломона или информация, воскресшая из пепла
Энтропия слепа, но терпелива. Рано или поздно, обстреливая наши позиции по квадратам, она нанесет удар по штабу, по центру связи. И тогда первая линия обороны будет уничтожена. И приходится отходить на запасные позиции. Иными словами, доставать из магнитотеки пакет дисков с копией тома.
Е. В. Лишак
"Тридцать второй день года.
(Записки парасистемного программиста)."
Все вы наверняка слышали о существовании помехозащитных кодов Рида-Соломона, широко использующихся в устройствах передачи и хранения данных для обнаружения и исправления как одиночных, так и групповых (!) ошибок. Область их применения необычайно широка — кодеры/декодеры Рида-Соломона можно найти и в ленточных запоминающих устройствах, и контроллерах оперативной памяти, и в модемах, и в жестких дисках, и в приводах CD-ROM/DVD приводах и т. д. Благодаря им некоторые "продвинутые" архиваторы безболезненно переносят порчу нескольких секторов носителя, содержащего архив, а подчас — и полное разрушение целого тома многотомного архива. Еще коды Рида-Соломона позволяют защитному механизму автоматически восстанавливать байтики, "хакнутые" взломщиком и/или искаженные в результате сбоя программного/аппаратного обеспечения.
Короче говоря, если владение техникой помехозащитного кодирования не превращает вас в бога, то, по крайней мере, поднимает на Олимп, где среди бесшумных вентиляторов и "безглючных" операционных систем снуют великие компьютерные Гуру.
В тоже время, лишь немногие программисты могут похвастаться собственной реализацией алгоритмов Рида-Соломона. Да и зачем? Готовых библиотек море — от прагматичных коммерческих пакетов, до бесплатных "исходников", распространяемых по лицензии GNU[n2k56] [Y57] . Как говориться, бери — не хочу.
Замечание
"…из-за ошибок в реализации данный код вместо исправления ошибок добавляет новые. Поэтому данный код больше недоступен" — комментарий к исходным текстам GNU'шным[n2k58] исходным текстам кодера/декодера Reed-Solomon'a'а GNU.
Вот и верь после этого в надежность Linux в целом и в "GNU-'тый" библиотечный код в частности.
Что ж, в использовании библиотек есть вполне определенный практический смысл, но никакой хакер (hacker) [n2k59] не доверит управления программе, до тех пор не поймет как именно она работает (а эта публикация именно для хакеров и предназначена, естественно "хакеров" в хорошем значении этого слова). С другой стороны, — при анализе программного обеспечения, распространяемого без исходных кодов, вы не сможете идентифицировать алгоритм Рида-Соломона, если только заранее не разберетесь во всех его тонкостях. Допустим, вам встретилась защита, хитрым образом манипулирующая с EDC/ECC полями ключевых секторов, считанных ею с лазерного диска, и каждый такой сектор содержит две умышленно внесенные ошибки (плюс еще ошибки, естественным путем возникающие при небрежном обращении с CD), причем, одна из этих ошибок ложная
и исправлять ее не нужно. При штатном копировании защищенного диска микропроцессорная начинка привода CD-ROM'a'а автоматически исправляет все ошибки, которые она только может исправить, в результате чего происходит искажение ключевых меток и, — как следствие — защищенная программа перестанет работать. Можно, конечно, скопировать диск в "сыром" режиме, т. е. без исправления ошибок, но тогда копия будет содержать как не предумышленные, так и предумышленные ошибки, в результате чего даже при незначительном повреждении оригинала, корректирующих возможностей кодов Рида-Соломона уже окажется недостаточно и диск просто перестанет читаться (А как вы хотели? Копирование дисков в сыром режиме ведет к накоплению
ошибок и потому крайне непрактично с любой точки зрения). Владение базовыми принципами помехозащитного кодирования позволит вам разобраться с логикой работы защитного механизма и понять какие конкретного ошибки следует исправлять, а какие нет.
К сожалению, подавляющее большинство публикаций на тему кодов Рида-Соломона написаны на языке высшей математики для постижения которой и университетских знаний под час оказывается недостаточно (да и все ли хакеры знают математику?), в результате чего все эти сильно теореитиизированные руководства забрасываются на полку, если вообще не применяются не по назначению…отправляются в туалет (не то, чтобы я разделял такие намерения, но все-таки…).
Программная реализация корректирующих кодов Рида-Соломона действительно очень сложна и действительнона самом деле требует определенной математической подготовки, изложение основ которой может показаться скучным и неинтересным для "системщиков" и "железячников", но иного пути по- видимому нет. В конце концов, никто не обещал вам, что быть программистом — легко, а хорошим программистом быть еще труднее. Так что не говорите потом, что я вас не предупреждал! Шутка! РасслабитесьРасслабьтесь и разгоните свой страх перед высшей математикой прочь. По ходу описания вам встретьсяповстречается пара формул (ну куда же в математике без формул?), но во всех остальных случаях я буду говорить на интернациональном программистом языке — языке Си, понятным любому системщику. В общем, пристегивайте ремни и поднимайте свои головы с клавиатуры, — мы поехали!
