fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold > Class Template Reference

#include <fft_blocks.hpp>

List of all members.

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

template<typename C, typename FFTER = fft_naive_transformer<C>, nat log2_outer_block_size = 9, nat log2_block_number = 7, nat log2_inner_block_size = 11, nat threshold = 12>
class mmx::fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >

Definition at line 31 of file fft_blocks.hpp.

Member Typedef Documentation

typedef implementation<vector_linear,vector_naive> NVec

Definition at line 33 of file fft_blocks.hpp.

typedef FFTER::R R

Definition at line 34 of file fft_blocks.hpp.

typedef R::S S

Definition at line 36 of file fft_blocks.hpp.

typedef R::U U

Definition at line 35 of file fft_blocks.hpp.

Constructor & Destructor Documentation

fft_blocks_transformer ( nat  n,
const format< C > &  fm 
) [inline]

Definition at line 44 of file fft_blocks.hpp.

00044                                                             :
00045     ffter (new FFTER (n, fm)),
00046     depth (ffter->depth), len (ffter->len), roots (ffter->roots) {}

~fft_blocks_transformer (  )  [inline]

Definition at line 48 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter.

00048 { delete ffter; }

Member Function Documentation

static void delocate ( C *  c1,
nat  s1,
C *  c0,
nat  s0,
nat  n 
) [inline, static]

Definition at line 51 of file fft_blocks.hpp.

References mmx::C.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

00051                                                  {
00052     for (nat i= 0; i < s1; i++, c0 += s0) {
00053       C* cc0= c0, * cc1= c1 + i;
00054       for (nat k= 0; k < n; k++, cc0++, cc1+= s1)
00055         *cc1= *cc0; } }

void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 159 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft().

00159                                                 {
00160     dfft (c, stride, shift, steps, 0, steps); }

void dfft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 65 of file fft_blocks.hpp.

References mmx::C, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::delocate(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter, max(), min(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::relocate().

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::direct_transform().

00065                                                                       {
00066     if (steps <= max (threshold, log2_inner_block_size))
00067       ffter->dfft (c, stride, shift, steps, step1, step2);
00068     else {
00069       nat temp_len= default_aligned_size<C>
00070         ((nat) 1<<(log2_outer_block_size+log2_block_number));
00071       C* c0, * temp= mmx_new<C> (temp_len);
00072       nat step, block, blocks, todo, k_beg, k_end;
00073 
00074       for (step= step1;
00075            step < min (steps - log2_inner_block_size, step2);
00076            step += block) {
00077         block = min (min (steps - log2_inner_block_size - step, step2 - step),
00078                      log2_outer_block_size);
00079         todo  = steps - 1 - step;
00080         blocks= todo - block + 1;
00081         c0= c;
00082         for (nat j= 0; j < ((nat) 1<<step); j++) {
00083           for (k_beg= 0; k_beg < ((nat) 1<<blocks); k_beg= k_end) {
00084             k_end= min (((nat) 1<<blocks),
00085                         k_beg + ((nat) 1<< log2_block_number));
00086             delocate (temp, (nat) 1<<block,
00087                       c0 + k_beg, stride<<blocks, k_end - k_beg);
00088             for (nat k= 0; k < k_end - k_beg; k++)
00089               ffter->dfft (temp+(k<<block), 1,
00090                            ((shift>>todo) + j)<<(block-1), block);
00091             relocate (temp, (nat) 1<<block,
00092                       c0+k_beg, stride<<blocks, k_end - k_beg);
00093           }
00094           c0 += (stride<<(todo+1));
00095         }
00096       }
00097       mmx_delete<C> (temp, temp_len);
00098       if (step < step2) {
00099         c0= c;
00100         todo= steps - 1 - step;
00101         for (nat j= 0; j < ((nat) 1<<step); j++) {
00102           ffter->dfft (c0, stride, ((shift>>todo) + j) << todo,
00103                        todo+1, 0, step2-step);
00104           c0 += (stride<<(todo+1));
00105         }
00106       }
00107     }
00108   }

void direct_transform ( C *  c  )  [inline]

Definition at line 167 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::depth, and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft().

00167                           {
00168     dfft (c, 1, 0, depth); }

void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps 
) [inline]

Definition at line 163 of file fft_blocks.hpp.

References fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

00163                                                 {
00164     ifft (c, stride, shift, steps, 0, steps); }

void ifft ( C *  c,
nat  stride,
nat  shift,
nat  steps,
nat  step1,
nat  step2 
) [inline]

Definition at line 111 of file fft_blocks.hpp.

References mmx::C, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::delocate(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ffter, max(), min(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::relocate().

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

00111                                                                       {
00112     if (steps <= max (threshold, log2_inner_block_size))
00113       ffter->ifft (c, stride, shift, steps, step1, step2);
00114     else {
00115       nat temp_len= default_aligned_size<C>
00116         ((nat) 1<<(log2_outer_block_size+log2_block_number));
00117       C* c0, * temp= mmx_new<C> (temp_len);
00118       nat step, block, blocks, todo, k_beg, k_end;
00119 
00120       if (log2_inner_block_size > steps - step2) {
00121         step= steps - log2_inner_block_size;
00122         c0= c;
00123         todo= steps - 1 - step;
00124         for (nat j= 0; j < ((nat) 1<<step); j++) {
00125           ffter->ifft (c0, stride, ((shift>>todo) + j) <<todo,
00126                        todo+1, max(0, (int) step1- (int) step), step2-step);
00127           c0 += (stride<<(todo+1));
00128         }
00129       }
00130       else
00131         step= step2;
00132 
00133       while (step > step1) {
00134         block = min (step - step1, log2_outer_block_size);
00135         step -= block;
00136         todo  = steps - 1 - step;
00137         blocks= todo - block + 1;
00138         c0= c;
00139         for (nat j= 0; j < ((nat) 1<<step); j++) {
00140           for (k_beg= 0; k_beg < ((nat) 1<<blocks); k_beg= k_end) {
00141             k_end= min (((nat) 1<<blocks),
00142                         k_beg + ((nat) 1<< log2_block_number));
00143             delocate (temp, (nat) 1<<block,
00144                       c0 + k_beg, stride<<blocks, k_end - k_beg);
00145             for (nat k= 0; k < k_end - k_beg; k++)
00146               ffter->ifft (temp+(k<<block), 1,
00147                            ((shift>>todo) + j)<<(block-1), block);
00148             relocate (temp, (nat) 1<<block,
00149                       c0+k_beg, stride<<blocks, k_end - k_beg);
00150           }
00151           c0 += (stride<<(todo+1));
00152         }
00153       }
00154       mmx_delete<C> (temp, temp_len);
00155     }
00156   }

void inverse_transform ( C *  c,
bool  divide = true 
) [inline]

Definition at line 171 of file fft_blocks.hpp.

References binpow(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::depth, fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), mmx::invert(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::len, and mmx::x.

00171                                              {
00172     ifft (c, 1, 0, depth);
00173     if (divide) {
00174       S x= binpow (S (2), depth);
00175       x= invert (x);
00176       NVec::template vec_unary_scalar<typename R::fft_mul_sc_op> (c, x, len);
00177     }
00178   }

static void relocate ( C *  c1,
nat  s1,
C *  c0,
nat  s0,
nat  n 
) [inline, static]

Definition at line 58 of file fft_blocks.hpp.

References mmx::C.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft().

00058                                                  {
00059     for (nat i= 0; i < s1; i++, c0 += s0) {
00060       C* cc0= c0, * cc1= c1 + i;
00061       for (nat k= 0; k < n; k++, cc0++, cc1+= s1)
00062         *cc0= *cc1; } }

Member Data Documentation

nat depth

Definition at line 39 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::direct_transform(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

FFTER* ffter

Definition at line 38 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::dfft(), fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::ifft(), and fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::~fft_blocks_transformer().

nat len

Definition at line 40 of file fft_blocks.hpp.

Referenced by fft_blocks_transformer< C, FFTER, log2_outer_block_size, log2_block_number, log2_inner_block_size, threshold >::inverse_transform().

U* roots

Definition at line 41 of file fft_blocks.hpp.

The documentation for this class was generated from the following file:
Generated on 6 Dec 2012 for algebramix by  doxygen 1.6.1