/*
 * RSDecoder.java - Implements decoding algorithm for Reed-Solomon codes.
 *
 * ------------------------------------------------------------------
 *
 * @begin[license]
 * Copyright (C) 2003  Kai Chen, Caltech
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * @author: Kai Chen
 * @email{kchen@cs.caltech.edu}
 * @end[license]
 *
 */


public class RSDecoder
{
    /* status flags */
    
    /* successfully decoded */
    public static final int SUCCESS = 1;
    /* no error */
    public static final int NO_ERROR = 0;
    /* too many erasures to decode */
    public static final int TOO_MANY_ERASURES = -1;
    /* v(0) == 0, we get divide by zero error when computing sigma */
    public static final int V_UNNORMALIZABLE = -2;
    /* deg(omega) >= deg(sigma) */
    public static final int DEGREE_ERROR = -3;
    /* sigma has too few roots */
    public static final int TOO_FEW_ROOTS = -4;
    /* sigma has multiple roots */
    public static final int MULTIPLE_ROOTS = -5;
    /* unspecified error */
    public static final int UNSPECIFIED_ERROR = -100;


    /* The finite field we are working with */
    protected GF gf;

    /* The received polynomial */
    protected GFPolynomial polyR;

    /* The Syndrome polynomial */
    protected GFPolynomial polyS;

    /* The Error polynomial */
    protected GFPolynomial polyE;

    /* The Code polynomial */
    protected GFPolynomial polyC;

    
    /* Number of erasures and errors */
    protected int numErasures, numErrors;

    /* 2*numErrors + numErasures <= r */
    protected int r;



    /*
     * post: constructs a default RSDecoder
     */
    public RSDecoder()
    {
        /* 
         * This depends on our assumption about the default GF constructor. 
         * Not a good practice.
         */
        this(new GF(), 16);
    }
    
    
    /*
     * post: constructs an RSDecoder over gf, capable of correcting r erasures.
     */
    public RSDecoder(GF gf, int r)
    {
        this.gf = gf;
        this.r = r;
    }


    /*
     * post: returns the GF we are working with
     */
    public GF getGF()
    {
        return gf;
    }


    /*
     * post: returns number of correctable erasures
     */
    public int getR()
    {
        return r;
    }


    /*
     * post: returns the received polynomial
     */
    public GFPolynomial getPolyR()
    {
        return polyR;
    }


    /*
     * post: returns the syndrome polynomial
     */
    public GFPolynomial getPolyS()
    {
        return polyS;
    }


    /*
     * post: returns the error polynomial
     */
    public GFPolynomial getPolyE()
    {
        return polyE;
    }


    /*
     * post: returns the code polynomial
     */
    public GFPolynomial getPolyC()
    {
        return polyC;
    }


    /*
     * pre:  rCoeff is the coefficents of the recieved polynomial
     *       erasures are coded with some negative value.
     * post: decode time-domain or frequency-domain decoding.
     *       returns the decoding status
     */
    public int decode(int rCoeff[], boolean time) throws RSException
    {
        /* reset */
        numErasures = numErrors = 0;
        
        /* sigma0 = \Pi_{i \in I0} (1 - \alpha^i x) */
        GFPolynomial sigma0 = new GFPolynomial(gf, 1);

        for(int i=0; i<rCoeff.length; i++){
            if(rCoeff[i]<0){
                rCoeff[i] = 0;
                /* (1 - \alpha^{i}x) */
                int termCoeff[] = {1, gf.neg(gf.power(i))};
                GFPolynomial term = new GFPolynomial(gf, termCoeff);
                sigma0 = sigma0.mul(term);
                numErasures ++;
            }
        }

        /* check if we have too many erasures */
        if(numErasures>r) return TOO_MANY_ERASURES;

        /* construct the received polynomial */
        polyR = new GFPolynomial(gf, rCoeff);

        /* 
         * next we compute the syndrome:
         * for j = 1, 2, ... r, Sj = Sum(i from 0 to n-1, Ri*\alpha^{ij}
         * we can first do a dft on R to generate a vector of length r+1, 
         * then divide by x.
         */
        polyS = polyR.dft(r+1);
        int xCoeff[] = {0, 1};
        GFPolynomial x = new GFPolynomial(gf, xCoeff);
        polyS = polyS.div(x);


        /* if syndrome is 0, there is no error */
        if(polyS.isZero()) return NO_ERROR;
        
        /*
         * now compute S0:
         * S0 = sigma0*S mod x^r
         */
        GFPolynomial polyS0 = (sigma0.mul(polyS));
        polyS0.setDegree(r-1);


        /* now we perform Euclid's algorithm */
        Euclid eu = new Euclid(gf);

        /* mu = floor((r-numErasures)/2) */
        int mu = (r-numErasures)/2;
        /* gamma = ceiling((r+numErasures)/2) - 1 */
        int gamma = (r+numErasures-1)/2;

        /* x^r polynomial */
        int xtorCoeff[] = new int[r+1];
        xtorCoeff[r] = 1;
        GFPolynomial xtor = new GFPolynomial(gf, xtorCoeff);
        eu.runEuclid(xtor, polyS0, mu, gamma);
        
        /* v(0) */
        int v0 = eu.getV().getCoeffAt(0);

        /* if v(0) == 0, gcd(sigma, omega) != 0 */
        if(v0==0) return V_UNNORMALIZABLE;

        /* compute sigma and omega */
        GFPolynomial sigma = eu.getV().divScaler(v0).mul(sigma0);
        GFPolynomial omega = eu.getR().divScaler(v0);

        /* check if deg(omega) >= deg(sigma) */
        if(omega.getDegree() >= sigma.getDegree()) 
            return DEGREE_ERROR;

        /* now completion */
        if(time)
            return timeCompletion(sigma, omega);

        return freqCompletion(sigma, omega);
    }


    /*
     * pre: sigma and omega are properly computed
     * post: computes time-domain completion
     *       returns current decoding status
     */
    protected int timeCompletion(GFPolynomial sigma, GFPolynomial omega) 
        throws RSException
    {
        /* formal derivative of sigma */
        GFPolynomial sigma_prime = sigma.deriv();

        /* alpha has order n */
        int n = gf.orderOfAlpha();

        /* the error pattern */
        int errors[] = new int[n];

        /* we also count number of roots of sigma */
        int numRoots = 0;
        
        for(int i=0; i<n; i++){
            int alpha = gf.power(-i);
            if(sigma.eval(alpha)==0){
                int a = sigma_prime.eval(alpha);
                if(a!=0)
                    errors[i] = gf.neg(gf.div(omega.eval(alpha), a));
                else
                    return MULTIPLE_ROOTS;
                    
                numRoots ++;
            }
            else
                errors[i] = 0;
        }

        /* check if we have too few roots */
        if(numRoots < sigma.getDegree())
            return TOO_FEW_ROOTS;

        /* sets the error and code polynomial */
        polyE = new GFPolynomial(gf, errors);
        polyC = polyR.sub(polyE);
            
        return SUCCESS;
    }


    /*
     * TODO: implement frequency-domain completion
     */
    protected int freqCompletion(GFPolynomial sigma, GFPolynomial omega) 
        throws RSException
    {
        return UNSPECIFIED_ERROR;
    }



    /*
     * A testdrive for RSDecoder
     */
    public static void main(String[] args)
    {
        /* this corresponds to Example 9.8 in the red book */

        /* build the GF */
        int gfPoly[] = {1, 1, 0, 1};
        GF gf = new GF(2, 3, gfPoly);

        /* received polynomial */
        int rCoeff[] = 
            {gf.power(3), gf.power(1), 1, gf.power(2), 0, gf.power(3), 1};
            
        GFPolynomial polyR = new GFPolynomial(gf, rCoeff);

        /* decode */
        RSDecoder decoder = new RSDecoder(gf, 4);
        System.out.println(decoder);
       
        try{
            int errno = decoder.decode(rCoeff, true);
            System.out.println(errno);
            System.out.println(polyR);
            System.out.println(decoder.getPolyR()); 
            System.out.println(decoder.getPolyS());
            System.out.println(decoder.getPolyC());
        }catch(RSException ex){
            ex.printStackTrace();
        }
    }
}