1  /*
       2   * Copyright (c) 2008-2020 Stefan Krah. All rights reserved.
       3   *
       4   * Redistribution and use in source and binary forms, with or without
       5   * modification, are permitted provided that the following conditions
       6   * are met:
       7   *
       8   * 1. Redistributions of source code must retain the above copyright
       9   *    notice, this list of conditions and the following disclaimer.
      10   *
      11   * 2. Redistributions in binary form must reproduce the above copyright
      12   *    notice, this list of conditions and the following disclaimer in the
      13   *    documentation and/or other materials provided with the distribution.
      14   *
      15   * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
      16   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      17   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      18   * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
      19   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
      20   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
      21   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
      22   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
      23   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
      24   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
      25   * SUCH DAMAGE.
      26   */
      27  
      28  
      29  #include "mpdecimal.h"
      30  
      31  #include <assert.h>
      32  #include <stdio.h>
      33  
      34  #include "bits.h"
      35  #include "difradix2.h"
      36  #include "fnt.h"
      37  #include "numbertheory.h"
      38  
      39  
      40  /* Bignum: Fast transform for medium-sized coefficients. */
      41  
      42  
      43  /* forward transform, sign = -1 */
      44  int
      45  std_fnt(mpd_uint_t *a, mpd_size_t n, int modnum)
      46  {
      47      struct fnt_params *tparams;
      48  
      49      assert(ispower2(n));
      50      assert(n >= 4);
      51      assert(n <= 3*MPD_MAXTRANSFORM_2N);
      52  
      53      if ((tparams = _mpd_init_fnt_params(n, -1, modnum)) == NULL) {
      54          return 0;
      55      }
      56      fnt_dif2(a, n, tparams);
      57  
      58      mpd_free(tparams);
      59      return 1;
      60  }
      61  
      62  /* reverse transform, sign = 1 */
      63  int
      64  std_inv_fnt(mpd_uint_t *a, mpd_size_t n, int modnum)
      65  {
      66      struct fnt_params *tparams;
      67  
      68      assert(ispower2(n));
      69      assert(n >= 4);
      70      assert(n <= 3*MPD_MAXTRANSFORM_2N);
      71  
      72      if ((tparams = _mpd_init_fnt_params(n, 1, modnum)) == NULL) {
      73          return 0;
      74      }
      75      fnt_dif2(a, n, tparams);
      76  
      77      mpd_free(tparams);
      78      return 1;
      79  }