integrity-test: check code and ro segments of libnttfft
[strongswan.git] / src / libstrongswan / math / libnttfft / ntt_fft_reduce.h
1 /*
2 * Copyright (C) 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 /**
17 * @defgroup ntt_fft ntt_fft
18 * @{ @ingroup ntt_p
19 */
20
21 #ifndef NTT_REDUCE_H_
22 #define NTT_REDUCE_H_
23
24 #include "ntt_fft_params.h"
25
26 /**
27 * Montgomery Reduction
28 *
29 * Montgomery, P. L. Modular multiplication without trial division.
30 * Mathematics of Computation 44, 170 (1985), 519–521.
31 */
32 static inline uint32_t ntt_fft_mreduce(uint32_t x, const ntt_fft_params_t *p)
33 {
34 uint32_t m, t;
35
36 m = (x * p->q_inv) & p->rmask;
37 t = (x + m * p->q) >> p->rlog;
38
39 return (t < p->q) ? t : t - p->q;
40 }
41
42 #endif /** NTT_REDUCE_H_ @}*/