]> AND Private Git Repository - Cipher_code.git/blob - IDA_new/jerasure/Examples/cauchy_03.c
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
add
[Cipher_code.git] / IDA_new / jerasure / Examples / cauchy_03.c
1 /* *
2  * Copyright (c) 2014, James S. Plank and Kevin Greenan
3  * All rights reserved.
4  *
5  * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure
6  * Coding Techniques
7  *
8  * Revision 2.0: Galois Field backend now links to GF-Complete
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
14  *  - Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions and the following disclaimer.
16  *
17  *  - Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in
19  *    the documentation and/or other materials provided with the
20  *    distribution.
21  *
22  *  - Neither the name of the University of Tennessee nor the names of its
23  *    contributors may be used to endorse or promote products derived
24  *    from this software without specific prior written permission.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
31  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
32  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
33  * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
34  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
36  * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37  * POSSIBILITY OF SUCH DAMAGE.
38  */
39
40 /* Jerasure's authors:
41  
42    Revision 2.x - 2014: James S. Plank and Kevin M. Greenan
43    Revision 1.2 - 2008: James S. Plank, Scott Simmerman and Catherine D. Schuman.
44    Revision 1.0 - 2007: James S. Plank
45  */
46
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <stdint.h>
50 #include <string.h>
51 #include <gf_rand.h>
52 #include "jerasure.h"
53 #include "cauchy.h"
54
55 #define talloc(type, num) (type *) malloc(sizeof(type)*(num))
56
57 static void usage(char *s)
58 {
59   fprintf(stderr, "usage: cauchy_03 k m w seed - CRS coding example improving the matrix.\n");
60   fprintf(stderr, "       \n");
61   fprintf(stderr, "k+m must be <= 2^w\n");
62   fprintf(stderr, "This sets up a generator matrix (G^T) in GF(2^w) whose last m rows are\n");
63   fprintf(stderr, "created from a Cauchy matrix, using the original definition from [Bloemer95].\n");
64   fprintf(stderr, "This is done with cauchy_xy_coding_matrix().\n");
65   fprintf(stderr, "\n");
66   fprintf(stderr, "It then it improves the matrix, which yields a different bitmatrix that is\n");
67   fprintf(stderr, "MDS like the original bitmatrix, but it will yield a bitmatrix with fewer ones.\n");
68   fprintf(stderr, "Then, it encodes w packets from each of k disks (simulated) onto w packets on\n");
69   fprintf(stderr, "on each of m disks.  Packets are longs.  Then, it deletes m random disks, and decodes.\n");
70   fprintf(stderr, "\n");
71   fprintf(stderr, "The encoding and decoding are done twice, first, with jerasure_bitmatrix_encode()\n");
72   fprintf(stderr, "and jerasure_bitmatrix_decode(), and second using 'smart' scheduling with\n");
73   fprintf(stderr, "jerasure_schedule_encode() and jerasure_schedule_decode_lazy().\n");
74
75   fprintf(stderr, "\n");
76   fprintf(stderr, "This demonstrates: cauchy_xy_coding_matrix()\n");
77   fprintf(stderr, "                   cauchy_improve_coding_matrix()\n");
78   fprintf(stderr, "                   jerasure_bitmatrix_encode()\n");
79   fprintf(stderr, "                   jerasure_bitmatrix_decode()\n");
80   fprintf(stderr, "                   cauchy_n_ones()\n");
81   fprintf(stderr, "                   jerasure_smart_bitmatrix_to_schedule()\n");
82   fprintf(stderr, "                   jerasure_schedule_encode()\n");
83   fprintf(stderr, "                   jerasure_schedule_decode_lazy()\n");
84   fprintf(stderr, "                   jerasure_print_matrix()\n");
85   fprintf(stderr, "                   jerasure_print_bitmatrix()\n");
86   fprintf(stderr, "                   jerasure_get_stats()\n");
87   if (s != NULL) fprintf(stderr, "%s\n", s);
88   exit(1);
89 }
90
91 static void print_array(char **ptrs, int ndevices, int size, int packetsize, char *label)
92 {
93   int i, j, x;
94   unsigned char *up;
95
96   printf("<center><table border=3 cellpadding=3><tr><td></td>\n");
97   
98   for (i = 0; i < ndevices; i++) printf("<td align=center>%s%x</td>\n", label, i);
99   printf("</tr>\n");
100   printf("<td align=right><pre>");
101   for (j = 0; j < size/packetsize; j++) printf("Packet %d\n", j);
102   printf("</pre></td>\n");
103   for (i = 0; i < ndevices; i++) {
104     printf("<td><pre>");
105     up = (unsigned char *) ptrs[i];
106     for (j = 0; j < size/packetsize; j++) {
107       for (x = 0; x < packetsize; x++) {
108         if (x > 0 && x%4 == 0) printf(" ");
109         printf("%02x", up[j*packetsize+x]);
110       }
111       printf("\n");
112     }
113     printf("</td>\n");
114   }
115   printf("</tr></table></center>\n");
116 }
117
118 int main(int argc, char **argv)
119 {
120   int k, w, i, m;
121   int *matrix, *bitmatrix, **schedule;
122   char **data, **coding, **dcopy, **ccopy;
123   int no;
124   int *erasures, *erased;
125   double mstats[3], sstats[3];
126   uint32_t seed;
127   int *X, *Y;
128   
129   if (argc != 5) usage(NULL);
130   if (sscanf(argv[1], "%d", &k) == 0 || k <= 0) usage("Bad k");
131   if (sscanf(argv[2], "%d", &m) == 0 || m <= 0) usage("Bad m");
132   if (sscanf(argv[3], "%d", &w) == 0 || w <= 0 || w > 32) usage("Bad w");
133   if (sscanf(argv[4], "%d", &seed) == 0) usage("Bad seed");
134   if (w < 30 && (k+m) > (1 << w)) usage("k + m is too big");
135
136   X = talloc(int, m);
137   Y = talloc(int, k);
138   for (i = 0; i < m; i++) X[i] = i;
139   for (i = 0; i < k; i++) Y[i] = m+i;
140
141   matrix = cauchy_xy_coding_matrix(k, m, w, X, Y);
142   if (matrix == NULL) {
143     usage("couldn't make coding matrix");
144   }
145
146   /* Print out header information to the output file. */
147   printf("<HTML>\n");
148   printf("<TITLE>Jerasure Example Output: cauchy_03 %d %d %d %d</TITLE>\n", k, m, w, seed);
149   printf("<h2>Jerasure Example Output: cauchy_03 %d %d %d %d</h3>\n", k, m, w, seed);
150
151   printf("<hr>\n");
152   printf("Parameters:\n");
153   printf("<UL><LI> Number of data disks <i>(k)</i>: %d\n", k);
154   printf("<LI> Number of coding disks <i>(m)</i>: %d\n", m);
155   printf("<LI> Word size of the Galois Field: <i>(w)</i>: %d\n", w);
156   printf("<LI> Seed for the random number generator: %d\n", seed);
157   printf("<LI> Number of bytes stored per disk: %ld\n", sizeof(long)*w);
158   printf("<LI> Number of packets stored per disk: %d\n", w);
159   printf("<LI> Number of bytes per packet: %ld\n", sizeof(long));
160   printf("</UL>\n");
161
162   /* Print out the matrix and the bitmatrix */
163   printf("<hr>\n");
164   printf("Here is the matrix, which was created with <b>cauchy_xy_coding_matrix()</b>.\n");
165
166   printf("<pre>\n");
167   jerasure_print_matrix(matrix, m, k, w);
168   printf("</pre>\n");
169
170   cauchy_improve_coding_matrix(k, m, w, matrix);
171
172   printf("<hr>\n");
173   printf("Here is the matrix improved with <b>cauchy_improve_coding_matrix()</b>.\n");
174
175   printf("<pre>\n");
176   jerasure_print_matrix(matrix, m, k, w);
177   printf("</pre>\n");
178
179   bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
180
181   no = 0;
182   for (i = 0; i < k*m; i++) {
183     no += cauchy_n_ones(matrix[i], w);
184   }
185
186   printf("The bitmatrix, which has %d one%s:<p><pre>\n", no, (no == 1) ? "" : "s");
187   jerasure_print_bitmatrix(bitmatrix, m*w, k*w, w);
188   printf("</pre>\n");
189   printf("<hr>\n");
190
191   MOA_Seed(seed);
192
193   data = talloc(char *, k);
194   dcopy = talloc(char *, k);
195   for (i = 0; i < k; i++) {
196     data[i] = talloc(char, sizeof(long)*w);
197     dcopy[i] = talloc(char, sizeof(long)*w);
198     MOA_Fill_Random_Region(data[i], sizeof(long)*w);
199     memcpy(dcopy[i], data[i], sizeof(long)*w);
200   }
201
202   printf("Here are the packets on the data disks:<p>\n");
203   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
204
205   coding = talloc(char *, m);
206   ccopy = talloc(char *, m);
207   for (i = 0; i < m; i++) {
208     coding[i] = talloc(char, sizeof(long)*w);
209     ccopy[i] = talloc(char, sizeof(long)*w);
210   }
211
212   jerasure_bitmatrix_encode(k, m, w, bitmatrix, data, coding, w*sizeof(long), sizeof(long));
213   jerasure_get_stats(mstats);
214
215   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
216   jerasure_schedule_encode(k, m, w, schedule, data, ccopy, w*sizeof(long), sizeof(long));
217   jerasure_get_stats(sstats);
218
219   printf("<p>Encoding with jerasure_bitmatrix_encode() - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);
220   printf("Encoding with jerasure_schedule_encode() - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);
221
222   for (i = 0; i < m; i++) {
223     if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
224       printf("Problem: the two encodings don't match on disk C%x\n", i);
225       exit(0);
226     }
227   }
228
229   printf("Here are the packets on the coding disks.<br>\n");
230   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
231   printf("<hr>\n");
232
233   erasures = talloc(int, (m+1));
234   erased = talloc(int, (k+m));
235   for (i = 0; i < m+k; i++) erased[i] = 0;
236   for (i = 0; i < m; ) {
237     erasures[i] = MOA_Random_W(31, 1)%(k+m);
238     if (erased[erasures[i]] == 0) {
239       erased[erasures[i]] = 1;
240       bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
241       i++;
242     }
243   }
244   erasures[i] = -1;
245   printf("Erasures on the following devices:");
246   for (i = 0; erasures[i] != -1; i++) {
247     printf(" %c%x", ((erasures[i] < k) ? 'D' : 'C'), (erasures[i] < k ? erasures[i] : erasures[i]-k));
248   }
249   printf("<br>\nHere is the state of the system:\n<p>\n");
250   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
251   printf("<p>\n");
252   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
253   printf("<hr>\n");
254
255   jerasure_bitmatrix_decode(k, m, w, bitmatrix, 0, erasures, data, coding, w*sizeof(long), sizeof(long));
256   jerasure_get_stats(mstats);
257
258   printf("<p>Decoded with jerasure_bitmatrix_decode - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);
259
260   for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
261     printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
262   }
263   for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
264     printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
265   }
266
267   for (i = 0; erasures[i] != -1; i++) {
268     bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
269   }
270
271   jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, coding, w*sizeof(long), sizeof(long), 1);
272   jerasure_get_stats(sstats);
273
274   printf("jerasure_schedule_decode_lazy - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);
275
276   for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
277     printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
278   }
279   for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
280     printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
281   }
282
283   printf("Here is the state of the system:\n<p>\n");
284   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
285   printf("<p>\n");
286   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
287   printf("<hr>\n");
288
289   return 0;
290 }