Три переезда равно одному пожару. Выгребая старый ящик, пропахший ацетоном, с многослойной пылью на донышке (как хорошо, что жена не видела) я наткнулся на до боли знакомые мне компакт диски. Вот один из любимых фильмов детства… а вот моя когда-то любимая аркадная игрушка…
Странная вещь — любопытство. Вот на столе экземпляр CD — безнадёжно устаревшего в наш просвященный XXI век формата хранения данных; а все таки интересно, как же там хранятся данные?.. Каков сам стек хранения данных?.. Как исправляются ошибки?.. Какова избыточность кода?..
В детстве мне было достаточно знаний о лазерном луче, о какой-то головке, об «этой крутящийся штуки» и о таинственных питах.
Сказано — сделано. Проглядев стандарт ECMA-130 (есть, кстати и отечественный стандарт: ГОСТ 27667-88) обнаружил массу любопытных деталей. Например, я догадывался об избыточности, но я и подумать не мог, что для записи 700 Мб данных «в реальности» записывается 1943 Мб (То есть в 2.776 раз больше)…
Схематично весь стек можно представить картинкой:
Стек рассмотрим «сверху вниз».
То есть от момента передачи данных приводу до записи самих питов.
Следует сказать, что не вся область диска используется для записи/хранения/чтения информации.
Компакт диск разделен на зоны (areas):
- Centre Hole (Центральное отверстие ) — это «та самая дырочка» диаметром 15 мм (±0.1 мм), за которую прикрепляется сам диск.
- First transition area (Первая переходная зона) — «кольцо», между 15 и 20 мм от центра диска.
- Сlamping area (Зона зажима) — как понятно из названия это область необходима, чтобы диск «не скакал» при чтении / записи. (26-33 мм)
- Second transition area (Вторая переходная зона) — «второе кольцо», между 33 и 44 мм от центра диска.
- Information area (Зона информации) — это «информационно полезная» часть компакт диска. Находится на расстоянии от 44 мм до 118 мм от центра.
- Rim area (обод) — последняя область. Представляет собой кольцо от 118 мм до 120 мм от центра.
Именно зона информации нам и интересна, поэтому о ней скажем более подробно. Information area разделяется на следующие «подзоны»:
- inner buffer zone (зона ввода)
- user data zone (зона программы)
- outer buffer zone (зона вывода)
Все три перевода сделаны ГОСТом… Так что от себя переводить не буду. При чем здесь «программа», когда речь идет о данных — ума приложить не могу. Если кто-то на Хабре сможет мне ответить, почему user data zone перевели как «зона программы» я буду крайне признателен!
Уф… С физическим ликбезом, надеюсь, покончили. Разумеется, я упустил многие моменты, связанные с ширинами и длинами; с методом покрытия; длиной волны луча; и прочими физическими свойствами. Однако, во-первых это не является целью данной статьи; во-вторых я и сам больше половины информации пока не разобрал. Да и нет желания, если честно… Мое любопытство чисто «программистской» направленности ;)
Information Tracks («Информационные дорожки»)
Первая фаза — это разбиение на «информационные дорожки». Уже тут есть два варианта записи, в цифровом виде (Digital Data Tracks, DDT) и аудиоданные (Audio Tracks).
В дальнейшем будем рассматривать только цифровые данные. Вся нижеследующая информация корректна только для DDT.
Sector (Сектор)
Данные разбиваются по 8 бит (по одному байту) и группируются в секторы.
Забавно, что количество секторов в диске не определено стандартом. Оно зависит от того, сколько данных «получиться» записать на диск…
Это кажется немного нелепым. Тем не менее эту нелепость в свою эпоху использовали различные компании по обнаружению контрафактных дисков. (Так как это «уход в сторону», то написал подробнее под спойлером чуть ниже, в конце главы.)
Разумеется, длина дорожки более-менее фиксирована и в целом QoS гарантировать можно.
Существует три способа (mode) записи данных в секторах:
- Sector Mode (00) — это пустой сектор, заполняемый данными, состоящие из 0x00 байтов.
- Sector Mode (01) — использование EDC, P-Q и CIRC кодирование. (об этом чуть ниже)
- Sector Mode (02) — отсутствие P и Q кодирования, только CIRC кодирование
Приведем картинки:
Запись лицензионного ключа.
- Следует сначала записать всю необходимую информацию на диск.
- Затем мы выбраем 2 сектора. Например 103123 и 120234 сектора. Обозначим эти сектора как A и Б.
- Выбираем два байта: по одному байту на каждом секторе. Например 4й байт первого сектора и 8й байт второго
- Затем следует подсчитать угол между этими байтами на секторе. Как это сделать? Предположим, у вас есть доступ к низкоуровневому драйверу чтения и вы знаете время одного оборота.Тогда следует вычислить время, потраченное на считывание между А и Б. Поделив это время на время одного оборота можно с определенной погрешностью вычислить угол.
- Зачение угла, округленное до определенного знака, подается на вход хеш-функции. У хеш-значения берутся несколько символов, например последние 3 символа.
- Эти три символа записываются в лицензионный ключ.
Процедура проверки лицензионного ключа.
- У пользователя просят ввести лицензионный ключ.
- Вычисляем угол между выбранными байтами A и Б секторами
- Вычисляем проверяемый список углов. Например мы вычислили угол 33,343°. Предположим, что округление происходит с точностью до градуса. Округляем и получаем 33°. Предположим, что погрешность ±2°. Список углов: [31°, 32°, 33°, 34°, 35°].
- Для каждого угла из списка вычисляем хеш. Берем несколько символов из хеша. Для примера — последние 3 символа
Если хотя бы один хеш из списка совпал с хешем из лицензионного ключа, то делаем вывод, что диск лицензионный. Иначе диск контрафактный
Коррекция ошибок (только Sector Mode 01)
Полезная информация (User Mode) состоит из 2048 байт в режиме 01; или 2336 байт в режиме 02.
Какой режим выбрать? Все зависит от того, какое требование надежности вам требуется.
Sector Mode 01 надежнее, так как в нем используются дополнительно EDC проверка и P-Q кодирование.
EDC
Error Detection Code (EDC), как понятно по названию, предназначен только для обнаружения, но не для исправления ошибок.
Вот его полином: P(x)=(x16+x15+x2+1)(x16+x2+x+1)
Intermediate
Восемь байт поля Intermediate заполняются нулевыми байтами (0x00).
Вот уж не знаю зачем их оставили… Может «про запас» (в IT стандартах это любят), а может это коварный план стеганографической передачи данных.
P и Q кодирование (RSPC)
Reed-Solomon Product-like Code (RSPC), оно же P+Q кодирование используется с 12 по 2075 байт данных в режиме 01. Подробности опущу, вы можете прочесть их в Annex A стандарта ECMA-130.
Байты с 12 по 2075 и проверочные с 2 076 по 2 351 составляют 2340 байт данных. Эти данные разбиваются на два блока по 1170 байт каждый. Разбиение происходит как в школьных уроках физкультуры. "На перррвый- вторрррой рассчитась!". То есть на нечетные и четные байты.
Дальше идет кодирование внешним и внутренними кодами. Внешний называется P-кодированием, внутренний Q-кодированием.
Самая сложная в понимании стека ECMA-130 пройдена. Теперь будет значительно проще.
Скремблирование
Переходим к скремблированию. Вот так выглядит один сектор скремблирования:
Каждый такой сектор называют Scrambled Sector.
Скремблер нужен для того, чтобы сделать спектр сигнала равномерным. Иначе, при однородных данных (например, много повторяющихся единиц или нулей) энергия сигнала будет сосредоточена в узком диапазоне.
F1, F2 и F3 frame'ы
Каждый Scrambled Sector разбивается на frame'ы, длиной по 24 байта каждый.
Данные frame'ы имеют название: F1 frame.
Каждый Scrambled Sector у нас состоит из 2352 байт.
Соответственно каждый сектор разбивается на 98 frame'ов.
CIRC кодирование (F2 frame)
Cross Interleaved Reed-Solomon (CIRC) кодирование осуществляется для каждого F1 frame'а.
Это код, корректирующий ошибки с длиной входного слова в 24 байта, а длиной выходного слова в 32 байта.
Причем в отличие от EDC и RSPC кодирования, CIRC кодирование применяется для всех Sector Mode.
Полученную последовательность из 32 байт называют F2 frame'ами.
Контрольный байт
В начало каждого F2 frame'а добавляют один проверочный байт и получается F3 frame с длиной в 33 байта (32+1=33).
8-to-14 кодирование
На этой стадии данные каждый байт (8 бит) преобразуется в 14 бит данных. Преобразование осуществляется по таблице.
Всю таблицу приводить не буду, вы можете найти её в Annex D стандарта ECMA-130.
... ...
00010000 10000000100000
00010001 10000010000000
00010010 10010010000000
00010011 00100000100000
00010100 01000010000000
00010101 00000010000000
00010110 00010010000000
... ...
Зачем необходимо 8-to-14 кодирование в стандарте не указано. (Стандарт и не обязан отвечать на вопросы ПОЧЕМУ, в стандарте должны быть ответы на вопросы КАКИМ ОБРАЗОМ)…
У меня есть одна гипотеза. Дело в том, что реальный мир не настолько «идеален», каким его видят программисты. Например, нарисованная точка — это маленькая «клякса», а нарисованная линия всегда имеет площадь; в противном случае наши бы глаза не видели бы точку и линию… По этой причине рискну высказать ряд предположений. Подчеркну, что я никогда не работал профессионально с изготовлением CD дисков. Это всего лишь предположения. (Дискуссия в коментариях категорически приветствуется!).
Гипотезы.
- Пит не «идеально» выжигается на поверхности диска, поэтому необходимо некое пространство рядом с питом, т.к. за это пространство выжженный пит может «заскочить».
- Скорее всего, есть определенные проблемы с синхронизацией самой головки.Слишком большое количество подряд идущих нулей — это плохо.
- Возможно большое количество единиц это дополнительная «нагрузка» на считывающую головку. Поэтому их уменьшение позволит существенно увеличить срок эксплуатации CD привода
Подсчитываем избыточность
Посмотрим, насколько протокол CD избыточен:
- В зависимости от Sector Mode:
- Sector Mode 01 (P-Q кодирование) — На входе блок из 2048 байт, на выходе 2352. Следовательно избыточность равна: 2352/2048=1.148
- Sector Mode 02 (без P-Q кодирования) — 2352/2336=1.007
- Скремблирование — мелочь, но для порядка учтем: (12+2340)/2340=1.005
- F1-F2-F3 фреймы — 33/24=1.375
- 8-to-14 кодирование — 14/8=1.750
Перемножая все, получаем: 1.148 ⋅ 1.005 ⋅ 1.375 ⋅ 1.750 = 2.776. Таким образом на сам диск в итоге записывается в 2.776 раз больше информации, чем «полезная информация».
Например при объеме «полезной информации» в 700Мб, реально на диск записывается 1943 Мб данных.
Для Sector Mode 02 не используется P-Q кодирование. Для этого режима избыточность равна: 1.007 ⋅ 1.005 ⋅ 1.375 ⋅ 1.750 = 2.435.
Бонус: SCSI Multimedia Commands
Есть стандарт SCSI Multimedia Commands. В нем дано описание команд «сырого» чтения данных. Команды READ CD и WRITE CD позволяют считывать 2352 байт данных со всего сектора. Однако команд для считывания F-fraim'ов я не нашел… В принципе если записывать избыточную информацию, для которой не страшны частичные потери (например видео, телематика)
можно обойтись без F1-F2-F3 фреймов увеличив «полезную нагрузку» в 1.375 раз.
Так же есть ряд неиспользуемых областей в компакт диске (например тот же Intermidiate), которыми так же можно воспользоваться. Например ради задач стеганографии.
К сожалению я не нашел OpenSource кода, реализующий данные возможности…
Если на хабре есть спецы по данному вопросу, буду рад получить ссылочку (с меня плюс в карму).
Автор: PavelMSTU
