Source file: raid.c
In computer engineering there is a technique called RAID (Redundant Array of Inexpensive Disks). It allows several degrees of protection against loss of data.
The technique is to split the data, into blocks, on more then one disk. At first, it was thought to make one disk the parity disk. Thus, whenever you wanted to store a block in a disk, lets say block 3 in disk 1, you had to read all the other blocks with the some number from the other disks and used them all to calculate the parity block to store in the parity disk.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Figure 1 – 4 bit blocks. Even parity. Parity blocks marked with bold over grey. A parity block is calculated with all the parities from the first, second, etc bits of the other blocks. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Figure 2 – The same data, parity, bits per block and disks as in Figure 1. This time with a better arrangement: the RAID 5. No bottlenecks! |
As you can see from the figure the way to place the parity blocks over the disks is easy. The first parity block to the first disk, the second to the second and so on. When you have more parity blocks than disks you start all over again.
You are to write a program that takes data from standard input and writes the same data plus the parity data (even parity) according to the RAID 5 technique. Note that you must add a disk. Thus if you receive data spread over d disks you must determine how that data and its parity will be spread over d+1 disks.
Input:
From standard input you will receive several sets of data. Each one is constituted by 2 parts: one line with two integers, b and d, and then b more lines each one with d hexadecimal characters. b is the number of blocks per disk and d is the number of disks. The hexadecimal characters have a single space between them. Between 2 sets of data there is an empty line. Input terminates with a line with both b and d equal to zero:
0 < d < 7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Output:
For each data set, you have to print one-header line and b data lines. The header line is in the form:
Where b and d are the numbers read from input. Remember again that you start with d disks from the input and end up with d+1 disks.
The b data lines must have a total of d+1 series of 4 bits (blocks) corresponding to d data hexadecimal numbers and 1 parity block. Before and after each data block there must be 2 space characters (2 before and 2 after). If the block is a parity block, then you have to write a space and a star before the block, " *" (".*"), and a star and a space after the block, "* " ("*.").
After each set there must be an empty line (just the "¿ "), even in the last set.
Sample input:
| 5 3
0 1 2 3 4 5 6 7 8 9 A B C D E 2 4
0 0 |
| 5.3¿
0.1.2¿ 3.4.5¿ 6.7.8¿ 9.A.B¿ C.D.E¿ ¿ 2.4¿ 1.2.3.2¿ 4.5.6.5¿ ¿ 0.0¿ |
| Blocks = 5 --- Disks = 3+1
*0011* 0000 0001 0010 0011 *0010* 0100 0101 0110 0111 *1001* 1000 1001 1010 1011 *1000* *1111* 1100 1101 1110 Blocks = 2 --- Disks = 4+1
|
| Blocks.=.5.---.Disks.=.3+1¿
.*0011*...0000....0001....0010¿ ..0011...*0010*...0100....0101¿ ..0110....0111...*1001*...1000¿ ..1001....1010....1011...*1000*¿ .*1111*...1100....1101....1110¿ ¿ Blocks.=.2.---.Disks.=.4+1¿ .*0010*...0001....0010....0011....0010¿ ..0100...*0010*...0101....0110....0101¿ ¿ |