package projectEQ2440.QRcode.ReedSolomon;

import projectEQ2440.QRcode.ReedSolomon.GaloisField.*;

public class RSdecoder {
	
	// Syndroms
	private Galois[] syndroms;
	
	// Number of correction word and number of corrected error
	private int nbr_corr_err;
	
	/**
	 * <b>public RSdecoder(int nbr_corrected_error)</b><br/>
	 * Constructor for RSdecoder, initialize the number of error correction
	 *  
	 * @param nbr_corrected_error : number of corrected error
	 */
	public RSdecoder(int nbr_corrected_error) {
		nbr_corr_err = nbr_corrected_error;
		
		syndroms = new Galois[2*nbr_corr_err];
	}
	
	/**
	 * <b>public boolean decode(byte[] message)</b><br/>
	 * Correct the message and tell you if the function worked
	 * 
	 * @param message : message to correct
	 * @return A boolean if the message is corrected or not
	 */
	public boolean decode(byte[] message) {
		int i, j, k;
		
		// First we calculate the syndroms and check if there is error
		if (!calculate_syndroms(Polynom.byte2gal(message))) return true;
		
		// We prepare the linear Galois resolution to find the sigma
		Galois[][] synd_matrix = new Galois[nbr_corr_err][nbr_corr_err];
		Galois[] synd_result = new Galois[nbr_corr_err];
		for (i=0; i<nbr_corr_err; i++) {
			for (j=0; j<nbr_corr_err; j++) {
				synd_matrix[i][j] = syndroms[i+j];
			}
			synd_result[i] = syndroms[i+nbr_corr_err];
		}
		Linear lin_res = new Linear(synd_matrix, synd_result);
	
		// Linear resolution
		if (!lin_res.resolve()) return false;
		
		// in the case that the number of solutions are not nbr_corr_err we do it again
		if (lin_res.nbr_solutions() < nbr_corr_err) {
			int n = lin_res.nbr_solutions();
			synd_matrix = new Galois[n][n];
			synd_result = new Galois[n];
			for (i=0; i<n; i++) {
				for (j=0; j<n; j++) {
					synd_matrix[i][j] = syndroms[i+j];
				}
				synd_result[i] = syndroms[i+n];
			}
			lin_res = new Linear(synd_matrix, synd_result);
			if (!lin_res.resolve()) return false;
		}
		
		// we calculate now sigma
		Galois[] sigma = new Galois[lin_res.nbr_solutions()+1];
		lin_res.solutions(sigma);
		sigma[lin_res.nbr_solutions()] = new Galois((byte) 0x01);
		if (sigma.length == 1) return false;
		
		// find the localization of the errors
		int[] root = find_error_localization(sigma, message.length);
		if (root.length <= sigma.length/5) return false;
		
		// prepare to find error correction
		Galois[][] matrix = new Galois[root.length][root.length];
		Galois[] result = new Galois[root.length];
		for (i=0; i<root.length; i++) {
			for (j=0; j<root.length; j++) {
				matrix[i][j] = Galois.pow((i+1)*(message.length-root[j]-1));
			}
			result[i] = syndroms[i];
		}
		lin_res = new Linear(matrix, result);
		
		// Linear resolution and calculation of error correction
		if (!lin_res.resolve()) return false;
		if (lin_res.nbr_solutions()<root.length) return false;
		Galois[] correction = lin_res.solutions();
		
		// apply the correction
		for (k=0; k<root.length; k++) {
			Galois tmp = new Galois(message[root[k]]);
			tmp.add(correction[k]);
			message[root[k]] = tmp.toByte();
		}
			
		return true;
	}
	
	/**
	 * <b>private boolean calculate_syndroms(Galois[] msg)</b><br/>
	 * Calculation of the syndroms
	 * 
	 * @param msg : message to use for calculation of syndroms
	 * @return if the syndroms detect error or not
	 */
	private boolean calculate_syndroms(Galois[] msg) {
		int k;
		boolean no_error = true;
		for (k=0; k<nbr_corr_err; k++) {
			syndroms[k] = Polynom.evaluation(msg, k+1);
			no_error = no_error && syndroms[k].isNull();
		}
		if (no_error) return false;
		for (k=nbr_corr_err; k<2*nbr_corr_err; k++) {
			syndroms[k] = Polynom.evaluation(msg, k+1);
		}
		return true;
	}
	
	/**
	 * <b>private int[] find_error_localization(Galois[] poly, int length)</b><br/>
	 * Find the error localization calculating the root of <b>poly</b> and inverted them
	 * 
	 * @param poly : polynom to use for root research (sigma)
	 * @param length : length of the root research
	 * @return an array with the position of the error
	 */
	private int[] find_error_localization(Galois[] poly, int length) {
		int[] localization = new int[length];
		int nbr_root = 0;
		
		int k;
		for (k=256-length; k<=255; k++) {
			if (Polynom.evaluation(poly, k).isNull()) {
				localization[nbr_root] = k-256+length;
				nbr_root++;
			}
		}
		
		int[] result = new int[nbr_root];
		for (k=0; k<nbr_root; k++) {
			result[k] = localization[k];
		}
		return result;
		
	}
	
}
