/shared/development/google_code/rssoft/library/lib/GFq.h

Go to the documentation of this file.

/*
     Copyright 2013 Edouard Griffiths <f4exb at free dot fr>

     This file is part of RSSoft. A Reed-Solomon Soft Decoding library

     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., 51 Franklin Street, Boston, MA  02110-1301  USA

         Original from Arash Partow (see original copytight notice).
         Modified and included in RSSoft in gf sub-namespace.

         Galois Field GF(q=2^m) class

*/
/*
 *********************************************************************
 *                                                                   *
 *        Galois Field Arithmetic Library (version 0.0.1)            *
 *                                                                   *
 * Class: Galois Field                                               *
 * Author: Arash Partow - 2000                                       *
 * URL: http://www.partow.net/projects/galois/index.html             *
 *                                                                   *
 * Copyright Notice:                                                 *
 * Free use of this library is permitted under the guidelines and    *
 * in accordance with the most current version of the Common Public  *
 * License.                                                          *
 * http://www.opensource.org/licenses/cpl.php                        *
 *                                                                   *
 *********************************************************************
 */

#ifndef __GFQ_H__
#define __GFQ_H__

#include "GF2_Polynomial.h"
#include <iostream>
#include <vector>
#include <string.h>

namespace rssoft
{
namespace gf
{
typedef int GFq_Symbol;        
const GFq_Symbol GFERROR = -1; 

class GFq
{

public:
        GFq(const int pwr, const GF2_Polynomial& primitive_poly);
        GFq(const GFq& gf);
        ~GFq();

        GFq& operator=(const GFq& gf);
        bool operator==(const GFq& gf) const;
        bool operator!=(const GFq& gf) const;

        inline unsigned int index(const GFq_Symbol value) const
        {
                return index_of[value];
        }

        inline GFq_Symbol alpha(const unsigned int power) const
        {
                return alpha_to[power];
        }

        inline unsigned int size() const
        {
                return field_size;
        }

        inline unsigned int pwr() const
        {
                return power;
        }

        inline GFq_Symbol add(const GFq_Symbol& a, const GFq_Symbol& b) const
        {
                return (a ^ b);
        }

        inline GFq_Symbol sub(const GFq_Symbol& a, const GFq_Symbol& b) const
        {
                return (a ^ b);
        }

        inline GFq_Symbol mul(const GFq_Symbol& a, const GFq_Symbol& b) const
        {
#if !defined(NO_GFLUT)
                return mul_table[a][b];
#else
                if ((a == 0) || (b == 0))
                {
                        return 0;
                }
                else
                {
                        return alpha_to[fast_modulus(index_of[a] + index_of[b])];
                }
#endif
        }

        inline GFq_Symbol div(const GFq_Symbol& a, const GFq_Symbol& b) const
        {
#if !defined(NO_GFLUT)
                return div_table[a][b];
#else
                if ((a == 0) || (b == 0))
                {
                        return 0;
                }
                else
                {
                        return alpha_to[fast_modulus(index_of[a] - index_of[b] + field_size)];
                }
#endif
        }

        inline GFq_Symbol exp(const GFq_Symbol& a, const int& n) const
        {
                if (n == 0)
                {
                        return 1;
                }
                else if (a == 0)
        {
            return 0;
        }
        else
        {
                unsigned int log_a = index_of[a];
                unsigned int log_a_pwr_n = log_a * n;
                return alpha_to[log_a_pwr_n % field_size];
        }
        }

/* Just does not work
        inline GFq_Symbol exp(const GFq_Symbol& a, const int& n) const
        {
        if (n == 0)
        {
            return 1;
        }
#if !defined(NO_GFLUT)
                if (n < 0)
                {
                        int b = n;
                        while (b < 0)
                        {
                                b += field_size; // b could be negative
                        }

                        if (b == 0)
                        {
                                return 1;
                        }
                        return exp_table[a][b];
                }
                else
                {
                        return exp_table[a][n & field_size];
                }
#else
                if (a != 0)
                {
                        if (n < 0)
                        {
                                int b = n;
                                while(b < 0)
                                {
                                        b += field_size; // b could be negative
                                }
                                if (b == 0)
                                {
                                        return 1;
                                }
                                return alpha_to[fast_modulus(index_of[a] * b)];
                        }
                        else if (n == 0)
                        {
                                return 1;
                        }
                        else
                        {
                                return alpha_to[fast_modulus(index_of[a] * n)];
                        }
                }
                else
                {
                        return 0;
                }
#endif
        }
*/

        inline GFq_Symbol inverse(const GFq_Symbol& val) const
        {
#if !defined(NO_GFLUT)
                return mul_inverse[val];
#else
                return alpha_to[fast_modulus(field_size - index_of[val])];
#endif
        }

        friend std::ostream& operator <<(std::ostream& os, const GFq& gf);

private:

        void generate_field();
        GFq_Symbol fast_modulus(GFq_Symbol x) const;
        GFq_Symbol gen_mul(const GFq_Symbol& a, const GFq_Symbol& b) const;
        GFq_Symbol gen_div(const GFq_Symbol& a, const GFq_Symbol& b) const;
        GFq_Symbol gen_exp(const GFq_Symbol& a, const unsigned int& n) const;
        GFq_Symbol gen_inverse(const GFq_Symbol& val) const;

        unsigned int power;                   
        unsigned int field_size;              
    const GF2_Polynomial& primitive_poly; 
        unsigned int prim_poly_hash;          
        GFq_Symbol* alpha_to;                 
        GFq_Symbol* index_of;                 
        GFq_Symbol* mul_inverse;              
        GFq_Symbol** mul_table;               
        GFq_Symbol** div_table;               
        GFq_Symbol** exp_table;               

};

} // namespace gf
} // namespace rssoft

#endif // __GFQ_H__