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