//! FFXIV path hashing primitives.
//!
//! Provides the path-to-key transformation that `SqPack` index tables are
//! built on.
//!
//! The hash
//! --------
//!
//! Every `SqPack` index keys its entries by CRC32 of a normalised game path,
//! computed with the standard reflected CRC32 byte loop (polynomial
//! `0xEDB8_8320`, init `0xFFFF_FFFF`, reflected input/output) but **without**
//! the standard final XOR. That matches Lumina's C# `Crc32.Get` — whose last
//! line `return ~( crcLocal ^ uint.MaxValue )` is algebraically just
//! `crcLocal` — and is what the `.index` / `.index2` hash-table keys equal on
//! disk. The empty input hashes to `0xFFFF_FFFF` here, not `0`. To recover
//! the standard zlib/IEEE CRC32 of the same bytes, XOR the output with
//! `0xFFFF_FFFF`.
//!
//! Two key shapes
//! --------------
//!
//! - v1 (`.index`) splits the path on its last `/`, CRC32's the folder and
//!   file halves separately, and concatenates them as `folder_hash << 32 |
//!   file_hash`. See [`hash_index1_path`] and [`hash_index1_key`].
//! - v2 (`.index2`) CRC32's the whole normalised path as a single 32-bit key.
//!   See [`hash_index2`].
//!
//! Normalisation
//! -------------
//!
//! Both shapes lowercase ASCII and replace backslashes with forward slashes
//! before hashing. The lowercase conversion is byte-wise ASCII only — non-ASCII
//! bytes pass through unchanged — which matches what the FFXIV asset
//! pipeline does. Real game paths are ASCII; if a future asset name carries
//! UTF-8 the hash will still be deterministic, it just won't case-fold the
//! non-ASCII bytes.
//!
//! No allocation in the primitive
//! ------------------------------
//!
//! [`crc32`] is the byte-slice primitive and allocates nothing. The
//! higher-level path entry points each allocate one normalised buffer
//! (lowercase ASCII + `/` separators); callers in hot loops that already
//! hold a pre-normalised path can call [`crc32`] directly on its bytes.

/// Polynomial for the standard reflected CRC32 (IEEE, zlib, gzip, PNG).
const CRC32_POLY: u32 = 0xEDB8_8320;

/// Precomputed 256-entry lookup table for the byte-at-a-time CRC32 inner
/// loop. Built at compile time via [`build_table`].
const CRC32_TABLE: [u32; 256] = build_table();

const fn build_table() -> [u32; 256] {
    let mut table = [0u32; 256];
    // `i` is a u32 deliberately — the loop terminates at 256 so it fits, and
    // a u32 lets us seed `k` without going through a usize→u32 cast (which
    // clippy's cast_possible_truncation would otherwise flag).
    let mut i: u32 = 0;
    while i < 256 {
        let mut k = i;
        let mut j = 0;
        while j < 8 {
            k = if k & 1 != 0 {
                (k >> 1) ^ CRC32_POLY
            } else {
                k >> 1
            };
            j += 1;
        }
        table[i as usize] = k;
        i += 1;
    }
    table
}

/// Compute the FFXIV / Lumina `SqPack` CRC32 of `bytes`.
///
/// Standard reflected CRC32 byte loop with the standard `0xEDB8_8320`
/// polynomial and `0xFFFF_FFFF` init, but **without** the standard final
/// XOR — matching Lumina's `Crc32.Get` form, which is what `SqPack` `.index`
/// / `.index2` hash keys equal on disk. The empty input hashes to
/// `0xFFFF_FFFF`, **not** `0`. To get the standard zlib / IEEE CRC32 of the
/// same bytes, XOR the output with `0xFFFF_FFFF`.
#[must_use]
pub fn crc32(bytes: &[u8]) -> u32 {
    let mut state: u32 = 0xFFFF_FFFF;
    for &b in bytes {
        let idx = ((state ^ u32::from(b)) & 0xFF) as usize;
        state = CRC32_TABLE[idx] ^ (state >> 8);
    }
    state
}

/// Normalise a game-relative path for hashing: ASCII-lowercase, `\` → `/`.
///
/// Operates on the raw byte sequence — every input byte produces exactly one
/// output byte, so non-ASCII bytes round-trip unchanged. The CRC32 layer
/// hashes bytes directly, so returning `Vec<u8>` lets us avoid an unsafe
/// `String::from_utf8_unchecked` for inputs whose ASCII-case-fold could
/// otherwise leave the buffer not-quite-UTF-8.
///
/// Shared with the routing layer in [`crate::route`] so the two stay in
/// lockstep: a path that hashes to a given key must route to the archive
/// keyed by that hash. The helper is `pub(crate)` so it is reusable inside
/// the crate without committing to a public surface.
#[must_use]
pub(crate) fn normalize(path: &str) -> Vec<u8> {
    let mut out = Vec::with_capacity(path.len());
    for b in path.bytes() {
        let c = if b == b'\\' {
            b'/'
        } else {
            b.to_ascii_lowercase()
        };
        out.push(c);
    }
    out
}

/// Hash a game-relative path the v1 (`.index`) way.
///
/// Lowercases ASCII, normalises `\` to `/`, splits on the **last** `/`, and
/// returns `(folder_hash, file_hash)` — two independent CRC32s. A path with
/// no `/` has an empty folder (CRC32 of the empty string, which under the
/// no-final-XOR convention used here is `0xFFFF_FFFF`, **not** `0`) and a
/// file half equal to the whole input.
#[must_use]
pub fn hash_index1_path(game_path: &str) -> (u32, u32) {
    let normalised = normalize(game_path);
    let (folder, file) = match normalised.iter().rposition(|&b| b == b'/') {
        Some(i) => (&normalised[..i], &normalised[i + 1..]),
        None => (&[][..], &normalised[..]),
    };
    (crc32(folder), crc32(file))
}

/// Composite v1 key: `((folder_hash as u64) << 32) | file_hash as u64`.
///
/// This is the 64-bit key the v1 index tables are keyed on; pair with
/// [`crate::Index::get`] (or feed the halves to
/// [`crate::Index::get_by_parts`]).
#[must_use]
pub fn hash_index1_key(game_path: &str) -> u64 {
    let (folder, file) = hash_index1_path(game_path);
    (u64::from(folder) << 32) | u64::from(file)
}

/// Hash a game-relative path the v2 (`.index2`) way.
///
/// Lowercases ASCII, normalises `\` to `/`, then CRC32's the whole resulting
/// byte sequence. The single `u32` is the key [`crate::Index2::get`]
/// expects.
#[must_use]
pub fn hash_index2(game_path: &str) -> u32 {
    let normalised = normalize(game_path);
    crc32(&normalised)
}

/// Composite v1 key for an already-normalised byte buffer.
///
/// Equivalent to [`hash_index1_key`] but skips the [`normalize`] allocation —
/// the caller has already done it. Used by [`crate::sqpack::SqPack::read_file`]
/// to avoid re-normalising the same path three times when hashing v1 + v2 and
/// routing.
#[must_use]
pub(crate) fn hash_index1_key_normalized(normalised: &[u8]) -> u64 {
    let (folder, file) = match normalised.iter().rposition(|&b| b == b'/') {
        Some(i) => (&normalised[..i], &normalised[i + 1..]),
        None => (&[][..], normalised),
    };
    let folder_hash = crc32(folder);
    let file_hash = crc32(file);
    (u64::from(folder_hash) << 32) | u64::from(file_hash)
}

/// v2 hash for an already-normalised byte buffer.
///
/// Equivalent to [`hash_index2`] but skips the [`normalize`] allocation — see
/// [`hash_index1_key_normalized`] for the same rationale.
#[must_use]
pub(crate) fn hash_index2_normalized(normalised: &[u8]) -> u32 {
    crc32(normalised)
}

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

    // ----- CRC32 known vectors -----
    //
    // Every value below is the **non-finalized** reflected CRC32 — the form
    // Lumina's `Crc32.Get` and the on-disk `.index` / `.index2` keys use.
    // Cross-checked against Python with `zlib.crc32(x) ^ 0xFFFFFFFF` (the
    // `^ 0xFFFFFFFF` undoes zlib's final XOR, recovering the same convention).

    #[test]
    fn crc32_of_empty_input_is_max() {
        // Empty input → state stays at the 0xFFFF_FFFF init value because no
        // bytes ever advance it through the table. The Lumina/SqPack convention
        // returns that state verbatim.
        assert_eq!(crc32(b""), 0xFFFF_FFFF);
    }

    #[test]
    fn crc32_known_vectors() {
        // Same path fragments used by the path-hash tests below; pre-computed
        // as `~zlib.crc32(x)` (equivalently `zlib.crc32(x) ^ 0xFFFFFFFF`).
        assert_eq!(crc32(b"exd"), 0xE39B_7999);
        assert_eq!(crc32(b"root.exl"), 0x51B5_7EBC);
        assert_eq!(crc32(b"exd/root.exl"), 0x3E16_266C);
        assert_eq!(crc32(b"common"), 0x1A13_8FAE);
        assert_eq!(crc32(b"foo.bin"), 0x7DBE_5FBF);
        assert_eq!(crc32(b"common/foo.bin"), 0x51F0_9F77);
    }

    #[test]
    fn crc32_known_vector_locks_polynomial_and_reflection() {
        // "123456789" is the canonical CRC32 self-test vector; the standard
        // finalised CRC32 of those nine bytes is `0xCBF4_3926`. Under this
        // crate's non-finalised convention the value is its bitwise complement,
        // i.e. `~zlib.crc32("123456789") == 0x340B_C6D9`. Locks in that our
        // polynomial and reflection (table-build + byte loop) match the
        // industry-standard variant; the only deviation from zlib is the
        // missing final XOR.
        assert_eq!(crc32(b"123456789"), 0x340B_C6D9);
    }

    // ----- v1 path hashing -----

    #[test]
    fn hash_index1_splits_on_last_slash() {
        let (folder, file) = hash_index1_path("exd/root.exl");
        assert_eq!(folder, 0xE39B_7999);
        assert_eq!(file, 0x51B5_7EBC);
    }

    #[test]
    fn hash_index1_no_slash_means_empty_folder() {
        let (folder, file) = hash_index1_path("root.exl");
        // Empty folder → CRC32 of zero bytes under the no-final-XOR convention
        // is 0xFFFF_FFFF (the init value, never mutated). NOT 0.
        assert_eq!(folder, 0xFFFF_FFFF);
        assert_eq!(file, 0x51B5_7EBC);
    }

    #[test]
    fn hash_index1_uppercase_normalises() {
        let lower = hash_index1_path("exd/root.exl");
        let upper = hash_index1_path("EXD/Root.EXL");
        assert_eq!(lower, upper);
    }

    #[test]
    fn hash_index1_backslash_normalises() {
        let slash = hash_index1_path("exd/root.exl");
        let backslash = hash_index1_path("exd\\root.exl");
        assert_eq!(slash, backslash);
    }

    #[test]
    fn hash_index1_key_packs_high_low() {
        let key = hash_index1_key("exd/root.exl");
        let (folder, file) = hash_index1_path("exd/root.exl");
        assert_eq!(key, (u64::from(folder) << 32) | u64::from(file));
        assert_eq!(key, 0xE39B_7999_51B5_7EBC);
    }

    #[test]
    fn hash_index1_nested_path_takes_last_slash() {
        // The split is on the LAST slash, so the folder half here is
        // "bg/ex1/wil/wil_w1/level".
        let (folder, file) = hash_index1_path("bg/ex1/wil/wil_w1/level/bg.lgb");
        assert_eq!(folder, crc32(b"bg/ex1/wil/wil_w1/level"));
        assert_eq!(file, crc32(b"bg.lgb"));
    }

    #[test]
    fn hash_index1_empty_path_is_double_ffff_ffff() {
        // Under the no-final-XOR convention, CRC32 of the empty buffer is the
        // initial state 0xFFFF_FFFF. Both halves of the v1 split therefore
        // equal that value, and the composite key equals 0xFFFFFFFF_FFFFFFFF.
        let (folder, file) = hash_index1_path("");
        assert_eq!(folder, 0xFFFF_FFFF);
        assert_eq!(file, 0xFFFF_FFFF);
        assert_eq!(hash_index1_key(""), 0xFFFF_FFFF_FFFF_FFFF);
    }

    // ----- v2 path hashing -----

    #[test]
    fn hash_index2_known_vector() {
        // 0x3E16_266C is the on-disk `.index2` hash key for "exd/root.exl" in
        // every shipping retail FFXIV install — i.e. this assertion locks our
        // crc32 to "matches real game data" rather than "matches my reference
        // implementation".
        assert_eq!(hash_index2("exd/root.exl"), 0x3E16_266C);
    }

    #[test]
    fn hash_index2_normalises_case_and_slashes() {
        let a = hash_index2("exd/root.exl");
        let b = hash_index2("EXD\\Root.EXL");
        assert_eq!(a, b);
    }

    #[test]
    fn hash_index2_empty_is_max() {
        // See crc32_of_empty_input_is_max for the underlying reason.
        assert_eq!(hash_index2(""), 0xFFFF_FFFF);
    }

    #[test]
    fn hash_index2_differs_from_v1_halves() {
        // The v2 key is CRC32 of the full path; the v1 halves are CRC32 of
        // the folder and file pieces. They must not be the same value (the
        // input bytes differ).
        let v2 = hash_index2("exd/root.exl");
        let (folder, file) = hash_index1_path("exd/root.exl");
        assert_ne!(v2, folder);
        assert_ne!(v2, file);
    }

    // ----- normalised helpers (pub(crate) for SqPack::read_file's hot path) -----

    #[test]
    fn normalized_helpers_match_public_entry_points() {
        // The pub(crate) `*_normalized` variants must produce byte-for-byte
        // identical output to the public path-taking versions for the same
        // input string. This locks the two code paths together so the
        // `SqPack::read_file` optimisation (normalise once, hash twice) cannot
        // silently diverge from the public hash functions.
        let inputs = [
            "exd/root.exl",
            "common/foo.bin",
            "EXD\\Root.EXL",
            "bg/ex1/wil/wil_w1/level/bg.lgb",
            "",
            "root.exl",
        ];
        for path in inputs {
            let normalised = normalize(path);
            assert_eq!(
                hash_index1_key_normalized(&normalised),
                hash_index1_key(path),
                "v1 mismatch for {path:?}",
            );
            assert_eq!(
                hash_index2_normalized(&normalised),
                hash_index2(path),
                "v2 mismatch for {path:?}",
            );
        }
    }

    // ----- normalize helper -----

    #[test]
    fn normalize_lowercases_ascii_and_swaps_slashes() {
        assert_eq!(normalize("EXD\\Root.EXL"), b"exd/root.exl");
    }

    #[test]
    fn normalize_passes_through_non_ascii_unchanged() {
        // Non-ASCII bytes are not case-folded; they survive normalisation
        // verbatim. (Real game paths are ASCII; this just locks the
        // behaviour down so a future surprise non-ASCII byte does not
        // silently change the hash.)
        let n = normalize("Café/Foo");
        // ASCII letters lowercase; the é (0xC3 0xA9) stays exactly as-is.
        assert_eq!(n, b"caf\xc3\xa9/foo");
    }

    // ----- normalize edge cases -----

    #[test]
    fn normalize_consecutive_slashes_are_preserved() {
        // normalize does no path canonicalisation — consecutive slashes pass
        // through as-is. The hash of "exd//root.exl" differs from "exd/root.exl".
        let n = normalize("exd//root.exl");
        assert_eq!(n, b"exd//root.exl");
        // The v2 hash of the double-slash form differs from the clean form.
        assert_ne!(crc32(b"exd//root.exl"), crc32(b"exd/root.exl"));
    }

    #[test]
    fn normalize_trailing_slash_pins_behaviour() {
        // "exd/" normalises to b"exd/" verbatim. The v1 split puts "exd" in the
        // folder half and the empty slice in the file half. The file half of an
        // empty slice is CRC32([]) = 0xFFFF_FFFF.
        let (folder, file) = hash_index1_path("exd/");
        // folder half = CRC32("exd") — same as a path that has something after
        // the slash.
        assert_eq!(folder, 0xE39B_7999, "folder half of trailing-slash path");
        // file half = CRC32("") = 0xFFFF_FFFF (empty-input init value, no final XOR).
        assert_eq!(
            file, 0xFFFF_FFFF,
            "file half of trailing-slash path is empty-CRC32"
        );
        // Full v2 hash of "exd/" differs from v2 hash of "exd/root.exl".
        assert_ne!(hash_index2("exd/"), hash_index2("exd/root.exl"));
    }

    #[test]
    fn normalize_leading_slash_is_preserved() {
        // A leading slash is not stripped; it becomes the folder-half boundary.
        let n = normalize("/exd/foo.bin");
        assert_eq!(n, b"/exd/foo.bin");
        let (folder, file) = hash_index1_path("/exd/foo.bin");
        // Split on the last slash: folder = "/exd", file = "foo.bin".
        assert_eq!(folder, crc32(b"/exd"));
        assert_eq!(file, crc32(b"foo.bin"));
    }

    #[test]
    fn normalize_mixed_backslash_and_slash() {
        // Mixed separators: both should become '/'.
        let n = normalize("exd\\sub/file.bin");
        assert_eq!(n, b"exd/sub/file.bin");
    }

    // ----- CRC32 additional Lumina cross-vectors -----
    //
    // Computed via `python3 -c "import zlib; print(hex(zlib.crc32(b'...') ^ 0xFFFFFFFF))"`.
    // These are real-world-shaped FFXIV paths; the short vectors above test the
    // algorithm correctness but do not exercise multi-level directory prefixes.

    #[test]
    fn crc32_chara_monster_material_path() {
        // Full path v2 vector.
        assert_eq!(
            crc32(b"chara/monster/m0001/obj/body/b0001/material/mt_m0001b0001_a.mtrl"),
            0x0DAE_F02C
        );
        // Folder / file halves for v1.
        assert_eq!(
            crc32(b"chara/monster/m0001/obj/body/b0001/material"),
            0x6E31_6251
        );
        assert_eq!(crc32(b"mt_m0001b0001_a.mtrl"), 0xFF8E_7325);
    }

    #[test]
    fn crc32_bg_ex1_level_path() {
        // Multi-expansion bg path.
        assert_eq!(
            crc32(b"bg/ex1/wil/wil_w1/twn/w1t1/level/bg.lgb"),
            0xB954_67BE
        );
        assert_eq!(crc32(b"bg/ex1/wil/wil_w1/twn/w1t1/level"), 0x36FA_D775);
        assert_eq!(crc32(b"bg.lgb"), 0xA833_4C0D);
    }

    #[test]
    fn crc32_ui_icon_path() {
        // UI icon with zero-padded folder.
        assert_eq!(crc32(b"ui/icon/000000/000001.tex"), 0x18B2_AD40);
        assert_eq!(crc32(b"ui/icon/000000"), 0x45C8_C92D);
        assert_eq!(crc32(b"000001.tex"), 0xBA63_CBBA);
    }

    // ----- crc32 determinism -----

    #[test]
    fn crc32_is_deterministic_across_calls() {
        // Calling crc32 repeatedly on the same input must always produce the
        // same value. Guards against accidental mutable global state.
        let expected = crc32(b"exd/root.exl");
        for _ in 0..999 {
            assert_eq!(
                crc32(b"exd/root.exl"),
                expected,
                "crc32 returned a different value on a repeated call"
            );
        }
    }

    // ----- normalize idempotency -----

    #[test]
    fn normalize_is_idempotent() {
        // normalize(normalize(s)) == normalize(s) for all inputs. Because the
        // output is already lowercase ASCII with only forward slashes, running it
        // again must produce the identical byte sequence.
        let inputs = [
            "exd/root.exl",
            "EXD\\Root.EXL",
            "bg/ex1/wil/wil_w1/level/bg.lgb",
            "",
            "exd/",
        ];
        for s in inputs {
            let once = normalize(s);
            // Reinterpret as str — all bytes are ASCII after normalize.
            let once_str = std::str::from_utf8(&once).unwrap();
            let twice = normalize(once_str);
            assert_eq!(once, twice, "normalize is not idempotent for {s:?}");
        }
    }

    // ----- cross-layer consistency: v1+v2 use the same normalisation -----

    #[test]
    fn v1_and_v2_use_same_normalisation_for_unusual_paths() {
        // For any input, the v1 key and v2 key must be derived from the same
        // normalised byte sequence. Verify by running both on identical inputs
        // and confirming the normalised form used by the pub(crate) helpers
        // (which share one allocation) matches the public-entry-point versions
        // (which normalise internally).
        let inputs = ["EXD\\Root.EXL", "BG/EX1/Foo.lgb", "exd/", "exd//root.exl"];
        for path in inputs {
            let normalised = normalize(path);
            let v1_via_norm = hash_index1_key_normalized(&normalised);
            let v2_via_norm = hash_index2_normalized(&normalised);
            let v1_via_str = hash_index1_key(path);
            let v2_via_str = hash_index2(path);
            assert_eq!(v1_via_norm, v1_via_str, "v1 mismatch for {path:?}");
            assert_eq!(v2_via_norm, v2_via_str, "v2 mismatch for {path:?}");
        }
    }
}
