static int build_chain(X509_STORE_CTX *ctx)
{
    SSL_DANE *dane = ctx->dane;
    int num = sk_X509_num(ctx->chain);
    X509 *cert = sk_X509_value(ctx->chain, num - 1);
    int ss = cert_self_signed(cert);
    STACK_OF(X509) *sktmp = NULL;
    unsigned int search;
    int may_trusted = 0;
    int may_alternate = 0;
    int trust = X509_TRUST_UNTRUSTED;
    int alt_untrusted = 0;
    int depth;
    int ok = 0;
    int i;
    OPENSSL_assert(num == 1 && ctx->num_untrusted == num);
#define S_DOUNTRUSTED      (1 << 0)
#define S_DOTRUSTED        (1 << 1)
#define S_DOALTERNATE      (1 << 2)
    search = (ctx->untrusted != NULL) ? S_DOUNTRUSTED : 0;
    if (DANETLS_HAS_PKIX(dane) || !DANETLS_HAS_DANE(dane)) {
        if (search == 0 || ctx->param->flags & X509_V_FLAG_TRUSTED_FIRST)
            search |= S_DOTRUSTED;
        else if (!(ctx->param->flags & X509_V_FLAG_NO_ALT_CHAINS))
            may_alternate = 1;
        may_trusted = 1;
    }
    if (ctx->untrusted && (sktmp = sk_X509_dup(ctx->untrusted)) == NULL) {
        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
        ctx->error = X509_V_ERR_OUT_OF_MEM;
        return 0;
    }
    if (DANETLS_ENABLED(dane) && dane->certs != NULL) {
        if (sktmp == NULL && (sktmp = sk_X509_new_null()) == NULL) {
            X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
            ctx->error = X509_V_ERR_OUT_OF_MEM;
            return 0;
        }
        for (i = 0; i < sk_X509_num(dane->certs); ++i) {
            if (!sk_X509_push(sktmp, sk_X509_value(dane->certs, i))) {
                sk_X509_free(sktmp);
                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                ctx->error = X509_V_ERR_OUT_OF_MEM;
                return 0;
            }
        }
    }
    if (ctx->param->depth > INT_MAX/2)
        ctx->param->depth = INT_MAX/2;
    depth = ctx->param->depth + 1;
    while (search != 0) {
        X509 *x;
        X509 *xtmp = NULL;
        if ((search & S_DOTRUSTED) != 0) {
            i = num = sk_X509_num(ctx->chain);
            if ((search & S_DOALTERNATE) != 0) {
                i = alt_untrusted;
            }
            x = sk_X509_value(ctx->chain, i-1);
            ok = (depth < num) ? 0 : get_issuer(&xtmp, ctx, x);
            if (ok < 0) {
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_STORE_LOOKUP;
                search = 0;
                continue;
            }
            if (ok > 0) {
                if ((search & S_DOALTERNATE) != 0) {
                    OPENSSL_assert(num > i && i > 0 && ss == 0);
                    search &= ~S_DOALTERNATE;
                    for (; num > i; --num)
                        X509_free(sk_X509_pop(ctx->chain));
                    ctx->num_untrusted = num;
                    if (DANETLS_ENABLED(dane) &&
                        dane->mdpth >= ctx->num_untrusted) {
                        dane->mdpth = -1;
                        X509_free(dane->mcert);
                        dane->mcert = NULL;
                    }
                    if (DANETLS_ENABLED(dane) &&
                        dane->pdpth >= ctx->num_untrusted)
                        dane->pdpth = -1;
                }
                if (ss == 0) {
                    if (!sk_X509_push(ctx->chain, x = xtmp)) {
                        X509_free(xtmp);
                        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                        trust = X509_TRUST_REJECTED;
                        ctx->error = X509_V_ERR_OUT_OF_MEM;
                        search = 0;
                        continue;
                    }
                    ss = cert_self_signed(x);
                } else if (num == ctx->num_untrusted) {
                    if (X509_cmp(x, xtmp) != 0) {
                        X509_free(xtmp);
                        ok = 0;
                    } else {
                        X509_free(x);
                        ctx->num_untrusted = --num;
                        (void) sk_X509_set(ctx->chain, num, x = xtmp);
                    }
                }
                if (ok) {
                    OPENSSL_assert(ctx->num_untrusted <= num);
                    search &= ~S_DOUNTRUSTED;
                    switch (trust = check_trust(ctx, num)) {
                    case X509_TRUST_TRUSTED:
                    case X509_TRUST_REJECTED:
                        search = 0;
                        continue;
                    }
                    if (ss == 0)
                        continue;
                }
            }
            if ((search & S_DOUNTRUSTED) == 0) {
                if ((search & S_DOALTERNATE) != 0 && --alt_untrusted > 0)
                    continue;
                if (!may_alternate || (search & S_DOALTERNATE) != 0 ||
                    ctx->num_untrusted < 2)
                    break;
                search |= S_DOALTERNATE;
                alt_untrusted = ctx->num_untrusted - 1;
                ss = 0;
            }
        }
        if ((search & S_DOUNTRUSTED) != 0) {
            num = sk_X509_num(ctx->chain);
            OPENSSL_assert(num == ctx->num_untrusted);
            x = sk_X509_value(ctx->chain, num-1);
            xtmp = (ss || depth < num) ? NULL : find_issuer(ctx, sktmp, x);
            if (xtmp == NULL) {
                search &= ~S_DOUNTRUSTED;
                if (may_trusted)
                    search |= S_DOTRUSTED;
                continue;
            }
            (void) sk_X509_delete_ptr(sktmp, xtmp);
            if (!sk_X509_push(ctx->chain, xtmp)) {
                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_OUT_OF_MEM;
                search = 0;
                continue;
            }
            X509_up_ref(x = xtmp);
            ++ctx->num_untrusted;
            ss = cert_self_signed(xtmp);
            switch (trust = check_dane_issuer(ctx, ctx->num_untrusted - 1)) {
            case X509_TRUST_TRUSTED:
            case X509_TRUST_REJECTED:
                search = 0;
                continue;
            }
        }
    }
    sk_X509_free(sktmp);
    num = sk_X509_num(ctx->chain);
    if (num <= depth) {
        if (trust == X509_TRUST_UNTRUSTED && DANETLS_HAS_DANE_TA(dane))
            trust = check_dane_pkeys(ctx);
        if (trust == X509_TRUST_UNTRUSTED && num == ctx->num_untrusted)
            trust = check_trust(ctx, num);
    }
    switch (trust) {
    case X509_TRUST_TRUSTED:
        return 1;
    case X509_TRUST_REJECTED:
        return 0;
    case X509_TRUST_UNTRUSTED:
    default:
        num = sk_X509_num(ctx->chain);
        if (num > depth)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_CERT_CHAIN_TOO_LONG);
        if (DANETLS_ENABLED(dane) &&
            (!DANETLS_HAS_PKIX(dane) || dane->pdpth >= 0))
            return verify_cb_cert(ctx, NULL, num-1, X509_V_ERR_DANE_NO_MATCH);
        if (ss && sk_X509_num(ctx->chain) == 1)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT);
        if (ss)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN);
        if (ctx->num_untrusted < num)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT);
        return verify_cb_cert(ctx, NULL, num-1,
                              X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY);
    }
}
['static int build_chain(X509_STORE_CTX *ctx)\n{\n    SSL_DANE *dane = ctx->dane;\n    int num = sk_X509_num(ctx->chain);\n    X509 *cert = sk_X509_value(ctx->chain, num - 1);\n    int ss = cert_self_signed(cert);\n    STACK_OF(X509) *sktmp = NULL;\n    unsigned int search;\n    int may_trusted = 0;\n    int may_alternate = 0;\n    int trust = X509_TRUST_UNTRUSTED;\n    int alt_untrusted = 0;\n    int depth;\n    int ok = 0;\n    int i;\n    OPENSSL_assert(num == 1 && ctx->num_untrusted == num);\n#define S_DOUNTRUSTED      (1 << 0)\n#define S_DOTRUSTED        (1 << 1)\n#define S_DOALTERNATE      (1 << 2)\n    search = (ctx->untrusted != NULL) ? S_DOUNTRUSTED : 0;\n    if (DANETLS_HAS_PKIX(dane) || !DANETLS_HAS_DANE(dane)) {\n        if (search == 0 || ctx->param->flags & X509_V_FLAG_TRUSTED_FIRST)\n            search |= S_DOTRUSTED;\n        else if (!(ctx->param->flags & X509_V_FLAG_NO_ALT_CHAINS))\n            may_alternate = 1;\n        may_trusted = 1;\n    }\n    if (ctx->untrusted && (sktmp = sk_X509_dup(ctx->untrusted)) == NULL) {\n        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);\n        ctx->error = X509_V_ERR_OUT_OF_MEM;\n        return 0;\n    }\n    if (DANETLS_ENABLED(dane) && dane->certs != NULL) {\n        if (sktmp == NULL && (sktmp = sk_X509_new_null()) == NULL) {\n            X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);\n            ctx->error = X509_V_ERR_OUT_OF_MEM;\n            return 0;\n        }\n        for (i = 0; i < sk_X509_num(dane->certs); ++i) {\n            if (!sk_X509_push(sktmp, sk_X509_value(dane->certs, i))) {\n                sk_X509_free(sktmp);\n                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);\n                ctx->error = X509_V_ERR_OUT_OF_MEM;\n                return 0;\n            }\n        }\n    }\n    if (ctx->param->depth > INT_MAX/2)\n        ctx->param->depth = INT_MAX/2;\n    depth = ctx->param->depth + 1;\n    while (search != 0) {\n        X509 *x;\n        X509 *xtmp = NULL;\n        if ((search & S_DOTRUSTED) != 0) {\n            i = num = sk_X509_num(ctx->chain);\n            if ((search & S_DOALTERNATE) != 0) {\n                i = alt_untrusted;\n            }\n            x = sk_X509_value(ctx->chain, i-1);\n            ok = (depth < num) ? 0 : get_issuer(&xtmp, ctx, x);\n            if (ok < 0) {\n                trust = X509_TRUST_REJECTED;\n                ctx->error = X509_V_ERR_STORE_LOOKUP;\n                search = 0;\n                continue;\n            }\n            if (ok > 0) {\n                if ((search & S_DOALTERNATE) != 0) {\n                    OPENSSL_assert(num > i && i > 0 && ss == 0);\n                    search &= ~S_DOALTERNATE;\n                    for (; num > i; --num)\n                        X509_free(sk_X509_pop(ctx->chain));\n                    ctx->num_untrusted = num;\n                    if (DANETLS_ENABLED(dane) &&\n                        dane->mdpth >= ctx->num_untrusted) {\n                        dane->mdpth = -1;\n                        X509_free(dane->mcert);\n                        dane->mcert = NULL;\n                    }\n                    if (DANETLS_ENABLED(dane) &&\n                        dane->pdpth >= ctx->num_untrusted)\n                        dane->pdpth = -1;\n                }\n                if (ss == 0) {\n                    if (!sk_X509_push(ctx->chain, x = xtmp)) {\n                        X509_free(xtmp);\n                        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);\n                        trust = X509_TRUST_REJECTED;\n                        ctx->error = X509_V_ERR_OUT_OF_MEM;\n                        search = 0;\n                        continue;\n                    }\n                    ss = cert_self_signed(x);\n                } else if (num == ctx->num_untrusted) {\n                    if (X509_cmp(x, xtmp) != 0) {\n                        X509_free(xtmp);\n                        ok = 0;\n                    } else {\n                        X509_free(x);\n                        ctx->num_untrusted = --num;\n                        (void) sk_X509_set(ctx->chain, num, x = xtmp);\n                    }\n                }\n                if (ok) {\n                    OPENSSL_assert(ctx->num_untrusted <= num);\n                    search &= ~S_DOUNTRUSTED;\n                    switch (trust = check_trust(ctx, num)) {\n                    case X509_TRUST_TRUSTED:\n                    case X509_TRUST_REJECTED:\n                        search = 0;\n                        continue;\n                    }\n                    if (ss == 0)\n                        continue;\n                }\n            }\n            if ((search & S_DOUNTRUSTED) == 0) {\n                if ((search & S_DOALTERNATE) != 0 && --alt_untrusted > 0)\n                    continue;\n                if (!may_alternate || (search & S_DOALTERNATE) != 0 ||\n                    ctx->num_untrusted < 2)\n                    break;\n                search |= S_DOALTERNATE;\n                alt_untrusted = ctx->num_untrusted - 1;\n                ss = 0;\n            }\n        }\n        if ((search & S_DOUNTRUSTED) != 0) {\n            num = sk_X509_num(ctx->chain);\n            OPENSSL_assert(num == ctx->num_untrusted);\n            x = sk_X509_value(ctx->chain, num-1);\n            xtmp = (ss || depth < num) ? NULL : find_issuer(ctx, sktmp, x);\n            if (xtmp == NULL) {\n                search &= ~S_DOUNTRUSTED;\n                if (may_trusted)\n                    search |= S_DOTRUSTED;\n                continue;\n            }\n            (void) sk_X509_delete_ptr(sktmp, xtmp);\n            if (!sk_X509_push(ctx->chain, xtmp)) {\n                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);\n                trust = X509_TRUST_REJECTED;\n                ctx->error = X509_V_ERR_OUT_OF_MEM;\n                search = 0;\n                continue;\n            }\n            X509_up_ref(x = xtmp);\n            ++ctx->num_untrusted;\n            ss = cert_self_signed(xtmp);\n            switch (trust = check_dane_issuer(ctx, ctx->num_untrusted - 1)) {\n            case X509_TRUST_TRUSTED:\n            case X509_TRUST_REJECTED:\n                search = 0;\n                continue;\n            }\n        }\n    }\n    sk_X509_free(sktmp);\n    num = sk_X509_num(ctx->chain);\n    if (num <= depth) {\n        if (trust == X509_TRUST_UNTRUSTED && DANETLS_HAS_DANE_TA(dane))\n            trust = check_dane_pkeys(ctx);\n        if (trust == X509_TRUST_UNTRUSTED && num == ctx->num_untrusted)\n            trust = check_trust(ctx, num);\n    }\n    switch (trust) {\n    case X509_TRUST_TRUSTED:\n        return 1;\n    case X509_TRUST_REJECTED:\n        return 0;\n    case X509_TRUST_UNTRUSTED:\n    default:\n        num = sk_X509_num(ctx->chain);\n        if (num > depth)\n            return verify_cb_cert(ctx, NULL, num-1,\n                                  X509_V_ERR_CERT_CHAIN_TOO_LONG);\n        if (DANETLS_ENABLED(dane) &&\n            (!DANETLS_HAS_PKIX(dane) || dane->pdpth >= 0))\n            return verify_cb_cert(ctx, NULL, num-1, X509_V_ERR_DANE_NO_MATCH);\n        if (ss && sk_X509_num(ctx->chain) == 1)\n            return verify_cb_cert(ctx, NULL, num-1,\n                                  X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT);\n        if (ss)\n            return verify_cb_cert(ctx, NULL, num-1,\n                                  X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN);\n        if (ctx->num_untrusted < num)\n            return verify_cb_cert(ctx, NULL, num-1,\n                                  X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT);\n        return verify_cb_cert(ctx, NULL, num-1,\n                              X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY);\n    }\n}', 'DEFINE_STACK_OF(X509)', 'int OPENSSL_sk_num(const OPENSSL_STACK *st)\n{\n    if (st == NULL)\n        return -1;\n    return st->num;\n}', 'void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)\n{\n    if (st == NULL || i < 0 || i >= st->num)\n        return NULL;\n    return st->data[i];\n}', 'static int cert_self_signed(X509 *x)\n{\n    X509_check_purpose(x, -1, 0);\n    if (x->ex_flags & EXFLAG_SS)\n        return 1;\n    else\n        return 0;\n}', 'int X509_check_purpose(X509 *x, int id, int ca)\n{\n    int idx;\n    const X509_PURPOSE *pt;\n    if (!(x->ex_flags & EXFLAG_SET)) {\n        CRYPTO_THREAD_write_lock(x->lock);\n        x509v3_cache_extensions(x);\n        CRYPTO_THREAD_unlock(x->lock);\n    }\n    if (id == -1)\n        return 1;\n    idx = X509_PURPOSE_get_by_id(id);\n    if (idx == -1)\n        return -1;\n    pt = X509_PURPOSE_get0(idx);\n    return pt->check_purpose(pt, x, ca);\n}']