xteink-web-emulator/web/fat32.js

export const FAT32_IMAGE_SIZE = 64 * 1024 * 1024;

const SECTOR_SIZE = 512;
const RESERVED_SECTORS = 32;
const FAT_COUNT = 2;
const ROOT_CLUSTER = 2;
const FAT_EOC = 0x0fffffff;

function setAscii(bytes, offset, value, length) {
  for (let i = 0; i < length; i++) {
    bytes[offset + i] = i < value.length ? value.charCodeAt(i) : 0x20;
  }
}

function fatGeometry(imageSize) {
  const totalSectors = imageSize / SECTOR_SIZE;
  let fatSectors = 1;
  while (true) {
    const clusters = totalSectors - RESERVED_SECTORS - FAT_COUNT * fatSectors;
    const required = Math.ceil((clusters + 2) * 4 / SECTOR_SIZE);
    if (required <= fatSectors) {
      return { totalSectors, fatSectors, clusters };
    }
    fatSectors = required;
  }
}

function makeNode(name, directory, parent = null) {
  return { name, directory, parent, children: new Map(), bytes: null, shortName: null, firstCluster: 0, clusters: [] };
}

function normalizeFiles(files) {
  const root = makeNode('', true);
  for (const { path, bytes } of files) {
    const parts = path.replaceAll('\\', '/').split('/').filter(Boolean);
    if (!parts.length || parts.some(part => part === '.' || part === '..' || part.includes('\0'))) {
      throw new Error(`Invalid SD path: ${path}`);
    }
    let directory = root;
    for (const part of parts.slice(0, -1)) {
      const existing = directory.children.get(part);
      if (existing && !existing.directory) {
        throw new Error(`SD path conflicts with a file: ${path}`);
      }
      if (!existing) {
        directory.children.set(part, makeNode(part, true, directory));
      }
      directory = directory.children.get(part);
    }
    const name = parts.at(-1);
    if (directory.children.has(name)) {
      throw new Error(`Duplicate SD path: ${path}`);
    }
    const file = makeNode(name, false, directory);
    file.bytes = bytes instanceof Uint8Array ? bytes : new Uint8Array(bytes);
    directory.children.set(name, file);
  }
  return root;
}

function sanitizeShortPart(value) {
  return value.toUpperCase().replace(/[^A-Z0-9$%'-_@~`!(){}^#&]/g, '_');
}

function assignShortNames(directory) {
  const used = new Set();
  for (const child of directory.children.values()) {
    const dot = child.directory ? -1 : child.name.lastIndexOf('.');
    const rawBase = dot > 0 ? child.name.slice(0, dot) : child.name;
    const rawExt = dot > 0 ? child.name.slice(dot + 1) : '';
    const base = sanitizeShortPart(rawBase);
    const ext = sanitizeShortPart(rawExt).slice(0, 3);
    const direct = base.length >= 1 && base.length <= 8 && rawExt.length <= 3 && `${base}${ext ? `.${ext}` : ''}` === child.name.toUpperCase();
    let short;
    if (direct) {
      short = `${base.padEnd(8)}${ext.padEnd(3)}`;
    } else {
      for (let n = 1; ; n++) {
        const suffix = `~${n}`;
        short = `${base.slice(0, 8 - suffix.length).padEnd(8 - suffix.length, '_')}${suffix}${ext.padEnd(3)}`;
        if (!used.has(short)) {
          break;
        }
      }
    }
    if (used.has(short)) {
      throw new Error(`Duplicate FAT short name for ${child.name}`);
    }
    used.add(short);
    child.shortName = short;
    if (child.directory) {
      assignShortNames(child);
    }
  }
}

function lfnChecksum(shortName) {
  let sum = 0;
  for (const char of shortName) {
    sum = ((sum & 1) << 7) + (sum >> 1) + char.charCodeAt(0);
    sum &= 0xff;
  }
  return sum;
}

function lfnEntries(node) {
  const shortDisplay = `${node.shortName.slice(0, 8).trimEnd()}${node.shortName.slice(8).trimEnd() ? `.${node.shortName.slice(8).trimEnd()}` : ''}`;
  if (node.name === shortDisplay) {
    return [];
  }
  const units = Array.from(node.name).flatMap(char => {
    const code = char.codePointAt(0);
    return code <= 0xffff ? [code] : [0xd800 + ((code - 0x10000) >> 10), 0xdc00 + ((code - 0x10000) & 0x3ff)];
  });
  if (units.length > 255) {
    throw new Error(`FAT filename is too long: ${node.name}`);
  }
  units.push(0);
  while (units.length % 13) {
    units.push(0xffff);
  }
  const count = units.length / 13;
  const checksum = lfnChecksum(node.shortName);
  const entries = [];
  const positions = [1, 3, 5, 7, 9, 14, 16, 18, 20, 22, 24, 28, 30];
  for (let sequence = count; sequence >= 1; sequence--) {
    const entry = new Uint8Array(32).fill(0xff);
    entry[0] = sequence | (sequence === count ? 0x40 : 0);
    entry[11] = 0x0f;
    entry[12] = 0;
    entry[13] = checksum;
    entry[26] = 0;
    entry[27] = 0;
    const chunk = units.slice((sequence - 1) * 13, sequence * 13);
    const view = new DataView(entry.buffer);
    positions.forEach((position, index) => view.setUint16(position, chunk[index], true));
    entries.push(entry);
  }
  return entries;
}

function shortEntry(node) {
  const entry = new Uint8Array(32);
  setAscii(entry, 0, node.shortName, 11);
  entry[11] = node.directory ? 0x10 : 0x20;
  const view = new DataView(entry.buffer);
  const fatDate = ((2024 - 1980) << 9) | (1 << 5) | 1;
  view.setUint16(14, 0, true);
  view.setUint16(16, fatDate, true);
  view.setUint16(18, fatDate, true);
  view.setUint16(22, 0, true);
  view.setUint16(24, fatDate, true);
  view.setUint16(20, node.firstCluster >>> 16, true);
  view.setUint16(26, node.firstCluster & 0xffff, true);
  view.setUint32(28, node.directory ? 0 : node.bytes.length, true);
  return entry;
}

function directoryEntryCount(directory) {
  let count = directory.parent ? 2 : 0;
  for (const child of directory.children.values()) {
    count += lfnEntries(child).length + 1;
  }
  return count + 1;
}

function allNodes(root) {
  const nodes = [];
  const visit = node => {
    nodes.push(node);
    for (const child of node.children.values()) {
      visit(child);
    }
  };
  visit(root);
  return nodes;
}

function allocateClusters(root, availableClusters) {
  let next = ROOT_CLUSTER;
  const allocate = (node, count) => {
    if (next + count - ROOT_CLUSTER > availableClusters) {
      throw new Error('SD card contents exceed the 64 MiB image capacity.');
    }
    node.clusters = Array.from({ length: count }, (_, i) => next + i);
    node.firstCluster = count ? next : 0;
    next += count;
  };
  for (const node of allNodes(root).filter(node => node.directory)) {
    allocate(node, Math.max(1, Math.ceil(directoryEntryCount(node) * 32 / SECTOR_SIZE)));
  }
  for (const node of allNodes(root).filter(node => !node.directory)) {
    allocate(node, Math.ceil(node.bytes.length / SECTOR_SIZE));
  }
  return next;
}

function writeBootSector(image, geometry) {
  const boot = image.subarray(0, SECTOR_SIZE);
  const view = new DataView(image.buffer);
  boot.set([0xeb, 0x58, 0x90]);
  setAscii(boot, 3, 'XTEINK  ', 8);
  view.setUint16(11, SECTOR_SIZE, true);
  boot[13] = 1;
  view.setUint16(14, RESERVED_SECTORS, true);
  boot[16] = FAT_COUNT;
  view.setUint16(17, 0, true);
  view.setUint16(19, 0, true);
  boot[21] = 0xf8;
  view.setUint16(22, 0, true);
  view.setUint16(24, 63, true);
  view.setUint16(26, 255, true);
  view.setUint32(28, 0, true);
  view.setUint32(32, geometry.totalSectors, true);
  view.setUint32(36, geometry.fatSectors, true);
  view.setUint16(40, 0, true);
  view.setUint16(42, 0, true);
  view.setUint32(44, ROOT_CLUSTER, true);
  view.setUint16(48, 1, true);
  view.setUint16(50, 6, true);
  boot[64] = 0x80;
  boot[66] = 0x29;
  view.setUint32(67, 0x58544549, true);
  setAscii(boot, 71, 'XTEINK', 11);
  setAscii(boot, 82, 'FAT32', 8);
  boot[510] = 0x55;
  boot[511] = 0xaa;
  image.set(boot, 6 * SECTOR_SIZE);

  const fsInfo = new DataView(image.buffer, SECTOR_SIZE, SECTOR_SIZE);
  fsInfo.setUint32(0, 0x41615252, true);
  fsInfo.setUint32(484, 0x61417272, true);
  fsInfo.setUint32(488, 0xffffffff, true);
  fsInfo.setUint32(492, ROOT_CLUSTER + 1, true);
  fsInfo.setUint32(508, 0xaa550000, true);
  image.copyWithin(7 * SECTOR_SIZE, SECTOR_SIZE, 2 * SECTOR_SIZE);
}

function dotEntry(name, cluster) {
  const entry = new Uint8Array(32);
  setAscii(entry, 0, name, 11);
  entry[11] = 0x10;
  const view = new DataView(entry.buffer);
  view.setUint16(20, cluster >>> 16, true);
  view.setUint16(26, cluster & 0xffff, true);
  return entry;
}

export function buildFat32Image(files, imageSize = FAT32_IMAGE_SIZE) {
  if (imageSize < 64 * 1024 * 1024 || imageSize % SECTOR_SIZE || (imageSize & (imageSize - 1))) {
    throw new Error('FAT32 SD image size must be a power of two and at least 64 MiB.');
  }
  const geometry = fatGeometry(imageSize);
  const root = normalizeFiles(files);
  assignShortNames(root);
  const nextCluster = allocateClusters(root, geometry.clusters);
  const image = new Uint8Array(imageSize);
  writeBootSector(image, geometry);

  const fatOffset = RESERVED_SECTORS * SECTOR_SIZE;
  const fatView = new DataView(image.buffer, fatOffset, geometry.fatSectors * SECTOR_SIZE);
  fatView.setUint32(0, 0x0ffffff8, true);
  fatView.setUint32(4, FAT_EOC, true);
  for (const node of allNodes(root)) {
    node.clusters.forEach((cluster, index) => fatView.setUint32(cluster * 4, node.clusters[index + 1] ?? FAT_EOC, true));
  }
  image.copyWithin(fatOffset + geometry.fatSectors * SECTOR_SIZE, fatOffset, fatOffset + geometry.fatSectors * SECTOR_SIZE);

  const dataOffset = (RESERVED_SECTORS + FAT_COUNT * geometry.fatSectors) * SECTOR_SIZE;
  const clusterOffset = cluster => dataOffset + (cluster - ROOT_CLUSTER) * SECTOR_SIZE;
  for (const directory of allNodes(root).filter(node => node.directory)) {
    const entries = [];
    if (directory.parent) {
      entries.push(dotEntry('.          ', directory.firstCluster));
      entries.push(dotEntry('..         ', directory.parent.parent ? directory.parent.firstCluster : ROOT_CLUSTER));
    }
    for (const child of directory.children.values()) {
      entries.push(...lfnEntries(child), shortEntry(child));
    }
    entries.push(new Uint8Array(32));
    const bytes = new Uint8Array(directory.clusters.length * SECTOR_SIZE);
    entries.forEach((entry, index) => bytes.set(entry, index * 32));
    directory.clusters.forEach((cluster, index) => image.set(bytes.subarray(index * SECTOR_SIZE, (index + 1) * SECTOR_SIZE), clusterOffset(cluster)));
  }
  for (const file of allNodes(root).filter(node => !node.directory)) {
    file.clusters.forEach((cluster, index) => image.set(file.bytes.subarray(index * SECTOR_SIZE, (index + 1) * SECTOR_SIZE), clusterOffset(cluster)));
  }

  const freeClusters = geometry.clusters - (nextCluster - ROOT_CLUSTER);
  new DataView(image.buffer).setUint32(SECTOR_SIZE + 488, freeClusters, true);
  image.copyWithin(7 * SECTOR_SIZE, SECTOR_SIZE, 2 * SECTOR_SIZE);
  return image;
}