Blame for lib/formats.js

// File formats for "Open your own", all decoded in the browser: OBJ and PLY meshes with UVs,
// baseline TIFF images, and zip archives (read and write). No dependencies.

// ------------------------------------------------------------ meshes
// Both parsers return { pos: Float32Array (xyz), uv: Float32Array (uv), index: Uint32Array, vertices, faces }.
// A vertex is a unique (position, uv) pair; polygons are fanned into triangles.

export function parseOBJ(text) {
  const P = [], T = [], key = new Map(), pos = [], uv = [], idx = [];
  let line = 0;
  const vert = (tok) => {
    const k = tok;
    let v = key.get(k);
    if (v !== undefined) return v;
    const [a, b] = tok.split('/');
    let pi = parseInt(a, 10), ti = parseInt(b, 10);
    if (!Number.isFinite(pi)) throw new Error(`OBJ line ${line}: bad face vertex "${tok}"`);
    if (!Number.isFinite(ti)) throw new Error(`OBJ line ${line}: face vertex "${tok}" has no texture coordinate. Every face needs v/vt indices (UVs).`);
    pi = pi < 0 ? P.length / 3 + pi : pi - 1;
    ti = ti < 0 ? T.length / 2 + ti : ti - 1;
    if (pi < 0 || pi * 3 >= P.length) throw new Error(`OBJ line ${line}: vertex index out of range`);
    if (ti < 0 || ti * 2 >= T.length) throw new Error(`OBJ line ${line}: texture index out of range`);
    v = pos.length / 3;
    pos.push(P[pi * 3], P[pi * 3 + 1], P[pi * 3 + 2]);
    uv.push(T[ti * 2], T[ti * 2 + 1]);
    key.set(k, v);
    return v;
  };
  let i0 = 0;
  while (i0 < text.length) {
    let i1 = text.indexOf('\n', i0);
    if (i1 < 0) i1 = text.length;
    const s = text.slice(i0, i1).trim();
    i0 = i1 + 1; line++;
    if (!s || s[0] === '#') continue;
    const t = s.split(/\s+/);
    if (t[0] === 'v') P.push(+t[1], +t[2], +t[3]);
    else if (t[0] === 'vt') T.push(+t[1], +(t[2] ?? 0));
    else if (t[0] === 'f') {
      const f = t.slice(1).map(vert);
      for (let k = 1; k + 1 < f.length; k++) idx.push(f[0], f[k], f[k + 1]);
    }
  }
  if (!P.length) throw new Error('OBJ has no vertices ("v" lines).');
  if (!T.length) throw new Error('OBJ has no texture coordinates ("vt" lines). The mesh needs UVs to place the image layers.');
  if (!idx.length) throw new Error('OBJ has no faces ("f" lines).');
  return finish(pos, uv, idx);
}

function finish(pos, uv, idx) {
  const out = { pos: Float32Array.from(pos), uv: Float32Array.from(uv), index: Uint32Array.from(idx) };
  out.vertices = out.pos.length / 3; out.faces = out.index.length / 3;
  for (let i = 0; i < out.pos.length; i++) if (!Number.isFinite(out.pos[i])) throw new Error('The mesh has a vertex with a non-numeric coordinate.');
  for (let i = 0; i < out.uv.length; i++) if (!Number.isFinite(out.uv[i])) throw new Error('The mesh has a non-numeric texture coordinate.');
  return out;
}

const PLY_TYPES = {
  char: ['getInt8', 1], int8: ['getInt8', 1], uchar: ['getUint8', 1], uint8: ['getUint8', 1],
  short: ['getInt16', 2], int16: ['getInt16', 2], ushort: ['getUint16', 2], uint16: ['getUint16', 2],
  int: ['getInt32', 4], int32: ['getInt32', 4], uint: ['getUint32', 4], uint32: ['getUint32', 4],
  float: ['getFloat32', 4], float32: ['getFloat32', 4], double: ['getFloat64', 8], float64: ['getFloat64', 8],
};

export function parsePLY(buf) {
  const u8 = new Uint8Array(buf);
  const head = new TextDecoder().decode(u8.subarray(0, Math.min(u8.length, 8192)));
  const end = head.indexOf('end_header');
  if (!head.startsWith('ply') || end < 0) throw new Error('Not a PLY file (no "ply" header).');
  const hlen = head.indexOf('\n', end) + 1;
  const lines = head.slice(0, hlen).split(/\r?\n/).map((s) => s.trim()).filter(Boolean);
  let fmt = null; const els = [];
  for (const l of lines) {
    const t = l.split(/\s+/);
    if (t[0] === 'format') fmt = t[1];
    else if (t[0] === 'element') els.push({ name: t[1], n: +t[2], props: [] });
    else if (t[0] === 'property') {
      const e = els[els.length - 1];
      if (t[1] === 'list') e.props.push({ list: true, ct: t[2], it: t[3], name: t[4] });
      else e.props.push({ type: t[1], name: t[2] });
    }
  }
  if (!['ascii', 'binary_little_endian', 'binary_big_endian'].includes(fmt)) throw new Error(`PLY format "${fmt}" is not supported.`);
  const V = els.find((e) => e.name === 'vertex');
  if (!V) throw new Error('PLY has no vertex element.');
  const pn = V.props.map((p) => p.name);
  const uName = ['u', 's', 'texture_u', 'texture_s'].find((n) => pn.includes(n));
  const vName = ['v', 't', 'texture_v', 'texture_t'].find((n) => pn.includes(n));
  if (!uName || !vName) throw new Error('PLY vertices have no texture coordinates (u, v or s, t). The mesh needs UVs to place the image layers.');
  const pos = new Float32Array(V.n * 3), uv = new Float32Array(V.n * 2), idx = [];
  const store = (e, i, rec) => {
    if (e === V) {
      pos[i * 3] = rec.x; pos[i * 3 + 1] = rec.y; pos[i * 3 + 2] = rec.z;
      uv[i * 2] = rec[uName]; uv[i * 2 + 1] = rec[vName];
    } else if (e.name === 'face') {
      const f = rec.vertex_indices || rec.vertex_index;
      if (!f) throw new Error('PLY faces have no vertex_indices list.');
      for (let k = 1; k + 1 < f.length; k++) idx.push(f[0], f[k], f[k + 1]);
    }
  };
  if (fmt === 'ascii') {
    const body = new TextDecoder().decode(u8.subarray(hlen)).split(/\s+/).filter(Boolean);
    let p = 0;
    for (const e of els) for (let i = 0; i < e.n; i++) {
      const rec = {};
      for (const pr of e.props) {
        if (pr.list) { const n = +body[p++]; rec[pr.name] = body.slice(p, p + n).map(Number); p += n; }
        else rec[pr.name] = +body[p++];
      }
      store(e, i, rec);
    }
  } else {
    const dv = new DataView(buf, 0), le = fmt === 'binary_little_endian';
    let o = hlen;
    const rd = (type) => { const [fn, n] = PLY_TYPES[type] || []; if (!fn) throw new Error(`PLY type "${type}" is not supported.`); const v = dv[fn](o, le); o += n; return v; };
    for (const e of els) for (let i = 0; i < e.n; i++) {
      const rec = {};
      for (const pr of e.props) {
        if (pr.list) { const n = rd(pr.ct); const a = new Array(n); for (let k = 0; k < n; k++) a[k] = rd(pr.it); rec[pr.name] = a; }
        else rec[pr.name] = rd(pr.type);
      }
      if (o > buf.byteLength) throw new Error('PLY file ends early.');
      store(e, i, rec);
    }
  }
  for (const k of idx) if (k >= V.n) throw new Error('PLY face index out of range.');
  if (!idx.length) throw new Error('PLY has no faces.');
  return finish(pos, uv, idx);
}

// ------------------------------------------------------------ TIFF
// Baseline TIFF: 8, 16 or 32 bit (int or float), 1 to 4 samples, strips or tiles,
// no compression, LZW, Deflate or PackBits, horizontal predictor. Returns ImageData (RGBA, 8 bit).

export async function decodeTIFF(buf, maxSide = 8192) {
  const dv = new DataView(buf);
  const bo = dv.getUint16(0);
  if (bo !== 0x4949 && bo !== 0x4d4d) throw new Error('Not a TIFF file.');
  const le = bo === 0x4949;
  if (dv.getUint16(2, le) === 43) throw new Error('BigTIFF is not supported; save as a standard TIFF or PNG.');
  const ifd = dv.getUint32(4, le);
  const n = dv.getUint16(ifd, le);
  const tags = {};
  const SZ = { 1: 1, 2: 1, 3: 2, 4: 4, 5: 8, 6: 1, 7: 1, 8: 2, 9: 4, 10: 8, 11: 4, 12: 8, 16: 8 };
  for (let i = 0; i < n; i++) {
    const e = ifd + 2 + i * 12;
    const tag = dv.getUint16(e, le), type = dv.getUint16(e + 2, le), cnt = dv.getUint32(e + 4, le);
    const size = (SZ[type] || 1) * cnt;
    const off = size <= 4 ? e + 8 : dv.getUint32(e + 8, le);
    const vals = [];
    for (let k = 0; k < Math.min(cnt, 1 << 20); k++) {
      if (type === 3) vals.push(dv.getUint16(off + k * 2, le));
      else if (type === 4) vals.push(dv.getUint32(off + k * 4, le));
      else if (type === 1 || type === 7) vals.push(dv.getUint8(off + k));
      else if (type === 16) vals.push(Number(dv.getBigUint64(off + k * 8, le)));
      else break;
    }
    tags[tag] = vals;
  }
  const W = tags[256]?.[0], H = tags[257]?.[0];
  if (!W || !H) throw new Error('TIFF has no width or height.');
  if (W > maxSide || H > maxSide) throw new Error(`TIFF is ${W} x ${H} px; the limit is ${maxSide} px on a side.`);
  const bps = tags[258]?.[0] || 1, spp = tags[277]?.[0] || 1, comp = tags[259]?.[0] || 1;
  const pred = tags[317]?.[0] || 1, fmt = tags[339]?.[0] || 1, photo = tags[262]?.[0] ?? 1;
  if (![8, 16, 32].includes(bps)) throw new Error(`TIFF with ${bps} bits per sample is not supported (use 8, 16 or 32).`);
  if ((tags[284]?.[0] || 1) !== 1 && spp > 1) throw new Error('Planar TIFF is not supported.');
  if (photo === 3) throw new Error('Palette TIFF is not supported.');
  const tiled = !!tags[322];
  const tw = tiled ? tags[322][0] : W, th = tiled ? tags[323][0] : (tags[278]?.[0] || H);
  const offs = tiled ? tags[324] : tags[273], cnts = tiled ? tags[325] : tags[279];
  if (!offs || !cnts) throw new Error('TIFF has no image data offsets.');
  const B = bps / 8, rowB = tw * spp * B;
  const raw = new Uint8Array(W * H * spp * B);
  const across = Math.ceil(W / tw);
  for (let c = 0; c < offs.length; c++) {
    let chunk = new Uint8Array(buf, offs[c], cnts[c]);
    if (comp === 5) chunk = lzw(chunk, rowB * th);
    else if (comp === 8 || comp === 32946) chunk = await inflate(chunk, 'deflate');
    else if (comp === 32773) chunk = packbits(chunk, rowB * th);
    else if (comp !== 1) throw new Error(`TIFF compression ${comp} is not supported (use none, LZW or Deflate).`);
    const x0 = tiled ? (c % across) * tw : 0, y0 = tiled ? Math.floor(c / across) * th : c * th;
    for (let y = 0; y < th && y0 + y < H; y++) {
      const row = chunk.subarray(y * rowB, (y + 1) * rowB);
      if (pred === 2) {
        if (B === 1) for (let i = spp; i < row.length; i++) row[i] = (row[i] + row[i - spp]) & 255;
        else if (B === 2) { const d = new DataView(row.buffer, row.byteOffset, row.length); for (let i = spp; i < tw * spp; i++) d.setUint16(i * 2, (d.getUint16(i * 2, le) + d.getUint16((i - spp) * 2, le)) & 65535, le); }
      }
      const w = Math.min(tw, W - x0) * spp * B;
      raw.set(row.subarray(0, w), ((y0 + y) * W + x0) * spp * B);
    }
  }
  // to 8-bit RGBA, stretching 16- and 32-bit data to the range it actually uses
  const N = W * H, d = new DataView(raw.buffer);
  const get = B === 1 ? (i) => raw[i] : B === 2 ? (i) => d.getUint16(i * 2, le)
    : fmt === 3 ? (i) => d.getFloat32(i * 4, le) : (i) => d.getUint32(i * 4, le);
  let lo = 0, hi = 255;
  if (B > 1) {
    lo = Infinity; hi = -Infinity;
    for (let i = 0; i < N * spp; i += Math.max(1, Math.floor(N * spp / 200000))) { const v = get(i); if (Number.isFinite(v)) { if (v < lo) lo = v; if (v > hi) hi = v; } }
    if (!(hi > lo)) { lo = 0; hi = 1; }
  }
  const k = 255 / (hi - lo);
  const out = new Uint8ClampedArray(N * 4);
  for (let p = 0; p < N; p++) {
    const s = p * spp;
    const r = (get(s) - lo) * k;
    const g = spp >= 3 ? (get(s + 1) - lo) * k : r, b = spp >= 3 ? (get(s + 2) - lo) * k : r;
    const a = spp === 4 ? (get(s + 3) - lo) * k : spp === 2 ? (get(s + 1) - lo) * k : 255;
    const inv = photo === 0 ? 255 : 0;
    out[p * 4] = Math.abs(inv - r); out[p * 4 + 1] = Math.abs(inv - g); out[p * 4 + 2] = Math.abs(inv - b); out[p * 4 + 3] = a;
  }
  return new ImageData(out, W, H);
}

function lzw(src, expect) {
  const out = new Uint8Array(Math.max(expect, 16));
  let o = 0, bit = 0, size = 9;
  let dict = [];
  const reset = () => { dict = []; for (let i = 0; i < 256; i++) dict.push([i]); dict.push(null, null); size = 9; };
  const read = () => {
    let v = 0;
    for (let i = 0; i < size; i++) { const B = src[(bit + i) >> 3]; v = (v << 1) | ((B >> (7 - ((bit + i) & 7))) & 1); }
    bit += size; return v;
  };
  reset();
  let prev = null;
  while ((bit + size) <= src.length * 8) {
    const c = read();
    if (c === 257) break;
    if (c === 256) { reset(); prev = null; continue; }
    let e;
    if (c < dict.length && dict[c]) e = dict[c];
    else if (prev) e = prev.concat(prev[0]);
    else throw new Error('Damaged LZW data in TIFF.');
    for (const x of e) { if (o < out.length) out[o++] = x; }
    if (prev) dict.push(prev.concat(e[0]));
    prev = e;
    if (dict.length + 1 >= (1 << size) && size < 12) size++;
  }
  return out;
}

function packbits(src, expect) {
  const out = new Uint8Array(expect); let o = 0, i = 0;
  while (i < src.length && o < expect) {
    const n = (src[i++] << 24) >> 24;
    if (n >= 0) { for (let k = 0; k <= n; k++) out[o++] = src[i++]; }
    else if (n !== -128) { const v = src[i++]; for (let k = 0; k < 1 - n; k++) out[o++] = v; }
  }
  return out;
}

async function inflate(bytes, fmt) {
  const ds = new DecompressionStream(fmt);
  const r = new Response(new Blob([bytes]).stream().pipeThrough(ds));
  return new Uint8Array(await r.arrayBuffer());
}

// ------------------------------------------------------------ zip

export async function readZip(buf, limits) {
  const u8 = new Uint8Array(buf), dv = new DataView(buf);
  let eocd = -1;
  for (let i = u8.length - 22; i >= Math.max(0, u8.length - 65557); i--) if (dv.getUint32(i, true) === 0x06054b50) { eocd = i; break; }
  if (eocd < 0) throw new Error('This is not a zip file, or it is damaged.');
  const count = dv.getUint16(eocd + 10, true);
  let p = dv.getUint32(eocd + 16, true);
  const files = [];
  let total = 0;
  for (let n = 0; n < count; n++) {
    if (dv.getUint32(p, true) !== 0x02014b50) throw new Error('Damaged zip directory.');
    const method = dv.getUint16(p + 10, true), csize = dv.getUint32(p + 20, true), usize = dv.getUint32(p + 24, true);
    const nl = dv.getUint16(p + 28, true), xl = dv.getUint16(p + 30, true), cl = dv.getUint16(p + 32, true);
    const flags = dv.getUint16(p + 8, true);
    const lho = dv.getUint32(p + 42, true);
    const name = new TextDecoder().decode(u8.subarray(p + 46, p + 46 + nl));
    p += 46 + nl + xl + cl;
    if (name.endsWith('/')) continue;
    if (flags & 1) throw new Error(`${name} in the zip is encrypted.`);
    if (usize === 0xffffffff || csize === 0xffffffff) throw new Error('Zip64 archives are not supported.');
    if (limits && usize > limits.maxFileBytes) throw new Error(`${name} is ${(usize / 1e6).toFixed(1)} MB unzipped; the limit per file is ${(limits.maxFileBytes / 1048576).toFixed(0)} MB.`);
    total += usize;
    if (limits && total > limits.maxTotalBytes) throw new Error(`The zip unpacks to more than ${(limits.maxTotalBytes / 1048576).toFixed(0)} MB.`);
    const ln = dv.getUint16(lho + 26, true), lx = dv.getUint16(lho + 28, true);
    const data = u8.subarray(lho + 30 + ln + lx, lho + 30 + ln + lx + csize);
    let bytes;
    if (method === 0) bytes = data.slice();
    else if (method === 8) bytes = await inflate(data, 'deflate-raw');
    else throw new Error(`${name} uses zip compression method ${method}; only stored and deflated files are supported.`);
    files.push({ name, blob: new Blob([bytes]), size: bytes.length });
  }
  return files;
}

const CRC = (() => { const t = new Uint32Array(256); for (let n = 0; n < 256; n++) { let c = n; for (let k = 0; k < 8; k++) c = c & 1 ? 0xedb88320 ^ (c >>> 1) : c >>> 1; t[n] = c >>> 0; } return t; })();
function crc32(u8) { let c = 0xffffffff; for (let i = 0; i < u8.length; i++) c = CRC[(c ^ u8[i]) & 255] ^ (c >>> 8); return (c ^ 0xffffffff) >>> 0; }

// a stored (uncompressed) zip from [{ name, bytes: Uint8Array }]
export function writeZip(entries) {
  const enc = new TextEncoder();
  const parts = [], cen = [];
  let off = 0;
  for (const e of entries) {
    const name = enc.encode(e.name), crc = crc32(e.bytes), n = e.bytes.length;
    const h = new DataView(new ArrayBuffer(30));
    h.setUint32(0, 0x04034b50, true); h.setUint16(4, 20, true); h.setUint16(6, 0x0800, true);
    h.setUint32(14, crc, true); h.setUint32(18, n, true); h.setUint32(22, n, true); h.setUint16(26, name.length, true);
    parts.push(new Uint8Array(h.buffer), name, e.bytes);
    const c = new DataView(new ArrayBuffer(46));
    c.setUint32(0, 0x02014b50, true); c.setUint16(4, 20, true); c.setUint16(6, 20, true); c.setUint16(8, 0x0800, true);
    c.setUint32(16, crc, true); c.setUint32(20, n, true); c.setUint32(24, n, true); c.setUint16(28, name.length, true); c.setUint32(42, off, true);
    cen.push(new Uint8Array(c.buffer), name);
    off += 30 + name.length + n;
  }
  const csz = cen.reduce((a, b) => a + b.length, 0);
  const z = new DataView(new ArrayBuffer(22));
  z.setUint32(0, 0x06054b50, true); z.setUint16(8, entries.length, true); z.setUint16(10, entries.length, true);
  z.setUint32(12, csz, true); z.setUint32(16, off, true);
  return new Blob([...parts, ...cen, new Uint8Array(z.buffer)], { type: 'application/zip' });
}

// Packed int16 geometry: the little-endian int16 stream split into a low-byte plane and a
// high-byte plane, then gzipped (tools/pack_bin.py). Splitting the planes roughly halves the
// gzip size (3.48 MB to 1.62 MB for PHerc0139); unpacking gives back the exact original bytes.
export function unshuffleInt16(planes) {
  const b = new Uint8Array(planes), n = b.length >> 1;
  if (b.length & 1) throw new Error('packed int16 data has an odd length');
  const out = new Uint8Array(b.length);
  for (let i = 0; i < n; i++) { out[2 * i] = b[i]; out[2 * i + 1] = b[n + i]; }
  return out.buffer;
}
export async function gunzip(buf) {
  const s = new Blob([buf]).stream().pipeThrough(new DecompressionStream('gzip'));
  return new Response(s).arrayBuffer();
}
export async function unpackInt16(buf) { return unshuffleInt16(await gunzip(buf)); }