split a number using OpenSSL's BIGNUM as quickly as possible

Question

I am using OpenSSL's BIGNUM library for arbitrary precision numbers.

I need to split a number in two pieces. I need the first n bits [0, n-1] in one number (by that I mean the n least significant bits), and the rest of the bits [n, end] in the other number.

The code I have that does works is this

void number_split(BIGNUM * first_n_bits, BIGNUM * the_rest, BIGNUM * number, long n) {
    int i = 0;

    BN_copy(first_n_bits, number);

    int bits = BN_num_bits(first_n_bits);

    while(bits > n) {
        BN_clear_bit(first_n_bits, --bits);
    }

    if(BN_num_bits(number) > n) {
        BN_rshift(the_rest, number, n);
    } else {
        BN_copy(the_rest, zero);
    }
}

I have determined that this function is one of the biggest contributors to execution time of my application, so making it a little faster would help me a lot.

The part that seems like it could be improved is the while loop where I am clearing the most significant bits one at a time. I would have thought that BIGNIM would have a function for accomplishing that more efficiently, but I couldn't find it.

So, what can I do to make this faster?

Answer 1

You can use the BN_mask_bits() function, which should be faster than looping over every bit.

// BN_num_bits(num) must be >= n
void number_split(BIGNUM *low_bits, BIGNUM *high_bits, BIGNUM *num, long n) {
  BN_copy(low_bits, num);
  BN_mask_bits(low_bits, n);
  BN_rshift(high_bits, num, n);
}

If it is possible that BN_num_bits(num) < n then add a check:

void number_split(BIGNUM *low_bits, BIGNUM *high_bits, BIGNUM *num, long n) {
  BN_copy(low_bits, num);
  if(BN_num_bits(num) <= n) {
    BN_copy(high_bits, zero);
  } else {
    BN_mask_bits(low_bits, n);
    BN_rshift(high_bits, num, n);
  }
}