src/libstrongswan/math/libnttfft/tests/suites/test_ntt_fft.c

   1 /*
   2  * Copyright (C) 2014-2016 Andreas Steffen
   3  * HSR Hochschule fuer Technik Rapperswil
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  */
  15
  16 #include "test_suite.h"
  17
  18 #include <ntt_fft.h>
  19 #include <ntt_fft_reduce.h>
  20
  21 #include <time.h>
  22
  23 static const ntt_fft_params_t *fft_params[] = {
  24         &ntt_fft_17_8,
  25         &ntt_fft_12289_512,
  26         &ntt_fft_12289_1024
  27 };
  28
  29 START_TEST(test_ntt_fft_impulse)
  30 {
  31         ntt_fft_t *fft;
  32         uint16_t n = fft_params[_i]->n;
  33         uint32_t rq = (1 << fft_params[_i]->rlog) % fft_params[_i]->q;
  34         uint32_t x[n], X[n];
  35         int i;
  36
  37         for (i = 0; i < n; i++)
  38         {
  39                 x[i] = 0;
  40         }
  41         x[0] = 1;
  42
  43         fft = ntt_fft_create(fft_params[_i]);
  44         fft->transform(fft, x, X, FALSE);
  45
  46         for (i = 0; i < n; i++)
  47         {
  48                 ck_assert(X[i] == rq);
  49         }
  50         fft->transform(fft, X, x, TRUE);
  51
  52         for (i = 0; i < n; i++)
  53         {
  54                 ck_assert(x[i] == (i == 0));
  55         }
  56         fft->destroy(fft);
  57 }
  58 END_TEST
  59
  60 START_TEST(test_ntt_fft_wrap)
  61 {
  62         ntt_fft_t *fft;
  63         uint16_t n = fft_params[_i]->n;
  64         uint16_t q = fft_params[_i]->q;
  65         uint32_t x[n],y[n], X[n], Y[n];
  66         int i, j;
  67
  68         for (i = 0; i < n; i++)
  69         {
  70                 x[i] = i;
  71                 y[i] = 0;
  72         }
  73         fft = ntt_fft_create(fft_params[_i]);
  74         ck_assert(fft->get_size(fft) == n);
  75         ck_assert(fft->get_modulus(fft) == q);
  76         fft->transform(fft, x, X, FALSE);
  77
  78         for (j = 0; j < n; j++)
  79         {
  80                 y[j] = 1;
  81                 fft->transform(fft, y, Y, FALSE);
  82
  83                 for (i = 0; i < n; i++)
  84                 {
  85                         Y[i] = ntt_fft_mreduce(X[i] * Y[i], fft_params[_i]);
  86                 }
  87                 fft->transform(fft, Y, Y, TRUE);
  88
  89                 for (i = 0; i < n; i++)
  90                 {
  91                         ck_assert(Y[i] == ( i < j ? q - n - i + j : i - j));
  92                 }
  93                 y[j] = 0;
  94         }
  95         fft->destroy(fft);
  96 }
  97 END_TEST
  98
  99 START_TEST(test_ntt_fft_speed)
 100 {
 101         ntt_fft_t *fft;
 102         struct timespec start, stop;
 103         int i, m, count = 10000;
 104         int n = fft_params[_i]->n;
 105         uint32_t x[n], X[n];
 106
 107         for (i = 0; i < n; i++)
 108         {
 109                 x[i] = i;
 110         }
 111         fft = ntt_fft_create(fft_params[_i]);
 112
 113         clock_gettime(CLOCK_THREAD_CPUTIME_ID, &start);
 114         for (m = 0; m < count; m++)
 115         {
 116                 fft->transform(fft, x, X, FALSE);
 117                 fft->transform(fft, X, x, TRUE);
 118         }
 119         clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stop);
 120
 121         DBG0(DBG_LIB, "%d FFT-%d loops in %d ms\n", count, n,
 122                                   (stop.tv_nsec - start.tv_nsec) / 1000000 +
 123                                   (stop.tv_sec - start.tv_sec) * 1000);
 124
 125         for (i = 0; i < n; i++)
 126         {
 127                 ck_assert(x[i] == i);
 128         }
 129         fft->destroy(fft);
 130 }
 131 END_TEST
 132
 133 START_TEST(test_ntt_fft_init)
 134 {
 135         libnttfft_init();
 136 }
 137 END_TEST
 138
 139 Suite *ntt_fft_suite_create()
 140 {
 141         Suite *s;
 142         TCase *tc;
 143
 144         s = suite_create("ntt_fft");
 145
 146         tc = tcase_create("init");
 147         tcase_add_test(tc, test_ntt_fft_init);
 148         suite_add_tcase(s, tc);
 149
 150         tc = tcase_create("impulse");
 151         tcase_add_loop_test(tc, test_ntt_fft_impulse, 0, countof(fft_params));
 152         suite_add_tcase(s, tc);
 153
 154         tc = tcase_create("negative_wrap");
 155         tcase_add_loop_test(tc, test_ntt_fft_wrap, 0, countof(fft_params));
 156         suite_add_tcase(s, tc);
 157
 158         tc = tcase_create("speed");
 159         tcase_set_timeout(tc, 10);
 160         tcase_add_loop_test(tc, test_ntt_fft_speed, 1, countof(fft_params));
 161         suite_add_tcase(s, tc);
 162
 163         return s;
 164 }