2
0

bigint_impl.h 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
  1. /*
  2. * Copyright (c) 2007, Cameron Rich
  3. *
  4. * All rights reserved.
  5. *
  6. * Redistribution and use in source and binary forms, with or without
  7. * modification, are permitted provided that the following conditions are met:
  8. *
  9. * * Redistributions of source code must retain the above copyright notice,
  10. * this list of conditions and the following disclaimer.
  11. * * Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. * * Neither the name of the axTLS project nor the names of its contributors
  15. * may be used to endorse or promote products derived from this software
  16. * without specific prior written permission.
  17. *
  18. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19. * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20. * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21. * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  22. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  23. * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  24. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  25. * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  26. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  27. * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  28. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29. */
  30. #ifndef BIGINT_IMPL_HEADER
  31. #define BIGINT_IMPL_HEADER
  32. /* Maintain a number of precomputed variables when doing reduction */
  33. #define BIGINT_M_OFFSET 0 /**< Normal modulo offset. */
  34. #ifdef CONFIG_BIGINT_CRT
  35. #define BIGINT_P_OFFSET 1 /**< p modulo offset. */
  36. #define BIGINT_Q_OFFSET 2 /**< q module offset. */
  37. #define BIGINT_NUM_MODS 3 /**< The number of modulus constants used. */
  38. #else
  39. #define BIGINT_NUM_MODS 1
  40. #endif
  41. /* Architecture specific functions for big ints */
  42. #ifdef WIN32
  43. #define COMP_RADIX 4294967296i64
  44. #define COMP_MAX 0xFFFFFFFFFFFFFFFFui64
  45. #else
  46. #define COMP_RADIX 4294967296ULL /**< Max component + 1 */
  47. #define COMP_MAX 0xFFFFFFFFFFFFFFFFULL/**< (Max dbl comp -1) */
  48. #endif
  49. #define COMP_BIT_SIZE 32 /**< Number of bits in a component. */
  50. #define COMP_BYTE_SIZE 4 /**< Number of bytes in a component. */
  51. #define COMP_NUM_NIBBLES 8 /**< Used For diagnostics only. */
  52. typedef uint32_t comp; /**< A single precision component. */
  53. typedef uint64_t long_comp; /**< A double precision component. */
  54. typedef int64_t slong_comp; /**< A signed double precision component. */
  55. /**
  56. * @struct _bigint
  57. * @brief A big integer basic object
  58. */
  59. struct _bigint
  60. {
  61. struct _bigint* next; /**< The next bigint in the cache. */
  62. short size; /**< The number of components in this bigint. */
  63. short max_comps; /**< The heapsize allocated for this bigint */
  64. int refs; /**< An internal reference count. */
  65. comp* comps; /**< A ptr to the actual component data */
  66. };
  67. typedef struct _bigint bigint; /**< An alias for _bigint */
  68. /**
  69. * Maintains the state of the cache, and a number of variables used in
  70. * reduction.
  71. */
  72. typedef struct /**< A big integer "session" context. */
  73. {
  74. bigint *active_list; /**< Bigints currently used. */
  75. bigint *free_list; /**< Bigints not used. */
  76. bigint *bi_radix; /**< The radix used. */
  77. bigint *bi_mod[BIGINT_NUM_MODS]; /**< modulus */
  78. #if defined(CONFIG_BIGINT_MONTGOMERY)
  79. bigint *bi_RR_mod_m[BIGINT_NUM_MODS]; /**< R^2 mod m */
  80. bigint *bi_R_mod_m[BIGINT_NUM_MODS]; /**< R mod m */
  81. comp N0_dash[BIGINT_NUM_MODS];
  82. #elif defined(CONFIG_BIGINT_BARRETT)
  83. bigint *bi_mu[BIGINT_NUM_MODS]; /**< Storage for mu */
  84. #endif
  85. bigint *bi_normalised_mod[BIGINT_NUM_MODS]; /**< Normalised mod storage. */
  86. bigint **g; /**< Used by sliding-window. */
  87. int window; /**< The size of the sliding window */
  88. int active_count; /**< Number of active bigints. */
  89. int free_count; /**< Number of free bigints. */
  90. #ifdef CONFIG_BIGINT_MONTGOMERY
  91. uint8_t use_classical; /**< Use classical reduction. */
  92. #endif
  93. uint8_t mod_offset; /**< The mod offset we are using */
  94. } BI_CTX;
  95. #ifndef WIN32
  96. #define max(a,b) ((a)>(b)?(a):(b)) /**< Find the maximum of 2 numbers. */
  97. #define min(a,b) ((a)<(b)?(a):(b)) /**< Find the minimum of 2 numbers. */
  98. #endif
  99. #define PERMANENT 0x7FFF55AA /**< A magic number for permanents. */
  100. #endif