int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx)
  {
  int ret;

  bn_check_top(n);
  if ((b->A == NULL) || (b->Ai == NULL))
    {
    BNerr(BN_F_BN_BLINDING_INVERT_EX,BN_R_NOT_INITIALIZED);
    return(0);
    }

  if (r != NULL)
    ret = BN_mod_mul(n, n, r, b->mod, ctx);
  else
    ret = BN_mod_mul(n, n, b->Ai, b->mod, ctx);

  if (ret >= 0)
    {
    if (!BN_BLINDING_update(b,ctx))
      return(0);
    }
  bn_check_top(n);
  return(ret);
  }

BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
	{
	int i;
	BN_ULONG *A;
	const BN_ULONG *B;

	bn_check_top(b);

	if (a == b) return(a);
	if (bn_wexpand(a,b->top) == NULL) return(NULL);

#if 1
	A=a->d;
	B=b->d;
	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
		{
		BN_ULONG a0,a1,a2,a3;
		a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
		A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
		}
	switch (b->top&3)
		{
		case 3: A[2]=B[2];
		case 2: A[1]=B[1];
		case 1: A[0]=B[0];
		case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */
		}
#else
	memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
#endif

	a->top=b->top;
	a->neg=b->neg;
	bn_check_top(a);
	return(a);
	}

static void
BN_POOL_release(BN_POOL *p, unsigned int num)
{
    unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;

    p->used -= num;
    while (num--) {
        bn_check_top(p->current->vals + offset);
        if (!offset) {
            offset = BN_CTX_POOL_SIZE - 1;
            p->current = p->current->prev;
        } else
            offset--;
    }
}

int bn_probable_prime_dh(BIGNUM *rnd, int bits,
                         const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
{
    int i, ret = 0;
    BIGNUM *t1;

    BN_CTX_start(ctx);
    if ((t1 = BN_CTX_get(ctx)) == NULL)
        goto err;

    if (!BN_priv_rand(rnd, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD))
        goto err;

    /* we need ((rnd-rem) % add) == 0 */

    if (!BN_mod(t1, rnd, add, ctx))
        goto err;
    if (!BN_sub(rnd, rnd, t1))
        goto err;
    if (rem == NULL) {
        if (!BN_add_word(rnd, 1))
            goto err;
    } else {
        if (!BN_add(rnd, rnd, rem))
            goto err;
    }

    /* we now have a random number 'rand' to test. */

 loop:
    for (i = 1; i < NUMPRIMES; i++) {
        /* check that rnd is a prime */
        BN_ULONG mod = BN_mod_word(rnd, (BN_ULONG)primes[i]);
        if (mod == (BN_ULONG)-1)
            goto err;
        if (mod <= 1) {
            if (!BN_add(rnd, rnd, add))
                goto err;
            goto loop;
        }
    }
    ret = 1;

 err:
    BN_CTX_end(ctx);
    bn_check_top(rnd);
    return ret;
}

int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
                       BN_CTX *ctx)
{
    int retn = 0;
#ifdef MONT_WORD
    BIGNUM *t;

    BN_CTX_start(ctx);
    if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
        retn = BN_from_montgomery_word(ret, t, mont);
    BN_CTX_end(ctx);
#else                           /* !MONT_WORD */
    BIGNUM *t1, *t2;

    BN_CTX_start(ctx);
    t1 = BN_CTX_get(ctx);
    t2 = BN_CTX_get(ctx);
    if (t1 == NULL || t2 == NULL)
        goto err;

    if (!BN_copy(t1, a))
        goto err;
    BN_mask_bits(t1, mont->ri);

    if (!BN_mul(t2, t1, &mont->Ni, ctx))
        goto err;
    BN_mask_bits(t2, mont->ri);

    if (!BN_mul(t1, t2, &mont->N, ctx))
        goto err;
    if (!BN_add(t2, a, t1))
        goto err;
    if (!BN_rshift(ret, t2, mont->ri))
        goto err;

#if !defined(BRANCH_FREE) || BRANCH_FREE==0
    if (BN_ucmp(ret, &(mont->N)) >= 0) {
        if (!BN_usub(ret, ret, &(mont->N)))
            goto err;
    }
#endif
    retn = 1;
    bn_check_top(ret);
 err:
    BN_CTX_end(ctx);
#endif                          /* MONT_WORD */
    return (retn);
}

/**
 * public static native long longInt(int)
 */
static long long NativeBN_longInt(JNIEnv* env, jclass cls, BIGNUM* a) {
    if (!oneValidHandle(env, a)) return -1;
    bn_check_top(a);
    int intLen = a->top;
    BN_ULONG* d = a->d;
    switch (intLen) {
    case 0:
        return 0;
    case 1:
        if (!a->neg) return d[0] & 0X00000000FFFFFFFFLL;
        else return -(d[0] & 0X00000000FFFFFFFFLL);
    default:
        if (!a->neg) return ((long long)d[1] << 32) | (d[0] & 0XFFFFFFFFLL);
        else return -(((long long)d[1] << 32) | (d[0] & 0XFFFFFFFFLL));
    }
}

/**
 * public static native int putULongInt(int, long, int)
 */
static jboolean NativeBN_putULongInt(JNIEnv* env, jclass cls, BIGNUM* a, unsigned long long dw, jboolean neg) {
    if (!oneValidHandle(env, a)) return FALSE;
    unsigned int hi = dw >> 32; // This shifts without sign extension.
    int lo = (int)dw; // This truncates implicitely.

    // cf. litEndInts2bn:
    bn_check_top(a);
        if (bn_wexpand(a, 2) != NULL) {
            a->d[0] = lo;
            a->d[1] = hi;
            a->top = 2;
            a->neg = neg;
            bn_correct_top(a);
            return TRUE;
        }
        else return FALSE;
}

int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx)
	{
	int ret;

	bn_check_top(n);
	if ((b->A == NULL) || (b->Ai == NULL))
		{
		BNerr(BN_F_BN_BLINDING_INVERT,BN_R_NOT_INITIALIZED);
		return(0);
		}
	if ((ret=BN_mod_mul(n,n,b->Ai,b->mod,ctx)) >= 0)
		{
		if (!BN_BLINDING_update(b,ctx))
			return(0);
		}
	return(ret);
	}

int bn_probable_prime_dh_coprime(BIGNUM *rnd, int bits, BN_CTX *ctx)
{
    int i;
    BIGNUM *offset_index;
    BIGNUM *offset_count;
    int ret = 0;

    OPENSSL_assert(bits > prime_multiplier_bits);

    BN_CTX_start(ctx);
    if ((offset_index = BN_CTX_get(ctx)) == NULL)
        goto err;
    if ((offset_count = BN_CTX_get(ctx)) == NULL)
        goto err;

    if (!BN_add_word(offset_count, prime_offset_count))
        goto err;

 loop:
    if (!BN_rand(rnd, bits - prime_multiplier_bits, 0, 1))
        goto err;
    if (BN_is_bit_set(rnd, bits))
        goto loop;
    if (!BN_rand_range(offset_index, offset_count))
        goto err;

    if (!BN_mul_word(rnd, prime_multiplier)
        || !BN_add_word(rnd, prime_offsets[BN_get_word(offset_index)]))
        goto err;

    /* we now have a random number 'rand' to test. */

    /* skip coprimes */
    for (i = first_prime_index; i < NUMPRIMES; i++) {
        /* check that rnd is a prime */
        if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
            goto loop;
        }
    }
    ret = 1;

 err:
    BN_CTX_end(ctx);
    bn_check_top(rnd);
    return ret;
}

/* BN_mod_lshift variant that may be used if  a  is non-negative
 * and less than  m */
int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
	{
	if (r != a)
		{
		if (BN_copy(r, a) == NULL) return 0;
		}

	while (n > 0)
		{
		int max_shift;
		
		/* 0 < r < m */
		max_shift = BN_num_bits(m) - BN_num_bits(r);
		/* max_shift >= 0 */

		if (max_shift < 0)
			{
			BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
			return 0;
			}

		if (max_shift > n)
			max_shift = n;

		if (max_shift)
			{
			if (!BN_lshift(r, r, max_shift)) return 0;
			n -= max_shift;
			}
		else
			{
			if (!BN_lshift1(r, r)) return 0;
			--n;
			}

		/* BN_num_bits(r) <= BN_num_bits(m) */

		if (BN_cmp(r, m) >= 0) 
			{
			if (!BN_sub(r, r, m)) return 0;
			}
		}
	bn_check_top(r);
	
	return 1;
	}

extern "C" void Java_java_math_NativeBN_putULongInt(JNIEnv* env, jclass, jlong a0, unsigned long long dw, jboolean neg) {
    if (!oneValidHandle(env, a0)) return;
    unsigned int hi = dw >> 32; // This shifts without sign extension.
    int lo = (int)dw; // This truncates implicitly.

    // cf. litEndInts2bn:
    BIGNUM* a = toBigNum(a0);
    bn_check_top(a);
    if (bn_wexpand(a, 2) != NULL) {
      a->d[0] = lo;
      a->d[1] = hi;
      a->top = 2;
      a->neg = neg;
      bn_correct_top(a);
    } else {
      throwExceptionIfNecessary(env);
    }
}

/* r := 2^len / m */
int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
	{
	int ret= -1;
	BIGNUM *t;

	BN_CTX_start(ctx);
	if((t = BN_CTX_get(ctx)) == NULL) goto err;

	if (!BN_set_bit(t,len)) goto err;

	if (!BN_div(r,NULL,t,m,ctx)) goto err;

	ret=len;
err:
	bn_check_top(r);
	BN_CTX_end(ctx);
	return(ret);
	}

/**
 * public static native int bitLength(int)
 */
static int NativeBN_bitLength(JNIEnv* env, jclass cls, BIGNUM* a) {
// We rely on: (BN_BITS2 == 32), i.e. BN_ULONG is unsigned int and has 4 bytes:
//
    if (!oneValidHandle(env, a)) return FALSE;
    bn_check_top(a);
    int intLen = a->top;
    if (intLen == 0) return 0;
    BN_ULONG* d = a->d;
    int i = intLen - 1;
    BN_ULONG msd = d[i]; // most significant digit
        if (a->neg) {
            // Handle negative values correctly:
            // i.e. decrement the msd if all other digits are 0:
            // while ((i > 0) && (d[i] != 0)) { i--; }
            do { i--; } while (!((i < 0) || (d[i] != 0)));
            if (i < 0) msd--; // Only if all lower significant digits are 0 we decrement the most significant one.
        }
        return (intLen - 1) * 32 + BN_num_bits_word(msd);
}

int BN_ucmp_word( const BN_ULONG *ap, const int aTop, const BIGNUM *b)	/* pcg */
	{
	int i;
	const BN_ULONG *bp;	
	BN_ULONG t1,t2;

	bn_check_top(b);

	i=aTop-b->top;
	if (i != 0) return(i);
	bp=b->d;
	for (i=aTop-1; i>=0; i--)
		{
		t1= ap[i];
		t2= bp[i];
		if (t1 != t2)
			return((t1 > t2) ? 1 : -1);
		}
	return(0);
	}

BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
	{
	unsigned int i,m;
	unsigned int n;
	BN_ULONG l;
	BIGNUM  *bn = NULL;
	
	if (ret == NULL)
		ret = bn = BN_new();
	if (ret == NULL) return(NULL);
	bn_check_top(ret);
	l=0;
	n=len;
	if (n == 0)
		{
		ret->top=0;
		return(ret);
		}
	i=((n-1)/BN_BYTES)+1;
	m=((n-1)%(BN_BYTES));
	if (bn_wexpand(ret, (int)i) == NULL)
		{
		//if (bn) BN_free(bn);
		return NULL;
		}
	ret->top=i;
	ret->neg=0;
	while (n--)
		{
		l=(l<<8L)| *(s++);
		if (m-- == 0)
			{
			ret->d[--i]=l;
			l=0;
			m=BN_BYTES-1;
			}
		}

	bn_correct_top(ret);
	return(ret);
	}

int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx)
  {
  int ret = 1;

  bn_check_top(n);

  if ((b->A == NULL) || (b->Ai == NULL))
    {
    BNerr(BN_F_BN_BLINDING_CONVERT_EX,BN_R_NOT_INITIALIZED);
    return(0);
    }

  if (r != NULL)
    {
    if (!BN_copy(r, b->Ai)) ret=0;
    }

  if (!BN_mod_mul(n,n,b->A,b->mod,ctx)) ret=0;
  
  return ret;
  }

int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
	{
	BIGNUM *abs_m = NULL;
	int ret;

	if (!BN_nnmod(r, a, m, ctx)) return 0;

	if (m->neg)
		{
		abs_m = BN_dup(m);
		if (abs_m == NULL) return 0;
		abs_m->neg = 0;
		}
	
	ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
	bn_check_top(r);

	if (abs_m)
		BN_free(abs_m);
	return ret;
	}

/**
 * public static native int[] bn2litEndInts(int, int[])
 * cf. litEndInts2bn
 */
static jintArray NativeBN_bn2litEndInts(JNIEnv* env, jclass cls, BIGNUM* a, jintArray to) {
    if (!oneValidHandle(env, a)) return NULL;
    jintArray returnJInts = to;
    bn_check_top(a);
    int len = a->top;
    if (len > 0) {
// FIXME: Currently ignoring array passed in to:
        returnJInts = (*env)->NewIntArray(env, len);
// FIXME: is it neccessary to check for returnJBytes != NULL?
        BN_ULONG* tmpInts = (BN_ULONG*)((*env)->GetPrimitiveArrayCritical(env, returnJInts, NULL));
        if (tmpInts != NULL) {
            int i = len; do { i--; tmpInts[i] = a->d[i]; } while (i > 0);
            (*env)->ReleasePrimitiveArrayCritical(env, returnJInts, tmpInts, 0);
            return returnJInts;
        }
        else return NULL;
    }
    else { // value = 0
        return NULL; // Client should not call when sign = 0!
    }
}

static void NativeBN_putULongInt(JNIEnv* env, jclass, jlong a0, jlong java_dw, jboolean neg) {
    if (!oneValidHandle(env, a0)) return;

    uint64_t dw = java_dw;

    // cf. litEndInts2bn:
    BIGNUM* a = toBigNum(a0);
    bn_check_top(a);
    if (bn_wexpand(a, 8/BN_BYTES) != NULL) {
#ifdef __LP64__
      a->d[0] = dw;
#else
      unsigned int hi = dw >> 32; // This shifts without sign extension.
      int lo = (int)dw; // This truncates implicitly.
      a->d[0] = lo;
      a->d[1] = hi;
#endif
      a->top = 8 / BN_BYTES;
      a->neg = neg;
      bn_correct_top(a);
    } else {

BN_BLINDING *BN_BLINDING_new (const BIGNUM * A, const BIGNUM * Ai, BIGNUM * mod)
{
    BN_BLINDING *ret = NULL;

    bn_check_top (mod);

    if ((ret = (BN_BLINDING *) OPENSSL_malloc (sizeof (BN_BLINDING))) == NULL)
    {
        BNerr (BN_F_BN_BLINDING_NEW, ERR_R_MALLOC_FAILURE);
        return (NULL);
    }
    memset (ret, 0, sizeof (BN_BLINDING));
    if (A != NULL)
    {
        if ((ret->A = BN_dup (A)) == NULL)
            goto err;
    }
    if (Ai != NULL)
    {
        if ((ret->Ai = BN_dup (Ai)) == NULL)
            goto err;
    }

    /* save a copy of mod in the BN_BLINDING structure */
    if ((ret->mod = BN_dup (mod)) == NULL)
        goto err;
    if (BN_get_flags (mod, BN_FLG_CONSTTIME) != 0)
        BN_set_flags (ret->mod, BN_FLG_CONSTTIME);

    /* Set the counter to the special value -1
     * to indicate that this is never-used fresh blinding
     * that does not need updating before first use. */
    ret->counter = -1;
    CRYPTO_THREADID_current (&ret->tid);
    return (ret);
  err:
    if (ret != NULL)
        BN_BLINDING_free (ret);
    return (NULL);
}