1 //===- lib/Support/Compressor.cpp -------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Reid Spencer and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the llvm::Compressor class, an abstraction for memory
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Config/config.h"
16 #include "llvm/Support/Compressor.h"
17 #include "llvm/ADT/StringExtras.h"
20 #include "bzip2/bzlib.h"
24 enum CompressionTypes {
26 COMP_TYPE_BZIP2 = '2',
29 inline int getdata(char*& buffer, unsigned& size,
30 llvm::Compressor::OutputDataCallback* cb, void* context) {
33 int result = (*cb)(buffer, size, context);
34 assert(buffer != 0 && "Invalid result from Compressor callback");
35 assert(size != 0 && "Invalid result from Compressor callback");
39 //===----------------------------------------------------------------------===//
40 //=== NULLCOMP - a compression like set of routines that just copies data
41 //=== without doing any compression. This is provided so that if the
42 //=== configured environment doesn't have a compression library the
43 //=== program can still work, albeit using more data/memory.
44 //===----------------------------------------------------------------------===//
46 struct NULLCOMP_stream {
47 // User provided fields
54 uint64_t output_count; // Total count of output bytes
57 void NULLCOMP_init(NULLCOMP_stream* s) {
61 bool NULLCOMP_compress(NULLCOMP_stream* s) {
62 assert(s && "Invalid NULLCOMP_stream");
63 assert(s->next_in != 0);
64 assert(s->next_out != 0);
65 assert(s->avail_in >= 1);
66 assert(s->avail_out >= 1);
68 if (s->avail_out >= s->avail_in) {
69 ::memcpy(s->next_out, s->next_in, s->avail_in);
70 s->output_count += s->avail_in;
71 s->avail_out -= s->avail_in;
72 s->next_in += s->avail_in;
76 ::memcpy(s->next_out, s->next_in, s->avail_out);
77 s->output_count += s->avail_out;
78 s->avail_in -= s->avail_out;
79 s->next_in += s->avail_out;
85 bool NULLCOMP_decompress(NULLCOMP_stream* s) {
86 assert(s && "Invalid NULLCOMP_stream");
87 assert(s->next_in != 0);
88 assert(s->next_out != 0);
89 assert(s->avail_in >= 1);
90 assert(s->avail_out >= 1);
92 if (s->avail_out >= s->avail_in) {
93 ::memcpy(s->next_out, s->next_in, s->avail_in);
94 s->output_count += s->avail_in;
95 s->avail_out -= s->avail_in;
96 s->next_in += s->avail_in;
100 ::memcpy(s->next_out, s->next_in, s->avail_out);
101 s->output_count += s->avail_out;
102 s->avail_in -= s->avail_out;
103 s->next_in += s->avail_out;
109 void NULLCOMP_end(NULLCOMP_stream* strm) {
112 /// This structure is only used when a bytecode file is compressed.
113 /// As bytecode is being decompressed, the memory buffer might need
114 /// to be reallocated. The buffer allocation is handled in a callback
115 /// and this structure is needed to retain information across calls
117 /// @brief An internal buffer object used for handling decompression
118 struct BufferContext {
121 BufferContext(unsigned compressedSize ) {
122 // Null to indicate malloc of a new block
125 // Compute the initial length of the uncompression buffer. Note that this
126 // is twice the length of the compressed buffer and will be doubled again
127 // in the callback for an initial allocation of 4x compressedSize. This
128 // calculation is based on the typical compression ratio of bzip2 on LLVM
129 // bytecode files which typically ranges in the 50%-75% range. Since we
130 // tyipcally get at least 50%, doubling is insufficient. By using a 4x
131 // multiplier on the first allocation, we minimize the impact of having to
132 // copy the buffer on reallocation.
133 size = compressedSize*2;
136 /// This function handles allocation of the buffer used for decompression of
137 /// compressed bytecode files. It is called by Compressor::decompress which is
138 /// called by BytecodeReader::ParseBytecode.
139 static unsigned callback(char*&buff, unsigned& sz, void* ctxt){
140 // Case the context variable to our BufferContext
141 BufferContext* bc = reinterpret_cast<BufferContext*>(ctxt);
143 // Compute the new, doubled, size of the block
144 unsigned new_size = bc->size * 2;
146 // Extend or allocate the block (realloc(0,n) == malloc(n))
147 char* new_buff = (char*) ::realloc(bc->buff, new_size);
149 // Figure out what to return to the Compressor. If this is the first call,
150 // then bc->buff will be null. In this case we want to return the entire
151 // buffer because there was no previous allocation. Otherwise, when the
152 // buffer is reallocated, we save the new base pointer in the
153 // BufferContext.buff field but return the address of only the extension,
154 // mid-way through the buffer (since its size was doubled). Furthermore,
155 // the sz result must be 1/2 the total size of the buffer.
156 if (bc->buff == 0 ) {
157 buff = bc->buff = new_buff;
161 buff = new_buff + bc->size;
165 // Retain the size of the allocated block
168 // Make sure we fail (return 1) if we didn't get any memory.
169 return (bc->buff == 0 ? 1 : 0);
173 // This structure retains the context when compressing the bytecode file. The
174 // WriteCompressedData function below uses it to keep track of the previously
175 // filled chunk of memory (which it writes) and how many bytes have been
177 struct WriterContext {
178 // Initialize the context
179 WriterContext(std::ostream*OS, unsigned CS)
180 : chunk(0), sz(0), written(0), compSize(CS), Out(OS) {}
182 // Make sure we clean up memory
189 void write(unsigned size = 0) {
190 unsigned write_size = (size == 0 ? sz : size);
191 Out->write(chunk,write_size);
192 written += write_size;
198 // This function is a callback used by the Compressor::compress function to
199 // allocate memory for the compression buffer. This function fulfills that
200 // responsibility but also writes the previous (now filled) buffer out to the
202 static unsigned callback(char*& buffer, unsigned& size, void* context) {
203 // Cast the context to the structure it must point to.
204 WriterContext* ctxt =
205 reinterpret_cast<WriterContext*>(context);
207 // If there's a previously allocated chunk, it must now be filled with
208 // compressed data, so we write it out and deallocate it.
209 if (ctxt->chunk != 0 && ctxt->sz > 0 ) {
213 // Compute the size of the next chunk to allocate. We attempt to allocate
214 // enough memory to handle the compression in a single memory allocation. In
215 // general, the worst we do on compression of bytecode is about 50% so we
216 // conservatively estimate compSize / 2 as the size needed for the
217 // compression buffer. compSize is the size of the compressed data, provided
218 // by WriteBytecodeToFile.
219 size = ctxt->sz = ctxt->compSize / 2;
221 // Allocate the chunks
222 buffer = ctxt->chunk = new char [size];
224 // We must return 1 if the allocation failed so that the Compressor knows
225 // not to use the buffer pointer.
226 return (ctxt->chunk == 0 ? 1 : 0);
229 char* chunk; // pointer to the chunk of memory filled by compression
230 unsigned sz; // size of chunk
231 unsigned written; // aggregate total of bytes written in all chunks
232 unsigned compSize; // size of the uncompressed buffer
233 std::ostream* Out; // The stream we write the data to.
240 // Compress in one of three ways
241 uint64_t Compressor::compress(const char* in, unsigned size,
242 OutputDataCallback* cb, void* context ) {
243 assert(in && "Can't compress null buffer");
244 assert(size && "Can't compress empty buffer");
245 assert(cb && "Can't compress without a callback function");
249 // For small files, we just don't bother compressing. bzip2 isn't very good
250 // with tiny files and can actually make the file larger, so we just avoid
252 if (size > 64*1024) {
253 // Set up the bz_stream
258 bzdata.next_in = (char*)in;
259 bzdata.avail_in = size;
261 bzdata.avail_out = 0;
262 switch ( BZ2_bzCompressInit(&bzdata, 5, 0, 100) ) {
263 case BZ_CONFIG_ERROR: throw std::string("bzip2 library mis-compiled");
264 case BZ_PARAM_ERROR: throw std::string("Compressor internal error");
265 case BZ_MEM_ERROR: throw std::string("Out of memory");
271 // Get a block of memory
272 if (0 != getdata(bzdata.next_out, bzdata.avail_out,cb,context)) {
273 BZ2_bzCompressEnd(&bzdata);
274 throw std::string("Can't allocate output buffer");
277 // Put compression code in first byte
278 (*bzdata.next_out++) = COMP_TYPE_BZIP2;
282 int bzerr = BZ_FINISH_OK;
283 while (BZ_FINISH_OK == (bzerr = BZ2_bzCompress(&bzdata, BZ_FINISH))) {
284 if (0 != getdata(bzdata.next_out, bzdata.avail_out,cb,context)) {
285 BZ2_bzCompressEnd(&bzdata);
286 throw std::string("Can't allocate output buffer");
290 case BZ_SEQUENCE_ERROR:
291 case BZ_PARAM_ERROR: throw std::string("Param/Sequence error");
293 case BZ_STREAM_END: break;
294 default: throw std::string("Oops: ") + utostr(unsigned(bzerr));
298 result = (static_cast<uint64_t>(bzdata.total_out_hi32) << 32) |
299 bzdata.total_out_lo32 + 1;
301 BZ2_bzCompressEnd(&bzdata);
303 // Do null compression, for small files
304 NULLCOMP_stream sdata;
305 sdata.next_in = (char*)in;
306 sdata.avail_in = size;
307 NULLCOMP_init(&sdata);
309 if (0 != getdata(sdata.next_out, sdata.avail_out,cb,context)) {
310 throw std::string("Can't allocate output buffer");
313 *(sdata.next_out++) = COMP_TYPE_NONE;
316 while (!NULLCOMP_compress(&sdata)) {
317 if (0 != getdata(sdata.next_out, sdata.avail_out,cb,context)) {
318 throw std::string("Can't allocate output buffer");
322 result = sdata.output_count + 1;
323 NULLCOMP_end(&sdata);
329 Compressor::compressToNewBuffer(const char* in, unsigned size, char*&out) {
330 BufferContext bc(size);
331 uint64_t result = compress(in,size,BufferContext::callback,(void*)&bc);
337 Compressor::compressToStream(const char*in, unsigned size, std::ostream& out) {
338 // Set up the context and writer
339 WriterContext ctxt(&out,size / 2);
341 // Compress everything after the magic number (which we'll alter)
342 uint64_t zipSize = Compressor::compress(in,size,
343 WriterContext::callback, (void*)&ctxt);
346 ctxt.write(zipSize - ctxt.written);
351 // Decompress in one of three ways
352 uint64_t Compressor::decompress(const char *in, unsigned size,
353 OutputDataCallback* cb, void* context) {
354 assert(in && "Can't decompress null buffer");
355 assert(size > 1 && "Can't decompress empty buffer");
356 assert(cb && "Can't decompress without a callback function");
361 case COMP_TYPE_BZIP2: {
362 // Set up the bz_stream
367 bzdata.next_in = (char*)in;
368 bzdata.avail_in = size - 1;
370 bzdata.avail_out = 0;
371 switch ( BZ2_bzDecompressInit(&bzdata, 0, 0) ) {
372 case BZ_CONFIG_ERROR: throw std::string("bzip2 library mis-compiled");
373 case BZ_PARAM_ERROR: throw std::string("Compressor internal error");
374 case BZ_MEM_ERROR: throw std::string("Out of memory");
380 // Get a block of memory
381 if (0 != getdata(bzdata.next_out, bzdata.avail_out,cb,context)) {
382 BZ2_bzDecompressEnd(&bzdata);
383 throw std::string("Can't allocate output buffer");
388 while (BZ_OK == (bzerr = BZ2_bzDecompress(&bzdata))) {
389 if (0 != getdata(bzdata.next_out, bzdata.avail_out,cb,context)) {
390 BZ2_bzDecompressEnd(&bzdata);
391 throw std::string("Can't allocate output buffer");
396 case BZ_PARAM_ERROR: throw std::string("Compressor internal error");
397 case BZ_MEM_ERROR: throw std::string("Out of memory");
398 case BZ_DATA_ERROR: throw std::string("Data integrity error");
399 case BZ_DATA_ERROR_MAGIC:throw std::string("Data is not BZIP2");
400 default: throw("Ooops");
406 result = (static_cast<uint64_t>(bzdata.total_out_hi32) << 32) |
407 bzdata.total_out_lo32;
408 BZ2_bzDecompressEnd(&bzdata);
412 case COMP_TYPE_NONE: {
413 NULLCOMP_stream sdata;
414 sdata.next_in = (char*)in;
415 sdata.avail_in = size - 1;
416 NULLCOMP_init(&sdata);
418 if (0 != getdata(sdata.next_out, sdata.avail_out,cb,context)) {
419 throw std::string("Can't allocate output buffer");
422 while (!NULLCOMP_decompress(&sdata)) {
423 if (0 != getdata(sdata.next_out, sdata.avail_out,cb,context)) {
424 throw std::string("Can't allocate output buffer");
428 result = sdata.output_count;
429 NULLCOMP_end(&sdata);
434 throw std::string("Unknown type of compressed data");
441 Compressor::decompressToNewBuffer(const char* in, unsigned size, char*&out) {
442 BufferContext bc(size);
443 unsigned result = decompress(in,size,BufferContext::callback,(void*)&bc);
449 Compressor::decompressToStream(const char*in, unsigned size, std::ostream& out){
450 // Set up the context and writer
451 WriterContext ctxt(&out,size / 2);
453 // Compress everything after the magic number (which we'll alter)
454 uint64_t zipSize = Compressor::decompress(in,size,
455 WriterContext::callback, (void*)&ctxt);
458 ctxt.write(zipSize - ctxt.written);