1/*
2 Run-Length Encoding utilities.
3 SPDX-FileCopyrightText: 2014-2015 Alex Merry <alex.merry@kde.org>
4
5 SPDX-License-Identifier: LGPL-2.0-or-later
6*/
7
8#ifndef KIMAGEFORMATS_RLE_P_H
9#define KIMAGEFORMATS_RLE_P_H
10
11#include <QDataStream>
12#include <QDebug>
13
14/**
15 * The RLEVariant to use.
16 *
17 * This mostly concerns what to do values >= 128.
18 */
19enum class RLEVariant {
20 /**
21 * PackBits-style RLE
22 *
23 * Value 128 is ignored, 129 indicates a repetition
24 * of size 2, 130 of size 3, up to 255 of size 128.
25 */
26 PackBits,
27 /**
28 * Same as PackBits, but treat unpacked data as
29 * 16-bit integers.
30 */
31 PackBits16,
32 /**
33 * PIC-style RLE
34 *
35 * Value 128 indicates a 16-bit repetition count
36 * follows, while 129 indicates a repetition
37 * of size 128, 130 of size 127, down to 255 of
38 * size 2.
39 */
40 PIC,
41};
42
43/**
44 * Decodes data written in run-length encoding format.
45 *
46 * This is intended to be used with lambda functions.
47 *
48 * Note that this functions expects that, at the current location in @p stream,
49 * exactly @p length items have been encoded as a unit (and so it will not be
50 * partway through a run when it has decoded @p length items). If this is not
51 * the case, it will return @c false.
52 *
53 * @param variant The RLE variant to decode.
54 * @param stream The stream to read the data from.
55 * @param buf The location to write the decoded data.
56 * @param length The number of items to read.
57 * @param readData A function that takes a QDataStream reference and reads a
58 * single value.
59 * @param updateItem A function that takes an item from @p buf and the result
60 * of a readData call, and produces the item that should be
61 * written to @p buf.
62 *
63 * @returns @c true if @p length items in mixed RLE were successfully read
64 * into @p buf, @c false otherwise.
65 */
66template<typename Item, typename Func1, typename Func2>
67static inline bool decodeRLEData(RLEVariant variant, QDataStream &stream, Item *dest, quint32 length, Func1 readData, Func2 updateItem)
68{
69 unsigned offset = 0; // in dest
70 bool is_msb = true; // only used for 16-bit PackBits, data is big-endian
71 quint16 temp_data = 0;
72 while (offset < length) {
73 unsigned remaining = length - offset;
74 quint8 count1;
75 stream >> count1;
76
77 if (count1 >= 128u) {
78 unsigned length = 0;
79 if (variant == RLEVariant::PIC) {
80 if (count1 == 128u) {
81 // If the value is exactly 128, it means that it is more than
82 // 127 repetitions
83 quint16 count2;
84 stream >> count2;
85 length = count2;
86 } else {
87 // 2 to 128 repetitions
88 length = count1 - 127u;
89 }
90 } else if (variant == RLEVariant::PackBits || variant == RLEVariant::PackBits16) {
91 if (count1 == 128u) {
92 // Ignore value 128
93 continue;
94 } else {
95 // 128 to 2 repetitions
96 length = 257u - count1;
97 }
98 } else {
99 Q_ASSERT(false);
100 }
101 if (length > remaining) {
102 qDebug() << "Row overrun:" << length << ">" << remaining;
103 return false;
104 }
105 auto datum = readData(stream);
106 for (unsigned i = offset; i < offset + length; ++i) {
107 if (variant == RLEVariant::PackBits16) {
108 if (is_msb) {
109 temp_data = datum << 8;
110 is_msb = false;
111 } else {
112 temp_data |= datum;
113 dest[i >> 1] = updateItem(dest[i >> 1], temp_data);
114 is_msb = true;
115 }
116 } else {
117 dest[i] = updateItem(dest[i], datum);
118 }
119 }
120 offset += length;
121 } else {
122 // No repetitions
123 unsigned length = count1 + 1u;
124 if (length > remaining) {
125 qDebug() << "Row overrun:" << length << ">" << remaining;
126 return false;
127 }
128 for (unsigned i = offset; i < offset + length; ++i) {
129 auto datum = readData(stream);
130 if (variant == RLEVariant::PackBits16) {
131 if (is_msb) {
132 temp_data = datum << 8;
133 is_msb = false;
134 } else {
135 temp_data |= datum;
136 dest[i >> 1] = updateItem(dest[i >> 1], temp_data);
137 is_msb = true;
138 }
139 } else {
140 dest[i] = updateItem(dest[i], datum);
141 }
142 }
143 offset += length;
144 }
145 }
146 if (stream.status() != QDataStream::Ok) {
147 qDebug() << "DataStream status was" << stream.status();
148 }
149 return stream.status() == QDataStream::Ok;
150}
151
152/**
153 * Encodes data in run-length encoding format.
154 *
155 * This is intended to be used with lambda functions.
156 *
157 * @param variant The RLE variant to encode in.
158 * @param stream The stream to write the data to.
159 * @param data The data to be written.
160 * @param length The number of items to write.
161 * @param itemsEqual A function that takes two items and returns whether
162 * @p writeItem would write them identically.
163 * @param writeItem A function that takes a QDataStream reference and an item
164 * and writes the item to the data stream.
165 */
166template<typename Item, typename Func1, typename Func2>
167static inline void encodeRLEData(RLEVariant variant, QDataStream &stream, const Item *data, unsigned length, Func1 itemsEqual, Func2 writeItem)
168{
169 unsigned offset = 0;
170 const unsigned maxEncodableChunk = (variant == RLEVariant::PIC) ? 65535u : 128;
171 while (offset < length) {
172 const Item *chunkStart = data + offset;
173 unsigned maxChunk = qMin(a: length - offset, b: maxEncodableChunk);
174
175 const Item *chunkEnd = chunkStart + 1;
176 quint16 chunkLength = 1;
177 while (chunkLength < maxChunk && itemsEqual(*chunkStart, *chunkEnd)) {
178 ++chunkEnd;
179 ++chunkLength;
180 }
181
182 if (chunkLength > 128) {
183 // Sequence of > 128 identical pixels
184 Q_ASSERT(variant == RLEVariant::PIC);
185 stream << quint8(128);
186 stream << quint16(chunkLength);
187 writeItem(stream, *chunkStart);
188 } else if (chunkLength > 1) {
189 // Sequence of <= 128 identical pixels
190 quint8 encodedLength;
191 if (variant == RLEVariant::PIC) {
192 encodedLength = quint8(chunkLength + 127);
193 } else if (variant == RLEVariant::PackBits) {
194 encodedLength = quint8(257 - chunkLength);
195 } else {
196 Q_ASSERT(false);
197 encodedLength = 0;
198 }
199 stream << encodedLength;
200 writeItem(stream, *chunkStart);
201 } else {
202 // find a string of up to 128 values, each different from the one
203 // that follows it
204 if (maxChunk > 128) {
205 maxChunk = 128;
206 }
207 chunkLength = 1;
208 chunkEnd = chunkStart + 1;
209 while (chunkLength < maxChunk && (chunkLength + 1u == maxChunk || !itemsEqual(*chunkEnd, *(chunkEnd + 1)))) {
210 ++chunkEnd;
211 ++chunkLength;
212 }
213 stream << quint8(chunkLength - 1);
214 for (unsigned i = 0; i < chunkLength; ++i) {
215 writeItem(stream, *(chunkStart + i));
216 }
217 }
218 offset += chunkLength;
219 }
220}
221
222#endif // KIMAGEFORMATS_RLE_P_H
223

source code of kimageformats/src/imageformats/rle_p.h