bn_add.c 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171
  1. /*
  2. * Copyright 1995-2018 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. /* signed add of b to a. */
  12. int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  13. {
  14. int ret, r_neg, cmp_res;
  15. bn_check_top(a);
  16. bn_check_top(b);
  17. if (a->neg == b->neg) {
  18. r_neg = a->neg;
  19. ret = BN_uadd(r, a, b);
  20. } else {
  21. cmp_res = BN_ucmp(a, b);
  22. if (cmp_res > 0) {
  23. r_neg = a->neg;
  24. ret = BN_usub(r, a, b);
  25. } else if (cmp_res < 0) {
  26. r_neg = b->neg;
  27. ret = BN_usub(r, b, a);
  28. } else {
  29. r_neg = 0;
  30. BN_zero(r);
  31. ret = 1;
  32. }
  33. }
  34. r->neg = r_neg;
  35. bn_check_top(r);
  36. return ret;
  37. }
  38. /* signed sub of b from a. */
  39. int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  40. {
  41. int ret, r_neg, cmp_res;
  42. bn_check_top(a);
  43. bn_check_top(b);
  44. if (a->neg != b->neg) {
  45. r_neg = a->neg;
  46. ret = BN_uadd(r, a, b);
  47. } else {
  48. cmp_res = BN_ucmp(a, b);
  49. if (cmp_res > 0) {
  50. r_neg = a->neg;
  51. ret = BN_usub(r, a, b);
  52. } else if (cmp_res < 0) {
  53. r_neg = !b->neg;
  54. ret = BN_usub(r, b, a);
  55. } else {
  56. r_neg = 0;
  57. BN_zero(r);
  58. ret = 1;
  59. }
  60. }
  61. r->neg = r_neg;
  62. bn_check_top(r);
  63. return ret;
  64. }
  65. /* unsigned add of b to a, r can be equal to a or b. */
  66. int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  67. {
  68. int max, min, dif;
  69. const BN_ULONG *ap, *bp;
  70. BN_ULONG *rp, carry, t1, t2;
  71. bn_check_top(a);
  72. bn_check_top(b);
  73. if (a->top < b->top) {
  74. const BIGNUM *tmp;
  75. tmp = a;
  76. a = b;
  77. b = tmp;
  78. }
  79. max = a->top;
  80. min = b->top;
  81. dif = max - min;
  82. if (bn_wexpand(r, max + 1) == NULL)
  83. return 0;
  84. r->top = max;
  85. ap = a->d;
  86. bp = b->d;
  87. rp = r->d;
  88. carry = bn_add_words(rp, ap, bp, min);
  89. rp += min;
  90. ap += min;
  91. while (dif) {
  92. dif--;
  93. t1 = *(ap++);
  94. t2 = (t1 + carry) & BN_MASK2;
  95. *(rp++) = t2;
  96. carry &= (t2 == 0);
  97. }
  98. *rp = carry;
  99. r->top += carry;
  100. r->neg = 0;
  101. bn_check_top(r);
  102. return 1;
  103. }
  104. /* unsigned subtraction of b from a, a must be larger than b. */
  105. int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
  106. {
  107. int max, min, dif;
  108. BN_ULONG t1, t2, borrow, *rp;
  109. const BN_ULONG *ap, *bp;
  110. bn_check_top(a);
  111. bn_check_top(b);
  112. max = a->top;
  113. min = b->top;
  114. dif = max - min;
  115. if (dif < 0) { /* hmm... should not be happening */
  116. BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);
  117. return 0;
  118. }
  119. if (bn_wexpand(r, max) == NULL)
  120. return 0;
  121. ap = a->d;
  122. bp = b->d;
  123. rp = r->d;
  124. borrow = bn_sub_words(rp, ap, bp, min);
  125. ap += min;
  126. rp += min;
  127. while (dif) {
  128. dif--;
  129. t1 = *(ap++);
  130. t2 = (t1 - borrow) & BN_MASK2;
  131. *(rp++) = t2;
  132. borrow &= (t1 == 0);
  133. }
  134. while (max && *--rp == 0)
  135. max--;
  136. r->top = max;
  137. r->neg = 0;
  138. bn_pollute(r);
  139. return 1;
  140. }