rs.c

QR Code码的解码程序

#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);
}