Something went wrong. Try again.
Builds Windows Installer packages from WiX sources on Linux or Windows, in pure Zig; a clean-room reimplementation of msitools' wixl.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Rewrites a raw deflate stream, as RFC 1951 defines it, so that every//! Huffman code in it is complete.//!//! RFC 1951 lets a block whose matches all share one distance send that one//! distance code in a single bit, leaving the other one-bit code unused, and//! `std.compress.flate` does. zlib never does, and the MSZIP decoders in use//! (cabextract's among them) reject such a code. So every block is decoded//! into its symbols and encoded again, with any code that has a single//! symbol given a second, unused one, and the code-length code built afresh.//! The stream decodes to exactly the bytes it did before.
const std = @import("std");const Allocator = std.mem.Allocator;
pub const Error = error{ /// The input is not a deflate stream this can read. Malformed,} || Allocator.Error;
const max_bits = 15;const end_of_block = 256;/// The order the code-length code's lengths are sent in.const cl_order = [19]u8{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
/// Returns `input` rewritten with every code complete.pub fn completeCodes(gpa: Allocator, input: []const u8) Error![]u8 { var r: BitReader = .{ .bytes = input }; var w: BitWriter = .{}; errdefer w.out.deinit(gpa); var symbols: std.ArrayList(Symbol) = .empty; defer symbols.deinit(gpa);
while (true) { const final = try r.bits(1); const kind = try r.bits(2); switch (kind) { 0 => { // Stored: copied as it is. r.alignToByte(); const len: u16 = @intCast(try r.bits(16)); const nlen: u16 = @intCast(try r.bits(16)); if (len != ~nlen) return error.Malformed; try w.bits(gpa, final, 1); try w.bits(gpa, 0, 2); try w.alignToByte(gpa); try w.bits(gpa, len, 16); try w.bits(gpa, nlen, 16); const data = try r.take(len); try w.out.appendSlice(gpa, data); }, 1 => { // Fixed: its codes are complete already, and it is copied // by decoding and encoding it again with the same codes. var lit: [288]u4 = undefined; for (&lit, 0..) |*l, i| l.* = if (i < 144) 8 else if (i < 256) 9 else if (i < 280) 7 else 8; const dist: [30]u4 = @splat(5); symbols.clearRetainingCapacity(); try decodeBody(gpa, &r, &lit, &dist, &symbols); try w.bits(gpa, final, 1); try w.bits(gpa, 1, 2); try encodeBody(gpa, &w, &lit, &dist, symbols.items); }, 2 => { const hlit = try r.bits(5) + 257; const hdist = try r.bits(5) + 1; const hclen = try r.bits(4) + 4; var cl: [19]u4 = @splat(0); for (cl_order[0..hclen]) |s| cl[s] = @intCast(try r.bits(3)); const cl_code: Decoder = try .init(&cl); var lengths: [288 + 32]u4 = @splat(0); var i: usize = 0; while (i < hlit + hdist) { const s = try cl_code.decode(&r); switch (s) { 0...15 => { lengths[i] = @intCast(s); i += 1; }, 16, 17, 18 => { const value: u4 = if (s == 16) blk: { if (i == 0) return error.Malformed; break :blk lengths[i - 1]; } else 0; const n = switch (s) { 16 => 3 + try r.bits(2), 17 => 3 + try r.bits(3), else => 11 + try r.bits(7), }; if (i + n > hlit + hdist) return error.Malformed; @memset(lengths[i..][0..n], value); i += n; }, else => return error.Malformed, } } var lit: [288]u4 = @splat(0); @memcpy(lit[0..hlit], lengths[0..hlit]); var dist: [30]u4 = @splat(0); if (hdist > 30) return error.Malformed; @memcpy(dist[0..hdist], lengths[hlit..][0..hdist]);
symbols.clearRetainingCapacity(); try decodeBody(gpa, &r, &lit, &dist, &symbols); complete(&lit, 286); complete(&dist, 30); try w.bits(gpa, final, 1); try w.bits(gpa, 2, 2); try encodeHeader(gpa, &w, &lit, &dist); try encodeBody(gpa, &w, &lit, &dist, symbols.items); }, else => return error.Malformed, } if (final == 1) break; } try w.alignToByte(gpa); return w.out.toOwnedSlice(gpa);}
/// Gives a code with a single symbol, which RFC 1951 sends in one bit, a/// second symbol of one bit, unused, so that the code is complete. A code/// with no symbols gets two.fn complete(lengths: []u4, limit: usize) void { var used: usize = 0; var only: usize = 0; for (lengths[0..limit], 0..) |l, i| if (l != 0) { used += 1; only = i; }; switch (used) { 0 => { lengths[0] = 1; lengths[1] = 1; }, 1 => { lengths[only] = 1; lengths[if (only + 1 < limit) only + 1 else only - 1] = 1; }, else => {}, }}
const Symbol = struct { /// A literal or length symbol, or a distance symbol when `is_distance`. value: u16, is_distance: bool, extra: u16 = 0, extra_bits: u4 = 0,};
fn lengthExtraBits(s: u16) u4 { if (s < 265 or s == 285) return 0; return @intCast((s - 261) / 4);}
fn distanceExtraBits(s: u16) u4 { if (s < 4) return 0; return @intCast(s / 2 - 1);}
fn decodeBody(gpa: Allocator, r: *BitReader, lit: []const u4, dist: []const u4, out: *std.ArrayList(Symbol)) Error!void { const lit_code: Decoder = try .init(lit); const dist_code: ?Decoder = Decoder.init(dist) catch null; while (true) { const s = try lit_code.decode(r); if (s < 256) { try out.append(gpa, .{ .value = s, .is_distance = false }); continue; } if (s == end_of_block) { try out.append(gpa, .{ .value = s, .is_distance = false }); return; } if (s > 285) return error.Malformed; const le = lengthExtraBits(s); try out.append(gpa, .{ .value = s, .is_distance = false, .extra = @intCast(try r.bits(le)), .extra_bits = le }); const d = try (dist_code orelse return error.Malformed).decode(r); if (d > 29) return error.Malformed; const de = distanceExtraBits(d); try out.append(gpa, .{ .value = d, .is_distance = true, .extra = @intCast(try r.bits(de)), .extra_bits = de }); }}
fn encodeBody(gpa: Allocator, w: *BitWriter, lit: []const u4, dist: []const u4, symbols: []const Symbol) Allocator.Error!void { var lit_codes: [288]u16 = undefined; canonical(lit, &lit_codes); var dist_codes: [30]u16 = undefined; canonical(dist, &dist_codes); for (symbols) |s| { if (s.is_distance) { try w.huffman(gpa, dist_codes[s.value], dist[s.value]); } else { try w.huffman(gpa, lit_codes[s.value], lit[s.value]); } try w.bits(gpa, s.extra, s.extra_bits); }}
/// The header of a dynamic block: the two codes' lengths, run-length/// encoded, sent with a code-length code built for them.fn encodeHeader(gpa: Allocator, w: *BitWriter, lit: []const u4, dist: []const u4) Allocator.Error!void { var hlit: usize = 286; while (hlit > 257 and lit[hlit - 1] == 0) hlit -= 1; var hdist: usize = 30; while (hdist > 1 and dist[hdist - 1] == 0) hdist -= 1;
var lengths: [286 + 30]u4 = undefined; @memcpy(lengths[0..hlit], lit[0..hlit]); @memcpy(lengths[hlit..][0..hdist], dist[0..hdist]); const all = lengths[0 .. hlit + hdist];
// The run-length encoding: each item a code-length symbol and the // value of its extra bits. var items: std.ArrayList(struct { u8, u8 }) = .empty; defer items.deinit(gpa); var i: usize = 0; while (i < all.len) { const v = all[i]; var run: usize = 1; while (i + run < all.len and all[i + run] == v) run += 1; if (v == 0 and run >= 3) { const n = @min(run, 138); if (n >= 11) { try items.append(gpa, .{ 18, @intCast(n - 11) }); } else { try items.append(gpa, .{ 17, @intCast(n - 3) }); } i += n; } else if (v != 0 and run >= 4) { try items.append(gpa, .{ v, 0 }); const n = @min(run - 1, 6); try items.append(gpa, .{ 16, @intCast(n - 3) }); i += 1 + n; } else { try items.append(gpa, .{ v, 0 }); i += 1; } }
var freqs: [19]u32 = @splat(0); for (items.items) |it| freqs[it[0]] += 1; var cl: [19]u4 = undefined; lengthLimited(&freqs, 7, &cl); var hclen: usize = 19; while (hclen > 4 and cl[cl_order[hclen - 1]] == 0) hclen -= 1;
try w.bits(gpa, hlit - 257, 5); try w.bits(gpa, hdist - 1, 5); try w.bits(gpa, hclen - 4, 4); for (cl_order[0..hclen]) |s| try w.bits(gpa, cl[s], 3); var cl_codes: [19]u16 = undefined; canonical(&cl, &cl_codes); for (items.items) |it| { try w.huffman(gpa, cl_codes[it[0]], cl[it[0]]); const extra: u4 = switch (it[0]) { 16 => 2, 17 => 3, 18 => 7, else => 0, }; try w.bits(gpa, it[1], extra); }}
/// Complete code lengths, none longer than `limit`, for the symbols with a/// nonzero frequency: Huffman's, when they fit, and otherwise as even as a/// complete code allows. A lone symbol gets a partner, so that the code is/// complete.fn lengthLimited(freqs: []const u32, limit: u4, out: []u4) void { @memset(out, 0); var used_buf: [19]usize = undefined; var n: usize = 0; for (freqs, 0..) |f, i| if (f > 0) { used_buf[n] = i; n += 1; }; if (n == 0) return; if (n == 1) { out[used_buf[0]] = 1; out[if (used_buf[0] == 0) 1 else 0] = 1; return; } const used = used_buf[0..n];
// Huffman's algorithm, on so few symbols that repeatedly finding the // two lightest is plenty fast. var weight: [38]u64 = undefined; var parent: [38]usize = undefined; var alive: [38]bool = @splat(false); for (used, 0..) |s, k| { weight[k] = freqs[s]; alive[k] = true; } var nodes = n; var remaining = n; while (remaining > 1) { var a: ?usize = null; var b: ?usize = null; for (0..nodes) |k| { if (!alive[k]) continue; if (a == null or weight[k] < weight[a.?]) { b = a; a = k; } else if (b == null or weight[k] < weight[b.?]) { b = k; } } alive[a.?] = false; alive[b.?] = false; weight[nodes] = weight[a.?] + weight[b.?]; parent[a.?] = nodes; parent[b.?] = nodes; alive[nodes] = true; nodes += 1; remaining -= 1; } const root = nodes - 1; var fits = true; for (used, 0..) |s, k| { var depth: usize = 0; var at = k; while (at != root) : (depth += 1) at = parent[at]; if (depth > limit) fits = false; out[s] = @intCast(@min(depth, max_bits)); } if (fits) return;
// The even code: with 2^b > n >= 2^(b-1), 2^b - n symbols get b - 1 bits // and the rest b, which sums to exactly one. var b: u4 = 1; while ((@as(usize, 1) << b) < n) b += 1; const short = (@as(usize, 1) << b) - n; for (used, 0..) |s, k| out[s] = if (k < short) b - 1 else b;}
/// The canonical codes RFC 1951 assigns to `lengths`.fn canonical(lengths: []const u4, codes: []u16) void { var count: [max_bits + 1]u16 = @splat(0); for (lengths) |l| count[l] += 1; count[0] = 0; var next: [max_bits + 1]u16 = undefined; var code: u16 = 0; for (1..max_bits + 1) |bits| { code = (code + count[bits - 1]) << 1; next[bits] = code; } for (lengths, 0..) |l, i| { if (l == 0) continue; codes[i] = next[l]; next[l] += 1; }}
/// A canonical Huffman decoder, which walks the code a bit at a time.const Decoder = struct { count: [max_bits + 1]u16, /// The symbols in code order. symbols: [320]u16,
fn init(lengths: []const u4) error{Malformed}!Decoder { var d: Decoder = .{ .count = @splat(0), .symbols = undefined }; for (lengths) |l| d.count[l] += 1; if (d.count[0] == lengths.len) return error.Malformed; var offsets: [max_bits + 1]u16 = undefined; offsets[1] = 0; for (1..max_bits) |bits| offsets[bits + 1] = offsets[bits] + d.count[bits]; for (lengths, 0..) |l, s| { if (l == 0) continue; d.symbols[offsets[l]] = @intCast(s); offsets[l] += 1; } return d; }
fn decode(d: *const Decoder, r: *BitReader) error{Malformed}!u16 { var code: i32 = 0; var first: i32 = 0; var index: i32 = 0; for (1..max_bits + 1) |bits| { code |= @intCast(try r.bits(1)); const count: i32 = d.count[bits]; if (code - count < first) return d.symbols[@intCast(index + (code - first))]; index += count; first += count; first <<= 1; code <<= 1; } return error.Malformed; }};
const BitReader = struct { bytes: []const u8, pos: usize = 0, bit: u3 = 0,
fn bits(r: *BitReader, n: usize) error{Malformed}!usize { var v: usize = 0; for (0..n) |k| { if (r.pos >= r.bytes.len) return error.Malformed; const b = (r.bytes[r.pos] >> r.bit) & 1; v |= @as(usize, b) << @intCast(k); if (r.bit == 7) { r.bit = 0; r.pos += 1; } else r.bit += 1; } return v; }
fn alignToByte(r: *BitReader) void { if (r.bit != 0) { r.bit = 0; r.pos += 1; } }
fn take(r: *BitReader, n: usize) error{Malformed}![]const u8 { if (r.pos + n > r.bytes.len) return error.Malformed; defer r.pos += n; return r.bytes[r.pos..][0..n]; }};
const BitWriter = struct { out: std.ArrayList(u8) = .empty, acc: u32 = 0, count: u5 = 0,
/// Writes the low `n` bits of `v`, least significant first. fn bits(w: *BitWriter, gpa: Allocator, v: usize, n: usize) Allocator.Error!void { for (0..n) |k| { w.acc |= @as(u32, @intCast((v >> @intCast(k)) & 1)) << w.count; w.count += 1; if (w.count == 8) { try w.out.append(gpa, @intCast(w.acc)); w.acc = 0; w.count = 0; } } }
/// Writes a Huffman code, which goes most significant bit first. fn huffman(w: *BitWriter, gpa: Allocator, code: u16, len: u4) Allocator.Error!void { var k: usize = len; while (k > 0) { k -= 1; try w.bits(gpa, (code >> @intCast(k)) & 1, 1); } }
fn alignToByte(w: *BitWriter, gpa: Allocator) Allocator.Error!void { if (w.count != 0) { try w.out.append(gpa, @intCast(w.acc)); w.acc = 0; w.count = 0; } }};
/// The Kraft sum of a block's distance code, times 2^15: 2^15 when the code/// is complete. For the tests.fn distanceKraft(stream: []const u8) !u32 { var r: BitReader = .{ .bytes = stream }; _ = try r.bits(1); if (try r.bits(2) != 2) return error.Malformed; const hlit = try r.bits(5) + 257; const hdist = try r.bits(5) + 1; const hclen = try r.bits(4) + 4; var cl: [19]u4 = @splat(0); for (cl_order[0..hclen]) |s| cl[s] = @intCast(try r.bits(3)); const cl_code: Decoder = try .init(&cl); var lengths: [320]u4 = @splat(0); var i: usize = 0; while (i < hlit + hdist) { const s = try cl_code.decode(&r); switch (s) { 0...15 => { lengths[i] = @intCast(s); i += 1; }, 16 => { const n = 3 + try r.bits(2); @memset(lengths[i..][0..n], lengths[i - 1]); i += n; }, 17 => i += 3 + try r.bits(3), else => i += 11 + try r.bits(7), } } var sum: u32 = 0; for (lengths[hlit..][0..hdist]) |l| if (l != 0) { sum += @as(u32, 1) << @intCast(15 - @as(u5, l)); }; return sum;}
fn compress(gpa: Allocator, data: []const u8) ![]u8 { // The compressor wants room for at least a few bytes from the start. var out: std.Io.Writer.Allocating = try .initCapacity(gpa, 64); const window = try gpa.alloc(u8, std.compress.flate.max_window_len); defer gpa.free(window); const c = try gpa.create(std.compress.flate.Compress); defer gpa.destroy(c); c.* = try .init(&out.writer, window, .raw, .default); try c.writer.writeAll(data); try c.finish(); return out.toOwnedSlice();}
fn inflate(gpa: Allocator, stream: []const u8) ![]u8 { var in: std.Io.Reader = .fixed(stream); var window: [std.compress.flate.max_window_len]u8 = undefined; var d: std.compress.flate.Decompress = .init(&in, .raw, &window); return d.reader.allocRemaining(gpa, .unlimited);}
test "a lone distance code gets a partner, and the data survives" { var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); defer arena.deinit(); const a = arena.allocator(); // A period of 54 bytes: every match the same distance. const data = try a.alloc(u8, 32768); for (data, 0..) |*b, i| b.* = "Windows Installer packages from WiX sources, in Zig.\n"[i % 54]; const original = try compress(a, data); try std.testing.expect(try distanceKraft(original) < 1 << 15); const fixed = try completeCodes(a, original); try std.testing.expectEqual(@as(u32, 1 << 15), try distanceKraft(fixed)); try std.testing.expectEqualSlices(u8, data, try inflate(a, fixed));}
test "zeros, text, noise and nothing all round-trip" { var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); defer arena.deinit(); const a = arena.allocator(); var rng: std.Random.DefaultPrng = .init(7); const noise = try a.alloc(u8, 32768); rng.random().bytes(noise); const zeros = try a.alloc(u8, 32768); @memset(zeros, 0); const text = try a.alloc(u8, 32768); for (text, 0..) |*b, i| b.* = @intCast(32 + (i * 7 + i / 13) % 95); for ([_][]const u8{ noise, zeros, text, "", "x" }) |data| { const fixed = try completeCodes(a, try compress(a, data)); try std.testing.expectEqualSlices(u8, data, try inflate(a, fixed)); }}
test "length-limited codes are complete" { var out: [19]u4 = undefined; // Frequencies so skewed that Huffman would go past seven bits. var freqs: [19]u32 = undefined; for (&freqs, 0..) |*f, i| f.* = @as(u32, 1) << @intCast(i); lengthLimited(&freqs, 7, &out); var sum: u32 = 0; for (out) |l| { try std.testing.expect(l <= 7); if (l != 0) sum += @as(u32, 1) << @intCast(15 - @as(u5, l)); } try std.testing.expectEqual(@as(u32, 1 << 15), sum);}