use aho_corasick::{AhoCorasick, MatchKind};
use crc::{CRC_4_G_704, Crc};
use ed25519_dalek::{
    SecretKey, Signature, SigningKey, VerifyingKey, ed25519::signature::SignerMut,
};
use include_lines::static_include_lines;
use rand_chacha::{
    ChaCha12Rng,
    rand_core::{RngCore, SeedableRng},
};
use serde::{Deserialize, Serialize};
use sha3::{Digest, Sha3_256};

const CHECKSUM: Crc<u8> = Crc::<u8>::new(&CRC_4_G_704);
static_include_lines!(DICTIONARY, "src/orchard-street-medium.txt");

/// A signature verifying an arbitrary message
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct Certificate {
    pub key: VerifyingKey,
    pub sig: Signature,
}

impl Certificate {
    /// Verify a message against this certificate
    pub fn verify(&self, message: &[u8]) -> Result<(), ed25519_dalek::SignatureError> {
        self.key.verify_strict(message, &self.sig)
    }
}

/// Errors that may occur during sealed key decoding
#[derive(Clone, Debug)]
pub enum DecodeError {
    WrongLength,
    CrcMismatch,
}

/// A secret key, XOR'd with a hashed password as last-resort security
#[derive(Serialize, Deserialize)]
pub struct SealedKey([u8; 32]);

impl SealedKey {
    /// Seal a raw secret key with a given passphrase
    pub fn seal(mut key: SecretKey, passphrase: impl AsRef<str>) -> Self {
        // Initialize crypto
        let mut hasher = Sha3_256::new();

        // Hash passphrase
        hasher.update(passphrase.as_ref());
        let hash = hasher.finalize();

        // XOR with passphrase hash
        for (k, h) in key.iter_mut().zip(hash) {
            *k ^= h;
        }

        Self(key)
    }

    /// Unseal into a raw secret key with a given passphrase
    ///
    /// No checks are done on if the passphrase was valid or not.
    pub fn unseal(&self, passphrase: impl AsRef<str>) -> SecretKey {
        // Initialize crypto
        let mut hasher = Sha3_256::new();

        // Hash passphrase
        hasher.update(passphrase.as_ref());
        let hash = hasher.finalize();

        // XOR with passphrase hash
        let mut key = self.0.clone();
        for (k, h) in key.iter_mut().zip(hash) {
            *k ^= h;
        }

        key
    }

    /// Encode the key into a list of words suitable for writing down and storing securely
    fn encode(&self) -> [&'static str; 20] {
        // Compute CRC
        let checksum = CHECKSUM.checksum(&self.0);

        // Break into 13-bit indices
        let mut indices = [0usize; 20];
        for (i, byte) in self.0.iter().enumerate() {
            let bit = i * 8;
            let idx = bit / 13;
            let shift = (bit as isize) % 13 - 4;

            if shift <= 0 {
                indices[idx] |= (*byte as usize) << -shift;
            } else {
                indices[idx] |= (*byte as usize) >> shift;
                indices[idx + 1] |= ((*byte as usize) << (13 - shift)) & 0x1fff;
            }
        }
        indices[19] |= checksum as usize;

        indices.map(|i| DICTIONARY[i])
    }

    pub fn decode(input: impl AsRef<str>) -> Result<Self, DecodeError> {
        // Strip any non-alphabetic characters
        let alpha = input
            .as_ref()
            .chars()
            .filter(|c| c.is_alphabetic())
            .collect::<String>();

        // Construct Aho-Corasick automaton
        // TODO See if this can be done at compile time
        let ac = AhoCorasick::builder()
            .ascii_case_insensitive(true)
            .build(DICTIONARY)
            .unwrap();

        // Find all overlapping matches
        let mut matches = ac.find_overlapping_iter(&alpha).collect::<Vec<_>>();

        // Decode using dynamic programming
        matches.sort_by(|m, n| m.end().cmp(&n.end()));

        let mut p = Vec::with_capacity(matches.len());
        for &m in &matches {
            let pv = matches.binary_search_by(|n| n.end().cmp(&m.start()));
            p.push(pv.ok());
        }

        let mut opt: Vec<usize> = Vec::with_capacity(matches.len());
        for i in 0..matches.len() {
            if let Some(pv) = p[i] {
                opt.push(
                    (matches[i].len() + opt[pv])
                        .max(opt.get(i.saturating_sub(1)).copied().unwrap_or(0)),
                );
            } else {
                opt.push(opt.get(i.saturating_sub(1)).copied().unwrap_or(0));
            }
        }

        let mut indices = Vec::with_capacity(20);
        let mut index = opt.len() - 1;
        while indices.len() < 20 {
            let pv = p[index].unwrap_or(0);

            if matches[index].len() + opt[pv] > opt[index.saturating_sub(1)] {
                indices.push(matches[index].pattern().as_usize());
                index = pv;
            } else {
                index = index.saturating_sub(1);
            }
        }

        indices.reverse();

        // Check length
        if indices.len() != 20 {
            return Err(DecodeError::WrongLength);
        }

        unimplemented!();
    }
}

/// A public/sealed-secret keypair capable of producing certificates
#[derive(Serialize, Deserialize)]
pub struct Keypair {
    public: VerifyingKey,
    secret: SealedKey,
}

impl Keypair {
    /// Create a new random keypair with a passphrase
    pub fn new(passphrase: impl AsRef<str>) -> Self {
        // Initalize crypto
        let mut rng = ChaCha12Rng::from_os_rng();

        // Generate secret key
        let mut unsealed = SecretKey::default();
        rng.fill_bytes(&mut unsealed);

        // Derive public key
        let public = SigningKey::from_bytes(&unsealed).verifying_key();

        // Seal secret key
        let secret = SealedKey::seal(unsealed, passphrase);

        Self { public, secret }
    }

    /// Sign a message with this keypair
    pub fn sign(&self, passphrase: impl AsRef<str>, message: &[u8]) -> Certificate {
        // Unseal secret key
        let unsealed = self.secret.unseal(passphrase);

        // Sign message
        let mut signer = SigningKey::from_bytes(&unsealed);
        let signature = signer.sign(message);

        Certificate {
            key: self.public.clone(),
            sig: signature,
        }
    }

    /// Sign this keypair's public key with itself
    pub fn self_sign(&self, passphrase: impl AsRef<str>) -> Certificate {
        self.sign(passphrase, self.public.as_bytes())
    }

    /// Encode the secret key into a list of words suitable for writing down and storing securely
    pub fn encode_secret(&self) -> [&'static str; 20] {
        self.secret.encode()
    }

    pub fn from_encoded(
        encoded: impl AsRef<str>,
        passphrase: impl AsRef<str>,
    ) -> Result<Self, DecodeError> {
        let sealed = SealedKey::decode(encoded)?;
        let unsealed = sealed.unseal(passphrase);

        Ok(Self {
            public: SigningKey::from_bytes(&unsealed).verifying_key(),
            secret: sealed,
        })
    }
}