/**
 * Authenticating space reads made with a credential.
 *
 * Each read asks for a MAC with `Atproto-Space-Want-Mac`, carrying a fresh
 * P-256 key share. The repo host derives the same secret from the share and
 * the author's `#atproto_kem` key, DHKEM(P-256, HKDF-SHA256) as RFC 9180
 * §4.1 specifies, and returns the MAC of the response in `Atproto-Space-Mac`.
 * A record read is good when the MAC covers its uri and cid and its value
 * encodes to that cid.
 *
 * Self-contained on WebCrypto, like space-signature.js, because this package
 * installs as a global CLI and keeps its dependency list empty.
 */

import { base58btc, compressedP256 } from './space-signature.js';

export const RECORD_MAC_TYPE = 'atproto-space-record';
export const WANT_MAC_HEADER = 'Atproto-Space-Want-Mac';
export const MAC_HEADER = 'Atproto-Space-Mac';
const MAC_VERSION = 1;

const P256_P =
  0xffffffff00000001000000000000000000000000ffffffffffffffffffffffffn;
const P256_B =
  0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604bn;
const B58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';
const B32 = 'abcdefghijklmnopqrstuvwxyz234567';

const encoder = new TextEncoder();

/** @param {...Uint8Array} parts */
function concat(...parts) {
  let size = 0;
  for (const part of parts) size += part.length;
  const out = new Uint8Array(size);
  let offset = 0;
  for (const part of parts) {
    out.set(part, offset);
    offset += part.length;
  }
  return out;
}

/** @param {number} n */
function uint16be(n) {
  return new Uint8Array([(n >> 8) & 0xff, n & 0xff]);
}

// "HPKE-v1" || "KEM" || 0x0010, the suite id of DHKEM(P-256, HKDF-SHA256).
const KEM_PREFIX = concat(
  encoder.encode('HPKE-v1'),
  encoder.encode('KEM'),
  uint16be(0x0010),
);

/**
 * @param {Uint8Array} key
 * @param {Uint8Array} data
 * @returns {Promise<Uint8Array>}
 */
async function hmacSha256(key, data) {
  const cryptoKey = await crypto.subtle.importKey(
    'raw',
    /** @type {BufferSource} */ (key),
    { name: 'HMAC', hash: 'SHA-256' },
    false,
    ['sign'],
  );
  return new Uint8Array(
    await crypto.subtle.sign(
      'HMAC',
      cryptoKey,
      /** @type {BufferSource} */ (data),
    ),
  );
}

/**
 * @param {string} text
 * @returns {Uint8Array}
 */
function base58Decode(text) {
  const bytes = [0];
  for (const char of text) {
    const value = B58.indexOf(char);
    if (value === -1) throw new Error('invalid base58');
    let carry = value;
    for (let i = 0; i < bytes.length; i++) {
      carry += bytes[i] * 58;
      bytes[i] = carry & 0xff;
      carry >>= 8;
    }
    while (carry) {
      bytes.push(carry & 0xff);
      carry >>= 8;
    }
  }
  for (const char of text) {
    if (char !== '1') break;
    bytes.push(0);
  }
  return new Uint8Array(bytes.reverse());
}

/** @param {bigint} n */
function mod(n) {
  const r = n % P256_P;
  return r < 0n ? r + P256_P : r;
}

/**
 * @param {bigint} base
 * @param {bigint} exp
 */
function modPow(base, exp) {
  let result = 1n;
  let b = mod(base);
  let e = exp;
  while (e > 0n) {
    if (e & 1n) result = mod(result * b);
    b = mod(b * b);
    e >>= 1n;
  }
  return result;
}

/**
 * The uncompressed point (0x04 || x || y) a P-256 did:key names.
 * @param {string} didKey
 * @returns {Uint8Array}
 */
export function p256PointFromDidKey(didKey) {
  if (!didKey.startsWith('did:key:z')) throw new Error('invalid KEM key');
  const bytes = base58Decode(didKey.slice('did:key:z'.length));
  if (
    bytes.length !== 35 ||
    bytes[0] !== 0x80 ||
    bytes[1] !== 0x24 ||
    (bytes[2] !== 0x02 && bytes[2] !== 0x03)
  ) {
    throw new Error('KEM key must be a P-256 did:key');
  }
  let x = 0n;
  for (const b of bytes.subarray(3)) x = (x << 8n) | BigInt(b);
  if (x >= P256_P) throw new Error('invalid KEM key');
  // y² = x³ - 3x + b, and p ≡ 3 (mod 4), so y = rhs^((p + 1) / 4).
  const rhs = mod(x ** 3n - 3n * x + P256_B);
  let y = modPow(rhs, (P256_P + 1n) / 4n);
  if (mod(y * y) !== rhs) throw new Error('invalid KEM key');
  if (Number(y & 1n) !== (bytes[2] & 1)) y = P256_P - y;
  const out = new Uint8Array(65);
  out[0] = 0x04;
  out.set(bytes.subarray(3), 1);
  for (let i = 64; i >= 33; i--) {
    out[i] = Number(y & 0xffn);
    y >>= 8n;
  }
  return out;
}

/**
 * A fresh key share against the author's KEM key, and the secret it shares
 * with them. One per request.
 * @param {string} authorKemKey - the author's `#atproto_kem` did:key
 * @returns {Promise<{keyShare: string, sharedSecret: Uint8Array}>}
 */
export async function encapsulate(authorKemKey) {
  const authorPoint = p256PointFromDidKey(authorKemKey);
  const authorKey = await crypto.subtle.importKey(
    'raw',
    /** @type {BufferSource} */ (authorPoint),
    { name: 'ECDH', namedCurve: 'P-256' },
    false,
    [],
  );
  const ephemeral = /** @type {CryptoKeyPair} */ (
    await crypto.subtle.generateKey(
      { name: 'ECDH', namedCurve: 'P-256' },
      false,
      ['deriveBits'],
    )
  );
  const syncerPoint = new Uint8Array(
    await crypto.subtle.exportKey('raw', ephemeral.publicKey),
  );
  const dh = new Uint8Array(
    await crypto.subtle.deriveBits(
      { name: 'ECDH', public: authorKey },
      ephemeral.privateKey,
      256,
    ),
  );
  // HKDF-SHA256: extract under an empty salt (HashLen zero bytes), then one
  // expand block, since the secret is exactly one hash long.
  const prk = await hmacSha256(
    new Uint8Array(32),
    concat(KEM_PREFIX, encoder.encode('eae_prk'), dh),
  );
  const info = concat(
    uint16be(32),
    KEM_PREFIX,
    encoder.encode('shared_secret'),
    syncerPoint,
    authorPoint,
  );
  const sharedSecret = await hmacSha256(prk, concat(info, new Uint8Array([1])));
  return {
    keyShare: `did:key:z${base58btc(new Uint8Array([0x80, 0x24, ...compressedP256(syncerPoint)]))}`,
    sharedSecret,
  };
}

/**
 * `type="atproto-space-record", ver=1, key_share="did:key:zDn..."`
 * @param {string} type
 * @param {string} keyShare
 * @returns {string}
 */
export function formatWantMacHeader(type, keyShare) {
  return `type="${type}", ver=${MAC_VERSION}, key_share="${keyShare}"`;
}

/**
 * The MAC an `Atproto-Space-Mac` header carries, checked for its type and
 * version. Its members are a quoted string, an integer and a byte sequence,
 * none of which holds a comma.
 * @param {string|null} value
 * @param {string} type
 * @returns {Uint8Array}
 */
export function parseMacHeader(value, type) {
  if (!value) throw new Error('response carries no MAC');
  /** @type {Map<string, string>} */
  const fields = new Map();
  for (const member of value.split(',')) {
    const match = /^\s*([a-z_][a-z0-9_.*-]*)=(.*?)\s*$/.exec(member);
    if (!match) throw new Error('malformed MAC header');
    fields.set(match[1], match[2]);
  }
  if (fields.get('type') !== `"${type}"`) {
    throw new Error(`MAC header is not of type ${type}`);
  }
  if (fields.get('ver') !== String(MAC_VERSION)) {
    throw new Error('unsupported MAC version');
  }
  const mac = /^:([A-Za-z0-9+/]*={0,2}):$/.exec(fields.get('mac') ?? '');
  if (!mac) throw new Error('malformed MAC');
  return Uint8Array.from(atob(mac[1]), (c) => c.charCodeAt(0));
}

/**
 * The binary form of a base32 CID string.
 * @param {string} cid
 * @returns {Uint8Array}
 */
function cidBytes(cid) {
  if (!cid.startsWith('b')) throw new Error('unsupported CID encoding');
  const out = [];
  let bits = 0;
  let value = 0;
  for (const char of cid.slice(1)) {
    const index = B32.indexOf(char);
    if (index === -1) throw new Error('invalid CID');
    value = (value << 5) | index;
    bits += 5;
    if (bits >= 8) {
      out.push((value >> (bits - 8)) & 0xff);
      bits -= 8;
    }
  }
  return new Uint8Array(out);
}

/**
 * @param {Uint8Array} bytes
 * @returns {string}
 */
function base32(bytes) {
  let out = 'b';
  let bits = 0;
  let value = 0;
  for (const byte of bytes) {
    value = (value << 8) | byte;
    bits += 8;
    while (bits >= 5) {
      out += B32[(value >> (bits - 5)) & 31];
      bits -= 5;
    }
  }
  if (bits > 0) out += B32[(value << (5 - bits)) & 31];
  return out;
}

/**
 * @param {number} major
 * @param {number} n
 * @returns {number[]}
 */
function cborHead(major, n) {
  const m = major << 5;
  if (n < 24) return [m | n];
  if (n < 0x100) return [m | 24, n];
  if (n < 0x10000) return [m | 25, n >> 8, n & 0xff];
  if (n < 0x100000000) {
    return [
      m | 26,
      (n >>> 24) & 0xff,
      (n >> 16) & 0xff,
      (n >> 8) & 0xff,
      n & 0xff,
    ];
  }
  const hi = Math.floor(n / 0x100000000);
  const lo = n % 0x100000000;
  return [
    m | 27,
    (hi >>> 24) & 0xff,
    (hi >> 16) & 0xff,
    (hi >> 8) & 0xff,
    hi & 0xff,
    (lo >>> 24) & 0xff,
    (lo >> 16) & 0xff,
    (lo >> 8) & 0xff,
    lo & 0xff,
  ];
}

/**
 * DAG-CBOR encoding of a record as JSON carries it, with `$link` and `$bytes`
 * objects standing for links and byte strings.
 * @param {unknown} value
 * @param {number[]} out
 */
function encodeDagCbor(value, out) {
  if (value === null) {
    out.push(0xf6);
  } else if (value === true || value === false) {
    out.push(value ? 0xf5 : 0xf4);
  } else if (typeof value === 'number') {
    if (!Number.isSafeInteger(value)) {
      throw new Error('a record holds a number that is not an integer');
    }
    if (value >= 0) out.push(...cborHead(0, value));
    else out.push(...cborHead(1, -1 - value));
  } else if (typeof value === 'string') {
    const bytes = encoder.encode(value);
    out.push(...cborHead(3, bytes.length), ...bytes);
  } else if (Array.isArray(value)) {
    out.push(...cborHead(4, value.length));
    for (const item of value) encodeDagCbor(item, out);
  } else if (typeof value === 'object') {
    const obj = /** @type {Record<string, unknown>} */ (value);
    const keys = Object.keys(obj).filter((k) => obj[k] !== undefined);
    if (
      keys.length === 1 &&
      keys[0] === '$link' &&
      typeof obj.$link === 'string'
    ) {
      const bytes = concat(new Uint8Array([0]), cidBytes(obj.$link));
      out.push(0xd8, 42, ...cborHead(2, bytes.length), ...bytes);
      return;
    }
    if (
      keys.length === 1 &&
      keys[0] === '$bytes' &&
      typeof obj.$bytes === 'string'
    ) {
      const b64 = obj.$bytes.replace(/-/g, '+').replace(/_/g, '/');
      const bytes = Uint8Array.from(
        atob(b64.padEnd(Math.ceil(b64.length / 4) * 4, '=')),
        (c) => c.charCodeAt(0),
      );
      out.push(...cborHead(2, bytes.length), ...bytes);
      return;
    }
    // Keys in DAG-CBOR order: shorter first, then bytewise.
    const encoded = keys.map((k) => ({ k, bytes: encoder.encode(k) }));
    encoded.sort((a, b) => {
      if (a.bytes.length !== b.bytes.length)
        return a.bytes.length - b.bytes.length;
      for (let i = 0; i < a.bytes.length; i++) {
        if (a.bytes[i] !== b.bytes[i]) return a.bytes[i] - b.bytes[i];
      }
      return 0;
    });
    out.push(...cborHead(5, encoded.length));
    for (const { k, bytes } of encoded) {
      out.push(...cborHead(3, bytes.length), ...bytes);
      encodeDagCbor(obj[k], out);
    }
  } else {
    throw new Error(`a record holds an unencodable ${typeof value}`);
  }
}

/**
 * The CID (v1, dag-cbor, sha-256) of a record value.
 * @param {unknown} value
 * @returns {Promise<string>}
 */
export async function recordCid(value) {
  /** @type {number[]} */
  const out = [];
  encodeDagCbor(value, out);
  const digest = new Uint8Array(
    await crypto.subtle.digest('SHA-256', new Uint8Array(out)),
  );
  return base32(concat(new Uint8Array([0x01, 0x71, 0x12, 0x20]), digest));
}

/**
 * Whether a getRecord response is the record that was asked for, under a MAC
 * from the author's key: the MAC covers its uri and cid, and its value
 * encodes to that cid.
 * @param {{uri: string, cid: string, value: unknown}} record
 * @param {{uri: string, sharedSecret: Uint8Array, mac: Uint8Array}} params
 * @returns {Promise<boolean>}
 */
export async function verifyRecord(record, params) {
  if (record.uri !== params.uri) return false;
  try {
    const uri = encoder.encode(record.uri);
    const expected = await hmacSha256(
      params.sharedSecret,
      concat(
        encoder.encode(`${RECORD_MAC_TYPE}-v${MAC_VERSION}`),
        uint16be(uri.length),
        uri,
        cidBytes(record.cid),
      ),
    );
    if (expected.length !== params.mac.length) return false;
    let diff = 0;
    for (let i = 0; i < expected.length; i++)
      diff |= expected[i] ^ params.mac[i];
    if (diff !== 0) return false;
    return (await recordCid(record.value)) === record.cid;
  } catch {
    return false;
  }
}