IDA_new/jerasure/Examples/jerasure_05.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 <stdint.h>
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50 #include <string.h>
  51 #include <gf_rand.h>
  52 #include "jerasure.h"
  53
  54 #define talloc(type, num) (type *) malloc(sizeof(type)*(num))
  55
  56 static void usage(char *s)
  57 {
  58   fprintf(stderr, "usage: jerasure_05 k m w size seed - Does a simple Reed-Solomon coding example in GF(2^w).\n");
  59   fprintf(stderr, "       \n");
  60   fprintf(stderr, "       k+m must be <= 2^w.  w can be 8, 16 or 32.\n");
  61   fprintf(stderr, "       It sets up a Cauchy generator matrix and encodes\n");
  62   fprintf(stderr, "       k devices of size bytes with it.  Then it decodes.\n");
  63   fprintf(stderr, "       After that, it decodes device 0 by using jerasure_make_decoding_matrix()\n");
  64   fprintf(stderr, "       and jerasure_matrix_dotprod().\n");
  65   fprintf(stderr, "       \n");
  66   fprintf(stderr, "This demonstrates: jerasure_matrix_encode()\n");
  67   fprintf(stderr, "                   jerasure_matrix_decode()\n");
  68   fprintf(stderr, "                   jerasure_print_matrix()\n");
  69   fprintf(stderr, "                   jerasure_make_decoding_matrix()\n");
  70   fprintf(stderr, "                   jerasure_matrix_dotprod()\n");
  71   if (s != NULL) fprintf(stderr, "\n%s\n\n", s);
  72   exit(1);
  73 }
  74
  75 static void print_data_and_coding(int k, int m, int w, int size,
  76                 char **data, char **coding)
  77 {
  78   int i, j, x;
  79   int n, sp;
  80
  81   if(k > m) n = k;
  82   else n = m;
  83   sp = size * 2 + size/(w/8) + 8;
  84
  85   printf("%-*sCoding\n", sp, "Data");
  86   for(i = 0; i < n; i++) {
  87           if(i < k) {
  88                   printf("D%-2d:", i);
  89                   for(j=0;j< size; j+=(w/8)) {
  90                           printf(" ");
  91                           for(x=0;x < w/8;x++){
  92                                 printf("%02x", (unsigned char)data[i][j+x]);
  93                           }
  94                   }
  95                   printf("    ");
  96           }
  97           else printf("%*s", sp, "");
  98           if(i < m) {
  99                   printf("C%-2d:", i);
 100                   for(j=0;j< size; j+=(w/8)) {
 101                           printf(" ");
 102                           for(x=0;x < w/8;x++){
 103                                 printf("%02x", (unsigned char)coding[i][j+x]);
 104                           }
 105                   }
 106           }
 107           printf("\n");
 108   }
 109         printf("\n");
 110 }
 111
 112 int main(int argc, char **argv)
 113 {
 114   int k, m, w, size;
 115   int i, j;
 116   int *matrix;
 117   char **data, **coding;
 118   int *erasures, *erased;
 119   int *decoding_matrix, *dm_ids;
 120   uint32_t seed;
 121
 122   if (argc != 6) usage(NULL);
 123   if (sscanf(argv[1], "%d", &k) == 0 || k <= 0) usage("Bad k");
 124   if (sscanf(argv[2], "%d", &m) == 0 || m <= 0) usage("Bad m");
 125   if (sscanf(argv[3], "%d", &w) == 0 || (w != 8 && w != 16 && w != 32)) usage("Bad w");
 126   if (w < 32 && k + m > (1 << w)) usage("k + m must be <= 2 ^ w");
 127   if (sscanf(argv[4], "%d", &size) == 0 || size % sizeof(long) != 0)
 128                 usage("size must be multiple of sizeof(long)");
 129   if (sscanf(argv[5], "%d", &seed) == 0) usage("Bad seed");
 130
 131   matrix = talloc(int, m*k);
 132   for (i = 0; i < m; i++) {
 133     for (j = 0; j < k; j++) {
 134       matrix[i*k+j] = galois_single_divide(1, i ^ (m + j), w);
 135     }
 136   }
 137
 138   printf("<HTML><TITLE>jerasure_05");
 139   for (i = 1; i < argc; i++) printf(" %s", argv[i]);
 140   printf("</TITLE>\n");
 141   printf("<h3>jerasure_05");
 142   for (i = 1; i < argc; i++) printf(" %s", argv[i]);
 143   printf("</h3>\n");
 144   printf("<pre>\n");
 145
 146   printf("The Coding Matrix (the last m rows of the Generator Matrix G^T):\n\n");
 147   jerasure_print_matrix(matrix, m, k, w);
 148   printf("\n");
 149
 150   MOA_Seed(seed);
 151   data = talloc(char *, k);
 152   for (i = 0; i < k; i++) {
 153     data[i] = talloc(char, size);
 154     MOA_Fill_Random_Region(data[i], size);
 155   }
 156
 157   coding = talloc(char *, m);
 158   for (i = 0; i < m; i++) {
 159     coding[i] = talloc(char, size);
 160   }
 161
 162   jerasure_matrix_encode(k, m, w, matrix, data, coding, size);
 163
 164   printf("Encoding Complete:\n\n");
 165   print_data_and_coding(k, m, w, size, data, coding);
 166
 167   erasures = talloc(int, (m+1));
 168   erased = talloc(int, (k+m));
 169   for (i = 0; i < m+k; i++) erased[i] = 0;
 170   for (i = 0; i < m; ) {
 171     erasures[i] = (MOA_Random_W(w, 1))%(k+m);
 172     if (erased[erasures[i]] == 0) {
 173       erased[erasures[i]] = 1;
 174
 175       bzero((erasures[i] < k) ? data[erasures[i]] : coding[erasures[i]-k], size);
 176       i++;
 177     }
 178   }
 179   erasures[i] = -1;
 180
 181   printf("Erased %d random devices:\n\n", m);
 182   print_data_and_coding(k, m, w, size, data, coding);
 183
 184   i = jerasure_matrix_decode(k, m, w, matrix, 0, erasures, data, coding, size);
 185
 186   printf("State of the system after decoding:\n\n");
 187   print_data_and_coding(k, m, w, size, data, coding);
 188
 189   decoding_matrix = talloc(int, k*k);
 190   dm_ids = talloc(int, k);
 191
 192   for (i = 0; i < m; i++) erased[i] = 1;
 193   for (; i < k+m; i++) erased[i] = 0;
 194
 195   jerasure_make_decoding_matrix(k, m, w, matrix, erased, decoding_matrix, dm_ids);
 196
 197   printf("Suppose we erase the first %d devices.  Here is the decoding matrix:\n\n", m);
 198   jerasure_print_matrix(decoding_matrix, k, k, w);
 199   printf("\n");
 200   printf("And dm_ids:\n\n");
 201   jerasure_print_matrix(dm_ids, 1, k, w);
 202
 203   bzero(data[0], size);
 204   jerasure_matrix_dotprod(k, w, decoding_matrix, dm_ids, 0, data, coding, size);
 205
 206   printf("\nAfter calling jerasure_matrix_dotprod, we calculate the value of device #0 to be:\n\n");
 207   printf("D0 :");
 208   for(i=0;i< size; i+=(w/8)) {
 209           printf(" ");
 210           for(j=0;j < w/8;j++){
 211                 printf("%02x", (unsigned char)data[0][i+j]);
 212           }
 213   }
 214   printf("\n\n");
 215
 216   return 0;
 217 }