int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
{
    int i, j, nw, lb, rb;
    BN_ULONG *t, *f;
    BN_ULONG l, tmp;
    bn_check_top(r);
    bn_check_top(a);
    if (n < 0) {
        BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
        return 0;
    }
    nw = n / BN_BITS2;
    rb = n % BN_BITS2;
    lb = BN_BITS2 - rb;
    if (nw >= a->top || a->top == 0) {
        BN_zero(r);
        return (1);
    }
    i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;
    if (r != a) {
        r->neg = a->neg;
        if (bn_wexpand(r, i) == NULL)
            return (0);
    } else {
        if (n == 0)
            return 1;
    }
    f = &(a->d[nw]);
    t = r->d;
    j = a->top - nw;
    r->top = i;
    if (rb == 0) {
        for (i = j; i != 0; i--)
            *(t++) = *(f++);
    } else {
        l = *(f++);
        for (i = j - 1; i != 0; i--) {
            tmp = (l >> rb) & BN_MASK2;
            l = *(f++);
            *(t++) = (tmp | (l << lb)) & BN_MASK2;
        }
        if ((l = (l >> rb) & BN_MASK2))
            *(t) = l;
    }
    bn_check_top(r);
    return (1);
}
['static int test_div_recip()\n{\n    BIGNUM *a, *b, *c, *d, *e;\n    BN_RECP_CTX *recp;\n    int i;\n    recp = BN_RECP_CTX_new();\n    a = BN_new();\n    b = BN_new();\n    c = BN_new();\n    d = BN_new();\n    e = BN_new();\n    for (i = 0; i < NUM0 + NUM1; i++) {\n        if (i < NUM1) {\n            BN_bntest_rand(a, 400, 0, 0);\n            BN_copy(b, a);\n            BN_lshift(a, a, i);\n            BN_add_word(a, i);\n        } else\n            BN_bntest_rand(b, 50 + 3 * (i - NUM1), 0, 0);\n        a->neg = rand_neg();\n        b->neg = rand_neg();\n        BN_RECP_CTX_set(recp, b, ctx);\n        BN_div_recp(d, c, a, recp, ctx);\n        BN_mul(e, d, b, ctx);\n        BN_add(d, e, c);\n        BN_sub(d, d, a);\n        if (!BN_is_zero(d)) {\n            printf("Reciprocal division test failed!\\n");\n            printf("a=");\n            BN_print_fp(stdout, a);\n            printf("\\nb=");\n            BN_print_fp(stdout, b);\n            printf("\\n");\n            return 0;\n        }\n    }\n    BN_free(a);\n    BN_free(b);\n    BN_free(c);\n    BN_free(d);\n    BN_free(e);\n    BN_RECP_CTX_free(recp);\n    return 1;\n}', 'int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)\n{\n    if (!BN_copy(&(recp->N), d))\n        return 0;\n    BN_zero(&(recp->Nr));\n    recp->num_bits = BN_num_bits(d);\n    recp->shift = 0;\n    return (1);\n}', 'int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m,\n                BN_RECP_CTX *recp, BN_CTX *ctx)\n{\n    int i, j, ret = 0;\n    BIGNUM *a, *b, *d, *r;\n    BN_CTX_start(ctx);\n    a = BN_CTX_get(ctx);\n    b = BN_CTX_get(ctx);\n    if (dv != NULL)\n        d = dv;\n    else\n        d = BN_CTX_get(ctx);\n    if (rem != NULL)\n        r = rem;\n    else\n        r = BN_CTX_get(ctx);\n    if (a == NULL || b == NULL || d == NULL || r == NULL)\n        goto err;\n    if (BN_ucmp(m, &(recp->N)) < 0) {\n        BN_zero(d);\n        if (!BN_copy(r, m)) {\n            BN_CTX_end(ctx);\n            return 0;\n        }\n        BN_CTX_end(ctx);\n        return (1);\n    }\n    i = BN_num_bits(m);\n    j = recp->num_bits << 1;\n    if (j > i)\n        i = j;\n    if (i != recp->shift)\n        recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N), i, ctx);\n    if (recp->shift == -1)\n        goto err;\n    if (!BN_rshift(a, m, recp->num_bits))\n        goto err;\n    if (!BN_mul(b, a, &(recp->Nr), ctx))\n        goto err;\n    if (!BN_rshift(d, b, i - recp->num_bits))\n        goto err;\n    d->neg = 0;\n    if (!BN_mul(b, &(recp->N), d, ctx))\n        goto err;\n    if (!BN_usub(r, m, b))\n        goto err;\n    r->neg = 0;\n    j = 0;\n    while (BN_ucmp(r, &(recp->N)) >= 0) {\n        if (j++ > 2) {\n            BNerr(BN_F_BN_DIV_RECP, BN_R_BAD_RECIPROCAL);\n            goto err;\n        }\n        if (!BN_usub(r, r, &(recp->N)))\n            goto err;\n        if (!BN_add_word(d, 1))\n            goto err;\n    }\n    r->neg = BN_is_zero(r) ? 0 : m->neg;\n    d->neg = m->neg ^ recp->N.neg;\n    ret = 1;\n err:\n    BN_CTX_end(ctx);\n    bn_check_top(dv);\n    bn_check_top(rem);\n    return (ret);\n}', 'BIGNUM *BN_CTX_get(BN_CTX *ctx)\n{\n    BIGNUM *ret;\n    CTXDBG_ENTRY("BN_CTX_get", ctx);\n    if (ctx->err_stack || ctx->too_many)\n        return NULL;\n    if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) {\n        ctx->too_many = 1;\n        BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);\n        return NULL;\n    }\n    BN_zero(ret);\n    ctx->used++;\n    CTXDBG_RET(ctx, ret);\n    return ret;\n}', 'int BN_set_word(BIGNUM *a, BN_ULONG w)\n{\n    bn_check_top(a);\n    if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)\n        return (0);\n    a->neg = 0;\n    a->d[0] = w;\n    a->top = (w ? 1 : 0);\n    bn_check_top(a);\n    return (1);\n}', 'static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)\n{\n    if (bits > (INT_MAX - BN_BITS2 + 1))\n        return NULL;\n    if (((bits+BN_BITS2-1)/BN_BITS2) <= (a)->dmax)\n        return a;\n    return bn_expand2((a),(bits+BN_BITS2-1)/BN_BITS2);\n}', 'int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)\n{\n    int i, j, nw, lb, rb;\n    BN_ULONG *t, *f;\n    BN_ULONG l, tmp;\n    bn_check_top(r);\n    bn_check_top(a);\n    if (n < 0) {\n        BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);\n        return 0;\n    }\n    nw = n / BN_BITS2;\n    rb = n % BN_BITS2;\n    lb = BN_BITS2 - rb;\n    if (nw >= a->top || a->top == 0) {\n        BN_zero(r);\n        return (1);\n    }\n    i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;\n    if (r != a) {\n        r->neg = a->neg;\n        if (bn_wexpand(r, i) == NULL)\n            return (0);\n    } else {\n        if (n == 0)\n            return 1;\n    }\n    f = &(a->d[nw]);\n    t = r->d;\n    j = a->top - nw;\n    r->top = i;\n    if (rb == 0) {\n        for (i = j; i != 0; i--)\n            *(t++) = *(f++);\n    } else {\n        l = *(f++);\n        for (i = j - 1; i != 0; i--) {\n            tmp = (l >> rb) & BN_MASK2;\n            l = *(f++);\n            *(t++) = (tmp | (l << lb)) & BN_MASK2;\n        }\n        if ((l = (l >> rb) & BN_MASK2))\n            *(t) = l;\n    }\n    bn_check_top(r);\n    return (1);\n}']