1 /*\
2 |*| Parity Archive - A way to restore missing files in a set.
3 |*|
4 |*| Copyright (C) 2001 Willem Monsuwe (willem@stack.nl)
5 |*|
6 |*| File format by Stefan Wehlus -
7 |*| initial idea by Tobias Rieper, further suggestions by Kilroy Balore
8 |*|
9 |*| Reed-Solomon coding
10 \*/
11
12 #include <stdio.h>
13 #include <string.h>
14 #include "types.h"
15 #include "fileops.h"
16 #include "rs.h"
17 #include "util.h"
18 #include "par.h"
19
20 /*\
21 |*| Calculations over a Galois Field, GF(8)
22 \*/
23
24 u8 gl[0x100], ge[0x200];
25
26 /*\ Multiply: a*b = exp(log(a) + log(b)) \*/
27 static int
gmul(int a,int b)28 gmul(int a, int b)
29 {
30 if ((a == 0) || (b == 0)) return 0;
31 return ge[gl[a] + gl[b]];
32 }
33
34 /*\ Divide: a/b = exp(log(a) - log(b)) \*/
35 static int
gdiv(int a,int b)36 gdiv(int a, int b)
37 {
38 if ((a == 0) || (b == 0)) return 0;
39 return ge[gl[a] - gl[b] + 255];
40 }
41
42 /*\ Power: a^b = exp(log(a) * b) \*/
43 static int
gpow(int a,int b)44 gpow(int a, int b)
45 {
46 if (a == 0) return 0;
47 return ge[(gl[a] * b) % 255];
48 }
49
50 /*\ Initialise log and exp tables using generator x^8 + x^4 + x^3 + x^2 + 1 \*/
51 void
ginit(void)52 ginit(void)
53 {
54 unsigned int b, l;
55
56 b = 1;
57 for (l = 0; l < 0xff; l++) {
58 gl[b] = l;
59 ge[l] = b;
60 b += b;
61 if (b & 0x100) b ^= 0x11d;
62 }
63 for (l = 0xff; l < 0x200; l++)
64 ge[l] = ge[l - 0xff];
65 }
66
67 /*\ Fill in a LUT \*/
68 static void
make_lut(u8 lut[0x100],int m)69 make_lut(u8 lut[0x100], int m)
70 {
71 int j;
72 for (j = 0x100; --j; )
73 lut[j] = ge[gl[m] + gl[j]];
74 lut[0] = 0;
75 }
76
77 #define MT(i,j) (mt[((i) * Q) + (j)])
78 #define IMT(i,j) (imt[((i) * N) + (j)])
79 #define MULS(i,j) (muls[((i) * N) + (j)])
80
81 int
recreate(xfile_t * in,xfile_t * out)82 recreate(xfile_t *in, xfile_t *out)
83 {
84 int i, j, k, l, M, N, Q, R;
85 u8 *mt, *imt, *muls;
86 u8 buf[0x10000], *work;
87 i64 s, size;
88 i64 perc;
89
90 ginit();
91
92 /*\ Count number of recovery files \*/
93 for (i = Q = R = 0; in[i].filenr; i++) {
94 if (in[i].files) {
95 R++;
96 /*\ Get max. matrix row size \*/
97 for (k = 0; in[i].files[k]; k++) {
98 if (in[i].files[k] > Q)
99 Q = in[i].files[k];
100 }
101 } else {
102 if (in[i].filenr > Q)
103 Q = in[i].filenr;
104 }
105 }
106 N = i;
107
108 /*\ Count number of volumes to output \*/
109 for (i = j = M = 0; out[i].filenr; i++) {
110 M++;
111 if (out[i].files) {
112 j++;
113 /*\ Get max. matrix row size \*/
114 for (k = 0; out[i].files[k]; k++) {
115 if (out[i].files[k] > Q)
116 Q = out[i].files[k];
117 }
118 } else {
119 if (out[i].filenr > Q)
120 Q = out[i].filenr;
121 }
122 }
123 R += j;
124 Q += j;
125
126 CNEW(mt, R * Q);
127 CNEW(imt, R * N);
128
129 /*\ Fill in matrix rows for recovery files \*/
130 for (i = j = 0; in[i].filenr; i++) {
131 if (!in[i].files)
132 continue;
133 for (k = 0; in[i].files[k]; k++)
134 MT(j, in[i].files[k]-1) = gpow(k+1, in[i].filenr - 1);
135 IMT(j, i) = 1;
136 j++;
137 }
138
139 /*\ Fill in matrix rows for output recovery files \*/
140 for (i = 0, l = Q; out[i].filenr; i++) {
141 if (!out[i].files)
142 continue;
143 for (k = 0; out[i].files[k]; k++)
144 MT(j, out[i].files[k]-1) = gpow(k+1, out[i].filenr - 1);
145 --l;
146 /*\ Fudge filenr \*/
147 out[i].filenr = l + 1;
148 MT(j, l) = 1;
149 j++;
150 }
151
152 if (cmd.loglevel > 0) {
153 fprintf(stderr, "Matrix input:\n");
154 for (i = 0; i < R; i++) {
155 fprintf(stderr, "| ");
156 for (j = 0; j < Q; j++)
157 fprintf(stderr, "%02x ", MT(i, j));
158 fprintf(stderr, "| ");
159 for (j = 0; j < N; j++)
160 fprintf(stderr, "%02x ", IMT(i, j));
161 fprintf(stderr, "|\n");
162 }
163 }
164
165 /*\ Use (virtual) rows from data files to eliminate columns \*/
166 for (i = 0; in[i].filenr; i++) {
167 if (in[i].files)
168 continue;
169 k = in[i].filenr - 1;
170 /*\ MT would have a 1 at (i, k), IMT a 1 at (i, i)
171 |*| IMT(j,i) -= MT(j,k) * IMT(i,i) (is MT(j, k))
172 |*| MT(j,k) -= MT(j,k) * MT(i,k) (becomes 0)
173 \*/
174 for (j = 0; j < R; j++) {
175 IMT(j, i) ^= MT(j, k);
176 MT(j, k) = 0;
177 }
178 }
179
180 if (cmd.loglevel > 0) {
181 fprintf(stderr, "Matrix after data file elimination:\n");
182 for (i = 0; i < R; i++) {
183 fprintf(stderr, "| ");
184 for (j = 0; j < Q; j++)
185 fprintf(stderr, "%02x ", MT(i, j));
186 fprintf(stderr, "| ");
187 for (j = 0; j < N; j++)
188 fprintf(stderr, "%02x ", IMT(i, j));
189 fprintf(stderr, "|\n");
190 }
191 }
192
193 /*\ Eliminate columns using the remaining rows, so we get I.
194 |*| The accompanying matrix will be the inverse
195 \*/
196 for (i = 0; i < R; i++) {
197 int d, l;
198 /*\ Find first non-zero entry \*/
199 for (l = 0; (l < Q) && !MT(i, l); l++)
200 ;
201 if (l == Q) continue;
202 d = MT(i, l);
203 /*\ Scale the matrix so MT(i, l) becomes 1 \*/
204 for (j = 0; j < Q; j++)
205 MT(i, j) = gdiv(MT(i, j), d);
206 for (j = 0; j < N; j++)
207 IMT(i, j) = gdiv(IMT(i, j), d);
208 /*\ Eliminate the column in the other matrices \*/
209 for (k = 0; k < R; k++) {
210 if (k == i) continue;
211 d = MT(k, l);
212 for (j = 0; j < Q; j++)
213 MT(k, j) ^= gmul(MT(i, j), d);
214 for (j = 0; j < N; j++)
215 IMT(k, j) ^= gmul(IMT(i, j), d);
216 }
217 }
218
219 if (cmd.loglevel > 0) {
220 fprintf(stderr, "Matrix after gaussian elimination:\n");
221 for (i = 0; i < R; i++) {
222 fprintf(stderr, "| ");
223 for (j = 0; j < Q; j++)
224 fprintf(stderr, "%02x ", MT(i, j));
225 fprintf(stderr, "| ");
226 for (j = 0; j < N; j++)
227 fprintf(stderr, "%02x ", IMT(i, j));
228 fprintf(stderr, "|\n");
229 }
230 }
231
232 /*\ Make the multiplication tables \*/
233 CNEW(muls, M * N);
234
235 for (i = 0; out[i].filenr; i++) {
236 /*\ File #x: The row IMT(j) for which MT(j,x) = 1 \*/
237 for (j = 0; j < R; j++) {
238 k = out[i].filenr - 1;
239 if (MT(j, k) != 1)
240 continue;
241 /*\ All other values should be 0 \*/
242 for (k = 0; !MT(j, k); k++)
243 ;
244 if (k != out[i].filenr - 1)
245 continue;
246 for (k++; (k < Q) && !MT(j, k); k++)
247 ;
248 if (k != Q)
249 continue;
250 break;
251 }
252 /*\ Did we find a suitable row ? \*/
253 if (j == R) {
254 out[i].size = 0;
255 continue;
256 }
257 for (k = 0; k < N; k++)
258 MULS(i, k) = IMT(j, k);
259 }
260 free(mt);
261 free(imt);
262
263 if (cmd.loglevel > 0) {
264 fprintf(stderr, "Multipliers:\n");
265 for (i = 0; i < M; i++) {
266 fprintf(stderr, "| ");
267 for (j = 0; j < N; j++)
268 fprintf(stderr, "%02x ", MULS(i, j));
269 fprintf(stderr, "|\n");
270 }
271 }
272
273 /*\ Check for columns with all-zeroes \*/
274 for (j = 0; j < N; j++) {
275 for (i = 0; i < M; i++)
276 if (MULS(i, j))
277 break;
278 /*\ This input file isn't used \*/
279 if (i == M)
280 in[j].size = 0;
281 }
282
283 /*\ Find out how much we should process in total \*/
284 size = 0;
285 for (i = 0; out[i].filenr; i++)
286 if (size < out[i].size)
287 size = out[i].size;
288
289 /*\ Restore all the files at once \*/
290 NEW(work, sizeof(buf) * M);
291
292 perc = 0;
293 fprintf(stderr, "0%%"); fflush(stderr);
294 /*\ Process all files \*/
295 for (s = 0; s < size; ) {
296 i64 tr, r, q;
297 u8 *p;
298
299 /*\ Display progress \*/
300 while (((s * 50) / size) > perc) {
301 perc++;
302 if (perc % 5) fprintf(stderr, ".");
303 else fprintf(stderr, "%lld%%", (perc / 5) * 10);
304 fflush(stderr);
305 }
306
307 /*\ See how much we should read \*/
308 memset(work, 0, sizeof(buf) * M);
309 for (i = 0; in[i].filenr; i++) {
310 tr = sizeof(buf);
311 if (tr > (in[i].size - s))
312 tr = in[i].size - s;
313 if (tr <= 0)
314 continue;
315 r = file_read(in[i].f, buf, tr);
316 if (r < tr) {
317 perror("READ ERROR");
318 free(muls);
319 free(work);
320 return 0;
321 }
322 for (j = 0; out[j].filenr; j++) {
323 u8 lut[0x100];
324 if (s >= out[j].size) continue;
325 if (!MULS(j, i)) continue;
326 /*\ Precalc LUT \*/
327 make_lut(lut, MULS(j, i));
328 p = work + (j * sizeof(buf));
329 /*\ XOR it in, passed through the LUTs \*/
330 for (q = r; --q >= 0; )
331 p[q] ^= lut[buf[q]];
332 }
333 }
334 for (j = 0; out[j].filenr; j++) {
335 if (s >= out[j].size) continue;
336 tr = sizeof(buf);
337 if (tr > (out[j].size - s))
338 tr = out[j].size - s;
339 r = file_write(out[j].f, work + (j * sizeof(buf)), tr);
340 if (r < tr) {
341 perror("WRITE ERROR");
342 free(muls);
343 free(work);
344 return 0;
345 }
346 }
347 s += sizeof(buf);
348 }
349 fprintf(stderr, "100%%\n"); fflush(stderr);
350 free(muls);
351 free(work);
352 return 1;
353 }
354