1 /* $OpenBSD: bn_primitives.c,v 1.2 2023/06/21 07:48:41 jsing Exp $ */
2 /*
3 * Copyright (c) 2023 Joel Sing <jsing@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 #include <openssl/bn.h>
19
20 #include "bn_arch.h"
21 #include "bn_internal.h"
22 #include "bn_local.h"
23
24 #ifndef HAVE_BN_CLZW
25 #ifndef HAVE_BN_WORD_CLZ
26 int
bn_word_clz(BN_ULONG w)27 bn_word_clz(BN_ULONG w)
28 {
29 BN_ULONG bits, mask, shift;
30
31 bits = shift = BN_BITS2;
32 mask = 0;
33
34 while ((shift >>= 1) != 0) {
35 bits += (shift & mask) - (shift & ~mask);
36 mask = bn_ct_ne_zero_mask(w >> bits);
37 }
38 bits += 1 & mask;
39
40 bits -= bn_ct_eq_zero(w);
41
42 return BN_BITS2 - bits;
43 }
44 #endif
45 #endif
46
47 #ifndef HAVE_BN_BITSIZE
48 int
bn_bitsize(const BIGNUM * bn)49 bn_bitsize(const BIGNUM *bn)
50 {
51 BN_ULONG n = 0, x = 0;
52 BN_ULONG mask, w;
53 int i = 0;
54
55 while (i < bn->top) {
56 w = bn->d[i];
57 mask = bn_ct_ne_zero_mask(w);
58 n = ((BN_ULONG)i & mask) | (n & ~mask);
59 x = (w & mask) | (x & ~mask);
60 i++;
61 }
62
63 return (n + 1) * BN_BITS2 - bn_clzw(x);
64 }
65 #endif
66