Chapter 1: CD Organization

Entropy is blind, but patient. Sooner or later, by centering its fire on our position, square by square, it will strike the headquarters, or communication center. The first line of defense will then be destroyed . We will have to retreat to positions prepared before-hand. In other words, in such a situation a programmer has to rely on a backup copy of the volume.

E.V.Lishak

32th Day of the year.

(Notes of para-system programmer).

Overview

Practically everyone will already have heard of the existence of error-correction Reed-Solomon codes, widely used in data storage and transmission devices for the detection and correction of both single and multiple errors. Their application area is unusually large. Reed-Solomon encoders/decoders can be found in tape storage drives, RAM controllers, modems, hard disks, CD-ROM/DVD drives , etc. Thanks to these codes, some advanced archivers can survive the corruption of several sectors of the media-containing archive, or, sometimes, even the total destruction of an entire volume of a multi-volume archive. Besides this, Reed-Solomon codes enable the protection mechanism to restore bytes hacked by someone trying to crack the system or corrupted as a result of software or hardware failure.

In brief, although mastering the technique of error-correction encoding doesn t automatically give God-like powers, it at least raises you to that Olympus where great computer Gurus dwell among noiseless coolers and bug-free operating systems.

At the same time, only a small number of programmers can claim pride in original implementation of Reed-Solomon codes. After all, what is the point of bothering? There are lots of ready-to-use libraries, ranging from commercial software to free source codes distributed according to the GNU license agreement. There is a wide range of possibilities. Take any library of your choice ^[i] . Sure, there is pragmatic reason for using libraries. However, if you entrust control to the program without understanding how it actually works, are you a hacker? This book s intended audience, after all, mainly comprises hackers (naturally, in only the most positive sense of the term ). On the other hand, when analyzing software distributed without source codes, you won t be able to identify the Reed-Solomon algorithm unless you carefully investigate it beforehand to gain a clear understanding of all of its intricacies. Suppose that you have encountered a protection mechanism that in some intricate way manipulates EDC/ECC fields of key sectors read from a CD. Further, assume that each of these sectors contains two mangled bits (plus errors that are generated in a natural way, provided that the CD is treated carelessly). At the same time, one of these is a false error and shouldn t be corrected. When copying the protected disc using a standard procedure, the microprocessor of the CD-ROM drive automatically correct all errors that the drive is capable of correcting. As a result, key marks will be erased. Consequently, the protected program will cease to operate . It is, of course, possible to copy the disc in the raw mode, e.g., without error correction. However, in this case, the copy will contain all of the errors of the original, both intentional and unintentional. As a result, even if the original is only slightly damaged, the correction capabilities of Reed-Solomon codes may be insufficient and the disc will become unreadable (What did you expect? Copying discs in raw mode results in error accumulation, and, therefore, is highly inefficient from any point of view). Mastering the basic principles of error-protected encoding will help us to grasp the logic of any protection mechanism. In particular, we will understand, which errors have to be corrected and which must be left as is.

Unfortunately , most publications related to the Reed-Solomon codes are written in the language of higher mathematics. It is often beyond the average university graduate to understand these materials (how many hackers have math skills at the University level?)

As a result, in the best case most of these abstract manuals end up buried at the back of hacker s bookshelves, where they gradually become covered with dust. In the worst case, they end up in the garbage can.

Software implementation of the Reed-Solomon error-correcting codes is actually very complicated and requires an above-average level of mathematical abilities . An explanation of the mathematical foundations of its implementation might seem boring and tiresome to system and hardware programmers, but, unfortunately, there is no other way around it. After all, no one promised that it was going to be easy to become a programmer. To become a really good programmer is significantly more difficult, so don t say you weren t warned beforehand! Just kidding :-). Don t worry, take it easy and don t be afraid of higher mathematics. You will encounter a few formulas in this chapter (what mathematician can live without formulas?), but, in most cases, I ll try to speak in the international programming language ”C, which is familiar to all system programmers. So, fasten your seatbelts, and raise your heads from the keyboards, and off we go!

^[i] due to implementation errors, this code adds new bugs instead of eliminating the existing ones. Therefore, this code is no longer available ”this is the comment to the GNU source codes of the Reed-Solomon encoder/decoder. Having encountered such a comment, would you trust in Linux reliability in general and GNU library code in particular? Well, I never!