Finite Field GF(2^8) or GF256 Polynomial Reed Solomon Related

[tt]

Finite Field GF(2^8) or GF256 Polynomial Reed Solomon Related

https://content.sakai.rutgers.edu/acces ... Report.pdf

http://www.cs.utsa.edu/~wagner/laws/FFM.html

http://cache.freescale.com/files/dsp/do ... AN2407.pdf

https://people.cs.clemson.edu/~westall/851/rs-code.pdf

http://www.ccs.neu.edu/home/alina/papers/tos-gf.pdf

[tt]

gfmul for RAID6 "0x11D"

Assume we got 32 disks in an RAID6 as max


DD & DP

Code: Select all

#include "gf.h"

unsigned char amatrix[256][256];
void gen_pq_gf_ginverse(int failx, int faily, int max) 
{
	
	int i, j;
	int k = 256;
	int working = 0;

	if ( faily <= failx ) {
		printf( "bug; exit!\n" );
		exit(-1);
	}

	
	for ( j = 0; j < k; j++ )
		for ( i = 0; i < k; i++ )
			amatrix[i][j] = 0x00;
	
	for ( j = 0; j < k; j++ ) {
		int set_ident = 0;
		for ( i = 0; i < k; i++ ) {
			if ( i == k-2 || i == k-1 ) {
				/* fill PQ */
				if ( i == k-2 )
					amatrix[i][j] = 0x01;
				else
					amatrix[i][j] = raid6_gfexp[j];
			
			}
			else {
				if ( j == failx || j == faily )
					amatrix[i][j] == 0x00;
				else {
					if ( i == working && !set_ident ) {
						amatrix[i][j] = 0x01;
						set_ident = 1;
						working++;
					}
					else
						amatrix[i][j] = 0x00;
				}

			}
		}
	}
	invert_mat(amatrix, k);
	{
		for ( i = 0; i < k; i++ ) {
			if ( i == failx || i == faily ) {
				//printf( "=(%02d)= ", i );
				printf( "	{ /* (%d,%d) */", failx, faily );
				for ( j = 0; j < max-2; j++ ) {
					if ( (j % 8 )==0 ) 
						printf( "\n		" );
					printf( "0x%02x, ", amatrix[i][j] );
				}
				printf( "0x%02x, 0x%02x, ", amatrix[i][254], amatrix[i][255] );
				printf( "\n	},\n" );
			}
		}
	}
}

#define MAX 32
int main(void)
{
	/* possible entry = C(max-2,2) => 24 PQ-disks, C(22,2)=(22!)/(20!2!) = 231 */ 
	int max = MAX;
	int failx, faily;
	int bytecnt=0, entrycnt=0;
	//gen_pq_gf_ginverse( 0, 2, max );
	//gen_pq_gf_ginverse( 1, 6, max );
#if 1
	for ( failx = 0; failx < (max-2); failx++ )
		for ( faily = (failx+1); faily < (max-2); faily++ ) {
			if ( faily > failx ) {
				//printf( "	/* (%d, x=%d, y=%d) */\n", entrycnt, failx, faily );
				gen_pq_gf_ginverse( failx, faily, max );
				bytecnt += max * 2;
				entrycnt++;
			}
		}
	printf( "total bytes for %d disks = %d, entry=%d\n", max, bytecnt,entrycnt );
#endif /* 1 */
}

Code: Select all

#include "gf.h"

#if 1
int k = 256;
unsigned char amatrix[256][256];
#else
int k = 8;
unsigned char amatrix[8][8];
#endif
void gen_pq_gf_ginverse(int failx, int faily, int max) 
{
	
	int i, j;
	int working = 0;

	if ( faily <= failx ) {
		printf( "bug; exit!\n" );
		exit(-1);
	}

	
	for ( j = 0; j < k; j++ )
		for ( i = 0; i < k; i++ )
			amatrix[i][j] = 0x00;
	
	for ( j = 0; j < k; j++ ) {
		int set_ident = 0;
		for ( i = 0; i < k; i++ ) {
			if ( i == k-1 ) {
				/* fill Q */
				amatrix[i][j] = raid6_gfexp[j];
			}
			else {
				if ( j == failx )
					amatrix[i][j] == 0x00;
				else {
					if ( i == working && !set_ident ) {
						amatrix[i][j] = 0x01;
						set_ident = 1;
						working++;
					}
					else
						amatrix[i][j] = 0x00;
				}

			}
		}
	}
#if 1
	invert_mat(amatrix, k);
	{
		for ( i = 0; i < k; i++ ) {
			if ( i == failx ) {
				//printf( "=(%02d)= ", i );
				printf( "	{ /* (%d,Px) */", failx );
				for ( j = 0; j < max-1; j++ ) {
					if ( (j % 8 )==0 ) 
						printf( "\n		" );
					printf( "0x%02x, ", amatrix[i][j] );
				}
				printf( "0x%02x, ", amatrix[i][255] ); /* pick G of Q */
				printf( "\n	},\n" );
			}
		}
	}
#else
		for ( i = 0; i < k; i++ ) {
			for ( j = 0; j < k; j++ ) {
				printf( "0x%02x, ", amatrix[i][j] );
			}
			printf( "\n" );
		}
			printf( "\n" );
		invert_mat(amatrix, k);
		for ( i = 0; i < k; i++ ) {
			for ( j = 0; j < k; j++ ) {
				printf( "0x%02x, ", amatrix[i][j] );
			}
			printf( "\n" );
		}
			printf( "\n" );
#endif 
}

#define MAX 32
int main(void)
{
	/* possible entry = C(max-2,2) => 24 PQ-disks, C(22,2)=(22!)/(20!2!) = 231 */ 
	int max = MAX;
	int failx, faily;
	int bytecnt=0, entrycnt=0;
#if 1
	for ( failx = 0; failx < (max-2); failx++ ) {
			faily = max - 2;
			if ( faily > failx ) {
				//printf( "	/* (%d, x=%d, y=%d) */\n", entrycnt, failx, faily );
				gen_pq_gf_ginverse( failx, faily, max );
				bytecnt += max * 2;
				entrycnt++;
			}
		}
	printf( "total bytes for %d disks = %d, entry=%d\n", max, bytecnt,entrycnt );
#endif /* 1 */
}

[tt]

gfmul for RAID6 "0x14D"

DD & DP

Code: Select all

#include "gf.h"

unsigned char amatrix[256][256];
void gen_pq_gf_ginverse(int failx, int faily, int max) 
{
	
	int i, j;
	int k = 256;
	int working = 0;

	if ( faily <= failx ) {
		printf( "bug; exit!\n" );
		exit(-1);
	}

	
	for ( j = 0; j < k; j++ )
		for ( i = 0; i < k; i++ )
			amatrix[i][j] = 0x00;
	
	for ( j = 0; j < k; j++ ) {
		int set_ident = 0;
		for ( i = 0; i < k; i++ ) {
			if ( i == k-2 || i == k-1 ) {
				/* fill PQ */
				if ( i == k-2 )
					amatrix[i][j] = 0x01;
				else
					amatrix[i][j] = raid6_gfexp[j];
			
			}
			else {
				if ( j == failx || j == faily )
					amatrix[i][j] == 0x00;
				else {
					if ( i == working && !set_ident ) {
						amatrix[i][j] = 0x01;
						set_ident = 1;
						working++;
					}
					else
						amatrix[i][j] = 0x00;
				}

			}
		}
	}
	invert_mat(amatrix, k);
	{
		for ( i = 0; i < k; i++ ) {
			if ( i == failx || i == faily ) {
				//printf( "=(%02d)= ", i );
				printf( "	{ /* (%d,%d) */", failx, faily );
				for ( j = 0; j < max-2; j++ ) {
					if ( (j % 8 )==0 ) 
						printf( "\n		" );
					printf( "0x%02x, ", amatrix[i][j] );
				}
				printf( "0x%02x, 0x%02x, ", amatrix[i][254], amatrix[i][255] );
				printf( "\n	},\n" );
			}
		}
	}
}

#define MAX 32
int main(void)
{
	/* possible entry = C(max-2,2) => 24 PQ-disks, C(22,2)=(22!)/(20!2!) = 231 */ 
	int max = MAX;
	int failx, faily;
	int bytecnt=0, entrycnt=0;
	//gen_pq_gf_ginverse( 0, 2, max );
	//gen_pq_gf_ginverse( 1, 6, max );
#if 1
	for ( failx = 0; failx < (max-2); failx++ )
		for ( faily = (failx+1); faily < (max-2); faily++ ) {
			if ( faily > failx ) {
				//printf( "	/* (%d, x=%d, y=%d) */\n", entrycnt, failx, faily );
				gen_pq_gf_ginverse( failx, faily, max );
				bytecnt += max * 2;
				entrycnt++;
			}
		}
	printf( "total bytes for %d disks = %d, entry=%d\n", max, bytecnt,entrycnt );
#endif /* 0 */
}

Code: Select all

#include "gf.h"

#if 1
int k = 256;
unsigned char amatrix[256][256];
#else
int k = 8;
unsigned char amatrix[8][8];
#endif
void gen_pq_gf_ginverse(int failx, int faily, int max) 
{
	
	int i, j;
	int working = 0;

	if ( faily <= failx ) {
		printf( "bug; exit!\n" );
		exit(-1);
	}

	
	for ( j = 0; j < k; j++ )
		for ( i = 0; i < k; i++ )
			amatrix[i][j] = 0x00;
	
	for ( j = 0; j < k; j++ ) {
		int set_ident = 0;
		for ( i = 0; i < k; i++ ) {
			if ( i == k-1 ) {
				/* fill Q */
				amatrix[i][j] = raid6_gfexp[j];
			}
			else {
				if ( j == failx )
					amatrix[i][j] == 0x00;
				else {
					if ( i == working && !set_ident ) {
						amatrix[i][j] = 0x01;
						set_ident = 1;
						working++;
					}
					else
						amatrix[i][j] = 0x00;
				}

			}
		}
	}
#if 1
	invert_mat(amatrix, k);
	{
		for ( i = 0; i < k; i++ ) {
			if ( i == failx ) {
				//printf( "=(%02d)= ", i );
				printf( "	{ /* (%d,Px) */", failx );
				for ( j = 0; j < max-1; j++ ) {
					if ( (j % 8 )==0 ) 
						printf( "\n		" );
					printf( "0x%02x, ", amatrix[i][j] );
				}
				printf( "0x%02x, ", amatrix[i][255] ); /* pick G of Q */
				printf( "\n	},\n" );
			}
		}
	}
#else
		for ( i = 0; i < k; i++ ) {
			for ( j = 0; j < k; j++ ) {
				printf( "0x%02x, ", amatrix[i][j] );
			}
			printf( "\n" );
		}
			printf( "\n" );
		invert_mat(amatrix, k);
		for ( i = 0; i < k; i++ ) {
			for ( j = 0; j < k; j++ ) {
				printf( "0x%02x, ", amatrix[i][j] );
			}
			printf( "\n" );
		}
			printf( "\n" );
#endif 
}

#define MAX 32
int main(void)
{
	/* possible entry = C(max-2,2) => 24 PQ-disks, C(22,2)=(22!)/(20!2!) = 231 */ 
	int max = MAX;
	int failx, faily;
	int bytecnt=0, entrycnt=0;
#if 1
	for ( failx = 0; failx < (max-2); failx++ ) {
			faily = max - 2;
			if ( faily > failx ) {
				//printf( "	/* (%d, x=%d, y=%d) */\n", entrycnt, failx, faily );
				gen_pq_gf_ginverse( failx, faily, max );
				bytecnt += max * 2;
				entrycnt++;
			}
		}
	printf( "total bytes for %d disks = %d, entry=%d\n", max, bytecnt,entrycnt );
#endif /* 0 */
}