mpi-internal.h 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  1. /* SPDX-License-Identifier: GPL-2.0-or-later */
  2. /* mpi-internal.h - Internal to the Multi Precision Integers
  3. * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
  4. * Copyright (C) 1998, 2000 Free Software Foundation, Inc.
  5. *
  6. * This file is part of GnuPG.
  7. *
  8. * Note: This code is heavily based on the GNU MP Library.
  9. * Actually it's the same code with only minor changes in the
  10. * way the data is stored; this is to support the abstraction
  11. * of an optional secure memory allocation which may be used
  12. * to avoid revealing of sensitive data due to paging etc.
  13. * The GNU MP Library itself is published under the LGPL;
  14. * however I decided to publish this code under the plain GPL.
  15. */
  16. #ifndef G10_MPI_INTERNAL_H
  17. #define G10_MPI_INTERNAL_H
  18. #include <linux/module.h>
  19. #include <linux/kernel.h>
  20. #include <linux/slab.h>
  21. #include <linux/string.h>
  22. #include <linux/mpi.h>
  23. #include <linux/errno.h>
  24. #define log_debug printk
  25. #define log_bug printk
  26. #define assert(x) \
  27. do { \
  28. if (!x) \
  29. log_bug("failed assertion\n"); \
  30. } while (0);
  31. /* If KARATSUBA_THRESHOLD is not already defined, define it to a
  32. * value which is good on most machines. */
  33. /* tested 4, 16, 32 and 64, where 16 gave the best performance when
  34. * checking a 768 and a 1024 bit ElGamal signature.
  35. * (wk 22.12.97) */
  36. #ifndef KARATSUBA_THRESHOLD
  37. #define KARATSUBA_THRESHOLD 16
  38. #endif
  39. /* The code can't handle KARATSUBA_THRESHOLD smaller than 2. */
  40. #if KARATSUBA_THRESHOLD < 2
  41. #undef KARATSUBA_THRESHOLD
  42. #define KARATSUBA_THRESHOLD 2
  43. #endif
  44. typedef mpi_limb_t *mpi_ptr_t; /* pointer to a limb */
  45. typedef int mpi_size_t; /* (must be a signed type) */
  46. #define RESIZE_IF_NEEDED(a, b) \
  47. do { \
  48. if ((a)->alloced < (b)) \
  49. mpi_resize((a), (b)); \
  50. } while (0)
  51. /* Copy N limbs from S to D. */
  52. #define MPN_COPY(d, s, n) \
  53. do { \
  54. mpi_size_t _i; \
  55. for (_i = 0; _i < (n); _i++) \
  56. (d)[_i] = (s)[_i]; \
  57. } while (0)
  58. #define MPN_COPY_INCR(d, s, n) \
  59. do { \
  60. mpi_size_t _i; \
  61. for (_i = 0; _i < (n); _i++) \
  62. (d)[_i] = (s)[_i]; \
  63. } while (0)
  64. #define MPN_COPY_DECR(d, s, n) \
  65. do { \
  66. mpi_size_t _i; \
  67. for (_i = (n)-1; _i >= 0; _i--) \
  68. (d)[_i] = (s)[_i]; \
  69. } while (0)
  70. /* Zero N limbs at D */
  71. #define MPN_ZERO(d, n) \
  72. do { \
  73. int _i; \
  74. for (_i = 0; _i < (n); _i++) \
  75. (d)[_i] = 0; \
  76. } while (0)
  77. #define MPN_NORMALIZE(d, n) \
  78. do { \
  79. while ((n) > 0) { \
  80. if ((d)[(n)-1]) \
  81. break; \
  82. (n)--; \
  83. } \
  84. } while (0)
  85. #define MPN_MUL_N_RECURSE(prodp, up, vp, size, tspace) \
  86. do { \
  87. if ((size) < KARATSUBA_THRESHOLD) \
  88. mul_n_basecase(prodp, up, vp, size); \
  89. else \
  90. mul_n(prodp, up, vp, size, tspace); \
  91. } while (0);
  92. /* Divide the two-limb number in (NH,,NL) by D, with DI being the largest
  93. * limb not larger than (2**(2*BITS_PER_MP_LIMB))/D - (2**BITS_PER_MP_LIMB).
  94. * If this would yield overflow, DI should be the largest possible number
  95. * (i.e., only ones). For correct operation, the most significant bit of D
  96. * has to be set. Put the quotient in Q and the remainder in R.
  97. */
  98. #define UDIV_QRNND_PREINV(q, r, nh, nl, d, di) \
  99. do { \
  100. mpi_limb_t _ql __maybe_unused; \
  101. mpi_limb_t _q, _r; \
  102. mpi_limb_t _xh, _xl; \
  103. umul_ppmm(_q, _ql, (nh), (di)); \
  104. _q += (nh); /* DI is 2**BITS_PER_MPI_LIMB too small */ \
  105. umul_ppmm(_xh, _xl, _q, (d)); \
  106. sub_ddmmss(_xh, _r, (nh), (nl), _xh, _xl); \
  107. if (_xh) { \
  108. sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
  109. _q++; \
  110. if (_xh) { \
  111. sub_ddmmss(_xh, _r, _xh, _r, 0, (d)); \
  112. _q++; \
  113. } \
  114. } \
  115. if (_r >= (d)) { \
  116. _r -= (d); \
  117. _q++; \
  118. } \
  119. (r) = _r; \
  120. (q) = _q; \
  121. } while (0)
  122. /*-- mpiutil.c --*/
  123. mpi_ptr_t mpi_alloc_limb_space(unsigned nlimbs);
  124. void mpi_free_limb_space(mpi_ptr_t a);
  125. void mpi_assign_limb_space(MPI a, mpi_ptr_t ap, unsigned nlimbs);
  126. static inline mpi_limb_t mpihelp_add_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  127. mpi_size_t s1_size, mpi_limb_t s2_limb);
  128. mpi_limb_t mpihelp_add_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  129. mpi_ptr_t s2_ptr, mpi_size_t size);
  130. static inline mpi_limb_t mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
  131. mpi_ptr_t s2_ptr, mpi_size_t s2_size);
  132. static inline mpi_limb_t mpihelp_sub_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  133. mpi_size_t s1_size, mpi_limb_t s2_limb);
  134. mpi_limb_t mpihelp_sub_n(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  135. mpi_ptr_t s2_ptr, mpi_size_t size);
  136. static inline mpi_limb_t mpihelp_sub(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
  137. mpi_ptr_t s2_ptr, mpi_size_t s2_size);
  138. /*-- mpih-cmp.c --*/
  139. int mpihelp_cmp(mpi_ptr_t op1_ptr, mpi_ptr_t op2_ptr, mpi_size_t size);
  140. /*-- mpih-mul.c --*/
  141. struct karatsuba_ctx {
  142. struct karatsuba_ctx *next;
  143. mpi_ptr_t tspace;
  144. mpi_size_t tspace_size;
  145. mpi_ptr_t tp;
  146. mpi_size_t tp_size;
  147. };
  148. void mpihelp_release_karatsuba_ctx(struct karatsuba_ctx *ctx);
  149. mpi_limb_t mpihelp_addmul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  150. mpi_size_t s1_size, mpi_limb_t s2_limb);
  151. mpi_limb_t mpihelp_submul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  152. mpi_size_t s1_size, mpi_limb_t s2_limb);
  153. int mpihelp_mul(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t usize,
  154. mpi_ptr_t vp, mpi_size_t vsize, mpi_limb_t *_result);
  155. void mpih_sqr_n_basecase(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size);
  156. void mpih_sqr_n(mpi_ptr_t prodp, mpi_ptr_t up, mpi_size_t size,
  157. mpi_ptr_t tspace);
  158. void mpihelp_mul_n(mpi_ptr_t prodp,
  159. mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t size);
  160. int mpihelp_mul_karatsuba_case(mpi_ptr_t prodp,
  161. mpi_ptr_t up, mpi_size_t usize,
  162. mpi_ptr_t vp, mpi_size_t vsize,
  163. struct karatsuba_ctx *ctx);
  164. /*-- generic_mpih-mul1.c --*/
  165. mpi_limb_t mpihelp_mul_1(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
  166. mpi_size_t s1_size, mpi_limb_t s2_limb);
  167. /*-- mpih-div.c --*/
  168. mpi_limb_t mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
  169. mpi_limb_t divisor_limb);
  170. mpi_limb_t mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
  171. mpi_ptr_t np, mpi_size_t nsize,
  172. mpi_ptr_t dp, mpi_size_t dsize);
  173. mpi_limb_t mpihelp_divmod_1(mpi_ptr_t quot_ptr,
  174. mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
  175. mpi_limb_t divisor_limb);
  176. /*-- generic_mpih-[lr]shift.c --*/
  177. mpi_limb_t mpihelp_lshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
  178. unsigned cnt);
  179. mpi_limb_t mpihelp_rshift(mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
  180. unsigned cnt);
  181. /* Define stuff for longlong.h. */
  182. #define W_TYPE_SIZE BITS_PER_MPI_LIMB
  183. typedef mpi_limb_t UWtype;
  184. typedef unsigned int UHWtype;
  185. #if defined(__GNUC__)
  186. typedef unsigned int UQItype __attribute__ ((mode(QI)));
  187. typedef int SItype __attribute__ ((mode(SI)));
  188. typedef unsigned int USItype __attribute__ ((mode(SI)));
  189. typedef int DItype __attribute__ ((mode(DI)));
  190. typedef unsigned int UDItype __attribute__ ((mode(DI)));
  191. #else
  192. typedef unsigned char UQItype;
  193. typedef long SItype;
  194. typedef unsigned long USItype;
  195. #endif
  196. #ifdef __GNUC__
  197. #include "mpi-inline.h"
  198. #endif
  199. #endif /*G10_MPI_INTERNAL_H */