/*
 * ====================================================================
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 *
 */
package org.apache.hc.client5.http.impl.auth;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.Principal;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Formatter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Locale;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

import org.apache.hc.client5.http.auth.AuthChallenge;
import org.apache.hc.client5.http.auth.AuthScheme;
import org.apache.hc.client5.http.auth.AuthScope;
import org.apache.hc.client5.http.auth.AuthenticationException;
import org.apache.hc.client5.http.auth.Credentials;
import org.apache.hc.client5.http.auth.CredentialsProvider;
import org.apache.hc.client5.http.auth.MalformedChallengeException;
import org.apache.hc.client5.http.auth.StandardAuthScheme;
import org.apache.hc.client5.http.auth.UsernamePasswordCredentials;
import org.apache.hc.client5.http.protocol.HttpClientContext;
import org.apache.hc.client5.http.utils.ByteArrayBuilder;
import org.apache.hc.core5.annotation.Internal;
import org.apache.hc.core5.http.ClassicHttpRequest;
import org.apache.hc.core5.http.HttpEntity;
import org.apache.hc.core5.http.HttpHost;
import org.apache.hc.core5.http.HttpRequest;
import org.apache.hc.core5.http.NameValuePair;
import org.apache.hc.core5.http.message.BasicHeaderValueFormatter;
import org.apache.hc.core5.http.message.BasicNameValuePair;
import org.apache.hc.core5.http.protocol.HttpContext;
import org.apache.hc.core5.net.PercentCodec;
import org.apache.hc.core5.util.Args;
import org.apache.hc.core5.util.CharArrayBuffer;
import org.apache.hc.core5.util.TextUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Digest authentication scheme.
 * Both MD5 (default) and MD5-sess are supported.
 * Currently only qop=auth or no qop is supported. qop=auth-int
 * is unsupported. If auth and auth-int are provided, auth is
 * used.
 * <p>
 * Since the digest username is included as clear text in the generated
 * Authentication header, the charset of the username must be compatible
 * with the HTTP element charset used by the connection.
 * </p>
 *
 * @since 4.0
 */
public class DigestScheme implements AuthScheme, Serializable {

    private static final long serialVersionUID = 3883908186234566916L;

    private static final Logger LOG = LoggerFactory.getLogger(DigestScheme.class);

    /**
     * Hexa values used when creating 32 character long digest in HTTP DigestScheme
     * in case of authentication.
     *
     * @see #formatHex(byte[])
     */
    private static final char[] HEXADECIMAL = {
        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd',
        'e', 'f'
    };

    /**
     * Represent the possible values of quality of protection.
     */
    private enum QualityOfProtection {
        UNKNOWN, MISSING, AUTH_INT, AUTH
    }

    private transient Charset defaultCharset;
    private final Map<String, String> paramMap;
    private boolean complete;
    private transient ByteArrayBuilder buffer;

    /**
     * Flag indicating whether username hashing is supported.
     * <p>
     * This flag is used to determine if the server supports hashing of the username
     * as part of the Digest Access Authentication process. When set to {@code true},
     * the client is expected to hash the username using the same algorithm used for
     * hashing the credentials. This is in accordance with Section 3.4.4 of RFC 7616.
     * </p>
     * <p>
     * The default value is {@code false}, indicating that username hashing is not
     * supported. If the server requires username hashing (indicated by the
     * {@code userhash} parameter in the  a header set to {@code true}),
     * this flag should be set to {@code true} to comply with the server's requirements.
     * </p>
     */
    private boolean userhashSupported = false;


    private String lastNonce;
    private long nounceCount;
    private String cnonce;
    private byte[] a1;
    private byte[] a2;

    private UsernamePasswordCredentials credentials;

    public DigestScheme() {
        this.defaultCharset = StandardCharsets.UTF_8;
        this.paramMap = new HashMap<>();
        this.complete = false;
    }

    /**
     * @deprecated This constructor is deprecated to enforce the use of {@link StandardCharsets#UTF_8} encoding
     * in compliance with RFC 7616 for HTTP Digest Access Authentication. Use the default constructor {@link #DigestScheme()} instead.
     *
     * @param charset the {@link Charset} set to be used for encoding credentials. This parameter is ignored as UTF-8 is always used.
     */
    @Deprecated
    public DigestScheme(final Charset charset) {
        this();
    }

    public void initPreemptive(final Credentials credentials, final String cnonce, final String realm) {
        Args.notNull(credentials, "Credentials");
        Args.check(credentials instanceof UsernamePasswordCredentials,
                "Unsupported credential type: " + credentials.getClass());
        this.credentials = (UsernamePasswordCredentials) credentials;
        this.paramMap.put("cnonce", cnonce);
        this.paramMap.put("realm", realm);
    }

    @Override
    public String getName() {
        return StandardAuthScheme.DIGEST;
    }

    @Override
    public boolean isConnectionBased() {
        return false;
    }

    @Override
    public String getRealm() {
        return this.paramMap.get("realm");
    }

    @Override
    public void processChallenge(
            final AuthChallenge authChallenge,
            final HttpContext context) throws MalformedChallengeException {
        Args.notNull(authChallenge, "AuthChallenge");
        this.paramMap.clear();
        final List<NameValuePair> params = authChallenge.getParams();
        if (params != null) {
            for (final NameValuePair param: params) {
                this.paramMap.put(param.getName().toLowerCase(Locale.ROOT), param.getValue());
            }
        }
        if (this.paramMap.isEmpty()) {
            throw new MalformedChallengeException("Missing digest auth parameters");
        }

        final String userHashValue = this.paramMap.get("userhash");
        this.userhashSupported = "true".equalsIgnoreCase(userHashValue);

        this.complete = true;
    }

    @Override
    public boolean isChallengeComplete() {
        final String s = this.paramMap.get("stale");
        return !"true".equalsIgnoreCase(s) && this.complete;
    }

    @Override
    public boolean isResponseReady(
            final HttpHost host,
            final CredentialsProvider credentialsProvider,
            final HttpContext context) throws AuthenticationException {

        Args.notNull(host, "Auth host");
        Args.notNull(credentialsProvider, "CredentialsProvider");

        final AuthScope authScope = new AuthScope(host, getRealm(), getName());
        final Credentials credentials = credentialsProvider.getCredentials(
                authScope, context);
        if (credentials instanceof UsernamePasswordCredentials) {
            this.credentials = (UsernamePasswordCredentials) credentials;
            return true;
        }

        if (LOG.isDebugEnabled()) {
            final HttpClientContext clientContext = HttpClientContext.cast(context);
            final String exchangeId = clientContext.getExchangeId();
            LOG.debug("{} No credentials found for auth scope [{}]", exchangeId, authScope);
        }
        this.credentials = null;
        return false;
    }

    @Override
    public Principal getPrincipal() {
        return null;
    }

    @Override
            public String generateAuthResponse(
            final HttpHost host,
            final HttpRequest request,
            final HttpContext context) throws AuthenticationException {

        Args.notNull(request, "HTTP request");
        if (this.paramMap.get("realm") == null) {
            throw new AuthenticationException("missing realm");
        }
        if (this.paramMap.get("nonce") == null) {
            throw new AuthenticationException("missing nonce");
        }

        if (context != null) {
            final HttpClientContext clientContext = HttpClientContext.cast(context);
            final String nextNonce = clientContext.getNextNonce();
            if (!TextUtils.isBlank(nextNonce)) {
                this.paramMap.put("nonce", nextNonce);
                clientContext.setNextNonce(null);
            }
        }

        return createDigestResponse(request);
    }

    private static MessageDigest createMessageDigest(
            final String digAlg) throws UnsupportedDigestAlgorithmException {
        try {
            return MessageDigest.getInstance(digAlg);
        } catch (final Exception e) {
            throw new UnsupportedDigestAlgorithmException(
              "Unsupported algorithm in HTTP Digest authentication: "
               + digAlg);
        }
    }

    private String createDigestResponse(final HttpRequest request) throws AuthenticationException {
        if (credentials == null) {
            throw new AuthenticationException("User credentials have not been provided");
        }
        final String uri = request.getRequestUri();
        final String method = request.getMethod();
        final String realm = this.paramMap.get("realm");
        final String nonce = this.paramMap.get("nonce");
        final String opaque = this.paramMap.get("opaque");
        final String algorithm = this.paramMap.get("algorithm");

        final Set<String> qopset = new HashSet<>(8);
        QualityOfProtection qop = QualityOfProtection.UNKNOWN;
        final String qoplist = this.paramMap.get("qop");
        if (qoplist != null) {
            final StringTokenizer tok = new StringTokenizer(qoplist, ",");
            while (tok.hasMoreTokens()) {
                final String variant = tok.nextToken().trim();
                qopset.add(variant.toLowerCase(Locale.ROOT));
            }
            final HttpEntity entity = request instanceof ClassicHttpRequest ? ((ClassicHttpRequest) request).getEntity() : null;
            if (entity != null && qopset.contains("auth-int")) {
                qop = QualityOfProtection.AUTH_INT;
            } else if (qopset.contains("auth")) {
                qop = QualityOfProtection.AUTH;
            } else if (qopset.contains("auth-int")) {
                qop = QualityOfProtection.AUTH_INT;
            }
        } else {
            qop = QualityOfProtection.MISSING;
        }

        if (qop == QualityOfProtection.UNKNOWN) {
            throw new AuthenticationException("None of the qop methods is supported: " + qoplist);
        }

        final Charset charset = AuthSchemeSupport.parseCharset(paramMap.get("charset"), defaultCharset);

        // If an algorithm is not specified, default to MD5.

        DigestAlgorithm digAlg = null;

        final MessageDigest digester;
        try {
            digAlg = DigestAlgorithm.fromString(algorithm == null ? "MD5" : algorithm);
            digester = createMessageDigest(digAlg.getBaseAlgorithm());
        } catch (final UnsupportedDigestAlgorithmException ex) {
            throw new AuthenticationException("Unsupported digest algorithm: " + digAlg);
        }

        if (nonce.equals(this.lastNonce)) {
            nounceCount++;
        } else {
            nounceCount = 1;
            cnonce = null;
            lastNonce = nonce;
        }

        final StringBuilder sb = new StringBuilder(8);
        try (final Formatter formatter = new Formatter(sb, Locale.ROOT)) {
            formatter.format("%08x", nounceCount);
        }
        final String nc = sb.toString();

        if (cnonce == null) {
            cnonce = formatHex(createCnonce(digAlg));
        }

        if (buffer == null) {
            buffer = new ByteArrayBuilder(128);
        } else {
            buffer.reset();
        }
        buffer.charset(charset);

        a1 = null;
        a2 = null;


        // Extract username and username*
        String username = credentials.getUserName();
        String encodedUsername = null;
        // Check if 'username' has invalid characters and use 'username*'
        if (username != null && containsInvalidABNFChars(username)) {
            encodedUsername = "UTF-8''" + PercentCodec.RFC5987.encode(username);
        }

        final String usernameForDigest;
        if (this.userhashSupported) {
            final String usernameRealm = username + ":" + realm;
            final byte[] hashedBytes = digester.digest(usernameRealm.getBytes(StandardCharsets.UTF_8));
            usernameForDigest = formatHex(hashedBytes); // Use hashed username for digest
            username = usernameForDigest;
        } else if (encodedUsername != null) {
            usernameForDigest = encodedUsername; // Use encoded username for digest
        } else {
            usernameForDigest = username; // Use regular username for digest
        }

        // 3.2.2.2: Calculating digest
        if (digAlg.isSessionBased()) {
            // H( unq(username-value) ":" unq(realm-value) ":" passwd )
            //      ":" unq(nonce-value)
            //      ":" unq(cnonce-value)

            // calculated one per session
            buffer.append(username).append(":").append(realm).append(":").append(credentials.getUserPassword());
            final String checksum = formatHex(digester.digest(this.buffer.toByteArray()));
            buffer.reset();
            buffer.append(checksum).append(":").append(nonce).append(":").append(cnonce);
        } else {
            // unq(username-value) ":" unq(realm-value) ":" passwd
            buffer.append(username).append(":").append(realm).append(":").append(credentials.getUserPassword());
        }
        a1 = buffer.toByteArray();

        final String hasha1 = formatHex(digester.digest(a1));
        buffer.reset();

        if (qop == QualityOfProtection.AUTH) {
            // Method ":" digest-uri-value
            a2 = buffer.append(method).append(":").append(uri).toByteArray();
        } else if (qop == QualityOfProtection.AUTH_INT) {
            // Method ":" digest-uri-value ":" H(entity-body)
            final HttpEntity entity = request instanceof ClassicHttpRequest ? ((ClassicHttpRequest) request).getEntity() : null;
            if (entity != null && !entity.isRepeatable()) {
                // If the entity is not repeatable, try falling back onto QOP_AUTH
                if (qopset.contains("auth")) {
                    qop = QualityOfProtection.AUTH;
                    a2 = buffer.append(method).append(":").append(uri).toByteArray();
                } else {
                    throw new AuthenticationException("Qop auth-int cannot be used with " +
                            "a non-repeatable entity");
                }
            } else {
                final HttpEntityDigester entityDigester = new HttpEntityDigester(digester);
                try {
                    if (entity != null) {
                        entity.writeTo(entityDigester);
                    }
                    entityDigester.close();
                } catch (final IOException ex) {
                    throw new AuthenticationException("I/O error reading entity content", ex);
                }
                a2 = buffer.append(method).append(":").append(uri)
                        .append(":").append(formatHex(entityDigester.getDigest())).toByteArray();
            }
        } else {
            a2 = buffer.append(method).append(":").append(uri).toByteArray();
        }

        final String hasha2 = formatHex(digester.digest(a2));
        buffer.reset();

        // 3.2.2.1

        final byte[] digestInput;
        if (qop == QualityOfProtection.MISSING) {
            buffer.append(hasha1).append(":").append(nonce).append(":").append(hasha2);
        } else {
            buffer.append(hasha1).append(":").append(nonce).append(":").append(nc).append(":")
                .append(cnonce).append(":").append(qop == QualityOfProtection.AUTH_INT ? "auth-int" : "auth")
                .append(":").append(hasha2);
        }
        digestInput = buffer.toByteArray();
        buffer.reset();

        final String digest = formatHex(digester.digest(digestInput));

        final CharArrayBuffer buffer = new CharArrayBuffer(128);
        buffer.append(StandardAuthScheme.DIGEST + " ");

        final List<BasicNameValuePair> params = new ArrayList<>(20);
        if (this.userhashSupported) {
            // Use hashed username for the 'username' parameter
            params.add(new BasicNameValuePair("username", usernameForDigest));
            params.add(new BasicNameValuePair("userhash", "true"));
        } else if (encodedUsername != null) {
            // Use encoded 'username*' parameter
            params.add(new BasicNameValuePair("username*", encodedUsername));
        } else {
            // Use regular 'username' parameter
            params.add(new BasicNameValuePair("username", username));
        }
        params.add(new BasicNameValuePair("realm", realm));
        params.add(new BasicNameValuePair("nonce", nonce));
        params.add(new BasicNameValuePair("uri", uri));
        params.add(new BasicNameValuePair("response", digest));

        if (qop != QualityOfProtection.MISSING) {
            params.add(new BasicNameValuePair("qop", qop == QualityOfProtection.AUTH_INT ? "auth-int" : "auth"));
            params.add(new BasicNameValuePair("nc", nc));
            params.add(new BasicNameValuePair("cnonce", cnonce));
        }
        if (algorithm != null) {
            params.add(new BasicNameValuePair("algorithm", algorithm));
        }
        if (opaque != null) {
            params.add(new BasicNameValuePair("opaque", opaque));
        }

        for (int i = 0; i < params.size(); i++) {
            final BasicNameValuePair param = params.get(i);
            if (i > 0) {
                buffer.append(", ");
            }
            final String name = param.getName();
            final boolean noQuotes = "nc".equals(name) || "qop".equals(name)
                    || "algorithm".equals(name);
            BasicHeaderValueFormatter.INSTANCE.formatNameValuePair(buffer, param, !noQuotes);
        }
        return buffer.toString();
    }

    @Internal
    public String getNonce() {
        return lastNonce;
    }

    @Internal
    public long getNounceCount() {
        return nounceCount;
    }

    @Internal
    public String getCnonce() {
        return cnonce;
    }

    String getA1() {
        return a1 != null ? new String(a1, StandardCharsets.US_ASCII) : null;
    }

    String getA2() {
        return a2 != null ? new String(a2, StandardCharsets.US_ASCII) : null;
    }

    /**
     * Encodes a byte array digest into a hexadecimal string.
     * <p>
     * This method supports digests of various lengths, such as 16 bytes (128-bit) for MD5,
     * 32 bytes (256-bit) for SHA-256, and SHA-512/256. Each byte is converted to two
     * hexadecimal characters, so the resulting string length is twice the byte array length.
     * </p>
     *
     * @param binaryData the array containing the digest bytes
     * @return encoded hexadecimal string, or {@code null} if encoding failed
     */
    static String formatHex(final byte[] binaryData) {
        final int n = binaryData.length;
        final char[] buffer = new char[n * 2];
        for (int i = 0; i < n; i++) {
            final int low = binaryData[i] & 0x0f;
            final int high = (binaryData[i] & 0xf0) >> 4;
            buffer[i * 2] = HEXADECIMAL[high];
            buffer[(i * 2) + 1] = HEXADECIMAL[low];
        }
        return new String(buffer);
    }


    /**
     * Creates a random cnonce value based on the specified algorithm's expected entropy.
     * Adjusts the length of the byte array based on the algorithm to ensure sufficient entropy.
     *
     * @param algorithm the algorithm for which the cnonce is being generated (e.g., "MD5", "SHA-256", "SHA-512-256").
     * @return The cnonce value as a byte array.
     * @since 5.5
     */
    static byte[] createCnonce(final DigestAlgorithm algorithm) {
        final SecureRandom rnd = new SecureRandom();
        final int length;
        switch (algorithm.name().toUpperCase()) {
            case "SHA-256":
            case "SHA-512/256":
                length = 32;
                break;
            case "MD5":
            default:
                length = 16;
                break;
        }
        final byte[] tmp = new byte[length];
        rnd.nextBytes(tmp);
        return tmp;
    }


    private void writeObject(final ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeUTF(defaultCharset.name());
    }

    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        this.defaultCharset = Charset.forName(in.readUTF());
    }

    @Override
    public String toString() {
        return getName() + this.paramMap;
    }

    /**
     * Checks if a given string contains characters that are not allowed
     * in an ABNF quoted-string as per standard specifications.
     * <p>
     * The method checks for:
     * - Control characters (ASCII 0x00 to 0x1F and 0x7F).
     * - Characters outside the printable ASCII range (above 0x7E).
     * - Double quotes (&quot;) and backslashes (\), which are not allowed.
     * </p>
     *
     * @param value The string to be checked for invalid ABNF characters.
     * @return {@code true} if invalid characters are found, {@code false} otherwise.
     * @throws IllegalArgumentException if the input string is null.
     */
    private boolean containsInvalidABNFChars(final String value) {
        if (value == null) {
            throw new IllegalArgumentException("Input string should not be null.");
        }

        for (int i = 0; i < value.length(); i++) {
            final char c = value.charAt(i);

            // Check for control characters and DEL
            if (c <= 0x1F || c == 0x7F) {
                return true;
            }

            // Check for characters outside the range 0x20 to 0x7E
            if (c > 0x7E) {
                return true;
            }

            // Exclude double quotes and backslash
            if (c == '"' || c == '\\') {
                return true;
            }
        }
        return false;
    }

    /**
     * Enum representing supported digest algorithms for HTTP Digest Authentication,
     * including session-based variants.
     */
    private enum DigestAlgorithm {

        /**
         * MD5 digest algorithm.
         */
        MD5("MD5", false),

        /**
         * MD5 digest algorithm with session-based variant.
         */
        MD5_SESS("MD5", true),

        /**
         * SHA-256 digest algorithm.
         */
        SHA_256("SHA-256", false),

        /**
         * SHA-256 digest algorithm with session-based variant.
         */
        SHA_256_SESS("SHA-256", true),

        /**
         * SHA-512/256 digest algorithm.
         */
        SHA_512_256("SHA-512/256", false),

        /**
         * SHA-512/256 digest algorithm with session-based variant.
         */
        SHA_512_256_SESS("SHA-512/256", true);

        private final String baseAlgorithm;
        private final boolean sessionBased;

        /**
         * Constructor for {@code DigestAlgorithm}.
         *
         * @param baseAlgorithm the base name of the algorithm, e.g., "MD5" or "SHA-256"
         * @param sessionBased indicates if the algorithm is session-based (i.e., includes the "-sess" suffix)
         */
        DigestAlgorithm(final String baseAlgorithm, final boolean sessionBased) {
            this.baseAlgorithm = baseAlgorithm;
            this.sessionBased = sessionBased;
        }

        /**
         * Retrieves the base algorithm name without session suffix.
         *
         * @return the base algorithm name
         */
        private String getBaseAlgorithm() {
            return baseAlgorithm;
        }

        /**
         * Checks if the algorithm is session-based.
         *
         * @return {@code true} if the algorithm includes the "-sess" suffix, otherwise {@code false}
         */
        private boolean isSessionBased() {
            return sessionBased;
        }

        /**
         * Maps a string representation of an algorithm to the corresponding enum constant.
         *
         * @param algorithm the algorithm name, e.g., "SHA-256" or "SHA-512-256-sess"
         * @return the corresponding {@code DigestAlgorithm} constant
         * @throws UnsupportedDigestAlgorithmException if the algorithm is unsupported
         */
        private static DigestAlgorithm fromString(final String algorithm) {
            switch (algorithm.toUpperCase(Locale.ROOT)) {
                case "MD5":
                    return MD5;
                case "MD5-SESS":
                    return MD5_SESS;
                case "SHA-256":
                    return SHA_256;
                case "SHA-256-SESS":
                    return SHA_256_SESS;
                case "SHA-512/256":
                case "SHA-512-256":
                    return SHA_512_256;
                case "SHA-512-256-SESS":
                    return SHA_512_256_SESS;
                default:
                    throw new UnsupportedDigestAlgorithmException("Unsupported digest algorithm: " + algorithm);
            }
        }
    }


}
