//! X.509 certificates as live-provenance §4.4 writes them and §11.2 steps 2, 3 and 5 check
//! them: DER (ITU-T X.690) written and read here, Ed25519 throughout (RFC 8410), the profile
//! of C2PA 2.4 §14.5.1.1, a chain to a trust anchor (RFC 5280 §6, names and key identifiers
//! matched, each signature verified), and validity at an instant.

use ed25519_dalek::{Signer, SigningKey};
use sha2::{Digest, Sha256};

/// `id-Ed25519` (RFC 8410 §3).
pub const OID_ED25519: &[u64] = &[1, 3, 101, 112];
/// `id-at-commonName`.
pub const OID_CN: &[u64] = &[2, 5, 4, 3];
/// `id-at-organizationName`.
pub const OID_O: &[u64] = &[2, 5, 4, 10];
/// Basic Constraints.
pub const OID_BC: &[u64] = &[2, 5, 29, 19];
/// Key Usage.
pub const OID_KU: &[u64] = &[2, 5, 29, 15];
/// Extended Key Usage.
pub const OID_EKU: &[u64] = &[2, 5, 29, 37];
/// Subject Key Identifier.
pub const OID_SKI: &[u64] = &[2, 5, 29, 14];
/// Authority Key Identifier.
pub const OID_AKI: &[u64] = &[2, 5, 29, 35];
/// `c2pa-kp-claimSigning` (C2PA 2.4 §14.4.1).
pub const EKU_CLAIM_SIGNING: &[u64] = &[1, 3, 6, 1, 4, 1, 62558, 2, 1];
/// `id-kp-documentSigning`.
pub const EKU_DOCUMENT_SIGNING: &[u64] = &[1, 3, 6, 1, 5, 5, 7, 3, 36];
/// `id-kp-timeStamping`.
pub const EKU_TIME_STAMPING: &[u64] = &[1, 3, 6, 1, 5, 5, 7, 3, 8];
/// `id-kp-OCSPSigning`.
pub const EKU_OCSP_SIGNING: &[u64] = &[1, 3, 6, 1, 5, 5, 7, 3, 9];
/// `anyExtendedKeyUsage`.
pub const EKU_ANY: &[u64] = &[2, 5, 29, 37, 0];

// ───────────────────────────── writing ─────────────────────────────

fn tlv(tag: u8, content: &[u8]) -> Vec<u8> {
    let mut o = vec![tag];
    let n = content.len();
    if n < 0x80 {
        o.push(n as u8);
    } else {
        let bytes: Vec<u8> = n.to_be_bytes().iter().copied().skip_while(|&x| x == 0).collect();
        o.push(0x80 | bytes.len() as u8);
        o.extend_from_slice(&bytes);
    }
    o.extend_from_slice(content);
    o
}

fn seq(parts: &[Vec<u8>]) -> Vec<u8> {
    tlv(0x30, &parts.concat())
}

fn uint(v: u64) -> Vec<u8> {
    let mut b: Vec<u8> = v.to_be_bytes().iter().copied().skip_while(|&x| x == 0).collect();
    if b.is_empty() || b[0] & 0x80 != 0 {
        b.insert(0, 0);
    }
    tlv(0x02, &b)
}

/// The content octets of an OID.
pub fn oid_content(arcs: &[u64]) -> Vec<u8> {
    let mut o = Vec::new();
    let mut put = |mut v: u64| {
        let mut tmp = vec![(v & 0x7f) as u8];
        v >>= 7;
        while v > 0 {
            tmp.push(0x80 | (v & 0x7f) as u8);
            v >>= 7;
        }
        tmp.reverse();
        o.extend_from_slice(&tmp);
    };
    put(arcs[0] * 40 + arcs[1]);
    for a in &arcs[2..] {
        put(*a);
    }
    o
}

fn oid(arcs: &[u64]) -> Vec<u8> {
    tlv(0x06, &oid_content(arcs))
}

/// A name of an organization and a common name, each a UTF8String.
fn name(o: &str, cn: &str) -> Vec<u8> {
    seq(&[tlv(0x31, &seq(&[oid(OID_O), tlv(0x0C, o.as_bytes())])), tlv(0x31, &seq(&[oid(OID_CN), tlv(0x0C, cn.as_bytes())]))])
}

fn ed25519_alg() -> Vec<u8> {
    seq(&[oid(OID_ED25519)])
}

/// Days since 1970-01-01 of a civil date (proleptic Gregorian).
fn days_from_civil(y: i64, m: i64, d: i64) -> i64 {
    let y = if m <= 2 { y - 1 } else { y };
    let era = y.div_euclid(400);
    let yoe = y - era * 400;
    let doy = (153 * (if m > 2 { m - 3 } else { m + 9 }) + 2) / 5 + d - 1;
    let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
    era * 146_097 + doe - 719_468
}

/// The civil date of a day count since 1970-01-01.
fn civil_from_days(z: i64) -> (i64, i64, i64) {
    let z = z + 719_468;
    let era = z.div_euclid(146_097);
    let doe = z - era * 146_097;
    let yoe = (doe - doe / 1460 + doe / 36_524 - doe / 146_096) / 365;
    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
    let mp = (5 * doy + 2) / 153;
    let d = doy - (153 * mp + 2) / 5 + 1;
    let m = if mp < 10 { mp + 3 } else { mp - 9 };
    (yoe + era * 400 + if m <= 2 { 1 } else { 0 }, m, d)
}

/// `(year, month, day, hour, minute, second)` of Unix seconds.
pub fn civil(secs: u64) -> (i64, i64, i64, i64, i64, i64) {
    let s = secs as i64;
    let (y, m, d) = civil_from_days(s.div_euclid(86_400));
    let r = s.rem_euclid(86_400);
    (y, m, d, r / 3600, r % 3600 / 60, r % 60)
}

/// Unix seconds of a civil instant.
pub fn unix(y: i64, mo: i64, d: i64, h: i64, mi: i64, s: i64) -> i64 {
    days_from_civil(y, mo, d) * 86_400 + h * 3600 + mi * 60 + s
}

/// RFC 5280 §4.1.2.5: UTCTime through 2049, GeneralizedTime from 2050.
fn time(secs: u64) -> Vec<u8> {
    let (y, m, d, h, mi, s) = civil(secs);
    if y < 2050 {
        tlv(0x17, format!("{:02}{m:02}{d:02}{h:02}{mi:02}{s:02}Z", y % 100).as_bytes())
    } else {
        tlv(0x18, format!("{y:04}{m:02}{d:02}{h:02}{mi:02}{s:02}Z").as_bytes())
    }
}

fn ext(arcs: &[u64], critical: bool, value: Vec<u8>) -> Vec<u8> {
    let mut parts = vec![oid(arcs)];
    if critical {
        parts.push(tlv(0x01, &[0xFF]));
    }
    parts.push(tlv(0x04, &value));
    seq(&parts)
}

/// RFC 7093 §2 method 1: the leftmost 160 bits of the SHA-256 of the subject public key.
pub fn key_id(key: &[u8; 32]) -> [u8; 20] {
    Sha256::digest(key)[..20].try_into().expect("twenty bytes")
}

/// What a certificate states (§4.4).
#[derive(Clone, Debug)]
pub struct CertSpec<'a> {
    pub serial: u64,
    /// The organization of both names.
    pub organization: &'a str,
    pub issuer: &'a str,
    pub subject: &'a str,
    pub not_before: u64,
    pub not_after: u64,
    /// A certificate authority's (Basic Constraints `cA`, `keyCertSign` and `cRLSign`), or an
    /// end-entity's (`digitalSignature`, with `eku`).
    pub ca: bool,
    pub eku: Vec<&'a [u64]>,
    pub subject_key: [u8; 32],
    /// The issuer's public key, for the Authority Key Identifier; `None` in a self-signed
    /// certificate, which has none.
    pub issuer_key: Option<[u8; 32]>,
}

/// The DER certificate `spec` states, signed by `issuer`.
pub fn certificate(spec: &CertSpec, issuer: &SigningKey) -> Vec<u8> {
    let mut exts = vec![
        ext(OID_BC, true, if spec.ca { seq(&[tlv(0x01, &[0xFF])]) } else { seq(&[]) }),
        ext(OID_KU, true, if spec.ca { tlv(0x03, &[0x01, 0x06]) } else { tlv(0x03, &[0x07, 0x80]) }),
    ];
    if !spec.eku.is_empty() {
        exts.push(ext(OID_EKU, false, seq(&spec.eku.iter().map(|e| oid(e)).collect::<Vec<_>>())));
    }
    exts.push(ext(OID_SKI, false, tlv(0x04, &key_id(&spec.subject_key))));
    if let Some(k) = spec.issuer_key {
        exts.push(ext(OID_AKI, false, seq(&[tlv(0x80, &key_id(&k))])));
    }
    let spki = seq(&[ed25519_alg(), tlv(0x03, &[&[0u8][..], &spec.subject_key[..]].concat())]);
    let tbs = seq(&[
        tlv(0xA0, &uint(2)),
        uint(spec.serial),
        ed25519_alg(),
        name(spec.organization, spec.issuer),
        seq(&[time(spec.not_before), time(spec.not_after)]),
        name(spec.organization, spec.subject),
        spki,
        tlv(0xA3, &seq(&exts)),
    ]);
    let sig = issuer.sign(&tbs).to_bytes();
    seq(&[tbs, ed25519_alg(), tlv(0x03, &[&[0u8][..], &sig[..]].concat())])
}

// ───────────────────────────── reading ─────────────────────────────

/// One DER element: its tag, its content, and the whole of it.
struct El<'a> {
    tag: u8,
    content: &'a [u8],
    whole: &'a [u8],
}

/// Read one element from the front of `b` in DER: a one-byte tag, a definite length in its
/// shortest form, and the content.
fn el(b: &[u8]) -> Option<(El<'_>, &[u8])> {
    let tag = *b.first()?;
    if tag & 0x1f == 0x1f {
        return None;
    }
    let l0 = *b.get(1)? as usize;
    let (len, hdr) = if l0 < 0x80 {
        (l0, 2)
    } else {
        let n = l0 & 0x7f;
        if n == 0 || n > 4 {
            return None;
        }
        let bytes = b.get(2..2 + n)?;
        if bytes[0] == 0 {
            return None;
        }
        let len = bytes.iter().fold(0usize, |a, &x| a << 8 | x as usize);
        if len < 0x80 {
            return None;
        }
        (len, 2 + n)
    };
    let end = hdr.checked_add(len)?;
    let whole = b.get(..end)?;
    Some((El { tag, content: &whole[hdr..], whole }, &b[end..]))
}

/// The elements of a constructed content, all of it.
fn items(b: &[u8]) -> Option<Vec<El<'_>>> {
    let mut out = Vec::new();
    let mut rest = b;
    while !rest.is_empty() {
        let (e, r) = el(rest)?;
        out.push(e);
        rest = r;
    }
    Some(out)
}

/// One element that is the whole of `b`, of tag `tag`.
fn only(b: &[u8], tag: u8) -> Option<El<'_>> {
    let (e, rest) = el(b)?;
    (rest.is_empty() && e.tag == tag).then_some(e)
}

fn read_time(e: &El) -> Option<i64> {
    let s = std::str::from_utf8(e.content).ok()?;
    let (y, rest) = match (e.tag, s.len()) {
        (0x17, 13) => {
            let yy: i64 = s[..2].parse().ok()?;
            (if yy >= 50 { 1900 + yy } else { 2000 + yy }, &s[2..])
        }
        (0x18, 15) => (s[..4].parse().ok()?, &s[4..]),
        _ => return None,
    };
    if !rest.ends_with('Z') || !rest[..rest.len() - 1].bytes().all(|c| c.is_ascii_digit()) {
        return None;
    }
    let f = |i: usize| -> i64 { rest[i..i + 2].parse().unwrap_or(-1) };
    let (mo, d, h, mi, sec) = (f(0), f(2), f(4), f(6), f(8));
    if !(1..=12).contains(&mo) || !(1..=31).contains(&d) || h > 23 || mi > 59 || sec > 59 || h < 0 || mi < 0 || sec < 0 {
        return None;
    }
    Some(unix(y, mo, d, h, mi, sec))
}

/// One extension.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Ext {
    pub oid: Vec<u8>,
    pub critical: bool,
    pub value: Vec<u8>,
}

/// A certificate, read.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Cert {
    pub der: Vec<u8>,
    pub tbs: Vec<u8>,
    pub version: u64,
    pub issuer: Vec<u8>,
    pub subject: Vec<u8>,
    pub not_before: i64,
    pub not_after: i64,
    pub key: [u8; 32],
    pub unique_ids: bool,
    pub ed25519: bool,
    pub exts: Vec<Ext>,
    pub sig: [u8; 64],
}

fn is_ed25519_alg(b: &[u8]) -> bool {
    b == ed25519_alg().as_slice()
}

/// Read a DER certificate. It reads only as an Ed25519 key; `ed25519` says whether both of
/// its signature algorithm fields are `id-Ed25519` without parameters.
pub fn read_cert(der: &[u8]) -> Option<Cert> {
    let top = only(der, 0x30)?;
    let parts = items(top.content)?;
    let [tbs, alg, sigbits] = parts.as_slice() else { return None };
    if tbs.tag != 0x30 || alg.tag != 0x30 || sigbits.tag != 0x03 {
        return None;
    }
    let t = items(tbs.content)?;
    let mut i = 0;
    let version = if t.first()?.tag == 0xA0 {
        let v = only(t[0].content, 0x02)?;
        i = 1;
        v.content.iter().fold(0u64, |a, &x| a << 8 | x as u64)
    } else {
        0
    };
    let [serial, tbs_alg, issuer, validity, subject, spki, rest @ ..] = &t[i..] else { return None };
    if serial.tag != 0x02 || tbs_alg.tag != 0x30 || issuer.tag != 0x30 || validity.tag != 0x30 || subject.tag != 0x30 || spki.tag != 0x30 {
        return None;
    }
    let v = items(validity.content)?;
    let [nb, na] = v.as_slice() else { return None };
    let sp = items(spki.content)?;
    let [spki_alg, keybits] = sp.as_slice() else { return None };
    if !is_ed25519_alg(spki_alg.whole) || keybits.tag != 0x03 || keybits.content.len() != 33 || keybits.content[0] != 0 {
        return None;
    }
    let mut unique_ids = false;
    let mut exts = Vec::new();
    for e in rest {
        match e.tag {
            0x81 | 0x82 => unique_ids = true,
            0xA3 => {
                for x in items(only(e.content, 0x30)?.content)? {
                    if x.tag != 0x30 {
                        return None;
                    }
                    let f = items(x.content)?;
                    let (o, crit, val) = match f.as_slice() {
                        [o, v] => (o, false, v),
                        [o, c, v] if c.tag == 0x01 && c.content == [0xFF] => (o, true, v),
                        _ => return None,
                    };
                    if o.tag != 0x06 || val.tag != 0x04 {
                        return None;
                    }
                    exts.push(Ext { oid: o.content.to_vec(), critical: crit, value: val.content.to_vec() });
                }
            }
            _ => return None,
        }
    }
    if sigbits.content.len() != 65 || sigbits.content[0] != 0 {
        return None;
    }
    Some(Cert {
        der: der.to_vec(),
        tbs: tbs.whole.to_vec(),
        version,
        issuer: issuer.whole.to_vec(),
        subject: subject.whole.to_vec(),
        not_before: read_time(nb)?,
        not_after: read_time(na)?,
        key: keybits.content[1..].try_into().expect("thirty-two bytes"),
        unique_ids,
        ed25519: is_ed25519_alg(tbs_alg.whole) && is_ed25519_alg(alg.whole),
        exts,
        sig: sigbits.content[1..].try_into().expect("sixty-four bytes"),
    })
}

impl Cert {
    fn ext(&self, arcs: &[u64]) -> Option<&Ext> {
        let o = oid_content(arcs);
        self.exts.iter().find(|e| e.oid == o)
    }

    /// The Subject Key Identifier, where present.
    pub fn ski(&self) -> Option<Vec<u8>> {
        Some(only(&self.ext(OID_SKI)?.value, 0x04)?.content.to_vec())
    }

    /// The key identifier of the Authority Key Identifier, where present.
    pub fn aki(&self) -> Option<Vec<u8>> {
        let s = only(&self.ext(OID_AKI)?.value, 0x30)?;
        let f = items(s.content)?;
        f.iter().find(|e| e.tag == 0x80).map(|e| e.content.to_vec())
    }

    /// Whether Basic Constraints asserts `cA`; `None` when the extension does not read.
    fn ca(&self) -> Option<bool> {
        let Some(e) = self.ext(OID_BC) else { return Some(false) };
        let s = only(&e.value, 0x30)?;
        match items(s.content)?.first() {
            Some(b) if b.tag == 0x01 => Some(b.content == [0xFF]),
            _ => Some(false),
        }
    }

    /// The Key Usage bits as a 16-bit field, bit 0 (`digitalSignature`) at the top.
    fn key_usage(&self) -> Option<u16> {
        let b = only(&self.ext(OID_KU)?.value, 0x03)?;
        let c = b.content;
        if c.is_empty() || c.len() > 3 || c[0] > 7 {
            return None;
        }
        Some(c[1..].iter().enumerate().fold(0u16, |a, (i, &x)| a | (x as u16) << (8 - 8 * i as u32)))
    }

    fn ekus(&self) -> Option<Vec<Vec<u8>>> {
        let s = only(&self.ext(OID_EKU)?.value, 0x30)?;
        items(s.content)?.iter().map(|e| (e.tag == 0x06).then(|| e.content.to_vec())).collect()
    }
}

/// C2PA 2.4 §14.5.1.1 and this extension's §4.4, for the claim signer's end-entity
/// certificate (`ca` false) or an intermediate (`ca` true): `credential_invalid` where it
/// fails.
pub fn profile_ok(c: &Cert, ca: bool) -> bool {
    let known = [OID_BC, OID_KU, OID_EKU, OID_SKI, OID_AKI].map(oid_content);
    let mut seen: Vec<&Vec<u8>> = Vec::new();
    for e in &c.exts {
        if seen.contains(&&e.oid) || (e.critical && !known.contains(&e.oid)) {
            return false;
        }
        seen.push(&e.oid);
    }
    if c.version != 2 || !c.ed25519 || c.unique_ids || c.aki().is_none() {
        return false;
    }
    let (Some(is_ca), Some(ku)) = (c.ca(), c.key_usage()) else { return false };
    const DIGITAL_SIGNATURE: u16 = 0x8000;
    const KEY_CERT_SIGN: u16 = 0x0400;
    if ca {
        return is_ca && ku & KEY_CERT_SIGN != 0 && c.ski().is_some();
    }
    if is_ca || ku & DIGITAL_SIGNATURE == 0 || ku & KEY_CERT_SIGN != 0 {
        return false;
    }
    let Some(ekus) = c.ekus() else { return false };
    let has = |arcs: &[u64]| ekus.contains(&oid_content(arcs));
    !ekus.is_empty()
        && !has(EKU_ANY)
        && has(EKU_CLAIM_SIGNING)
        && !has(EKU_TIME_STAMPING)
        && !has(EKU_OCSP_SIGNING)
}

/// Whether `issuer` issued `c`: the issuer name is its subject, the key identifiers agree,
/// and its key verifies the signature, strictly.
fn issued_by(c: &Cert, issuer: &Cert) -> bool {
    c.issuer == issuer.subject
        && c.aki().is_some_and(|a| issuer.ski().is_none_or(|s| s == a))
        && crate::sig::verify_strict(&issuer.key, &c.tbs, &c.sig).is_ok()
}

/// §11.2 step 3: `chain` (end-entity first) leads to one of `anchors`; the anchor's index.
pub fn chain_to_anchor(chain: &[Cert], anchors: &[Cert]) -> Option<usize> {
    if chain.is_empty() || chain.windows(2).any(|w| !issued_by(&w[0], &w[1])) {
        return None;
    }
    let last = chain.last().expect("non-empty");
    anchors.iter().position(|a| issued_by(last, a))
}

/// §11.2 step 5: the instant `t_us` (microseconds) is within the validity of every certificate.
pub fn valid_at(certs: &[&Cert], t_us: u64) -> bool {
    let t = t_us as i128;
    certs.iter().all(|c| (c.not_before as i128) * 1_000_000 <= t && t <= (c.not_after as i128) * 1_000_000)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn spec<'a>(ca: bool, sub: [u8; 32], iss: Option<[u8; 32]>, eku: Vec<&'a [u64]>) -> CertSpec<'a> {
        CertSpec {
            serial: 1,
            organization: "o",
            issuer: "issuer",
            subject: if ca { "issuer" } else { "subject" },
            not_before: 1_767_225_600,
            not_after: 1_798_761_600,
            ca,
            eku,
            subject_key: sub,
            issuer_key: iss,
        }
    }

    #[test]
    fn dates_round_trip() {
        for s in [0u64, 951_782_400, 1_767_225_600, 2_524_608_000, 4_102_444_799] {
            let (y, m, d, h, mi, sec) = civil(s);
            assert_eq!(unix(y, m, d, h, mi, sec), s as i64);
        }
        assert_eq!(civil(1_767_225_600), (2026, 1, 1, 0, 0, 0));
    }

    #[test]
    fn a_chain_reads_meets_the_profile_and_reaches_its_anchor() {
        let root = SigningKey::from_bytes(&[1; 32]);
        let ee = SigningKey::from_bytes(&[2; 32]);
        let rk = root.verifying_key().to_bytes();
        let ek = ee.verifying_key().to_bytes();
        let mut rs = spec(true, rk, None, vec![]);
        rs.issuer_key = None;
        let anchor = read_cert(&certificate(&rs, &root)).unwrap();
        let leaf = read_cert(&certificate(&spec(false, ek, Some(rk), vec![EKU_CLAIM_SIGNING]), &root)).unwrap();
        assert!(profile_ok(&leaf, false));
        assert_eq!(chain_to_anchor(std::slice::from_ref(&leaf), std::slice::from_ref(&anchor)), Some(0));
        assert!(valid_at(&[&leaf, &anchor], 1_790_000_000_000_000));
        assert!(!valid_at(&[&leaf, &anchor], 1_800_000_000_000_000));
        // A time-stamping end-entity, or one with no Authority Key Identifier, fails the profile.
        let ts = read_cert(&certificate(&spec(false, ek, Some(rk), vec![EKU_TIME_STAMPING]), &root)).unwrap();
        assert!(!profile_ok(&ts, false));
        let no_aki = read_cert(&certificate(&spec(false, ek, None, vec![EKU_CLAIM_SIGNING]), &root)).unwrap();
        assert!(!profile_ok(&no_aki, false));
        // Signed by another key, it reaches no anchor.
        let forged = read_cert(&certificate(&spec(false, ek, Some(rk), vec![EKU_CLAIM_SIGNING]), &ee)).unwrap();
        assert_eq!(chain_to_anchor(&[forged], &[anchor]), None);
    }
}
