1 // ==========================================================================
2 // Copyright(c)'1994-2010 by The Givaro group
3 // This file is part of Givaro.
4 // Givaro is governed by the CeCILL-B license under French law
5 // and abiding by the rules of distribution of free software.
6 // see the COPYRIGHT file for more details.
7 // file: gfqkronecker.h
8 // Time-stamp: <12 Apr 10 16:45:02 Jean-Guillaume.Dumas@imag.fr>
9 // date: 2007
10 // version:
11 // author: Jean-Guillaume.Dumas
12 
13 /*! @file gfqkronecker.h
14  * @ingroup zpz
15  * @brief  Arithmetic on GF(p^k), with dynamic Kronecker substitution.
16  * @pre  k(p-1)^2 < word size
17  */
18 
19 #ifndef __GIVARO_gfq_kronecker_H
20 #define __GIVARO_gfq_kronecker_H
21 
22 #include "givaro/givzpz.h"
23 #include "givaro/givzpzInt.h"
24 #include "givaro/gfq.h"
25 #include "givaro/givpower.h"
26 #include <limits>
27 #include <vector>
28 #include <deque>
29 
30 namespace Givaro {
31 
32 	//! GFqKronecker
33 template<class TT, class Ints> struct GFqKronecker : public GFqDom<TT> {
34 protected:
35     typedef typename Signed_Trait<TT>::unsigned_type UTT;
36     typedef TT Rep;
37     typedef GFqDom<TT> Father_t;
38 
39 public:
40     typedef GFqKronecker<TT,Ints> Self_t;
41 
42     typedef Rep Element;
43     typedef Element* Element_ptr ;
44   typedef const Element* ConstElement_ptr;
45 
46 
47     typedef UTT Residu_t;
48 
49     typedef Rep* Array;
50     typedef const Rep* constArray;
51 
52     typedef ModularRandIter< Father_t , Rep> RandIter;
53 
GFqKroneckerGFqKronecker54     GFqKronecker(): Father_t() {}
55 
56         // Extension MUST be a parameter of the constructor
GFqKroneckerGFqKronecker57     GFqKronecker( const UTT P, const UTT e) : Father_t(P,e), _degree(e-1),_epmunsq(e*(P-1)*(P-1))  {
58         buildsmalltables();
59         setShift(std::numeric_limits<UTT>::digits/( (e<<1)-1) );
60     }
61 
getMaxnGFqKronecker62     Ints getMaxn() const {
63 	return _sMAXN;
64     }
getShiftGFqKronecker65     UTT getShift() const {
66 	return _SHIFTS;
67     }
getBaseGFqKronecker68     UTT getBase() const {
69 	return _sBASE;
70     }
71 
72         // Set shifts, returns maxn
setShiftGFqKronecker73     Ints setShift(const Ints& i) {
74         _SHIFTS=i;
75         _sBASE = Ints(1); _sBASE <<=_SHIFTS;
76         _sMASK = _sBASE - 1;
77         return _sMAXN = _sBASE / _epmunsq;
78     }
79 
80         // Set maxn, returns shifts
setMaxnGFqKronecker81     UTT setMaxn(const Ints& n) {
82         _sMAXN = n;
83         Ints m = _sMAXN * _epmunsq;
84         _SHIFTS = 0;
85         for(_sBASE = 1; _sBASE < m; ++_SHIFTS, _sBASE<<=1);
86         _sMASK = _sBASE - 1;
87         return _SHIFTS;
88     }
89 
90 
~GFqKroneckerGFqKronecker91     virtual ~GFqKronecker() {};
92 
93     using Father_t::init;
94     using Father_t::convert;
95 
convertGFqKronecker96     virtual Ints& convert(Ints& r, const Rep a) const {
97             // First Step
98             // 	from element to polynomial coefficient binary shifted
99         UTT binpol=_log2bin[a];
100             // Second step
101             // 	from a0|a1|...|ad
102             // 	to 0-0ad | ... | 0-0a1 | 0-0a0
103         r = binpol & _pMASK; // a0
104         for(size_t i=1; i<this->_exponent; ++i) {
105             r <<= _SHIFTS;
106             binpol >>= _pceil;
107             r |= ( binpol & _pMASK);
108         }
109         return r;
110     }
111 
112 
113 
initGFqKronecker114     virtual Rep& init(Rep& a, const Ints r) const {
115             // WARNING: This could be speeded up with a REDQ transform
116 
117             // First Step lower part
118             // 	from rd | ... | r1 | r0
119             // 	to   a0|a1|...|ad
120             // 	where ai = ri mod p
121         Ints rs=r;
122         UTT binpolLOW = (UTT)( (rs & _sMASK) % this->_characteristic);
123         for(size_t i=1; i<this->_exponent; ++i) {
124             binpolLOW <<= _pceil;
125             rs >>= _SHIFTS;
126             binpolLOW |= (UTT)( (rs & _sMASK) % this->_characteristic);
127         }
128             // First Step upper part
129         rs >>= _SHIFTS;
130         UTT binpolHIGH = (UTT)( (rs & _sMASK) % this->_characteristic);
131         for(size_t i=1; i<this->_degree; ++i) {
132             binpolHIGH <<= _pceil;
133             rs >>= _SHIFTS;
134             binpolHIGH |= (UTT)( (rs & _sMASK) % this->_characteristic);
135         }
136         binpolHIGH <<= _pceil;
137 
138             // Second step
139             //  transform to element H*X^k+L
140         return this->axpy(a, _bin2log[binpolHIGH], _Xk, _bin2log[binpolLOW]);
141     }
142 
143 
144 
145 
146 protected:
147     std::ostream& polywrite(std::ostream& out, const Element& a, const Indeter In= "B") const {
148         static Modular<Integer> Zp(this->_characteristic);
149         static Poly1PadicDom<Modular<Integer> > PAD(Zp ,In);
150         static Poly1PadicDom<Modular<Integer> >::Element pol;
151         Integer r;
152         PAD.radixdirect(pol, this->convert(r, a), this->_exponent);
153         return PAD.write(out, pol);
154     }
155 
156 
buildsmalltablesGFqKronecker157     void buildsmalltables() {
158         _log2bin.resize(this->_log2pol.size());
159         _pceil = 1;
160         for(unsigned long ppow = 2; ppow < this->_characteristic; ppow <<= 1,++_pceil) {}
161         _pMASK = (1<<_pceil) - 1;
162 
163         Father_t Zp(this->_characteristic,1);
164         typedef Poly1FactorDom< Father_t, Dense > PolDom;
165         PolDom Pdom( Zp );
166         typedef Poly1PadicDom< Father_t, Dense > PadicDom;
167         PadicDom PAD(Pdom);
168 
169         typename std::vector<UTT>::iterator binit = _log2bin.begin();
170         typename std::vector<UTT>::const_iterator polit = this->_log2pol.begin();
171         for( ; polit != this->_log2pol.end(); ++polit, ++binit) {
172 
173             std::vector<unsigned long> vect;
174             PAD.radixdirect( vect, (unsigned long)(*polit), this->_exponent);
175 
176             *binit = vect[0];
177             for(size_t i =1; i<this->_exponent; ++i) {
178                 *binit <<= _pceil;
179                 *binit += vect[i];
180             }
181         }
182 
183         _bin2log.resize( 1<<(_pceil*this->_exponent) );
184         for(size_t i=0; i<_log2bin.size(); ++i)
185             _bin2log[ _log2bin[ i ] ] = i;
186 
187 
188             // This is X
189         _Xk = this->_pol2log[this->_characteristic];
190 //         polywrite(std::cerr << "Xk: " << _Xk << " rep ", _Xk) << std::endl;
191             // This is X^{e}
192         dom_power(_Xk,_Xk,this->_exponent,*this);
193 //         polywrite(std::cerr << "Xk: ", _Xk) << std::endl;
194     }
195 
196 
197 
198     UTT _SHIFTS;
199     Ints _sBASE,_sMASK,_sMAXN;
200 
201     UTT _pceil,_pMASK,_degree;
202     Ints _epmunsq;
203 
204     std::vector<UTT> _log2bin;
205     std::vector<UTT> _bin2log;
206 
207     Element _Xk;
208 };
209 
210 } // namespace Givaro
211 
212 #endif // __GIVARO_gfq_kronecker_H
213 /* -*- mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
214 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s
215