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 }