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

Странная вещь — любопытство. Вот на столе экземпляр CD — безнадёжно устаревшего в наш просвященный XXI век формата хранения данных; а все таки интересно, как же там хранятся данные?.. Каков сам стек хранения данных?.. Как исправляются ошибки?.. Какова избыточность кода?..

В детстве мне было достаточно знаний о лазерном луче, о какой-то головке, об «этой крутящийся штуки» и о таинственных питах.

Сказано — сделано. Проглядев стандарт ECMA-130 (есть, кстати и отечественный стандарт: ГОСТ 27667-88) обнаружил массу любопытных деталей. Например, я догадывался об избыточности, но я и подумать не мог, что для записи 700 Мб данных «в реальности» записывается 1943 Мб (То есть в 2.776 раз больше)…

Схематично весь стек можно представить картинкой:




Стек рассмотрим «сверху вниз».
То есть от момента передачи данных приводу до записи самих питов.
Следует сказать, что не вся область диска используется для записи/хранения/чтения информации.
Компакт диск разделен на зоны (areas):
  1. Centre Hole (Центральное отверстие ) — это «та самая дырочка» диаметром 15 мм (±0.1 мм), за которую прикрепляется сам диск.
  2. First transition area (Первая переходная зона) — «кольцо», между 15 и 20 мм от центра диска.
  3. Сlamping area (Зона зажима) — как понятно из названия это область необходима, чтобы диск «не скакал» при чтении / записи. (26-33 мм)
  4. Second transition area (Вторая переходная зона) — «второе кольцо», между 33 и 44 мм от центра диска.
  5. Information area (Зона информации) — это «информационно полезная» часть компакт диска. Находится на расстоянии от 44 мм до 118 мм от центра.
  6. 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 кодирование


Приведем картинки:


Метод определения контрафактного диска
Метод, как и все гениальное, прост.

Запись лицензионного ключа.
  1. Следует сначала записать всю необходимую информацию на диск.
  2. Затем мы выбраем 2 сектора. Например 103123 и 120234 сектора. Обозначим эти сектора как A и Б.
  3. Выбираем два байта: по одному байту на каждом секторе. Например 4й байт первого сектора и 8й байт второго
  4. Затем следует подсчитать угол между этими байтами на секторе. Как это сделать? Предположим, у вас есть доступ к низкоуровневому драйверу чтения и вы знаете время одного оборота.Тогда следует вычислить время, потраченное на считывание между А и Б. Поделив это время на время одного оборота можно с определенной погрешностью вычислить угол.
  5. Зачение угла, округленное до определенного знака, подается на вход хеш-функции. У хеш-значения берутся несколько символов, например последние 3 символа.
  6. Эти три символа записываются в лицензионный ключ.


Процедура проверки лицензионного ключа.
  1. У пользователя просят ввести лицензионный ключ.
  2. Вычисляем угол между выбранными байтами A и Б секторами
  3. Вычисляем проверяемый список углов. Например мы вычислили угол 33,343°. Предположим, что округление происходит с точностью до градуса. Округляем и получаем 33°. Предположим, что погрешность ±2°. Список углов: [31°, 32°, 33°, 34°, 35°].
  4. Для каждого угла из списка вычисляем хеш. Берем несколько символов из хеша. Для примера — последние 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-кодированием.

Картинка с P и Q кодированием


Для большего понимания: картинка только с Q кодированием



Самая сложная в понимании стека ECMA-130 пройдена. Теперь будет значительно проще.

Скремблирование



Переходим к скремблированию. Вот так выглядит один сектор скремблирования:


Каждый такой сектор называют Scrambled Sector.

А что такое ''скремблирование'' и зачем это нужно?
О смысле скремблирования кратко и емко в комментарии к одному из моих постов написал snapdragon
Скремблер нужен для того, чтобы сделать спектр сигнала равномерным. Иначе, при однородных данных (например, много повторяющихся единиц или нулей) энергия сигнала будет сосредоточена в узком диапазоне.



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 дисков. Это всего лишь предположения. (Дискуссия в коментариях категорически приветствуется!).

Гипотезы.
  1. Пит не «идеально» выжигается на поверхности диска, поэтому необходимо некое пространство рядом с питом, т.к. за это пространство выжженный пит может «заскочить».
  2. Скорее всего, есть определенные проблемы с синхронизацией самой головки.Слишком большое количество подряд идущих нулей — это плохо.
  3. Возможно большое количество единиц это дополнительная «нагрузка» на считывающую головку. Поэтому их уменьшение позволит существенно увеличить срок эксплуатации CD привода. В среднем на 8 бит данных мы имеети 4 единицы. В 8-to-14 кодировании в кодовом слове у нас 1 или 2 единицы. То есть в два раза меньше.


Подсчитываем избыточность



Посмотрим, насколько протокол CD избыточен:
  1. В зависимости от Sector Mode:
    • Sector Mode 01 (P-Q кодирование) — На входе блок из 2048 байт, на выходе 2352. Следовательно избыточность равна: 2352/2048=1.148
    • Sector Mode 02 (без P-Q кодирования) — 2352/2336=1.007
  2. Скремблирование — мелочь, но для порядка учтем: (12+2340)/2340=1.005
  3. F1-F2-F3 фреймы33/24=1.375
  4. 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 кода, реализующий данные возможности…
Если на хабре есть спецы по данному вопросу, буду рад получить ссылочку (с меня плюс в карму).

Комментарии (9)


  1. AlanDrakes
    23.02.2016 17:40
    +4

    Как говорится, добавлю свои 5 копеек к теме CD записи.
    Зачем использовать кодирование 8-to-14? Всё очень просто. Для гаранритованного чтения записанных данных.
    Действительно на поверхности диска могут возникнуть ошибки в данных как при записи, так и при чтении. Собственно, этих ошибок в какой-то мере позволяет избежать таблица значений. Не буду приводить громоздких примеров, ограничусь лишь общей фразой: "Узнать искажённую знакомую последовательность проще, чем гадать где же была ошибка в байте". Достаточно хороший метод исправления ошибок, а так же, для улучшения синхронизации с дорожкой в потоке нулей.
    В этом плане технология похожа на Ethernet с кодированием 4-to-5 и на некоторые другие. Как пример могу ткнуть в E1-фреймы (телефония), но там код всё же другой (HDB3, работающий с отрицательными и положительными импульсами), но и в нём так же используется занятный метод кодирования информации, добавляющий дополнительные импульсы по определённой функции к потоку для гарантии устойчивой синхронизации кадров.


    1. PavelMSTU
      23.02.2016 17:42

      То есть это еще один код, помимо RSPC и CIRC кодирования?
      Неужели нужна ТАКАЯ избыточность 0_о...


      1. Eklykti
        23.02.2016 18:05
        +2

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


        1. PavelMSTU
          23.02.2016 18:19

          Я тут подумал…
          Может быть 8-to-14 кодирование используется для обнаружения ошибок, а RSPC и CIRC уже для исправления?..

          Хабр, тут есть спецы по данному вопросу?


  1. sysprg
    23.02.2016 18:54
    +1

    О назначении 8-to-14 кодирования: https://en.wikipedia.org/wiki/Eight-to-fourteen_modulation
    EFM belongs to the class of DC-free run length limited (RLL) codes; these have the following two properties:

    • the spectrum (power density function) of the encoded sequence vanishes at the low-frequency end and
    • both the minimum and maximum number of consecutive bits of the same kind are within specified bounds.


    1. PavelMSTU
      24.02.2016 11:16

      Гм… да… стандарт на выходных разобрал а в вики посмотреть забыл… ^__^

      Кстати, спасибо за ссылку на Кееса Схаухамера Имминка.
      Наяндексил его книгу "Codes for Mass Data Storage Systems".
      На досуге почитаю.


  1. Alexeyslav
    24.02.2016 11:59

    Была где-то статья что из-за алгоритма скремблирования кодирование определённого набора байт в итоге на диск пишется участок данных точь в точь совпадающий с старым маркером начала дорожки(кажется, 56 байт подряд идущих нулей или что-то вроде того), на которых реагировали приводы со старой пошивкой в которой был код который поддерживал такие маркеры.
    В итоге долго не могли понять почему при записи определённого фильма на компакт многие приводы просто не могли прочитать это место на диске, спотыкаясь. Маркер-то есть, привод реагирует но дальше данные не валидны для начала дорожки и привод честно рапортует об ошибке чтения… Потом уже выделили эту магическую последовательность байт и с каким смещением она должна находится в пользовательских данных чтобы привести к проблеме и успешно воспроизвели. Так что, в принципе применённое скремблирование не способно на 100% размазать спектр сигнала, вероятно поэтому дополнительно используют еще и 8-в-14 кодирование.
    По сложности, это наверно как найти данные, для которых хеш даёт много нулей подряд.


  1. interrupt
    24.02.2016 12:35
    +1

    Предположу (основываясь на некотором изучении MD устройств) одно из назначений EFM (помимо спектра, и постоянной составляющей) — восстановление тактовых импульсов для дальнейших преобразований. Ведь на диске нет отдельного тактового сигнала (как в i2s, например). Жестко привязать вращение диска к частоте тактового генератора тоже не получится. Следовательно на нижнем уровне нам нужно некоторое кодирование которое позволит выделить тактовый сигнал и поток данных не смотря на возможные ошибки "аналоговой природы" (проскальзывание, ошибки слежения, неидеальность установления скорости вращения диска и т.д.) в сигнале прочитанном фотодиодом.


  1. Wesha
    25.02.2016 00:16
    +2

    Про манипуляции с данными на компакт-дисках и срыв синхронизации на некоторых приводах на IXBT была классная детективная история (спойлер: убийца — скремблер).