bn_word.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. /*
  2. * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include "internal/cryptlib.h"
  10. #include "bn_lcl.h"
  11. BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w)
  12. {
  13. #ifndef BN_LLONG
  14. BN_ULONG ret = 0;
  15. #else
  16. BN_ULLONG ret = 0;
  17. #endif
  18. int i;
  19. if (w == 0)
  20. return (BN_ULONG)-1;
  21. #ifndef BN_LLONG
  22. /*
  23. * If |w| is too long and we don't have BN_ULLONG then we need to fall
  24. * back to using BN_div_word
  25. */
  26. if (w > ((BN_ULONG)1 << BN_BITS4)) {
  27. BIGNUM *tmp = BN_dup(a);
  28. if (tmp == NULL)
  29. return (BN_ULONG)-1;
  30. ret = BN_div_word(tmp, w);
  31. BN_free(tmp);
  32. return ret;
  33. }
  34. #endif
  35. bn_check_top(a);
  36. w &= BN_MASK2;
  37. for (i = a->top - 1; i >= 0; i--) {
  38. #ifndef BN_LLONG
  39. /*
  40. * We can assume here that | w <= ((BN_ULONG)1 << BN_BITS4) | and so
  41. * | ret < ((BN_ULONG)1 << BN_BITS4) | and therefore the shifts here are
  42. * safe and will not overflow
  43. */
  44. ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
  45. ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
  46. #else
  47. ret = (BN_ULLONG) (((ret << (BN_ULLONG) BN_BITS2) | a->d[i]) %
  48. (BN_ULLONG) w);
  49. #endif
  50. }
  51. return (BN_ULONG)ret;
  52. }
  53. BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
  54. {
  55. BN_ULONG ret = 0;
  56. int i, j;
  57. bn_check_top(a);
  58. w &= BN_MASK2;
  59. if (!w)
  60. /* actually this an error (division by zero) */
  61. return (BN_ULONG)-1;
  62. if (a->top == 0)
  63. return 0;
  64. /* normalize input (so bn_div_words doesn't complain) */
  65. j = BN_BITS2 - BN_num_bits_word(w);
  66. w <<= j;
  67. if (!BN_lshift(a, a, j))
  68. return (BN_ULONG)-1;
  69. for (i = a->top - 1; i >= 0; i--) {
  70. BN_ULONG l, d;
  71. l = a->d[i];
  72. d = bn_div_words(ret, l, w);
  73. ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
  74. a->d[i] = d;
  75. }
  76. if ((a->top > 0) && (a->d[a->top - 1] == 0))
  77. a->top--;
  78. ret >>= j;
  79. if (!a->top)
  80. a->neg = 0; /* don't allow negative zero */
  81. bn_check_top(a);
  82. return ret;
  83. }
  84. int BN_add_word(BIGNUM *a, BN_ULONG w)
  85. {
  86. BN_ULONG l;
  87. int i;
  88. bn_check_top(a);
  89. w &= BN_MASK2;
  90. /* degenerate case: w is zero */
  91. if (!w)
  92. return 1;
  93. /* degenerate case: a is zero */
  94. if (BN_is_zero(a))
  95. return BN_set_word(a, w);
  96. /* handle 'a' when negative */
  97. if (a->neg) {
  98. a->neg = 0;
  99. i = BN_sub_word(a, w);
  100. if (!BN_is_zero(a))
  101. a->neg = !(a->neg);
  102. return i;
  103. }
  104. for (i = 0; w != 0 && i < a->top; i++) {
  105. a->d[i] = l = (a->d[i] + w) & BN_MASK2;
  106. w = (w > l) ? 1 : 0;
  107. }
  108. if (w && i == a->top) {
  109. if (bn_wexpand(a, a->top + 1) == NULL)
  110. return 0;
  111. a->top++;
  112. a->d[i] = w;
  113. }
  114. bn_check_top(a);
  115. return 1;
  116. }
  117. int BN_sub_word(BIGNUM *a, BN_ULONG w)
  118. {
  119. int i;
  120. bn_check_top(a);
  121. w &= BN_MASK2;
  122. /* degenerate case: w is zero */
  123. if (!w)
  124. return 1;
  125. /* degenerate case: a is zero */
  126. if (BN_is_zero(a)) {
  127. i = BN_set_word(a, w);
  128. if (i != 0)
  129. BN_set_negative(a, 1);
  130. return i;
  131. }
  132. /* handle 'a' when negative */
  133. if (a->neg) {
  134. a->neg = 0;
  135. i = BN_add_word(a, w);
  136. a->neg = 1;
  137. return i;
  138. }
  139. if ((a->top == 1) && (a->d[0] < w)) {
  140. a->d[0] = w - a->d[0];
  141. a->neg = 1;
  142. return 1;
  143. }
  144. i = 0;
  145. for (;;) {
  146. if (a->d[i] >= w) {
  147. a->d[i] -= w;
  148. break;
  149. } else {
  150. a->d[i] = (a->d[i] - w) & BN_MASK2;
  151. i++;
  152. w = 1;
  153. }
  154. }
  155. if ((a->d[i] == 0) && (i == (a->top - 1)))
  156. a->top--;
  157. bn_check_top(a);
  158. return 1;
  159. }
  160. int BN_mul_word(BIGNUM *a, BN_ULONG w)
  161. {
  162. BN_ULONG ll;
  163. bn_check_top(a);
  164. w &= BN_MASK2;
  165. if (a->top) {
  166. if (w == 0)
  167. BN_zero(a);
  168. else {
  169. ll = bn_mul_words(a->d, a->d, a->top, w);
  170. if (ll) {
  171. if (bn_wexpand(a, a->top + 1) == NULL)
  172. return 0;
  173. a->d[a->top++] = ll;
  174. }
  175. }
  176. }
  177. bn_check_top(a);
  178. return 1;
  179. }