Move |bn_div_words| to crypto/bn/div.c and make it static.
It is only used by |bn_div_rem_words|.
Change-Id: I57627091d8db5890d7fea34d8560897717008646
Reviewed-on: https://boringssl-review.googlesource.com/7128
Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/bn/div.c b/crypto/bn/div.c
index 69791f7..6f67291 100644
--- a/crypto/bn/div.c
+++ b/crypto/bn/div.c
@@ -56,12 +56,86 @@
#include <openssl/bn.h>
+#include <assert.h>
#include <limits.h>
#include <openssl/err.h>
#include "internal.h"
+#if !defined(BN_ULLONG)
+/* bn_div_words divides a double-width |h|,|l| by |d| and returns the result,
+ * which must fit in a |BN_ULONG|. */
+static BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) {
+ BN_ULONG dh, dl, q, ret = 0, th, tl, t;
+ int i, count = 2;
+
+ if (d == 0) {
+ return BN_MASK2;
+ }
+
+ i = BN_num_bits_word(d);
+ assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i));
+
+ i = BN_BITS2 - i;
+ if (h >= d) {
+ h -= d;
+ }
+
+ if (i) {
+ d <<= i;
+ h = (h << i) | (l >> (BN_BITS2 - i));
+ l <<= i;
+ }
+ dh = (d & BN_MASK2h) >> BN_BITS4;
+ dl = (d & BN_MASK2l);
+ for (;;) {
+ if ((h >> BN_BITS4) == dh) {
+ q = BN_MASK2l;
+ } else {
+ q = h / dh;
+ }
+
+ th = q * dh;
+ tl = dl * q;
+ for (;;) {
+ t = h - th;
+ if ((t & BN_MASK2h) ||
+ ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4)))) {
+ break;
+ }
+ q--;
+ th -= dh;
+ tl -= dl;
+ }
+ t = (tl >> BN_BITS4);
+ tl = (tl << BN_BITS4) & BN_MASK2h;
+ th += t;
+
+ if (l < tl) {
+ th++;
+ }
+ l -= tl;
+ if (h < th) {
+ h += d;
+ q--;
+ }
+ h -= th;
+
+ if (--count == 0) {
+ break;
+ }
+
+ ret = q << BN_BITS4;
+ h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
+ l = (l & BN_MASK2l) << BN_BITS4;
+ }
+
+ ret |= q;
+ return ret;
+}
+#endif /* !defined(BN_ULLONG) */
+
static inline void bn_div_rem_words(BN_ULONG *quotient_out, BN_ULONG *rem_out,
BN_ULONG n0, BN_ULONG n1, BN_ULONG d0) {
/* GCC and Clang generate function calls to |__udivdi3| and |__umoddi3| when
diff --git a/crypto/bn/generic.c b/crypto/bn/generic.c
index b7fedca..f552d99 100644
--- a/crypto/bn/generic.c
+++ b/crypto/bn/generic.c
@@ -202,80 +202,6 @@
}
}
-#if !defined(BN_ULLONG)
-
-/* Divide h,l by d and return the result. */
-BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) {
- BN_ULONG dh, dl, q, ret = 0, th, tl, t;
- int i, count = 2;
-
- if (d == 0) {
- return BN_MASK2;
- }
-
- i = BN_num_bits_word(d);
- assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i));
-
- i = BN_BITS2 - i;
- if (h >= d) {
- h -= d;
- }
-
- if (i) {
- d <<= i;
- h = (h << i) | (l >> (BN_BITS2 - i));
- l <<= i;
- }
- dh = (d & BN_MASK2h) >> BN_BITS4;
- dl = (d & BN_MASK2l);
- for (;;) {
- if ((h >> BN_BITS4) == dh) {
- q = BN_MASK2l;
- } else {
- q = h / dh;
- }
-
- th = q * dh;
- tl = dl * q;
- for (;;) {
- t = h - th;
- if ((t & BN_MASK2h) ||
- ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4)))) {
- break;
- }
- q--;
- th -= dh;
- tl -= dl;
- }
- t = (tl >> BN_BITS4);
- tl = (tl << BN_BITS4) & BN_MASK2h;
- th += t;
-
- if (l < tl) {
- th++;
- }
- l -= tl;
- if (h < th) {
- h += d;
- q--;
- }
- h -= th;
-
- if (--count == 0) {
- break;
- }
-
- ret = q << BN_BITS4;
- h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
- l = (l & BN_MASK2l) << BN_BITS4;
- }
-
- ret |= q;
- return ret;
-}
-
-#endif /* !defined(BN_ULLONG) */
-
#ifdef BN_ULLONG
BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
int n) {
diff --git a/crypto/bn/internal.h b/crypto/bn/internal.h
index e8a2bdd..1e78dc2 100644
--- a/crypto/bn/internal.h
+++ b/crypto/bn/internal.h
@@ -224,10 +224,6 @@
#error "Either BN_ULLONG or BN_UMULT_LOHI must be defined on every platform."
#endif
-#if !defined(BN_ULLONG)
-BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d);
-#endif
-
#if defined(__cplusplus)
} /* extern C */