GCC Code Coverage Report

Directory: src/
File: src/mpq-huffman.c
Date: 2026-10-06 13:47:41
Exec Total Coverage
Lines: 391 468 83.5%
Functions: 18 18 100.0%
Branches: 166 255 65.1%
Line Branch Exec Source
1 /*
2 * mpq-huffman.c -- adaptive Huffman decompression for MPQ block payloads.
3 *
4 * Copyright (c) 2003-2026 Maik Broemme <mbroemme@libmpq.org>
5 *
6 * Differences between C++ and C version:
7 *
8 * - Removed the object-oriented wrapper.
9 * - Replaced translated goto flow with structured C control flow.
10 *
11 * This source was adapted from the C++ version of huffman.cpp included
12 * in stormlib. The C++ version belongs to the following authors:
13 *
14 * Ladislav Zezula <ladik@zezula.net>
15 * ShadowFlare <BlakFlare@hotmail.com>
16 *
17 * This file is free software; you can redistribute it and/or modify
18 * it under the terms of the GNU Lesser General Public License as published by
19 * the Free Software Foundation; either version 2.1 of the License, or
20 * (at your option) any later version.
21 *
22 * This file is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU Lesser General Public License for more details.
26 *
27 * You should have received a copy of the GNU Lesser General Public License
28 * along with this file; if not, see <https://www.gnu.org/licenses/>.
29 */
30
31 #include "mpq-huffman.h"
32 #include "mpq-endian.h"
33 #include <libmpq/mpq.h>
34
35 #include <stdlib.h>
36 #include <string.h>
37
38 /* Initial adaptive Huffman weights indexed by compression type. */
39 static const uint8_t huffman_initial_weights[] = {
40
41 /* Compression type 0x00. */
42 0x0A, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
43 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
44 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
45 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
46 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
47 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
48 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
49 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
50 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
51 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
52 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
53 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
54 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
55 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
56 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
57 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
58 0x00, 0x00,
59
60 /* Compression type 0x01. */
61 0x54, 0x16, 0x16, 0x0D, 0x0C, 0x08, 0x06, 0x05, 0x06, 0x05, 0x06, 0x03, 0x04, 0x04, 0x03, 0x05,
62 0x0E, 0x0B, 0x14, 0x13, 0x13, 0x09, 0x0B, 0x06, 0x05, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02,
63 0x0D, 0x07, 0x09, 0x06, 0x06, 0x04, 0x03, 0x02, 0x04, 0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02,
64 0x09, 0x06, 0x04, 0x04, 0x04, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02, 0x02, 0x03, 0x02, 0x04,
65 0x08, 0x03, 0x04, 0x07, 0x09, 0x05, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x02, 0x03, 0x02, 0x02,
66 0x03, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02,
67 0x06, 0x0A, 0x08, 0x08, 0x06, 0x07, 0x04, 0x03, 0x04, 0x04, 0x02, 0x02, 0x04, 0x02, 0x03, 0x03,
68 0x04, 0x03, 0x07, 0x07, 0x09, 0x06, 0x04, 0x03, 0x03, 0x02, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02,
69 0x0A, 0x02, 0x02, 0x03, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x03, 0x05, 0x02, 0x03,
70 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x03, 0x01, 0x01, 0x01,
71 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x04, 0x04, 0x04, 0x07, 0x09, 0x08, 0x0C, 0x02,
72 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x03,
73 0x04, 0x01, 0x02, 0x04, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
74 0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
75 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
76 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x4B,
77 0x00, 0x00,
78
79 /* Compression type 0x02. */
80 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x27, 0x00, 0x00, 0x23, 0x00, 0x00,
81 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
82 0xFF, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x06, 0x0E, 0x10, 0x04,
83 0x06, 0x08, 0x05, 0x04, 0x04, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03, 0x01, 0x01, 0x02, 0x01, 0x01,
84 0x01, 0x04, 0x02, 0x04, 0x02, 0x02, 0x02, 0x01, 0x01, 0x04, 0x01, 0x01, 0x02, 0x03, 0x03, 0x02,
85 0x03, 0x01, 0x03, 0x06, 0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x01, 0x01,
86 0x01, 0x29, 0x07, 0x16, 0x12, 0x40, 0x0A, 0x0A, 0x11, 0x25, 0x01, 0x03, 0x17, 0x10, 0x26, 0x2A,
87 0x10, 0x01, 0x23, 0x23, 0x2F, 0x10, 0x06, 0x07, 0x02, 0x09, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00,
88 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
89 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
90 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
91 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
92 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
93 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
94 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
95 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
96 0x00, 0x00,
97
98 /* Compression type 0x03. */
99 0xFF, 0x0B, 0x07, 0x05, 0x0B, 0x02, 0x02, 0x02, 0x06, 0x02, 0x02, 0x01, 0x04, 0x02, 0x01, 0x03,
100 0x09, 0x01, 0x01, 0x01, 0x03, 0x04, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
101 0x05, 0x01, 0x01, 0x01, 0x0D, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
102 0x02, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
103 0x0A, 0x04, 0x02, 0x01, 0x06, 0x03, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01,
104 0x05, 0x02, 0x03, 0x04, 0x03, 0x03, 0x03, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x03, 0x03,
105 0x01, 0x03, 0x01, 0x01, 0x02, 0x05, 0x01, 0x01, 0x04, 0x03, 0x05, 0x01, 0x03, 0x01, 0x03, 0x03,
106 0x02, 0x01, 0x04, 0x03, 0x0A, 0x06, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
107 0x02, 0x02, 0x01, 0x0A, 0x02, 0x05, 0x01, 0x01, 0x02, 0x07, 0x02, 0x17, 0x01, 0x05, 0x01, 0x01,
108 0x0E, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
109 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
110 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
111 0x06, 0x02, 0x01, 0x04, 0x05, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
112 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
113 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x07, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
114 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x11,
115 0x00, 0x00,
116
117 /* Compression type 0x04. */
118 0xFF, 0xFB, 0x98, 0x9A, 0x84, 0x85, 0x63, 0x64, 0x3E, 0x3E, 0x22, 0x22, 0x13, 0x13, 0x18, 0x17,
119 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
120 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
121 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
122 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
123 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
124 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
125 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
126 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
127 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
128 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
129 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
130 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
131 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
132 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
133 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
134 0x00, 0x00,
135
136 /* Compression type 0x05. */
137 0xFF, 0xF1, 0x9D, 0x9E, 0x9A, 0x9B, 0x9A, 0x97, 0x93, 0x93, 0x8C, 0x8E, 0x86, 0x88, 0x80, 0x82,
138 0x7C, 0x7C, 0x72, 0x73, 0x69, 0x6B, 0x5F, 0x60, 0x55, 0x56, 0x4A, 0x4B, 0x40, 0x41, 0x37, 0x37,
139 0x2F, 0x2F, 0x27, 0x27, 0x21, 0x21, 0x1B, 0x1C, 0x17, 0x17, 0x13, 0x13, 0x10, 0x10, 0x0D, 0x0D,
140 0x0B, 0x0B, 0x09, 0x09, 0x08, 0x08, 0x07, 0x07, 0x06, 0x05, 0x05, 0x04, 0x04, 0x04, 0x19, 0x18,
141 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
142 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
143 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
144 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
145 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
146 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
147 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
148 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
149 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
150 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
151 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
152 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
153 0x00, 0x00,
154
155 /* Compression type 0x06. */
156 0xC3, 0xCB, 0xF5, 0x41, 0xFF, 0x7B, 0xF7, 0x21, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
157 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
158 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
159 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
160 0xBF, 0xCC, 0xF2, 0x40, 0xFD, 0x7C, 0xF7, 0x22, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
161 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
162 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
163 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
164 0x7A, 0x46, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
165 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
166 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
167 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
168 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
169 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
170 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
171 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
172 0x00, 0x00,
173
174 /* Compression type 0x07. */
175 0xC3, 0xD9, 0xEF, 0x3D, 0xF9, 0x7C, 0xE9, 0x1E, 0xFD, 0xAB, 0xF1, 0x2C, 0xFC, 0x5B, 0xFE, 0x17,
176 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
177 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
178 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
179 0xBD, 0xD9, 0xEC, 0x3D, 0xF5, 0x7D, 0xE8, 0x1D, 0xFB, 0xAE, 0xF0, 0x2C, 0xFB, 0x5C, 0xFF, 0x18,
180 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
181 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
182 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
183 0x70, 0x6C, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
184 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
185 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
186 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
187 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
188 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
189 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
190 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
191 0x00, 0x00,
192
193 /* Compression type 0x08. */
194 0xBA, 0xC5, 0xDA, 0x33, 0xE3, 0x6D, 0xD8, 0x18, 0xE5, 0x94, 0xDA, 0x23, 0xDF, 0x4A, 0xD1, 0x10,
195 0xEE, 0xAF, 0xE4, 0x2C, 0xEA, 0x5A, 0xDE, 0x15, 0xF4, 0x87, 0xE9, 0x21, 0xF6, 0x43, 0xFC, 0x12,
196 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
197 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
198 0xB0, 0xC7, 0xD8, 0x33, 0xE3, 0x6B, 0xD6, 0x18, 0xE7, 0x95, 0xD8, 0x23, 0xDB, 0x49, 0xD0, 0x11,
199 0xE9, 0xB2, 0xE2, 0x2B, 0xE8, 0x5C, 0xDD, 0x15, 0xF1, 0x87, 0xE7, 0x20, 0xF7, 0x44, 0xFF, 0x13,
200 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
201 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
202 0x5F, 0x9E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
203 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
204 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
205 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
206 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
207 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
208 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
209 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
210 0x00, 0x00
211 };
212
213 #define HUFFMAN_INITIAL_WEIGHT_BLOCK_SIZE 258U
214 #define HUFFMAN_INITIAL_WEIGHT_TYPES \
215 (sizeof(huffman_initial_weights) / HUFFMAN_INITIAL_WEIGHT_BLOCK_SIZE)
216
217 /*
218 * Append one least-significant-bit-first bit to the Huffman output stream.
219 * The bit accumulator is flushed only after a complete byte is available,
220 * and capacity failures are reported before writing beyond the destination.
221 */
222 static int32_t
223 5746986 huffman_write_bit(struct huffman_output_stream_s *os, uint32_t bit)
224 {
225 5746986 os->bit_buf |= (bit & 1u) << os->bits++;
226
2/2
✓ Branch 0 taken 718264 times.
✓ Branch 1 taken 5028722 times.
 5746986 if (os->bits == 8) {
227
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 718264 times.
 718264 if (os->out_pos >= os->capacity)
228 ✗ return LIBMPQ_ERROR_SIZE;
229 718264 os->out_buf[os->out_pos++] = (uint8_t)os->bit_buf;
230 718264 os->bit_buf = 0;
231 718264 os->bits = 0;
232 }
233 5746986 return 0;
234 }
235
236 /*
237 * Append a little-endian run of bits to the Huffman output stream.
238 * Bits are emitted from the least significant end because that is the order
239 * used by the MPQ adaptive Huffman wire format.
240 */
241 static int32_t
242 905257 huffman_write_bits(struct huffman_output_stream_s *os, uint32_t value, uint32_t count)
243 {
244
2/2
✓ Branch 0 taken 5746986 times.
✓ Branch 1 taken 905257 times.
 6652243 while (count-- != 0) {
245 5746986 int32_t result = huffman_write_bit(os, value);
246
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5746986 times.
 5746986 if (result < 0)
247 ✗ return result;
248 5746986 value >>= 1;
249 }
250 905257 return 0;
251 }
252
253 /*
254 * Emit the adaptive-tree path for one Huffman symbol.
255 * The path is reconstructed from the leaf toward the root and reversed by
256 * the bit writer so decoder traversal reaches the same symbol.
257 */
258 static int32_t
259 895391 huffman_encode_symbol(struct huffman_output_stream_s *os, struct huffman_tree_item_s *item)
260 {
261 895391 uint32_t bits = 0;
262 895391 uint32_t count = 0;
263 struct huffman_tree_item_s *parent;
264
2/2
✓ Branch 0 taken 5668058 times.
✓ Branch 1 taken 895391 times.
 6563449 for (parent = item->parent; parent != NULL; parent = parent->parent) {
265
2/2
✓ Branch 0 taken 3047613 times.
✓ Branch 1 taken 2620445 times.
 5668058 bits = (bits << 1) | (parent->child->prev == item ? 1u : 0u);
266 5668058 item = parent;
267
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5668058 times.
 5668058 if (++count == 32)
268 ✗ return LIBMPQ_ERROR_FORMAT;
269 }
270 895391 return huffman_write_bits(os, bits, count);
271 }
272
273 /*
274 * Replace the NYT node with an escape branch and the newly seen literal.
275 * Newly introduced bytes are encoded through the escape symbol before they
276 * receive a normal adaptive-tree entry and weight update.
277 */
278 static int32_t
279 9866 huffman_insert_literal(struct huffman_tree_s *ht, uint32_t value)
280 {
281 9866 struct huffman_tree_item_s *escape = ht->last;
282 struct huffman_tree_item_s *old;
283 struct huffman_tree_item_s *literal;
284
2/4
✓ Branch 0 taken 9866 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 9866 times.
 9866 if (escape == NULL || PTR_INT(escape) <= 0)
285 ✗ return LIBMPQ_ERROR_FORMAT;
286 9866 old = libmpq__huffman_acquire_item(ht);
287 9866 literal = libmpq__huffman_acquire_item(ht);
288
2/4
✓ Branch 0 taken 9866 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 9866 times.
 9866 if (old == NULL || literal == NULL)
289 ✗ return LIBMPQ_ERROR_MALLOC;
290 9866 old->parent = escape;
291 9866 old->dcmp_byte = escape->dcmp_byte;
292 9866 old->byte_value = escape->byte_value;
293 9866 literal->parent = escape;
294 9866 literal->dcmp_byte = value;
295 9866 literal->byte_value = 0;
296 9866 escape->child = literal;
297 9866 ht->symbol_nodes[old->dcmp_byte] = old;
298 9866 ht->symbol_nodes[value] = literal;
299 9866 libmpq__huffman_update_weights(ht, literal);
300
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 9866 times.
 9866 if (ht->compression_type_zero == 0)
301 ✗ libmpq__huffman_update_weights(ht, old);
302 9866 return 0;
303 }
304
305 /*
306 * Insert a Huffman tree item before another item in the adaptive list.
307 * The list uses encoded relative links inherited from the StormLib layout,
308 * so each insertion preserves both ordinary and sentinel-linked neighbors.
309 */
310 void
311 3948 libmpq__huffman_insert_item(
312 struct huffman_tree_s *ht, struct huffman_tree_item_s *item, uint32_t where,
313 struct huffman_tree_item_s *item2
314 )
315 {
316 3948 struct huffman_tree_item_s *next = item->next;
317
318 /* Previous item relative to the insertion point. */
319 3948 struct huffman_tree_item_s *prev = item->prev;
320
321 struct huffman_tree_item_s *prev2;
322
323 /* Relative previous-link offset from the original pointer encoding. */
324 intptr_t next2;
325
326
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3948 times.
 3948 if (next != 0) {
327
328 /* Resolve encoded previous-item references from the original tree layout. */
329 ✗ if (PTR_INT(prev) < 0) {
330 ✗ prev = PTR_NOT(prev);
331 } else {
332 ✗ prev += (item - next->prev);
333 }
334
335 ✗ prev->next = next;
336 ✗ next->prev = prev;
337
338 ✗ item->next = 0;
339 ✗ item->prev = 0;
340 }
341
342
1/2
✓ Branch 0 taken 3948 times.
✗ Branch 1 not taken.
 3948 if (item2 == NULL) {
343 3948 item2 = PTR_PTR(&ht->first);
344 }
345
346
2/3
✓ Branch 0 taken 2820 times.
✓ Branch 1 taken 1128 times.
✗ Branch 2 not taken.
 3948 switch (where) {
347 2820 case SWITCH_ITEMS:
348
349 /* Reinsert item before item2->next while preserving the encoded first-link slot. */
350 2820 item->next = item2->next;
351 2820 item->prev = item2->next->prev;
352 2820 item2->next->prev = item;
353
354 2820 item2->next = item;
355 2820 return;
356 1128 case INSERT_ITEM:
357
358 1128 item->next = item2;
359 1128 item->prev = item2->prev;
360 1128 next2 = PTR_INT(ht->insertion_scratch);
361 1128 prev2 = item2->prev;
362
363
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1128 times.
 1128 if (PTR_INT(prev2) < 0) {
364 ✗ prev2 = PTR_NOT(prev);
365 ✗ prev2->next = item;
366
367 ✗ item2->prev = item;
368 ✗ return;
369 }
370
371
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1128 times.
 1128 if (next2 < 0) {
372 ✗ next2 = item2 - item2->next->prev;
373 }
374
375 1128 prev2 += next2;
376 1128 prev2->next = item;
377 1128 item2->prev = item;
378 1128 return;
379 ✗ default:
380 ✗ return;
381 }
382 }
383
384 /*
385 * Remove a Huffman item from the adaptive linked list.
386 * Sentinel references and relative previous pointers are resolved before the
387 * item is detached, leaving it available for later tree-item reuse.
388 */
389 void
390 564 libmpq__huffman_remove_item(struct huffman_tree_s *ht, struct huffman_tree_item_s *hi)
391 {
392
393 /* Previous-link scratch value used while unlinking the item. */
394 struct huffman_tree_item_s *temp;
395
396
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (hi->next != NULL) {
397 564 temp = hi->prev;
398
399
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (PTR_INT(temp) <= 0) {
400 564 temp = PTR_NOT(temp);
401
402
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 564 times.
 564 if (temp == PTR_PTR(&ht->current_sentinel)) {
403 ✗ ht->current_sentinel = hi->next;
404
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 } else if (temp == PTR_PTR(&ht->first)) {
405 564 ht->first = hi->next;
406 }
407 } else {
408 ✗ temp += (hi - hi->next->prev);
409
410 ✗ temp->next = hi->next;
411 }
412
413 564 hi->next->prev = hi->prev;
414 564 hi->next = hi->prev = NULL;
415 }
416 564 }
417
418 /*
419 * Resolve the previous Huffman tree item, including encoded relative pointers.
420 * A negative link is a direct encoded reference, while a non-negative value
421 * is interpreted relative to the neighboring item and supplied offset.
422 */
423 struct huffman_tree_item_s *
424 973376 libmpq__huffman_previous_item(struct huffman_tree_item_s *hi, intptr_t value)
425 {
426
427 /* Negative pointer values encode direct references in the original layout. */
428
2/2
✓ Branch 0 taken 1128 times.
✓ Branch 1 taken 972248 times.
 973376 if (PTR_INT(hi->prev) < 0) {
429 1128 return PTR_NOT(hi->prev);
430 }
431
432
1/2
✓ Branch 0 taken 972248 times.
✗ Branch 1 not taken.
 972248 if (value < 0) {
433 972248 value = hi - hi->next->prev;
434 }
435
436
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 972248 times.
 972248 if (hi->prev == NULL) {
437 ✗ return NULL;
438 }
439
440 972248 return hi->prev + value;
441 }
442
443 /*
444 * Refill the bit accumulator with complete input bytes until it contains the
445 * requested number of bits. The final byte is handled without a word-sized
446 * lookahead, so a valid stream tail cannot read beyond its input buffer.
447 */
448 static int
449 5113255 huffman_refill(struct huffman_input_stream_s *is, uint32_t required_bits)
450 {
451
4/4
✓ Branch 0 taken 888921 times.
✓ Branch 1 taken 5113253 times.
✓ Branch 2 taken 888919 times.
✓ Branch 3 taken 2 times.
 6002174 while (is->bits < required_bits && is->in_buf < is->in_end) {
452 888919 is->bit_buf |= (uint32_t)*is->in_buf++ << is->bits;
453 888919 is->bits += 8;
454 }
455
456
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5113253 times.
 5113255 if (is->bits < required_bits) {
457 2 is->failed = 1;
458 2 return 0;
459 }
460
461 5113253 return 1;
462 }
463
464 /* Read one bit from the bounded Huffman input stream. */
465 uint32_t
466 3772667 libmpq__huffman_read_bit(struct huffman_input_stream_s *is)
467 {
468 uint32_t bit;
469
470
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3772666 times.
 3772667 if (!huffman_refill(is, 1)) {
471 1 return 0;
472 }
473
474 3772666 bit = is->bit_buf & 1;
475 3772666 is->bit_buf >>= 1;
476 3772666 is->bits--;
477
478 3772666 return bit;
479 }
480
481 /*
482 * Peek at the next seven Huffman bits without consuming them.
483 * The seven-bit prefix feeds the adaptive decoder's quick lookup cache, so
484 * refilling never changes the logical input position.
485 */
486 uint32_t
487 1325058 libmpq__huffman_peek_seven_bits(struct huffman_input_stream_s *is)
488 {
489
490 /* Ensure the quick-decode prefix is fully available. */
491
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1325058 times.
 1325058 if (!huffman_refill(is, 7)) {
492 ✗ return 0;
493 }
494
495 1325058 return (is->bit_buf & 0x7F);
496 }
497
498 /*
499 * Read one byte from the bounded Huffman input stream, refilling only from
500 * bytes that remain inside the compressed input range.
501 */
502 uint32_t
503 15530 libmpq__huffman_read_byte(struct huffman_input_stream_s *is)
504 {
505
506 /* Byte extracted from the low bits of the input buffer. */
507 uint32_t one_byte;
508
509 /* Refill before consuming a byte that crosses the current bit buffer. */
510
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 15529 times.
 15530 if (!huffman_refill(is, 8)) {
511 1 return 0;
512 }
513
514 15529 one_byte = (is->bit_buf & 0xFF);
515 15529 is->bit_buf >>= 8;
516 15529 is->bits -= 8;
517
518 15529 return one_byte;
519 }
520
521 /*
522 * Allocate or recycle a Huffman tree item and move it to the front list.
523 * Reuse keeps the fixed tree pool bounded while preserving the linked-list
524 * ordering required by adaptive weight updates.
525 */
526 static int
527 1 huffman_item_reference_valid(
528 const struct huffman_tree_s *ht, const struct huffman_tree_item_s *item
529 )
530 {
531 1 uintptr_t address = (uintptr_t)item;
532 1 uintptr_t first = (uintptr_t)&ht->node_pool[0];
533 1 uintptr_t end = (uintptr_t)&ht->node_pool[sizeof(ht->node_pool) / sizeof(ht->node_pool[0])];
534
535
2/4
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
 1 if (item == PTR_PTR(&ht->current_sentinel) || item == PTR_PTR(&ht->first)) {
536 ✗ return 1;
537 }
538
539
1/6
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 1 return address >= first && address < end && (address - first) % sizeof(ht->node_pool[0]) == 0;
540 }
541
542 /* Acquire a bounded item from the adaptive tree's fixed node pool. */
543 struct huffman_tree_item_s *
544 50048 libmpq__huffman_acquire_item(struct huffman_tree_s *ht)
545 {
546 50048 struct huffman_tree_item_s *p_item1 = ht->next_reusable_item;
547 struct huffman_tree_item_s *p_item2;
548
549 /* Temporary item and pointer-array state used by the original tree update routine. */
550 struct huffman_tree_item_s *p_next;
551 struct huffman_tree_item_s *p_prev;
552
553
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 50047 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 50048 if (PTR_INT(p_item1) > 0 && !huffman_item_reference_valid(ht, p_item1)) {
554 1 return NULL;
555 }
556
557
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 50047 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 50047 if (PTR_INT(p_item1) <= 0 || (p_item2 = p_item1) == NULL) {
558
2/2
✓ Branch 0 taken 50046 times.
✓ Branch 1 taken 1 times.
 50047 if (ht->items < sizeof(ht->node_pool) / sizeof(ht->node_pool[0])) {
559 50046 p_item2 = &ht->node_pool[ht->items++];
560 50046 p_item1 = p_item2;
561 } else {
562 1 return NULL;
563 }
564 } else {
565 ✗ p_item1 = p_item2;
566 }
567
568 50046 p_next = p_item1->next;
569
570
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50046 times.
 50046 if (p_next != NULL) {
571 ✗ p_prev = p_item1->prev;
572
573 ✗ if (PTR_INT(p_prev) <= 0) {
574 ✗ p_prev = PTR_NOT(p_prev);
575 } else {
576 ✗ p_prev += (p_item1 - p_item1->next->prev);
577 }
578
579 ✗ p_prev->next = p_next;
580 ✗ p_next->prev = p_prev;
581 ✗ p_item1->next = NULL;
582 ✗ p_item1->prev = NULL;
583 }
584
585 50046 p_item1->next = PTR_PTR(&ht->first);
586 50046 p_item1->prev = ht->last;
587
588 50046 p_prev = ht->last;
589
590
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50046 times.
 50046 if (PTR_INT(p_prev) <= 0) {
591 ✗ p_prev = PTR_NOT(p_prev);
592 ✗ p_prev->next = p_item1;
593 ✗ p_prev->prev = p_item2;
594 ✗ p_item2->parent = NULL;
595 ✗ p_item2->child = NULL;
596 } else {
597
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50046 times.
 50046 if (PTR_INT(ht->insertion_scratch) < 0) {
598 ✗ p_prev += PTR_PTR(&ht->first) - ht->first->prev;
599 } else {
600 50046 p_prev += PTR_INT(ht->insertion_scratch);
601 }
602
603 50046 p_prev->next = p_item1;
604 50046 ht->last = p_item2;
605 50046 p_item2->parent = NULL;
606 50046 p_item2->child = NULL;
607 }
608
609 50046 return p_item2;
610 }
611
612 /*
613 * Increase adaptive Huffman weights and reorder items to keep the tree sorted.
614 * Every ancestor is updated, and nodes are moved when their new weight would
615 * violate the monotonic ordering used by the encoder and decoder.
616 */
617 void
618 2244907 libmpq__huffman_update_weights(struct huffman_tree_s *ht, struct huffman_tree_item_s *p_item)
619 {
620 struct huffman_tree_item_s *p_item1;
621 2244907 struct huffman_tree_item_s *p_item2 = NULL;
622 struct huffman_tree_item_s *p_item3;
623 struct huffman_tree_item_s *p_prev;
624
625 /* Walk toward the root, increasing weights and moving nodes forward as needed. */
626
2/2
✓ Branch 0 taken 15076011 times.
✓ Branch 1 taken 2244907 times.
 17320918 for (; p_item != NULL; p_item = p_item->parent) {
627 15076011 p_item->byte_value++;
628
629 17060107 for (p_item1 = p_item;; p_item1 = p_prev) {
630 17060107 p_prev = p_item1->prev;
631
632
2/2
✓ Branch 0 taken 2244907 times.
✓ Branch 1 taken 14815200 times.
 17060107 if (PTR_INT(p_prev) <= 0) {
633 2244907 p_prev = NULL;
634 2244907 break;
635 }
636
637
2/2
✓ Branch 0 taken 12831104 times.
✓ Branch 1 taken 1984096 times.
 14815200 if (p_prev->byte_value >= p_item->byte_value) {
638 12831104 break;
639 }
640 }
641
642
2/2
✓ Branch 0 taken 14589887 times.
✓ Branch 1 taken 486124 times.
 15076011 if (p_item1 == p_item) {
643 14589887 continue;
644 }
645
646
1/2
✓ Branch 0 taken 486124 times.
✗ Branch 1 not taken.
 486124 if (p_item1->next != NULL) {
647 486124 p_item2 = libmpq__huffman_previous_item(p_item1, -1);
648 486124 p_item2->next = p_item1->next;
649 486124 p_item1->next->prev = p_item1->prev;
650 486124 p_item1->next = NULL;
651 486124 p_item1->prev = NULL;
652 }
653
654 486124 p_item2 = p_item->next;
655 486124 p_item1->next = p_item2;
656 486124 p_item1->prev = p_item2->prev;
657 486124 p_item2->prev = p_item1;
658 486124 p_item->next = p_item1;
659
660
1/2
✓ Branch 0 taken 486124 times.
✗ Branch 1 not taken.
 486124 if (p_item1 != NULL) {
661 486124 p_item2 = libmpq__huffman_previous_item(p_item, -1);
662 486124 p_item2->next = p_item->next;
663 486124 p_item->next->prev = p_item->prev;
664 486124 p_item->next = NULL;
665 486124 p_item->prev = NULL;
666 }
667
668
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 486124 times.
 486124 if (p_prev == NULL) {
669 ✗ p_prev = PTR_PTR(&ht->first);
670 }
671
672 486124 p_item2 = p_prev->next;
673 486124 p_item->next = p_item2;
674 486124 p_item->prev = p_item2->prev;
675 486124 p_item2->prev = p_item;
676 486124 p_prev->next = p_item;
677 486124 p_item3 = p_item1->parent->child;
678 486124 p_item2 = p_item->parent;
679
680
2/2
✓ Branch 0 taken 280398 times.
✓ Branch 1 taken 205726 times.
 486124 if (p_item2->child == p_item) {
681 280398 p_item2->child = p_item1;
682 }
683
684
2/2
✓ Branch 0 taken 236792 times.
✓ Branch 1 taken 249332 times.
 486124 if (p_item3 == p_item1) {
685 236792 p_item1->parent->child = p_item;
686 }
687
688 486124 p_item2 = p_item->parent;
689 486124 p_item->parent = p_item1->parent;
690 486124 p_item1->parent = p_item2;
691
692 486124 ht->tree_update_generation++;
693 }
694 2244907 }
695
696 /*
697 * Initialize the adaptive Huffman tree with fresh sentinels and lookup cache state.
698 * This resets the fixed node pool, encoded-link sentinels, reusable-item cursor,
699 * and decoder cache so no adaptive state leaks between MPQ blocks.
700 */
701 void
702 568 libmpq__huffman_tree_init(struct huffman_tree_s *ht, uint32_t cmp)
703 {
704
705 /* Tree item cursor and remaining item count. */
706 uint32_t count;
707 struct huffman_tree_item_s *hi;
708
709
2/2
✓ Branch 0 taken 292520 times.
✓ Branch 1 taken 568 times.
 293088 for (hi = ht->node_pool, count = 0x203; count != 0; hi++, count--) {
710 292520 hi->next = hi->prev = NULL;
711 }
712
713 /* Recreate the sentinel links used by the adaptive tree list. */
714 568 ht->encoded_sentinel = NULL;
715 568 ht->current_sentinel = PTR_PTR(&ht->current_sentinel);
716 568 ht->next_reusable_item = PTR_NOT(ht->current_sentinel);
717 568 ht->insertion_scratch = NULL;
718 568 ht->first = PTR_PTR(&ht->first);
719 568 ht->last = PTR_NOT(ht->first);
720 568 ht->tree_update_generation = 1;
721 568 ht->items = 0;
722
723 /* Decompression starts with an empty seven-bit quick-decode cache. */
724
2/2
✓ Branch 0 taken 375 times.
✓ Branch 1 taken 193 times.
 568 if (cmp == LIBMPQ_HUFF_DECOMPRESS) {
725 375 for (count = 0;
726
2/2
✓ Branch 0 taken 48000 times.
✓ Branch 1 taken 375 times.
 48375 count < sizeof(ht->quick_decode_cache) / sizeof(struct huffman_decompress_s);
727 48000 count++) {
728 48000 ht->quick_decode_cache[count].tree_update_generation = 0;
729 }
730 }
731 568 }
732
733 /*
734 * Build the adaptive Huffman tree using the first byte already loaded from the stream.
735 * The compression type selects the initial weight table, after which symbols
736 * and internal nodes are inserted in the canonical adaptive-list order.
737 */
738 void
739 564 libmpq__huffman_tree_build(struct huffman_tree_s *ht, uint32_t cmp_type)
740 {
741
742 /* Greatest weight found while inserting initial symbols. */
743 uint32_t max_byte;
744
745 /* Compression-specific initial weight table. */
746 const uint8_t *byte_array;
747
748 /* Tracks whether the translated control flow found a matching insertion point. */
749 uint32_t found;
750
751 struct huffman_tree_item_s **p_item;
752 struct huffman_tree_item_s *child1;
753
754 /* Loop index used while rebuilding quick-decode tables. */
755 uint32_t i;
756
757 /* Move pending last-list items back into the main linked list. */
758
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 564 times.
 564 while (PTR_INT(ht->last) > 0) {
759 struct huffman_tree_item_s *temp;
760 ✗ if (ht->last->next != NULL) {
761 ✗ libmpq__huffman_remove_item(ht, ht->last);
762 }
763
764 ✗ ht->next_reusable_item = PTR_PTR(&ht->current_sentinel);
765 ✗ ht->last->prev = ht->next_reusable_item;
766 ✗ temp = libmpq__huffman_previous_item(
767 ✗ PTR_PTR(&ht->current_sentinel), PTR_INT(&ht->encoded_sentinel)
768 );
769 ✗ temp->next = ht->last;
770 ✗ ht->current_sentinel = ht->last;
771 }
772
773 /* Clear symbol lookup pointers before rebuilding the adaptive population. */
774 564 memset(ht->symbol_nodes, 0, sizeof(ht->symbol_nodes));
775
776 564 max_byte = 0;
777
778 564 p_item = (struct huffman_tree_item_s **)&ht->symbol_nodes;
779
780 564 cmp_type &= 0xFF;
781
782 /* Each compression type has 258 initial symbol weights. */
783 564 byte_array = huffman_initial_weights + cmp_type * 258;
784
785 /* Insert weighted literal symbols in the order required by the wire format. */
786
2/2
✓ Branch 0 taken 144384 times.
✓ Branch 1 taken 564 times.
 144948 for (i = 0; i < 0x100; i++, p_item++) {
787
788 /* Reuse a pending tree item or allocate the next item from the static pool. */
789 144384 struct huffman_tree_item_s *item = ht->next_reusable_item;
790 struct huffman_tree_item_s *p_item3;
791 144384 uint8_t one_byte = byte_array[i];
792
793
2/2
✓ Branch 0 taken 143256 times.
✓ Branch 1 taken 1128 times.
 144384 if (byte_array[i] == 0) {
794 143256 continue;
795 }
796
797
1/2
✓ Branch 0 taken 1128 times.
✗ Branch 1 not taken.
 1128 if (PTR_INT(item) <= 0) {
798 1128 item = &ht->node_pool[ht->items++];
799 }
800
801 1128 libmpq__huffman_insert_item(ht, item, SWITCH_ITEMS, NULL);
802
803 1128 item->parent = NULL;
804 1128 item->child = NULL;
805
806 1128 *p_item = item;
807 1128 item->dcmp_byte = i;
808 1128 item->byte_value = one_byte;
809
810
2/2
✓ Branch 0 taken 564 times.
✓ Branch 1 taken 564 times.
 1128 if (one_byte >= max_byte) {
811 564 max_byte = one_byte;
812 564 continue;
813 }
814
815 /* Reinsert before the first node with a high enough adaptive weight. */
816 564 found = 0;
817
818
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (PTR_INT((p_item3 = ht->last)) > 0) {
819
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (p_item3 != NULL) {
820 do {
821
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (p_item3->byte_value >= one_byte) {
822 564 found = 1;
823 564 break;
824 }
825
826 ✗ p_item3 = p_item3->prev;
827 ✗ } while (PTR_INT(p_item3) > 0);
828 }
829 }
830
831
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 564 times.
 564 if (found == 0) {
832 ✗ p_item3 = NULL;
833 }
834
835
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (item->next != NULL) {
836 564 libmpq__huffman_remove_item(ht, item);
837 }
838
839
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 564 times.
 564 if (p_item3 == NULL) {
840 ✗ p_item3 = PTR_PTR(&ht->first);
841 }
842
843 564 item->next = p_item3->next;
844 564 item->prev = p_item3->next->prev;
845 564 p_item3->next->prev = item;
846 564 p_item3->next = item;
847 }
848
849 /* Add the escape and end-of-stream control symbols after literal symbols. */
850
2/2
✓ Branch 0 taken 1128 times.
✓ Branch 1 taken 564 times.
 1692 for (; i < 0x102; i++) {
851 1128 struct huffman_tree_item_s **p_item2 = &ht->symbol_nodes[i];
852 1128 struct huffman_tree_item_s *item2 = ht->next_reusable_item;
853
854
1/2
✓ Branch 0 taken 1128 times.
✗ Branch 1 not taken.
 1128 if (PTR_INT(item2) <= 0) {
855 1128 item2 = &ht->node_pool[ht->items++];
856 }
857
858 1128 libmpq__huffman_insert_item(ht, item2, INSERT_ITEM, NULL);
859
860 1128 item2->dcmp_byte = i;
861 1128 item2->byte_value = 1;
862 1128 item2->parent = NULL;
863 1128 item2->child = NULL;
864 1128 *p_item2++ = item2;
865 }
866
867 /* Pair the lowest-weight nodes into parents until the tree has one root. */
868
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
 564 if (PTR_INT((child1 = ht->last)) > 0) {
869 struct huffman_tree_item_s *child2;
870 struct huffman_tree_item_s *item;
871
872
2/2
✓ Branch 0 taken 1692 times.
✓ Branch 1 taken 564 times.
 2256 while (PTR_INT((child2 = child1->prev)) > 0) {
873
1/2
✓ Branch 0 taken 1692 times.
✗ Branch 1 not taken.
 1692 if (PTR_INT((item = ht->next_reusable_item)) <= 0) {
874 1692 item = &ht->node_pool[ht->items++];
875 }
876
877 1692 libmpq__huffman_insert_item(ht, item, SWITCH_ITEMS, NULL);
878
879 1692 item->parent = NULL;
880 1692 item->child = NULL;
881
882 1692 item->byte_value = child1->byte_value + child2->byte_value;
883
884 1692 item->child = child1;
885 1692 child1->parent = item;
886 1692 child2->parent = item;
887
888
2/2
✓ Branch 0 taken 564 times.
✓ Branch 1 taken 1128 times.
 1692 if (item->byte_value >= max_byte) {
889 564 max_byte = item->byte_value;
890 } else {
891 1128 struct huffman_tree_item_s *p_item2 = child2->prev;
892 1128 found = 0;
893
894
1/2
✓ Branch 0 taken 1128 times.
✗ Branch 1 not taken.
 1128 if (PTR_INT(p_item2) > 0) {
895 do {
896
1/2
✓ Branch 0 taken 1128 times.
✗ Branch 1 not taken.
 1128 if (p_item2->byte_value >= item->byte_value) {
897 1128 found = 1;
898 1128 break;
899 }
900
901 ✗ p_item2 = p_item2->prev;
902 ✗ } while (PTR_INT(p_item2) > 0);
903 }
904
905
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1128 times.
 1128 if (found == 0) {
906 ✗ p_item2 = NULL;
907 }
908
909
1/2
✓ Branch 0 taken 1128 times.
✗ Branch 1 not taken.
 1128 if (item->next != 0) {
910
911 /* Previous item resolved before unlinking this child. */
912 1128 struct huffman_tree_item_s *temp4 = libmpq__huffman_previous_item(item, -1);
913
914 /* Relink the previous item to skip the removed child. */
915 1128 temp4->next = item->next;
916
917 /* Preserve the encoded previous reference on the next item. */
918 1128 item->next->prev = item->prev;
919 1128 item->next = NULL;
920 1128 item->prev = NULL;
921 }
922
923
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1128 times.
 1128 if (p_item2 == NULL) {
924 ✗ p_item2 = PTR_PTR(&ht->first);
925 }
926
927 1128 item->next = p_item2->next;
928 1128 item->prev = p_item2->next->prev;
929
930 /* Insert the item before the next sibling. */
931 1128 p_item2->next->prev = item;
932 1128 p_item2->next = item;
933 }
934
935
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1692 times.
 1692 if (PTR_INT((child1 = child2->prev)) <= 0) {
936 ✗ break;
937 }
938 }
939 }
940
941 564 ht->tree_update_generation = 1;
942 564 }
943
944 /*
945 * Decode the Huffman bitstream into the output buffer.
946 * It combines cached prefix traversal with adaptive tree walking, handles
947 * literal-introduction and end markers, and stops at the requested output size.
948 */
949 int32_t
950 373 libmpq__huffman_decode(
951 struct huffman_tree_s *ht, struct huffman_input_stream_s *is, uint8_t *out_buf,
952 uint32_t out_length
953 )
954 {
955
956 /* Output cursor, decoded symbol and adaptive tree traversal state. */
957 373 uint32_t dcmp_byte = 0;
958 373 uint8_t *out_pos = out_buf;
959 uint32_t bit_count;
960 struct huffman_decompress_s *qd;
961 struct huffman_tree_item_s *p_item1;
962 struct huffman_tree_item_s *p_item2;
963
964 /* 8 bits loaded from input stream. */
965 uint32_t n8bits;
966
967 /* 7 bits loaded from input stream. */
968 uint32_t n7bits;
969
970 /* Tracks translated control flow that replaced gotos in the original source. */
971 uint32_t found;
972
973 /* Select whether the quick-decode table can satisfy the current bit prefix. */
974 uint32_t has_qd;
975
976 /* Nothing can be written when the caller requested a zero-length output. */
977
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 373 times.
 373 if (out_length == 0) {
978 ✗ return 0;
979 }
980
981 /* The first byte selects the initial tree weights and decoder mode. */
982 373 n8bits = libmpq__huffman_read_byte(is);
983
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 372 times.
 373 if (is->failed) {
984 1 return LIBMPQ_ERROR_UNPACK;
985 }
986
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 371 times.
 372 if (n8bits >= HUFFMAN_INITIAL_WEIGHT_TYPES) {
987 1 return LIBMPQ_ERROR_UNPACK;
988 }
989
990 371 libmpq__huffman_tree_build(ht, n8bits);
991
992 /* Compression type 0 uses 8-bit literal handling. */
993 371 ht->compression_type_zero = (n8bits == 0) ? 1 : 0;
994
995 for (;;) {
996 1325057 n7bits = libmpq__huffman_peek_seven_bits(is);
997
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1325057 times.
 1325057 if (is->failed) {
998 ✗ return LIBMPQ_ERROR_UNPACK;
999 }
1000
1001 /* Quick-decode entries cache symbols for seven-bit prefixes after tree updates. */
1002 1325057 qd = &ht->quick_decode_cache[n7bits];
1003 1325057 has_qd = (qd->tree_update_generation >= ht->tree_update_generation) ? 1 : 0;
1004
1005 /* Prefer a cache entry, falling back to tree traversal after updates. */
1006
2/2
✓ Branch 0 taken 750868 times.
✓ Branch 1 taken 574189 times.
 1325057 if (has_qd) {
1007 750868 found = 0;
1008
2/2
✓ Branch 0 taken 178358 times.
✓ Branch 1 taken 572510 times.
 750868 if (qd->bits > 7) {
1009 178358 is->bit_buf >>= 7;
1010 178358 is->bits -= 7;
1011 178358 p_item1 = qd->value.p_item;
1012 178358 found = 1;
1013 }
1014
2/2
✓ Branch 0 taken 572510 times.
✓ Branch 1 taken 178358 times.
 750868 if (found == 0) {
1015 572510 is->bit_buf >>= qd->bits;
1016 572510 is->bits -= qd->bits;
1017 572510 dcmp_byte = qd->value.dcmp_byte;
1018 }
1019 } else {
1020 574189 found = 1;
1021 574189 p_item1 = ht->first->next->prev;
1022
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 574189 times.
 574189 if (PTR_INT(p_item1) <= 0) {
1023 ✗ p_item1 = NULL;
1024 }
1025 }
1026
1027
2/2
✓ Branch 0 taken 752547 times.
✓ Branch 1 taken 572510 times.
 1325057 if (found == 1) {
1028
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 752547 times.
 752547 if (p_item1 == NULL) {
1029 ✗ return 0;
1030 }
1031
1032 752547 bit_count = 0;
1033 752547 p_item2 = NULL;
1034
1035 /* Walk one adaptive branch per input bit until reaching a leaf. */
1036 do {
1037 3772666 p_item1 = p_item1->child;
1038
1039
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3772666 times.
 3772666 if (p_item1 == NULL) {
1040 ✗ return 0;
1041 }
1042
1043
2/2
✓ Branch 1 taken 1991069 times.
✓ Branch 2 taken 1781597 times.
 3772666 if (libmpq__huffman_read_bit(is)) {
1044 1991069 p_item1 = p_item1->prev;
1045
1046
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1991069 times.
 1991069 if (p_item1 == NULL) {
1047 ✗ return 0;
1048 }
1049 }
1050
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3772666 times.
 3772666 if (is->failed) {
1051 ✗ return LIBMPQ_ERROR_UNPACK;
1052 }
1053
1054 /* Store the seventh-level item so the quick cache can resume from it later. */
1055
2/2
✓ Branch 0 taken 242769 times.
✓ Branch 1 taken 3529897 times.
 3772666 if (++bit_count == 7) {
1056 242769 p_item2 = p_item1;
1057 }
1058
2/2
✓ Branch 0 taken 3020119 times.
✓ Branch 1 taken 752547 times.
 3772666 } while (p_item1->child != NULL);
1059
1060
2/2
✓ Branch 0 taken 574189 times.
✓ Branch 1 taken 178358 times.
 752547 if (has_qd == 0) {
1061
2/2
✓ Branch 0 taken 144710 times.
✓ Branch 1 taken 429479 times.
 574189 if (bit_count > 7) {
1062 144710 qd->tree_update_generation = ht->tree_update_generation;
1063 144710 qd->bits = bit_count;
1064 144710 qd->value.p_item = p_item2;
1065 } else {
1066 429479 uint32_t index = n7bits & (0xFFFFFFFF >> (32 - bit_count));
1067 429479 uint32_t add = (1 << bit_count);
1068
1069
2/2
✓ Branch 0 taken 3414321 times.
✓ Branch 1 taken 429479 times.
 3843800 for (qd = &ht->quick_decode_cache[index]; index <= 0x7F;
1070 3414321 index += add, qd += add) {
1071 3414321 qd->tree_update_generation = ht->tree_update_generation;
1072 3414321 qd->bits = bit_count;
1073 3414321 qd->value.dcmp_byte = p_item1->dcmp_byte;
1074 }
1075 }
1076 }
1077
1078 752547 dcmp_byte = p_item1->dcmp_byte;
1079 }
1080
1081 /*
1082 * Escape symbols carry a literal byte not yet present in the tree and
1083 * split the current escape node into an old branch and a new literal.
1084 */
1085
2/2
✓ Branch 0 taken 15157 times.
✓ Branch 1 taken 1309900 times.
 1325057 if (dcmp_byte == 0x101) {
1086 15157 n8bits = libmpq__huffman_read_byte(is);
1087
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15157 times.
 15157 if (is->failed) {
1088 ✗ return LIBMPQ_ERROR_UNPACK;
1089 }
1090
1/2
✓ Branch 0 taken 15157 times.
✗ Branch 1 not taken.
 15157 p_item1 = (PTR_INT(ht->last) <= 0) ? NULL : ht->last;
1091
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15157 times.
 15157 if (p_item1 == NULL) {
1092 ✗ return 0;
1093 }
1094 15157 p_item2 = libmpq__huffman_acquire_item(ht);
1095
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15157 times.
 15157 if (p_item2 == NULL) {
1096 ✗ return LIBMPQ_ERROR_UNPACK;
1097 }
1098 15157 p_item2->parent = p_item1;
1099 15157 p_item2->dcmp_byte = p_item1->dcmp_byte;
1100 15157 p_item2->byte_value = p_item1->byte_value;
1101 15157 ht->symbol_nodes[p_item2->dcmp_byte] = p_item2;
1102 15157 p_item2 = libmpq__huffman_acquire_item(ht);
1103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15157 times.
 15157 if (p_item2 == NULL) {
1104 ✗ return LIBMPQ_ERROR_UNPACK;
1105 }
1106 15157 p_item2->parent = p_item1;
1107 15157 p_item2->dcmp_byte = n8bits;
1108 15157 p_item2->byte_value = 0;
1109 15157 ht->symbol_nodes[p_item2->dcmp_byte] = p_item2;
1110 15157 p_item1->child = p_item2;
1111
1112 15157 libmpq__huffman_update_weights(ht, p_item2);
1113
1114
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 15157 times.
 15157 if (ht->compression_type_zero == 0) {
1115 ✗ libmpq__huffman_update_weights(ht, ht->symbol_nodes[n8bits]);
1116 }
1117
1118 15157 dcmp_byte = n8bits;
1119 }
1120
1121 /* The end marker terminates decoding before another output byte is written. */
1122
2/2
✓ Branch 0 taken 212 times.
✓ Branch 1 taken 1324845 times.
 1325057 if (dcmp_byte == 0x100) {
1123 212 break;
1124 }
1125
1126 1324845 *out_pos++ = (uint8_t)dcmp_byte;
1127
2/2
✓ Branch 0 taken 159 times.
✓ Branch 1 taken 1324686 times.
 1324845 if (--out_length == 0) {
1128 159 break;
1129 }
1130
1131
1/2
✓ Branch 0 taken 1324686 times.
✗ Branch 1 not taken.
 1324686 if (ht->compression_type_zero) {
1132 1324686 libmpq__huffman_update_weights(ht, ht->symbol_nodes[dcmp_byte]);
1133 }
1134 }
1135
1136 371 return (out_pos - out_buf);
1137 }
1138
1139 /*
1140 * Encode a byte stream using the MPQ adaptive Huffman wire format.
1141 * The encoder emits the initial type byte, introduces unseen literals through
1142 * the escape node, writes the end marker, and pads the stream to MPQ alignment.
1143 */
1144 int32_t
1145 193 libmpq__huffman_encode(
1146 struct huffman_tree_s *ht, struct huffman_output_stream_s *os, const uint8_t *in_buf,
1147 uint32_t in_length
1148 )
1149 {
1150 uint32_t i;
1151
5/10
✓ Branch 0 taken 193 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 193 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 193 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 193 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 193 times.
 193 if (ht == NULL || os == NULL || (in_length != 0 && in_buf == NULL) || os->capacity < 4)
1152 ✗ return LIBMPQ_ERROR_FORMAT;
1153
1154 /* Reserve the first byte for the compression type before writing symbols. */
1155 193 os->out_pos = 1;
1156 193 os->bit_buf = 0;
1157 193 os->bits = 0;
1158 193 os->out_buf[0] = 0;
1159 193 libmpq__huffman_tree_init(ht, LIBMPQ_HUFF_COMPRESS);
1160 193 libmpq__huffman_tree_build(ht, 0);
1161 193 ht->compression_type_zero = 1;
1162
1163 /* Encode each input byte while keeping the tree synchronized with decoding. */
1164
2/2
✓ Branch 0 taken 895198 times.
✓ Branch 1 taken 193 times.
 895391 for (i = 0; i < in_length; i++) {
1165 895198 uint32_t value = in_buf[i];
1166 895198 struct huffman_tree_item_s *item = ht->symbol_nodes[value];
1167
2/2
✓ Branch 0 taken 9866 times.
✓ Branch 1 taken 885332 times.
 895198 if (item == NULL) {
1168
2/4
✓ Branch 1 taken 9866 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 9866 times.
 19732 if (huffman_encode_symbol(os, ht->symbol_nodes[0x101]) < 0 ||
1169 9866 huffman_write_bits(os, value, 8) < 0)
1170 ✗ return LIBMPQ_ERROR_SIZE;
1171
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 9866 times.
 9866 if (huffman_insert_literal(ht, value) < 0)
1172 ✗ return LIBMPQ_ERROR_FORMAT;
1173
1174 /*
1175 * The decoder updates a newly introduced literal once while
1176 * splitting the escape node and once again after emitting it.
1177 */
1178 9866 libmpq__huffman_update_weights(ht, ht->symbol_nodes[value]);
1179
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 885332 times.
 885332 } else if (huffman_encode_symbol(os, item) < 0) {
1180 ✗ return LIBMPQ_ERROR_SIZE;
1181 } else {
1182 885332 libmpq__huffman_update_weights(ht, item);
1183 }
1184 }
1185
1186 /* Mark the logical end of the stream after the final input symbol. */
1187
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 193 times.
 193 if (huffman_encode_symbol(os, ht->symbol_nodes[0x100]) < 0)
1188 ✗ return LIBMPQ_ERROR_SIZE;
1189
2/2
✓ Branch 0 taken 179 times.
✓ Branch 1 taken 14 times.
 193 if (os->bits != 0) {
1190
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 179 times.
 179 if (os->out_pos >= os->capacity)
1191 ✗ return LIBMPQ_ERROR_SIZE;
1192 179 os->out_buf[os->out_pos++] = (uint8_t)os->bit_buf;
1193 }
1194
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 193 times.
 235 while (os->out_pos < 4)
1195 42 os->out_buf[os->out_pos++] = 0;
1196 193 return (int32_t)os->out_pos;
1197 }
1198