crypto/rsa/rsa_x931g.c:169: error: BUFFER_OVERRUN_L3
  Offset: [8, +oo] (⇐ [8, +oo] + [0, +oo]) Size: [0, 8388607] by call to `BN_X931_generate_prime_ex`.
Showing all 36 steps of the trace


crypto/rsa/rsa_x931g.c:155:10: Call
153.   
154.       BN_CTX_start(ctx);
155.       Xp = BN_CTX_get(ctx);
                ^
156.       Xq = BN_CTX_get(ctx);
157.       if (Xq == NULL)

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:387:1: Parameter `*a->d`
    385.   }
    386.   
    387. > int BN_set_word(BIGNUM *a, BN_ULONG w)
    388.   {
    389.       bn_check_top(a);

crypto/bn/bn_lib.c:390:9: Call
    388.   {
    389.       bn_check_top(a);
    390.       if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
                   ^
    391.           return (0);
    392.       a->neg = 0;

crypto/bn/bn_lcl.h:651:1: Parameter `*a->d`
      649.                            const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
      650.   
      651. > static ossl_inline BIGNUM *bn_expand(BIGNUM *a, int bits)
      652.   {
      653.       if (bits > (INT_MAX - BN_BITS2 + 1))

crypto/rsa/rsa_x931g.c:159:10: Call
157.       if (Xq == NULL)
158.           goto error;
159.       if (!BN_X931_generate_Xpq(Xp, Xq, bits, ctx))
                ^
160.           goto error;
161.   

crypto/bn/bn_x931p.c:160:1: Parameter `*Xp->d`
  158.    */
  159.   
  160. > int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx)
  161.   {
  162.       BIGNUM *t;

crypto/bn/bn_x931p.c:176:10: Call
  174.        * exceeded.
  175.        */
  176.       if (!BN_priv_rand(Xp, nbits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY))
                  ^
  177.           goto err;
  178.   

crypto/bn/bn_rand.c:107:1: Parameter `*rnd->d`
    105.   }
    106.   
    107. > int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom)
    108.   {
    109.       return bnrand(PRIVATE, rnd, bits, top, bottom);

crypto/bn/bn_rand.c:109:12: Call
    107.   int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom)
    108.   {
    109.       return bnrand(PRIVATE, rnd, bits, top, bottom);
                      ^
    110.   }
    111.   

crypto/bn/bn_rand.c:21:1: Parameter `*rnd->d`
      19.   } BNRAND_FLAG;
      20.   
      21. > static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom)
      22.   {
      23.       unsigned char *buf = NULL;

crypto/bn/bn_rand.c:84:10: Call
      82.       if (bottom)                 /* set bottom bit if requested */
      83.           buf[bytes - 1] |= 1;
      84.       if (!BN_bin2bn(buf, bytes, rnd))
                     ^
      85.           goto err;
      86.       ret = 1;

crypto/bn/bn_lib.c:399:1: Parameter `*ret->d`
        397.   }
        398.   
        399. > BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
        400.   {
        401.       unsigned int i, m;

crypto/bn/bn_lib.c:421:9: Call
        419.       i = ((n - 1) / BN_BYTES) + 1;
        420.       m = ((n - 1) % (BN_BYTES));
        421.       if (bn_wexpand(ret, (int)i) == NULL) {
                       ^
        422.           BN_free(bn);
        423.           return NULL;

crypto/bn/bn_lib.c:940:1: Parameter `*a->d`
          938.   }
          939.   
          940. > BIGNUM *bn_wexpand(BIGNUM *a, int words)
          941.   {
          942.       return (words <= a->dmax) ? a : bn_expand2(a, words);

crypto/rsa/rsa_x931g.c:169:10: Call
167.       /* Generate two primes from Xp, Xq */
168.   
169.       if (!BN_X931_generate_prime_ex(rsa->p, NULL, NULL, NULL, NULL, Xp,
                ^
170.                                      e, ctx, cb))
171.           goto error;

crypto/bn/bn_x931p.c:213:1: Parameter `*p->d`
  211.    */
  212.   
  213. > int BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
  214.                                 BIGNUM *Xp1, BIGNUM *Xp2,
  215.                                 const BIGNUM *Xp,

crypto/bn/bn_x931p.c:232:10: Call
  230.       if (!BN_priv_rand(Xp2, 101, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
  231.           goto error;
  232.       if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb))
                  ^
  233.           goto error;
  234.   

crypto/bn/bn_x931p.c:51:1: Parameter `*p->d`
    49.    */
    50.   
    51. > int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
    52.                               const BIGNUM *Xp, const BIGNUM *Xp1,
    53.                               const BIGNUM *Xp2, const BIGNUM *e, BN_CTX *ctx,

crypto/bn/bn_x931p.c:91:10: Call
    89.       /* First set p to value of Rp */
    90.   
    91.       if (!BN_mod_inverse(p, p2, p1, ctx))
                   ^
    92.           goto err;
    93.   

crypto/bn/bn_gcd.c:124:1: Parameter `*in->d`
      122.                                           BN_CTX *ctx);
      123.   
      124. > BIGNUM *BN_mod_inverse(BIGNUM *in,
      125.                          const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
      126.   {

crypto/bn/bn_gcd.c:129:10: Call
      127.       BIGNUM *rv;
      128.       int noinv;
      129.       rv = int_bn_mod_inverse(in, a, n, ctx, &noinv);
                      ^
      130.       if (noinv)
      131.           BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);

crypto/bn/bn_gcd.c:135:1: Parameter `*in->d`
        133.   }
        134.   
        135. > BIGNUM *int_bn_mod_inverse(BIGNUM *in,
        136.                              const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
        137.                              int *pnoinv)

crypto/bn/bn_x931p.c:94:10: Call
    92.           goto err;
    93.   
    94.       if (!BN_mul(p, p, p2, ctx))
                   ^
    95.           goto err;
    96.   

crypto/bn/bn_mul.c:497:1: Parameter `*a->d`
      495.   #endif                          /* BN_RECURSION */
      496.   
      497. > int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
      498.   {
      499.       int ret = 0;

crypto/bn/bn_mul.c:577:17: Call
      575.                   if (bn_wexpand(rr, k * 4) == NULL)
      576.                       goto err;
      577.                   bn_mul_part_recursive(rr->d, a->d, b->d,
                             ^
      578.                                         j, al - j, bl - j, t->d);
      579.               } 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:727:1: Parameter `cl`
          725.    */
          726.   
          727. > int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
          728.   {
          729.       int n, i;

crypto/bn/bn_lib.c:744:12: Call
          742.           }
          743.       }
          744.       return bn_cmp_words(a, b, cl);
                            ^
          745.   }
          746.   

crypto/bn/bn_lib.c:700:1: <Offset trace>
698.   }
699.   
700. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
701.   {
702.       int i;

crypto/bn/bn_lib.c:700:1: Parameter `n`
            698.   }
            699.   
            700. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
            701.   {
            702.       int i;

crypto/bn/bn_lib.c:709:10: Assignment
            707.       if (aa != bb)
            708.           return ((aa > bb) ? 1 : -1);
            709.       for (i = n - 2; i >= 0; i--) {
                            ^
            710.           aa = a[i];
            711.           bb = b[i];

crypto/bn/bn_lib.c:700:1: <Length trace>
698.   }
699.   
700. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
701.   {
702.       int i;

crypto/bn/bn_lib.c:700:1: Parameter `*b`
            698.   }
            699.   
            700. > int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
            701.   {
            702.       int i;

crypto/bn/bn_lib.c:711:14: Array access: Offset: [8, +oo] (⇐ [8, +oo] + [0, +oo]) Size: [0, 8388607] by call to `BN_X931_generate_prime_ex` 
            709.       for (i = n - 2; i >= 0; i--) {
            710.           aa = a[i];
            711.           bb = b[i];
                                ^
            712.           if (aa != bb)
            713.               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);
}
['int RSA_X931_generate_key_ex(RSA *rsa, int bits, const BIGNUM *e,\n                             BN_GENCB *cb)\n{\n    int ok = 0;\n    BIGNUM *Xp = NULL, *Xq = NULL;\n    BN_CTX *ctx = NULL;\n    ctx = BN_CTX_new();\n    if (ctx == NULL)\n        goto error;\n    BN_CTX_start(ctx);\n    Xp = BN_CTX_get(ctx);\n    Xq = BN_CTX_get(ctx);\n    if (Xq == NULL)\n        goto error;\n    if (!BN_X931_generate_Xpq(Xp, Xq, bits, ctx))\n        goto error;\n    rsa->p = BN_new();\n    rsa->q = BN_new();\n    if (rsa->p == NULL || rsa->q == NULL)\n        goto error;\n    if (!BN_X931_generate_prime_ex(rsa->p, NULL, NULL, NULL, NULL, Xp,\n                                   e, ctx, cb))\n        goto error;\n    if (!BN_X931_generate_prime_ex(rsa->q, NULL, NULL, NULL, NULL, Xq,\n                                   e, ctx, cb))\n        goto error;\n    if (!RSA_X931_derive_ex(rsa, NULL, NULL, NULL, NULL,\n                            NULL, NULL, NULL, NULL, NULL, NULL, e, cb))\n        goto error;\n    ok = 1;\n error:\n    if (ctx)\n        BN_CTX_end(ctx);\n    BN_CTX_free(ctx);\n    if (ok)\n        return 1;\n    return 0;\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_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx)\n{\n    BIGNUM *t;\n    int i;\n    if ((nbits < 1024) || (nbits & 0xff))\n        return 0;\n    nbits >>= 1;\n    if (!BN_priv_rand(Xp, nbits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY))\n        goto err;\n    BN_CTX_start(ctx);\n    t = BN_CTX_get(ctx);\n    if (t == NULL)\n        goto err;\n    for (i = 0; i < 1000; i++) {\n        if (!BN_priv_rand(Xq, nbits, BN_RAND_TOP_TWO, BN_RAND_BOTTOM_ANY))\n            goto err;\n        BN_sub(t, Xp, Xq);\n        if (BN_num_bits(t) > (nbits - 100))\n            break;\n    }\n    BN_CTX_end(ctx);\n    if (i < 1000)\n        return 1;\n    return 0;\n err:\n    BN_CTX_end(ctx);\n    return 0;\n}', 'int BN_priv_rand(BIGNUM *rnd, int bits, int top, int bottom)\n{\n    return bnrand(PRIVATE, rnd, bits, top, bottom);\n}', 'static int bnrand(BNRAND_FLAG flag, BIGNUM *rnd, int bits, int top, int bottom)\n{\n    unsigned char *buf = NULL;\n    int b, ret = 0, bit, bytes, mask;\n    if (bits == 0) {\n        if (top != BN_RAND_TOP_ANY || bottom != BN_RAND_BOTTOM_ANY)\n            goto toosmall;\n        BN_zero(rnd);\n        return 1;\n    }\n    if (bits < 0 || (bits == 1 && top > 0))\n        goto toosmall;\n    bytes = (bits + 7) / 8;\n    bit = (bits - 1) % 8;\n    mask = 0xff << (bit + 1);\n    buf = OPENSSL_malloc(bytes);\n    if (buf == NULL) {\n        BNerr(BN_F_BNRAND, ERR_R_MALLOC_FAILURE);\n        goto err;\n    }\n    b = flag == NORMAL ? RAND_bytes(buf, bytes) : RAND_priv_bytes(buf, bytes);\n    if (b <= 0)\n        goto err;\n    if (flag == TESTING) {\n        int i;\n        unsigned char c;\n        for (i = 0; i < bytes; i++) {\n            if (RAND_bytes(&c, 1) <= 0)\n                goto err;\n            if (c >= 128 && i > 0)\n                buf[i] = buf[i - 1];\n            else if (c < 42)\n                buf[i] = 0;\n            else if (c < 84)\n                buf[i] = 255;\n        }\n    }\n    if (top >= 0) {\n        if (top) {\n            if (bit == 0) {\n                buf[0] = 1;\n                buf[1] |= 0x80;\n            } else {\n                buf[0] |= (3 << (bit - 1));\n            }\n        } else {\n            buf[0] |= (1 << bit);\n        }\n    }\n    buf[0] &= ~mask;\n    if (bottom)\n        buf[bytes - 1] |= 1;\n    if (!BN_bin2bn(buf, bytes, rnd))\n        goto err;\n    ret = 1;\n err:\n    OPENSSL_clear_free(buf, bytes);\n    bn_check_top(rnd);\n    return (ret);\ntoosmall:\n    BNerr(BN_F_BNRAND, BN_R_BITS_TOO_SMALL);\n    return 0;\n}', 'BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)\n{\n    unsigned int i, m;\n    unsigned int n;\n    BN_ULONG l;\n    BIGNUM *bn = NULL;\n    if (ret == NULL)\n        ret = bn = BN_new();\n    if (ret == NULL)\n        return (NULL);\n    bn_check_top(ret);\n    for ( ; len > 0 && *s == 0; s++, len--)\n        continue;\n    n = len;\n    if (n == 0) {\n        ret->top = 0;\n        return (ret);\n    }\n    i = ((n - 1) / BN_BYTES) + 1;\n    m = ((n - 1) % (BN_BYTES));\n    if (bn_wexpand(ret, (int)i) == NULL) {\n        BN_free(bn);\n        return NULL;\n    }\n    ret->top = i;\n    ret->neg = 0;\n    l = 0;\n    while (n--) {\n        l = (l << 8L) | *(s++);\n        if (m-- == 0) {\n            ret->d[--i] = l;\n            l = 0;\n            m = BN_BYTES - 1;\n        }\n    }\n    bn_correct_top(ret);\n    return (ret);\n}', 'BIGNUM *bn_wexpand(BIGNUM *a, int words)\n{\n    return (words <= a->dmax) ? a : bn_expand2(a, words);\n}', 'int BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,\n                              BIGNUM *Xp1, BIGNUM *Xp2,\n                              const BIGNUM *Xp,\n                              const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)\n{\n    int ret = 0;\n    BN_CTX_start(ctx);\n    if (Xp1 == NULL)\n        Xp1 = BN_CTX_get(ctx);\n    if (Xp2 == NULL)\n        Xp2 = BN_CTX_get(ctx);\n    if (Xp1 == NULL || Xp2 == NULL)\n        goto error;\n    if (!BN_priv_rand(Xp1, 101, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))\n        goto error;\n    if (!BN_priv_rand(Xp2, 101, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))\n        goto error;\n    if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb))\n        goto error;\n    ret = 1;\n error:\n    BN_CTX_end(ctx);\n    return ret;\n}', 'int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,\n                            const BIGNUM *Xp, const BIGNUM *Xp1,\n                            const BIGNUM *Xp2, const BIGNUM *e, BN_CTX *ctx,\n                            BN_GENCB *cb)\n{\n    int ret = 0;\n    BIGNUM *t, *p1p2, *pm1;\n    if (!BN_is_odd(e))\n        return 0;\n    BN_CTX_start(ctx);\n    if (p1 == NULL)\n        p1 = BN_CTX_get(ctx);\n    if (p2 == NULL)\n        p2 = BN_CTX_get(ctx);\n    t = BN_CTX_get(ctx);\n    p1p2 = BN_CTX_get(ctx);\n    pm1 = BN_CTX_get(ctx);\n    if (pm1 == NULL)\n        goto err;\n    if (!bn_x931_derive_pi(p1, Xp1, ctx, cb))\n        goto err;\n    if (!bn_x931_derive_pi(p2, Xp2, ctx, cb))\n        goto err;\n    if (!BN_mul(p1p2, p1, p2, ctx))\n        goto err;\n    if (!BN_mod_inverse(p, p2, p1, ctx))\n        goto err;\n    if (!BN_mul(p, p, p2, ctx))\n        goto err;\n    if (!BN_mod_inverse(t, p1, p2, ctx))\n        goto err;\n    if (!BN_mul(t, t, p1, ctx))\n        goto err;\n    if (!BN_sub(p, p, t))\n        goto err;\n    if (p->neg && !BN_add(p, p, p1p2))\n        goto err;\n    if (!BN_mod_sub(p, p, Xp, p1p2, ctx))\n        goto err;\n    if (!BN_add(p, p, Xp))\n        goto err;\n    for (;;) {\n        int i = 1;\n        BN_GENCB_call(cb, 0, i++);\n        if (!BN_copy(pm1, p))\n            goto err;\n        if (!BN_sub_word(pm1, 1))\n            goto err;\n        if (!BN_gcd(t, pm1, e, ctx))\n            goto err;\n        if (BN_is_one(t)) {\n            int r = BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb);\n            if (r < 0)\n                goto err;\n            if (r)\n                break;\n        }\n        if (!BN_add(p, p, p1p2))\n            goto err;\n    }\n    BN_GENCB_call(cb, 3, 0);\n    ret = 1;\n err:\n    BN_CTX_end(ctx);\n    return ret;\n}', 'BIGNUM *BN_mod_inverse(BIGNUM *in,\n                       const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)\n{\n    BIGNUM *rv;\n    int noinv;\n    rv = int_bn_mod_inverse(in, a, n, ctx, &noinv);\n    if (noinv)\n        BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);\n    return rv;\n}', 'BIGNUM *int_bn_mod_inverse(BIGNUM *in,\n                           const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,\n                           int *pnoinv)\n{\n    BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;\n    BIGNUM *ret = NULL;\n    int sign;\n    if (pnoinv)\n        *pnoinv = 0;\n    if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0)\n        || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {\n        return BN_mod_inverse_no_branch(in, a, n, ctx);\n    }\n    bn_check_top(a);\n    bn_check_top(n);\n    BN_CTX_start(ctx);\n    A = BN_CTX_get(ctx);\n    B = BN_CTX_get(ctx);\n    X = BN_CTX_get(ctx);\n    D = BN_CTX_get(ctx);\n    M = BN_CTX_get(ctx);\n    Y = BN_CTX_get(ctx);\n    T = BN_CTX_get(ctx);\n    if (T == NULL)\n        goto err;\n    if (in == NULL)\n        R = BN_new();\n    else\n        R = in;\n    if (R == NULL)\n        goto err;\n    BN_one(X);\n    BN_zero(Y);\n    if (BN_copy(B, a) == NULL)\n        goto err;\n    if (BN_copy(A, n) == NULL)\n        goto err;\n    A->neg = 0;\n    if (B->neg || (BN_ucmp(B, A) >= 0)) {\n        if (!BN_nnmod(B, B, A, ctx))\n            goto err;\n    }\n    sign = -1;\n    if (BN_is_odd(n) && (BN_num_bits(n) <= 2048)) {\n        int shift;\n        while (!BN_is_zero(B)) {\n            shift = 0;\n            while (!BN_is_bit_set(B, shift)) {\n                shift++;\n                if (BN_is_odd(X)) {\n                    if (!BN_uadd(X, X, n))\n                        goto err;\n                }\n                if (!BN_rshift1(X, X))\n                    goto err;\n            }\n            if (shift > 0) {\n                if (!BN_rshift(B, B, shift))\n                    goto err;\n            }\n            shift = 0;\n            while (!BN_is_bit_set(A, shift)) {\n                shift++;\n                if (BN_is_odd(Y)) {\n                    if (!BN_uadd(Y, Y, n))\n                        goto err;\n                }\n                if (!BN_rshift1(Y, Y))\n                    goto err;\n            }\n            if (shift > 0) {\n                if (!BN_rshift(A, A, shift))\n                    goto err;\n            }\n            if (BN_ucmp(B, A) >= 0) {\n                if (!BN_uadd(X, X, Y))\n                    goto err;\n                if (!BN_usub(B, B, A))\n                    goto err;\n            } else {\n                if (!BN_uadd(Y, Y, X))\n                    goto err;\n                if (!BN_usub(A, A, B))\n                    goto err;\n            }\n        }\n    } else {\n        while (!BN_is_zero(B)) {\n            BIGNUM *tmp;\n            if (BN_num_bits(A) == BN_num_bits(B)) {\n                if (!BN_one(D))\n                    goto err;\n                if (!BN_sub(M, A, B))\n                    goto err;\n            } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {\n                if (!BN_lshift1(T, B))\n                    goto err;\n                if (BN_ucmp(A, T) < 0) {\n                    if (!BN_one(D))\n                        goto err;\n                    if (!BN_sub(M, A, B))\n                        goto err;\n                } else {\n                    if (!BN_sub(M, A, T))\n                        goto err;\n                    if (!BN_add(D, T, B))\n                        goto err;\n                    if (BN_ucmp(A, D) < 0) {\n                        if (!BN_set_word(D, 2))\n                            goto err;\n                    } else {\n                        if (!BN_set_word(D, 3))\n                            goto err;\n                        if (!BN_sub(M, M, B))\n                            goto err;\n                    }\n                }\n            } else {\n                if (!BN_div(D, M, A, B, ctx))\n                    goto err;\n            }\n            tmp = A;\n            A = B;\n            B = M;\n            if (BN_is_one(D)) {\n                if (!BN_add(tmp, X, Y))\n                    goto err;\n            } else {\n                if (BN_is_word(D, 2)) {\n                    if (!BN_lshift1(tmp, X))\n                        goto err;\n                } else if (BN_is_word(D, 4)) {\n                    if (!BN_lshift(tmp, X, 2))\n                        goto err;\n                } else if (D->top == 1) {\n                    if (!BN_copy(tmp, X))\n                        goto err;\n                    if (!BN_mul_word(tmp, D->d[0]))\n                        goto err;\n                } else {\n                    if (!BN_mul(tmp, D, X, ctx))\n                        goto err;\n                }\n                if (!BN_add(tmp, tmp, Y))\n                    goto err;\n            }\n            M = Y;\n            Y = X;\n            X = tmp;\n            sign = -sign;\n        }\n    }\n    if (sign < 0) {\n        if (!BN_sub(Y, n, Y))\n            goto err;\n    }\n    if (BN_is_one(A)) {\n        if (!Y->neg && BN_ucmp(Y, n) < 0) {\n            if (!BN_copy(R, Y))\n                goto err;\n        } else {\n            if (!BN_nnmod(R, Y, n, ctx))\n                goto err;\n        }\n    } else {\n        if (pnoinv)\n            *pnoinv = 1;\n        goto err;\n    }\n    ret = R;\n err:\n    if ((ret == NULL) && (in == NULL))\n        BN_free(R);\n    BN_CTX_end(ctx);\n    bn_check_top(ret);\n    return (ret);\n}', 'int BN_mul(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    bn_correct_top(rr);\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}']