1//===--- Compression.cpp - Compression implementation ---------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements compression functions.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Support/Compression.h"
14#include "llvm/ADT/ScopeExit.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/StringRef.h"
17#include "llvm/Config/config.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/Error.h"
20#include "llvm/Support/ErrorHandling.h"
21#include <limits>
22#include <optional>
23#if LLVM_ENABLE_ZLIB
24#include <zlib.h>
25#endif
26#if LLVM_ENABLE_ZSTD
27#include <zstd.h>
28#endif
29#if LLVM_ENABLE_LZMA
30#include <lzma.h>
31#endif
32
33using namespace llvm;
34using namespace llvm::compression;
35
36// RFC 1950 section 2.2 zlib wrapper. Two-byte header CMF then FLG:
37// CMF: CM (bits 0-3) must be 8 (deflate). CINFO (bits 4-7) is
38// log2(windowSize)-8 and must be <= 7.
39// FLG: FCHECK (bits 0-4) is chosen so CMF*256+FLG is a multiple of 31;
40// FDICT (bit 5) marks a preset dictionary; FLEVEL (bits 6-7) is a
41// compressor hint. This only identifies the wrapper.
42static bool isZlibHeader(ArrayRef<uint8_t> Input) {
43 if (Input.size() < 2)
44 return false;
45 unsigned CMF = Input[0];
46 unsigned FLG = Input[1];
47 if ((CMF & 0x0f) != 8 || (CMF >> 4) > 7)
48 return false;
49 return (CMF * 256 + FLG) % 31 == 0;
50}
51
52// RFC 8878 section 3.1.1: Zstandard frame magic 0xFD2FB528, little-endian.
53static bool isZstdMagic(ArrayRef<uint8_t> Input) {
54 static constexpr uint8_t Magic[] = {0x28, 0xb5, 0x2f, 0xfd};
55 return Input.take_front(N: 4) == ArrayRef(Magic);
56}
57
58// Check zstd first: 0x28 is a valid zlib CMF (CINFO=2, 1KiB window).
59static std::optional<Format> identifyFormat(ArrayRef<uint8_t> Input) {
60 if (isZstdMagic(Input))
61 return Format::Zstd;
62 if (isZlibHeader(Input))
63 return Format::Zlib;
64 return std::nullopt;
65}
66
67const char *compression::getReasonIfUnsupported(compression::Format F) {
68 switch (F) {
69 case compression::Format::Zlib:
70 if (zlib::isAvailable())
71 return nullptr;
72 return "LLVM was not built with LLVM_ENABLE_ZLIB or did not find zlib at "
73 "build time";
74 case compression::Format::Zstd:
75 if (zstd::isAvailable())
76 return nullptr;
77 return "LLVM was not built with LLVM_ENABLE_ZSTD or did not find zstd at "
78 "build time";
79 }
80 llvm_unreachable("");
81}
82
83const char *compression::getReasonIfUnsupported(ArrayRef<uint8_t> Input) {
84 if (std::optional<Format> F = identifyFormat(Input))
85 return getReasonIfUnsupported(F: *F);
86 return "unknown compression format";
87}
88
89void compression::compress(Params P, ArrayRef<uint8_t> Input,
90 SmallVectorImpl<uint8_t> &Output) {
91 switch (P.format) {
92 case compression::Format::Zlib:
93 zlib::compress(Input, CompressedBuffer&: Output, Level: P.level);
94 break;
95 case compression::Format::Zstd:
96 zstd::compress(Input, CompressedBuffer&: Output, Level: P.level, EnableLdm: P.zstdEnableLdm);
97 break;
98 }
99}
100
101Error compression::decompress(DebugCompressionType T, ArrayRef<uint8_t> Input,
102 uint8_t *Output, size_t UncompressedSize) {
103 switch (formatFor(Type: T)) {
104 case compression::Format::Zlib:
105 return zlib::decompress(Input, Output, UncompressedSize);
106 case compression::Format::Zstd:
107 return zstd::decompress(Input, Output, UncompressedSize);
108 }
109 llvm_unreachable("");
110}
111
112Error compression::decompress(compression::Format F, ArrayRef<uint8_t> Input,
113 SmallVectorImpl<uint8_t> &Output,
114 size_t UncompressedSize) {
115 switch (F) {
116 case compression::Format::Zlib:
117 return zlib::decompress(Input, Output, UncompressedSize);
118 case compression::Format::Zstd:
119 return zstd::decompress(Input, Output, UncompressedSize);
120 }
121 llvm_unreachable("");
122}
123
124Error compression::decompress(DebugCompressionType T, ArrayRef<uint8_t> Input,
125 SmallVectorImpl<uint8_t> &Output,
126 size_t UncompressedSize) {
127 return decompress(F: formatFor(Type: T), Input, Output, UncompressedSize);
128}
129
130Error compression::decompress(ArrayRef<uint8_t> Input,
131 SmallVectorImpl<uint8_t> &Output,
132 size_t UncompressedSize) {
133 std::optional<Format> F = identifyFormat(Input);
134 if (const char *Reason =
135 F ? getReasonIfUnsupported(F: *F) : "unknown compression format")
136 return createStringError(Fmt: Reason);
137 return decompress(F: *F, Input, Output, UncompressedSize);
138}
139
140#if LLVM_ENABLE_ZLIB
141
142static StringRef convertZlibCodeToString(int Code) {
143 switch (Code) {
144 case Z_MEM_ERROR:
145 return "zlib error: Z_MEM_ERROR";
146 case Z_BUF_ERROR:
147 return "zlib error: Z_BUF_ERROR";
148 case Z_STREAM_ERROR:
149 return "zlib error: Z_STREAM_ERROR";
150 case Z_DATA_ERROR:
151 return "zlib error: Z_DATA_ERROR";
152 case Z_OK:
153 default:
154 llvm_unreachable("unknown or unexpected zlib status code");
155 }
156}
157
158bool zlib::isAvailable() { return true; }
159
160void zlib::compress(ArrayRef<uint8_t> Input,
161 SmallVectorImpl<uint8_t> &CompressedBuffer, int Level) {
162 unsigned long CompressedSize = ::compressBound(sourceLen: Input.size());
163 CompressedBuffer.resize_for_overwrite(N: CompressedSize);
164 int Res = ::compress2(dest: (Bytef *)CompressedBuffer.data(), destLen: &CompressedSize,
165 source: (const Bytef *)Input.data(), sourceLen: Input.size(), level: Level);
166 if (Res == Z_MEM_ERROR)
167 report_bad_alloc_error(Reason: "Allocation failed");
168 assert(Res == Z_OK);
169 // Tell MemorySanitizer that zlib output buffer is fully initialized.
170 // This avoids a false report when running LLVM with uninstrumented ZLib.
171 __msan_unpoison(CompressedBuffer.data(), CompressedSize);
172 if (CompressedSize < CompressedBuffer.size())
173 CompressedBuffer.truncate(N: CompressedSize);
174}
175
176Error zlib::decompress(ArrayRef<uint8_t> Input, uint8_t *Output,
177 size_t &UncompressedSize) {
178 int Res = ::uncompress(dest: (Bytef *)Output, destLen: (uLongf *)&UncompressedSize,
179 source: (const Bytef *)Input.data(), sourceLen: Input.size());
180 // Tell MemorySanitizer that zlib output buffer is fully initialized.
181 // This avoids a false report when running LLVM with uninstrumented ZLib.
182 __msan_unpoison(Output, UncompressedSize);
183 return Res ? make_error<StringError>(Args: convertZlibCodeToString(Code: Res),
184 Args: inconvertibleErrorCode())
185 : Error::success();
186}
187
188Error zlib::decompress(ArrayRef<uint8_t> Input,
189 SmallVectorImpl<uint8_t> &Output,
190 size_t UncompressedSize) {
191 Output.resize_for_overwrite(N: UncompressedSize);
192 Error E = zlib::decompress(Input, Output: Output.data(), UncompressedSize);
193 if (UncompressedSize < Output.size())
194 Output.truncate(N: UncompressedSize);
195 return E;
196}
197
198#else
199bool zlib::isAvailable() { return false; }
200void zlib::compress(ArrayRef<uint8_t> Input,
201 SmallVectorImpl<uint8_t> &CompressedBuffer, int Level) {
202 llvm_unreachable("zlib::compress is unavailable");
203}
204Error zlib::decompress(ArrayRef<uint8_t> Input, uint8_t *UncompressedBuffer,
205 size_t &UncompressedSize) {
206 llvm_unreachable("zlib::decompress is unavailable");
207}
208Error zlib::decompress(ArrayRef<uint8_t> Input,
209 SmallVectorImpl<uint8_t> &UncompressedBuffer,
210 size_t UncompressedSize) {
211 llvm_unreachable("zlib::decompress is unavailable");
212}
213#endif
214
215#if LLVM_ENABLE_ZSTD
216
217bool zstd::isAvailable() { return true; }
218
219#include <zstd.h> // Ensure ZSTD library is included
220
221void zstd::compress(ArrayRef<uint8_t> Input,
222 SmallVectorImpl<uint8_t> &CompressedBuffer, int Level,
223 bool EnableLdm) {
224 ZSTD_CCtx *Cctx = ZSTD_createCCtx();
225 if (!Cctx)
226 report_bad_alloc_error(Reason: "Failed to create ZSTD_CCtx");
227
228 if (ZSTD_isError(result: ZSTD_CCtx_setParameter(
229 cctx: Cctx, param: ZSTD_c_enableLongDistanceMatching, value: EnableLdm ? 1 : 0))) {
230 ZSTD_freeCCtx(cctx: Cctx);
231 report_bad_alloc_error(Reason: "Failed to set ZSTD_c_enableLongDistanceMatching");
232 }
233
234 if (ZSTD_isError(
235 result: ZSTD_CCtx_setParameter(cctx: Cctx, param: ZSTD_c_compressionLevel, value: Level))) {
236 ZSTD_freeCCtx(cctx: Cctx);
237 report_bad_alloc_error(Reason: "Failed to set ZSTD_c_compressionLevel");
238 }
239
240 unsigned long CompressedBufferSize = ZSTD_compressBound(srcSize: Input.size());
241 CompressedBuffer.resize_for_overwrite(N: CompressedBufferSize);
242
243 size_t const CompressedSize =
244 ZSTD_compress2(cctx: Cctx, dst: CompressedBuffer.data(), dstCapacity: CompressedBufferSize,
245 src: Input.data(), srcSize: Input.size());
246
247 ZSTD_freeCCtx(cctx: Cctx);
248
249 if (ZSTD_isError(result: CompressedSize))
250 report_bad_alloc_error(Reason: "Compression failed");
251
252 __msan_unpoison(CompressedBuffer.data(), CompressedSize);
253 if (CompressedSize < CompressedBuffer.size())
254 CompressedBuffer.truncate(N: CompressedSize);
255}
256
257Error zstd::decompress(ArrayRef<uint8_t> Input, uint8_t *Output,
258 size_t &UncompressedSize) {
259 const size_t Res = ::ZSTD_decompress(
260 dst: Output, dstCapacity: UncompressedSize, src: (const uint8_t *)Input.data(), compressedSize: Input.size());
261 UncompressedSize = Res;
262 if (ZSTD_isError(result: Res))
263 return make_error<StringError>(Args: ZSTD_getErrorName(result: Res),
264 Args: inconvertibleErrorCode());
265 // Tell MemorySanitizer that zstd output buffer is fully initialized.
266 // This avoids a false report when running LLVM with uninstrumented ZLib.
267 __msan_unpoison(Output, UncompressedSize);
268 return Error::success();
269}
270
271Error zstd::decompress(ArrayRef<uint8_t> Input,
272 SmallVectorImpl<uint8_t> &Output,
273 size_t UncompressedSize) {
274 Output.resize_for_overwrite(N: UncompressedSize);
275 Error E = zstd::decompress(Input, Output: Output.data(), UncompressedSize);
276 if (UncompressedSize < Output.size())
277 Output.truncate(N: UncompressedSize);
278 return E;
279}
280
281#else
282bool zstd::isAvailable() { return false; }
283void zstd::compress(ArrayRef<uint8_t> Input,
284 SmallVectorImpl<uint8_t> &CompressedBuffer, int Level,
285 bool EnableLdm) {
286 llvm_unreachable("zstd::compress is unavailable");
287}
288Error zstd::decompress(ArrayRef<uint8_t> Input, uint8_t *Output,
289 size_t &UncompressedSize) {
290 llvm_unreachable("zstd::decompress is unavailable");
291}
292Error zstd::decompress(ArrayRef<uint8_t> Input,
293 SmallVectorImpl<uint8_t> &Output,
294 size_t UncompressedSize) {
295 llvm_unreachable("zstd::decompress is unavailable");
296}
297#endif
298
299#if LLVM_ENABLE_LZMA
300
301bool xz::isAvailable() { return true; }
302
303// Returns a C string rather than a StringRef because every caller feeds the
304// result to a printf-style "%s", which requires NUL termination.
305static const char *convertLZMACodeToString(lzma_ret Code) {
306 switch (Code) {
307 case LZMA_STREAM_END:
308 return "lzma error: LZMA_STREAM_END";
309 case LZMA_NO_CHECK:
310 return "lzma error: LZMA_NO_CHECK";
311 case LZMA_UNSUPPORTED_CHECK:
312 return "lzma error: LZMA_UNSUPPORTED_CHECK";
313 case LZMA_GET_CHECK:
314 return "lzma error: LZMA_GET_CHECK";
315 case LZMA_MEM_ERROR:
316 return "lzma error: LZMA_MEM_ERROR";
317 case LZMA_MEMLIMIT_ERROR:
318 return "lzma error: LZMA_MEMLIMIT_ERROR";
319 case LZMA_FORMAT_ERROR:
320 return "lzma error: LZMA_FORMAT_ERROR";
321 case LZMA_OPTIONS_ERROR:
322 return "lzma error: LZMA_OPTIONS_ERROR";
323 case LZMA_DATA_ERROR:
324 return "lzma error: LZMA_DATA_ERROR";
325 case LZMA_BUF_ERROR:
326 return "lzma error: LZMA_BUF_ERROR";
327 case LZMA_PROG_ERROR:
328 return "lzma error: LZMA_PROG_ERROR";
329 default:
330 llvm_unreachable("unknown or unexpected lzma status code");
331 }
332}
333
334/// Read the uncompressed size recorded in the xz stream's index.
335static Expected<uint64_t> getUncompressedSize(ArrayRef<uint8_t> Input) {
336 if (Input.size() < LZMA_STREAM_HEADER_SIZE)
337 return createStringError(
338 Fmt: "size of xz-compressed blob (%zu bytes) is smaller than the "
339 "LZMA_STREAM_HEADER_SIZE (%zu bytes)",
340 Vals: Input.size(), Vals: size_t(LZMA_STREAM_HEADER_SIZE));
341
342 // Decode the xz footer.
343 lzma_stream_flags FooterFlags{};
344 lzma_ret Ret = lzma_stream_footer_decode(
345 options: &FooterFlags, in: Input.take_back(LZMA_STREAM_HEADER_SIZE).data());
346 if (Ret != LZMA_OK)
347 return createStringError(Fmt: "lzma_stream_footer_decode()=%s",
348 Vals: convertLZMACodeToString(Code: Ret));
349
350 // A stream is the header, block data, index and stream footer
351 uint64_t MinSize = FooterFlags.backward_size + 2 * LZMA_STREAM_HEADER_SIZE;
352 if (Input.size() < MinSize)
353 return createStringError(
354 Fmt: "xz-compressed buffer size (%zu bytes) too small (required at "
355 "least %" PRIu64 " bytes)",
356 Vals: Input.size(), Vals: MinSize);
357
358 // Decode xz index.
359 // liblzma stores null on failure, and lzma_index_end() ignores null.
360 lzma_index *Index = nullptr;
361 llvm::scope_exit FreeIndex([&] { lzma_index_end(i: Index, allocator: nullptr); });
362 uint64_t MemLimit = UINT64_MAX;
363 size_t InPos = 0;
364 Ret = lzma_index_buffer_decode(
365 i: &Index, memlimit: &MemLimit, allocator: nullptr,
366 in: Input.take_back(LZMA_STREAM_HEADER_SIZE + FooterFlags.backward_size)
367 .data(),
368 in_pos: &InPos, in_size: Input.size());
369 if (Ret != LZMA_OK)
370 return createStringError(Fmt: "lzma_index_buffer_decode()=%s",
371 Vals: convertLZMACodeToString(Code: Ret));
372
373 return lzma_index_uncompressed_size(i: Index);
374}
375
376Error xz::decompress(ArrayRef<uint8_t> Input,
377 SmallVectorImpl<uint8_t> &Output) {
378 // Hand back nothing unless the whole stream decodes.
379 Output.clear();
380
381 Expected<uint64_t> UncompressedSize = getUncompressedSize(Input);
382 if (!UncompressedSize)
383 return UncompressedSize.takeError();
384
385 if (*UncompressedSize > std::numeric_limits<size_t>::max())
386 return createStringError(Fmt: "xz uncompressed size (%" PRIu64
387 " bytes) exceeds addressable memory",
388 Vals: *UncompressedSize);
389
390 // Concatenated streams are unsupported: liblzma decodes only the first and
391 // still reports LZMA_OK, leaving the rest of Output zero-filled.
392 Output.resize(N: static_cast<size_t>(*UncompressedSize));
393 uint64_t MemLimit = UINT64_MAX;
394 size_t InPos = 0;
395 size_t OutPos = 0;
396 lzma_ret Ret = lzma_stream_buffer_decode(
397 memlimit: &MemLimit, /*flags=*/0, allocator: nullptr, in: Input.data(), in_pos: &InPos, in_size: Input.size(),
398 out: Output.data(), out_pos: &OutPos, out_size: Output.size());
399 if (Ret != LZMA_OK) {
400 Output.clear();
401 return createStringError(Fmt: "lzma_stream_buffer_decode()=%s",
402 Vals: convertLZMACodeToString(Code: Ret));
403 }
404
405 return Error::success();
406}
407
408#else
409
410bool xz::isAvailable() { return false; }
411Error xz::decompress(ArrayRef<uint8_t> Input,
412 SmallVectorImpl<uint8_t> &Output) {
413 llvm_unreachable("xz::decompress is unavailable");
414}
415
416#endif
417