Something went wrong. Try again.
A Zig library and CLI for reading Mobipocket (.mobi, .prc, .azw) e-books.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! HUFF/CDIC decompression, used by MOBI compression type 17480.//!//! The HUFF record holds the Huffman tables; each following CDIC record holds a//! slice of the phrase dictionary that the decoded symbols index into. A phrase//! may itself be HUFF/CDIC compressed, in which case it is decoded on first use//! and cached.
const std = @import("std");
pub const Error = error{ InvalidHuffRecord, InvalidCdicRecord, CorruptCompressedData, OutOfMemory };
const Dict1Entry = struct { codelen: u8, terminal: bool, maxcode: u64,};
const Phrase = struct { raw: []const u8, terminal: bool, /// Set once a non-terminal phrase has been decoded; owned by the decoder. decoded: ?[]u8 = null,};
pub const Decoder = struct { gpa: std.mem.Allocator, dict1: [256]Dict1Entry, mincode: [32]u64, maxcode: [32]u64, phrases: []Phrase,
/// `huff` is the HUFF record, `cdics` the CDIC records that follow it, in order. /// The records must outlive the decoder; phrase data is referenced, not copied. pub fn init(gpa: std.mem.Allocator, huff: []const u8, cdics: []const []const u8) Error!Decoder { if (huff.len < 24 or !std.mem.eql(u8, huff[0..4], "HUFF")) return error.InvalidHuffRecord; if (std.mem.readInt(u32, huff[4..8], .big) != 24) return error.InvalidHuffRecord;
const off1 = std.mem.readInt(u32, huff[8..12], .big); const off2 = std.mem.readInt(u32, huff[12..16], .big); if (off1 + 256 * 4 > huff.len or off2 + 64 * 4 > huff.len) return error.InvalidHuffRecord;
var self: Decoder = .{ .gpa = gpa, .dict1 = undefined, .mincode = undefined, .maxcode = undefined, .phrases = &.{}, };
for (&self.dict1, 0..) |*slot, i| { const v = std.mem.readInt(u32, huff[off1 + i * 4 ..][0..4], .big); const codelen: u8 = @intCast(v & 0x1f); if (codelen == 0 or codelen > 32) return error.InvalidHuffRecord; slot.* = .{ .codelen = codelen, .terminal = (v & 0x80) != 0, .maxcode = ((@as(u64, v >> 8) + 1) << @intCast(32 - codelen)) - 1, }; }
for (0..32) |codelen| { const lo = std.mem.readInt(u32, huff[off2 + codelen * 8 ..][0..4], .big); const hi = std.mem.readInt(u32, huff[off2 + codelen * 8 + 4 ..][0..4], .big); const shift: u6 = @intCast(32 - codelen); self.mincode[codelen] = @as(u64, lo) << shift; self.maxcode[codelen] = ((@as(u64, hi) + 1) << shift) - 1; }
var list: std.ArrayList(Phrase) = .empty; errdefer list.deinit(gpa); for (cdics) |cdic| try loadCdic(gpa, &list, cdic); self.phrases = try list.toOwnedSlice(gpa); return self; }
fn loadCdic(gpa: std.mem.Allocator, list: *std.ArrayList(Phrase), cdic: []const u8) Error!void { if (cdic.len < 16 or !std.mem.eql(u8, cdic[0..4], "CDIC")) return error.InvalidCdicRecord; if (std.mem.readInt(u32, cdic[4..8], .big) != 16) return error.InvalidCdicRecord;
const total = std.mem.readInt(u32, cdic[8..12], .big); const bits = std.mem.readInt(u32, cdic[12..16], .big); if (bits > 16) return error.InvalidCdicRecord; if (total < list.items.len) return error.InvalidCdicRecord;
const n = @min(@as(usize, 1) << @intCast(bits), total - list.items.len); if (16 + n * 2 > cdic.len) return error.InvalidCdicRecord;
for (0..n) |i| { const off = std.mem.readInt(u16, cdic[16 + i * 2 ..][0..2], .big); if (16 + @as(usize, off) + 2 > cdic.len) return error.InvalidCdicRecord; const blen = std.mem.readInt(u16, cdic[16 + @as(usize, off) ..][0..2], .big); const len: usize = blen & 0x7fff; const start = 18 + @as(usize, off); if (start + len > cdic.len) return error.InvalidCdicRecord; try list.append(gpa, .{ .raw = cdic[start .. start + len], .terminal = (blen & 0x8000) != 0, }); } }
pub fn deinit(self: *Decoder) void { for (self.phrases) |p| if (p.decoded) |d| self.gpa.free(d); self.gpa.free(self.phrases); self.* = undefined; }
pub fn decompressAppend(self: *Decoder, out: *std.ArrayList(u8), input: []const u8) Error!void { try self.unpack(out, input, 0); }
pub fn decompress(self: *Decoder, input: []const u8) Error![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(self.gpa); try self.unpack(&out, input, 0); return out.toOwnedSlice(self.gpa); }
fn unpack(self: *Decoder, out: *std.ArrayList(u8), input: []const u8, depth: u8) Error!void { if (depth > 16) return error.CorruptCompressedData;
// The bit reader always loads eight bytes at a time, so pad the tail. const buf = try self.gpa.alloc(u8, input.len + 16); defer self.gpa.free(buf); @memcpy(buf[0..input.len], input); @memset(buf[input.len..], 0);
var bits_left: i64 = @intCast(input.len * 8); var pos: usize = 0; var n: i64 = 32; var x = std.mem.readInt(u64, buf[0..8], .big);
while (true) { if (n <= 0) { pos += 4; if (pos + 8 > buf.len) break; x = std.mem.readInt(u64, buf[pos..][0..8], .big); n += 32; } const code: u64 = (x >> @intCast(n)) & 0xffff_ffff;
const entry = self.dict1[@intCast(code >> 24)]; var codelen = entry.codelen; var maxcode = entry.maxcode; if (!entry.terminal) { while (codelen < 32 and code < self.mincode[codelen]) codelen += 1; if (codelen >= 32) return error.CorruptCompressedData; maxcode = self.maxcode[codelen]; }
n -= codelen; bits_left -= codelen; if (bits_left < 0) break;
if (maxcode < code) return error.CorruptCompressedData; const index = (maxcode - code) >> @intCast(32 - codelen); if (index >= self.phrases.len) return error.CorruptCompressedData;
const phrase = &self.phrases[index]; if (phrase.terminal) { try out.appendSlice(self.gpa, phrase.raw); } else { if (phrase.decoded == null) { var nested: std.ArrayList(u8) = .empty; errdefer nested.deinit(self.gpa); // Guard against a phrase that expands to itself. phrase.terminal = true; const raw = phrase.raw; phrase.raw = &.{}; try self.unpack(&nested, raw, depth + 1); phrase.raw = raw; phrase.terminal = false; phrase.decoded = try nested.toOwnedSlice(self.gpa); } try out.appendSlice(self.gpa, phrase.decoded.?); } } }};
// -- Tests -----------------------------------------------------------------//// There is no HUFF/CDIC sample in the test data, so these tests build the// tables by hand. Every symbol is given an eight bit terminal code, which lets// a byte stream be "encoded" by writing the bytes themselves: byte `b` selects// dictionary phrase `b`. See `buildHuff` for how the code length and dictionary// index are packed into the table entry.
const testing = std.testing;
/// A phrase to place in the dictionary. Non-terminal phrases hold a nested/// encoded stream that the decoder must expand on first use.const TestPhrase = struct { bytes: []const u8, terminal: bool = true,};
/// Build a HUFF record where dict1[b] is an eight bit terminal code selecting/// dictionary entry `b`.fn buildHuff(gpa: std.mem.Allocator) ![]u8 { const off1 = 24; const off2 = off1 + 256 * 4; const buf = try gpa.alloc(u8, off2 + 64 * 4); @memset(buf, 0);
@memcpy(buf[0..4], "HUFF"); std.mem.writeInt(u32, buf[4..8], 24, .big); std.mem.writeInt(u32, buf[8..12], off1, .big); std.mem.writeInt(u32, buf[12..16], off2, .big);
for (0..256) |b| { // Decoding computes index = (maxcode - code) >> (32 - codelen), which for // codelen 8 reduces to (v >> 8) - b. Storing 2b makes that index b. const v: u32 = (@as(u32, @intCast(b)) * 2 << 8) | 0x80 | 8; std.mem.writeInt(u32, buf[off1 + b * 4 ..][0..4], v, .big); } return buf;}
fn buildCdic(gpa: std.mem.Allocator, phrases: []const TestPhrase) ![]u8 { var buf: std.ArrayList(u8) = .empty; errdefer buf.deinit(gpa);
const table_start = 16; const blobs_start = table_start + phrases.len * 2; try buf.appendNTimes(gpa, 0, blobs_start);
@memcpy(buf.items[0..4], "CDIC"); std.mem.writeInt(u32, buf.items[4..8], 16, .big); std.mem.writeInt(u32, buf.items[8..12], @intCast(phrases.len), .big); // 2^8 == 256 entries fit in this record, which is all the tests use. std.mem.writeInt(u32, buf.items[12..16], 8, .big);
for (phrases, 0..) |phrase, i| { const off = buf.items.len - table_start; std.mem.writeInt(u16, buf.items[table_start + i * 2 ..][0..2], @intCast(off), .big); const flag: u16 = if (phrase.terminal) 0x8000 else 0; try buf.appendNTimes(gpa, 0, 2); std.mem.writeInt(u16, buf.items[buf.items.len - 2 ..][0..2], flag | @as(u16, @intCast(phrase.bytes.len)), .big); try buf.appendSlice(gpa, phrase.bytes); } return buf.toOwnedSlice(gpa);}
/// Every byte value, so each phrase can borrow a one byte slice from it.const all_bytes: [256]u8 = blk: { var tmp: [256]u8 = undefined; for (&tmp, 0..) |*b, i| b.* = @intCast(i); break :blk tmp;};
/// The identity dictionary: phrase `b` is the single byte `b`.fn identityPhrases() [256]TestPhrase { var phrases: [256]TestPhrase = undefined; for (&phrases, 0..) |*p, i| p.* = .{ .bytes = all_bytes[i .. i + 1] }; return phrases;}
test "round trips a byte stream through terminal phrases" { const gpa = testing.allocator; const huff = try buildHuff(gpa); defer gpa.free(huff); const phrases = identityPhrases(); const cdic = try buildCdic(gpa, &phrases); defer gpa.free(cdic);
var decoder = try Decoder.init(gpa, huff, &.{cdic}); defer decoder.deinit();
const out = try decoder.decompress("Hello, MOBI!"); defer gpa.free(out); try testing.expectEqualStrings("Hello, MOBI!", out);}
test "expands and caches a non-terminal phrase" { const gpa = testing.allocator; const huff = try buildHuff(gpa); defer gpa.free(huff);
var phrases = identityPhrases(); // 'Z' becomes a nested stream that itself decodes to "abc". phrases['Z'] = .{ .bytes = "abc", .terminal = false }; const cdic = try buildCdic(gpa, &phrases); defer gpa.free(cdic);
var decoder = try Decoder.init(gpa, huff, &.{cdic}); defer decoder.deinit();
const out = try decoder.decompress("xZyZ"); defer gpa.free(out); try testing.expectEqualStrings("xabcyabc", out); // The second use must come from the cache, not a second expansion. try testing.expect(decoder.phrases['Z'].decoded != null);}
test "a self-referential phrase terminates instead of recursing forever" { const gpa = testing.allocator; const huff = try buildHuff(gpa); defer gpa.free(huff);
var phrases = identityPhrases(); phrases['Q'] = .{ .bytes = "Q", .terminal = false }; const cdic = try buildCdic(gpa, &phrases); defer gpa.free(cdic);
var decoder = try Decoder.init(gpa, huff, &.{cdic}); defer decoder.deinit();
const out = try decoder.decompress("aQb"); defer gpa.free(out); try testing.expectEqualStrings("ab", out);}
test "rejects malformed records" { const gpa = testing.allocator; try testing.expectError(error.InvalidHuffRecord, Decoder.init(gpa, "not a huff record", &.{}));
const huff = try buildHuff(gpa); defer gpa.free(huff); try testing.expectError(error.InvalidCdicRecord, Decoder.init(gpa, huff, &.{"nope"}));}