package org.bouncycastle.asn1.x509;

import java.io.IOException;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import org.bouncycastle.asn1.ASN1Encodable;
import org.bouncycastle.asn1.ASN1IA5String;
import org.bouncycastle.asn1.ASN1OctetString;
import org.bouncycastle.asn1.ASN1PrintableString;
import org.bouncycastle.asn1.ASN1Sequence;
import org.bouncycastle.asn1.ASN1String;
import org.bouncycastle.asn1.x500.AttributeTypeAndValue;
import org.bouncycastle.asn1.x500.RDN;
import org.bouncycastle.asn1.x500.X500Name;
import org.bouncycastle.asn1.x500.style.IETFUtils;
import org.bouncycastle.asn1.x500.style.RFC4519Style;
import org.bouncycastle.util.Arrays;
import org.bouncycastle.util.Integers;
import org.bouncycastle.util.Properties;
import org.bouncycastle.util.Strings;
import org.bouncycastle.util.encoders.Hex;

public class PKIXNameConstraintValidator
    implements NameConstraintValidator
{
    private Set excludedSubtreesDN = new HashSet();

    private Set excludedSubtreesDNS = new HashSet();

    private Set excludedSubtreesEmail = new HashSet();

    private Set excludedSubtreesURI = new HashSet();

    private Set excludedSubtreesIP = new HashSet();

    private Set excludedSubtreesOtherName = new HashSet();

    private Set permittedSubtreesDN;

    private Set permittedSubtreesDNS;

    private Set permittedSubtreesEmail;

    private Set permittedSubtreesURI;

    private Set permittedSubtreesIP;

    private Set permittedSubtreesOtherName;

    public PKIXNameConstraintValidator()
    {
    }

    /**
     * Checks if the given GeneralName is in the permitted set.
     *
     * @param name The GeneralName
     * @throws NameConstraintValidatorException If the  name</code>
     */
    public void checkPermitted(GeneralName name)
        throws NameConstraintValidatorException
    {
        ASN1Encodable nameValue = name.getName();

        switch (name.getTagNo())
        {
        case GeneralName.otherName:
            checkPermittedOtherName(permittedSubtreesOtherName, OtherName.getInstance(nameValue));
            break;
        case GeneralName.rfc822Name:
            checkPermittedEmail(extractNameAsString(nameValue));
            break;
        case GeneralName.dNSName:
            checkPermittedDNS(permittedSubtreesDNS, extractNameAsString(nameValue));
            break;
        case GeneralName.directoryName:
            checkPermittedDN(X500Name.getInstance(nameValue));
            break;
        case GeneralName.uniformResourceIdentifier:
            checkPermittedURI(permittedSubtreesURI, extractNameAsString(nameValue));
            break;
        case GeneralName.iPAddress:
            checkPermittedIP(permittedSubtreesIP, ASN1OctetString.getInstance(nameValue).getOctets());
            break;
        default:
            // other tags to be ignored.
        }
    }

    /**
     * Check if the given GeneralName is contained in the excluded set.
     *
     * @param name The GeneralName.
     * @throws NameConstraintValidatorException If the  name</code> is
     * excluded.
     */
    public void checkExcluded(GeneralName name)
        throws NameConstraintValidatorException
    {
        ASN1Encodable nameValue = name.getName();

        switch (name.getTagNo())
        {
        case GeneralName.otherName:
            checkExcludedOtherName(excludedSubtreesOtherName, OtherName.getInstance(nameValue));
            break;
        case GeneralName.rfc822Name:
            checkExcludedEmail(extractNameAsString(nameValue));
            break;
        case GeneralName.dNSName:
            checkExcludedDNS(excludedSubtreesDNS, extractNameAsString(nameValue));
            break;
        case GeneralName.directoryName:
            checkExcludedDN(X500Name.getInstance(nameValue));
            break;
        case GeneralName.uniformResourceIdentifier:
            checkExcludedURI(excludedSubtreesURI, extractNameAsString(nameValue));
            break;
        case GeneralName.iPAddress:
            checkExcludedIP(excludedSubtreesIP, ASN1OctetString.getInstance(nameValue).getOctets());
            break;
        default:
            // other tags to be ignored.
        }
    }

    public void intersectPermittedSubtree(GeneralSubtree permitted)
    {
        intersectPermittedSubtree(new GeneralSubtree[]{permitted});
    }

    /**
     * Updates the permitted set of these name constraints with the intersection
     * with the given subtree.
     *
     * @param permitted The permitted subtrees
     */
    public void intersectPermittedSubtree(GeneralSubtree[] permitted)
    {
        Map subtreesMap = new HashMap();

        // group in sets in a map ordered by tag no.
        for (int i = 0; i != permitted.length; i++)
        {
            GeneralSubtree subtree = permitted[i];
            Integer tagNo = Integers.valueOf(subtree.getBase().getTagNo());

            Set subtrees = (Set)subtreesMap.get(tagNo);
            if (subtrees == null)
            {
                subtrees = new HashSet();
                subtreesMap.put(tagNo, subtrees);
            }

            subtrees.add(subtree);
        }

        for (Iterator it = subtreesMap.entrySet().iterator(); it.hasNext();)
        {
            Map.Entry entry = (Map.Entry)it.next();

            // go through all subtree groups
            int nameType = ((Integer)entry.getKey()).intValue();
            Set subtrees = (Set)entry.getValue();

            switch (nameType)
            {
            case GeneralName.otherName:
                permittedSubtreesOtherName = intersectOtherName(permittedSubtreesOtherName, subtrees);
                break;
            case GeneralName.rfc822Name:
                permittedSubtreesEmail = intersectEmail(permittedSubtreesEmail, subtrees);
                break;
            case GeneralName.dNSName:
                permittedSubtreesDNS = intersectDNS(permittedSubtreesDNS, subtrees);
                break;
            case GeneralName.directoryName:
                permittedSubtreesDN = intersectDN(permittedSubtreesDN, subtrees);
                break;
            case GeneralName.uniformResourceIdentifier:
                permittedSubtreesURI = intersectURI(permittedSubtreesURI, subtrees);
                break;
            case GeneralName.iPAddress:
                permittedSubtreesIP = intersectIP(permittedSubtreesIP, subtrees);
                break;
            default:
                throw new IllegalStateException("Unknown tag encountered: " + nameType);
            }
        }
    }

    public void intersectEmptyPermittedSubtree(int nameType)
    {
        switch (nameType)
        {
        case GeneralName.otherName:
            permittedSubtreesOtherName = new HashSet();
            break;
        case GeneralName.rfc822Name:
            permittedSubtreesEmail = new HashSet();
            break;
        case GeneralName.dNSName:
            permittedSubtreesDNS = new HashSet();
            break;
        case GeneralName.directoryName:
            permittedSubtreesDN = new HashSet();
            break;
        case GeneralName.uniformResourceIdentifier:
            permittedSubtreesURI = new HashSet();
            break;
        case GeneralName.iPAddress:
            permittedSubtreesIP = new HashSet();
            break;
        default:
            throw new IllegalStateException("Unknown tag encountered: " + nameType);
        }
    }

    /**
     * Adds a subtree to the excluded set of these name constraints.
     *
     * @param subtree A subtree with an excluded GeneralName.
     */
    public void addExcludedSubtree(GeneralSubtree subtree)
    {
        GeneralName subtreeBase = subtree.getBase();
        ASN1Encodable nameValue = subtreeBase.getName();

        switch (subtreeBase.getTagNo())
        {
        case GeneralName.otherName:
            excludedSubtreesOtherName = unionOtherName(excludedSubtreesOtherName, OtherName.getInstance(nameValue));
            break;
        case GeneralName.rfc822Name:
            excludedSubtreesEmail = unionEmail(excludedSubtreesEmail, extractNameAsString(nameValue));
            break;
        case GeneralName.dNSName:
            excludedSubtreesDNS = unionDNS(excludedSubtreesDNS, extractNameAsString(nameValue));
            break;
        case GeneralName.directoryName:
            excludedSubtreesDN = unionDN(excludedSubtreesDN, ASN1Sequence.getInstance(nameValue));
            break;
        case GeneralName.uniformResourceIdentifier:
            excludedSubtreesURI = unionURI(excludedSubtreesURI, extractNameAsString(nameValue));
            break;
        case GeneralName.iPAddress:
            excludedSubtreesIP = unionIP(excludedSubtreesIP, ASN1OctetString.getInstance(nameValue).getOctets());
            break;
        default:
            throw new IllegalStateException("Unknown tag encountered: " + subtreeBase.getTagNo());
        }
    }

    public int hashCode()
    {
        return hashCollection(excludedSubtreesDN)
            + hashCollection(excludedSubtreesDNS)
            + hashCollection(excludedSubtreesEmail)
            + hashCollection(excludedSubtreesIP)
            + hashCollection(excludedSubtreesURI)
            + hashCollection(excludedSubtreesOtherName)
            + hashCollection(permittedSubtreesDN)
            + hashCollection(permittedSubtreesDNS)
            + hashCollection(permittedSubtreesEmail)
            + hashCollection(permittedSubtreesIP)
            + hashCollection(permittedSubtreesURI)
            + hashCollection(permittedSubtreesOtherName);
    }

    public boolean equals(Object o)
    {
        if (!(o instanceof PKIXNameConstraintValidator))
        {
            return false;
        }
        PKIXNameConstraintValidator constraintValidator = (PKIXNameConstraintValidator)o;
        return collectionsAreEqual(constraintValidator.excludedSubtreesDN, excludedSubtreesDN)
            && collectionsAreEqual(constraintValidator.excludedSubtreesDNS, excludedSubtreesDNS)
            && collectionsAreEqual(constraintValidator.excludedSubtreesEmail, excludedSubtreesEmail)
            && collectionsAreEqual(constraintValidator.excludedSubtreesIP, excludedSubtreesIP)
            && collectionsAreEqual(constraintValidator.excludedSubtreesURI, excludedSubtreesURI)
            && collectionsAreEqual(constraintValidator.excludedSubtreesOtherName, excludedSubtreesOtherName)
            && collectionsAreEqual(constraintValidator.permittedSubtreesDN, permittedSubtreesDN)
            && collectionsAreEqual(constraintValidator.permittedSubtreesDNS, permittedSubtreesDNS)
            && collectionsAreEqual(constraintValidator.permittedSubtreesEmail, permittedSubtreesEmail)
            && collectionsAreEqual(constraintValidator.permittedSubtreesIP, permittedSubtreesIP)
            && collectionsAreEqual(constraintValidator.permittedSubtreesURI, permittedSubtreesURI)
            && collectionsAreEqual(constraintValidator.permittedSubtreesOtherName, permittedSubtreesOtherName);
    }

    public void checkPermittedDN(X500Name dns)
        throws NameConstraintValidatorException
    {
        checkPermittedDN(permittedSubtreesDN, ASN1Sequence.getInstance(dns));
    }

    public void checkExcludedDN(X500Name dns)
        throws NameConstraintValidatorException
    {
        checkExcludedDN(excludedSubtreesDN, ASN1Sequence.getInstance(dns));
    }

    public void checkPermittedEmail(String email)
        throws NameConstraintValidatorException
    {
        checkPermittedEmail(permittedSubtreesEmail, email);
    }

    public void checkExcludedEmail(String email)
        throws NameConstraintValidatorException
    {
        checkExcludedEmail(excludedSubtreesEmail, email);
    }

    private static boolean withinDNSubtree(ASN1Sequence dns, ASN1Sequence subtree)
    {
        // An empty subtree would be a prefix of every DN; treat it as "no match" instead, so an empty permitted
        // base can't nullify the permittedSubtrees restriction.
        if (subtree.size() < 1)
        {
            return false;
        }

        // A prefix can't be longer than the DN.
        if (subtree.size() > dns.size())
        {
            return false;
        }

        // Relaxed anywhere-match needed for GSMA SGP.22, gated behind a property.
        if (Properties.isOverrideSet(Properties.X509_SGP22_NAME_CONSTRAINTS))
        {
            return withinDNSubtreeSGP22(dns, subtree);
        }

        // RFC 5280 4.2.1.10 / 7.1: a directoryName constraint is satisfied only when the constraint's RDNSequence
        // is an initial prefix of the subject's. Match from index 0 only - searching for the constraint's first RDN
        // at an arbitrary offset let an attacker prepend RDNs ahead of the permitted sequence (e.g. a subject
        // C=FR,O=Attacker,C=US,O=TrustedOrg,CN=x being judged inside permitted subtree C=US,O=TrustedOrg) and still
        // pass the permittedSubtrees check.

        for (int j = 0; j < subtree.size(); j++)
        {
            // both subtree and dns are a ASN.1 Name and the elements are a RDN
            RDN subtreeRdn = RDN.getInstance(subtree.getObjectAt(j));
            RDN dnsRdn = RDN.getInstance(dns.getObjectAt(j));

            // Obey RFC 5280 7.1. Two relative distinguished names RDN1 and RDN2 match if they have the same number
            // of naming attributes and for each naming attribute in RDN1 there is a matching naming attribute in
            // RDN2. NOTE: this is now different from the RFC 3280 version, where only binary comparison was used.
            if (!IETFUtils.rDNAreEqual(subtreeRdn, dnsRdn))
            {
                return false;
            }
        }

        return true;
    }

    /**
     * Relaxed directoryName subtree matching for GSMA SGP.22 v2.5 (sections 4.5.2.1.0.2 and
     * 4.5.2.1.0.3), enabled only when {@link Properties#X509_SGP22_NAME_CONSTRAINTS} is set. Each
     * RDN of the permitted subtree must be matched by some RDN of the subject DN regardless of
     * position; additional subject attributes are permitted, and a serialNumber RDN is matched with
     * a startsWith comparison wherever it occurs. This deliberately departs from the contiguous
     * prefix matching of RFC 5280 7.1 implemented by {@link #withinDNSubtree(ASN1Sequence, ASN1Sequence)}.
     */
    private static boolean withinDNSubtreeSGP22(ASN1Sequence dns, ASN1Sequence subtree)
    {
        int count = dns.size();
        RDN[] dnsRdns = new RDN[count];
        for (int i = 0; i < count; ++i)
        {
            dnsRdns[i] = RDN.getInstance(dns.getObjectAt(i));
        }

        for (int i = 0; i < subtree.size(); i++)
        {
            RDN subtreeRdn = RDN.getInstance(subtree.getObjectAt(i));

            if (!rdnMatchesSGP22Any(subtreeRdn, dnsRdns))
            {
                return false;
            }
        }

        return true;
    }

    private static boolean rdnMatchesSGP22Any(RDN subtreeRdn, RDN[] dnsRdns)
    {
        for (int i = 0; i < dnsRdns.length; ++i)
        {
            if (rdnMatchesSGP22(subtreeRdn, dnsRdns[i]))
            {
                return true;
            }
        }
        return false;
    }

    private static boolean rdnMatchesSGP22(RDN subtreeRdn, RDN dnsRdn)
    {
        if (subtreeRdn.size() != dnsRdn.size())
        {
            return false;
        }

        AttributeTypeAndValue subtreeFirst = subtreeRdn.getFirst();
        AttributeTypeAndValue dnsFirst = dnsRdn.getFirst();

        if (!subtreeFirst.getType().equals(dnsFirst.getType()))
        {
            return false;
        }

        // Special treatment of serialNumber for the GSMA SGP.22 RSP specification: the constraint's
        // IIN is a prefix (EID digits 1 to 8) of the subject's EID. The subject side is held to the
        // encoding SGP.22 explicitly mandates (the EID "as a decimal PrintableString"); the constraint
        // side accepts any ASN.1 string form - X.520 binds serialNumber to PrintableString there too,
        // but only by inheritance, and refusing a misencoded trust-side IIN would reject every leaf
        // under that EUM (the historical code read it type-agnostically via toString). Anything else
        // falls through to ordinary RDN equality below instead of throwing from an ASN.1 accessor.
        if (subtreeRdn.size() == 1 && subtreeFirst.getType().equals(RFC4519Style.serialNumber))
        {
            ASN1Encodable dnsFirstValue = dnsFirst.getValue();
            ASN1Encodable subtreeFirstValue = subtreeFirst.getValue();

            if (dnsFirstValue instanceof ASN1PrintableString && subtreeFirstValue instanceof ASN1String)
            {
                return ((ASN1PrintableString)dnsFirstValue).getString().startsWith(
                    ((ASN1String)subtreeFirstValue).getString());
            }
        }

        return IETFUtils.rDNAreEqual(subtreeRdn, dnsRdn);
    }

    private static void checkPermittedDN(Set permitted, ASN1Sequence dns)
        throws NameConstraintValidatorException
    {
        if (permitted != null
            && !(permitted.isEmpty() && dns.size() == 0)
            && !isDNConstrained(permitted, dns))
        {
            throw new NameConstraintValidatorException("Subject distinguished name is not from a permitted subtree");
        }
    }

    private static void checkExcludedDN(Set excluded, ASN1Sequence dns)
        throws NameConstraintValidatorException
    {
        if (isDNConstrained(excluded, dns))
        {
            throw new NameConstraintValidatorException("Subject distinguished name is from an excluded subtree");
        }
    }

    private static boolean isDNConstrained(Set constraints, ASN1Sequence dns)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            ASN1Sequence subtree = (ASN1Sequence)it.next();
            if (withinDNSubtree(dns, subtree))
            {
                return true;
            }
        }

        return false;
    }

    private static Set intersectDN(Set permitted, Set dns)
    {
        Set intersect = new HashSet();
        for (Iterator it = dns.iterator(); it.hasNext();)
        {
            GeneralSubtree subtree = (GeneralSubtree)it.next();
            ASN1Sequence dn1 = ASN1Sequence.getInstance(subtree.getBase().getName());
            if (permitted == null)
            {
                if (dn1 != null)
                {
                    intersect.add(dn1);
                }
            }
            else
            {
                Iterator _iter = permitted.iterator();
                while (_iter.hasNext())
                {
                    ASN1Sequence dn2 = (ASN1Sequence)_iter.next();

                    if (withinDNSubtree(dn1, dn2))
                    {
                        intersect.add(dn1);
                    }
                    else if (withinDNSubtree(dn2, dn1))
                    {
                        intersect.add(dn2);
                    }
                }
            }
        }
        return intersect;
    }

    private static Set unionDN(Set excluded, ASN1Sequence dn)
    {
        if (excluded.isEmpty())
        {
            if (dn != null)
            {
                excluded.add(dn);
            }
            return excluded;
        }
        else
        {
            Set intersect = new HashSet();

            Iterator it = excluded.iterator();
            while (it.hasNext())
            {
                ASN1Sequence subtree = ASN1Sequence.getInstance(it.next());

                if (withinDNSubtree(dn, subtree))
                {
                    intersect.add(subtree);
                }
                else if (withinDNSubtree(subtree, dn))
                {
                    intersect.add(dn);
                }
                else
                {
                    intersect.add(subtree);
                    intersect.add(dn);
                }
            }

            return intersect;
        }
    }

    private static Set intersectOtherName(Set permitted, Set otherNames)
    {
        Set intersect = new HashSet();
        for (Iterator it = otherNames.iterator(); it.hasNext();)
        {
            GeneralSubtree subtree = (GeneralSubtree)it.next();
            OtherName otherName1 = OtherName.getInstance(subtree.getBase().getName());
            if (otherName1 == null)
            {
                continue;
            }

            if (permitted == null)
            {
                intersect.add(otherName1);
            }
            else
            {
                Iterator it2 = permitted.iterator();
                while (it2.hasNext())
                {
                    OtherName otherName2 = OtherName.getInstance(it2.next());

                    intersectOtherName(otherName1, otherName2, intersect);
                }
            }
        }
        return intersect;
    }

    private static void intersectOtherName(OtherName otName1, OtherName otName2, Set intersect)
    {
        if (otName1.equals(otName2))
        {
            intersect.add(otName1);
        }
    }

    private static Set unionOtherName(Set permitted, OtherName otherName)
    {
        Set union = permitted != null ? new HashSet(permitted) : new HashSet();

        union.add(otherName);

        return union;
    }

    private static Set intersectEmail(Set permitted, Set emails)
    {
        Set intersect = new HashSet();
        for (Iterator it = emails.iterator(); it.hasNext();)
        {
            String email = extractNameAsString((GeneralSubtree)it.next());

            if (permitted == null)
            {
                intersect.add(email);
            }
            else
            {
                Iterator it2 = permitted.iterator();
                while (it2.hasNext())
                {
                    String _permitted = (String)it2.next();

                    intersectEmail(email, _permitted, intersect);
                }
            }
        }
        return intersect;
    }

    private static Set unionEmail(Set excluded, String email)
    {
        if (excluded.isEmpty())
        {
            excluded.add(email);
            return excluded;
        }

        Set union = new HashSet();

        Iterator it = excluded.iterator();
        while (it.hasNext())
        {
            String _excluded = (String)it.next();

            unionEmail(_excluded, email, union);
        }

        return union;
    }

    /**
     * Returns the intersection of the permitted IP ranges in  permitted</code> with
     *  ips</code>.
     *
     * @param permitted A  Set</code> of permitted IP addresses with their subnet mask as byte
     * arrays.
     * @param ips The IP address with its subnet mask.
     * @return The  Set</code> of permitted IP ranges intersected with  ips</code>.
     */
    private static Set intersectIP(Set permitted, Set ips)
    {
        Set intersect = new HashSet();
        for (Iterator it = ips.iterator(); it.hasNext();)
        {
            GeneralSubtree subtree = (GeneralSubtree)it.next();
            byte[] ip = ASN1OctetString.getInstance(subtree.getBase().getName()).getOctets();
            if (permitted == null)
            {
                intersect.add(ip);
            }
            else
            {
                Iterator it2 = permitted.iterator();
                while (it2.hasNext())
                {
                    byte[] _permitted = (byte[])it2.next();

                    byte[] intersection = intersectIPRange(_permitted, ip);
                    if (intersection != null)
                    {
                        intersect.add(intersection);
                    }
                }
            }
        }
        return intersect;
    }

    /**
     * Returns the union of the excluded IP ranges in  excluded</code>
     * with  ip</code>.
     *
     * @param excluded A  Set</code> of excluded IP addresses with their
     *                 subnet mask as byte arrays.
     * @param ip       The IP address with its subnet mask.
     * @return The  Set</code> of excluded IP ranges unified with
     *  ip</code> as byte arrays.
     */
    private static Set unionIP(Set excluded, byte[] ip)
    {
        if (excluded.isEmpty())
        {
            if (ip != null)
            {
                excluded.add(ip);
            }
            return excluded;
        }
        else
        {
            Set union = new HashSet();

            Iterator it = excluded.iterator();
            while (it.hasNext())
            {
                byte[] _excluded = (byte[])it.next();
                union.addAll(unionIPRange(_excluded, ip));
            }

            return union;
        }
    }

    /**
     * Calculates the union if two IP ranges.
     *
     * @param ipWithSubmask1 The first IP address with its subnet mask.
     * @param ipWithSubmask2 The second IP address with its subnet mask.
     * @return A  Set</code> with the union of both addresses.
     */
    private static Set unionIPRange(byte[] ipWithSubmask1, byte[] ipWithSubmask2)
    {
        Set set = new HashSet();

        // difficult, adding always all IPs is not wrong
        if (Arrays.areEqual(ipWithSubmask1, ipWithSubmask2))
        {
            set.add(ipWithSubmask1);
        }
        else
        {
            set.add(ipWithSubmask1);
            set.add(ipWithSubmask2);
        }
        return set;
    }

    /**
     * Calculates the intersection if two IP ranges.
     *
     * @param ipWithSubmask1 The first IP address with its subnet mask.
     * @param ipWithSubmask2 The second IP address with its subnet mask.
     * @return A single IP address with its subnet mask as a byte array, or null.
     */
    private static byte[] intersectIPRange(byte[] ipWithSubmask1, byte[] ipWithSubmask2)
    {
        // i.e. no intersection between IPv4 and IPv6 ranges
        if (ipWithSubmask1.length != ipWithSubmask2.length)
        {
            return null;
        }

        byte[][] temp = extractIPsAndSubnetMasks(ipWithSubmask1, ipWithSubmask2);
        byte ip1[] = temp[0];
        byte subnetmask1[] = temp[1];
        byte ip2[] = temp[2];
        byte subnetmask2[] = temp[3];

        byte minMax[][] = minMaxIPs(ip1, subnetmask1, ip2, subnetmask2);
        byte[] min1 = minMax[0];
        byte[] max1 = minMax[1];
        byte[] min2 = minMax[2];
        byte[] max2 = minMax[3];

        byte[] max = min(max1, max2);
        byte[] min = max(min1, min2);

        // minimum IP address can't be bigger than max
        if (compareTo(min, max) == 1)
        {
            return null;
        }

        // OR keeps all significant bits
        byte[] ip = or(min1, min2);
        byte[] subnetmask = or(subnetmask1, subnetmask2);
        return ipWithSubnetMask(ip, subnetmask);
    }

    /**
     * Concatenates the IP address with its subnet mask.
     *
     * @param ip         The IP address.
     * @param subnetMask Its subnet mask.
     * @return The concatenated IP address with its subnet mask.
     */
    private static byte[] ipWithSubnetMask(byte[] ip, byte[] subnetMask)
    {
        return Arrays.concatenate(ip, subnetMask);
    }

    /**
     * Splits the IP addresses and their subnet mask.
     *
     * @param ipWithSubmask1 The first IP address with the subnet mask.
     * @param ipWithSubmask2 The second IP address with the subnet mask.
     * @return An array with two elements. Each element contains the IP address
     * and the subnet mask in this order.
     */
    private static byte[][] extractIPsAndSubnetMasks(byte[] ipWithSubmask1, byte[] ipWithSubmask2)
    {
        int ipLength = ipWithSubmask1.length / 2;
        byte ip1[] = new byte[ipLength];
        byte subnetmask1[] = new byte[ipLength];
        System.arraycopy(ipWithSubmask1, 0, ip1, 0, ipLength);
        System.arraycopy(ipWithSubmask1, ipLength, subnetmask1, 0, ipLength);

        byte ip2[] = new byte[ipLength];
        byte subnetmask2[] = new byte[ipLength];
        System.arraycopy(ipWithSubmask2, 0, ip2, 0, ipLength);
        System.arraycopy(ipWithSubmask2, ipLength, subnetmask2, 0, ipLength);
        return new byte[][]{ ip1, subnetmask1, ip2, subnetmask2 };
    }

    /**
     * Based on the two IP addresses and their subnet masks the IP range is
     * computed for each IP address - subnet mask pair and returned as the
     * minimum IP address and the maximum address of the range.
     *
     * @param ip1         The first IP address.
     * @param subnetmask1 The subnet mask of the first IP address.
     * @param ip2         The second IP address.
     * @param subnetmask2 The subnet mask of the second IP address.
     * @return A array with two elements. The first/second element contains the
     * min and max IP address of the first/second IP address and its
     * subnet mask.
     */
    private static byte[][] minMaxIPs(byte[] ip1, byte[] subnetmask1, byte[] ip2, byte[] subnetmask2)
    {
        int ipLength = ip1.length;
        byte[] min1 = new byte[ipLength];
        byte[] max1 = new byte[ipLength];

        byte[] min2 = new byte[ipLength];
        byte[] max2 = new byte[ipLength];

        for (int i = 0; i < ipLength; i++)
        {
            min1[i] = (byte)(ip1[i] & subnetmask1[i]);
            max1[i] = (byte)(ip1[i] & subnetmask1[i] | ~subnetmask1[i]);

            min2[i] = (byte)(ip2[i] & subnetmask2[i]);
            max2[i] = (byte)(ip2[i] & subnetmask2[i] | ~subnetmask2[i]);
        }

        return new byte[][]{ min1, max1, min2, max2 };
    }

    private static void checkPermittedEmail(Set permitted, String email)
        throws NameConstraintValidatorException
    {
        if (permitted == null || (email.length() == 0 && permitted.size() == 0))
        {
            return;
        }

        checkEmailNotAmbiguous(email);

        if (!isEmailConstrained(permitted, email))
        {
            throw new NameConstraintValidatorException("Subject email address is not from a permitted subtree.");
        }
    }

    private static void checkExcludedEmail(Set excluded, String email)
        throws NameConstraintValidatorException
    {
        if (excluded.isEmpty())
        {
            return;
        }

        checkEmailNotAmbiguous(email);

        if (isEmailConstrained(excluded, email))
        {
            throw new NameConstraintValidatorException("Email address is from an excluded subtree.");
        }
    }

    /**
     * A tested rfc822Name must have exactly one '@': a quoted local part may legally contain '@'
     * (RFC 5321 sec. 4.1.2), so a value with more than one is ambiguous and could be split into the
     * wrong host, evading a constraint. Fail closed rather than guess. This applies to tested names
     * only; a constraint is matched by whole-string equality, so its '@' positions are immaterial.
     * Skipped when {@link Properties#X509_ALLOW_LENIENT_RFC822_NAME} opts back in to legacy parsing.
     */
    private static void checkEmailNotAmbiguous(String email)
        throws NameConstraintValidatorException
    {
        if (email.indexOf('@') != email.lastIndexOf('@')
            && !Properties.isOverrideSet(Properties.X509_ALLOW_LENIENT_RFC822_NAME))
        {
            throw new NameConstraintValidatorException("Subject email address is ambiguous (multiple '@').");
        }
    }

    private static void checkPermittedOtherName(Set permitted, OtherName otherName)
        throws NameConstraintValidatorException
    {
        if (permitted != null && !isOtherNameConstrained(permitted, otherName))
        {
            throw new NameConstraintValidatorException("Subject OtherName is not from a permitted subtree.");
        }
    }

    private static void checkExcludedOtherName(Set excluded, OtherName otherName)
        throws NameConstraintValidatorException
    {
        if (isOtherNameConstrained(excluded, otherName))
        {
            throw new NameConstraintValidatorException("OtherName is from an excluded subtree.");
        }
    }

    /**
     * Checks if the IP  ip</code> is included in the permitted set
     *  permitted</code>.
     *
     * @param permitted A  Set</code> of permitted IP addresses with
     *                  their subnet mask as byte arrays.
     * @param ip        The IP address.
     * @throws NameConstraintValidatorException if the IP is not permitted.
     */
    private static void checkPermittedIP(Set permitted, byte[] ip)
        throws NameConstraintValidatorException
    {
        if (permitted != null
            && !(ip.length == 0 && permitted.size() == 0)
            && !isIPConstrained(permitted, ip))
        {
            throw new NameConstraintValidatorException("IP is not from a permitted subtree.");
        }
    }

    /**
     * Checks if the IP  ip</code> is included in the excluded set
     *  excluded</code>.
     *
     * @param excluded A  Set</code> of excluded IP addresses with their
     *                 subnet mask as byte arrays.
     * @param ip       The IP address.
     * @throws NameConstraintValidatorException if the IP is excluded.
     */
    private static void checkExcludedIP(Set excluded, byte[] ip)
        throws NameConstraintValidatorException
    {
        if (isIPConstrained(excluded, ip))
        {
            throw new NameConstraintValidatorException("IP is from an excluded subtree.");
        }
    }

    private static boolean isIPConstrained(Set constraints, byte[] ip)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            byte[] constraint = (byte[])it.next();
            if (isIPConstrained(constraint, ip))
            {
                return true;
            }
        }

        return false;
    }

    /**
     * Checks if the IP address  ip</code> is constrained by
     *  constraint</code>.
     *
     * @param ip         The IP address.
     * @param constraint The constraint. This is an IP address concatenated with
     *                   its subnetmask.
     * @return  true</code> if constrained,  false</code>
     * otherwise.
     */
    private static boolean isIPConstrained(byte[] constraint, byte[] ip)
    {
        // Normalise IPv4-mapped IPv6 (::ffff:0:0/96 per RFC 4291 sec. 2.5.5.2)
        // to IPv4 on BOTH sides before the length-equality pre-filter, so a
        // SAN that encodes the same IPv4 address using the 16-byte IPv4-
        // mapped IPv6 form doesn't escape an 8-byte IPv4 constraint via
        // the address-family-length mismatch. RFC 4291 makes the two forms
        // equivalent for host identification, so the normalisation is also
        // semantics-preserving in the permitted-subtree direction.
        byte[] normIp = normalizeIPv4MappedIPv6Address(ip);
        byte[] normConstraint = normalizeIPv4MappedIPv6Constraint(constraint);

        int ipLength = normIp.length;

        if (ipLength != (normConstraint.length / 2))
        {
            return false;
        }

        byte[] subnetMask = new byte[ipLength];
        System.arraycopy(normConstraint, ipLength, subnetMask, 0, ipLength);

        byte[] permittedSubnetAddress = new byte[ipLength];

        byte[] ipSubnetAddress = new byte[ipLength];

        // the resulting IP address by applying the subnet mask
        for (int i = 0; i < ipLength; i++)
        {
            permittedSubnetAddress[i] = (byte)(normConstraint[i] & subnetMask[i]);
            ipSubnetAddress[i] = (byte)(normIp[i] & subnetMask[i]);
        }

        return Arrays.areEqual(permittedSubnetAddress, ipSubnetAddress);
    }

    /**
     * If {@code ip} is a 16-byte IPv4-mapped IPv6 address (RFC 4291
     * sec. 2.5.5.2: leading 80 bits zero, next 16 bits all-ones, trailing
     * 32 bits the IPv4 address), return the 4-byte IPv4 form; otherwise
     * return {@code ip} unchanged.
     */
    private static byte[] normalizeIPv4MappedIPv6Address(byte[] ip)
    {
        if (!isIPv4MappedIPv6Address(ip))
        {
            return ip;
        }
        byte[] ipv4 = new byte[4];
        System.arraycopy(ip, 12, ipv4, 0, 4);
        return ipv4;
    }

    /**
     * A Name-Constraints iPAddress constraint is encoded as
     * {@code IP || subnet-mask}. If both halves are in IPv4-mapped IPv6
     * form (the IP half matches the {@code ::ffff:0:0/96} prefix and the
     * mask half is all-ones across the first 96 bits), reduce to the
     * 8-byte (4-byte IPv4 || 4-byte mask) form. Otherwise return the
     * constraint unchanged. The mask check matters: a mask narrower than
     * /96 means the constraint is really an IPv6 range that happens to
     * start at an IPv4-mapped address, and collapsing it to IPv4 would
     * change which addresses match.
     */
    private static byte[] normalizeIPv4MappedIPv6Constraint(byte[] constraint)
    {
        if (constraint.length != 32)
        {
            return constraint;
        }
        byte[] ipHalf = new byte[16];
        byte[] maskHalf = new byte[16];
        System.arraycopy(constraint, 0, ipHalf, 0, 16);
        System.arraycopy(constraint, 16, maskHalf, 0, 16);
        if (!isIPv4MappedIPv6Address(ipHalf))
        {
            return constraint;
        }
        for (int i = 0; i < 12; i++)
        {
            if (maskHalf[i] != (byte)0xff)
            {
                return constraint;
            }
        }
        byte[] result = new byte[8];
        System.arraycopy(ipHalf, 12, result, 0, 4);
        System.arraycopy(maskHalf, 12, result, 4, 4);
        return result;
    }

    private static boolean isIPv4MappedIPv6Address(byte[] ip)
    {
        if (ip == null || ip.length != 16)
        {
            return false;
        }
        for (int i = 0; i < 10; i++)
        {
            if (ip[i] != 0)
            {
                return false;
            }
        }
        return ip[10] == (byte)0xff && ip[11] == (byte)0xff;
    }

    private static boolean isOtherNameConstrained(Set constraints, OtherName otherName)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            OtherName constraint = OtherName.getInstance(it.next());
            if (isOtherNameConstrained(constraint, otherName))
            {
                return true;
            }
        }

        return false;
    }

    private static boolean isOtherNameConstrained(OtherName constraint, OtherName otherName)
    {
        return constraint.equals(otherName);
    }

    private static boolean isEmailConstrained(Set constraints, String email)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            String constraint = (String)it.next();
            if (isEmailConstrained(constraint, email))
            {
                return true;
            }
        }

        return false;
    }

    private static boolean isEmailConstrained(String constraint, String email)
    {
        int atPos = constraint.indexOf('@');

        // a particular mailbox. RFC 1034 root-label trailing dot: the dNSName path strips it (see
        // isDNSConstrained); apply the same canonicalisation to the rfc822Name host so a trailing dot
        // (e.g. "user@bank.com.") cannot slip a leaf past an excluded/permitted "bank.com" constraint.
        if (atPos > 0)
        {
            return stripTrailingDot(email).equalsIgnoreCase(stripTrailingDot(constraint));
        }

        String sub = stripTrailingDot(email.substring(email.indexOf('@') + 1));

        // "@domain" style
        if (atPos == 0)
        {
            return sub.equalsIgnoreCase(stripTrailingDot(constraint.substring(1)));
        }

        // address in sub domain
        if (constraint.startsWith("."))
        {
            return withinDomain(sub, constraint);
        }

        // on particular host
        return sub.equalsIgnoreCase(stripTrailingDot(constraint));
    }

    private static boolean withinDomain(String testDomain, String domain)
    {
        if (domain.startsWith("."))
        {
            domain = domain.substring(1);
        }
        // Strip the RFC 1034 root-label trailing dot so the per-label
        // compare doesn't see a phantom empty label.
        testDomain = stripTrailingDot(testDomain);
        domain = stripTrailingDot(domain);

        String[] domainParts = Strings.split(domain, '.');
        String[] testDomainParts = Strings.split(testDomain, '.');

        // must have at least one subdomain
        if (testDomainParts.length <= domainParts.length)
        {
            return false;
        }

        int d = testDomainParts.length - domainParts.length;
        if (testDomainParts[d - 1].equals(""))
        {
            return false;
        }

        for (int i = 0; i < domainParts.length; i++)
        {
            if (!domainParts[i].equalsIgnoreCase(testDomainParts[d + i]))
            {
                return false;
            }
        }
        return true;
    }

    private static void checkExcludedDNS(Set excluded, String dns)
        throws NameConstraintValidatorException
    {
        if (isDNSConstrained(excluded, dns))
        {
            throw new NameConstraintValidatorException("DNS is from an excluded subtree.");
        }
    }

    private static void checkPermittedDNS(Set permitted, String dns)
        throws NameConstraintValidatorException
    {
        if (permitted != null
            && !(dns.length() == 0 && permitted.size() == 0)
            && !isDNSConstrained(permitted, dns))
        {
            throw new NameConstraintValidatorException("DNS is not from a permitted subtree.");
        }
    }

    private static boolean isDNSConstrained(Set constraints, String dns)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            String constraint = (String)it.next();
            if (isDNSConstrained(constraint, dns))
            {
                return true;
            }
        }

        return false;
    }

    private static boolean isDNSConstrained(String constraint, String dns)
    {
        // RFC 1034 sec. 3.1 allows a trailing dot to denote the root label of
        // a fully-qualified domain name. A dNSName SAN such as
        // "foo.example.com." (legal IA5String per RFC 5280 sec. 4.2.1.6) used
        // to escape Name-Constraint matching because withinDomain split it
        // to ["foo", "example", "com", ""], misaligning the per-label
        // compare against a "example.com" constraint and returning "not
        // constrained" — bypassing the excluded subtree.  Normalise away
        // at most one trailing dot on both sides before comparing.
        String normDns = stripTrailingDot(dns);
        String normConstraint = stripTrailingDot(constraint);
        return normDns.equalsIgnoreCase(normConstraint) || withinDomain(normDns, normConstraint);
    }

    private static String stripTrailingDot(String s)
    {
        // length > 1 so a single bare "." (theoretically the empty-label
        // root) is preserved rather than reduced to "".
        if (s != null && s.length() > 1 && s.charAt(s.length() - 1) == '.')
        {
            return s.substring(0, s.length() - 1);
        }
        return s;
    }

    /**
     * The common part of  email1</code> and  email2</code> is
     * added to the union  union</code>. If  email1</code> and
     *  email2</code> have nothing in common they are added both.
     *
     * @param email1 Email address constraint 1.
     * @param email2 Email address constraint 2.
     * @param union  The union.
     */
    private static void unionEmail(String email1, String email2, Set union)
    {
        // email1 is a particular address
        if (email1.indexOf('@') != -1)
        {
            String _sub = email1.substring(email1.indexOf('@') + 1);
            // both are a particular mailbox
            if (email2.indexOf('@') != -1)
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(_sub, email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (_sub.equalsIgnoreCase(email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
        // email1 specifies a domain
        else if (email1.startsWith("."))
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (withinDomain(_sub, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (isDNSConstrained(email2, email1))
                {
                    union.add(email2);
                }
                else if (withinDomain(email2, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            else
            {
                if (withinDomain(email2, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
        // email specifies a host
        else
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (_sub.equalsIgnoreCase(email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(email1, email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
    }

    private static void unionURI(String email1, String email2, Set union)
    {
        // email1 is a particular address
        if (email1.indexOf('@') != -1)
        {
            String _sub = email1.substring(email1.indexOf('@') + 1);
            // both are a particular mailbox
            if (email2.indexOf('@') != -1)
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(_sub, email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (_sub.equalsIgnoreCase(email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
        // email1 specifies a domain
        else if (email1.startsWith("."))
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (withinDomain(_sub, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (isDNSConstrained(email2, email1))
                {
                    union.add(email2);
                }
                else if (withinDomain(email2, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            else
            {
                if (withinDomain(email2, email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
        // email specifies a host
        else
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (_sub.equalsIgnoreCase(email1))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(email1, email2))
                {
                    union.add(email2);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    union.add(email1);
                }
                else
                {
                    union.add(email1);
                    union.add(email2);
                }
            }
        }
    }

    private static Set intersectDNS(Set permitted, Set dnss)
    {
        Set intersect = new HashSet();
        for (Iterator it = dnss.iterator(); it.hasNext();)
        {
            String dns = extractNameAsString((GeneralSubtree)it.next());

            if (permitted == null)
            {
                intersect.add(dns);
            }
            else
            {
                Iterator _iter = permitted.iterator();
                while (_iter.hasNext())
                {
                    String _permitted = (String)_iter.next();

                    if (isDNSConstrained(dns, _permitted))
                    {
                        intersect.add(_permitted);
                    }
                    else if (withinDomain(dns, _permitted))
                    {
                        intersect.add(dns);
                    }
                    else
                    {
                        // No intersection
                    }
                }
            }
        }

        return intersect;
    }

    private static Set unionDNS(Set excluded, String dns)
    {
        if (excluded.isEmpty())
        {
            excluded.add(dns);
            return excluded;
        }

        Set union = new HashSet();

        Iterator _iter = excluded.iterator();
        while (_iter.hasNext())
        {
            String _permitted = (String)_iter.next();

            if (isDNSConstrained(dns, _permitted))
            {
                union.add(dns);
            }
            else if (withinDomain(dns, _permitted))
            {
                union.add(_permitted);
            }
            else
            {
                union.add(_permitted);
                union.add(dns);
            }
        }

        return union;
    }

    /**
     * The most restricting part from  email1</code> and
     *  email2</code> is added to the intersection  intersect</code>.
     *
     * @param email1    Email address constraint 1.
     * @param email2    Email address constraint 2.
     * @param intersect The intersection.
     */
    private static void intersectEmail(String email1, String email2, Set intersect)
    {
        // email1 is a particular address
        if (email1.indexOf('@') != -1)
        {
            String _sub = email1.substring(email1.indexOf('@') + 1);
            // both are a particular mailbox
            if (email2.indexOf('@') != -1)
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(_sub, email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (_sub.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
        }
        // email specifies a domain
        else if (email1.startsWith("."))
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (withinDomain(_sub, email1))
                {
                    intersect.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (isDNSConstrained(email2, email1))
                {
                    intersect.add(email1);
                }
                else if (withinDomain(email2, email1))
                {
                    intersect.add(email2);
                }
                else
                {
                    // No intersection
                }
            }
            else
            {
                if (withinDomain(email2, email1))
                {
                    intersect.add(email2);
                }
            }
        }
        // email1 specifies a host
        else
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (_sub.equalsIgnoreCase(email1))
                {
                    intersect.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(email1, email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
        }
    }

    private static void checkExcludedURI(Set excluded, String uri)
        throws NameConstraintValidatorException
    {
        if (isURIConstrained(excluded, uri))
        {
            throw new NameConstraintValidatorException("URI is from an excluded subtree.");
        }
    }

    private static Set intersectURI(Set permitted, Set uris)
    {
        Set intersect = new HashSet();
        for (Iterator it = uris.iterator(); it.hasNext();)
        {
            String uri = extractNameAsString((GeneralSubtree)it.next());

            if (permitted == null)
            {
                intersect.add(uri);
            }
            else
            {
                Iterator _iter = permitted.iterator();
                while (_iter.hasNext())
                {
                    String _permitted = (String)_iter.next();
                    intersectURI(_permitted, uri, intersect);
                }
            }
        }
        return intersect;
    }

    private static Set unionURI(Set excluded, String uri)
    {
        if (excluded.isEmpty())
        {
            excluded.add(uri);
            return excluded;
        }

        Set union = new HashSet();

        Iterator _iter = excluded.iterator();
        while (_iter.hasNext())
        {
            String _excluded = (String)_iter.next();

            unionURI(_excluded, uri, union);
        }

        return union;
    }

    private static void intersectURI(String email1, String email2, Set intersect)
    {
        // email1 is a particular address
        if (email1.indexOf('@') != -1)
        {
            String _sub = email1.substring(email1.indexOf('@') + 1);
            // both are a particular mailbox
            if (email2.indexOf('@') != -1)
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(_sub, email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (_sub.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
        }
        // email specifies a domain
        else if (email1.startsWith("."))
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (withinDomain(_sub, email1))
                {
                    intersect.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (isDNSConstrained(email2, email1))
                {
                    intersect.add(email1);
                }
                else if (withinDomain(email2, email1))
                {
                    intersect.add(email2);
                }
                else
                {
                    // No intersection
                }
            }
            else
            {
                if (withinDomain(email2, email1))
                {
                    intersect.add(email2);
                }
            }
        }
        // email1 specifies a host
        else
        {
            if (email2.indexOf('@') != -1)
            {
                String _sub = email2.substring(email2.indexOf('@') + 1);
                if (_sub.equalsIgnoreCase(email1))
                {
                    intersect.add(email2);
                }
            }
            // email2 specifies a domain
            else if (email2.startsWith("."))
            {
                if (withinDomain(email1, email2))
                {
                    intersect.add(email1);
                }
            }
            // email2 specifies a particular host
            else
            {
                if (email1.equalsIgnoreCase(email2))
                {
                    intersect.add(email1);
                }
            }
        }
    }

    private static void checkPermittedURI(Set permitted, String uri)
        throws NameConstraintValidatorException
    {
        if (permitted != null
            && !(uri.length() == 0 && permitted.size() == 0)
            && !isURIConstrained(permitted, uri))
        {
            throw new NameConstraintValidatorException("URI is not from a permitted subtree.");
        }
    }

    private static boolean isURIConstrained(Set constraints, String uri)
    {
        Iterator it = constraints.iterator();
        while (it.hasNext())
        {
            String constraint = ((String)it.next());
            if (isURIConstrained(constraint, uri))
            {
                return true;
            }
        }

        return false;
    }

    private static boolean isURIConstrained(String constraint, String uri)
    {
        // Strip an RFC 1034 root-label trailing dot from the host, matching the dNSName path, so a
        // URI host such as "competitor.example." cannot slip past a "competitor.example" constraint.
        String host = stripTrailingDot(extractHostFromURL(uri));

        // in sub domain or domain
        if (constraint.startsWith("."))
        {
            return withinDomain(host, constraint);
        }

        // a host
        return host.equalsIgnoreCase(stripTrailingDot(constraint));
    }

    private static String extractHostFromURL(String url)
    {
        // RFC 3986 §3.2 authority structure:
        //   authority = [ userinfo "@" ] host [ ":" port ]
        // The strip order is: scheme → "//" → path/query/fragment terminator → userinfo (last '@') → host
        // with optional bracketed IPv6 / trailing ":port".
        String sub = url;
        int schemeEnd = sub.indexOf(':');
        if (schemeEnd >= 0)
        {
            sub = sub.substring(schemeEnd + 1);
        }
        if (sub.startsWith("//"))
        {
            sub = sub.substring(2);
        }
        for (int i = 0; i < sub.length(); ++i)
        {
            char c = sub.charAt(i);
            if (c == '/' || c == '?' || c == '#')
            {
                sub = sub.substring(0, i);
                break;
            }
        }
        int atPos = sub.lastIndexOf('@');
        if (atPos >= 0)
        {
            sub = sub.substring(atPos + 1);
        }
        if (sub.startsWith("["))
        {
            int closeBracket = sub.indexOf(']');
            if (closeBracket > 0)
            {
                return sub.substring(1, closeBracket);
            }
            return sub.substring(1);
        }
        int portColon = sub.lastIndexOf(':');
        if (portColon >= 0)
        {
            sub = sub.substring(0, portColon);
        }
        return sub;
    }

    /**
     * Returns the maximum IP address.
     *
     * @param ip1 The first IP address.
     * @param ip2 The second IP address.
     * @return The maximum IP address.
     */
    private static byte[] max(byte[] ip1, byte[] ip2)
    {
        return compareTo(ip1, ip2) > 0 ? ip1 : ip2;
    }

    /**
     * Returns the minimum IP address.
     *
     * @param ip1 The first IP address.
     * @param ip2 The second IP address.
     * @return The minimum IP address.
     */
    private static byte[] min(byte[] ip1, byte[] ip2)
    {
        return compareTo(ip1, ip2) < 0 ? ip1 : ip2;
    }

    /**
     * Compares IP address  ip1</code> with  ip2</code>. If ip1
     * is equal to ip2 0 is returned. If ip1 is bigger 1 is returned, -1
     * otherwise.
     *
     * @param ip1 The first IP address.
     * @param ip2 The second IP address.
     * @return 0 if ip1 is equal to ip2, 1 if ip1 is bigger, -1 otherwise.
     */
    private static int compareTo(byte[] ip1, byte[] ip2)
    {
        for (int i = 0; i < ip1.length; i++)
        {
            int t1 = ip1[i] & 0xFF, t2 = ip2[i] & 0xFF;
            if (t1 < t2)
            {
                return -1;
            }
            if (t1 > t2)
            {
                return 1;
            }
        }
        return 0;
    }

    /**
     * Returns the logical OR of the IP addresses  ip1</code> and
     *  ip2</code>.
     *
     * @param ip1 The first IP address.
     * @param ip2 The second IP address.
     * @return The OR of  ip1</code> and  ip2</code>.
     */
    private static byte[] or(byte[] ip1, byte[] ip2)
    {
        byte[] temp = new byte[ip1.length];
        for (int i = 0; i < ip1.length; i++)
        {
            temp[i] = (byte)(ip1[i] | ip2[i]);
        }
        return temp;
    }

    private static int hashCollection(Collection coll)
    {
        if (coll == null)
        {
            return 0;
        }
        int hash = 0;
        Iterator it1 = coll.iterator();
        while (it1.hasNext())
        {
            Object o = it1.next();
            if (o instanceof byte[])
            {
                hash += Arrays.hashCode((byte[])o);
            }
            else
            {
                hash += o.hashCode();
            }
        }
        return hash;
    }

    private static boolean collectionsAreEqual(Collection coll1, Collection coll2)
    {
        if (coll1 == coll2)
        {
            return true;
        }
        if (coll1 == null || coll2 == null)
        {
            return false;
        }
        if (coll1.size() != coll2.size())
        {
            return false;
        }
        Iterator it1 = coll1.iterator();

        while (it1.hasNext())
        {
            Object a = it1.next();
            Iterator it2 = coll2.iterator();
            boolean found = false;
            while (it2.hasNext())
            {
                Object b = it2.next();
                if (equals(a, b))
                {
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                return false;
            }
        }
        return true;
    }

    private static boolean equals(Object o1, Object o2)
    {
        if (o1 == o2)
        {
            return true;
        }
        if (o1 == null || o2 == null)
        {
            return false;
        }
        if (o1 instanceof byte[] && o2 instanceof byte[])
        {
            return Arrays.areEqual((byte[])o1, (byte[])o2);
        }
        else
        {
            return o1.equals(o2);
        }
    }

    /**
     * Stringifies an IPv4 or v6 address with subnet mask.
     *
     * @param ip The IP with subnet mask.
     * @return The stringified IP address.
     */
    private static String stringifyIP(byte[] ip)
    {
        StringBuffer temp = new StringBuffer();
        for (int i = 0; i < ip.length / 2; i++)
        {
            if (temp.length() > 0)
            {
                temp.append(".");
            }
            temp.append(Integer.toString(ip[i] & 0x00FF));
        }

        temp.append("/");
        boolean first = true;
        for (int i = ip.length / 2; i < ip.length; i++)
        {
            if (first)
            {
                first = false;
            }
            else
            {
                temp.append(".");
            }
            temp.append(Integer.toString(ip[i] & 0x00FF));
        }

        return temp.toString();
    }

    private static String stringifyIPCollection(Set ips)
    {
        StringBuffer temp = new StringBuffer();
        temp.append("[");
        for (Iterator it = ips.iterator(); it.hasNext();)
        {
            if (temp.length() > 1)
            {
                temp.append(",");
            }
            temp.append(stringifyIP((byte[])it.next()));
        }
        temp.append("]");
        return temp.toString();
    }

    private static String stringifyOtherNameCollection(Set otherNames)
    {
        StringBuffer temp = new StringBuffer();
        temp.append("[");
        for (Iterator it = otherNames.iterator(); it.hasNext();)
        {
            if (temp.length() > 1)
            {
                temp.append(",");
            }
            OtherName otherName = OtherName.getInstance(it.next());
            temp.append(otherName.getTypeID().getId());
            temp.append(":");
            try
            {
                // -DM Hex.toHexString
                temp.append(Hex.toHexString(otherName.getValue().toASN1Primitive().getEncoded()));
            }
            catch (IOException e)
            {
                temp.append(e.toString());
            }
        }
        temp.append("]");
        return temp.toString();
    }

    public String toString()
    {
        StringBuffer temp = new StringBuffer();

        addLine(temp, "permitted:");
        if (permittedSubtreesDN != null)
        {
            addLine(temp, "DN:");
            addLine(temp, permittedSubtreesDN.toString());
        }
        if (permittedSubtreesDNS != null)
        {
            addLine(temp, "DNS:");
            addLine(temp, permittedSubtreesDNS.toString());
        }
        if (permittedSubtreesEmail != null)
        {
            addLine(temp, "Email:");
            addLine(temp, permittedSubtreesEmail.toString());
        }
        if (permittedSubtreesURI != null)
        {
            addLine(temp, "URI:");
            addLine(temp, permittedSubtreesURI.toString());
        }
        if (permittedSubtreesIP != null)
        {
            addLine(temp, "IP:");
            addLine(temp, stringifyIPCollection(permittedSubtreesIP));
        }
        if (permittedSubtreesOtherName != null)
        {
            addLine(temp, "OtherName:");
            addLine(temp, stringifyOtherNameCollection(permittedSubtreesOtherName));
        }
        addLine(temp, "excluded:");
        if (!excludedSubtreesDN.isEmpty())
        {
            addLine(temp, "DN:");
            addLine(temp, excludedSubtreesDN.toString());
        }
        if (!excludedSubtreesDNS.isEmpty())
        {
            addLine(temp, "DNS:");
            addLine(temp, excludedSubtreesDNS.toString());
        }
        if (!excludedSubtreesEmail.isEmpty())
        {
            addLine(temp, "Email:");
            addLine(temp, excludedSubtreesEmail.toString());
        }
        if (!excludedSubtreesURI.isEmpty())
        {
            addLine(temp, "URI:");
            addLine(temp, excludedSubtreesURI.toString());
        }
        if (!excludedSubtreesIP.isEmpty())
        {
            addLine(temp, "IP:");
            addLine(temp, stringifyIPCollection(excludedSubtreesIP));
        }
        if (!excludedSubtreesOtherName.isEmpty())
        {
            addLine(temp, "OtherName:");
            addLine(temp, stringifyOtherNameCollection(excludedSubtreesOtherName));
        }
        return temp.toString();
    }

    private static void addLine(StringBuffer sb, String str)
    {
         sb.append(str).append(Strings.lineSeparator());
    }

    private static String extractNameAsString(GeneralSubtree subtree)
    {
        return extractNameAsString(subtree.getBase().getName());
    }

    private static String extractNameAsString(ASN1Encodable nameValue)
    {
        return ASN1IA5String.getInstance(nameValue).getString();
    }
}
