GCC Code Coverage Report

Directory: src/
File: src/mpq-pkware.c
Date: 2026-10-06 13:47:41
Exec Total Coverage
Lines: 198 263 75.3%
Functions: 12 13 92.3%
Branches: 101 150 67.3%
Line Branch Exec Source
1 /*
2 * mpq-pkware.c -- PKWARE Data Compression Library implementation.
3 *
4 * Copyright (c) 2003-2026 Maik Broemme <mbroemme@libmpq.org>
5 *
6 * This source was adapted from the C++ version of pkware.cpp included
7 * in stormlib. The C++ version belongs to the following authors:
8 *
9 * Ladislav Zezula <ladik@zezula.net>
10 *
11 * This file is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU Lesser General Public License as published by
13 * the Free Software Foundation; either version 2.1 of the License, or
14 * (at your option) any later version.
15 *
16 * This file is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public License
22 * along with this file; if not, see <https://www.gnu.org/licenses/>.
23 */
24
25 #include "mpq-pkware.h"
26 #include <libmpq/mpq.h>
27
28 #include <stdlib.h>
29 #include <string.h>
30
31 /* Distance bit lengths used by the PKWARE explode distance decoder. */
32 static const uint8_t pkzip_dist_bits[] = {
33 0x02, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
34 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
35 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
36 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
37 };
38
39 /* Distance code lookup table used by the PKWARE explode decoder. */
40 static const uint8_t pkzip_dist_code[] = {
41 0x03, 0x0D, 0x05, 0x19, 0x09, 0x11, 0x01, 0x3E, 0x1E, 0x2E, 0x0E, 0x36, 0x16, 0x26, 0x06, 0x3A,
42 0x1A, 0x2A, 0x0A, 0x32, 0x12, 0x22, 0x42, 0x02, 0x7C, 0x3C, 0x5C, 0x1C, 0x6C, 0x2C, 0x4C, 0x0C,
43 0x74, 0x34, 0x54, 0x14, 0x64, 0x24, 0x44, 0x04, 0x78, 0x38, 0x58, 0x18, 0x68, 0x28, 0x48, 0x08,
44 0xF0, 0x70, 0xB0, 0x30, 0xD0, 0x50, 0x90, 0x10, 0xE0, 0x60, 0xA0, 0x20, 0xC0, 0x40, 0x80, 0x00
45 };
46
47 /* Extra bit counts for decoded copy lengths. */
48 static const uint8_t pkzip_clen_bits[] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
49 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 };
50
51 /* Base values for decoded copy lengths. */
52 static const uint16_t pkzip_len_base[] = { 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005,
53 0x0006, 0x0007, 0x0008, 0x000A, 0x000E, 0x0016,
54 0x0026, 0x0046, 0x0086, 0x0106 };
55
56 /* Bit lengths for the static copy-length Huffman table. */
57 static const uint8_t pkzip_slen_bits[] = { 0x03, 0x02, 0x03, 0x03, 0x04, 0x04, 0x04, 0x05,
58 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x07, 0x07 };
59
60 /* Codes for the static copy-length Huffman table. */
61 static const uint8_t pkzip_len_code[] = { 0x05, 0x03, 0x01, 0x06, 0x0A, 0x02, 0x0C, 0x14,
62 0x04, 0x18, 0x08, 0x30, 0x10, 0x20, 0x40, 0x00 };
63
64 /*
65 * Append a low-bit-first PKWARE code to the output bitstream.
66 * The caller provides a zeroed output buffer and a bit cursor, and this helper
67 * sets only the bits represented by the requested code.
68 */
69 static void
70 1285594 pkzip_put_bits(uint8_t *out, size_t *bit_pos, uint32_t value, unsigned bits)
71 {
72 unsigned i;
73
2/2
✓ Branch 0 taken 5845067 times.
✓ Branch 1 taken 1285594 times.
 7130661 for (i = 0; i < bits; i++, (*bit_pos)++)
74
2/2
✓ Branch 0 taken 2608266 times.
✓ Branch 1 taken 3236801 times.
 5845067 if (value & (1u << i))
75 2608266 out[*bit_pos >> 3] |= (uint8_t)(1u << (*bit_pos & 7));
76 1285594 }
77
78 /* Bit lengths for the ASCII literal table. */
79 static const uint8_t pkzip_bits_asc[] = {
80 0x0B, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x08, 0x07, 0x0C, 0x0C, 0x07, 0x0C, 0x0C,
81 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C,
82 0x04, 0x0A, 0x08, 0x0C, 0x0A, 0x0C, 0x0A, 0x08, 0x07, 0x07, 0x08, 0x09, 0x07, 0x06, 0x07, 0x08,
83 0x07, 0x06, 0x07, 0x07, 0x07, 0x07, 0x08, 0x07, 0x07, 0x08, 0x08, 0x0C, 0x0B, 0x07, 0x09, 0x0B,
84 0x0C, 0x06, 0x07, 0x06, 0x06, 0x05, 0x07, 0x08, 0x08, 0x06, 0x0B, 0x09, 0x06, 0x07, 0x06, 0x06,
85 0x07, 0x0B, 0x06, 0x06, 0x06, 0x07, 0x09, 0x08, 0x09, 0x09, 0x0B, 0x08, 0x0B, 0x09, 0x0C, 0x08,
86 0x0C, 0x05, 0x06, 0x06, 0x06, 0x05, 0x06, 0x06, 0x06, 0x05, 0x0B, 0x07, 0x05, 0x06, 0x05, 0x05,
87 0x06, 0x0A, 0x05, 0x05, 0x05, 0x05, 0x08, 0x07, 0x08, 0x08, 0x0A, 0x0B, 0x0B, 0x0C, 0x0C, 0x0C,
88 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D,
89 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D,
90 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D,
91 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C,
92 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C,
93 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C, 0x0C,
94 0x0D, 0x0C, 0x0D, 0x0D, 0x0D, 0x0C, 0x0D, 0x0D, 0x0D, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D, 0x0C, 0x0D,
95 0x0D, 0x0D, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D, 0x0D
96 };
97
98 /* Codes for the ASCII literal table. */
99 static const uint16_t pkzip_code_asc[] = {
100 0x0490, 0x0FE0, 0x07E0, 0x0BE0, 0x03E0, 0x0DE0, 0x05E0, 0x09E0, 0x01E0, 0x00B8, 0x0062, 0x0EE0,
101 0x06E0, 0x0022, 0x0AE0, 0x02E0, 0x0CE0, 0x04E0, 0x08E0, 0x00E0, 0x0F60, 0x0760, 0x0B60, 0x0360,
102 0x0D60, 0x0560, 0x1240, 0x0960, 0x0160, 0x0E60, 0x0660, 0x0A60, 0x000F, 0x0250, 0x0038, 0x0260,
103 0x0050, 0x0C60, 0x0390, 0x00D8, 0x0042, 0x0002, 0x0058, 0x01B0, 0x007C, 0x0029, 0x003C, 0x0098,
104 0x005C, 0x0009, 0x001C, 0x006C, 0x002C, 0x004C, 0x0018, 0x000C, 0x0074, 0x00E8, 0x0068, 0x0460,
105 0x0090, 0x0034, 0x00B0, 0x0710, 0x0860, 0x0031, 0x0054, 0x0011, 0x0021, 0x0017, 0x0014, 0x00A8,
106 0x0028, 0x0001, 0x0310, 0x0130, 0x003E, 0x0064, 0x001E, 0x002E, 0x0024, 0x0510, 0x000E, 0x0036,
107 0x0016, 0x0044, 0x0030, 0x00C8, 0x01D0, 0x00D0, 0x0110, 0x0048, 0x0610, 0x0150, 0x0060, 0x0088,
108 0x0FA0, 0x0007, 0x0026, 0x0006, 0x003A, 0x001B, 0x001A, 0x002A, 0x000A, 0x000B, 0x0210, 0x0004,
109 0x0013, 0x0032, 0x0003, 0x001D, 0x0012, 0x0190, 0x000D, 0x0015, 0x0005, 0x0019, 0x0008, 0x0078,
110 0x00F0, 0x0070, 0x0290, 0x0410, 0x0010, 0x07A0, 0x0BA0, 0x03A0, 0x0240, 0x1C40, 0x0C40, 0x1440,
111 0x0440, 0x1840, 0x0840, 0x1040, 0x0040, 0x1F80, 0x0F80, 0x1780, 0x0780, 0x1B80, 0x0B80, 0x1380,
112 0x0380, 0x1D80, 0x0D80, 0x1580, 0x0580, 0x1980, 0x0980, 0x1180, 0x0180, 0x1E80, 0x0E80, 0x1680,
113 0x0680, 0x1A80, 0x0A80, 0x1280, 0x0280, 0x1C80, 0x0C80, 0x1480, 0x0480, 0x1880, 0x0880, 0x1080,
114 0x0080, 0x1F00, 0x0F00, 0x1700, 0x0700, 0x1B00, 0x0B00, 0x1300, 0x0DA0, 0x05A0, 0x09A0, 0x01A0,
115 0x0EA0, 0x06A0, 0x0AA0, 0x02A0, 0x0CA0, 0x04A0, 0x08A0, 0x00A0, 0x0F20, 0x0720, 0x0B20, 0x0320,
116 0x0D20, 0x0520, 0x0920, 0x0120, 0x0E20, 0x0620, 0x0A20, 0x0220, 0x0C20, 0x0420, 0x0820, 0x0020,
117 0x0FC0, 0x07C0, 0x0BC0, 0x03C0, 0x0DC0, 0x05C0, 0x09C0, 0x01C0, 0x0EC0, 0x06C0, 0x0AC0, 0x02C0,
118 0x0CC0, 0x04C0, 0x08C0, 0x00C0, 0x0F40, 0x0740, 0x0B40, 0x0340, 0x0300, 0x0D40, 0x1D00, 0x0D00,
119 0x1500, 0x0540, 0x0500, 0x1900, 0x0900, 0x0940, 0x1100, 0x0100, 0x1E00, 0x0E00, 0x0140, 0x1600,
120 0x0600, 0x1A00, 0x0E40, 0x0640, 0x0A40, 0x0A00, 0x1200, 0x0200, 0x1C00, 0x0C00, 0x1400, 0x0400,
121 0x1800, 0x0800, 0x1000, 0x0000
122 };
123
124 /*
125 * Consume bits from the PKWARE input accumulator.
126 * It refills the eight-bit staging window through the configured callback and
127 * returns a nonzero value when the compressed input ends prematurely.
128 */
129 static int32_t
130 740487 skip_bit(pkzip_cmp_s *mpq_pkzip, uint32_t bits)
131 {
132
2/2
✓ Branch 0 taken 340103 times.
✓ Branch 1 taken 400384 times.
 740487 if (bits <= mpq_pkzip->extra_bits) {
133 340103 mpq_pkzip->extra_bits -= bits;
134 340103 mpq_pkzip->bit_buf >>= bits;
135 340103 return 0;
136 }
137
138 /* Refill the bit buffer from the input callback when the staging buffer is empty. */
139 400384 mpq_pkzip->bit_buf >>= mpq_pkzip->extra_bits;
140
2/2
✓ Branch 0 taken 1212 times.
✓ Branch 1 taken 399172 times.
 400384 if (mpq_pkzip->in_pos == mpq_pkzip->in_bytes) {
141 1212 uint32_t in_size = sizeof(mpq_pkzip->in_buf);
142
143
2/2
✓ Branch 0 taken 1100 times.
✓ Branch 1 taken 112 times.
 1212 if ((mpq_pkzip->in_bytes =
144 1212 mpq_pkzip->read_buf((char *)mpq_pkzip->in_buf, &in_size, mpq_pkzip->param)) == 0) {
145 1100 return 1;
146 }
147 112 mpq_pkzip->in_pos = 0;
148 }
149
150 399284 mpq_pkzip->bit_buf |= (mpq_pkzip->in_buf[mpq_pkzip->in_pos++] << 8);
151 399284 mpq_pkzip->bit_buf >>= (bits - mpq_pkzip->extra_bits);
152 399284 mpq_pkzip->extra_bits = (mpq_pkzip->extra_bits - bits) + 8;
153
154 399284 return 0;
155 }
156
157 /*
158 * Build a decode lookup table from PKWARE canonical bit codes.
159 * Each short code is expanded across all matching low-byte prefixes so the
160 * decoder can resolve literals and lengths without walking a tree at runtime.
161 */
162 static void
163 2200 generate_tables_decode(int32_t count, uint8_t *bits, const uint8_t *code, uint8_t *buf2)
164 {
165
166 /* Walk backwards because the original table order assigns higher codes first. */
167 int32_t i;
168
169
2/2
✓ Branch 0 taken 88000 times.
✓ Branch 1 taken 2200 times.
 90200 for (i = count - 1; i >= 0; i--) {
170
171 /* Fill every lookup slot reachable by this code prefix. */
172 88000 uint32_t idx1 = code[i];
173 88000 uint32_t idx2 = 1 << bits[i];
174
175 do {
176 563200 buf2[idx1] = (uint8_t)i;
177 563200 idx1 += idx2;
178
2/2
✓ Branch 0 taken 475200 times.
✓ Branch 1 taken 88000 times.
 563200 } while (idx1 < 0x100);
179 }
180 2200 }
181
182 /*
183 * Build the ASCII literal lookup tables used by the PKWARE decoder.
184 * The static canonical tables are expanded into prefix tables that support
185 * the variable-length ASCII mode used by DCL streams.
186 */
187 static void
188 ✗ generate_tables_ascii(pkzip_cmp_s *mpq_pkzip)
189 {
190
191 /* ASCII table cursor and bit expansion state. */
192 ✗ const uint16_t *code_asc = &pkzip_code_asc[0xFF];
193 uint32_t acc;
194 uint32_t add;
195 uint16_t count;
196
197 /* Expand the static ASCII literal codes into the decoder lookup tables. */
198 ✗ for (count = 0x00FF; code_asc >= pkzip_code_asc; code_asc--, count--) {
199 ✗ uint8_t *bits_asc = mpq_pkzip->bits_asc + count;
200 ✗ uint8_t bits_tmp = *bits_asc;
201
202 ✗ if (bits_tmp <= 8) {
203 ✗ add = (1 << bits_tmp);
204 ✗ acc = *code_asc;
205 ✗ while (acc < 0x100) {
206 ✗ mpq_pkzip->offs_2c34[acc] = (uint8_t)count;
207 ✗ acc += add;
208 }
209 } else {
210 ✗ if ((acc = (*code_asc & 0xFF)) != 0) {
211 ✗ mpq_pkzip->offs_2c34[acc] = 0xFF;
212 ✗ if (*code_asc & 0x3F) {
213 ✗ bits_tmp -= 4;
214 ✗ *bits_asc = bits_tmp;
215 ✗ add = (1 << bits_tmp);
216 ✗ acc = *code_asc >> 4;
217 do {
218 ✗ mpq_pkzip->offs_2d34[acc] = (uint8_t)count;
219 ✗ acc += add;
220 ✗ } while (acc < 0x100);
221 } else {
222 ✗ bits_tmp -= 6;
223 ✗ *bits_asc = bits_tmp;
224 ✗ add = (1 << bits_tmp);
225 ✗ acc = *code_asc >> 6;
226 do {
227 ✗ mpq_pkzip->offs_2e34[acc] = (uint8_t)count;
228 ✗ acc += add;
229 ✗ } while (acc < 0x80);
230 }
231 } else {
232 ✗ bits_tmp -= 8;
233 ✗ *bits_asc = bits_tmp;
234 ✗ add = (1 << bits_tmp);
235 ✗ acc = *code_asc >> 8;
236 do {
237 ✗ mpq_pkzip->offs_2eb4[acc] = (uint8_t)count;
238 ✗ acc += add;
239 ✗ } while (acc < 0x100);
240 }
241 }
242 }
243 ✗ }
244
245 /*
246 * Decode one PKWARE literal or copy marker.
247 * The low control bit distinguishes a length/distance match from a literal,
248 * and the selected mode determines whether literals are binary or ASCII-coded.
249 */
250 static uint32_t
251 331788 decode_literal(pkzip_cmp_s *mpq_pkzip)
252 {
253 uint32_t bits;
254 uint32_t value;
255
256 /* A set low bit marks a length code; an unset bit marks a literal code. */
257
2/2
✓ Branch 0 taken 32490 times.
✓ Branch 1 taken 299298 times.
 331788 if (mpq_pkzip->bit_buf & 1) {
258
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 32490 times.
 32490 if (skip_bit(mpq_pkzip, 1)) {
259 ✗ return 0x306;
260 }
261
262 /* The next prefix selects a length-code table entry. */
263 32490 value = mpq_pkzip->pos2[(mpq_pkzip->bit_buf & 0xFF)];
264
265
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 32490 times.
 32490 if (skip_bit(mpq_pkzip, mpq_pkzip->slen_bits[value])) {
266 ✗ return 0x306;
267 }
268
269
2/2
✓ Branch 0 taken 14127 times.
✓ Branch 1 taken 18363 times.
 32490 if ((bits = mpq_pkzip->clen_bits[value]) != 0) {
270
271 /* Decoded literal symbol and bit length for this table entry. */
272 14127 uint32_t val2 = mpq_pkzip->bit_buf & ((1 << bits) - 1);
273
274
2/2
✓ Branch 1 taken 1098 times.
✓ Branch 2 taken 13029 times.
 14127 if (skip_bit(mpq_pkzip, bits)) {
275
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1098 times.
 1098 if ((value + val2) != 0x10E) {
276 ✗ return 0x306;
277 }
278 }
279
280 14127 value = mpq_pkzip->len_base[value] + val2;
281 }
282
283 32490 return value + 0x100;
284 }
285
286
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 299298 times.
 299298 if (skip_bit(mpq_pkzip, 1)) {
287 ✗ return 0x306;
288 }
289
290 /* Binary mode carries literal bytes directly after the control bit. */
291
1/2
✓ Branch 0 taken 299298 times.
✗ Branch 1 not taken.
 299298 if (mpq_pkzip->cmp_type == LIBMPQ_PKZIP_CMP_BINARY) {
292 299298 value = mpq_pkzip->bit_buf & 0xFF;
293
294
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 299297 times.
 299298 if (skip_bit(mpq_pkzip, 8)) {
295 1 return 0x306;
296 }
297
298 299297 return value;
299 }
300
301 /* ASCII mode resolves short prefixes through progressively wider tables. */
302 ✗ if (mpq_pkzip->bit_buf & 0xFF) {
303 ✗ value = mpq_pkzip->offs_2c34[mpq_pkzip->bit_buf & 0xFF];
304
305 ✗ if (value == 0xFF) {
306 ✗ if (mpq_pkzip->bit_buf & 0x3F) {
307 ✗ if (skip_bit(mpq_pkzip, 4)) {
308 ✗ return 0x306;
309 }
310
311 ✗ value = mpq_pkzip->offs_2d34[mpq_pkzip->bit_buf & 0xFF];
312 } else {
313 ✗ if (skip_bit(mpq_pkzip, 6)) {
314 ✗ return 0x306;
315 }
316
317 ✗ value = mpq_pkzip->offs_2e34[mpq_pkzip->bit_buf & 0x7F];
318 }
319 }
320 } else {
321
322 /* Ensure eight bits are available before advancing the bit buffer. */
323 ✗ if (skip_bit(mpq_pkzip, 8)) {
324 ✗ return 0x306;
325 }
326
327 ✗ value = mpq_pkzip->offs_2eb4[mpq_pkzip->bit_buf & 0xFF];
328 }
329
330 ✗ return skip_bit(mpq_pkzip, mpq_pkzip->bits_asc[value]) ? 0x306 : value;
331 }
332
333 /*
334 * Decode the backward distance for a PKWARE copy operation.
335 * Two-byte matches use a fixed suffix width, while longer matches use the
336 * dictionary-size-dependent distance width configured in the stream header.
337 */
338 static uint32_t
339 31392 decode_distance(pkzip_cmp_s *mpq_pkzip, uint32_t length)
340 {
341
342 /* Distance prefix, extra bits and final byte distance. */
343 31392 uint32_t pos = mpq_pkzip->pos1[(mpq_pkzip->bit_buf & 0xFF)];
344
345 31392 uint32_t skip = mpq_pkzip->dist_bits[pos];
346
347
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 31392 times.
 31392 if (skip_bit(mpq_pkzip, skip) == 1) {
348 ✗ return 0;
349 }
350
351 /* Two-byte matches use a fixed two-bit distance suffix. */
352
2/2
✓ Branch 0 taken 4022 times.
✓ Branch 1 taken 27370 times.
 31392 if (length == 2) {
353 4022 pos = (pos << 2) | (mpq_pkzip->bit_buf & 0x03);
354
355
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4022 times.
 4022 if (skip_bit(mpq_pkzip, 2) == 1) {
356 ✗ return 0;
357 }
358 } else {
359 27370 pos = (pos << mpq_pkzip->dsize_bits) | (mpq_pkzip->bit_buf & mpq_pkzip->dsize_mask);
360
361
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 27369 times.
 27370 if (skip_bit(mpq_pkzip, mpq_pkzip->dsize_bits) == 1) {
362 1 return 0;
363 }
364 }
365
366 31391 return pos + 1;
367 }
368
369 /*
370 * Supply compressed bytes to the PKWARE decoder callback.
371 * The callback clamps each request to the remaining input and advances the
372 * wrapper-owned cursor so the codec never reads beyond the MPQ block.
373 */
374 static uint32_t
375 2318 data_read_input(char *buf, uint32_t *size, void *param)
376 {
377
378 /* Source state passed by the public decompression wrapper. */
379 2318 pkzip_data_s *info = (pkzip_data_s *)param;
380 2318 uint32_t max_avail = (info->in_bytes - info->in_pos);
381 2318 uint32_t to_read = *size;
382
383
2/2
✓ Branch 0 taken 2206 times.
✓ Branch 1 taken 112 times.
 2318 if (to_read > max_avail) {
384 2206 to_read = max_avail;
385 }
386
387 2318 memcpy(buf, info->in_buf + info->in_pos, to_read);
388 2318 info->in_pos += to_read;
389
390 2318 return to_read;
391 }
392
393 /*
394 * Receive expanded bytes from the PKWARE decoder callback.
395 * Output is clamped to the caller's capacity and the accepted byte count is
396 * recorded for the extraction wrapper after each decoder flush.
397 */
398 static void
399 1424 data_write_output(char *buf, uint32_t *size, void *param)
400 {
401
402 /* Destination state passed by the public decompression wrapper. */
403 1424 pkzip_data_s *info = (pkzip_data_s *)param;
404 1424 uint32_t max_write = (info->max_out - info->out_pos);
405 1424 uint32_t to_write = *size;
406
407
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1424 times.
 1424 if (to_write > max_write) {
408 ✗ to_write = max_write;
409 }
410
411 1424 memcpy(info->out_buf + info->out_pos, buf, to_write);
412 1424 info->out_pos += to_write;
413 1424 }
414
415 /*
416 * Expand one complete PKWARE stream using its configured callbacks.
417 * The sliding 4 KiB window supplies LZ history while completed upper-half
418 * data is flushed incrementally through the output callback.
419 */
420 static uint32_t
421 1100 expand(pkzip_cmp_s *mpq_pkzip)
422 {
423 uint32_t copy_bytes;
424 uint32_t one_byte;
425 uint32_t result;
426
427 /* The lower half preserves history while the upper half is flushed to the caller. */
428 1100 mpq_pkzip->out_pos = 0x1000;
429
430
2/2
✓ Branch 1 taken 330689 times.
✓ Branch 2 taken 1099 times.
 331788 while ((result = one_byte = decode_literal(mpq_pkzip)) < 0x305) {
431
432 /* Values above 0x100 are LZ matches; lower values are literal bytes. */
433
2/2
✓ Branch 0 taken 31392 times.
✓ Branch 1 taken 299297 times.
 330689 if (one_byte >= 0x100) {
434 uint8_t *source;
435 uint8_t *target;
436
437 /* Decoded match length and backward copy distance. */
438 31392 uint32_t copy_length = one_byte - 0xFE;
439 uint32_t move_back;
440
441
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 31391 times.
 31392 if ((move_back = decode_distance(mpq_pkzip, copy_length)) == 0) {
442 1 result = 0x306;
443 1 break;
444 }
445
446 /* Copy from the sliding history window, allowing overlapping matches. */
447 31391 target = &mpq_pkzip->out_buf[mpq_pkzip->out_pos];
448 31391 source = target - move_back;
449 31391 mpq_pkzip->out_pos += copy_length;
450
451
2/2
✓ Branch 0 taken 1689224 times.
✓ Branch 1 taken 31391 times.
 1720615 while (copy_length-- > 0) {
452 1689224 *target++ = *source++;
453 }
454 } else {
455 299297 mpq_pkzip->out_buf[mpq_pkzip->out_pos++] = (uint8_t)one_byte;
456 }
457
458 /* Flush half the window while retaining the other half as match history. */
459
2/2
✓ Branch 0 taken 324 times.
✓ Branch 1 taken 330364 times.
 330688 if (mpq_pkzip->out_pos >= 0x2000) {
460 324 copy_bytes = 0x1000;
461 324 mpq_pkzip->write_buf(
462 324 (char *)&mpq_pkzip->out_buf[0x1000], &copy_bytes, mpq_pkzip->param
463 );
464
465 324 memmove(mpq_pkzip->out_buf, &mpq_pkzip->out_buf[0x1000], mpq_pkzip->out_pos - 0x1000);
466 324 mpq_pkzip->out_pos -= 0x1000;
467 }
468 }
469
470 1100 copy_bytes = mpq_pkzip->out_pos - 0x1000;
471 1100 mpq_pkzip->write_buf((char *)&mpq_pkzip->out_buf[0x1000], &copy_bytes, mpq_pkzip->param);
472
473 1100 return result;
474 }
475
476 /* Bound match history and search work independently of the input size. */
477 #define PKZIP_DICTIONARY_SIZE 4096u
478 #define PKZIP_MATCH_MAX 516u
479 #define PKZIP_SEARCH_MAX 256u
480
481 /* Hash chains retain absolute positions in a circular dictionary. */
482 typedef struct
483 {
484 uint32_t head[PKZIP_DICTIONARY_SIZE];
485 uint32_t previous[PKZIP_DICTIONARY_SIZE];
486 } pkzip_match_s;
487
488 /* Hash a byte pair so two-byte matches remain discoverable. */
489 static uint32_t
490 2569038 pair_hash(const uint8_t *data)
491 {
492 2569038 return ((uint32_t)data[0] * 251u + data[1]) & (PKZIP_DICTIONARY_SIZE - 1u);
493 }
494
495 /* Find the longest recent match, allowing copies to overlap their source. */
496 static uint32_t
497 626030 find_match(
498 const pkzip_match_s *history, const uint8_t *input, uint32_t size, uint32_t position,
499 uint32_t *distance
500 )
501 {
502 626030 uint32_t limit = size - position;
503 626030 uint32_t best = 1;
504 uint32_t candidate;
505 626030 uint32_t probes = 0;
506
507
2/2
✓ Branch 0 taken 225 times.
✓ Branch 1 taken 625805 times.
 626030 if (limit < 2)
508 225 return best;
509
2/2
✓ Branch 0 taken 550120 times.
✓ Branch 1 taken 75685 times.
 625805 if (limit > PKZIP_MATCH_MAX)
510 550120 limit = PKZIP_MATCH_MAX;
511 625805 candidate = history->head[pair_hash(input + position)];
512
4/4
✓ Branch 0 taken 1396405 times.
✓ Branch 1 taken 513085 times.
✓ Branch 2 taken 1284407 times.
✓ Branch 3 taken 111998 times.
 1909490 while (candidate != UINT32_MAX && position - candidate <= PKZIP_DICTIONARY_SIZE &&
513
2/2
✓ Branch 0 taken 1284405 times.
✓ Branch 1 taken 2 times.
 1284407 probes++ < PKZIP_SEARCH_MAX) {
514 1284405 uint32_t length = 0;
515 1284405 uint32_t back = position - candidate;
516
517
4/4
✓ Branch 0 taken 5524044 times.
✓ Branch 1 taken 729 times.
✓ Branch 2 taken 4240368 times.
✓ Branch 3 taken 1283676 times.
 5524773 while (length < limit && input[candidate + length] == input[position + length])
518 4240368 ++length;
519
520 /* Length two has only two distance suffix bits, hence a 256-byte range. */
521
6/6
✓ Branch 0 taken 56024 times.
✓ Branch 1 taken 1228381 times.
✓ Branch 2 taken 26665 times.
✓ Branch 3 taken 29359 times.
✓ Branch 4 taken 8576 times.
✓ Branch 5 taken 18089 times.
 1284405 if (length > best && (length > 2 || back <= 256u)) {
522 37935 best = length;
523 37935 *distance = back;
524
2/2
✓ Branch 0 taken 720 times.
✓ Branch 1 taken 37215 times.
 37935 if (best == limit)
525 720 break;
526 }
527 1283685 candidate = history->previous[candidate & (PKZIP_DICTIONARY_SIZE - 1u)];
528 }
529 625805 return best;
530 }
531
532 /* Encode binary input with general dictionary matches and the DCL terminator. */
533 int32_t
534 671 libmpq__pkzip_compress(
535 const uint8_t *in_buf, uint32_t in_size, uint8_t **out_buf, uint32_t *out_size
536 )
537 {
538 671 uint64_t maximum_bits = (uint64_t)in_size * 9u + 16u;
539 671 uint64_t maximum_bytes = 2u + (maximum_bits + 7u) / 8u;
540 671 size_t bit_count = 0;
541 pkzip_match_s *history;
542 uint8_t *out;
543 uint32_t i;
544
545
5/8
✓ Branch 0 taken 671 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 671 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 663 times.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 663 times.
 671 if (out_buf == NULL || out_size == NULL || (in_size != 0 && in_buf == NULL))
546 ✗ return LIBMPQ_ERROR_FORMAT;
547
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 671 times.
 671 if (maximum_bits > SIZE_MAX || maximum_bytes > UINT32_MAX || maximum_bytes > SIZE_MAX)
548 ✗ return LIBMPQ_ERROR_SIZE;
549 671 out = calloc(1, (size_t)maximum_bytes);
550
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 671 times.
 671 if (out == NULL)
551 ✗ return LIBMPQ_ERROR_MALLOC;
552 671 history = malloc(sizeof(*history));
553
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 671 times.
 671 if (history == NULL) {
554 ✗ free(out);
555 ✗ return LIBMPQ_ERROR_MALLOC;
556 }
557 671 memset(history, 0xff, sizeof(*history));
558 671 out[0] = LIBMPQ_PKZIP_CMP_BINARY;
559 671 out[1] = 6;
560
561 /* Six distance suffix bits select the full 4 KiB dictionary. */
562
2/2
✓ Branch 0 taken 626030 times.
✓ Branch 1 taken 671 times.
 626701 for (i = 0; i < in_size;) {
563 626030 uint32_t distance = 0;
564 626030 uint32_t match_length = find_match(history, in_buf, in_size, i, &distance);
565 626030 uint32_t end = i + match_length;
566
567
2/2
✓ Branch 0 taken 32863 times.
✓ Branch 1 taken 593167 times.
 626030 if (match_length >= 2) {
568 uint32_t value;
569 uint32_t entry;
570 uint32_t extra;
571 uint32_t code;
572
2/2
✓ Branch 0 taken 6035 times.
✓ Branch 1 taken 26828 times.
 32863 uint32_t suffix = match_length == 2 ? 2u : 6u;
573 32863 uint32_t encoded_distance = distance - 1u;
574 32863 uint32_t prefix = encoded_distance >> suffix;
575 32863 value = match_length - 2;
576
1/2
✓ Branch 0 taken 220197 times.
✗ Branch 1 not taken.
 220197 for (entry = 0; entry < 16; entry++) {
577 220197 extra = pkzip_clen_bits[entry];
578
3/4
✓ Branch 0 taken 220197 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 32863 times.
✓ Branch 3 taken 187334 times.
 220197 if (value >= pkzip_len_base[entry] && value < pkzip_len_base[entry] + (1u << extra))
579 32863 break;
580 }
581
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32863 times.
 32863 if (entry == 16)
582 ✗ entry = 15;
583 32863 code = ((value - pkzip_len_base[entry]) << (pkzip_slen_bits[entry] + 1)) |
584 32863 (pkzip_len_code[entry] * 2u) | 1u;
585 32863 pkzip_put_bits(
586 32863 out + 2, &bit_count, code, pkzip_slen_bits[entry] + pkzip_clen_bits[entry] + 1
587 );
588
589 32863 pkzip_put_bits(out + 2, &bit_count, pkzip_dist_code[prefix], pkzip_dist_bits[prefix]);
590 32863 pkzip_put_bits(out + 2, &bit_count, encoded_distance & ((1u << suffix) - 1u), suffix);
591 } else {
592 593167 pkzip_put_bits(out + 2, &bit_count, 0, 1);
593 593167 pkzip_put_bits(out + 2, &bit_count, in_buf[i], 8);
594 }
595
596 /* Index every consumed position, including positions inside a match. */
597
2/2
✓ Branch 0 taken 1943896 times.
✓ Branch 1 taken 626030 times.
 2569926 for (; i < end; ++i) {
598
2/2
✓ Branch 0 taken 1943233 times.
✓ Branch 1 taken 663 times.
 1943896 if (in_size - i >= 2) {
599 1943233 uint32_t hash = pair_hash(in_buf + i);
600
601 1943233 history->previous[i & (PKZIP_DICTIONARY_SIZE - 1u)] = history->head[hash];
602 1943233 history->head[hash] = i;
603 }
604 }
605 }
606
607 /* Length table 15, extra value 255: the canonical 0x305 terminator. */
608 671 pkzip_put_bits(out + 2, &bit_count, 0xFF01u, 16);
609 671 free(history);
610 671 *out_buf = out;
611 671 *out_size = (uint32_t)(2 + (bit_count + 7) / 8);
612 671 return 0;
613 }
614
615 /* PKWARE copyright banner kept for parity with the original implementation. */
616 char pkware_copyright[] = "PKWARE Data Compression Library for Win32\r\n"
617 "Copyright 1989-1995 PKWARE Inc. All Rights Reserved\r\n"
618 "Patent No. 5,051,745\r\n"
619 "PKWARE Data Compression Library Reg. U.S. Pat. and Tm. Off.\r\n"
620 "Version 1.11\r\n";
621
622 /*
623 * Initialize PKWARE decoder state and explode the compressed data stream.
624 * The caller owns the work buffer and callback parameter; this routine fills
625 * the codec state, validates the stream header, and delegates expansion.
626 */
627 uint32_t
628 1106 libmpq__pkzip_decompress(uint8_t *work_buf, void *param)
629 {
630
631 /* Caller-provided work buffer interpreted as PKWARE decoder state. */
632 1106 pkzip_cmp_s *mpq_pkzip = (pkzip_cmp_s *)work_buf;
633
634 1106 memset(mpq_pkzip, 0, sizeof(pkzip_cmp_s));
635
636 1106 mpq_pkzip->read_buf = data_read_input;
637 1106 mpq_pkzip->write_buf = data_write_output;
638 1106 mpq_pkzip->param = param;
639 1106 mpq_pkzip->in_pos = 0;
640
641 1106 uint32_t in_size = sizeof(mpq_pkzip->in_buf);
642 1106 mpq_pkzip->in_bytes =
643 1106 mpq_pkzip->read_buf((char *)mpq_pkzip->in_buf, &in_size, mpq_pkzip->param);
644
645 /* An empty stream needs only the two-byte header and its end marker. */
646
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1102 times.
 1106 if (mpq_pkzip->in_bytes < 4) {
647 4 return LIBMPQ_PKZIP_CMP_BAD_DATA;
648 }
649
650 /* The two-byte header selects literal mode and dictionary width. */
651 1102 mpq_pkzip->cmp_type = mpq_pkzip->in_buf[0];
652 1102 mpq_pkzip->dsize_bits = mpq_pkzip->in_buf[1];
653 1102 mpq_pkzip->bit_buf = mpq_pkzip->in_buf[2];
654 1102 mpq_pkzip->extra_bits = 0;
655 1102 mpq_pkzip->in_pos = 3;
656
657
3/4
✓ Branch 0 taken 1101 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1101 times.
 1102 if (4 > mpq_pkzip->dsize_bits || mpq_pkzip->dsize_bits > 6) {
658 1 return LIBMPQ_PKZIP_CMP_INV_DICTSIZE;
659 }
660
661 /* Mask the variable-width distance suffix for the selected dictionary size. */
662 1101 mpq_pkzip->dsize_mask = 0xFFFF >> (0x10 - mpq_pkzip->dsize_bits);
663
664
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1100 times.
 1101 if (mpq_pkzip->cmp_type != LIBMPQ_PKZIP_CMP_BINARY) {
665
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 if (mpq_pkzip->cmp_type != LIBMPQ_PKZIP_CMP_ASCII) {
666 1 return LIBMPQ_PKZIP_CMP_INV_MODE;
667 }
668
669 ✗ memcpy(mpq_pkzip->bits_asc, pkzip_bits_asc, sizeof(mpq_pkzip->bits_asc));
670 ✗ generate_tables_ascii(mpq_pkzip);
671 }
672
673 /* Build lookup tables for copy lengths, distances and optional ASCII literals. */
674 1100 memcpy(mpq_pkzip->slen_bits, pkzip_slen_bits, sizeof(mpq_pkzip->slen_bits));
675 1100 generate_tables_decode(0x10, mpq_pkzip->slen_bits, pkzip_len_code, mpq_pkzip->pos2);
676
677 1100 memcpy(mpq_pkzip->clen_bits, pkzip_clen_bits, sizeof(mpq_pkzip->clen_bits));
678 1100 memcpy(mpq_pkzip->len_base, pkzip_len_base, sizeof(mpq_pkzip->len_base));
679 1100 memcpy(mpq_pkzip->dist_bits, pkzip_dist_bits, sizeof(mpq_pkzip->dist_bits));
680 1100 generate_tables_decode(0x40, mpq_pkzip->dist_bits, pkzip_dist_code, mpq_pkzip->pos1);
681
682
2/2
✓ Branch 1 taken 1098 times.
✓ Branch 2 taken 2 times.
 1100 if (expand(mpq_pkzip) != 0x306) {
683 1098 return LIBMPQ_PKZIP_CMP_NO_ERROR;
684 }
685
686 2 return LIBMPQ_PKZIP_CMP_ABORT;
687 }
688