mary.my.id
streaming RAR extractor
jsr.io/@mary/rar
jsr
1/**
2 * @module
3 *
4 * the RAR1.5 - RAR4 ("RAR3", "v29") LZSS decompressor. RAR3 wraps an LZ77
5 * scheme with canonical Huffman coding and a small set of pre-defined VM
6 * filters (x86, audio, RGB, etc.). this implementation handles the LZSS
7 * codec end to end; the PPMd-H mode used by some `best` (method 0x35)
8 * archives and the VM filter program format are recognized but not yet
9 * supported.
10 *
11 * written from an understanding of libarchive's RAR3 reader; not a port
12 * of RARLAB's unrar.
13 */
14
15import { crc32 } from '@mary/crc32';
16
17import { ChecksumMismatchError, MalformedArchiveError, UnsupportedFeatureError } from '../errors.ts';
18
19import type { StreamReader } from '../utils/stream-reader.ts';
20import { PPMD_CORRUPT, PPMD_END_OF_DATA, type PpmdByteIn, RAR3PpmdModel } from './ppmd.ts';
21
22// #region constants
23
24// the four Huffman tables that drive the LZSS engine: literals + base
25// length/offset selectors (`main`), separate offset and length extra-bit
26// selectors, and the "low offset" table used for distances above 16 MB.
27const MAIN_CODE_SIZE = 299;
28const OFFSET_CODE_SIZE = 60;
29const LOW_OFFSET_CODE_SIZE = 17;
30const LENGTH_CODE_SIZE = 28;
31const HUFFMAN_TABLE_SIZE = MAIN_CODE_SIZE + OFFSET_CODE_SIZE + LOW_OFFSET_CODE_SIZE + LENGTH_CODE_SIZE;
32
33// the 20-symbol precode that describes the four main tables' bit lengths.
34const PRECODE_SIZE = 20;
35
36// every code length is in 0..15.
37const MAX_SYMBOL_LENGTH = 15;
38
39// the largest dictionary size RAR3 allows (4 MiB). the window is sized at
40// or above the largest match distance the stream can encode.
41const MAX_DICTIONARY = 0x400000;
42
43// length-code base values and the number of extra bits to read.
44const LENGTH_BASES = new Uint8Array([
45 0,
46 1,
47 2,
48 3,
49 4,
50 5,
51 6,
52 7,
53 8,
54 10,
55 12,
56 14,
57 16,
58 20,
59 24,
60 28,
61 32,
62 40,
63 48,
64 56,
65 64,
66 80,
67 96,
68 112,
69 128,
70 160,
71 192,
72 224,
73]);
74const LENGTH_EXTRA_BITS = new Uint8Array([
75 0,
76 0,
77 0,
78 0,
79 0,
80 0,
81 0,
82 0,
83 1,
84 1,
85 1,
86 1,
87 2,
88 2,
89 2,
90 2,
91 3,
92 3,
93 3,
94 3,
95 4,
96 4,
97 4,
98 4,
99 5,
100 5,
101 5,
102 5,
103]);
104
105// offset-code base values and the number of extra bits to read.
106const OFFSET_BASES = new Uint32Array([
107 0,
108 1,
109 2,
110 3,
111 4,
112 6,
113 8,
114 12,
115 16,
116 24,
117 32,
118 48,
119 64,
120 96,
121 128,
122 192,
123 256,
124 384,
125 512,
126 768,
127 1024,
128 1536,
129 2048,
130 3072,
131 4096,
132 6144,
133 8192,
134 12288,
135 16384,
136 24576,
137 32768,
138 49152,
139 65536,
140 98304,
141 131072,
142 196608,
143 262144,
144 327680,
145 393216,
146 458752,
147 524288,
148 589824,
149 655360,
150 720896,
151 786432,
152 851968,
153 917504,
154 983040,
155 1048576,
156 1310720,
157 1572864,
158 1835008,
159 2097152,
160 2359296,
161 2621440,
162 2883584,
163 3145728,
164 3407872,
165 3670016,
166 3932160,
167]);
168const OFFSET_EXTRA_BITS = new Uint8Array([
169 0,
170 0,
171 0,
172 0,
173 1,
174 1,
175 2,
176 2,
177 3,
178 3,
179 4,
180 4,
181 5,
182 5,
183 6,
184 6,
185 7,
186 7,
187 8,
188 8,
189 9,
190 9,
191 10,
192 10,
193 11,
194 11,
195 12,
196 12,
197 13,
198 13,
199 14,
200 14,
201 15,
202 15,
203 16,
204 16,
205 16,
206 16,
207 16,
208 16,
209 16,
210 16,
211 16,
212 16,
213 16,
214 16,
215 16,
216 16,
217 18,
218 18,
219 18,
220 18,
221 18,
222 18,
223 18,
224 18,
225 18,
226 18,
227 18,
228 18,
229]);
230
231// short-match base offsets and extra bits, used by main symbols 263-270.
232// short matches always have length 2.
233const SHORT_BASES = new Uint8Array([0, 4, 8, 16, 32, 64, 128, 192]);
234const SHORT_EXTRA_BITS = new Uint8Array([2, 2, 3, 4, 5, 6, 6, 6]);
235
236// #endregion
237
238// #region bit reader
239
240// an MSB-first bit reader over a forward-only buffer. RAR3 feeds the reader
241// in 64 KiB - 1 MiB chunks; we keep a `Uint8Array` buffer that the caller
242// extends and rotate the byte position + intra-byte bit index in lockstep.
243// peek16/peek32 read up to 4 bytes ahead, so the backing buffer needs at
244// least 8 zero-padding bytes past the last meaningful byte.
245class BitReader {
246 #data: Uint8Array;
247 /** byte offset of the next unread bit */
248 addr = 0;
249 /** bit offset within that byte, 0 through 7 */
250 bit = 0;
251
252 constructor(data: Uint8Array) {
253 this.#data = data;
254 }
255
256 /** swaps the backing buffer, keeping the current addr/bit position. */
257 rebind(data: Uint8Array): void {
258 this.#data = data;
259 }
260
261 get data(): Uint8Array {
262 return this.#data;
263 }
264
265 /** the next 16 bits, without consuming them. */
266 peek16(): number {
267 const p = this.#data;
268 const a = this.addr;
269 const bits = (p[a] << 16) | (p[a + 1] << 8) | p[a + 2];
270 return (bits >>> (8 - this.bit)) & 0xffff;
271 }
272
273 /** the next 32 bits, without consuming them. */
274 peek32(): number {
275 const p = this.#data;
276 const a = this.addr;
277 const bits = ((p[a] << 24) | (p[a + 1] << 16) | (p[a + 2] << 8) | p[a + 3]) >>> 0;
278 if (this.bit === 0) {
279 return bits;
280 }
281 return ((bits << this.bit) | (p[a + 4] >>> (8 - this.bit))) >>> 0;
282 }
283
284 skip(count: number): void {
285 const total = this.bit + count;
286 this.addr += total >> 3;
287 this.bit = total & 7;
288 }
289
290 read(count: number): number {
291 if (count === 0) {
292 return 0;
293 }
294 if (count <= 16) {
295 const value = this.peek16() >>> (16 - count);
296 this.skip(count);
297 return value;
298 }
299 // values up to 32 bits are needed for the offset-bits high group.
300 const high = this.read(count - 16);
301 const low = this.read(16);
302 return high * 0x10000 + low;
303 }
304
305 /** rounds addr/bit up to the next byte boundary. */
306 alignByte(): void {
307 if (this.bit !== 0) {
308 this.addr++;
309 this.bit = 0;
310 }
311 }
312}
313
314// #endregion
315
316// #region huffman
317
318// a decoded canonical Huffman table. `decodeLen[k]` is `count[k] << (16 - k)`
319// where `count[k]` runs over all symbols of length k or less; `decodePos[k]`
320// is the running offset into `symbols` where length-k codes begin. quick is a
321// flat lookup that resolves any code whose length is <= QUICK_BITS in one
322// peek; the slow path falls through to the per-length comparison.
323const QUICK_BITS = 10;
324const QUICK_SIZE = 1 << QUICK_BITS;
325
326interface HuffmanTable {
327 size: number;
328 decodeLen: Int32Array;
329 decodePos: Uint32Array;
330 symbols: Uint16Array;
331 quickLen: Uint8Array;
332 quickSym: Uint16Array;
333}
334
335// builds a canonical Huffman decode table from per-symbol code lengths.
336const createTable = (lengths: Uint8Array, size: number): HuffmanTable => {
337 const counts = new Uint32Array(MAX_SYMBOL_LENGTH + 1);
338 for (let idx = 0; idx < size; idx++) {
339 const len = lengths[idx];
340 if (len > MAX_SYMBOL_LENGTH) {
341 throw new MalformedArchiveError(
342 `RAR3 Huffman code length out of range: ${len} > ${MAX_SYMBOL_LENGTH}`,
343 );
344 }
345 counts[len]++;
346 }
347 counts[0] = 0;
348
349 const decodeLen = new Int32Array(MAX_SYMBOL_LENGTH + 1);
350 const decodePos = new Uint32Array(MAX_SYMBOL_LENGTH + 1);
351
352 let upperLimit = 0;
353 for (let len = 1; len <= MAX_SYMBOL_LENGTH; len++) {
354 upperLimit += counts[len];
355 decodeLen[len] = upperLimit << (16 - len);
356 decodePos[len] = decodePos[len - 1] + counts[len - 1];
357 upperLimit <<= 1;
358 }
359 if (upperLimit > 65536) {
360 throw new MalformedArchiveError('over-subscribed RAR3 Huffman table');
361 }
362
363 const symbols = new Uint16Array(size);
364 {
365 const cursor = decodePos.slice();
366 for (let idx = 0; idx < size; idx++) {
367 const len = lengths[idx];
368 if (len > 0) {
369 symbols[cursor[len]++] = idx;
370 }
371 }
372 }
373
374 const quickLen = new Uint8Array(QUICK_SIZE);
375 const quickSym = new Uint16Array(QUICK_SIZE);
376 let len = 1;
377 for (let code = 0; code < QUICK_SIZE; code++) {
378 const field = code << (16 - QUICK_BITS);
379 while (len <= MAX_SYMBOL_LENGTH && field >= decodeLen[len]) {
380 len++;
381 }
382 if (len > MAX_SYMBOL_LENGTH) {
383 quickLen[code] = MAX_SYMBOL_LENGTH;
384 quickSym[code] = 0;
385 continue;
386 }
387 quickLen[code] = len;
388 const position = decodePos[len] + ((field - decodeLen[len - 1]) >>> (16 - len));
389 quickSym[code] = position < size ? symbols[position] : 0;
390 }
391
392 return { decodeLen, decodePos, quickLen, quickSym, size, symbols };
393};
394
395// decodes one symbol from the bit stream using a decode table.
396const decodeSymbol = (table: HuffmanTable, bits: BitReader): number => {
397 const field = bits.peek16();
398
399 if (field < table.decodeLen[QUICK_BITS]) {
400 const code = field >>> (16 - QUICK_BITS);
401 bits.skip(table.quickLen[code]);
402 return table.quickSym[code];
403 }
404
405 let length = MAX_SYMBOL_LENGTH;
406 for (let candidate = QUICK_BITS + 1; candidate < MAX_SYMBOL_LENGTH; candidate++) {
407 if (field < table.decodeLen[candidate]) {
408 length = candidate;
409 break;
410 }
411 }
412
413 bits.skip(length);
414
415 const position = table.decodePos[length] +
416 ((field - table.decodeLen[length - 1]) >>> (16 - length));
417 return table.symbols[position >= table.size ? 0 : position];
418};
419
420// #endregion
421
422// #region table parsing
423
424interface Tables {
425 main: HuffmanTable;
426 offset: HuffmanTable;
427 lowOffset: HuffmanTable;
428 length: HuffmanTable;
429}
430
431// the decision a parseCodes call hands back to the decoder loop: either a
432// fresh set of Huffman tables (LZSS mode) or the parameters needed to
433// initialise or refresh the PPMd-H model.
434type CodeMode =
435 | { kind: 'huffman'; tables: Tables }
436 | {
437 kind: 'ppmd';
438 /** present only on a "full reinit" block; the model is rebuilt with these */
439 init?: { dictSize: number; maxorder: number };
440 /** escape symbol value the decoder loop watches for */
441 escape: number;
442 };
443
444// reads the four Huffman tables that drive the LZSS engine. `lengthtable`
445// carries the per-symbol bit lengths across calls because RAR3 supports a
446// "keep existing tables" mode: a 1 bit means amend the running table by the
447// (signed-4-bit-delta-style) precode output; a 0 bit means start fresh from
448// all zeros.
449const parseCodes = (
450 bits: BitReader,
451 lengthTable: Uint8Array,
452): CodeMode => {
453 bits.alignByte();
454
455 const ppmd = bits.read(1) !== 0;
456 if (ppmd) {
457 // PPMd-H block — 7 flag bits, then optionally dict size (8 bits) and
458 // escape symbol (8 bits). flag bit 0x20 means "full reinit" (read dict
459 // size + max order); without it we reuse the existing PPMd model but
460 // still reinitialise the range decoder.
461 const flags = bits.read(7);
462 let dictSize: number | undefined;
463 if ((flags & 0x20) !== 0) {
464 dictSize = (bits.read(8) + 1) << 20;
465 }
466 let escape = 2;
467 if ((flags & 0x40) !== 0) {
468 escape = bits.read(8);
469 }
470 if ((flags & 0x20) !== 0) {
471 let maxorder = (flags & 0x1f) + 1;
472 if (maxorder > 16) {
473 maxorder = 16 + (maxorder - 16) * 3;
474 }
475 if (maxorder < 2) {
476 throw new MalformedArchiveError(`RAR3 PPMd max order out of range: ${maxorder}`);
477 }
478 return { escape, init: { dictSize: dictSize!, maxorder }, kind: 'ppmd' };
479 }
480 return { escape, kind: 'ppmd' };
481 }
482
483 const keepExisting = bits.read(1) !== 0;
484 if (!keepExisting) {
485 lengthTable.fill(0);
486 }
487
488 // stage 1: 20 nibble-packed precode lengths with a 0xF escape used both
489 // for the literal length 15 (when the next nibble is 0) and for a run of
490 // zero lengths (when the next nibble is non-zero).
491 const precodeLengths = new Uint8Array(PRECODE_SIZE);
492 for (let idx = 0; idx < PRECODE_SIZE;) {
493 const value = bits.read(4);
494 if (value !== 0xf) {
495 precodeLengths[idx++] = value;
496 continue;
497 }
498 const run = bits.read(4);
499 if (run === 0) {
500 precodeLengths[idx++] = 0xf;
501 } else {
502 for (let j = 0; j < run + 2 && idx < PRECODE_SIZE; j++) {
503 precodeLengths[idx++] = 0;
504 }
505 }
506 }
507 const precode = createTable(precodeLengths, PRECODE_SIZE);
508
509 // stage 2: walk the precode, applying its symbols to `lengthTable`.
510 // symbols 0-15 add to the running length (mod 16); 16/17 repeat the
511 // previous length for 3 + 3-bit (16) or 11 + 7-bit (17) entries; 18/19
512 // emit a run of zero lengths with the same two run-length encodings.
513 for (let idx = 0; idx < HUFFMAN_TABLE_SIZE;) {
514 const symbol = decodeSymbol(precode, bits);
515
516 if (symbol < 16) {
517 lengthTable[idx] = (lengthTable[idx] + symbol) & 0xf;
518 idx++;
519 } else if (symbol < 18) {
520 if (idx === 0) {
521 throw new MalformedArchiveError('RAR3 Huffman table repeat with no previous length');
522 }
523 const run = symbol === 16 ? bits.read(3) + 3 : bits.read(7) + 11;
524 const prev = lengthTable[idx - 1];
525 for (let j = 0; j < run && idx < HUFFMAN_TABLE_SIZE; j++) {
526 lengthTable[idx++] = prev;
527 }
528 } else {
529 const run = symbol === 18 ? bits.read(3) + 3 : bits.read(7) + 11;
530 for (let j = 0; j < run && idx < HUFFMAN_TABLE_SIZE; j++) {
531 lengthTable[idx++] = 0;
532 }
533 }
534 }
535
536 const main = createTable(lengthTable.subarray(0, MAIN_CODE_SIZE), MAIN_CODE_SIZE);
537 const offset = createTable(
538 lengthTable.subarray(MAIN_CODE_SIZE, MAIN_CODE_SIZE + OFFSET_CODE_SIZE),
539 OFFSET_CODE_SIZE,
540 );
541 const lowOffset = createTable(
542 lengthTable.subarray(
543 MAIN_CODE_SIZE + OFFSET_CODE_SIZE,
544 MAIN_CODE_SIZE + OFFSET_CODE_SIZE + LOW_OFFSET_CODE_SIZE,
545 ),
546 LOW_OFFSET_CODE_SIZE,
547 );
548 const length = createTable(
549 lengthTable.subarray(MAIN_CODE_SIZE + OFFSET_CODE_SIZE + LOW_OFFSET_CODE_SIZE),
550 LENGTH_CODE_SIZE,
551 );
552
553 return { kind: 'huffman', tables: { length, lowOffset, main, offset } };
554};
555
556// #endregion
557
558// #region filters
559
560// VM memory layout matches libarchive's PROGRAM_WORK_SIZE / VM_MEMORY_SIZE.
561// the filter source bytes go in `[0, blockLength)` and the standard filters
562// either rewrite in place (e8/e8e9) or write the result into
563// `[blockLength, 2*blockLength)`. the upper bound (256 KiB) caps the
564// per-filter range; archives that exceed it are malformed.
565const VM_MEMORY_SIZE = 0x40000;
566const PROGRAM_SYSTEM_GLOBAL_ADDRESS = 0x3c000;
567
568// the standard RAR3 filter programs that ship with WinRAR. each entry's
569// fingerprint is `(byteLength, crc32(bytecode))`; libarchive packs both into
570// a uint64 (`length << 32 | crc`) for the same purpose.
571const enum FilterKind {
572 Audio,
573 Delta,
574 E8,
575 E8E9,
576 Rgb,
577 Unknown,
578}
579
580const FILTER_FINGERPRINTS = new Map<string, FilterKind>([
581 [`29:${(0x0e06077d).toString(16)}`, FilterKind.Delta],
582 [`53:${(0xad576887).toString(16)}`, FilterKind.E8],
583 [`57:${(0x3cd7e57e).toString(16)}`, FilterKind.E8E9],
584 [`149:${(0x1c2c5dc8).toString(16)}`, FilterKind.Rgb],
585 [`216:${(0xbc85e701).toString(16)}`, FilterKind.Audio],
586]);
587
588const fingerprint = (bytecode: Uint8Array): FilterKind => {
589 const key = `${bytecode.length}:${crc32(bytecode).toString(16)}`;
590 return FILTER_FINGERPRINTS.get(key) ?? FilterKind.Unknown;
591};
592
593const readLe32 = (data: Uint8Array, offset: number): number => {
594 return (data[offset] | (data[offset + 1] << 8) | (data[offset + 2] << 16) |
595 (data[offset + 3] << 24)) >>> 0;
596};
597
598const writeLe32 = (data: Uint8Array, offset: number, value: number): void => {
599 data[offset] = value;
600 data[offset + 1] = value >>> 8;
601 data[offset + 2] = value >>> 16;
602 data[offset + 3] = value >>> 24;
603};
604
605// reads one byte from the LZSS bit stream. unlike the main `bits.read(8)`
606// path this aligns to 8 bits exactly, matching libarchive's
607// `rar_decode_byte` helper used by the filter reader.
608const readByte = (bits: BitReader): number => bits.read(8);
609
610// consumes a single VM-style variable-length number from a byte buffer using
611// a memory bit reader. matches libarchive's `membr_next_rarvm_number`.
612class MemoryBitReader {
613 #data: Uint8Array;
614 #bit = 0; // total bits consumed
615
616 constructor(data: Uint8Array) {
617 this.#data = data;
618 }
619
620 bits(count: number): number {
621 let value = 0;
622 for (let idx = 0; idx < count; idx++) {
623 const byteIndex = this.#bit >>> 3;
624 const bitIndex = 7 - (this.#bit & 7);
625 const bit = byteIndex < this.#data.length ? (this.#data[byteIndex] >>> bitIndex) & 1 : 0;
626 value = (value << 1) | bit;
627 this.#bit++;
628 }
629 return value;
630 }
631
632 number(): number {
633 const tag = this.bits(2);
634 if (tag === 0) {
635 return this.bits(4);
636 }
637 if (tag === 1) {
638 const high = this.bits(8);
639 if (high >= 16) {
640 return high;
641 }
642 // libarchive `membr_next_rarvm_number` sign-extends low-high values
643 // by OR-ing 0xFFFFFF00 into the 12-bit composite, producing a
644 // negative int32 for high<16. blockstart/blocklength consumers
645 // rely on the resulting negative offset.
646 return (0xffffff00 | (high << 4) | this.bits(4)) | 0;
647 }
648 if (tag === 2) {
649 return this.bits(16);
650 }
651 // 32-bit values overflow JS bitwise math, but in practice they only
652 // appear for register overrides — read as two 16-bit halves and
653 // combine through arithmetic.
654 const hi = this.bits(16);
655 const lo = this.bits(16);
656 return hi * 0x10000 + lo;
657 }
658}
659
660// a compiled (well, fingerprinted) filter program. the program list lives on
661// the decoder state and is referenced by index in subsequent filter commands.
662interface FilterProgram {
663 kind: FilterKind;
664 usageCount: number;
665 oldFilterLength: number;
666}
667
668// a queued filter: its parsed parameters plus a pointer to the program. the
669// LZSS engine emits its filter list one at a time as the LZ output catches up
670// to each `blockStart`.
671interface PendingFilter {
672 prog: FilterProgram;
673 /** in monotonic write coordinates (shared across the solid run). */
674 blockStart: number;
675 blockLength: number;
676 /** registers[0..7]; non-zero entries come from the filter command. */
677 registers: Uint32Array;
678}
679
680// the slice of decoder state that {@link parseFilterCommand} mutates.
681interface Rar3DecoderState {
682 programs: (FilterProgram | undefined)[];
683 lastFilterNum: number;
684 stack: PendingFilter[];
685}
686
687// reads one full filter command off the LZSS bit stream, enrolling its program
688// in the decoder state on first sight and pushing a {@link PendingFilter} onto
689// the stack. the program bytecode is fingerprinted against the standard
690// WinRAR filter set; archives carrying a custom program raise an error at
691// execute time (parse still succeeds so the LZSS bit stream stays in sync).
692//
693// the filter payload can be up to ~65 KiB long, far beyond the 16-byte refill
694// cushion the main LZSS loop maintains. `ensureBytes` is the same refill
695// closure the loop uses, called here to enlarge the bit reader's backing
696// buffer before each composite read.
697const parseFilterCommand = async (
698 bits: BitReader,
699 state: Rar3DecoderState,
700 lzssPosition: number,
701 windowSize: number,
702 ensureBytes: (count: number) => Promise<void>,
703): Promise<void> => {
704 // flags + up to a 2-byte extended length prefix.
705 await ensureBytes(3);
706 const flags = readByte(bits);
707
708 // libarchive: length = (flags & 7) + 1, with 7 and 8 extending it.
709 let length = (flags & 0x07) + 1;
710 if (length === 7) {
711 length = readByte(bits) + 7;
712 } else if (length === 8) {
713 const high = readByte(bits);
714 const low = readByte(bits);
715 length = (high << 8) | low;
716 }
717
718 // the program bytecode is `length` bytes; reserve extra cushion so the
719 // next LZSS loop iteration's peek16/peek32 stays in-buffer too.
720 await ensureBytes(length + 16);
721
722 const code = new Uint8Array(length);
723 for (let idx = 0; idx < length; idx++) {
724 code[idx] = readByte(bits);
725 }
726
727 const mbr = new MemoryBitReader(code);
728
729 let progIndex: number;
730 if (flags & 0x80) {
731 const num = mbr.number();
732 if (num === 0) {
733 state.programs.length = 0;
734 state.stack.length = 0;
735 progIndex = 0;
736 } else {
737 progIndex = num - 1;
738 }
739 if (progIndex > state.programs.length) {
740 throw new MalformedArchiveError(
741 `RAR3 filter command references program past list end: ${progIndex}`,
742 );
743 }
744 state.lastFilterNum = progIndex;
745 } else {
746 progIndex = state.lastFilterNum;
747 }
748 let prog = state.programs[progIndex];
749
750 // blockStart is signed (small-magnitude values come back negative through
751 // `mbr.number`'s sign extension) and adds onto the current LZSS write
752 // position; flag 0x40 bumps it by 258 (the "long form").
753 let blockStart = mbr.number() + lzssPosition;
754 if (flags & 0x40) {
755 blockStart += 258;
756 }
757
758 let blockLength: number;
759 if (flags & 0x20) {
760 blockLength = mbr.number();
761 } else {
762 blockLength = prog?.oldFilterLength ?? 0;
763 }
764
765 if (blockLength > windowSize || blockLength > VM_MEMORY_SIZE) {
766 throw new MalformedArchiveError(
767 `RAR3 filter block length exceeds window or VM cap: ${blockLength} (window ${windowSize})`,
768 );
769 }
770
771 // libarchive's parse_filter seeds the register file with the system
772 // global address, the block length, and the program usage count.
773 const registers = new Uint32Array(8);
774 registers[3] = PROGRAM_SYSTEM_GLOBAL_ADDRESS;
775 registers[4] = blockLength;
776 registers[5] = prog?.usageCount ?? 0;
777 registers[7] = VM_MEMORY_SIZE;
778
779 if (flags & 0x10) {
780 const mask = mbr.bits(7);
781 for (let idx = 0; idx < 7; idx++) {
782 if (mask & (1 << idx)) {
783 registers[idx] = mbr.number() >>> 0;
784 }
785 }
786 }
787
788 if (prog === undefined) {
789 const len = mbr.number();
790 if (len === 0 || len > 0x10000) {
791 throw new MalformedArchiveError(`RAR3 filter bytecode length out of range: ${len}`);
792 }
793 const bytecode = new Uint8Array(len);
794 for (let idx = 0; idx < len; idx++) {
795 bytecode[idx] = mbr.bits(8);
796 }
797 // the bytecode carries an XOR checksum in byte 0; libarchive uses it
798 // to reject corrupted programs before computing the fingerprint.
799 let xor = 0;
800 for (let idx = 1; idx < len; idx++) {
801 xor ^= bytecode[idx];
802 }
803 if (xor !== bytecode[0]) {
804 throw new ChecksumMismatchError('RAR3 filter bytecode XOR checksum mismatch');
805 }
806 prog = { kind: fingerprint(bytecode), oldFilterLength: 0, usageCount: 1 };
807 state.programs[progIndex] = prog;
808 } else {
809 prog.usageCount++;
810 }
811 prog.oldFilterLength = blockLength;
812
813 // optional global-data overlay. the standard filters don't consult it, so
814 // we just walk past the bits to keep the MemoryBitReader in sync.
815 if (flags & 0x08) {
816 const len = mbr.number();
817 for (let idx = 0; idx < len; idx++) {
818 mbr.bits(8);
819 }
820 }
821
822 state.stack.push({ blockLength, blockStart, prog, registers });
823};
824
825// transforms one filter's input bytes (`source`, taken from the window) into
826// the post-filter output. the standard executors are translated from
827// libarchive's `execute_filter_*` helpers.
828//
829// `entryPos` is the entry-relative offset where the filter's range begins; the
830// e8/e8e9 filter uses it as the base for its absolute-address rewrites, while
831// the others ignore it.
832const runFilter = (filter: PendingFilter, source: Uint8Array, entryPos: number): Uint8Array => {
833 const { blockLength, prog, registers } = filter;
834
835 switch (prog.kind) {
836 case FilterKind.Delta: {
837 const channels = registers[0];
838 if (channels === 0) {
839 throw new MalformedArchiveError('RAR3 delta filter with zero channels');
840 }
841 const result = new Uint8Array(blockLength);
842 let srcIdx = 0;
843 for (let ch = 0; ch < channels; ch++) {
844 let prev = 0;
845 for (let dst = ch; dst < blockLength; dst += channels) {
846 prev = (prev - source[srcIdx++]) & 0xff;
847 result[dst] = prev;
848 }
849 }
850 return result;
851 }
852 case FilterKind.E8:
853 case FilterKind.E8E9: {
854 const e9also = prog.kind === FilterKind.E8E9;
855 const fileSize = 0x1000000;
856 const out = new Uint8Array(blockLength);
857 out.set(source.subarray(0, blockLength));
858 if (blockLength <= 4) {
859 return out;
860 }
861 for (let i = 0; i + 5 <= blockLength;) {
862 const op = out[i];
863 if (op === 0xe8 || (e9also && op === 0xe9)) {
864 const currpos = (entryPos + i + 1) >>> 0;
865 const address = readLe32(out, i + 1) | 0;
866 if (address < 0 && currpos >= (-address >>> 0)) {
867 writeLe32(out, i + 1, (address + fileSize) >>> 0);
868 } else if (address >= 0 && address < fileSize) {
869 writeLe32(out, i + 1, (address - currpos) >>> 0);
870 }
871 i += 5;
872 } else {
873 i++;
874 }
875 }
876 return out;
877 }
878 case FilterKind.Rgb: {
879 const stride = registers[0];
880 const byteOffset = registers[1];
881 if (stride === 0 || stride > blockLength || blockLength < 3 || byteOffset > 2) {
882 throw new MalformedArchiveError('RAR3 RGB filter parameters invalid');
883 }
884 const result = new Uint8Array(blockLength);
885 let src = 0;
886 for (let i = 0; i < 3; i++) {
887 let byte = 0;
888 // `prev` walks the previous scanline; it starts negative for the
889 // first row (no prior data) and the predictor falls through.
890 let prev = i - stride;
891 for (let j = i; j < blockLength; j += 3) {
892 if (prev >= 0 && prev + 3 < blockLength) {
893 const a = result[prev + 3];
894 const b = result[prev];
895 const delta1 = Math.abs(a - b);
896 const delta2 = Math.abs(byte - b);
897 const delta3 = Math.abs(a - b + byte - b);
898 if (delta1 > delta2 || delta1 > delta3) {
899 byte = delta2 <= delta3 ? a : b;
900 }
901 }
902 byte = (byte - source[src++]) & 0xff;
903 result[j] = byte;
904 prev += 3;
905 }
906 }
907 for (let i = byteOffset; i + 2 < blockLength; i += 3) {
908 result[i] = (result[i] + result[i + 1]) & 0xff;
909 result[i + 2] = (result[i + 2] + result[i + 1]) & 0xff;
910 }
911 return result;
912 }
913 case FilterKind.Audio: {
914 const channels = registers[0];
915 if (channels === 0) {
916 throw new MalformedArchiveError('RAR3 audio filter with zero channels');
917 }
918 const result = new Uint8Array(blockLength);
919 let src = 0;
920 for (let ch = 0; ch < channels; ch++) {
921 const error = [0, 0, 0, 0, 0, 0, 0];
922 const weight = [0, 0, 0];
923 const delta = [0, 0, 0];
924 let lastByte = 0;
925 let lastDelta = 0;
926 let count = 0;
927 for (let j = ch; j < blockLength; j += channels) {
928 const deltaIn = (source[src++] << 24) >> 24; // int8
929 delta[2] = delta[1];
930 delta[1] = lastDelta - delta[0];
931 delta[0] = lastDelta;
932 const predicted = ((8 * lastByte +
933 weight[0] * delta[0] +
934 weight[1] * delta[1] +
935 weight[2] * delta[2]) >> 3) & 0xff;
936 const byte = (predicted - deltaIn) & 0xff;
937 const predError = deltaIn << 3;
938 error[0] += Math.abs(predError);
939 error[1] += Math.abs(predError - delta[0]);
940 error[2] += Math.abs(predError + delta[0]);
941 error[3] += Math.abs(predError - delta[1]);
942 error[4] += Math.abs(predError + delta[1]);
943 error[5] += Math.abs(predError - delta[2]);
944 error[6] += Math.abs(predError + delta[2]);
945 lastDelta = (byte - lastByte) << 24 >> 24; // int8 wrap
946 lastByte = byte;
947 result[j] = byte;
948 if ((count++ & 0x1f) === 0) {
949 let idx = 0;
950 for (let k = 1; k < 7; k++) {
951 if (error[k] < error[idx]) {
952 idx = k;
953 }
954 }
955 error.fill(0);
956 switch (idx) {
957 case 1:
958 if (weight[0] >= -16) weight[0]--;
959 break;
960 case 2:
961 if (weight[0] < 16) weight[0]++;
962 break;
963 case 3:
964 if (weight[1] >= -16) weight[1]--;
965 break;
966 case 4:
967 if (weight[1] < 16) weight[1]++;
968 break;
969 case 5:
970 if (weight[2] >= -16) weight[2]--;
971 break;
972 case 6:
973 if (weight[2] < 16) weight[2]++;
974 break;
975 }
976 }
977 }
978 }
979 return result;
980 }
981 case FilterKind.Unknown: {
982 throw new UnsupportedFeatureError('RAR3 filter program not in the standard set');
983 }
984 }
985};
986
987// #endregion
988
989// #region decoder
990
991/**
992 * receives decoded chunks as they settle. a sink that returns a promise
993 * pauses the decoder until the promise resolves, providing backpressure.
994 */
995export type DecodeSink = (chunk: Uint8Array<ArrayBuffer>) => void | Promise<void>;
996
997/**
998 * a stateful RAR3 LZSS decoder.
999 *
1000 * one instance carries the sliding window, repeat-distance cache, last match
1001 * length, last low-offset, Huffman length table and tables themselves, the bit
1002 * reader, and the VM filter list across calls. consecutive
1003 * {@link Rar3Decoder.decode} calls represent the entries of a solid run
1004 * sharing one state.
1005 *
1006 * filter execution covers the standard WinRAR programs (e8, e8e9, delta, rgb,
1007 * audio); archives carrying a custom bytecode raise an "unknown filter
1008 * program" error when the filter would execute.
1009 */
1010export class Rar3Decoder {
1011 /** the maximum window size implied by the file header's dictionary flag,
1012 * rounded up to a power of two. matches with distance up to this value can
1013 * appear in the bit stream. */
1014 readonly #targetSize: number;
1015 /** the actually-allocated window. starts at zero length and grows toward
1016 * `#targetSize` only when an entry's expected output (or accumulated solid
1017 * history) requires more. for small archives the window never reaches
1018 * `#targetSize`, sparing a multi-megabyte allocation up front. */
1019 #window: Uint8Array = new Uint8Array(0);
1020 #windowMask = 0;
1021
1022 /** four-deep LRU of recent match distances, oldest at index 3. */
1023 #oldOffsets: [number, number, number, number] = [0, 0, 0, 0];
1024 #lastOffset = 0;
1025 #lastLength = 0;
1026 #lastLowOffset = 0;
1027 #lowOffsetRepeats = 0;
1028
1029 /** monotonic count of bytes ever written to the window. */
1030 #write = 0;
1031
1032 /** running bit lengths used by `keep-existing-tables` (precode) mode. */
1033 readonly #lengthTable = new Uint8Array(HUFFMAN_TABLE_SIZE);
1034 #tables?: Tables;
1035 /** set when the previous entry left a `start new table` marker in flight. */
1036 #startNewTable = true;
1037 /**
1038 * PPMd-H state carried across solid-run entries. lifetime mirrors `#tables`
1039 * — re-set at every block boundary based on what `parseCodes` returns.
1040 */
1041 #ppmd?: { model: RAR3PpmdModel; escape: number };
1042 /** filter program list and pending filter queue, shared across the solid run. */
1043 readonly #filterState: Rar3DecoderState = { lastFilterNum: 0, programs: [], stack: [] };
1044 /**
1045 * filters whose range is fully written and whose post-filter bytes are
1046 * computed, waiting to be overlaid on top of the emit chunks they cover.
1047 * keyed by the filter's `blockStart` in write-pointer coordinates.
1048 */
1049 readonly #ready = new Map<number, Uint8Array>();
1050
1051 /**
1052 * @param dictionarySize the dictionary size declared by the file header.
1053 * the window is rounded up to the next power of two but never above the
1054 * RAR3 cap of 4 MiB.
1055 */
1056 constructor(dictionarySize: number) {
1057 let target = 1;
1058 while (target < dictionarySize) {
1059 target <<= 1;
1060 }
1061 if (target === 0 || target > MAX_DICTIONARY) {
1062 target = MAX_DICTIONARY;
1063 }
1064 this.#targetSize = target;
1065 }
1066
1067 /** the dictionary capacity this decoder was sized for. the underlying
1068 * window may currently be smaller (lazy-allocated to fit decoded content),
1069 * but matches with distances up to this value are guaranteed handlable. */
1070 get windowSize(): number {
1071 return this.#targetSize;
1072 }
1073
1074 /**
1075 * ensures the window can hold at least `neededWrite` bytes contiguously
1076 * (no circular wraparound), up to `#targetSize`. on growth, existing
1077 * contents at positions `[0, #write)` are preserved one-to-one — this is
1078 * safe because we only grow while still in the no-wrap regime where every
1079 * byte sits at its logical address.
1080 */
1081 #ensureCapacity(neededWrite: number): void {
1082 const current = this.#window.length;
1083 if (current >= this.#targetSize) {
1084 return;
1085 }
1086 if (current >= neededWrite) {
1087 return;
1088 }
1089 let cap = current === 0 ? 1 : current;
1090 while (cap < neededWrite) {
1091 cap <<= 1;
1092 }
1093 if (cap > this.#targetSize) {
1094 cap = this.#targetSize;
1095 }
1096 const grown = new Uint8Array(cap);
1097 if (this.#write > 0) {
1098 grown.set(this.#window.subarray(0, this.#write));
1099 }
1100 this.#window = grown;
1101 this.#windowMask = cap - 1;
1102 }
1103
1104 /**
1105 * resets the carry-over state so this decoder can be driven for a fresh
1106 * non-solid entry without reallocating the multi-megabyte window. clears
1107 * write position, distance cache, Huffman tables, PPMd state, and filter
1108 * queue; the window bytes themselves are left intact (LZ matches can only
1109 * reference positions in `[0, write)`, so stale bytes are unreachable).
1110 */
1111 reset(): void {
1112 this.#oldOffsets = [0, 0, 0, 0];
1113 this.#lastOffset = 0;
1114 this.#lastLength = 0;
1115 this.#lastLowOffset = 0;
1116 this.#lowOffsetRepeats = 0;
1117 this.#write = 0;
1118 this.#lengthTable.fill(0);
1119 this.#tables = undefined;
1120 this.#startNewTable = true;
1121 this.#ppmd = undefined;
1122 this.#filterState.lastFilterNum = 0;
1123 this.#filterState.programs.length = 0;
1124 this.#filterState.stack.length = 0;
1125 this.#ready.clear();
1126 }
1127
1128 /**
1129 * decodes the data area of one RAR3 file entry, appending its bytes to the
1130 * shared window and emitting decoded chunks to `sink` as they settle.
1131 *
1132 * compressed bytes are pulled from `input` in 64 KiB blocks. across a
1133 * solid run, the Huffman tables, distance cache, and pending filter list
1134 * carry over so the next entry's first symbols can reference them.
1135 *
1136 * filter commands (symbol 257) are parsed, their programs are fingerprinted
1137 * against the standard WinRAR filter set, and they execute when their range
1138 * is fully written — the resulting post-filter bytes overlay the raw LZ
1139 * output before reaching the sink.
1140 *
1141 * @param input compressed bytes of the entry's data area, in order
1142 * @param unpackedSize the expected uncompressed size
1143 * @param sink receives each decoded chunk in order
1144 * @throws if the stream is invalid, requests PPMd, or carries a filter
1145 * program outside the standard set
1146 */
1147 async decode(input: StreamReader, unpackedSize: number, sink: DecodeSink): Promise<void> {
1148 // size the window to fit this entry's output (plus any accumulated
1149 // solid-run history), capped at the declared dictionary target. this
1150 // is the only point growth can happen — after this the locals below
1151 // pin the buffer for the entry.
1152 this.#ensureCapacity(this.#write + unpackedSize);
1153
1154 const mask = this.#windowMask;
1155 const window = this.#window;
1156 const windowSize = window.length;
1157 const startWrite = this.#write;
1158 const targetWrite = startWrite + unpackedSize;
1159
1160 // the longest single LZ copy is ~260 bytes (length base 224 + 31 extra
1161 // + base bumps); leave generous headroom so periodic flushing always
1162 // runs before the next iteration could overwrite unflushed window data.
1163 // when the window grew exactly to fit this entry (still below the
1164 // declared cap), writes won't wrap, so unflushed bytes are safe — set
1165 // the threshold past `targetWrite` to disable mid-flushing entirely.
1166 const FLUSH_MARGIN = 512;
1167 const FLUSH_HIGH_WATER = targetWrite > windowSize ? windowSize - FLUSH_MARGIN : unpackedSize + 1;
1168
1169 let emitted = startWrite;
1170
1171 // for any pending filter whose range is now complete, stage the source
1172 // bytes from the window and run the filter (chaining when consecutive
1173 // filters share the same blockStart/blockLength). filtered bytes land
1174 // in `#ready` keyed by blockStart so the next emit can overlay them.
1175 const tryRunFilters = (): void => {
1176 const stillPending: PendingFilter[] = [];
1177 let lastFiltered: Uint8Array | undefined;
1178 let lastBlockStart = -1;
1179 let lastBlockLength = -1;
1180 for (const f of this.#filterState.stack) {
1181 const end = f.blockStart + f.blockLength;
1182 if (this.#write < end) {
1183 stillPending.push(f);
1184 continue;
1185 }
1186 if (f.blockStart < emitted) {
1187 throw new MalformedArchiveError(
1188 'RAR3 filter range begins before already-emitted bytes',
1189 );
1190 }
1191 let source: Uint8Array;
1192 if (
1193 f.blockStart === lastBlockStart && f.blockLength === lastBlockLength &&
1194 lastFiltered !== undefined
1195 ) {
1196 // chained: same range as the previous filter, source is its output.
1197 source = lastFiltered;
1198 } else {
1199 source = new Uint8Array(f.blockLength);
1200 // monotonic range in the circular window — at most one wrap.
1201 const startInWindow = f.blockStart & mask;
1202 if (startInWindow + f.blockLength <= windowSize) {
1203 source.set(window.subarray(startInWindow, startInWindow + f.blockLength));
1204 } else {
1205 const partA = windowSize - startInWindow;
1206 source.set(window.subarray(startInWindow));
1207 source.set(window.subarray(0, f.blockLength - partA), partA);
1208 }
1209 }
1210 const entryPos = f.blockStart - startWrite;
1211 const filtered = runFilter(f, source, entryPos);
1212 this.#ready.set(f.blockStart, filtered);
1213 lastFiltered = filtered;
1214 lastBlockStart = f.blockStart;
1215 lastBlockLength = f.blockLength;
1216 }
1217 this.#filterState.stack = stillPending;
1218 };
1219
1220 // drain bytes from the window into one chunk and pass it to the sink.
1221 // called periodically inside the loop so that the unflushed window slice
1222 // never reaches `windowSize`, which would let later writes wrap over
1223 // and overwrite bytes the sink has not yet received. emission is
1224 // bounded by the earliest still-pending filter's start, and ready
1225 // filters' post-filter bytes overlay the chunk in place.
1226 const flush = async (final: boolean): Promise<void> => {
1227 tryRunFilters();
1228
1229 let safeEnd = final ? targetWrite : Math.min(this.#write, targetWrite);
1230 for (const f of this.#filterState.stack) {
1231 if (f.blockStart < safeEnd) {
1232 safeEnd = f.blockStart;
1233 }
1234 }
1235 if (safeEnd <= emitted) {
1236 return;
1237 }
1238
1239 const size = safeEnd - emitted;
1240 const chunk = new Uint8Array(size);
1241 // copy from the window using typed-array `set()` instead of a
1242 // byte loop. the window is circular, so a single contiguous
1243 // monotonic range can wrap; in that case fall back to two sets.
1244 const startInWindow = emitted & mask;
1245 if (startInWindow + size <= windowSize) {
1246 chunk.set(window.subarray(startInWindow, startInWindow + size));
1247 } else {
1248 const partA = windowSize - startInWindow;
1249 chunk.set(window.subarray(startInWindow));
1250 chunk.set(window.subarray(0, size - partA), partA);
1251 }
1252
1253 // overlay ready filters whose range intersects the chunk. any
1254 // portion that tails past `safeEnd` stays in `#ready` for the
1255 // next emit cycle.
1256 for (const [fs, filtered] of this.#ready) {
1257 const fe = fs + filtered.length;
1258 const overlayStart = Math.max(fs, emitted);
1259 const overlayEnd = Math.min(fe, safeEnd);
1260 if (overlayEnd <= overlayStart) {
1261 continue;
1262 }
1263 chunk.set(
1264 filtered.subarray(overlayStart - fs, overlayEnd - fs),
1265 overlayStart - emitted,
1266 );
1267 if (overlayEnd >= fe) {
1268 this.#ready.delete(fs);
1269 }
1270 }
1271
1272 await sink(chunk);
1273 emitted = safeEnd;
1274 };
1275
1276 // pulls a contiguous slab of compressed bytes large enough that the
1277 // inner loop can run for a while without re-checking. 64 KiB matches
1278 // libarchive's `UNP_BUFFER_SIZE / 2`, leaves headroom for the longest
1279 // composite read (a few dozen bits), and lets `peek32` look past the
1280 // nominal end safely thanks to 8 trailing pad bytes.
1281 const BLOCK_SIZE = 64 * 1024;
1282 const PAD = 8;
1283 let bits: BitReader | undefined;
1284
1285 // grows the bit reader's backing buffer until it has at least `count`
1286 // bytes available past the current position (plus PAD). when the
1287 // source is exhausted but the bit reader still has unread bytes,
1288 // returns true — peek16/peek32 stay safe thanks to the PAD cushion
1289 // and the encoder's last symbols sit at the tail of the real data.
1290 // only returns false once the bit reader has nothing usable left.
1291 const ensureBytes = async (count: number): Promise<boolean> => {
1292 while (bits === undefined || bits.addr + count > bits.data.length - PAD) {
1293 if (input.buffered === 0) {
1294 try {
1295 await input.require(1);
1296 } catch {
1297 return bits !== undefined && bits.addr + 5 <= bits.data.length;
1298 }
1299 }
1300 const take = Math.min(input.buffered, BLOCK_SIZE);
1301 const chunk = input.take(take);
1302 if (bits === undefined) {
1303 const padded = new Uint8Array(chunk.length + PAD);
1304 padded.set(chunk);
1305 bits = new BitReader(padded);
1306 continue;
1307 }
1308 const tail = bits.data.subarray(bits.addr, bits.data.length - PAD);
1309 const carriedBit = bits.bit;
1310 const merged = new Uint8Array(tail.length + chunk.length + PAD);
1311 merged.set(tail);
1312 merged.set(chunk, tail.length);
1313 bits.rebind(merged);
1314 bits.addr = 0;
1315 bits.bit = carriedBit;
1316 }
1317 return true;
1318 };
1319
1320 // `skipFilterCommand` calls ensureBytes too, but bits is rebound in
1321 // place so its local reference stays valid. wrap it so the throwing
1322 // `ensureBytes` variant is hidden behind a void-returning shim that
1323 // the filter parser can `await` without worrying about exhaustion mid
1324 // command (which would be a malformed archive).
1325 const ensureBytesOrThrow = async (count: number): Promise<void> => {
1326 if (!await ensureBytes(count)) {
1327 throw new MalformedArchiveError(
1328 'RAR3 filter command extends past end of compressed data',
1329 );
1330 }
1331 };
1332
1333 if (!await ensureBytes(16)) {
1334 if (unpackedSize === 0) {
1335 // 0-byte entry with no data area: nothing to do. solid follow-ups
1336 // will start cleanly because the bit position is unchanged.
1337 return;
1338 }
1339 throw new MalformedArchiveError('RAR3 compressed data area is empty');
1340 }
1341 // at this point `bits` is set; assert for the type checker.
1342 const _ = bits!;
1343 void _;
1344
1345 const copy = (length: number, distance: number): void => {
1346 const write = this.#write;
1347 // when source and destination ranges don't overlap (distance >=
1348 // length), and neither end wraps the window, hand the copy off
1349 // to `copyWithin` — a single native memmove instead of a per-byte
1350 // js loop. the overlap case (distance < length) needs the runlength
1351 // repeat semantics: each new byte may be a byte we just wrote.
1352 if (distance >= length) {
1353 const dst = write & mask;
1354 const src = (write - distance) & mask;
1355 if (dst + length <= windowSize && src + length <= windowSize) {
1356 window.copyWithin(dst, src, src + length);
1357 this.#write = write + length;
1358 return;
1359 }
1360 }
1361 for (let idx = 0; idx < length; idx++) {
1362 window[(write + idx) & mask] = window[(write + idx - distance) & mask];
1363 }
1364 this.#write = write + length;
1365 };
1366
1367 // the loop terminates on the symbol-256 end-of-entry marker rather than
1368 // on `write >= targetWrite`, so the marker is always consumed and a
1369 // follow-up solid entry begins at a clean bit position. the
1370 // write-overflow check at the top guards against malformed archives
1371 // that emit literals past the declared size.
1372 let endMarkerSeen = false;
1373 while (!endMarkerSeen) {
1374 if (this.#write > targetWrite) {
1375 throw new ChecksumMismatchError(`RAR3 wrote past expected size: ${unpackedSize} bytes`);
1376 }
1377
1378 // keep at most `windowSize - 512` bytes unflushed so the next
1379 // iteration's copy can't overwrite bytes that haven't reached the
1380 // sink. for a small entry this typically only runs at the end.
1381 if (this.#write - emitted >= FLUSH_HIGH_WATER) {
1382 await flush(false);
1383 }
1384
1385 if (!await ensureBytes(16)) {
1386 // no more input — the caller validates write < targetWrite below.
1387 break;
1388 }
1389
1390 if (this.#startNewTable) {
1391 const mode = parseCodes(bits!, this.#lengthTable);
1392 if (mode.kind === 'huffman') {
1393 this.#tables = mode.tables;
1394 this.#ppmd = undefined;
1395 } else {
1396 this.#tables = undefined;
1397 if (mode.init === undefined && this.#ppmd === undefined) {
1398 throw new MalformedArchiveError(
1399 'RAR3 PPMd reuse block with no prior model state',
1400 );
1401 }
1402 // the byte source has to be rebound per block — entry 2 of
1403 // a solid run would get its own BitReader, not the one we
1404 // built the model with — so the stream object always points
1405 // at the current call's bit reader.
1406 const ppmdStream: PpmdByteIn = {
1407 read: () => {
1408 if (bits!.bit !== 0) {
1409 bits!.alignByte();
1410 }
1411 if (bits!.addr >= bits!.data.length - 8) {
1412 return 0;
1413 }
1414 return bits!.read(8);
1415 },
1416 };
1417 // drain whatever's still in flight so the sync PPMd decoder
1418 // won't run out of bytes mid-symbol. PPMd archives in the
1419 // wild fit comfortably in memory at per-entry granularity.
1420 await ensureBytes(1 << 30);
1421 bits!.alignByte();
1422 const model = mode.init !== undefined ? new RAR3PpmdModel(mode.init.dictSize) : this.#ppmd!.model;
1423 if (!model.initRangeDecoder(ppmdStream)) {
1424 throw new MalformedArchiveError('RAR3 PPMd range decoder init failed');
1425 }
1426 if (mode.init !== undefined) {
1427 model.initEsc = mode.escape;
1428 model.init(mode.init.maxorder);
1429 }
1430 this.#ppmd = { escape: mode.escape, model };
1431 }
1432 this.#startNewTable = false;
1433 }
1434
1435 if (this.#ppmd !== undefined) {
1436 const { model, escape } = this.#ppmd;
1437 // PPMd entries terminate on an in-stream end-of-data marker
1438 // (escape + code 2). we must consume it — even after the
1439 // output budget is met — so the model state stays in sync
1440 // with the encoder for the next solid entry.
1441 for (;;) {
1442 if (this.#write > targetWrite) {
1443 throw new ChecksumMismatchError(`RAR3 wrote past expected size: ${unpackedSize} bytes`);
1444 }
1445 if (this.#write - emitted >= FLUSH_HIGH_WATER) {
1446 await flush(false);
1447 }
1448
1449 const sym = model.decodeSymbol();
1450 if (sym === PPMD_CORRUPT || sym === PPMD_END_OF_DATA) {
1451 throw new MalformedArchiveError('RAR3 PPMd: decoder reported invalid symbol');
1452 }
1453 if (sym !== escape) {
1454 window[this.#write++ & mask] = sym;
1455 continue;
1456 }
1457
1458 const code = model.decodeSymbol();
1459 if (code < 0) {
1460 throw new MalformedArchiveError('RAR3 PPMd: invalid escape code');
1461 }
1462 if (code === 0) {
1463 // in-stream "new table" marker: loop back to parseCodes.
1464 this.#startNewTable = true;
1465 break;
1466 }
1467 if (code === 2) {
1468 // end-of-data for the current entry. model state
1469 // survives; the next entry's decode() must re-parse a
1470 // fresh block header and re-prime the range decoder
1471 // against its own bit reader.
1472 this.#startNewTable = true;
1473 endMarkerSeen = true;
1474 break;
1475 }
1476 if (code === 3) {
1477 throw new UnsupportedFeatureError('RAR3 PPMd: filter commands not supported');
1478 }
1479 if (code === 4) {
1480 let lzssOffset = 0;
1481 for (let i = 2; i >= 0; i--) {
1482 const piece = model.decodeSymbol();
1483 if (piece < 0) {
1484 throw new MalformedArchiveError('RAR3 PPMd: truncated offset symbol');
1485 }
1486 lzssOffset |= piece << (i * 8);
1487 }
1488 const length = model.decodeSymbol();
1489 if (length < 0) {
1490 throw new MalformedArchiveError('RAR3 PPMd: truncated length symbol');
1491 }
1492 copy(length + 32, lzssOffset + 2);
1493 continue;
1494 }
1495 if (code === 5) {
1496 const length = model.decodeSymbol();
1497 if (length < 0) {
1498 throw new MalformedArchiveError('RAR3 PPMd: truncated repeat length');
1499 }
1500 copy(length + 4, 1);
1501 continue;
1502 }
1503 // any other escape code: treat as a literal of the escape value.
1504 window[this.#write++ & mask] = sym;
1505 }
1506
1507 if (endMarkerSeen) {
1508 break;
1509 }
1510 // fell out via the in-stream "new table" marker; loop back
1511 // to parseCodes for the refreshed block header.
1512 continue;
1513 }
1514
1515 const tables = this.#tables!;
1516
1517 const symbol = decodeSymbol(tables.main, bits!);
1518
1519 if (symbol < 256) {
1520 window[this.#write++ & mask] = symbol;
1521 continue;
1522 }
1523
1524 if (symbol === 256) {
1525 const newFile = bits!.read(1) === 0;
1526 if (newFile) {
1527 // end-of-entry marker: the next bit decides whether the next
1528 // entry rebuilds Huffman tables or carries the current set
1529 // over (solid runs typically carry).
1530 this.#startNewTable = bits!.read(1) !== 0;
1531 endMarkerSeen = true;
1532 break;
1533 }
1534 // in-stream table change: re-parse codes against the same length
1535 // table and keep decoding from the new tables.
1536 const refreshed = parseCodes(bits!, this.#lengthTable);
1537 if (refreshed.kind !== 'huffman') {
1538 throw new MalformedArchiveError(
1539 'RAR3 in-stream table refresh switched to PPMd unexpectedly',
1540 );
1541 }
1542 this.#tables = refreshed.tables;
1543 continue;
1544 }
1545
1546 if (symbol === 257) {
1547 // parse the filter command off the bit stream and stage it on
1548 // the decoder's filter stack; the queued filter will execute
1549 // when the LZSS engine has produced enough output to cover
1550 // its `[blockStart, blockStart + blockLength)` range.
1551 await parseFilterCommand(
1552 bits!,
1553 this.#filterState,
1554 this.#write,
1555 this.#targetSize,
1556 ensureBytesOrThrow,
1557 );
1558 continue;
1559 }
1560
1561 let offs: number;
1562 let len: number;
1563
1564 if (symbol === 258) {
1565 if (this.#lastLength === 0) {
1566 continue;
1567 }
1568 offs = this.#lastOffset;
1569 len = this.#lastLength;
1570 } else if (symbol < 263) {
1571 const offsetIndex = symbol - 259;
1572 offs = this.#oldOffsets[offsetIndex];
1573 const lengthSymbol = decodeSymbol(tables.length, bits!);
1574 if (lengthSymbol >= LENGTH_BASES.length) {
1575 throw new MalformedArchiveError(`RAR3 length symbol out of range: ${lengthSymbol}`);
1576 }
1577 len = LENGTH_BASES[lengthSymbol] + 2;
1578 if (LENGTH_EXTRA_BITS[lengthSymbol] > 0) {
1579 len += bits!.read(LENGTH_EXTRA_BITS[lengthSymbol]);
1580 }
1581 for (let i = offsetIndex; i > 0; i--) {
1582 this.#oldOffsets[i] = this.#oldOffsets[i - 1];
1583 }
1584 this.#oldOffsets[0] = offs;
1585 } else if (symbol < 271) {
1586 const slot = symbol - 263;
1587 offs = SHORT_BASES[slot] + 1;
1588 if (SHORT_EXTRA_BITS[slot] > 0) {
1589 offs += bits!.read(SHORT_EXTRA_BITS[slot]);
1590 }
1591 len = 2;
1592 for (let i = 3; i > 0; i--) {
1593 this.#oldOffsets[i] = this.#oldOffsets[i - 1];
1594 }
1595 this.#oldOffsets[0] = offs;
1596 } else {
1597 const lengthSlot = symbol - 271;
1598 if (lengthSlot >= LENGTH_BASES.length) {
1599 throw new MalformedArchiveError(`RAR3 main symbol out of length range: ${symbol}`);
1600 }
1601 len = LENGTH_BASES[lengthSlot] + 3;
1602 if (LENGTH_EXTRA_BITS[lengthSlot] > 0) {
1603 len += bits!.read(LENGTH_EXTRA_BITS[lengthSlot]);
1604 }
1605
1606 const offsetSymbol = decodeSymbol(tables.offset, bits!);
1607 if (offsetSymbol >= OFFSET_BASES.length) {
1608 throw new MalformedArchiveError(`RAR3 offset symbol out of range: ${offsetSymbol}`);
1609 }
1610 offs = OFFSET_BASES[offsetSymbol] + 1;
1611 const extraBits = OFFSET_EXTRA_BITS[offsetSymbol];
1612 if (extraBits > 0) {
1613 if (offsetSymbol > 9) {
1614 if (extraBits > 4) {
1615 offs += bits!.read(extraBits - 4) << 4;
1616 }
1617 if (this.#lowOffsetRepeats > 0) {
1618 this.#lowOffsetRepeats--;
1619 offs += this.#lastLowOffset;
1620 } else {
1621 const lowSymbol = decodeSymbol(tables.lowOffset, bits!);
1622 if (lowSymbol === 16) {
1623 this.#lowOffsetRepeats = 15;
1624 offs += this.#lastLowOffset;
1625 } else {
1626 offs += lowSymbol;
1627 this.#lastLowOffset = lowSymbol;
1628 }
1629 }
1630 } else {
1631 offs += bits!.read(extraBits);
1632 }
1633 }
1634
1635 // libarchive: long-distance matches encode shorter length codes,
1636 // so bump the decoded length back up for the appropriate slots.
1637 if (offs >= 0x40000) {
1638 len++;
1639 }
1640 if (offs >= 0x2000) {
1641 len++;
1642 }
1643
1644 for (let i = 3; i > 0; i--) {
1645 this.#oldOffsets[i] = this.#oldOffsets[i - 1];
1646 }
1647 this.#oldOffsets[0] = offs;
1648 }
1649
1650 this.#lastOffset = offs;
1651 this.#lastLength = len;
1652 copy(len, offs);
1653 }
1654
1655 await flush(true);
1656
1657 if (this.#write < targetWrite) {
1658 throw new ChecksumMismatchError(
1659 `RAR3 decompressed size mismatch: got ${this.#write - startWrite} bytes, expected ${unpackedSize}`,
1660 );
1661 }
1662 if (emitted < targetWrite) {
1663 throw new MalformedArchiveError(
1664 `RAR3 pending filter prevents final emission past byte ${emitted - startWrite}`,
1665 );
1666 }
1667 }
1668}
1669
1670// #endregion