Страница Ивана Рощина > Статьи >

© Иван Рощин, Москва

ZXNet: 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW: http://www.ivr.da.ru

Использование избыточной информации для защиты файлов от повреждений

Радиомир. Ваш компьютер» 11/2002)
Дата последнего редактирования: 9.11.2002.

Введение
Теория
Применение для защиты файлов
Выводы
О программах
Полезные процедуры
Литература

Введение

Для долговременного хранения информации на ZX Spectrum традиционно используются дискеты. Это не очень-то надёжный носитель: наверняка вам не раз приходилось сталкиваться с ситуацией, когда при обращении к файлу появляется сообщение о дисковой ошибке, и прочитать файл не удаётся. Так что защита файлов от повреждений была бы очень кстати…

Теория

Всё предельно просто. Пусть у нас имеется n m-битных чисел. Построим дополнительное число, представляющее собой результат поразрядной логической операции «исключающее или» над исходными числами: если общее число единиц в каком-то разряде чётно, то соответствующий разряд результата равен нулю; если нечётно — единице.

Ниже приведён пример для случая n=4, m=10:

0110010110
0100111010
1000100111
0110100101
----------
1100101110

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

Пусть для рассмотренного примера утрачено, скажем, третье число. Вот как оно восстанавливается:

0110010110 <- 1 число
0100111010 <- 2 число
0110100101 <- 4 число
1100101110 <- дополнительное число
----------
1000100111 <- восстановленное 3 число

Можете сами убедиться, что способ сработает и при утрате другого числа — первого, второго или четвёртого.

Применение для защиты файлов

Файл хранится на диске разбитым на небольшие блоки — сектора. В TR-DOS размер сектора — 256 байтов. При записи каждого сектора дисковый контроллер вычисляет и записывает на диск его контрольную сумму, а при чтении — вычисляет контрольную сумму прочитанных данных и сравнивает с ранее записанной. При несовпадении делается вывод, что сектор прочитан с ошибкой. Иногда после нескольких попыток такой сектор всё же удаётся правильно прочитать, но не всегда. Бывает ещё, что не удаётся прочитать заголовок сектора — тогда хранившаяся в этом секторе информация также оказывается недоступной.

Потеря данных в повреждённом файле обычно не бывает полной — часто «не читается» только один или несколько секторов, а другие остаются неповреждёнными.

Пусть файл занимает n секторов. Каждый сектор можно считать 256-байтным числом. Выполним над всеми n числами поразрядную логическую операцию «исключающее или», получив в результате также 256-байтное число, и допишем его к файлу. Зная это число, можно, как описывалось выше, восстановить любое из утраченных чисел, если известны оставшиеся.

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

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

На рис. 1 приведён пример для случая, когда длина исходного файла — 7 секторов. В 8 секторе содержится избыточная информация для секторов 2, 4 и 6, а в 9 секторе — избыточная информация для секторов 1, 3, 5 и 7.

Рис. 1

Если в этом файле окажутся повреждены, например, 2 и 3 сектора, то 2 сектор мы сможем восстановить по содержимому 4, 6 и 8 секторов, а 3 сектор — по содержимому 1, 5, 7 и 9 секторов.

Если окажутся повреждены 7 и 8 сектора, то надо восстановить только 7 сектор — это можно сделать по содержимому 1, 3, 5 и 9 секторов. Заметим, что если бы сектора с дополнительной информацией располагались в другом порядке, восстановить 7 сектор было бы невозможно.

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

Рис. 2

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

Выводы

Раньше, чтобы обеспечить сохранность файлов, вам приходилось использовать резервное копирование или архивирование. Что нового даёт использование избыточной информации?

Можно хранить вместо копий файлов только избыточную информацию для этих файлов. При этом потребуется значительно меньше дискового пространства, что немаловажно: во-первых, дискеты не бесплатны, а во-вторых, они постепенно становятся дефицитом, и если трёхдюймовые дискеты ещё можно встретить в продаже, то пятидюймовые — увы…

Недостаток этого способа в том, что можно исправить лишь ограниченное число повреждённых секторов файла. Впрочем, как уже упоминалось выше, в файле обычно бывают повреждены лишь один или несколько секторов.

Если надёжность этого способа не кажется вам достаточной, и вы предпочитаете использовать резервное копирование или архивирование, то задумайтесь вот о чём: при повреждении файла мало удовольствия узнать, что копия тоже «не читается», не правда ли? Так что использование избыточной информации для защиты копий файлов или архива тоже имеет смысл.

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

К сожалению, возможность создания архивов с избыточной информацией для защиты от повреждений не реализована ни в одном из известных мне архиваторов на ZX Spectrum. А вот на PC такая возможность есть — например, в архиваторе RAR (опция «Add recovery record»).

О программах

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

В простейшем случае такая программа должна уметь создавать для указанных пользователем файлов (например, отмеченных в каталоге) файлы с избыточной информацией (возможно, расположенные на другом диске). Имена создаваемых файлов можно сделать такими же, как у исходных файлов, а расширение — «rec» (от «recovery record»). Обратная операция — восстановление указанных пользователем файлов с помощью файлов с избыточной информацией (возможно, расположенных на другом диске). Если полностью восстановить файл нельзя, надо по крайней мере восстановить то, что можно. Необходимо предусмотреть запись восстановленных файлов как поверх исходных, так и на другой диск (на случай, если исходный диск имеет физические повреждения).

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

Можете попробовать написать архиватор, в котором была бы возможность защиты создаваемых архивов от повреждений. В этом случае удобно хранить избыточную информацию в конце архива.

Можно использовать защиту файлов от повреждений и в какой-нибудь другой программе. Например, в текстовом редакторе можно при записи текста на диск автоматически записывать и rec-файл с избыточной информацией, если пользователем выбрана соответствующая опция.

Между прочим, с помощью избыточной информации можно защищать от повреждений не только файлы на диске, но и пересылаемую по некоторому каналу связи информацию, если она разбивается на пакеты и часть пакетов может быть повреждена или потеряна. (Например, пересылка разбитого на секции файла в FIDO или ZXNet.) Может быть выгодно передать несколько больший объём информации, но зато получатель не будет «переспрашивать» при каждой ошибке. Соответственно, ещё одна область применения — коммуникационные программы.

Полезные процедуры

1.

Получение 256 байтов избыточной информации для группы 256-байтных участков, расположенных в памяти один за другим.

Вход: B

количество участков в группе,

HL

адрес начала первого участка (должен быть кратным 256),

DE

адрес, по которому будет размещена избыточная информация (должен быть кратным 256).

MK_256REC  PUSH HL
           PUSH BC
           XOR  A

MK_256_1   XOR  (HL)
           INC  H
           DJNZ MK_256_1

           LD   (DE),A
           POP  BC
           POP  HL
           INC  L
           INC  E
           JR   NZ,MK_256REC

           RET
2.

Получение 512 байтов избыточной информации для группы 256-байтных участков, расположенных в памяти один за другим. Первые 256 байтов избыточной информации соответствуют участкам 1, 3, 5…; вторые 256 байтов — участкам 2, 4, 6…

Вход: B

количество участков в группе (не менее двух),

HL

адрес начала первого участка (должен быть кратным 256),

DE

адрес, по которому будет размещена избыточная информация (должен быть кратным 256).

MK_512REC  PUSH BC
           INC  B
           CALL MK_512_1
           INC  D
           INC  H
           POP  BC

MK_512_1   SRL  B
MK_512_2   PUSH HL
           PUSH BC
           XOR  A

MK_512_3   XOR  (HL)
           INC  H
           INC  H
           DJNZ MK_512_3

           LD   (DE),A
           POP  BC
           POP  HL
           INC  L
           INC  E
           JR   NZ,MK_512_2

           RET
3.

Восстановление одного 256-байтного участка из группы таких участков, расположенных в памяти один за другим, по 256 байтам избыточной информации.

Вход: B

количество участков в группе,

C

номер восстанавливаемого участка, уменьшенный на 1 (т.е. для первого участка — 0),

HL

адрес начала первого участка (должен быть кратным 256),

DE

адрес, по которому находится избыточная информация (должен быть кратным 256).

US_256REC  LD   A,H
           ADD  A,C
           LD   XH,A

;XH - старший байт адреса восстанавливаемого участка.

US_256_1   PUSH BC
           PUSH HL

           LD   A,L
           LD   XL,A
           LD   A,(DE)

US_256_2   LD   C,A
           LD   A,H
           CP   XH
           LD   A,C
           JR   Z,US_256_3
           XOR  (HL)
US_256_3   INC  H
           DJNZ US_256_2

           LD   (IX),A

           POP  HL
           POP  BC
           INC  L
           INC  E
           JR   NZ,US_256_1

           RET
4.

Восстановление одного 256-байтного участка из группы таких участков, расположенных в памяти один за другим, по 512 байтам избыточной информации. Первые 256 байтов избыточной информации должны соответствовать участкам 1, 3, 5…; вторые 256 байтов — участкам 2, 4, 6…

Вход: B

количество участков в группе,

C

номер восстанавливаемого участка, уменьшенный на 1 (т.е. для первого участка — 0),

HL

адрес начала первого участка (должен быть кратным 256),

DE

адрес, по которому находится избыточная информация (должен быть кратным 256).

Если надо восстановить два участка из группы (тогда один из участков должен быть чётным, а другой — нечётным), то перед вторым вызовом процедуры все входные параметры должны быть установлены заново, так как процедура не сохраняет первоначальные значения соответствующих регистров.

US_512REC  LD   A,H
           ADD  A,C
           LD   XH,A

;XH - старший байт адреса восстанавливаемого участка.

           INC  B
           BIT  0,C
           JR   Z,US_512_1
           INC  H
           INC  D
           DEC  B
US_512_1   SRL  B

US_512_2   PUSH BC
           PUSH HL

           LD   A,L
           LD   XL,A
           LD   A,(DE)

US_512_3   LD   C,A
           LD   A,H
           CP   XH
           LD   A,C
           JR   Z,US_512_4
           XOR  (HL)
US_512_4   INC  H
           INC  H
           DJNZ US_512_3

           LD   (IX),A

           POP  HL
           POP  BC
           INC  L
           INC  E
           JR   NZ,US_512_2

           RET
5.

Формирование в памяти избыточной информации для файла. Создается 256 байтов избыточной информации на каждые 16 полных или неполных секторов файла. Эта процедура использует описанную выше процедуру MK_256REC.

Вход: B

длина файла в секторах,

DE

трек-секторный адрес начала файла.

BUF_16_SEC EQU  #8000  ;Буфер для загрузки 16 секторов файла.
BUF_RESULT EQU  #9000  ;Буфер для избыточной информации.

;Длина и того, и другого буфера - #1000 байтов; адреса буферов
;могут быть другими, но обязательно кратными 256.

MAKE_INFO  LD   HL,BUF_RESULT
           LD   (ADR_256),HL

MAKE_I_1   LD   C,16
           LD   A,B
           SUB  C
           JR   NC,MAKE_I_2
           LD   C,B
MAKE_I_2   PUSH BC

           PUSH DE
           LD   B,C

;Сейчас в регистре B - количество читаемых секторов (16 или
;меньше), в DE - трек-секторный адрес, откуда читать.

           PUSH BC
           LD   HL,BUF_16_SEC
           PUSH HL
           LD   C,5   ;Номер функции "чтение секторов".
           CALL #3D13
           POP  HL
           POP  BC

;Сейчас HL=BUF_16_SEC. Формируем для прочитанного участка файла
;256 байтов избыточной информации:

           LD   DE,0
ADR_256    EQU  $-2
           CALL MK_256REC
           INC  D
           LD   (ADR_256),DE

;Увеличиваем трек-секторный адрес:

           POP  DE
           INC  D

;Повторяем, пока не будет обработан весь файл:

           POP  BC
           LD   A,B
           SUB  C
           LD   B,A
           JR   NZ,MAKE_I_1

           RET

Литература

  1. М.А.Карцев. «Арифметика цифровых машин». Москва, изд-во «Наука», 1969.

Другие мои статьи о TR-DOS:

1. 

«Доступ к порту #1F в TR-DOS 5.03». «ZX-Ревю» 1—2/1997.

2. 

«О сокращении времени форматирования». «ZX-Ревю» 1—2/1997.

3. 

«TR-DOS: как не допустить ошибки?». «ZX-Ревю» 5—6/1997.

4. 

«Работа с диском при включённых прерываниях». Adventurer #9, «Чёрная ворона» #3, «Радиолюбитель. Ваш компьютер» 6/2000 (дополненная версия).

5. 

«Вывод трёхсимвольных расширений файлов в операционной системе TR-DOS». «Радиолюбитель. Ваш компьютер» 7/2000.

6. 

«Усовершенствованный алгоритм определения смены диска». «Радиолюбитель. Ваш компьютер» 9/2000.

7. 

«Расширения файлов TR-DOS». «Радиолюбитель. Ваш компьютер» 12/2000, «Радиомир. Ваш компьютер» 9/2001 (под псевдонимом BV_Creator).

8. 

«Обрубаем файлам „хвост“». «Радиомир. Ваш компьютер» 4/2002.

9. 

«Проверка корректности файловой структуры дисков TR-DOS». «Радиомир. Ваш компьютер» 6/2004.

Страница Ивана Рощина > Статьи >