IDA_new/jerasure/Examples/cauchy_04.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_04 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, "a 'good' matrix, created with cauchy_good_general_coding_matrix().\n");
  64   fprintf(stderr, "It converts this matrix to a bitmatrix.\n");
  65   fprintf(stderr, "\n");
  66   fprintf(stderr, "Then, it encodes w packets from each of k disks (simulated) onto w packets on\n");
  67   fprintf(stderr, "on each of m disks.  Packets are longs.  Then, it deletes m random disks, and decodes.\n");
  68   fprintf(stderr, "\n");
  69   fprintf(stderr, "The encoding and decoding are done twice, first, with jerasure_bitmatrix_encode()\n");
  70   fprintf(stderr, "and jerasure_bitmatrix_decode(), and second using 'smart' scheduling with\n");
  71   fprintf(stderr, "jerasure_schedule_encode() and jerasure_schedule_decode_lazy().\n");
  72
  73   fprintf(stderr, "\n");
  74   fprintf(stderr, "This demonstrates: cauchy_good_general_coding_matrix()\n");
  75   fprintf(stderr, "                   jerasure_bitmatrix_encode()\n");
  76   fprintf(stderr, "                   jerasure_bitmatrix_decode()\n");
  77   fprintf(stderr, "                   cauchy_n_ones()\n");
  78   fprintf(stderr, "                   jerasure_smart_bitmatrix_to_schedule()\n");
  79   fprintf(stderr, "                   jerasure_schedule_encode()\n");
  80   fprintf(stderr, "                   jerasure_schedule_decode_lazy()\n");
  81   fprintf(stderr, "                   jerasure_print_matrix()\n");
  82   fprintf(stderr, "                   jerasure_print_bitmatrix()\n");
  83   fprintf(stderr, "                   jerasure_get_stats()\n");
  84   if (s != NULL) fprintf(stderr, "%s\n", s);
  85   exit(1);
  86 }
  87
  88 static void print_array(char **ptrs, int ndevices, int size, int packetsize, char *label)
  89 {
  90   int i, j, x;
  91   unsigned char *up;
  92
  93   printf("<center><table border=3 cellpadding=3><tr><td></td>\n");
  94
  95   for (i = 0; i < ndevices; i++) printf("<td align=center>%s%x</td>\n", label, i);
  96   printf("</tr>\n");
  97   printf("<td align=right><pre>");
  98   for (j = 0; j < size/packetsize; j++) printf("Packet %d\n", j);
  99   printf("</pre></td>\n");
 100   for (i = 0; i < ndevices; i++) {
 101     printf("<td><pre>");
 102     up = (unsigned char *) ptrs[i];
 103     for (j = 0; j < size/packetsize; j++) {
 104       for (x = 0; x < packetsize; x++) {
 105         if (x > 0 && x%4 == 0) printf(" ");
 106         printf("%02x", up[j*packetsize+x]);
 107       }
 108       printf("\n");
 109     }
 110     printf("</td>\n");
 111   }
 112   printf("</tr></table></center>\n");
 113 }
 114
 115 int main(int argc, char **argv)
 116 {
 117   int k, w, i, m;
 118   int *matrix, *bitmatrix, **schedule;
 119   char **data, **coding, **dcopy, **ccopy;
 120   int no;
 121   int *erasures, *erased;
 122   double mstats[3], sstats[3];
 123   uint32_t seed;
 124
 125   if (argc != 5) usage(NULL);
 126   if (sscanf(argv[1], "%d", &k) == 0 || k <= 0) usage("Bad k");
 127   if (sscanf(argv[2], "%d", &m) == 0 || m <= 0) usage("Bad m");
 128   if (sscanf(argv[3], "%d", &w) == 0 || w <= 0 || w > 32) usage("Bad w");
 129   if (sscanf(argv[4], "%d", &seed) == 0) usage("Bad seed");
 130   if (w < 30 && (k+m) > (1 << w)) usage("k + m is too big");
 131
 132   matrix = cauchy_good_general_coding_matrix(k, m, w);
 133   if (matrix == NULL) {
 134     usage("couldn't make coding matrix");
 135   }
 136
 137   /* Print out header information to the output file. */
 138   printf("<HTML>\n");
 139   printf("<TITLE>Jerasure Example Output: cauchy_04 %d %d %d %d</TITLE>\n", k, m, w, seed);
 140   printf("<h2>Jerasure Example Output: cauchy_04 %d %d %d %d</h3>\n", k, m, w, seed);
 141
 142   printf("<hr>\n");
 143   printf("Parameters:\n");
 144   printf("<UL><LI> Number of data disks <i>(k)</i>: %d\n", k);
 145   printf("<LI> Number of coding disks <i>(m)</i>: %d\n", m);
 146   printf("<LI> Word size of the Galois Field: <i>(w)</i>: %d\n", w);
 147   printf("<LI> Seed for the random number generator: %d\n", seed);
 148   printf("<LI> Number of bytes stored per disk: %ld\n", sizeof(long)*w);
 149   printf("<LI> Number of packets stored per disk: %d\n", w);
 150   printf("<LI> Number of bytes per packet: %ld\n", sizeof(long));
 151   printf("</UL>\n");
 152
 153   /* Print out the matrix and the bitmatrix */
 154   printf("<hr>\n");
 155   printf("Here is the matrix, which was created with <b>cauchy_good_general_coding_matrix()</b>.\n");
 156
 157   printf("<pre>\n");
 158   jerasure_print_matrix(matrix, m, k, w);
 159   printf("</pre>\n");
 160
 161   bitmatrix = jerasure_matrix_to_bitmatrix(k, m, w, matrix);
 162
 163   no = 0;
 164   for (i = 0; i < k*m; i++) {
 165     no += cauchy_n_ones(matrix[i], w);
 166   }
 167
 168   printf("The bitmatrix, which has %d one%s:<p><pre>\n", no, (no == 1) ? "" : "s");
 169   jerasure_print_bitmatrix(bitmatrix, m*w, k*w, w);
 170   printf("</pre>\n");
 171   printf("<hr>\n");
 172
 173   MOA_Seed(seed);
 174
 175   data = talloc(char *, k);
 176   dcopy = talloc(char *, k);
 177   for (i = 0; i < k; i++) {
 178     data[i] = talloc(char, sizeof(long)*w);
 179     dcopy[i] = talloc(char, sizeof(long)*w);
 180     MOA_Fill_Random_Region(data[i], sizeof(long)*w);
 181     memcpy(dcopy[i], data[i], sizeof(long)*w);
 182   }
 183
 184   printf("Here are the packets on the data disks:<p>\n");
 185   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
 186
 187   coding = talloc(char *, m);
 188   ccopy = talloc(char *, m);
 189   for (i = 0; i < m; i++) {
 190     coding[i] = talloc(char, sizeof(long)*w);
 191     ccopy[i] = talloc(char, sizeof(long)*w);
 192   }
 193
 194   jerasure_bitmatrix_encode(k, m, w, bitmatrix, data, coding, w*sizeof(long), sizeof(long));
 195   jerasure_get_stats(mstats);
 196
 197   schedule = jerasure_smart_bitmatrix_to_schedule(k, m, w, bitmatrix);
 198   jerasure_schedule_encode(k, m, w, schedule, data, ccopy, w*sizeof(long), sizeof(long));
 199   jerasure_get_stats(sstats);
 200
 201   printf("<p>Encoding with jerasure_bitmatrix_encode() - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);
 202   printf("Encoding with jerasure_schedule_encode() - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);
 203
 204   for (i = 0; i < m; i++) {
 205     if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
 206       printf("Problem: the two encodings don't match on disk C%x\n", i);
 207       exit(0);
 208     }
 209   }
 210
 211   printf("Here are the packets on the coding disks.<br>\n");
 212   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
 213   printf("<hr>\n");
 214
 215   erasures = talloc(int, (m+1));
 216   erased = talloc(int, (k+m));
 217   for (i = 0; i < m+k; i++) erased[i] = 0;
 218   for (i = 0; i < m; ) {
 219     erasures[i] = MOA_Random_W(31, 1)%(k+m);
 220     if (erased[erasures[i]] == 0) {
 221       erased[erasures[i]] = 1;
 222       bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
 223       i++;
 224     }
 225   }
 226   erasures[i] = -1;
 227   printf("Erasures on the following devices:");
 228   for (i = 0; erasures[i] != -1; i++) {
 229     printf(" %c%x", ((erasures[i] < k) ? 'D' : 'C'), (erasures[i] < k ? erasures[i] : erasures[i]-k));
 230   }
 231   printf("<br>\nHere is the state of the system:\n<p>\n");
 232   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
 233   printf("<p>\n");
 234   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
 235   printf("<hr>\n");
 236
 237   jerasure_bitmatrix_decode(k, m, w, bitmatrix, 0, erasures, data, coding, w*sizeof(long), sizeof(long));
 238   jerasure_get_stats(mstats);
 239
 240   printf("<p>Decoded with jerasure_bitmatrix_decode - Bytes XOR'd: %.0lf.<br>\n", mstats[0]);
 241
 242   for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
 243     printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
 244   }
 245   for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
 246     printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
 247   }
 248
 249   for (i = 0; erasures[i] != -1; i++) {
 250     bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], sizeof(long)*w);
 251   }
 252
 253   jerasure_schedule_decode_lazy(k, m, w, bitmatrix, erasures, data, coding, w*sizeof(long), sizeof(long), 1);
 254   jerasure_get_stats(sstats);
 255
 256   printf("jerasure_schedule_decode_lazy - Bytes XOR'd: %.0lf.<br>\n", sstats[0]);
 257
 258   for (i = 0; i < k; i++) if (memcmp(data[i], dcopy[i], sizeof(long)*w) != 0) {
 259     printf("ERROR: D%x after decoding does not match its state before decoding!<br>\n", i);
 260   }
 261   for (i = 0; i < m; i++) if (memcmp(coding[i], ccopy[i], sizeof(long)*w) != 0) {
 262     printf("ERROR: C%x after decoding does not match its state before decoding!<br>\n", i);
 263   }
 264
 265   printf("Here is the state of the system:\n<p>\n");
 266   print_array(data, k, sizeof(long)*w, sizeof(long), "D");
 267   printf("<p>\n");
 268   print_array(coding, m, sizeof(long)*w, sizeof(long), "C");
 269   printf("<hr>\n");
 270
 271   return 0;
 272 }