package jp.sourceforge.reedsolomon;/** * タイトル: RSコード?デコーダ * * @author Masayuki Miyazaki * http://sourceforge.jp/projects/reedsolomon/ */public class RsDecode {	public static final int RS_PERM_ERROR = -1;	public static final int RS_CORRECT_ERROR = -2;	private static final Galois galois = Galois.getInstance();	private int npar;	public RsDecode(int npar) {		this.npar = npar;	}	/**	 * Modified Berlekamp-Massey	 *	 * @param sigma int[]	 *		σ(z)格納用配列、最大npar/2 + 2個の領域が必要	 * 		σ0,σ1,σ2, ... σ<jisu>	 * @param omega int[]	 *		ω(z)格納用配列、最大npar/2 + 1個の領域が必要	 *		ω0,ω1,ω2, ... ω<jisu-1>	 * @param syn int[]	 *		シンドローム配列	 * 		s0,s1,s2, ... s<npar-1>	 * @return int	 * 		>= 0: σの次數	 * 		< 0: エラー	 */	public int calcSigmaMBM(int[] sigma, int[] omega, final int[] syn) {		int[] sg0 = new int[npar];		int[] sg1 = new int [npar];		sg0[1] = 1;		sg1[0] = 1;		int jisu0 = 1;		int jisu1 = 0;		int m = -1;		for(int n = 0; n < npar; n++) {			// 判別式を計算			int d = syn[n];			for(int i = 1; i <= jisu1; i++) {				d ^= galois.mul(sg1[i], syn[n - i]);			}			if(d != 0) {				int logd = galois.toLog(d);				int[] wk = new int[npar];				for(int i = 0; i <= n; i++) {					wk[i] = sg1[i] ^ galois.mulExp(sg0[i], logd);				}				int js = n - m;				if(js > jisu1) {					m = n - jisu1;					jisu1 = js;					if(jisu1 > npar / 2) {						return -1;				// σの次數がnpar / 2を超えたらエラー					}					for(int i = 0; i <= jisu0; i++) {						sg0[i] = galois.divExp(sg1[i], logd);					}					jisu0 = jisu1;				}				sg1 = wk;			}			System.arraycopy(sg0, 0, sg0, 1, Math.min(sg0.length - 1, jisu0));			sg0[0] = 0;			jisu0++;		}		galois.mulPoly(omega, sg1, syn);		System.arraycopy(sg1, 0, sigma, 0, Math.min(sg1.length, sigma.length));		return jisu1;	}	/**	 * 最終エラー位置のセット	 * @param pos	 * 		誤り位置格納用初列	 * @param n	 * 		データ長	 * @param last	 * 		エラー位置	 * @return	 * 		0: 正常終了	 * 		< 0: エラー	 */	private int setLastErrorPos(int[] pos, int n, int last) {		if(galois.toLog(last) >= n) {			return RS_CORRECT_ERROR;	// 範囲外なのでエラー		}		pos[0] = last;		return 0;	}	/**	 * チェン探索により誤り位置を求める	 *		σ(z) = 0の解を探索する	 *		ただし、探索はデータ長以內の解のみで	 *		jisu個の解が見つからなければ、エラーとする	 * @param pos int[]	 * 		誤り位置格納用配列、jisu個の領域が必要	 * @param n int	 * 		データ長	 * @param jisu int	 * 		σの次數	 * @param sigma int[]	 * 		σ0,σ1,σ2, ... σ<jisu>	 * @return int	 *		0: 正常終了	 *		< 0: エラー	 */	private int chienSearch(int[] pos, int n, int jisu, final int[] sigma) {		/*		 * σ(z) = (1-α^i*z)(1-α^j*z)(1-α^k*z)		 *       = 1 + σ1z + σ2z^2 +...		 * σ1 = α^i + α^j + α^k		 * つまりσ1は全ての解の合計となっている。上記の性質を利用して、プチ最適化		 * last = σ1から、見つけた解を次々と引いていくことにより、最後の解はlastとなる		 */		int last = sigma[1];		if(jisu == 1) {			// 次數が1ならばlastがその解である			return setLastErrorPos(pos, n, last);		}		int posIdx = jisu - 1;		// 誤り位置格納用インデックス		for(int i = 0; i < n; i++) {			/*			 * σ(z)の計算			 * w を1(0乗の項)に初期化した後、殘りの項<1..jisu>を加算			 * z = 1/α^i = α^Iとすると			 * σ(z) = 1 + σ1α^I + σ2(α^I)^2 + σ3(α^I)^3 + ... + σ<jisu>/(α^I)^<jisu>			 *      = 1 + σ1α^I + σ2α^(I*2) + σ3α^(I*3) + ... + σ<jisu>α^(I*<jisu>)			 */			int z = 255 - i;					// z = 1/α^iのスカラー			int wk = 1;			for(int j = 1; j <= jisu; j++) {				wk ^= galois.mulExp(sigma[j], (z * j) % 255);			}			if(wk == 0) {				int pv = galois.toExp(i);		// σ(z) = 0の解				last ^=  pv;					// lastから今見つかった解を引く				pos[posIdx--] = pv;				if(posIdx == 0) {					// 殘りが一つならば、lastがその解である					return setLastErrorPos(pos, n, last);				}			}		}		// 探索によりデータ長以內に、jisu個の解が見つからなかった		return RS_CORRECT_ERROR;	}	/**	 * Forney法で誤り訂正を行う	 *		σ(z) = (1-α^i*z)(1-α^j*z)(1-α^k*z)	 *		σ'(z) = α^i * (1-α^j*z)(1-α^k*z)...	 *			   + α^j * (1-α^i*z)(1-α^k*z)...	 *			   + α^k * (1-α^i*z)(1-α^j*z)...	 *		ω(z) = (E^i/(1-α^i*z) + E^j/(1-α^j*z) + ...) * σ(z)	 *			  = E^i*(1-α^j*z)(1-α^k*z)...	 *			  + E^j*(1-α^i*z)(1-α^k*z)...	 *			  + E^k*(1-α^i*z)(1-α^j*z)...	 *		∴ E^i = α^i * ω(z) / σ'(z)	 * @param data int[]	 *		入力データ配列	 * @param length int	 *		入力データ長さ	 * @param jisu int	 *		σの次數	 * @param pos int[]	 *		誤り位置配列	 * @param sigma int[]	 *		σ0,σ1,σ2, ... σ<jisu>	 * @param omega int[]	 *		ω0,ω1,ω2, ... ω<jisu-1>	 */	private void doForney(int[] data, int length, int jisu, int[] pos, int[] sigma, int[] omega) {		for(int i = 0; i < jisu; i++) {			int ps = pos[i];			int zlog = 255 - galois.toLog(ps);					// zのスカラー			// ω(z)の計算			int ov = omega[0];			for(int j = 1; j < jisu; j++) {				ov ^= galois.mulExp(omega[j], (zlog * j) % 255);		// ov += ωi * z^j			}			// σ'(z)の値を計算(σ(z)の形式的微分)			int dv = sigma[1];			for(int j = 2; j < jisu; j += 2) {				dv ^= galois.mulExp(sigma[j + 1], (zlog * j) % 255);	// dv += σ<j+1> * z^j			}			/*			 * 誤り訂正 E^i = α^i * ω(z) / σ'(z)			 * 誤り位置の範囲はチェン探索のときに保証されているので、			 * ここではチェックしない			 */			data[galois.toPos(length, ps)] ^= galois.mul(ps, galois.div(ov, dv));		}	}	/**	 * RSコードのデコード	 *	 * @param data int[]	 *		入力データ配列	 * @param length int	 * 		パリティを含めたデータ長	 * @param noCorrect boolean	 * 		チェックのみで訂正は行わない	 * @return int	 * 		0: エラーなし	 * 		> 0: 戻り値個の誤りを訂正した	 * 		< 0: 訂正不能	 */	public int decode(int[] data, int length, boolean noCorrect) {		if(length < npar || length > 255) {			return RS_PERM_ERROR;		}		// シンドロームを計算		int[] syn = new int[npar];		if(galois.calcSyndrome(data, length, syn)) {			return 0;		// エラー無し		}		// シンドロームよりσとωを求める		int[] sigma = new int[npar / 2 + 2];		int[] omega = new int[npar / 2 + 1];		int jisu = calcSigmaMBM(sigma, omega, syn);		if(jisu <= 0) {			return RS_CORRECT_ERROR;		}		// チェン探索により誤り位置を求める		int[] pos = new int[jisu];		int r = chienSearch(pos, length, jisu, sigma);		if(r < 0) {			return r;		}		if(!noCorrect) {			// 誤り訂正			doForney(data, length, jisu, pos, sigma, omega);		}		return jisu;	}	public int decode(int[] data, int length) {		return decode(data, length, false);	}	public int decode(int[] data) {		return decode(data, data.length, false);	}/*	public static void main(String[] args) {		int[] data = new int[] {			32, 65, 205, 69, 41, 220, 46, 128, 236,			42, 159, 74, 221, 244, 169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61		};		RsDecode dec = new RsDecode(17);		int r = dec.decode(data);		System.out.println("r=" + r);		for(int i = 0; i < 8; i++) {			data[i] ^= (int) (Math.random() * 256);		}		System.out.println(java.util.Arrays.toString(data));		r = dec.decode(data);		System.out.println("r=" + r);		System.out.println(java.util.Arrays.toString(data));	}*/}