Blame view

Examples/cauchy_03.c 11 KB
44201cf4   KMG   Added new license...
1
/* *
be40b4e5   Jim Plank   Revision 2.0 is r...
2
 * Copyright (c) 2014, James S. Plank and Kevin Greenan
44201cf4   KMG   Added new license...
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 * All rights reserved.
 *
 * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure
 * Coding Techniques
 *
 * Revision 2.0: Galois Field backend now links to GF-Complete
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *  - Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 *  - Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 *  - Neither the name of the University of Tennessee nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
b5745fa4   Jim Plank   Adding the curren...
38
39
 */

be40b4e5   Jim Plank   Revision 2.0 is r...
40
41
42
43
44
45
46
/* Jerasure's authors:
 
   Revision 2.x - 2014: James S. Plank and Kevin M. Greenan
   Revision 1.2 - 2008: James S. Plank, Scott Simmerman and Catherine D. Schuman.
   Revision 1.0 - 2007: James S. Plank
 */

b5745fa4   Jim Plank   Adding the curren...
47
48
#include <stdio.h>
#include <stdlib.h>
9124ad13   Jim Plank   Ran through all o...
49
#include <stdint.h>
b5745fa4   Jim Plank   Adding the curren...
50
#include <string.h>
9124ad13   Jim Plank   Ran through all o...
51
#include <gf_rand.h>
b5745fa4   Jim Plank   Adding the curren...
52
53
54
55
56
#include "jerasure.h"
#include "cauchy.h"

#define talloc(type, num) (type *) malloc(sizeof(type)*(num))

e79904ea   David Glessner   This is the squas...
57
static void usage(char *s)
b5745fa4   Jim Plank   Adding the curren...
58
{
9124ad13   Jim Plank   Ran through all o...
59
  fprintf(stderr, "usage: cauchy_03 k m w seed - CRS coding example improving the matrix.\n");
b5745fa4   Jim Plank   Adding the curren...
60
  fprintf(stderr, "       \n");
9124ad13   Jim Plank   Ran through all o...
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
  fprintf(stderr, "k+m must be <= 2^w\n");
  fprintf(stderr, "This sets up a generator matrix (G^T) in GF(2^w) whose last m rows are\n");
  fprintf(stderr, "created from a Cauchy matrix, using the original definition from [Bloemer95].\n");
  fprintf(stderr, "This is done with cauchy_xy_coding_matrix().\n");
  fprintf(stderr, "\n");
  fprintf(stderr, "It then it improves the matrix, which yields a different bitmatrix that is\n");
  fprintf(stderr, "MDS like the original bitmatrix, but it will yield a bitmatrix with fewer ones.\n");
  fprintf(stderr, "Then, it encodes w packets from each of k disks (simulated) onto w packets on\n");
  fprintf(stderr, "on each of m disks.  Packets are longs.  Then, it deletes m random disks, and decodes.\n");
  fprintf(stderr, "\n");
  fprintf(stderr, "The encoding and decoding are done twice, first, with jerasure_bitmatrix_encode()\n");
  fprintf(stderr, "and jerasure_bitmatrix_decode(), and second using 'smart' scheduling with\n");
  fprintf(stderr, "jerasure_schedule_encode() and jerasure_schedule_decode_lazy().\n");

  fprintf(stderr, "\n");
  fprintf(stderr, "This demonstrates: cauchy_xy_coding_matrix()\n");
b5745fa4   Jim Plank   Adding the curren...
77
  fprintf(stderr, "                   cauchy_improve_coding_matrix()\n");
9124ad13   Jim Plank   Ran through all o...
78
79
  fprintf(stderr, "                   jerasure_bitmatrix_encode()\n");
  fprintf(stderr, "                   jerasure_bitmatrix_decode()\n");
b5745fa4   Jim Plank   Adding the curren...
80
81
82
83
84
  fprintf(stderr, "                   cauchy_n_ones()\n");
  fprintf(stderr, "                   jerasure_smart_bitmatrix_to_schedule()\n");
  fprintf(stderr, "                   jerasure_schedule_encode()\n");
  fprintf(stderr, "                   jerasure_schedule_decode_lazy()\n");
  fprintf(stderr, "                   jerasure_print_matrix()\n");
9124ad13   Jim Plank   Ran through all o...
85
  fprintf(stderr, "                   jerasure_print_bitmatrix()\n");
b5745fa4   Jim Plank   Adding the curren...
86
87
88
89
90
  fprintf(stderr, "                   jerasure_get_stats()\n");
  if (s != NULL) fprintf(stderr, "%s\n", s);
  exit(1);
}

e79904ea   David Glessner   This is the squas...
91
static void print_array(char **ptrs, int ndevices, int size, int packetsize, char *label)
b5745fa4   Jim Plank   Adding the curren...
92
{
9124ad13   Jim Plank   Ran through all o...
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
  int i, j, x;
  unsigned char *up;

  printf("<center><table border=3 cellpadding=3><tr><td></td>\n");
  
  for (i = 0; i < ndevices; i++) printf("<td align=center>%s%x</td>\n", label, i);
  printf("</tr>\n");
  printf("<td align=right><pre>");
  for (j = 0; j < size/packetsize; j++) printf("Packet %d\n", j);
  printf("</pre></td>\n");
  for (i = 0; i < ndevices; i++) {
    printf("<td><pre>");
    up = (unsigned char *) ptrs[i];
    for (j = 0; j < size/packetsize; j++) {
      for (x = 0; x < packetsize; x++) {
        if (x > 0 && x%4 == 0) printf(" ");
        printf("%02x", up[j*packetsize+x]);
      }
      printf("\n");
    }
    printf("</td>\n");
  }
  printf("</tr></table></center>\n");
b5745fa4   Jim Plank   Adding the curren...
116
117
118
119
}

int main(int argc, char **argv)
{
e79904ea   David Glessner   This is the squas...
120
  int k, w, i, m;
9124ad13   Jim Plank   Ran through all o...
121
  int *matrix, *bitmatrix, **schedule;
e79904ea   David Glessner   This is the squas...
122
  char **data, **coding, **dcopy, **ccopy;
b5745fa4   Jim Plank   Adding the curren...
123
124
  int no;
  int *erasures, *erased;
9124ad13   Jim Plank   Ran through all o...
125
126
127
  double mstats[3], sstats[3];
  uint32_t seed;
  int *X, *Y;
b5745fa4   Jim Plank   Adding the curren...
128
  
9124ad13   Jim Plank   Ran through all o...
129
  if (argc != 5) usage(NULL);
b5745fa4   Jim Plank   Adding the curren...
130
131
132
  if (sscanf(argv[1], "%d", &k) == 0 || k <= 0) usage("Bad k");
  if (sscanf(argv[2], "%d", &m) == 0 || m <= 0) usage("Bad m");
  if (sscanf(argv[3], "%d", &w) == 0 || w <= 0 || w > 32) usage("Bad w");
9124ad13   Jim Plank   Ran through all o...
133
  if (sscanf(argv[4], "%d", &seed) == 0) usage("Bad seed");
b5745fa4   Jim Plank   Adding the curren...
134
135
  if (w < 30 && (k+m) > (1 << w)) usage("k + m is too big");

9124ad13   Jim Plank   Ran through all o...
136
137
138
139
140
141
  X = talloc(int, m);
  Y = talloc(int, k);
  for (i = 0; i < m; i++) X[i] = i;
  for (i = 0; i < k; i++) Y[i] = m+i;

  matrix = cauchy_xy_coding_matrix(k, m, w, X, Y);
b5745fa4   Jim Plank   Adding the curren...
142
143
144
145
  if (matrix == NULL) {
    usage("couldn't make coding matrix");
  }

9124ad13   Jim Plank   Ran through all o...
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
  /* Print out header information to the output file. */
  printf("<HTML>\n");
  printf("<TITLE>Jerasure Example Output: cauchy_03 %d %d %d %d</TITLE>\n", k, m, w, seed);
  printf("<h2>Jerasure Example Output: cauchy_03 %d %d %d %d</h3>\n", k, m, w, seed);

  printf("<hr>\n");
  printf("Parameters:\n");
  printf("<UL><LI> Number of data disks <i>(k)</i>: %d\n", k);
  printf("<LI> Number of coding disks <i>(m)</i>: %d\n", m);
  printf("<LI> Word size of the Galois Field: <i>(w)</i>: %d\n", w);
  printf("<LI> Seed for the random number generator: %d\n", seed);
  printf("<LI> Number of bytes stored per disk: %ld\n", sizeof(long)*w);
  printf("<LI> Number of packets stored per disk: %d\n", w);
  printf("<LI> Number of bytes per packet: %ld\n", sizeof(long));
  printf("</UL>\n");

  /* Print out the matrix and the bitmatrix */
  printf("<hr>\n");
  printf("Here is the matrix, which was created with <b>cauchy_xy_coding_matrix()</b>.\n");

  printf("<pre>\n");
  jerasure_print_matrix(matrix, m, k, w);
  printf("</pre>\n");

b5745fa4   Jim Plank   Adding the curren...
170
  cauchy_improve_coding_matrix(k, m, w, matrix);
9124ad13   Jim Plank   Ran through all o...
171
172
173
174
175
176
177
178
179
180

  printf("<hr>\n");
  printf("Here is the matrix improved with <b>cauchy_improve_coding_matrix()</b>.\n");

  printf("<pre>\n");
  jerasure_print_matrix(matrix, m, k, w);
  printf("</pre>\n");

  bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);

b5745fa4   Jim Plank   Adding the curren...
181
182
183
184
  no = 0;
  for (i = 0; i < k*m; i++) {
    no += cauchy_n_ones(matrix[i], w);
  }
b5745fa4   Jim Plank   Adding the curren...
185

9124ad13   Jim Plank   Ran through all o...
186
187
188
189
190
191
  printf("The bitmatrix, which has %d one%s:<p><pre>\n", no, (no == 1) ? "" : "s");
  jerasure_print_bitmatrix(bitmatrix, m*w, k*w, w);
  printf("</pre>\n");
  printf("<hr>\n");

  MOA_Seed(seed);
b5745fa4   Jim Plank   Adding the curren...
192

b5745fa4   Jim Plank   Adding the curren...
193
  data = talloc(char *, k);
9124ad13   Jim Plank   Ran through all o...
194
  dcopy = talloc(char *, k);
b5745fa4   Jim Plank   Adding the curren...
195
196
  for (i = 0; i < k; i++) {
    data[i] = talloc(char, sizeof(long)*w);
9124ad13   Jim Plank   Ran through all o...
197
198
199
    dcopy[i] = talloc(char, sizeof(long)*w);
    MOA_Fill_Random_Region(data[i], sizeof(long)*w);
    memcpy(dcopy[i], data[i], sizeof(long)*w);
b5745fa4   Jim Plank   Adding the curren...
200
201
  }

9124ad13   Jim Plank   Ran through all o...
202
203
204
  printf("Here are the packets on the data disks:<p>\n");
  print_array(data, k, sizeof(long)*w, sizeof(long), "D");

b5745fa4   Jim Plank   Adding the curren...
205
  coding = talloc(char *, m);
9124ad13   Jim Plank   Ran through all o...
206
  ccopy = talloc(char *, m);
b5745fa4   Jim Plank   Adding the curren...
207
208
  for (i = 0; i < m; i++) {
    coding[i] = talloc(char, sizeof(long)*w);
9124ad13   Jim Plank   Ran through all o...
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
    ccopy[i] = talloc(char, sizeof(long)*w);
  }

  jerasure_bitmatrix_encode(k, m, w, bitmatrix, data, coding, w*sizeof(long), sizeof(long));
  jerasure_get_stats(mstats);

  schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
  jerasure_schedule_encode(k, m, w, schedule, data, ccopy, w*sizeof(long), sizeof(long));
  jerasure_get_stats(sstats);

  printf("<p>Encoding with jerasure_bitmatrix_encode() - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);
  printf("Encoding with jerasure_schedule_encode() - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);

  for (i = 0; i < m; i++) {
    if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
      printf("Problem: the two encodings don't match on disk C%x\n", i);
      exit(0);
    }
b5745fa4   Jim Plank   Adding the curren...
227
228
  }

9124ad13   Jim Plank   Ran through all o...
229
230
231
  printf("Here are the packets on the coding disks.<br>\n");
  print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
  printf("<hr>\n");
b5745fa4   Jim Plank   Adding the curren...
232
233
234
235
236

  erasures = talloc(int, (m+1));
  erased = talloc(int, (k+m));
  for (i = 0; i < m+k; i++) erased[i] = 0;
  for (i = 0; i < m; ) {
9124ad13   Jim Plank   Ran through all o...
237
    erasures[i] = MOA_Random_W(31, 1)%(k+m);
b5745fa4   Jim Plank   Adding the curren...
238
239
240
241
242
243
244
    if (erased[erasures[i]] == 0) {
      erased[erasures[i]] = 1;
      bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
      i++;
    }
  }
  erasures[i] = -1;
9124ad13   Jim Plank   Ran through all o...
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
  printf("Erasures on the following devices:");
  for (i = 0; erasures[i] != -1; i++) {
    printf(" %c%x", ((erasures[i] < k) ? 'D' : 'C'), (erasures[i] < k ? erasures[i] : erasures[i]-k));
  }
  printf("<br>\nHere is the state of the system:\n<p>\n");
  print_array(data, k, sizeof(long)*w, sizeof(long), "D");
  printf("<p>\n");
  print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
  printf("<hr>\n");

  jerasure_bitmatrix_decode(k, m, w, bitmatrix, 0, erasures, data, coding, w*sizeof(long), sizeof(long));
  jerasure_get_stats(mstats);

  printf("<p>Decoded with jerasure_bitmatrix_decode - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);

  for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
    printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
  }
  for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
    printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
  }

  for (i = 0; erasures[i] != -1; i++) {
    bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
  }
b5745fa4   Jim Plank   Adding the curren...
270

b5745fa4   Jim Plank   Adding the curren...
271
  jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, coding, w*sizeof(long), sizeof(long), 1);
9124ad13   Jim Plank   Ran through all o...
272
  jerasure_get_stats(sstats);
b5745fa4   Jim Plank   Adding the curren...
273

9124ad13   Jim Plank   Ran through all o...
274
275
276
277
278
279
280
281
  printf("jerasure_schedule_decode_lazy - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);

  for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
    printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
  }
  for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
    printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
  }
b5745fa4   Jim Plank   Adding the curren...
282

9124ad13   Jim Plank   Ran through all o...
283
284
285
286
287
  printf("Here is the state of the system:\n<p>\n");
  print_array(data, k, sizeof(long)*w, sizeof(long), "D");
  printf("<p>\n");
  print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
  printf("<hr>\n");
e79904ea   David Glessner   This is the squas...
288
289

  return 0;
b5745fa4   Jim Plank   Adding the curren...
290
}