?? rs.c
字號:
#include <stdio.h>
#include "rs.h"
static int gfpwr[] = {1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205,
135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35, 70, 140,
5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97, 194,
153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107,
214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34,
68, 136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199,
147, 59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169,
79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57,
114, 228, 213, 183, 115, 230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179,
123, 246, 241, 255, 227, 219, 171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87,
174, 65, 130, 25, 50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144,
61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233,
207, 131, 27, 54, 108, 216, 173, 71, 142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116,
232, 205, 135, 19, 38, 76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48,
96, 192, 157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222, 161, 95, 190, 97,
194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60, 120, 240, 253, 231, 211, 187, 107,
214, 177, 127, 254, 225, 223, 163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68,
136, 13, 26, 52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59, 118,
236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218, 169, 79, 158, 33, 66, 132,
21, 42, 84, 168, 77, 154, 41, 82, 164, 85, 170, 73, 146, 57, 114, 228, 213, 183, 115,
230, 209, 191, 99, 198, 145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219,
171, 75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25, 50, 100, 200,
141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81, 162, 89, 178, 121, 242, 249, 239,
195, 155, 43, 86, 172, 69, 138, 9, 18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251,
235, 203, 139, 11, 22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
142, 1, 0, };
static int gflog[] = { 0, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51,
238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193,
105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53,
147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249,
185, 201, 154, 9, 120, 77, 228, 114, 166, 6, 191, 139, 98, 102,
221, 48, 253, 226, 152, 37, 179, 16, 145, 34, 136, 54, 208, 148,
206, 143, 150, 219, 189, 241, 210, 19, 92, 131, 56, 70, 64, 30, 66,
182, 163, 195, 72, 126, 110, 107, 58, 40, 84, 250, 133, 186, 61,
202, 94, 155, 159, 10, 21, 121, 43, 78, 212, 229, 172, 115, 243,
167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103, 74, 222, 237, 49,
197, 254, 24, 227, 165, 153, 119, 38, 184, 180, 124, 17, 68, 146,
217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188, 207, 205, 144,
135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171, 20, 42, 93,
158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216, 183, 123,
164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161, 59, 82,
41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203, 89, 95,
176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215, 79,
174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80, 88,
175 };
static int logsym[MAXBUF];
// S的值
static int syndrome[MAXBUF];
// 求xi時的參數矩陣
static int tpltzarray[MAXTOEPLITZ*(MAXTOEPLITZ+10)];
// xi的解
static int tpltzrslt[MAXTOEPLITZ];
static int errloc[MAXTOEPLITZ];
static int iSSize;
int CorrectErrs(unsigned char * aSym, int dsize, int csize, int p)
{
int i, e, d, errcnt;
// unsigned char str[MAXBUF];
int aSize = (csize - p) / 2;
d = dsize;
e = 0;
// sym總的數據長度
iSSize = d + csize;
// 計算S
CalcSyndromes(aSym, iSSize, csize - p, aSize);
// 處理參數矩陣
errcnt = NormlzToeplitz(aSize);
if (errcnt > 0) {
if (tpltzarray[0] == 0) { return(-1); }
// 求解方程組算出xi
SolveToeplitz(errcnt);
// 檢查錯誤位置
if (!ChienSearch(errcnt)) { return(-1); }
// 初始化錯誤矩陣
ErrLocInit(errcnt);
// 處理錯誤方程參數矩陣
if (NormlzToeplitz(errcnt) != errcnt) { return(-1); }
// 求解方程組算出錯誤值
SolveToeplitz(errcnt);
for (i = 0; i < errcnt; i++) {
aSym[((iSSize-((errloc[i] == 0) ? 255 : errloc[i])) )] ^= tpltzrslt[i];
}
}
e += errcnt;
return(e);
}
void CalcSyndromes(unsigned char *aSym, int aCSize, int aSsize, int aSize)
{
int i, i1, j, n;
/* init array of logs of sym chars */
// 計算所有輸入數據的指數
for (i = 0; i < aCSize; i++ ) {
i1 = ( (aSym[i] == 0) ? 255 : gflog[aSym[i]] );
if (i1 != 255) {
i1 = i1 + (aCSize - i);
i1 = ( (i1 > 254) ? (i1 - 255) : i1 );
}
logsym[i] = i1;
}
//Debug("Logs of the syms", logsym, aCSize);
/* calculate syndromes */
// 計算S
for (j = 0; j < aSsize; j++) {
syndrome[j] = 0;
// 對每項進行計算
for (i = 0; i < aCSize; i++) {
if (logsym[i] != 255){
syndrome[j] ^= gfpwr[logsym[i]];
n = logsym[i] + (aCSize - i);
logsym[i] = ( (n > 254) ? (n - 255) : n);
/*
n = j * i;
if (n > 254) n -= 255;
syndrome[j] ^= gfpwr[logsym[i] + n];
*/
}
}
}
//Debug ("Symdromes", syndrome, aSsize);
/* use syndromes to initialize solution matrix tpltzarray */
// 初始化計算錯誤的S矩陣
for (j = n = 0; j < MAXTOEPLITZ*aSsize; j += MAXTOEPLITZ, n++) {
for (i = 0; i <= aSsize; i++) {
tpltzarray[j + i] = syndrome[n + i];
}
}
}
/**
* OK
*/
int NormlzToeplitz(int size)
{
int x, y, x1, y1, n;
for (x = y = 0; x < size; x++, y++) {
/* if entry in top row is 0; swap it with a lower non-0 row */
if (tpltzarray[x+(MAXTOEPLITZ*y)] == 0) {
for (y1 = y+1; y1 < size; y1++) {
if (tpltzarray[x+(MAXTOEPLITZ*y1)] != 0) {
for (x1 = x; x1 <= size; x1++) {
/* swap entries */
n = tpltzarray[x1+(MAXTOEPLITZ*y1)];
tpltzarray[x1+(MAXTOEPLITZ*y1)] = tpltzarray[x1+(MAXTOEPLITZ*y)];
tpltzarray[x1+(MAXTOEPLITZ*y)] = n;
}
break;
}
}
/* if all were 0, same row but increment to next column */
if (y1 == size) {
y--;
continue;
}
}
/* use y row to 0 all higher x column entries */
for (y1 = y+1; y1 < size; y1++) {
if (tpltzarray[x+(MAXTOEPLITZ*y1)] != 0) {
n = GFdiv( tpltzarray[x+(MAXTOEPLITZ*y1)], tpltzarray[x+(MAXTOEPLITZ*y)]);
tpltzarray[x+(MAXTOEPLITZ*y1)] = 0;
for (x1 = x+1; x1 <= size; x1++) {
tpltzarray[x1+(MAXTOEPLITZ*y1)] ^= GFmul(n, tpltzarray[x1+(MAXTOEPLITZ*y)]);
}
}
}
}
return(y);
}
/**
* OK
*/
void SolveToeplitz(int size)
{
int x, x1, r;
/* solve for each xi */
for (x = size-1; x >= 0; x--) {
r = tpltzarray[size + (MAXTOEPLITZ*x)];
/* first substitute any previously solved xi's */
for (x1 = size-1; x1 > x; x1--) {
r ^= GFmul(tpltzrslt[x1], tpltzarray[x1 + (MAXTOEPLITZ*x)]);
}
tpltzrslt[x] = GFdiv(r, tpltzarray[x + (MAXTOEPLITZ*x)]);
}
//Debug ("Xis", tpltzrslt, size);
}
/**
* OK
*/
int ChienSearch(int size)
{
int i, j, r, e = 0;
int log[MAXTOEPLITZ];
// 算出所有xi的log值,并倒置存儲
for (i = 0; i < size; i++) {
log[i] = gflog[tpltzrslt[size-1-i]];
}
// 對每一個輸入codeword計算xi
for (j = 1; j <= iSSize; j++) {
// 默認x的0次冪為1
r = 1;
for (i = 0; i < size; i++) {
if ((log[i] -= i+1) < 0) {
log[i] += 255;
}
r ^= gfpwr[log[i]];
}
if (r == 0) {
errloc[e] = (j < 255) ? j : 0;
e++;
if (e >= size) break;
}
}
//Debug ("Error", errloc, size);
return(e >= size);
}
/**
* OK
*/
void ErrLocInit(int size)
{
int i, j;
int log[MAXTOEPLITZ], log1[MAXTOEPLITZ];
for (i = 0; i < size; i++) {
log[i] = log1[i] = errloc[i];
}
for (j = 0; j < size; j++) {
for (i = 0; i < size; i++) {
tpltzarray[i+(MAXTOEPLITZ*j)] = gfpwr[log1[i]];
if ((log1[i] += log[i]) > 254) { log1[i] -= 255; }
}
tpltzarray[i+(MAXTOEPLITZ*j)] = syndrome[j];
}
}
/**
* OK
*/
int GFmul(int aP1, int aP2)
{
int i,j;
if (aP1==0 || aP2 == 0) return (0);
i = gflog[aP1];
j = gflog[aP2];
return (gfpwr[i+j]);
}
/**
* OK
*/
int GFdiv(int aP1, int aP2)
{
int i;
if (aP2 == 0) {
// printf("\ndivide by 0\n");
return(0);
}
if (aP1 == 0) {
return(0);
}
i = (int)gflog[aP1] - (int)gflog[aP2];
if (i < 0) i += 255;
i = (int)gfpwr[i];
return(i);
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -