]>
git.proxmox.com Git - ceph.git/blob - ceph/src/erasure-code/jerasure/jerasure/Examples/jerasure_06.c
2 * Copyright (c) 2014, James S. Plank and Kevin Greenan
5 * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure
8 * Revision 2.0: Galois Field backend now links to GF-Complete
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * - Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
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
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.
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.
40 /* Jerasure's authors:
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.
54 #define talloc(type, num) (type *) malloc(sizeof(type)*(num))
58 fprintf ( stderr
, "usage: jerasure_06 k m w packetsize seed \n " );
59 fprintf ( stderr
, "Does a simple Cauchy Reed-Solomon coding example in GF(2^w). \n " );
60 fprintf ( stderr
, " \n " );
61 fprintf ( stderr
, " k+m must be < 2^w. Packetsize must be a multiple of sizeof(long) \n " );
62 fprintf ( stderr
, " It sets up a Cauchy generator matrix and encodes k devices of w*packetsize bytes. \n " );
63 fprintf ( stderr
, " After that, it decodes device 0 by using jerasure_make_decoding_bitmatrix() \n " );
64 fprintf ( stderr
, " and jerasure_bitmatrix_dotprod(). \n " );
65 fprintf ( stderr
, " \n " );
66 fprintf ( stderr
, "This demonstrates: jerasure_bitmatrix_encode() \n " );
67 fprintf ( stderr
, " jerasure_bitmatrix_decode() \n " );
68 fprintf ( stderr
, " jerasure_print_bitmatrix() \n " );
69 fprintf ( stderr
, " jerasure_make_decoding_bitmatrix() \n " );
70 fprintf ( stderr
, " jerasure_bitmatrix_dotprod() \n " );
71 if ( s
!= NULL
) fprintf ( stderr
, " \n %s \n\n " , s
);
75 static print_array ( char ** ptrs
, int ndevices
, int size
, int packetsize
, char * label
)
80 printf ( "<center><table border=3 cellpadding=3><tr><td></td> \n " );
82 for ( i
= 0 ; i
< ndevices
; i
++) printf ( "<td align=center>%s%x</td> \n " , label
, i
);
84 printf ( "<td align=right><pre>" );
85 for ( j
= 0 ; j
< size
/ packetsize
; j
++) printf ( "Packet %d \n " , j
);
86 printf ( "</pre></td> \n " );
87 for ( i
= 0 ; i
< ndevices
; i
++) {
89 up
= ( unsigned char *) ptrs
[ i
];
90 for ( j
= 0 ; j
< size
/ packetsize
; j
++) {
91 for ( x
= 0 ; x
< packetsize
; x
++) {
92 if ( x
> 0 && x
% 4 == 0 ) printf ( " " );
93 printf ( "%02x" , up
[ j
* packetsize
+ x
]);
99 printf ( "</tr></table></center> \n " );
102 int main ( int argc
, char ** argv
)
105 int k
, w
, i
, j
, m
, psize
, x
;
106 int * matrix
, * bitmatrix
;
107 char ** data
, ** coding
;
108 int * erasures
, * erased
;
109 int * decoding_matrix
, * dm_ids
;
112 if ( argc
!= 6 ) usage ( NULL
);
113 if ( sscanf ( argv
[ 1 ], "%d" , & k
) == 0 || k
<= 0 ) usage ( "Bad k" );
114 if ( sscanf ( argv
[ 2 ], "%d" , & m
) == 0 || m
<= 0 ) usage ( "Bad m" );
115 if ( sscanf ( argv
[ 3 ], "%d" , & w
) == 0 || w
<= 0 || w
> 32 ) usage ( "Bad w" );
116 if ( w
< 30 && ( k
+ m
) > ( 1 << w
)) usage ( "k + m is too big" );
117 if ( sscanf ( argv
[ 4 ], "%d" , & psize
) == 0 || psize
<= 0 ) usage ( "Bad packetsize" );
118 if ( psize
% sizeof ( long ) != 0 ) usage ( "Packetsize must be multiple of sizeof(long)" );
119 if ( sscanf ( argv
[ 5 ], "%d" , & seed
) == 0 ) usage ( "Bad seed" );
122 matrix
= talloc ( int , m
* k
);
123 for ( i
= 0 ; i
< m
; i
++) {
124 for ( j
= 0 ; j
< k
; j
++) {
125 matrix
[ i
* k
+ j
] = galois_single_divide ( 1 , i
^ ( m
+ j
), w
);
128 bitmatrix
= jerasure_matrix_to_bitmatrix ( k
, m
, w
, matrix
);
130 printf ( "<HTML><TITLE>jerasure_06" );
131 for ( i
= 1 ; i
< argc
; i
++) printf ( " %s" , argv
[ i
]);
132 printf ( "</TITLE> \n " );
133 printf ( "<h3>jerasure_06" );
134 for ( i
= 1 ; i
< argc
; i
++) printf ( " %s" , argv
[ i
]);
138 printf ( "Last (m * w) rows of the Generator Matrix: (G^T): \n <pre> \n " );
139 jerasure_print_bitmatrix ( bitmatrix
, w
* m
, w
* k
, w
);
140 printf ( "</pre><hr> \n " );
142 data
= talloc ( char *, k
);
143 for ( i
= 0 ; i
< k
; i
++) {
144 data
[ i
] = talloc ( char , psize
* w
);
145 MOA_Fill_Random_Region ( data
[ i
], psize
* w
);
148 coding
= talloc ( char *, m
);
149 for ( i
= 0 ; i
< m
; i
++) {
150 coding
[ i
] = talloc ( char , psize
* w
);
153 jerasure_bitmatrix_encode ( k
, m
, w
, bitmatrix
, data
, coding
, w
* psize
, psize
);
155 printf ( "Encoding Complete - Here is the state of the system \n\n " );
157 print_array ( data
, k
, psize
* w
, psize
, "D" );
159 print_array ( coding
, m
, psize
* w
, psize
, "C" );
162 erasures
= talloc ( int , ( m
+ 1 ));
163 erased
= talloc ( int , ( k
+ m
));
164 for ( i
= 0 ; i
< m
+ k
; i
++) erased
[ i
] = 0 ;
165 for ( i
= 0 ; i
< m
; ) {
166 erasures
[ i
] = MOA_Random_W ( w
, 1 )%( k
+ m
);
167 if ( erased
[ erasures
[ i
]] == 0 ) {
168 erased
[ erasures
[ i
]] = 1 ;
169 bzero (( erasures
[ i
] < k
) ? data
[ erasures
[ i
]] : coding
[ erasures
[ i
]- k
], psize
* w
);
175 printf ( "Erased %d random devices:" , m
);
176 for ( i
= 0 ; erasures
[ i
] != - 1 ; i
++) {
177 printf ( " %c%x" , (( erasures
[ i
] < k
) ? 'D' : 'C' ), ( erasures
[ i
] < k
? erasures
[ i
] : erasures
[ i
]- k
));
179 printf ( ". Here is the state of the system: \n " );
182 print_array ( data
, k
, psize
* w
, psize
, "D" );
184 print_array ( coding
, m
, psize
* w
, psize
, "C" );
187 i
= jerasure_bitmatrix_decode ( k
, m
, w
, bitmatrix
, 0 , erasures
, data
, coding
,
190 printf ( "Here is the state of the system after decoding: \n\n " );
192 print_array ( data
, k
, psize
* w
, psize
, "D" );
194 print_array ( coding
, m
, psize
* w
, psize
, "C" );
197 decoding_matrix
= talloc ( int , k
* k
* w
* w
);
198 dm_ids
= talloc ( int , k
);
202 for ( i
= 0 ; i
< x
; i
++) erased
[ i
] = 1 ;
203 for (; i
< k
+ m
; i
++) erased
[ i
] = 0 ;
205 jerasure_make_decoding_bitmatrix ( k
, m
, w
, bitmatrix
, erased
, decoding_matrix
, dm_ids
);
207 printf ( "Suppose we erase the first %d devices. Here is the decoding matrix: \n <pre> \n " , x
);
208 jerasure_print_bitmatrix ( decoding_matrix
, k
* w
, k
* w
, w
);
210 printf ( "And dm_ids: \n <pre> \n " );
211 jerasure_print_matrix ( dm_ids
, 1 , k
, w
);
212 printf ( "</pre><hr> \n " );
214 for ( i
= 0 ; i
< x
; i
++) bzero ( data
[ i
], w
* psize
);
216 printf ( "Here is the state of the system after the erasures: \n\n " );
218 print_array ( data
, k
, psize
* w
, psize
, "D" );
220 print_array ( coding
, m
, psize
* w
, psize
, "C" );
223 for ( i
= 0 ; i
< x
; i
++) {
224 jerasure_bitmatrix_dotprod ( k
, w
, decoding_matrix
+ i
*( k
* w
* w
), dm_ids
, i
, data
, coding
, w
* psize
, psize
);
227 printf ( "Here is the state of the system after calling <b>jerasure_bitmatrix_dotprod()</b> %d time%s with the decoding matrix: \n\n " , x
, ( x
== 1 ) ? "" : "s" );
229 print_array ( data
, k
, psize
* w
, psize
, "D" );
231 print_array ( coding
, m
, psize
* w
, psize
, "C" );