GCC Code Coverage Report

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