/src/kdegraphics-mobipocket/lib/decompressor.cpp

Source
// SPDX-FileCopyrightText: 2008 by Jakub Stachowski <qbast@go2.pl>
// RLE decompressor based on FBReader
// SPDX-FileCopyrightText: 2004-2008 Geometer Plus <contact@geometerplus.com>
// Huffdic decompressor based on Python code by Igor Skochinsky
// SPDX-License-Identifier: GPL-2.0-or-later

#include "decompressor.h"

#include "bitreader_p.h"

#include <QVector>
#include <QtEndian>

#include <vector>

// clang-format off
static const unsigned char TOKEN_CODE[256] = {
  0, 1, 1, 1,   1, 1, 1, 1,   1, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,   0, 0, 0, 0,
  3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,
  3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,
  3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,
  3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,   3, 3, 3, 3,
  2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,
  2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,
  2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,
  2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,   2, 2, 2, 2,
};
// clang-format on

namespace Mobipocket
{

class NOOPDecompressor : public Decompressor
{
public:
    NOOPDecompressor()
    {
        valid = true;
    }
    QByteArray decompress(const QByteArray &data) override
    {
        return data;
    }
};

class RLEDecompressor : public Decompressor
{
public:
    RLEDecompressor()
    {
        valid = true;
    }
    QByteArray decompress(const QByteArray &data) override;
};

class HuffdicDecompressor : public Decompressor
{
public:
    HuffdicDecompressor() = delete;
    HuffdicDecompressor(const HuffdicDecompressor &) = delete;
    HuffdicDecompressor(const QVector<QByteArray> &huffData);
    QByteArray decompress(const QByteArray &data) override;

private:
    bool unpack(std::vector<char> &buf, BitReader reader, int depth) const;
    const QVector<QByteArray> dicts;
    quint32 entry_bits;
    quint32 dict1[256];
    quint32 dict2[64];
};

QByteArray RLEDecompressor::decompress(const QByteArray &data)
{
    QByteArray ret;
    ret.reserve(8192);

    int i = 0;
    int maxIndex = data.size() - 1;

    while (i < data.size()) {
        unsigned char token = data.at(i++);
        switch (TOKEN_CODE[token]) {
        case 0:
            ret.append(token);
            break;
        case 1:
            if ((i + token > maxIndex + 1)) {
                return ret;
            }
            ret.append(data.mid(i, token));
            i += token;
            break;
        case 2:
            ret.append(' ');
            ret.append(token ^ 0x80);
            break;
        case 3:
            {
                if (i > maxIndex) {
                    return ret;
                }
                quint16 N = token << 8;
                N += (unsigned char)data.at(i++);
                quint16 copyLength = (N & 7) + 3;
                quint16 shift = (N & 0x3fff) / 8;
                if ((shift < 1) || (shift > ret.size())) {
                    return ret;
                }
                auto shifted = ret.size() - shift;
                for (auto j = shifted; j < shifted + copyLength; j++) {
                    ret.append(ret.at(j));
                }
            }
            break;
        }
    }
    return ret;
}

HuffdicDecompressor::HuffdicDecompressor(const QVector<QByteArray> &huffData)
    : dicts(huffData.mid(1))
{
    if (dicts.empty())
        return;

    if ((dicts[0].size() < 18) || !dicts[0].startsWith("CDIC"))
        return;

    const QByteArray &huff1 = huffData[0];
    if ((huff1.size() < 24) || !huff1.startsWith("HUFF"))
        return;

    quint32 off1 = qFromBigEndian<quint32>(huff1.constData() + 16);
    quint32 off2 = qFromBigEndian<quint32>(huff1.constData() + 20);
    if (((off1 + 256 * 4) > huff1.size()) || ((off2 + 64 * 4) > huff1.size()))
        return;

    memcpy(dict1, huff1.data() + off1, 256 * 4);
    memcpy(dict2, huff1.data() + off2, 64 * 4);

    entry_bits = qFromBigEndian<quint32>(dicts[0].constData() + 12);
    if (entry_bits > 32)
        return;

    valid = true;
}

QByteArray HuffdicDecompressor::decompress(const QByteArray &data)
{
    std::vector<char> buf;
    buf.reserve(4096);
    if (!unpack(buf, BitReader(data), 0)) {
        valid = false;
    }
    return QByteArray(buf.data(), buf.size());
}

bool HuffdicDecompressor::unpack(std::vector<char> &buf, BitReader reader, int depth) const
{
    // These two checks are fairly arbitrary, due to lack of an actual specification
    // Both exceed typical real world files by far, but are useful to protect against
    // 'ZIP bomb' style attacks
    if (depth > 32) {
        return false;
    } else if (buf.size() > 16 * 1024 * 1024) {
        return false;
    }

    auto dict_count = dicts.size();
    quint32 entry_mask = (quint64(1) << entry_bits) - 1;

    while (reader.left()) {
        quint32 dw = reader.read();
        quint32 v = dict1[dw >> 24];
        quint8 codelen = v & 0x1F;
        if (!codelen)
            return false;
        quint32 code = dw >> (32 - codelen);
        quint32 r = (v >> 8);
        if (!(v & 0x80)) {
            while (code < dict2[(codelen - 1) * 2]) {
                codelen++;
                code = dw >> (32 - codelen);
            }
            r = dict2[(codelen - 1) * 2 + 1];
        }
        r -= code;
        if (!reader.eat(codelen))
            return true;
        quint32 dict_no = quint64(r) >> entry_bits;
        if (dict_no >= dict_count) {
            return false;
        }
        QByteArrayView dict = dicts.at(dict_no);
        auto dict_size = dict.size();

        quint32 off1 = 16 + (r & entry_mask) * 2;
        if (off1 > (dict_size - 2)) {
            return false;
        }

        quint16 off2 = 16 + qFromBigEndian<quint16>(dict.constData() + off1);
        if (off2 > (dict_size - 2)) {
            return false;
        }

        quint16 blen = qFromBigEndian<quint16>(dict.constData() + off2);
        if ((blen & 0x7fff) > (dict_size - 2 - off2)) {
            return false;
        }

        auto slice = dict.mid(off2 + 2, (blen & 0x7fff));
        if (blen & 0x8000) {
            buf.insert(buf.end(), slice.begin(), slice.end());
        } else {
            if (!unpack(buf, BitReader(slice), depth + 1)) {
                return false;
            }
        }
    }
    return true;
}

std::unique_ptr<Decompressor> Decompressor::create(quint8 type, const QVector<QByteArray> &auxData)
{
    switch (type) {
    case 1:
        return std::make_unique<NOOPDecompressor>();
    case 2:
        return std::make_unique<RLEDecompressor>();
    case 'H':
        return std::make_unique<HuffdicDecompressor>(auxData);
    default:
        return nullptr;
    }
}
}

Coverage Report

Created: 2026-07-30 07:17

Line	Count	Source
1		// SPDX-FileCopyrightText: 2008 by Jakub Stachowski <qbast@go2.pl>
2		// RLE decompressor based on FBReader
3		// SPDX-FileCopyrightText: 2004-2008 Geometer Plus <contact@geometerplus.com>
4		// Huffdic decompressor based on Python code by Igor Skochinsky
5		// SPDX-License-Identifier: GPL-2.0-or-later
6
7		#include "decompressor.h"
8
9		#include "bitreader_p.h"
10
11		#include <QVector>
12		#include <QtEndian>
13
14		#include <vector>
15
16		// clang-format off
17		static const unsigned char TOKEN_CODE[256] = {
18		0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
19		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
20		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
21		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
23		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
24		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
25		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
26		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
27		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
28		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
29		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
30		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
31		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
32		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
33		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
34		};
35		// clang-format on
36
37		namespace Mobipocket
38		{
39
40		class NOOPDecompressor : public Decompressor
41		{
42		public:
43		NOOPDecompressor()
44	57	{
45	57	valid = true;
46	57	}
47		QByteArray decompress(const QByteArray &data) override
48	47	{
49	47	return data;
50	47	}
51		};
52
53		class RLEDecompressor : public Decompressor
54		{
55		public:
56		RLEDecompressor()
57	1.00k	{
58	1.00k	valid = true;
59	1.00k	}
60		QByteArray decompress(const QByteArray &data) override;
61		};
62
63		class HuffdicDecompressor : public Decompressor
64		{
65		public:
66		HuffdicDecompressor() = delete;
67		HuffdicDecompressor(const HuffdicDecompressor &) = delete;
68		HuffdicDecompressor(const QVector<QByteArray> &huffData);
69		QByteArray decompress(const QByteArray &data) override;
70
71		private:
72		bool unpack(std::vector<char> &buf, BitReader reader, int depth) const;
73		const QVector<QByteArray> dicts;
74		quint32 entry_bits;
75		quint32 dict1[256];
76		quint32 dict2[64];
77		};
78
79		QByteArray RLEDecompressor::decompress(const QByteArray &data)
80	438	{
81	438	QByteArray ret;
82	438	ret.reserve(8192);
83
84	438	int i = 0;
85	438	int maxIndex = data.size() - 1;
86
87	706k	while (i < data.size()) {
88	706k	unsigned char token = data.at(i++);
89	706k	switch (TOKEN_CODE[token]) {
90	607k	case 0:
91	607k	ret.append(token);
92	607k	break;
93	3.32k	case 1:
94	3.32k	if ((i + token > maxIndex + 1)) {
95	11	return ret;
96	11	}
97	3.31k	ret.append(data.mid(i, token));
98	3.31k	i += token;
99	3.31k	break;
100	77.1k	case 2:
101	77.1k	ret.append(' ');
102	77.1k	ret.append(token ^ 0x80);
103	77.1k	break;
104	18.0k	case 3:
105	18.0k	{
106	18.0k	if (i > maxIndex) {
107	7	return ret;
108	7	}
109	18.0k	quint16 N = token << 8;
110	18.0k	N += (unsigned char)data.at(i++);
111	18.0k	quint16 copyLength = (N & 7) + 3;
112	18.0k	quint16 shift = (N & 0x3fff) / 8;
113	18.0k	if ((shift < 1) \|\| (shift > ret.size())) {
114	91	return ret;
115	91	}
116	17.9k	auto shifted = ret.size() - shift;
117	148k	for (auto j = shifted; j < shifted + copyLength; j++) {
118	130k	ret.append(ret.at(j));
119	130k	}
120	17.9k	}
121	0	break;
122	706k	}
123	706k	}
124	329	return ret;
125	438	}
126
127		HuffdicDecompressor::HuffdicDecompressor(const QVector<QByteArray> &huffData)
128	97	: dicts(huffData.mid(1))
129	97	{
130	97	if (dicts.empty())
131	78	return;
132
133	19	if ((dicts[0].size() < 18) \|\| !dicts[0].startsWith("CDIC"))
134	19	return;
135
136	0	const QByteArray &huff1 = huffData[0];
137	0	if ((huff1.size() < 24) \|\| !huff1.startsWith("HUFF"))
138	0	return;
139
140	0	quint32 off1 = qFromBigEndian<quint32>(huff1.constData() + 16);
141	0	quint32 off2 = qFromBigEndian<quint32>(huff1.constData() + 20);
142	0	if (((off1 + 256 * 4) > huff1.size()) \|\| ((off2 + 64 * 4) > huff1.size()))
143	0	return;
144
145	0	memcpy(dict1, huff1.data() + off1, 256 * 4);
146	0	memcpy(dict2, huff1.data() + off2, 64 * 4);
147
148	0	entry_bits = qFromBigEndian<quint32>(dicts[0].constData() + 12);
149	0	if (entry_bits > 32)
150	0	return;
151
152	0	valid = true;
153	0	}
154
155		QByteArray HuffdicDecompressor::decompress(const QByteArray &data)
156	89	{
157	89	std::vector<char> buf;
158	89	buf.reserve(4096);
159	89	if (!unpack(buf, BitReader(data), 0)) {
160	39	valid = false;
161	39	}
162	89	return QByteArray(buf.data(), buf.size());
163	89	}
164
165		bool HuffdicDecompressor::unpack(std::vector<char> &buf, BitReader reader, int depth) const
166	391	{
167		// These two checks are fairly arbitrary, due to lack of an actual specification
168		// Both exceed typical real world files by far, but are useful to protect against
169		// 'ZIP bomb' style attacks
170	391	if (depth > 32) {
171	0	return false;
172	391	} else if (buf.size() > 16 * 1024 * 1024) {
173	0	return false;
174	0	}
175
176	391	auto dict_count = dicts.size();
177	391	quint32 entry_mask = (quint64(1) << entry_bits) - 1;
178
179	693	while (reader.left()) {
180	341	quint32 dw = reader.read();
181	341	quint32 v = dict1[dw >> 24];
182	341	quint8 codelen = v & 0x1F;
183	341	if (!codelen)
184	18	return false;
185	323	quint32 code = dw >> (32 - codelen);
186	323	quint32 r = (v >> 8);
187	323	if (!(v & 0x80)) {
188	895	while (code < dict2[(codelen - 1) * 2]) {
189	572	codelen++;
190	572	code = dw >> (32 - codelen);
191	572	}
192	323	r = dict2[(codelen - 1) * 2 + 1];
193	323	}
194	323	r -= code;
195	323	if (!reader.eat(codelen))
196	0	return true;
197	323	quint32 dict_no = quint64(r) >> entry_bits;
198	323	if (dict_no >= dict_count) {
199	17	return false;
200	17	}
201	306	QByteArrayView dict = dicts.at(dict_no);
202	306	auto dict_size = dict.size();
203
204	306	quint32 off1 = 16 + (r & entry_mask) * 2;
205	306	if (off1 > (dict_size - 2)) {
206	4	return false;
207	4	}
208
209	302	quint16 off2 = 16 + qFromBigEndian<quint16>(dict.constData() + off1);
210	302	if (off2 > (dict_size - 2)) {
211	0	return false;
212	0	}
213
214	302	quint16 blen = qFromBigEndian<quint16>(dict.constData() + off2);
215	302	if ((blen & 0x7fff) > (dict_size - 2 - off2)) {
216	0	return false;
217	0	}
218
219	302	auto slice = dict.mid(off2 + 2, (blen & 0x7fff));
220	302	if (blen & 0x8000) {
221	0	buf.insert(buf.end(), slice.begin(), slice.end());
222	302	} else {
223	302	if (!unpack(buf, BitReader(slice), depth + 1)) {
224	0	return false;
225	0	}
226	302	}
227	302	}
228	352	return true;
229	391	}
230
231		std::unique_ptr<Decompressor> Decompressor::create(quint8 type, const QVector<QByteArray> &auxData)
232	1.18k	{
233	1.18k	switch (type) {
234	57	case 1:
235	57	return std::make_unique<NOOPDecompressor>();
236	1.00k	case 2:
237	1.00k	return std::make_unique<RLEDecompressor>();
238	97	case 'H':
239	97	return std::make_unique<HuffdicDecompressor>(auxData);
240	24	default:
241	24	return nullptr;
242	1.18k	}
243	1.18k	}
244		}