<commit_before>/*
 * Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012 <NAME>
 * Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012 Virginia Polytechnic
 *                                      Institute & State University
 *
 * This file is part of liquid.
 *
 * liquid 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 3 of the License, or
 * (at your option) any later version.
 *
 * liquid 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 liquid.  If not, see <http://www.gnu.org/licenses/>.
 */

//
// fft_mixed_radix.c : definitions for mixed-radix transforms using
//                     the Cooley-Tukey algorithm
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "liquid.internal.h"

#define FFT_DEBUG_MIXED_RADIX 0

// create FFT plan for regular DFT
//  _nfft   :   FFT size
//  _x      :   input array [size: _nfft x 1]
//  _y      :   output array [size: _nfft x 1]
//  _dir    :   fft direction: {FFT_FORWARD, FFT_REVERSE}
//  _method :   fft method
FFT(plan) FFT(_create_plan_mixed_radix)(unsigned int _nfft,
                                        TC *         _x,
                                        TC *         _y,
                                        int          _dir,
                                        int          _flags)
{
    // allocate plan and initialize all internal arrays to NULL
    FFT(plan) q = (FFT(plan)) malloc(sizeof(struct FFT(plan_s)));

    q->nfft      = _nfft;
    q->x         = _x;
    q->y         = _y;
    q->flags     = _flags;
    q->kind      = LIQUID_FFT_DFT_1D;
    q->direction = (_dir == FFT_FORWARD) ? FFT_FORWARD : FFT_REVERSE;
    q->method    = LIQUID_FFT_METHOD_MIXED_RADIX;

    q->execute   = FFT(_execute_mixed_radix);

    // find first 'prime' factor of _nfft
    unsigned int i;
    unsigned int Q=0;
    for (i=2; i<q->nfft; i++) {
        if ( (q->nfft % i)==0 ) {
            Q = i;
            break;
        }
    }
    if (Q==0) {
        fprintf(stderr,"error: fft_create_plan_mixed_radix(), _nfft=%u is prime\n", _nfft);
        exit(1);
    }

    // set mixed-radix data
    unsigned int P = q->nfft / Q;
    q->data.mixedradix.Q = Q;
    q->data.mixedradix.P = P;

    // allocate memory for buffers
    unsigned int t_len = Q > P ? Q : P;
    q->data.mixedradix.t0 = (TC *) malloc(t_len * sizeof(TC));
    q->data.mixedradix.t1 = (TC *) malloc(t_len * sizeof(TC));

    // allocate memory for input buffers
    q->data.mixedradix.x = (TC *) malloc(q->nfft * sizeof(TC));

    // create P-point FFT plan
    q->data.mixedradix.fft_P = FFT(_create_plan)(q->data.mixedradix.P,
                                                 q->data.mixedradix.t0,
                                                 q->data.mixedradix.t1,
                                                 q->direction,
                                                 q->flags);

    // create Q-point FFT plan<commit_msg>fft|mixed-radix: preferring Q=4 to Q=2 if possible (fewer recursions)<commit_after>/*
 * Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012 <NAME>
 * Copyright (c) 2007, 2008, 2009, 2010, 2011, 2012 Virginia Polytechnic
 *                                      Institute & State University
 *
 * This file is part of liquid.
 *
 * liquid 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 3 of the License, or
 * (at your option) any later version.
 *
 * liquid 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 liquid.  If not, see <http://www.gnu.org/licenses/>.
 */

//
// fft_mixed_radix.c : definitions for mixed-radix transforms using
//                     the Cooley-Tukey algorithm
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "liquid.internal.h"

#define FFT_DEBUG_MIXED_RADIX 0

// create FFT plan for regular DFT
//  _nfft   :   FFT size
//  _x      :   input array [size: _nfft x 1]
//  _y      :   output array [size: _nfft x 1]
//  _dir    :   fft direction: {FFT_FORWARD, FFT_REVERSE}
//  _method :   fft method
FFT(plan) FFT(_create_plan_mixed_radix)(unsigned int _nfft,
                                        TC *         _x,
                                        TC *         _y,
                                        int          _dir,
                                        int          _flags)
{
    // allocate plan and initialize all internal arrays to NULL
    FFT(plan) q = (FFT(plan)) malloc(sizeof(struct FFT(plan_s)));

    q->nfft      = _nfft;
    q->x         = _x;
    q->y         = _y;
    q->flags     = _flags;
    q->kind      = LIQUID_FFT_DFT_1D;
    q->direction = (_dir == FFT_FORWARD) ? FFT_FORWARD : FFT_REVERSE;
    q->method    = LIQUID_FFT_METHOD_MIXED_RADIX;

    q->execute   = FFT(_execute_mixed_radix);

    // find first 'prime' factor of _nfft
    unsigned int i;
    unsigned int Q=0;
    for (i=2; i<q->nfft; i++) {
        if ( (q->nfft % i)==0 ) {
            Q = i;
            break;
        }
    }
    if (Q==0) {
        fprintf(stderr,"error: fft_create_plan_mixed_radix(), _nfft=%u is prime\n", _nfft);
        exit(1);
    } if (Q==2 && (q->nfft % 4)==0) {
        // prefer Q=4 if possible
        Q = 4;
    }

    // set mixed-radix data
    unsigned int P = q->nfft / Q;
    q->data.mixedradix.Q = Q;
    q->data.mixedradix.P = P;

    // allocate memory for buffers
    unsigned int t_len = Q > P ? Q : P;
    q->data.mixedradix.t0 = (TC *) malloc(t_len * sizeof(TC));
    q->data.mixedradix.t1 = (TC *) malloc(t_len * sizeof(TC));

    // allocate memory for input buffers
    q->data.mixedradix.x = (TC *) malloc(q->nfft * sizeof(TC));

    // create P-point FFT plan
    q->data.mixedradix.fft_P = FFT(_create_plan)(q->data.mixedradix.P,
                                                 q->data.mixedradix.t0,
                                                 q->data.mixedradix.t1,
                                                 q->direction,
                                                 q->flags);

    // create Q-point FFT plan
{'fraction_non_alphanumeric': 0.11094652644052733, 'fraction_numerical': 0.019404532661827876, 'mean_word_length': 1.717102615694165, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 64, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1659010', 'n_tokens_mistral': 2292, 'n_tokens_neox': 2096, 'n_words': 633}