Pull BN_mod_pow2 and BN_nnmod_pow2 out of BCM
These are not used by BCM anywhere.
Change-Id: Ifeee35f05c2c06e93c4bd3b684eed5a81bca09d4
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/78570
Auto-Submit: David Benjamin <davidben@google.com>
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/build.json b/build.json
index 9783857..41d30db 100644
--- a/build.json
+++ b/build.json
@@ -204,6 +204,7 @@
"crypto/blake2/blake2.cc",
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
+ "crypto/bn/div.cc",
"crypto/bn/exponentiation.cc",
"crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
diff --git a/crypto/bn/div.cc b/crypto/bn/div.cc
new file mode 100644
index 0000000..868a2a3
--- /dev/null
+++ b/crypto/bn/div.cc
@@ -0,0 +1,100 @@
+// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <openssl/bn.h>
+
+#include <openssl/err.h>
+
+#include "../fipsmodule/bn/internal.h"
+#include "../internal.h"
+
+
+int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) {
+ if (e == 0 || a->width == 0) {
+ BN_zero(r);
+ return 1;
+ }
+
+ size_t num_words = 1 + ((e - 1) / BN_BITS2);
+
+ // If |a| definitely has less than |e| bits, just BN_copy.
+ if ((size_t)a->width < num_words) {
+ return BN_copy(r, a) != NULL;
+ }
+
+ // Otherwise, first make sure we have enough space in |r|.
+ // Note that this will fail if num_words > INT_MAX.
+ if (!bn_wexpand(r, num_words)) {
+ return 0;
+ }
+
+ // Copy the content of |a| into |r|.
+ OPENSSL_memcpy(r->d, a->d, num_words * sizeof(BN_ULONG));
+
+ // If |e| isn't word-aligned, we have to mask off some of our bits.
+ size_t top_word_exponent = e % (sizeof(BN_ULONG) * 8);
+ if (top_word_exponent != 0) {
+ r->d[num_words - 1] &= (((BN_ULONG)1) << top_word_exponent) - 1;
+ }
+
+ // Fill in the remaining fields of |r|.
+ r->neg = a->neg;
+ r->width = (int)num_words;
+ bn_set_minimal_width(r);
+ return 1;
+}
+
+int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) {
+ if (!BN_mod_pow2(r, a, e)) {
+ return 0;
+ }
+
+ // If the returned value was non-negative, we're done.
+ if (BN_is_zero(r) || !r->neg) {
+ return 1;
+ }
+
+ size_t num_words = 1 + (e - 1) / BN_BITS2;
+
+ // Expand |r| to the size of our modulus.
+ if (!bn_wexpand(r, num_words)) {
+ return 0;
+ }
+
+ // Clear the upper words of |r|.
+ OPENSSL_memset(&r->d[r->width], 0, (num_words - r->width) * BN_BYTES);
+
+ // Set parameters of |r|.
+ r->neg = 0;
+ r->width = (int)num_words;
+
+ // Now, invert every word. The idea here is that we want to compute 2^e-|x|,
+ // which is actually equivalent to the twos-complement representation of |x|
+ // in |e| bits, which is -x = ~x + 1.
+ for (int i = 0; i < r->width; i++) {
+ r->d[i] = ~r->d[i];
+ }
+
+ // If our exponent doesn't span the top word, we have to mask the rest.
+ size_t top_word_exponent = e % BN_BITS2;
+ if (top_word_exponent != 0) {
+ r->d[r->width - 1] &= (((BN_ULONG)1) << top_word_exponent) - 1;
+ }
+
+ // Keep the minimal-width invariant for |BIGNUM|.
+ bn_set_minimal_width(r);
+
+ // Finally, add one, for the reason described above.
+ return BN_add(r, r, BN_value_one());
+}
diff --git a/crypto/fipsmodule/bn/div.cc.inc b/crypto/fipsmodule/bn/div.cc.inc
index 374e6e1..a29bf9c 100644
--- a/crypto/fipsmodule/bn/div.cc.inc
+++ b/crypto/fipsmodule/bn/div.cc.inc
@@ -732,82 +732,3 @@
}
return (BN_ULONG)ret;
}
-
-int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) {
- if (e == 0 || a->width == 0) {
- BN_zero(r);
- return 1;
- }
-
- size_t num_words = 1 + ((e - 1) / BN_BITS2);
-
- // If |a| definitely has less than |e| bits, just BN_copy.
- if ((size_t)a->width < num_words) {
- return BN_copy(r, a) != NULL;
- }
-
- // Otherwise, first make sure we have enough space in |r|.
- // Note that this will fail if num_words > INT_MAX.
- if (!bn_wexpand(r, num_words)) {
- return 0;
- }
-
- // Copy the content of |a| into |r|.
- OPENSSL_memcpy(r->d, a->d, num_words * sizeof(BN_ULONG));
-
- // If |e| isn't word-aligned, we have to mask off some of our bits.
- size_t top_word_exponent = e % (sizeof(BN_ULONG) * 8);
- if (top_word_exponent != 0) {
- r->d[num_words - 1] &= (((BN_ULONG)1) << top_word_exponent) - 1;
- }
-
- // Fill in the remaining fields of |r|.
- r->neg = a->neg;
- r->width = (int)num_words;
- bn_set_minimal_width(r);
- return 1;
-}
-
-int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) {
- if (!BN_mod_pow2(r, a, e)) {
- return 0;
- }
-
- // If the returned value was non-negative, we're done.
- if (BN_is_zero(r) || !r->neg) {
- return 1;
- }
-
- size_t num_words = 1 + (e - 1) / BN_BITS2;
-
- // Expand |r| to the size of our modulus.
- if (!bn_wexpand(r, num_words)) {
- return 0;
- }
-
- // Clear the upper words of |r|.
- OPENSSL_memset(&r->d[r->width], 0, (num_words - r->width) * BN_BYTES);
-
- // Set parameters of |r|.
- r->neg = 0;
- r->width = (int)num_words;
-
- // Now, invert every word. The idea here is that we want to compute 2^e-|x|,
- // which is actually equivalent to the twos-complement representation of |x|
- // in |e| bits, which is -x = ~x + 1.
- for (int i = 0; i < r->width; i++) {
- r->d[i] = ~r->d[i];
- }
-
- // If our exponent doesn't span the top word, we have to mask the rest.
- size_t top_word_exponent = e % BN_BITS2;
- if (top_word_exponent != 0) {
- r->d[r->width - 1] &= (((BN_ULONG)1) << top_word_exponent) - 1;
- }
-
- // Keep the minimal-width invariant for |BIGNUM|.
- bn_set_minimal_width(r);
-
- // Finally, add one, for the reason described above.
- return BN_add(r, r, BN_value_one());
-}
diff --git a/gen/sources.bzl b/gen/sources.bzl
index ff0f337..390c651 100644
--- a/gen/sources.bzl
+++ b/gen/sources.bzl
@@ -303,6 +303,7 @@
"crypto/blake2/blake2.cc",
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
+ "crypto/bn/div.cc",
"crypto/bn/exponentiation.cc",
"crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
diff --git a/gen/sources.cmake b/gen/sources.cmake
index 5536c13..ccdde32 100644
--- a/gen/sources.cmake
+++ b/gen/sources.cmake
@@ -317,6 +317,7 @@
crypto/blake2/blake2.cc
crypto/bn/bn_asn1.cc
crypto/bn/convert.cc
+ crypto/bn/div.cc
crypto/bn/exponentiation.cc
crypto/bn/sqrt.cc
crypto/buf/buf.cc
diff --git a/gen/sources.gni b/gen/sources.gni
index ade8cd3..1b50f09 100644
--- a/gen/sources.gni
+++ b/gen/sources.gni
@@ -303,6 +303,7 @@
"crypto/blake2/blake2.cc",
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
+ "crypto/bn/div.cc",
"crypto/bn/exponentiation.cc",
"crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
diff --git a/gen/sources.json b/gen/sources.json
index a7cc03a..d4f4c2d 100644
--- a/gen/sources.json
+++ b/gen/sources.json
@@ -287,6 +287,7 @@
"crypto/blake2/blake2.cc",
"crypto/bn/bn_asn1.cc",
"crypto/bn/convert.cc",
+ "crypto/bn/div.cc",
"crypto/bn/exponentiation.cc",
"crypto/bn/sqrt.cc",
"crypto/buf/buf.cc",
diff --git a/gen/sources.mk b/gen/sources.mk
index 7db953e..3c6285d 100644
--- a/gen/sources.mk
+++ b/gen/sources.mk
@@ -297,6 +297,7 @@
crypto/blake2/blake2.cc \
crypto/bn/bn_asn1.cc \
crypto/bn/convert.cc \
+ crypto/bn/div.cc \
crypto/bn/exponentiation.cc \
crypto/bn/sqrt.cc \
crypto/buf/buf.cc \
