Магия чисел, или Детективная история о нечитаемых компакт-дисках

Предыстория

Вся эта история началась с того, что моему коллеге Растегаеву Сергею «посчастливилось» испортить 3 болванки, когда он безуспешно пытался записать видеофайл, скачанный по сети. Видеофильм этот был записан на 3 CD-R-диска Verbatim Datalife Plus, верификация в программе Nero Burning Rom заканчивалась провалом на всех трёх дисках в одном и том же месте. При попытке скопировать файл на жёсткий диск происходила ошибка чтения диска на 78-ом проценте. Болванки были хорошие, с другими файлами проблем не было, на других компьютерах с другими устройствами записи повторялось то же самое – это было очень странно. Я заинтересовался загадкой и решил вплотную заняться изучением проблемы.

Начало расследования

Первым делом я открыл видеофайл и посмотрел, что же находится на 78-ом проценте. Файл в этом месте был испорчен, изображение рассыпалось – файл был повреждён. Я вылечил битое место при помощи VirtualDub. Записал на CD вылеченную версию, рядом с ней повреждённую. Результат: исправленная версия читается хорошо, битая версия выдаёт ошибку чтения. Стало ясно только одно: либо на читаемость, либо на записываемость файла каким-то невероятным образом влияют те данные, которые в нём содержатся. Так как я не знал точно, существует ли уже объяснение описанной проблемы, я поискал информацию по данной теме в интернете и, не найдя ничего подходящего, решил обратиться к специалистам, посещающим forum.ixbt.com. Оказалось, что с этой проблемой некоторые сталкивались, но никто до сих пор не отнёсся к ней серьёзно, поэтому наряду с некоторой степенью недоверия интерес к загадке рос очень быстро. Всем желающим убедиться в том, что существует последовательность байтов, которая не может быть корректно прочитана после записи, был разослан фрагмент видеофайла, содержащий «волшебные» данные badvideo.avi. Все желающие принялись тестировать чтение и запись странного фрагмента, используя различное программное и аппаратное обеспечение. Это был важный этап, так как пока не было точно известно, является ли проблема программной или аппаратной.

Первые версии

Первые тесты дали очень интересные результаты.

1. Битый файл некоторые марки приводов читают без ошибок (см. таблицу). Таким образом, раз не все приводы выдают ошибку чтения, то вероятно, что проблема не в записи данных, хотя это ещё надо было проверять.

2. Читаемость файла с загадочными данными зависит от режима, в котором производится запись. Если файл записан в формате Mode 1, он не читается, а если в формате Mode 2/XA или UDF, – читается.

C самого начала обсуждения участник abgm предложил первую версию, что на этапе EFM-кодирования возможна неоднозначность кодирования данных.

Справка :

«EFM-кодирование – это кодирование с использованием избыточного кода 8/14 (Eight to Fourteen Modulation — EFM), в котором исходные байты кодируются 14-битными словами, повышающими помехозащищённость из-за введения избыточности, кроме того достигается аппаратная компрессия данных, хранящихся на компакт-диске. Между 14-битными словами вставляется по три связующих бита для соблюдения ограничений на количество смежных нулей и единиц, что облегчает синхронизацию и уменьшает постоянную составляющую сигнала (DSV), т.к. привод синхронизируется по фронтам перехода от пита к ленду и от ленда к питу. Если расстояние между двумя такими переходами будет излишне большим, то привод может потерять синхронизацию из-за неидеальной стабильности вращения диска.»

abgm привёл цитату из Andy McFadden's CD-Recordable FAQ: «Если существует больше одной возможности для размещения объединяющих битов, удовлетворяющего требованиям длины участков и синхрогрупп, тогда используется синхрогруппа, минимизирующая низкочастотные составляющие сигнала. Это достигается снижением до минимума значения цифровой суммы (DSV), которая рассчитывается путем прибавления единицы к каждому времени T после перехода из углубления к плоскому участку или путем вычитания единицы из каждого Т после перехода к углублению. Добавление единицы к объединяющим битам инвертирует сигнал, вызывая переход от углубления к плоскому участку или наоборот. Снижение до минимума DSV имеет большое значение, поскольку низкочастотные сигналы могут помешать правильной фокусировке лазера и его позиционированию на дорожке. (Предположительно, такие сигналы мешают поиску отсчетов на спиральной дорожке записываемого диска)».

Таким образом, возникло предположение, что существуют последовательности данных, которые допускают потерю синхронизации приводом по записанному сигналу. Такие последовательности действительно существуют – это так называемые weak-сектора, принцип действия которых основан именно на нарушении DSV. Проверка версии №1 требовала глубокого изучения технологии кодирования сигнала на CD, а доступной документации пока не хватало, чтобы однозначно подтвердить или опровергнуть эту версию.

Вместе с обнаружением того факта, что файл, записанный на CD в формате Mode 2/XA, читается без ошибок, возникла и вторая версия. Так как данные обнаружения и исправления ошибок EDC/ECC (error correction code и error detection code) в форматах Mode 1 и Mode 2/XA.

Mode 1


Mode 2/XA


вычисляются с некоторыми отличиями, то возникло предположение, что существует ошибка в алгоритме вычисления EDC/ECC, проявляющаяся для некоторых последовательностей данных, записанных в режиме Mode 1.

Версию №2 проверить было относительно просто, так как существующее программное обеспечение позволяет прочитать RAW-данные секторов и программным путём рассчитать и проверить EDC/ECC. Сканирование диска с файлом на нечитающем приводе производства LiteOn в программах CDDoctor и KProbe не выявило ошибок. Так как данные программы работают с диском на низком уровне, это склоняло некоторых участников к версии об ошибке уровня EDC/ECC. Но тестирование RAW-чтения с игнорированием EDC/ECC-ошибок при помощи таких программ, как CloneCD, на нечитающих приводах всё равно приводило к появлению ошибок чтения секторов. Это свидетельствовало, что ошибка лежит не на уровне вычисления EDC/ECC. При этом на разных приводах ошибки чтения секторов отличались.

Ну и, разумеется, нельзя было исключать версию №3: ошибки в программном обеспечении, в частности, в программах записи или драйверах устройств. Чтобы проверить версию №3, нужно было протестировать чтение и запись с разными версиями драйверов, различными программами записи, а также в операционных системах не из семейства Windows. Участники продолжили тестирование и установили, что в общем случае читаемость странного файла не зависит от того, каким приложением производилась запись, при условии, что запись производилась в Mode 1. Читаемость также не зависела от метода записи: Track-At-Once, Disk-At-Once или Disk-At-Once 96. Ошибка повторилась и в операционной системе Linux. Таким образом, ответственность с разработчиков Nero также можно было снять.

Немного позже Алексей Полукаров (aka ANPolter) предложил четвёртую версию, что отдельные приводы могут воспринимать поцарапанные участки диска как последовательности какого-то EFM-кода, в котором количество нулей превалирует над количеством единиц (есть в таблице такие коды), и успешно пытаются декодировать их в пользовательские данные. При записи данных обратно на CD получаются неверно воспринятые EFM-коды. И получается некоторое подобие weak-сектора. Именно на таком приводе, по мнению Алексея, и был изначально прочитан CD, содержащий исходный видеофайл.

Мысль была интересная, но она была оспорена участниками обсуждения. Главным аргументом против версии о длинной последовательности нулей на диске было то, что в процессе EFM-кодирования не должно было создаваться ситуации, при которой длина последовательности нулей была бы больше десяти из-за «разрежающих» согласующих трёх бит. Но weak-сектора существуют и работают, поэтому полностью отвергнуть эту версию тоже было нельзя. Против прозвучавшего в версии Алексея Полукарова предположения о том, что “волшебная” последовательность данных прочитана с повреждённого носителя, никто возражать не стал. Возможно, это предположение имело право на жизнь, и мы дальше посмотрим, могло ли так быть на самом деле.

Сигнатуры

Итак, у нас было уже несколько версий. Чтобы окончательно проверить все высказанные версии и однозначно определить их право на жизнь, необходимо было провести математические преобразования над данными и посмотреть, что получается на выходе алгоритма преобразования, но для этого надо было выделить пакет данных, влияющих на читаемость диска. Я взялся за детальное исследование содержимого нечитаемого фрагмента файла.

Первым делом мегабайтный фрагмент был разрезан на 2-килобайтные фрагменты (по секторам), и фрагменты эти записаны последовательно. Я обратил внимание, что сектора не читаются парами. Значит, либо последовательность байтов лежит на границе двух секторов, либо нечитаемость одного сектора вызывает нечитаемость другого.

Увеличив размер фрагмента до 4 Кб, мне удалось отделить фрагменты, которые по одиночке читаются. В этих файлах мне и предстояло искать магические последовательности. Для этого была написана несложная программа, на вход которой подаётся 4-килобайтный фрагмент, а на выходе получается набор файлов, в которые байт за байтом проецируется содержимое входного фрагмента. Записав все эти файлы на CD-RW, я смог без труда установить, в какой момент начинается и в какой заканчивается последовательность байтов, определяющая нечитаемость файла. Бинго! Таким образом, я нашёл первую сигнатуру, начинающуюся с 8-го байта от начала файла (нумерация с нуля): A8 FD 01 7E 7F 9F 9F D7 D7 E1 61 88. Далее я решил проверить, влияет ли местоположение найденной сигнатуры на читаемость файла, создав ещё 4096 файлов, каждый раз сдвигая сигнатуру на 1 байт. Тестирование показало, что сигнатура действует в точно определённом месте сектора.

Применение этой последовательности на любом секторе любого файла приводило к стабильной нечитаемости файла на нечитающих приводах (см. таблицу). Т.е. начало 2048-байтного сектора внутри файла, содержащего сигнатуру и приводящего к сбою чтения, выглядит так:

XX XX XX XX XX XX XX XX A8 FD 01 7E 7F 9F 9F D7 
D7 E1 61 88 XX XX XX XX XX XX XX XX XX XX XX XX

Несколько позже, продолжая просеивать исходный файл, я смог обнаружить ещё несколько сигнатур, обладающих такими же характеристиками, как и первая найденная:

  • Все найденные сигнатуры имеют длину 12 байт. Если посмотреть на формат сектора (рис. 1), то видно, что длину 12 байт имеет также синхрозаголовок сектора (Sync).
  • Сигнатура «действует» только в точно определённом месте сектора.
  • Все найденные сигнатуры начинаются с адреса, кратного 8.

Детально исследуя записанные данные, я выяснил, что на приводе Teac CD-W524 сигнатура не сказывается на читаемости сектора, в котором она находится, но вызывает нечитаемость следующих двух секторов (именно поэтому сектора не читались парами). Но один из участников тестирования вскоре обнаружил, что на приводе Sony CRX-225E не читается сектор, содержащий сигнатуру, но соседние сектора читаются нормально. Эта информация означала то, что на нечитающие приводы разных производителей сигнатура оказывает разное влияние. Это косвенно подтверждало высказанную ранее мысль о том, что привод, возможно, теряет синхронизацию из-за какого-то сочетания факторов.

C помощью программы weak_detector, которая ищет weak-сектора в ISO-образах и на CD, был протестирован ISO-образ, содержащий badvideo.avi, созданный при помощи программы WinISO. Программа weak_detector там ошибок не нашла. Затем ISO-образ был записан на CD-RW, и получился нечитаемый файл. Это показывало, что найденные сигнатуры не имеют отношения к последовательностям, применяемым для создания weak-секторов. К тому же последовательности для создания weak-секторов гораздо длиннее 12 байт.

Тесты с другими операционными системами и пишущими программами ещё раз доказали, что читаемость файла с сигнатурами не зависит ни от устройства, на котором была произведена запись, ни от типа носителя, ни от программы записи, но зависит лишь от устройства, которое данные читает.

Бинго!

Казалось, что мы ходим вокруг да около. Все тестирования давали интересные результаты, но не могли пролить свет на причину проблемы. Обратив внимание на моё открытие, что сигнатура «действует» в точно определённом месте сектора, всё тот же Алексей Полукаров высказал одну любопытную мысль: “По-другому и быть не может, т.к. ей нужно пройти скрамблер. А вот после скрамблера все сигнатуры выглядят одинаково.”

В подтверждение своей догадки Алексей привёл очень показательный эксперимент. Если сравнить формат секторов CD в режимах Mode1 и Mode2/XA Form1, то видно, что начало пользовательских данных в секторе режима Mode2/XA Form1 смещено относительно Mode1 на 8 байт. Алексей сдвинул сигнатуру внутри файла на 8 байт так, чтобы начало 2048 сектора выглядело так:

A8 FD 01 7E 7F 9F 9F D7 D7 E1 61 88 XX XX XX XX 
XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX
Он записал файл в Mode 2/XA, и проблема была воспроизведена и в Mode 2/XA!

Давайте рассмотрим, что представляет из себя скрамблер.


Скрамблирование представляет собой операцию сложения по модулю 2 (или исключающее ИЛИ, что одно и то же) данных сектора с таблицей псевдослучайных чисел. Скрамблирование было введено для того, чтобы преобразовать регулярные последовательности чисел, которые часто встречаются в данных, в последовательность случайных чисел, и тем самым улучшить вероятностные характеристики выходного сигнала. Как вы уже, наверное, догадываетесь, у этой медали тоже есть вторая сторона, и в принципе возможно (хоть и маловероятно) стечение обстоятельств, при котором случайные пользовательские данные после скрамблера превратятся в однородный шаблон или даже в одну и ту же последовательность байтов.

Для решения загадки не хватало какой-то мелочи, надо было докопаться до природы проблемы, поэтому было необходимо программно повторить этапы преобразования данных и изучить результаты этих преобразований. Мысль Алексея про скрамблер была интересной и, возможно, таила в себе ключ к разгадке тайны. Её определённо стоило проверить.

Я написал небольшую функцию, преобразующую пользовательские данные с помощью скрамблера по тому же алгоритму, как это делается перед записью на CD, и пропустил все найденные файлы с сигнатурами через функцию. И на выходе нас ждал сюрприз. Все сигнатуры после скрамблера выглядели одинаково, как и предполагал Алексей Полукаров. Эта последовательность 00 FF FF FF FF FF FF FF FF FF FF 00 представляет собой ничто иное, как 12-байтный заголовок сектора Sync, который использовался для синхронизации и определения начала сектора в старых моделях CD-ROM. Как мы видим, многие самые современные модели CD-ROM(R/RW) и DVD-ROM(R/RW) также не брезгуют пользоваться морально устаревшим синхрозаголовком для определения начала сектора!

Таким образом, ошибка проявляется из-за того, что пользовательские данные после прохождения преобразования перед записью на компакт-диск превратились в ту же последовательность, которая является признаком начала сектора. И многие модели приводов не могут отличить ложный признак начала сектора от настоящего. Разгадка была так проста, что никто этого не ожидал. После обнаружения Алексей скажет: «Да-а-а-а-а, не думал я, что приводы до сих пор такие тупые. У меня сразу была такая мысль, но я её отбросил, т.к. прочитал, что заголовок сектора — вещь устаревшая и применялась только в первых CD-ROM, электроника которых была основана на чипах от аудиоаппаратов со сплошным потоком декодирования, а потому эту версию даже проверять не стал».

Если допустить, что привод ожидает начала фрейма с любой позиции, то возможно существование 2048 – 11 = 2037 сигнатур. Помимо этого необходимо учитывать, что сигнатура может возникнуть в данных EDC/ECC. Разработчики программ для записи могли бы очень легко написать функцию, проверяющую пользовательские данные перед записью на диск. Но слишком опасаться записи данных с сигнатурой не стоит.

Во-первых, если оценить вероятность попадания определённого числа длиной 12 байт в точно определённое место сектора, то оказывается, что эта вероятность ничтожно мала 1/(2^96)=1,3^-29. Если учитывать возможность существования около 2300 сигнатур в разных местах сектора, то вероятность появления ложных синхрозаголовков настолько мала (3^-25), что эта специфичная ошибка могла никогда не встретиться за всё время существования компакт-дисков. Наличие же нескольких сигнатур длиной 12 байт в одном файле косвенно подтверждает версию Алексея Полукарова о том, что последовательности оказались в файле при его чтении с повреждённого диска, иначе такое совпадение просто невероятно! Эта вероятность настолько мала, что гораздо больше вероятность повредить диск, чем встретить такие данные. Видимо, на это и рассчитывали разработчики приводов, сознательно (или бессознательно) допуская сбой синхронизации со столь малой вероятностью.

Во-вторых, наверняка всегда можно найти привод, на котором Вы сможете прочитать важные данные и сможете переписать их в другой формат (например, из Mode1 в Mode2/XA) или на другой носитель (например, DVD).

В дополнение к проведённым исследованиям участникам обсуждения стало интересно проверить, используют ли в принципе синхрозаголовок приводы, успешно прочитавшие мегабайтный фрагмент испорченного видеофайла. Для этого теста был сгенерирован 4-мегабайтный файл, целиком состоящий из сигнатур, сплошным потоком идущих друг за другом badfile.bin. Файл этот был записан и протестирован на нескольких приводах. Оказалось, что ряд приводов (например, Nec) не может прочитать badfile.bin в отдельности, но может прочитать при чтении образа диска. Очевидно, синхрозаголовок всё-таки используется ими в качестве вспомогательного маркера при поиске начала сектора, но не используется при последующем чтении. Другие приводы не смогли прочитать диск с badfile.bin вообще, что говорит о том, что синхрозаголовок ими тоже используется как вспомогательный, но в меньшей степени, чем приводами, которые вообще не читают файлы, содержащие даже одиночные сигнатуры. Были также и приводы, которые смогли прочесть badfile.bin без труда.

Заключение

Итак, налицо массовая экономия производителей железа на своих пользователях. Вышеописанной болезни подвержены устройства таких крупных производителей, как Teac, Sony (LiteOn), Plextor. Взгляните на таблицу. Более 2/3 протестированных приводов не могут прочитать файл, если его данные содержат сигнатуру, превращающуюся в последовательность данных, повторяющую Sync Header! За исключением Toshiba и HP, все производители в тех или иных устройствах попались на использовании синхрозаголовка как основного признака начала сектора при чтении данных. Такое отношение к данным пользователей заставляет с тревогой задуматься, а не напакостили ли производители ещё в чём-то, сэкономив на пользователях? Надеемся, что выход статьи изменит ситуацию к лучшему и подстегнёт производителей оптических устройств к скорейшему выпуску обновлений firmware, исправляющих найденную проблему.

По многочисленным просьбам читателей автор разработал утилиту, позволяющую проверять привод на способность чтения сигнатур. Утилиту можно взять здесь.


Автор выражает благодарность Марии Десятниковой за помощь в написании статьи.

Автор выражает благодарность всем, принявшим участие в обсуждении и тестировании на http://forum.ixbt.com/0031/017979.html, за помощь в разгадке тайны.



Юрий Малич (malich_y@mail.ru)
Алексей Полукаров (alexpolter@bee-s.com)
Опубликовано — 24 декабря 2003 г.
 
Комментарии?  Поправки?  Дополнения? srl@ixbt.com