crypto/bn/bn_sqrt.c:98: error: BUFFER_OVERRUN_L3
  Offset: [8, +oo] (⇐ [8, +oo] + [0, +oo]) Size: [0, 8388607] by call to `BN_mod_exp`.
Showing all 26 steps of the trace


crypto/bn/bn_sqrt.c:60:9: Call
58.   
59.       BN_CTX_start(ctx);
60.       A = BN_CTX_get(ctx);
              ^
61.       b = BN_CTX_get(ctx);
62.       q = BN_CTX_get(ctx);

crypto/bn/bn_ctx.c:229:5: Call
  227.       }
  228.       /* OK, make sure the returned bignum is "zero" */
  229.       BN_zero(ret);
             ^
  230.       ctx->used++;
  231.       CTXDBG_RET(ctx, ret);

crypto/bn/bn_lib.c:359:1: Parameter `*a->d`
    357.   }
    358.   
    359. > int BN_set_word(BIGNUM *a, BN_ULONG w)
    360.   {
    361.       bn_check_top(a);

crypto/bn/bn_lib.c:362:9: Call
    360.   {
    361.       bn_check_top(a);
    362.       if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
                   ^
    363.           return 0;
    364.       a->neg = 0;

crypto/bn/bn_lcl.h:660:1: Parameter `*a->d`
      658.                            const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
      659.   
      660. > static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
      661.   {
      662.       if (bits > (INT_MAX - BN_BITS2 + 1))

crypto/bn/bn_sqrt.c:98:14: Call
96.           if (!BN_add_word(q, 1))
97.               goto end;
98.           if (!BN_mod_exp(ret, A, q, p, ctx))
                    ^
99.               goto end;
100.           err = 0;

crypto/bn/bn_exp.c:89:1: Parameter `*a->d`
  87.   }
  88.   
  89. > int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
  90.                  BN_CTX *ctx)
  91.   {

crypto/bn/bn_exp.c:144:19: Call
  142.           } else
  143.   # endif
  144.               ret = BN_mod_exp_mont(r, a, p, m, ctx, NULL);
                           ^
  145.       } else
  146.   #endif

crypto/bn/bn_exp.c:296:1: Parameter `*a->d`
    294.   }
    295.   
    296. > int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
    297.                       const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
    298.   {

crypto/bn/bn_exp.c:359:10: Call
    357.       } else
    358.           aa = a;
    359.       if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx))
                    ^
    360.           goto err;               /* 1 */
    361.   

crypto/bn/bn_mont.c:222:1: Parameter `*a->d`
      220.   }
      221.   
      222. > int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
      223.                            BN_CTX *ctx)
      224.   {

crypto/bn/bn_mont.c:225:12: Call
      223.                            BN_CTX *ctx)
      224.   {
      225.       return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx);
                        ^
      226.   }
      227.   

crypto/bn/bn_mont.c:37:1: Parameter `*a->d`
        35.   }
        36.   
        37. > int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
        38.                             BN_MONT_CTX *mont, BN_CTX *ctx)
        39.   {

crypto/bn/bn_mont.c:70:14: Call
        68.               goto err;
        69.       } else {
        70.           if (!bn_mul_fixed_top(tmp, a, b, ctx))
                           ^
        71.               goto err;
        72.       }

crypto/bn/bn_mul.c:507:1: Parameter `*a->d`
          505.   }
          506.   
          507. > int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
          508.   {
          509.       int ret = 0;

crypto/bn/bn_mul.c:587:17: Call
          585.                   if (bn_wexpand(rr, k * 4) == NULL)
          586.                       goto err;
          587.                   bn_mul_part_recursive(rr->d, a->d, b->d,
                                 ^
          588.                                         j, al - j, bl - j, t->d);
          589.               } else {            /* al <= j || bl <= j */

crypto/bn/bn_mul.c:322:1: Parameter `n`
            320.    */
            321.   /* tnX may not be negative but less than n */
            322. > void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,
            323.                              int tna, int tnb, BN_ULONG *t)
            324.   {

crypto/bn/bn_mul.c:335:10: Call
            333.   
            334.       /* r=(a[0]-a[1])*(b[1]-b[0]) */
            335.       c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
                            ^
            336.       c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
            337.       neg = 0;

crypto/bn/bn_lib.c:706:1: Parameter `cl`
              704.    */
              705.   
              706. > int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
              707.   {
              708.       int n, i;

crypto/bn/bn_lib.c:723:12: Call
              721.           }
              722.       }
              723.       return bn_cmp_words(a, b, cl);
                                ^
              724.   }
              725.   

crypto/bn/bn_lib.c:679:1: <Offset trace>
677.   }
678.   
679. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
680.   {
681.       int i;

crypto/bn/bn_lib.c:679:1: Parameter `n`
                677.   }
                678.   
                679. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
                680.   {
                681.       int i;

crypto/bn/bn_lib.c:688:10: Assignment
                686.       if (aa != bb)
                687.           return ((aa > bb) ? 1 : -1);
                688.       for (i = n - 2; i >= 0; i--) {
                                ^
                689.           aa = a[i];
                690.           bb = b[i];

crypto/bn/bn_lib.c:679:1: <Length trace>
677.   }
678.   
679. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
680.   {
681.       int i;

crypto/bn/bn_lib.c:679:1: Parameter `*b`
                677.   }
                678.   
                679. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
                680.   {
                681.       int i;

crypto/bn/bn_lib.c:690:14: Array access: Offset: [8, +oo] (⇐ [8, +oo] + [0, +oo]) Size: [0, 8388607] by call to `BN_mod_exp` 
                688.       for (i = n - 2; i >= 0; i--) {
                689.           aa = a[i];
                690.           bb = b[i];
                                    ^
                691.           if (aa != bb)
                692.               return ((aa > bb) ? 1 : -1);

int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
{
    int i;
    BN_ULONG aa, bb;
    aa = a[n - 1];
    bb = b[n - 1];
    if (aa != bb)
        return ((aa > bb) ? 1 : -1);
    for (i = n - 2; i >= 0; i--) {
        aa = a[i];
        bb = b[i];
        if (aa != bb)
            return ((aa > bb) ? 1 : -1);
    }
    return 0;
}
['BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)\n{\n    BIGNUM *ret = in;\n    int err = 1;\n    int r;\n    BIGNUM *A, *b, *q, *t, *x, *y;\n    int e, i, j;\n    if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) {\n        if (BN_abs_is_word(p, 2)) {\n            if (ret == NULL)\n                ret = BN_new();\n            if (ret == NULL)\n                goto end;\n            if (!BN_set_word(ret, BN_is_bit_set(a, 0))) {\n                if (ret != in)\n                    BN_free(ret);\n                return NULL;\n            }\n            bn_check_top(ret);\n            return ret;\n        }\n        BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);\n        return NULL;\n    }\n    if (BN_is_zero(a) || BN_is_one(a)) {\n        if (ret == NULL)\n            ret = BN_new();\n        if (ret == NULL)\n            goto end;\n        if (!BN_set_word(ret, BN_is_one(a))) {\n            if (ret != in)\n                BN_free(ret);\n            return NULL;\n        }\n        bn_check_top(ret);\n        return ret;\n    }\n    BN_CTX_start(ctx);\n    A = BN_CTX_get(ctx);\n    b = BN_CTX_get(ctx);\n    q = BN_CTX_get(ctx);\n    t = BN_CTX_get(ctx);\n    x = BN_CTX_get(ctx);\n    y = BN_CTX_get(ctx);\n    if (y == NULL)\n        goto end;\n    if (ret == NULL)\n        ret = BN_new();\n    if (ret == NULL)\n        goto end;\n    if (!BN_nnmod(A, a, p, ctx))\n        goto end;\n    e = 1;\n    while (!BN_is_bit_set(p, e))\n        e++;\n    if (e == 1) {\n        if (!BN_rshift(q, p, 2))\n            goto end;\n        q->neg = 0;\n        if (!BN_add_word(q, 1))\n            goto end;\n        if (!BN_mod_exp(ret, A, q, p, ctx))\n            goto end;\n        err = 0;\n        goto vrfy;\n    }\n    if (e == 2) {\n        if (!BN_mod_lshift1_quick(t, A, p))\n            goto end;\n        if (!BN_rshift(q, p, 3))\n            goto end;\n        q->neg = 0;\n        if (!BN_mod_exp(b, t, q, p, ctx))\n            goto end;\n        if (!BN_mod_sqr(y, b, p, ctx))\n            goto end;\n        if (!BN_mod_mul(t, t, y, p, ctx))\n            goto end;\n        if (!BN_sub_word(t, 1))\n            goto end;\n        if (!BN_mod_mul(x, A, b, p, ctx))\n            goto end;\n        if (!BN_mod_mul(x, x, t, p, ctx))\n            goto end;\n        if (!BN_copy(ret, x))\n            goto end;\n        err = 0;\n        goto vrfy;\n    }\n    if (!BN_copy(q, p))\n        goto end;\n    q->neg = 0;\n    i = 2;\n    do {\n        if (i < 22) {\n            if (!BN_set_word(y, i))\n                goto end;\n        } else {\n            if (!BN_priv_rand(y, BN_num_bits(p), 0, 0))\n                goto end;\n            if (BN_ucmp(y, p) >= 0) {\n                if (!(p->neg ? BN_add : BN_sub) (y, y, p))\n                    goto end;\n            }\n            if (BN_is_zero(y))\n                if (!BN_set_word(y, i))\n                    goto end;\n        }\n        r = BN_kronecker(y, q, ctx);\n        if (r < -1)\n            goto end;\n        if (r == 0) {\n            BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);\n            goto end;\n        }\n    }\n    while (r == 1 && ++i < 82);\n    if (r != -1) {\n        BNerr(BN_F_BN_MOD_SQRT, BN_R_TOO_MANY_ITERATIONS);\n        goto end;\n    }\n    if (!BN_rshift(q, q, e))\n        goto end;\n    if (!BN_mod_exp(y, y, q, p, ctx))\n        goto end;\n    if (BN_is_one(y)) {\n        BNerr(BN_F_BN_MOD_SQRT, BN_R_P_IS_NOT_PRIME);\n        goto end;\n    }\n    if (!BN_rshift1(t, q))\n        goto end;\n    if (BN_is_zero(t)) {\n        if (!BN_nnmod(t, A, p, ctx))\n            goto end;\n        if (BN_is_zero(t)) {\n            BN_zero(ret);\n            err = 0;\n            goto end;\n        } else if (!BN_one(x))\n            goto end;\n    } else {\n        if (!BN_mod_exp(x, A, t, p, ctx))\n            goto end;\n        if (BN_is_zero(x)) {\n            BN_zero(ret);\n            err = 0;\n            goto end;\n        }\n    }\n    if (!BN_mod_sqr(b, x, p, ctx))\n        goto end;\n    if (!BN_mod_mul(b, b, A, p, ctx))\n        goto end;\n    if (!BN_mod_mul(x, x, A, p, ctx))\n        goto end;\n    while (1) {\n        if (BN_is_one(b)) {\n            if (!BN_copy(ret, x))\n                goto end;\n            err = 0;\n            goto vrfy;\n        }\n        i = 1;\n        if (!BN_mod_sqr(t, b, p, ctx))\n            goto end;\n        while (!BN_is_one(t)) {\n            i++;\n            if (i == e) {\n                BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);\n                goto end;\n            }\n            if (!BN_mod_mul(t, t, t, p, ctx))\n                goto end;\n        }\n        if (!BN_copy(t, y))\n            goto end;\n        for (j = e - i - 1; j > 0; j--) {\n            if (!BN_mod_sqr(t, t, p, ctx))\n                goto end;\n        }\n        if (!BN_mod_mul(y, t, t, p, ctx))\n            goto end;\n        if (!BN_mod_mul(x, x, t, p, ctx))\n            goto end;\n        if (!BN_mod_mul(b, b, y, p, ctx))\n            goto end;\n        e = i;\n    }\n vrfy:\n    if (!err) {\n        if (!BN_mod_sqr(x, ret, p, ctx))\n            err = 1;\n        if (!err && 0 != BN_cmp(x, A)) {\n            BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);\n            err = 1;\n        }\n    }\n end:\n    if (err) {\n        if (ret != in)\n            BN_clear_free(ret);\n        ret = NULL;\n    }\n    BN_CTX_end(ctx);\n    bn_check_top(ret);\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    a->flags &= ~BN_FLG_FIXED_TOP;\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_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,\n               BN_CTX *ctx)\n{\n    int ret;\n    bn_check_top(a);\n    bn_check_top(p);\n    bn_check_top(m);\n#define MONT_MUL_MOD\n#define MONT_EXP_WORD\n#define RECP_MUL_MOD\n#ifdef MONT_MUL_MOD\n    if (BN_is_odd(m)) {\n# ifdef MONT_EXP_WORD\n        if (a->top == 1 && !a->neg\n            && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)\n            && (BN_get_flags(a, BN_FLG_CONSTTIME) == 0)\n            && (BN_get_flags(m, BN_FLG_CONSTTIME) == 0)) {\n            BN_ULONG A = a->d[0];\n            ret = BN_mod_exp_mont_word(r, A, p, m, ctx, NULL);\n        } else\n# endif\n            ret = BN_mod_exp_mont(r, a, p, m, ctx, NULL);\n    } else\n#endif\n#ifdef RECP_MUL_MOD\n    {\n        ret = BN_mod_exp_recp(r, a, p, m, ctx);\n    }\n#else\n    {\n        ret = BN_mod_exp_simple(r, a, p, m, ctx);\n    }\n#endif\n    bn_check_top(r);\n    return ret;\n}', 'int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,\n                    const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)\n{\n    int i, j, bits, ret = 0, wstart, wend, window, wvalue;\n    int start = 1;\n    BIGNUM *d, *r;\n    const BIGNUM *aa;\n    BIGNUM *val[TABLE_SIZE];\n    BN_MONT_CTX *mont = NULL;\n    if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0\n            || BN_get_flags(a, BN_FLG_CONSTTIME) != 0\n            || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {\n        return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont);\n    }\n    bn_check_top(a);\n    bn_check_top(p);\n    bn_check_top(m);\n    if (!BN_is_odd(m)) {\n        BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS);\n        return 0;\n    }\n    bits = BN_num_bits(p);\n    if (bits == 0) {\n        if (BN_abs_is_word(m, 1)) {\n            ret = 1;\n            BN_zero(rr);\n        } else {\n            ret = BN_one(rr);\n        }\n        return ret;\n    }\n    BN_CTX_start(ctx);\n    d = BN_CTX_get(ctx);\n    r = BN_CTX_get(ctx);\n    val[0] = BN_CTX_get(ctx);\n    if (val[0] == NULL)\n        goto err;\n    if (in_mont != NULL)\n        mont = in_mont;\n    else {\n        if ((mont = BN_MONT_CTX_new()) == NULL)\n            goto err;\n        if (!BN_MONT_CTX_set(mont, m, ctx))\n            goto err;\n    }\n    if (a->neg || BN_ucmp(a, m) >= 0) {\n        if (!BN_nnmod(val[0], a, m, ctx))\n            goto err;\n        aa = val[0];\n    } else\n        aa = a;\n    if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx))\n        goto err;\n    window = BN_window_bits_for_exponent_size(bits);\n    if (window > 1) {\n        if (!bn_mul_mont_fixed_top(d, val[0], val[0], mont, ctx))\n            goto err;\n        j = 1 << (window - 1);\n        for (i = 1; i < j; i++) {\n            if (((val[i] = BN_CTX_get(ctx)) == NULL) ||\n                !bn_mul_mont_fixed_top(val[i], val[i - 1], d, mont, ctx))\n                goto err;\n        }\n    }\n    start = 1;\n    wvalue = 0;\n    wstart = bits - 1;\n    wend = 0;\n#if 1\n    j = m->top;\n    if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {\n        if (bn_wexpand(r, j) == NULL)\n            goto err;\n        r->d[0] = (0 - m->d[0]) & BN_MASK2;\n        for (i = 1; i < j; i++)\n            r->d[i] = (~m->d[i]) & BN_MASK2;\n        r->top = j;\n        r->flags |= BN_FLG_FIXED_TOP;\n    } else\n#endif\n    if (!bn_to_mont_fixed_top(r, BN_value_one(), mont, ctx))\n        goto err;\n    for (;;) {\n        if (BN_is_bit_set(p, wstart) == 0) {\n            if (!start) {\n                if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))\n                    goto err;\n            }\n            if (wstart == 0)\n                break;\n            wstart--;\n            continue;\n        }\n        j = wstart;\n        wvalue = 1;\n        wend = 0;\n        for (i = 1; i < window; i++) {\n            if (wstart - i < 0)\n                break;\n            if (BN_is_bit_set(p, wstart - i)) {\n                wvalue <<= (i - wend);\n                wvalue |= 1;\n                wend = i;\n            }\n        }\n        j = wend + 1;\n        if (!start)\n            for (i = 0; i < j; i++) {\n                if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))\n                    goto err;\n            }\n        if (!bn_mul_mont_fixed_top(r, r, val[wvalue >> 1], mont, ctx))\n            goto err;\n        wstart -= wend + 1;\n        wvalue = 0;\n        start = 0;\n        if (wstart < 0)\n            break;\n    }\n#if defined(SPARC_T4_MONT)\n    if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) {\n        j = mont->N.top;\n        val[0]->d[0] = 1;\n        for (i = 1; i < j; i++)\n            val[0]->d[i] = 0;\n        val[0]->top = j;\n        if (!BN_mod_mul_montgomery(rr, r, val[0], mont, ctx))\n            goto err;\n    } else\n#endif\n    if (!BN_from_montgomery(rr, r, mont, ctx))\n        goto err;\n    ret = 1;\n err:\n    if (in_mont == NULL)\n        BN_MONT_CTX_free(mont);\n    BN_CTX_end(ctx);\n    bn_check_top(rr);\n    return ret;\n}', 'int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,\n                         BN_CTX *ctx)\n{\n    return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx);\n}', 'int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,\n                          BN_MONT_CTX *mont, BN_CTX *ctx)\n{\n    BIGNUM *tmp;\n    int ret = 0;\n    int num = mont->N.top;\n#if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)\n    if (num > 1 && a->top == num && b->top == num) {\n        if (bn_wexpand(r, num) == NULL)\n            return 0;\n        if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {\n            r->neg = a->neg ^ b->neg;\n            r->top = num;\n            r->flags |= BN_FLG_FIXED_TOP;\n            return 1;\n        }\n    }\n#endif\n    if ((a->top + b->top) > 2 * num)\n        return 0;\n    BN_CTX_start(ctx);\n    tmp = BN_CTX_get(ctx);\n    if (tmp == NULL)\n        goto err;\n    bn_check_top(tmp);\n    if (a == b) {\n        if (!bn_sqr_fixed_top(tmp, a, ctx))\n            goto err;\n    } else {\n        if (!bn_mul_fixed_top(tmp, a, b, ctx))\n            goto err;\n    }\n#ifdef MONT_WORD\n    if (!bn_from_montgomery_word(r, tmp, mont))\n        goto err;\n#else\n    if (!BN_from_montgomery(r, tmp, mont, ctx))\n        goto err;\n#endif\n    ret = 1;\n err:\n    BN_CTX_end(ctx);\n    return ret;\n}', 'int bn_mul_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)\n{\n    int ret = 0;\n    int top, al, bl;\n    BIGNUM *rr;\n#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)\n    int i;\n#endif\n#ifdef BN_RECURSION\n    BIGNUM *t = NULL;\n    int j = 0, k;\n#endif\n    bn_check_top(a);\n    bn_check_top(b);\n    bn_check_top(r);\n    al = a->top;\n    bl = b->top;\n    if ((al == 0) || (bl == 0)) {\n        BN_zero(r);\n        return 1;\n    }\n    top = al + bl;\n    BN_CTX_start(ctx);\n    if ((r == a) || (r == b)) {\n        if ((rr = BN_CTX_get(ctx)) == NULL)\n            goto err;\n    } else\n        rr = r;\n#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)\n    i = al - bl;\n#endif\n#ifdef BN_MUL_COMBA\n    if (i == 0) {\n# if 0\n        if (al == 4) {\n            if (bn_wexpand(rr, 8) == NULL)\n                goto err;\n            rr->top = 8;\n            bn_mul_comba4(rr->d, a->d, b->d);\n            goto end;\n        }\n# endif\n        if (al == 8) {\n            if (bn_wexpand(rr, 16) == NULL)\n                goto err;\n            rr->top = 16;\n            bn_mul_comba8(rr->d, a->d, b->d);\n            goto end;\n        }\n    }\n#endif\n#ifdef BN_RECURSION\n    if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {\n        if (i >= -1 && i <= 1) {\n            if (i >= 0) {\n                j = BN_num_bits_word((BN_ULONG)al);\n            }\n            if (i == -1) {\n                j = BN_num_bits_word((BN_ULONG)bl);\n            }\n            j = 1 << (j - 1);\n            assert(j <= al || j <= bl);\n            k = j + j;\n            t = BN_CTX_get(ctx);\n            if (t == NULL)\n                goto err;\n            if (al > j || bl > j) {\n                if (bn_wexpand(t, k * 4) == NULL)\n                    goto err;\n                if (bn_wexpand(rr, k * 4) == NULL)\n                    goto err;\n                bn_mul_part_recursive(rr->d, a->d, b->d,\n                                      j, al - j, bl - j, t->d);\n            } else {\n                if (bn_wexpand(t, k * 2) == NULL)\n                    goto err;\n                if (bn_wexpand(rr, k * 2) == NULL)\n                    goto err;\n                bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d);\n            }\n            rr->top = top;\n            goto end;\n        }\n    }\n#endif\n    if (bn_wexpand(rr, top) == NULL)\n        goto err;\n    rr->top = top;\n    bn_mul_normal(rr->d, a->d, al, b->d, bl);\n#if defined(BN_MUL_COMBA) || defined(BN_RECURSION)\n end:\n#endif\n    rr->neg = a->neg ^ b->neg;\n    rr->flags |= BN_FLG_FIXED_TOP;\n    if (r != rr && BN_copy(r, rr) == NULL)\n        goto err;\n    ret = 1;\n err:\n    bn_check_top(r);\n    BN_CTX_end(ctx);\n    return ret;\n}', 'void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n,\n                           int tna, int tnb, BN_ULONG *t)\n{\n    int i, j, n2 = n * 2;\n    int c1, c2, neg;\n    BN_ULONG ln, lo, *p;\n    if (n < 8) {\n        bn_mul_normal(r, a, n + tna, b, n + tnb);\n        return;\n    }\n    c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);\n    c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);\n    neg = 0;\n    switch (c1 * 3 + c2) {\n    case -4:\n        bn_sub_part_words(t, &(a[n]), a, tna, tna - n);\n        bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb);\n        break;\n    case -3:\n    case -2:\n        bn_sub_part_words(t, &(a[n]), a, tna, tna - n);\n        bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);\n        neg = 1;\n        break;\n    case -1:\n    case 0:\n    case 1:\n    case 2:\n        bn_sub_part_words(t, a, &(a[n]), tna, n - tna);\n        bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb);\n        neg = 1;\n        break;\n    case 3:\n    case 4:\n        bn_sub_part_words(t, a, &(a[n]), tna, n - tna);\n        bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n);\n        break;\n    }\n# if 0\n    if (n == 4) {\n        bn_mul_comba4(&(t[n2]), t, &(t[n]));\n        bn_mul_comba4(r, a, b);\n        bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);\n        memset(&r[n2 + tn * 2], 0, sizeof(*r) * (n2 - tn * 2));\n    } else\n# endif\n    if (n == 8) {\n        bn_mul_comba8(&(t[n2]), t, &(t[n]));\n        bn_mul_comba8(r, a, b);\n        bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);\n        memset(&r[n2 + tna + tnb], 0, sizeof(*r) * (n2 - tna - tnb));\n    } else {\n        p = &(t[n2 * 2]);\n        bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);\n        bn_mul_recursive(r, a, b, n, 0, 0, p);\n        i = n / 2;\n        if (tna > tnb)\n            j = tna - i;\n        else\n            j = tnb - i;\n        if (j == 0) {\n            bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),\n                             i, tna - i, tnb - i, p);\n            memset(&r[n2 + i * 2], 0, sizeof(*r) * (n2 - i * 2));\n        } else if (j > 0) {\n            bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),\n                                  i, tna - i, tnb - i, p);\n            memset(&(r[n2 + tna + tnb]), 0,\n                   sizeof(BN_ULONG) * (n2 - tna - tnb));\n        } else {\n            memset(&r[n2], 0, sizeof(*r) * n2);\n            if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL\n                && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {\n                bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);\n            } else {\n                for (;;) {\n                    i /= 2;\n                    if (i < tna || i < tnb) {\n                        bn_mul_part_recursive(&(r[n2]),\n                                              &(a[n]), &(b[n]),\n                                              i, tna - i, tnb - i, p);\n                        break;\n                    } else if (i == tna || i == tnb) {\n                        bn_mul_recursive(&(r[n2]),\n                                         &(a[n]), &(b[n]),\n                                         i, tna - i, tnb - i, p);\n                        break;\n                    }\n                }\n            }\n        }\n    }\n    c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));\n    if (neg) {\n        c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));\n    } else {\n        c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));\n    }\n    c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));\n    if (c1) {\n        p = &(r[n + n2]);\n        lo = *p;\n        ln = (lo + c1) & BN_MASK2;\n        *p = ln;\n        if (ln < (BN_ULONG)c1) {\n            do {\n                p++;\n                lo = *p;\n                ln = (lo + 1) & BN_MASK2;\n                *p = ln;\n            } while (ln == 0);\n        }\n    }\n}', 'int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)\n{\n    int n, i;\n    n = cl - 1;\n    if (dl < 0) {\n        for (i = dl; i < 0; i++) {\n            if (b[n - i] != 0)\n                return -1;\n        }\n    }\n    if (dl > 0) {\n        for (i = dl; i > 0; i--) {\n            if (a[n + i] != 0)\n                return 1;\n        }\n    }\n    return bn_cmp_words(a, b, cl);\n}', 'int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)\n{\n    int i;\n    BN_ULONG aa, bb;\n    aa = a[n - 1];\n    bb = b[n - 1];\n    if (aa != bb)\n        return ((aa > bb) ? 1 : -1);\n    for (i = n - 2; i >= 0; i--) {\n        aa = a[i];\n        bb = b[i];\n        if (aa != bb)\n            return ((aa > bb) ? 1 : -1);\n    }\n    return 0;\n}']