// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! A writer of compound files, as [MS-CFB] specifies them: version 3, with //! 512-byte sectors, holding streams in the root storage and nothing else. //! //! Everything about the output is decided by its input: the directory, the //! sector layout and every timestamp, which is always zero. The same streams //! therefore always give the same bytes. const std = @import("std"); const Allocator = std.mem.Allocator; const Io = std.Io; pub const Stream = struct { /// The name as UTF-16 code units, without a terminator. At most 31. name: []const u16, data: []const u8, }; const sector_size = 512; const mini_sector_size = 64; const mini_stream_cutoff = 4096; const header_difat_entries = 109; /// FAT sector locations a DIFAT sector holds, the last slot pointing on. const difat_entries_per_sector = sector_size / 4 - 1; const entries_per_fat_sector = sector_size / 4; const directory_entry_size = 128; const ENDOFCHAIN: u32 = 0xFFFF_FFFE; const FREESECT: u32 = 0xFFFF_FFFF; const FATSECT: u32 = 0xFFFF_FFFD; const DIFSECT: u32 = 0xFFFF_FFFC; const NOSTREAM: u32 = 0xFFFF_FFFF; pub const Error = error{ /// A stream name is empty, too long, or used twice. InvalidName, /// A stream is larger than a version 3 compound file can hold. StreamTooLarge, } || Allocator.Error || Io.Writer.Error; /// Writes a compound file holding `streams` in its root storage, whose CLSID /// is `clsid` (16 bytes, as they appear on disk). pub fn write(gpa: Allocator, w: *Io.Writer, clsid: [16]u8, streams: []const Stream) Error!void { for (streams, 0..) |s, i| { if (s.name.len == 0 or s.name.len > 31) return error.InvalidName; if (s.data.len > std.math.maxInt(u32)) return error.StreamTooLarge; for (streams[0..i]) |earlier| { if (compareNames(earlier.name, s.name) == .eq) return error.InvalidName; } } // Where each stream's data starts: a sector of the file, or a mini // sector of the mini stream. const starts = try gpa.alloc(u32, streams.len); defer gpa.free(starts); // The mini stream and its FAT. var mini_fat: std.ArrayList(u32) = .empty; defer mini_fat.deinit(gpa); for (streams, 0..) |s, i| { if (s.data.len == 0 or s.data.len >= mini_stream_cutoff) continue; const first: u32 = @intCast(mini_fat.items.len); starts[i] = first; const count = std.math.divCeil(usize, s.data.len, mini_sector_size) catch unreachable; for (0..count) |k| { try mini_fat.append(gpa, if (k + 1 == count) ENDOFCHAIN else first + @as(u32, @intCast(k)) + 1); } } const mini_stream_len = mini_fat.items.len * mini_sector_size; // The sectors, in the order they are laid out: the large streams, the // mini stream, the mini FAT, the directory, then the FAT and the DIFAT. var fat: std.ArrayList(u32) = .empty; defer fat.deinit(gpa); for (streams, 0..) |s, i| { if (s.data.len < mini_stream_cutoff) continue; starts[i] = try appendChain(gpa, &fat, sectorsFor(s.data.len)); } const mini_stream_start = if (mini_stream_len == 0) ENDOFCHAIN else try appendChain(gpa, &fat, sectorsFor(mini_stream_len)); const mini_fat_sectors = sectorsFor(mini_fat.items.len * 4); const mini_fat_start = if (mini_fat_sectors == 0) ENDOFCHAIN else try appendChain(gpa, &fat, mini_fat_sectors); const directory_entries = streams.len + 1; const directory_start = try appendChain(gpa, &fat, sectorsFor(directory_entries * directory_entry_size)); // The FAT has to describe its own sectors and the DIFAT's, so their // number is found by trying until it covers everything. const used = fat.items.len; var fat_sectors: usize = 1; var difat_sectors: usize = 0; while (true) { difat_sectors = if (fat_sectors <= header_difat_entries) 0 else std.math.divCeil(usize, fat_sectors - header_difat_entries, difat_entries_per_sector) catch unreachable; const needed = std.math.divCeil(usize, used + fat_sectors + difat_sectors, entries_per_fat_sector) catch unreachable; if (needed <= fat_sectors) break; fat_sectors = needed; } const fat_start: u32 = @intCast(fat.items.len); for (0..fat_sectors) |_| try fat.append(gpa, FATSECT); const difat_start: u32 = if (difat_sectors == 0) ENDOFCHAIN else @intCast(fat.items.len); for (0..difat_sectors) |_| try fat.append(gpa, DIFSECT); const total_sectors = fat.items.len; while (fat.items.len < fat_sectors * entries_per_fat_sector) try fat.append(gpa, FREESECT); // -- header ------------------------------------------------------------ var header: [sector_size]u8 = @splat(0); @memcpy(header[0..8], &[_]u8{ 0xD0, 0xCF, 0x11, 0xE0, 0xA1, 0xB1, 0x1A, 0xE1 }); std.mem.writeInt(u16, header[0x18..0x1A], 0x003E, .little); // minor version std.mem.writeInt(u16, header[0x1A..0x1C], 0x0003, .little); // major version std.mem.writeInt(u16, header[0x1C..0x1E], 0xFFFE, .little); // byte order std.mem.writeInt(u16, header[0x1E..0x20], 9, .little); // sector shift std.mem.writeInt(u16, header[0x20..0x22], 6, .little); // mini sector shift std.mem.writeInt(u32, header[0x2C..0x30], @intCast(fat_sectors), .little); std.mem.writeInt(u32, header[0x30..0x34], directory_start, .little); std.mem.writeInt(u32, header[0x38..0x3C], mini_stream_cutoff, .little); std.mem.writeInt(u32, header[0x3C..0x40], mini_fat_start, .little); std.mem.writeInt(u32, header[0x40..0x44], @intCast(mini_fat_sectors), .little); std.mem.writeInt(u32, header[0x44..0x48], difat_start, .little); std.mem.writeInt(u32, header[0x48..0x4C], @intCast(difat_sectors), .little); for (0..header_difat_entries) |k| { const v: u32 = if (k < fat_sectors) fat_start + @as(u32, @intCast(k)) else FREESECT; std.mem.writeInt(u32, header[0x4C + 4 * k ..][0..4], v, .little); } try w.writeAll(&header); // -- the large streams --------------------------------------------------- for (streams) |s| { if (s.data.len < mini_stream_cutoff) continue; try writePadded(w, s.data, sector_size); } // -- the mini stream and its FAT ------------------------------------------- if (mini_stream_len > 0) { var written: usize = 0; for (streams) |s| { if (s.data.len == 0 or s.data.len >= mini_stream_cutoff) continue; try writePadded(w, s.data, mini_sector_size); written += std.mem.alignForward(usize, s.data.len, mini_sector_size); } try w.splatByteAll(0, sectorsFor(written) * sector_size - written); for (mini_fat.items) |v| try w.writeInt(u32, v, .little); const pad = mini_fat_sectors * entries_per_fat_sector - mini_fat.items.len; for (0..pad) |_| try w.writeInt(u32, FREESECT, .little); } // -- the directory --------------------------------------------------------- const order = try gpa.alloc(u32, streams.len); defer gpa.free(order); for (order, 0..) |*o, i| o.* = @intCast(i); std.mem.sort(u32, order, streams, struct { fn lessThan(ctx: []const Stream, a: u32, b: u32) bool { return compareNames(ctx[a].name, ctx[b].name) == .lt; } }.lessThan); // Siblings form a binary search tree. A balanced one with every node // black is what is written; [MS-CFB] readers do not rebalance it. const left = try gpa.alloc(u32, streams.len); defer gpa.free(left); const right = try gpa.alloc(u32, streams.len); defer gpa.free(right); const tree_root = buildTree(order, left, right); var entry: [directory_entry_size]u8 = undefined; directoryEntry(&entry, &std.unicode.utf8ToUtf16LeStringLiteral("Root Entry").*, 5, NOSTREAM, NOSTREAM, tree_root, clsid, mini_stream_start, mini_stream_len); try w.writeAll(&entry); for (streams, 0..) |s, i| { const start = if (s.data.len == 0) ENDOFCHAIN else starts[i]; directoryEntry(&entry, s.name, 2, left[i], right[i], NOSTREAM, @splat(0), start, s.data.len); try w.writeAll(&entry); } const directory_slots = sectorsFor(directory_entries * directory_entry_size) * (sector_size / directory_entry_size); for (directory_entries..directory_slots) |_| { directoryEntry(&entry, &.{}, 0, NOSTREAM, NOSTREAM, NOSTREAM, @splat(0), 0, 0); try w.writeAll(&entry); } // -- the FAT and the DIFAT ------------------------------------------------- for (fat.items) |v| try w.writeInt(u32, v, .little); for (0..difat_sectors) |d| { for (0..difat_entries_per_sector) |k| { const index = header_difat_entries + d * difat_entries_per_sector + k; const v: u32 = if (index < fat_sectors) fat_start + @as(u32, @intCast(index)) else FREESECT; try w.writeInt(u32, v, .little); } const next: u32 = if (d + 1 < difat_sectors) difat_start + @as(u32, @intCast(d)) + 1 else ENDOFCHAIN; try w.writeInt(u32, next, .little); } std.debug.assert(total_sectors <= fat.items.len); } fn sectorsFor(len: usize) usize { return std.math.divCeil(usize, len, sector_size) catch unreachable; } /// Appends a chain of `count` consecutive sectors to the FAT, returning the /// first. fn appendChain(gpa: Allocator, fat: *std.ArrayList(u32), count: usize) Allocator.Error!u32 { const first: u32 = @intCast(fat.items.len); for (0..count) |k| { try fat.append(gpa, if (k + 1 == count) ENDOFCHAIN else first + @as(u32, @intCast(k)) + 1); } return first; } fn writePadded(w: *Io.Writer, data: []const u8, alignment: usize) Io.Writer.Error!void { try w.writeAll(data); try w.splatByteAll(0, std.mem.alignForward(usize, data.len, alignment) - data.len); } /// The order [MS-CFB] keeps siblings in: shorter names first, then by code /// unit after mapping to upper case. pub fn compareNames(a: []const u16, b: []const u16) std.math.Order { if (a.len != b.len) return std.math.order(a.len, b.len); for (a, b) |x, y| { const o = std.math.order(upper(x), upper(y)); if (o != .eq) return o; } return .eq; } fn upper(c: u16) u16 { return if (c >= 'a' and c <= 'z') c - 32 else c; } /// Makes `sorted` (stream indices in name order) a balanced tree, filling in /// each stream's left and right siblings and returning the root's directory /// entry number. Stream `i` is directory entry `i + 1`. fn buildTree(sorted: []const u32, left: []u32, right: []u32) u32 { if (sorted.len == 0) return NOSTREAM; const mid = sorted.len / 2; const i = sorted[mid]; left[i] = buildTree(sorted[0..mid], left, right); right[i] = buildTree(sorted[mid + 1 ..], left, right); return i + 1; } fn directoryEntry( out: *[directory_entry_size]u8, name: []const u16, object_type: u8, left_sibling: u32, right_sibling: u32, child: u32, clsid: [16]u8, start: u32, size: usize, ) void { out.* = @splat(0); for (name, 0..) |c, k| std.mem.writeInt(u16, out[2 * k ..][0..2], c, .little); const name_bytes: u16 = if (name.len == 0) 0 else @intCast((name.len + 1) * 2); std.mem.writeInt(u16, out[0x40..0x42], name_bytes, .little); out[0x42] = object_type; out[0x43] = 1; // black std.mem.writeInt(u32, out[0x44..0x48], left_sibling, .little); std.mem.writeInt(u32, out[0x48..0x4C], right_sibling, .little); std.mem.writeInt(u32, out[0x4C..0x50], child, .little); @memcpy(out[0x50..0x60], &clsid); std.mem.writeInt(u32, out[0x74..0x78], start, .little); std.mem.writeInt(u64, out[0x78..0x80], size, .little); } test "names order by length, then without case" { const a = std.unicode.utf8ToUtf16LeStringLiteral("abc"); const b = std.unicode.utf8ToUtf16LeStringLiteral("ABD"); const c = std.unicode.utf8ToUtf16LeStringLiteral("ab"); try std.testing.expectEqual(std.math.Order.lt, compareNames(a, b)); try std.testing.expectEqual(std.math.Order.gt, compareNames(a, c)); try std.testing.expectEqual(std.math.Order.eq, compareNames(a, std.unicode.utf8ToUtf16LeStringLiteral("ABC"))); } test "the header and the directory of a small file" { var out: Io.Writer.Allocating = .init(std.testing.allocator); defer out.deinit(); const name = std.unicode.utf8ToUtf16LeStringLiteral("small"); try write(std.testing.allocator, &out.writer, @splat(0), &.{.{ .name = name, .data = "hello" }}); const bytes = out.written(); // The header, then one sector each for the mini stream, the mini FAT, // the directory and the FAT. try std.testing.expectEqual(@as(usize, 512 * 5), bytes.len); try std.testing.expectEqualSlices(u8, &.{ 0xD0, 0xCF, 0x11, 0xE0 }, bytes[0..4]); try std.testing.expectEqualStrings("hello", bytes[512..517]); // The directory is the fourth sector after the header, sector 2. try std.testing.expectEqual(@as(u32, 2), std.mem.readInt(u32, bytes[0x30..0x34], .little)); const dir = bytes[512 * 3 ..]; try std.testing.expectEqual(@as(u8, 5), dir[0x42]); try std.testing.expectEqual(@as(u32, 1), std.mem.readInt(u32, dir[0x4C..0x50], .little)); try std.testing.expectEqual(@as(u8, 2), dir[128 + 0x42]); try std.testing.expectEqual(@as(u64, 5), std.mem.readInt(u64, dir[128 + 0x78 ..][0..8], .little)); }