Using redundant information to protect files...

Hello, All! ═══════════════════ 1 .C ══════════════════ (c) Ivan Roshchin, Moscow Fido: 2:5020/689.53 ZXNet: 500:95/462.53 E-mail: bestview@mtu-net.ru WWW: http://www.ivr.da.ru Using redundant information to protect files from damage ════════════════════════════════ ("Radiomir. Your computer" 11/2002) Last edit date: 11/9/2002. Introduction ──────── For long-term storage of information on the ZX Spectrum floppy disks are traditionally used. It's not very reliable carrier: you've probably had to deal with more than once situation when, when accessing a file, a message appears about disk error and the file cannot be read. So the defense files from damage would be very helpful... Theory ────── Everything is extremely simple. Let us have n m-bit numbers. Let's construct an additional number representing the result bitwise logical operation "exclusive or" over the original numbers: if the total number of units in some place is even, then the corresponding bit of the result is zero; if odd - unit. Below is an example for the case n=4, m=10: 0110010110 0100111010 1000100111 0110100101 ────────── 1100101110This additional number will be redundant information. Now, if any of the original numbers are lost, it it will be possible to restore using the remaining numbers and additional number. To do this, it is enough to perform the same operation on them "exclusive or", the result of which will be equal to lost number. Let for the considered example be lost, say, the third number. Here's how it is restored: 0110010110 <- 1 number 0100111010 <- 2nd number 0110100101 <- 4th number 1100101110 <- additional number ────────── 1000100111 <- restored 3rd number You can see for yourself that the method will work even if you lose another number - the first, second or fourth. Application for file protection ──────────────────────────── The file is stored on disk divided into small blocks - sectors. In TR-DOS, the sector size is 256 bytes. When recording each sector, the disk controller calculates and writes to disk its checksum, and when reading, calculates the checksum the sum of the read data and compares it with the previously recorded one. When If there is a discrepancy, it is concluded that the sector was read with an error. Sometimes, after several attempts, such a sector is still successful read correctly, but not always. It also happens that it doesn’t work outread the sector header - then stored in this sector information is also unavailable. Data loss in a damaged file is usually not complete - often only one or several sectors are “unreadable”, while others remain undamaged. Let the file occupy n sectors. Each sector can be considered 256-byte number. Let’s perform a bitwise operation on all n numbers logical operation "exclusive or", resulting in also a 256-byte number, and append it to the file. Knowing this number, you can, as described above, restore any of the lost numbers, if the remaining ones are known. In other words, by adding one redundant sector to the file information, we can restore any damaged sector this file, if the information in the remaining sectors has survived. If you add two sectors to a file, one of which (with an even number) contains redundant information for even sectors, and another (with an odd number) - for odd numbers, then it will be possible restore already two damaged sectors of the file, if one of one of them is even, and the other is odd (note that this condition satisfy any two adjacent sectors). ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 1 .C ══════════════════ (c) Ivan Roshchin, Moscow Fido: 2:5020/689.53 ZXNet: 500:95/462.53 E-mail: bestview@mtu-net.ru WWW: http://www.ivr.da.ru Using redundant information to protect files from damage ════════════════════════════════ ("Radiomir. Your computer" 11/2002) Last edit date: 11/9/2002. Introduction ──────── For long-term storage of information on the ZX Spectrum floppy disks are traditionally used. It's not very reliable carrier: you've probably had to deal with more than once situation when, when accessing a file, a message appears about disk error and the file cannot be read. So the defense files from damage would be very helpful... Theory ────── Everything is extremely simple. Let us have n m-bit numbers. Let's construct an additional number representing the result bitwise logical operation "exclusive or" over the original numbers: if the total number of units in some place is even, then the corresponding bit of the result is zero; if odd - unit. Below is an example for the case n=4, m=10: 0110010110 0100111010 1000100111 0110100101 ────────── 1100101110This additional number will be redundant information. Now, if any of the original numbers are lost, it it will be possible to restore using the remaining numbers and additional number. To do this, it is enough to perform the same operation on them "exclusive or", the result of which will be equal to lost number. Let for the considered example be lost, say, the third number. Here's how it is restored: 0110010110 <- 1 number 0100111010 <- 2nd number 0110100101 <- 4th number 1100101110 <- additional number ────────── 1000100111 <- restored 3rd number You can see for yourself that the method will work even if you lose another number - the first, second or fourth. Application for file protection ──────────────────────────── The file is stored on disk divided into small blocks - sectors. In TR-DOS, the sector size is 256 bytes. When recording each sector, the disk controller calculates and writes to disk its checksum, and when reading, calculates the checksum the sum of the read data and compares it with the previously recorded one. When If there is a discrepancy, it is concluded that the sector was read with an error. Sometimes, after several attempts, such a sector is still successful read correctly, but not always. It also happens that it doesn’t work outread the sector header - then stored in this sector information is also unavailable. Data loss in a damaged file is usually not complete - often only one or several sectors are “unreadable”, while others remain undamaged. Let the file occupy n sectors. Each sector can be considered 256-byte number. Let’s perform a bitwise operation on all n numbers logical operation "exclusive or", resulting in also a 256-byte number, and append it to the file. Knowing this number, you can, as described above, restore any of the lost numbers, if the remaining ones are known. In other words, by adding one redundant sector to the file information, we can restore any damaged sector this file, if the information in the remaining sectors has survived. If you add two sectors to a file, one of which (with an even number) contains redundant information for even sectors, and another (with an odd number) - for odd numbers, then it will be possible restore already two damaged sectors of the file, if one of one of them is even, and the other is odd (note that this condition satisfy any two adjacent sectors). ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 2 .C ══════════════════ In Fig. 1 shows an example for the case when the length of the original file - 7 sectors. Sector 8 contains redundant information for sectors 2, 4 and 6, and in sector 9 - redundant information for sectors 1, 3, 5 and 7. ┌───────────┬─────────── ┬───────────┬───────────┐ │ │ │ │ │ ╔══╧══╦═════╦══╧══╦═════╦══ ╧══╦═════╦══╧══╦═════╦══.══╗ ║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║ 6 ║ 7 ║░░8░░║░░9░░║ ╚═════╩══╤══╩═════╩══╤══╩══ ═══╩══╤══╩═════╩══.══╩═════╝ │ │ │ │ └───────────┴───────────┴───────────┘ Fig. 1 If this file turns out to be damaged, for example, 2 and 3 sectors, then we can restore sector 2 from the contents of 4, 6 and 8 sectors, and sector 3 - according to the contents of sectors 1, 5, 7 and 9. If sectors 7 and 8 are damaged, then it is necessary to restore only sector 7 - this can be done by the contents of 1, 3, 5 and 9 sectors. Note that if sectors with additional information was placed in a different order, restore 7 sector would be impossible. Similarly, by adding to the file (in the appropriate order) three sectors containing redundant information for sectors, numbers which are divisible by three without remainder, with remainder 1 and with remainder 2(Fig. 2), we can guarantee the possibility of restoring any three adjacent sectors of the file, and so on. ┌─────────────────┬──────── ─────────┬─────────────────┐ │ │ │ │ │ ┌─────────────────┬─────────────────┐ │ │ │ │ │ │ │ │ ╔══╧══╦═════╦══╧══╦══╧══╦═════ ╦══╧══╦══╧══╦═════╦══.══╦══.══╗ ║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║ 6 ║ 7 ║░░8░░║░░9░░║░10░░║ ╚═════╩══╤══╩═════╩═════╩══╤══ ╩═════╩═════╩══.══╩═════╩═════╝ │ │ │ └─────────────────┴─────────────────┘ Fig. 2 You can split the file into sections (for example, 16 sectors) and calculate redundant information for each section separately. Then it will be possible to restore the file, even if there is damage in each section. Conclusions ────── Previously, to ensure the safety of your files, you had to use backup or archiving. What's new does the use of redundant information give? You can store only redundant copies of files instead information for these files. This will require significant less disk space, which is important: firstly, floppy disks are not free, and secondly, they are gradually becoming shortage, and if three-inch floppy disks can still be found in sale, then five-inch ones - alas...The disadvantage of this method is that it can only be corrected limited number of bad sectors of the file. However, as already mentioned above, there is usually only one damaged in a file or several sectors. If the reliability of this method does not seem sufficient to you, and you prefer to use backup or archiving, then think about this: if the file is damaged it’s not much pleasure to find out that the copy is also “unreadable”, not Is it true? So using redundant information to Protecting copies of files or archives also makes sense. This especially applies to archives. If in a regular file there is sector is damaged, only information from this sector will be lost sector, and if the same happens to the archive, then most likely the entire end of the zipped file to which there was damage. The fact is that usually in the process unpacking uses the contents of the already unpacked part file. Unfortunately, the ability to create archives with redundant information for protection against damage is not implemented in any from the archivers known to me on the ZX Spectrum. But on PC it’s like this there is a possibility - for example, in the RAR archiver (option "Add recovery record"). ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 2 .C ══════════════════ In Fig. 1 shows an example for the case when the length of the original file - 7 sectors. Sector 8 contains redundant information for sectors 2, 4 and 6, and in sector 9 - redundant information for sectors 1, 3, 5 and 7. ┌───────────┬─────────── ┬───────────┬───────────┐ │ │ │ │ │ ╔══╧══╦═════╦══╧══╦═════╦══ ╧══╦═════╦══╧══╦═════╦══.══╗ ║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║ 6 ║ 7 ║░░8░░║░░9░░║ ╚═════╩══╤══╩═════╩══╤══╩══ ═══╩══╤══╩═════╩══.══╩═════╝ │ │ │ │ └───────────┴───────────┴───────────┘ Fig. 1 If this file turns out to be damaged, for example, 2 and 3 sectors, then we can restore sector 2 from the contents of 4, 6 and 8 sectors, and sector 3 - according to the contents of sectors 1, 5, 7 and 9. If sectors 7 and 8 are damaged, then it is necessary to restore only sector 7 - this can be done by the contents of 1, 3, 5 and 9 sectors. Note that if sectors with additional information was placed in a different order, restore 7 sector would be impossible. Similarly, by adding to the file (in the appropriate order) three sectors containing redundant information for sectors, numbers which are divisible by three without remainder, with remainder 1 and with remainder 2(Fig. 2), we can guarantee the possibility of restoring any three adjacent sectors of the file, and so on. ┌─────────────────┬──────── ─────────┬─────────────────┐ │ │ │ │ │ ┌─────────────────┬─────────────────┐ │ │ │ │ │ │ │ │ ╔══╧══╦═════╦══╧══╦══╧══╦═════ ╦══╧══╦══╧══╦═════╦══.══╦══.══╗ ║ 1 ║ 2 ║ 3 ║ 4 ║ 5 ║ 6 ║ 7 ║░░8░░║░░9░░║░10░░║ ╚═════╩══╤══╩═════╩═════╩══╤══ ╩═════╩═════╩══.══╩═════╩═════╝ │ │ │ └─────────────────┴─────────────────┘ Fig. 2 You can split the file into sections (for example, 16 sectors) and calculate redundant information for each section separately. Then it will be possible to restore the file, even if there is damage in each section. Conclusions ────── Previously, to ensure the safety of your files, you had to use backup or archiving. What's new does the use of redundant information give? You can store only redundant copies of files instead information for these files. This will require significant less disk space, which is important: firstly, floppy disks are not free, and secondly, they are gradually becoming shortage, and if three-inch floppy disks can still be found in sale, then five-inch ones - alas...The disadvantage of this method is that it can only be corrected limited number of bad sectors of the file. However, as already mentioned above, there is usually only one damaged in a file or several sectors. If the reliability of this method does not seem sufficient to you, and you prefer to use backup or archiving, then think about this: if the file is damaged it’s not much pleasure to find out that the copy is also “unreadable”, not Is it true? So using redundant information to Protecting copies of files or archives also makes sense. This especially applies to archives. If in a regular file there is sector is damaged, only information from this sector will be lost sector, and if the same happens to the archive, then most likely the entire end of the zipped file to which there was damage. The fact is that usually in the process unpacking uses the contents of the already unpacked part file. Unfortunately, the ability to create archives with redundant information for protection against damage is not implemented in any from the archivers known to me on the ZX Spectrum. But on PC it’s like this there is a possibility - for example, in the RAR archiver (option "Add recovery record"). ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 3 .C ══════════════════ About the programs ──────────── Yes, but is there at least one protection program on the ZX Spectrum? files from damage due to redundant information? Alas... At least I haven't come across them, and I haven't even heard of them. their existence. So if you want to protect your files, You will have to write such a program yourself. This is the case not very complicated, especially since some useful procedures you you will find at the end of this article. In the simplest case, such a program should be able to create for user-specified files (for example, those marked in directory) files with redundant information (possibly located on another disk). The names of the created files can be make them the same as the source files, and the extension is "rec" (from "recovery record"). Reverse operation - restoration user-specified files using redundant files information (possibly located on another disk). If It is impossible to completely restore the file, you need to at least restore what is possible. It is necessary to provide a recording recovered files both on top of the original ones and on another disk (in case the original disk is physically damaged). It is desirable that the program offers a choice of several options for generating redundant information (one sector foreach file, or several sectors, or one sector for each 16 file sectors, or something else) and provided information about what damage can be repaired in each case. You can try to write an archiver in which you had It would be possible to protect created archives from damage. In this In this case, it is convenient to store redundant information at the end of the archive. You can use file protection against damage and some other program. For example, in a text editor When writing text to disk, you can automatically record and rec file with redundant information if user selected corresponding option. By the way, with the help of redundant information you can protect from damage not only the files on the disk, but also those sent via information to some communication channel if it is divided into packages and some packages may be damaged or lost. (For example, sending a sectioned file to FIDO or ZXNet.) It may be advantageous to transmit a slightly larger volume information, but the recipient will not “ask again” when every mistake. Accordingly, another area of application is communication programs. Useful procedures ────────────────── 1. Receive 256 bytes of redundant information for the group 256-byte sections located in memory one after another. Input: B - number of sections in the group,HL - address of the beginning of the first section (must be a multiple 256), DE - the address where the redundant will be placed information (must be a multiple of 256). MK_256REC PUSH HL PUSH BC XOR A MK_256_1 XOR (HL) INC H DJNZ MK_256_1 LD(DE),A POP B.C. POP HL INC L INC E JR NZ,MK_256REC RET 2. Receive 512 bytes of redundant information for the group 256-byte sections located in memory one after another. The first 256 bytes of redundant information correspond to sections 1,3,5...; the second 256 bytes - sections 2,4,6... Input: B - number of sites in the group (at least two), HL - address of the beginning of the first section (must be a multiple 256), DE - the address where the redundant will be placed information (must be a multiple of 256). MK_512REC PUSH BC INC B CALL MK_512_1 INC D INC H POP B.C. 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 B.C. POP HL INC L INC E JR NZ,MK_512_2 RET ════════════════════════ ════════════════════════Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 3 .C ══════════════════ About the programs ──────────── Yes, but is there at least one protection program on the ZX Spectrum? files from damage due to redundant information? Alas... At least I haven't come across them, and I haven't even heard of them. their existence. So if you want to protect your files, You will have to write such a program yourself. This is the case not very complicated, especially since some useful procedures you you will find at the end of this article. In the simplest case, such a program should be able to create for user-specified files (for example, those marked in directory) files with redundant information (possibly located on another disk). The names of the created files can be make them the same as the source files, and the extension is "rec" (from "recovery record"). Reverse operation - restoration user-specified files using redundant files information (possibly located on another disk). If It is impossible to completely restore the file, you need to at least restore what is possible. It is necessary to provide a recording recovered files both on top of the original ones and on another disk (in case the original disk is physically damaged). It is desirable that the program offers a choice of several options for generating redundant information (one sector foreach file, or several sectors, or one sector for each 16 file sectors, or something else) and provided information about what damage can be repaired in each case. You can try to write an archiver in which you had It would be possible to protect created archives from damage. In this In this case, it is convenient to store redundant information at the end of the archive. You can use file protection against damage and some other program. For example, in a text editor When writing text to disk, you can automatically record and rec file with redundant information if user selected corresponding option. By the way, with the help of redundant information you can protect from damage not only the files on the disk, but also those sent via information to some communication channel if it is divided into packages and some packages may be damaged or lost. (For example, sending a sectioned file to FIDO or ZXNet.) It may be advantageous to transmit a slightly larger volume information, but the recipient will not “ask again” when every mistake. Accordingly, another area of application is communication programs. Useful procedures ────────────────── 1. Receive 256 bytes of redundant information for the group 256-byte sections located in memory one after another. Input: B - number of sections in the group,HL - address of the beginning of the first section (must be a multiple 256), DE - the address where the redundant will be placed information (must be a multiple of 256). MK_256REC PUSH HL PUSH BC XOR A MK_256_1 XOR (HL) INC H DJNZ MK_256_1 LD(DE),A POP B.C. POP HL INC L INC E JR NZ,MK_256REC RET 2. Receive 512 bytes of redundant information for the group 256-byte sections located in memory one after another. The first 256 bytes of redundant information correspond to sections 1,3,5...; the second 256 bytes - sections 2,4,6... Input: B - number of sites in the group (at least two), HL - address of the beginning of the first section (must be a multiple 256), DE - the address where the redundant will be placed information (must be a multiple of 256). MK_512REC PUSH BC INC B CALL MK_512_1 INC D INC H POP B.C. 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 B.C. POP HL INC L INC E JR NZ,MK_512_2 RET ════════════════════════ ════════════════════════Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 4 .C ══════════════════ 3. Restoring one 256-byte section from a group of such sections located in memory one after another, 256 each bytes of redundant information. Input: B - number of sections in the group, C - number of the area being restored, reduced by 1 (i.e. for the first section - 0), HL - address of the beginning of the first section (must be a multiple 256), DE - address where redundant information is located (must be a multiple of 256). US_256REC LD A,H ADD A,C LD XH,A ;XH - high byte of the address of the restored section. 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 B.C. INC L INC E JR NZ,US_256_1 RET 4. Restoring one 256-byte section from a group of such sections located in memory one after another, 512 each bytes of redundant information. First 256 bytes are redundant information must correspond to sections 1,3,5...; second 256 bytes - sections 2,4,6...Input: B - number of sections in the group, C - number of the area being restored, reduced by 1 (i.e. for the first section - 0), HL - address of the beginning of the first section (must be a multiple 256), DE - address where redundant information is located (must be a multiple of 256). If you need to restore two sections from a group (then one of the sections must be even, and the other - odd), then before the second call to the procedure, all input parameters must be installed again because the procedure does not save initial values of the corresponding registers. US_512REC LD A,H ADD A,C LD XH,A ;XH - high byte of the address of the restored section. 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 B.C. INC L INC E JR NZ,US_512_2 RET ════════════════════════ ════════════════════════Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 5 .C ══════════════════ 5. Formation of redundant information for the file in memory. 256 bytes of redundant information are created for every 16 full or incomplete sectors of the file. This procedure uses the MK_256REC procedure described above. Input: B - file length in sectors, DE - track-sector address of the beginning of the file. BUF_16_SEC EQU #8000 ;Buffer for loading 16 sectors of the file. BUF_RESULT EQU #9000 ;Buffer for redundant information. ;The length of both buffers is #1000 bytes; buffer addresses ;may be different, but must be a multiple of 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 ;Now in register B - the number of readable sectors (16 or ;less), in DE - track-sector address from where to read. PUSH BC LD HL,BUF_16_SEC PUSH HL LD C,5 ;Number of the "read sectors" function. CALL #3D13 POP HL POP B.C. ;Now HL=BUF_16_SEC. We form for the read section of the file ;256 bytes of redundant information: LD DE,0 ADR_256 EQU $-2 CALL MK_256REC INC D LD (ADR_256),DE;Increase the track-sector address: POP DE INC D ;Repeat until the entire file has been processed: POP B.C. LD A,B SUB C LD B,A JR NZ,MAKE_I_1 RET Literature ────────── 1. M.A. Kartsev. "Arithmetic of Digital Machines". Moscow, publishing house "Science", 1969. ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.

Hello, All! ═══════════════════ 5 .C ══════════════════ 5. Formation of redundant information for the file in memory. 256 bytes of redundant information are created for every 16 full or incomplete sectors of the file. This procedure uses the MK_256REC procedure described above. Input: B - file length in sectors, DE - track-sector address of the beginning of the file. BUF_16_SEC EQU #8000 ;Buffer for loading 16 sectors of the file. BUF_RESULT EQU #9000 ;Buffer for redundant information. ;The length of both buffers is #1000 bytes; buffer addresses ;may be different, but must be a multiple of 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 ;Now in register B - the number of readable sectors (16 or ;less), in DE - track-sector address from where to read. PUSH BC LD HL,BUF_16_SEC PUSH HL LD C,5 ;Number of the "read sectors" function. CALL #3D13 POP HL POP B.C. ;Now HL=BUF_16_SEC. We form for the read section of the file ;256 bytes of redundant information: LD DE,0 ADR_256 EQU $-2 CALL MK_256REC INC D LD (ADR_256),DE;Increase the track-sector address: POP DE INC D ;Repeat until the entire file has been processed: POP B.C. LD A,B SUB C LD B,A JR NZ,MAKE_I_1 RET Literature ────────── 1. M.A. Kartsev. "Arithmetic of Digital Machines". Moscow, publishing house "Science", 1969. ════════════════════════ ════════════════════════ Best regards, Ivan Roshchin.