1 ///////////////////////////////////////////////////////////////////////////////
3 /// \file block_buffer_encoder.c
4 /// \brief Single-call .xz Block encoder
6 // Copyright (C) 2009 Lasse Collin
8 // This library is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU Lesser General Public
10 // License as published by the Free Software Foundation; either
11 // version 2.1 of the License, or (at your option) any later version.
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 // Lesser General Public License for more details.
18 ///////////////////////////////////////////////////////////////////////////////
20 #include "block_encoder.h"
21 #include "filter_encoder.h"
22 #include "lzma2_encoder.h"
26 /// Estimate the maximum size of the Block Header and Check fields for
27 /// a Block that uses LZMA2 uncompressed chunks. We could use
28 /// lzma_block_header_size() but this is simpler.
30 /// Block Header Size + Block Flags + Compressed Size
31 /// + Uncompressed Size + Filter Flags for LZMA2 + CRC32 + Check
32 /// and round up to the next multiple of four to take Header Padding
34 #define HEADERS_BOUND ((1 + 1 + 2 * LZMA_VLI_BYTES_MAX + 3 + 4 \
35 + LZMA_CHECK_SIZE_MAX + 3) & ~3)
39 lzma2_bound(lzma_vli uncompressed_size)
41 // Prevent integer overflow in overhead calculation.
42 if (uncompressed_size > COMPRESSED_SIZE_MAX)
45 // Calculate the exact overhead of the LZMA2 headers: Round
46 // uncompressed_size up to the next multiple of LZMA2_CHUNK_MAX,
47 // multiply by the size of per-chunk header, and add one byte for
49 const lzma_vli overhead = ((uncompressed_size + LZMA2_CHUNK_MAX - 1)
51 * LZMA2_HEADER_UNCOMPRESSED + 1;
53 // Catch the possible integer overflow.
54 if (COMPRESSED_SIZE_MAX - overhead < uncompressed_size)
57 return uncompressed_size + overhead;
61 extern LZMA_API(size_t)
62 lzma_block_buffer_bound(size_t uncompressed_size)
64 // For now, if the data doesn't compress, we always use uncompressed
65 // chunks of LZMA2. In future we may use Subblock filter too, but
66 // but for simplicity we probably will still use the same bound
67 // calculation even though Subblock filter would have slightly less
69 lzma_vli lzma2_size = lzma2_bound(uncompressed_size);
73 // Take Block Padding into account.
74 lzma2_size = (lzma2_size + 3) & ~LZMA_VLI_C(3);
76 #if SIZE_MAX < LZMA_VLI_MAX
77 // Catch the possible integer overflow on 32-bit systems. There's no
78 // overflow on 64-bit systems, because lzma2_bound() already takes
79 // into account the size of the headers in the Block.
80 if (SIZE_MAX - HEADERS_BOUND < lzma2_size)
84 return HEADERS_BOUND + lzma2_size;
89 block_encode_uncompressed(lzma_block *block, const uint8_t *in, size_t in_size,
90 uint8_t *out, size_t *out_pos, size_t out_size)
92 // TODO: Figure out if the last filter is LZMA2 or Subblock and use
93 // that filter to encode the uncompressed chunks.
95 // Use LZMA2 uncompressed chunks. We wouldn't need a dictionary at
96 // all, but LZMA2 always requires a dictionary, so use the minimum
97 // value to minimize memory usage of the decoder.
98 lzma_options_lzma lzma2 = {
99 .dict_size = LZMA_DICT_SIZE_MIN,
102 lzma_filter filters[2];
103 filters[0].id = LZMA_FILTER_LZMA2;
104 filters[0].options = &lzma2;
105 filters[1].id = LZMA_VLI_UNKNOWN;
107 // Set the above filter options to *block temporarily so that we can
108 // encode the Block Header.
109 lzma_filter *filters_orig = block->filters;
110 block->filters = filters;
112 if (lzma_block_header_size(block) != LZMA_OK) {
113 block->filters = filters_orig;
114 return LZMA_PROG_ERROR;
117 // Check that there's enough output space. The caller has already
118 // set block->compressed_size to what lzma2_bound() has returned,
119 // so we can reuse that value. We know that compressed_size is a
120 // known valid VLI and header_size is a small value so their sum
121 // will never overflow.
122 assert(block->compressed_size == lzma2_bound(in_size));
123 if (out_size - *out_pos
124 < block->header_size + block->compressed_size) {
125 block->filters = filters_orig;
126 return LZMA_BUF_ERROR;
129 if (lzma_block_header_encode(block, out + *out_pos) != LZMA_OK) {
130 block->filters = filters_orig;
131 return LZMA_PROG_ERROR;
134 block->filters = filters_orig;
135 *out_pos += block->header_size;
137 // Encode the data using LZMA2 uncompressed chunks.
139 uint8_t control = 0x01; // Dictionary reset
141 while (in_pos < in_size) {
142 // Control byte: Indicate uncompressed chunk, of which
143 // the first resets the dictionary.
144 out[(*out_pos)++] = control;
145 control = 0x02; // No dictionary reset
147 // Size of the uncompressed chunk
148 const size_t copy_size
149 = MIN(in_size - in_pos, LZMA2_CHUNK_MAX);
150 out[(*out_pos)++] = (copy_size - 1) >> 8;
151 out[(*out_pos)++] = (copy_size - 1) & 0xFF;
154 assert(*out_pos + copy_size <= out_size);
155 memcpy(out + *out_pos, in + in_pos, copy_size);
158 *out_pos += copy_size;
162 out[(*out_pos)++] = 0x00;
163 assert(*out_pos <= out_size);
170 block_encode_normal(lzma_block *block, lzma_allocator *allocator,
171 const uint8_t *in, size_t in_size,
172 uint8_t *out, size_t *out_pos, size_t out_size)
174 // Find out the size of the Block Header.
175 block->compressed_size = lzma2_bound(in_size);
176 if (block->compressed_size == 0)
177 return LZMA_DATA_ERROR;
179 block->uncompressed_size = in_size;
180 return_if_error(lzma_block_header_size(block));
182 // Reserve space for the Block Header and skip it for now.
183 if (out_size - *out_pos <= block->header_size)
184 return LZMA_BUF_ERROR;
186 const size_t out_start = *out_pos;
187 *out_pos += block->header_size;
189 // Limit out_size so that we stop encoding if the output would grow
190 // bigger than what uncompressed Block would be.
191 if (out_size - *out_pos > block->compressed_size)
192 out_size = *out_pos + block->compressed_size;
194 // TODO: In many common cases this could be optimized to use
195 // significantly less memory.
196 lzma_next_coder raw_encoder = LZMA_NEXT_CODER_INIT;
197 lzma_ret ret = lzma_raw_encoder_init(
198 &raw_encoder, allocator, block->filters);
200 if (ret == LZMA_OK) {
202 ret = raw_encoder.code(raw_encoder.coder, allocator,
203 in, &in_pos, in_size, out, out_pos, out_size,
207 // NOTE: This needs to be run even if lzma_raw_encoder_init() failed.
208 lzma_next_end(&raw_encoder, allocator);
210 if (ret == LZMA_STREAM_END) {
211 // Compression was successful. Write the Block Header.
212 block->compressed_size
213 = *out_pos - (out_start + block->header_size);
214 ret = lzma_block_header_encode(block, out + out_start);
216 ret = LZMA_PROG_ERROR;
218 } else if (ret == LZMA_OK) {
219 // Output buffer became full.
220 ret = LZMA_BUF_ERROR;
223 // Reset *out_pos if something went wrong.
225 *out_pos = out_start;
231 extern LZMA_API(lzma_ret)
232 lzma_block_buffer_encode(lzma_block *block, lzma_allocator *allocator,
233 const uint8_t *in, size_t in_size,
234 uint8_t *out, size_t *out_pos, size_t out_size)
237 if (block == NULL || block->filters == NULL
238 || (in == NULL && in_size != 0) || out == NULL
239 || out_pos == NULL || *out_pos > out_size)
240 return LZMA_PROG_ERROR;
242 // Check the version field.
243 if (block->version != 0)
244 return LZMA_OPTIONS_ERROR;
246 // Size of a Block has to be a multiple of four, so limit the size
247 // here already. This way we don't need to check it again when adding
249 out_size -= (out_size - *out_pos) & 3;
251 // Get the size of the Check field.
252 const size_t check_size = lzma_check_size(block->check);
253 if (check_size == UINT32_MAX)
254 return LZMA_PROG_ERROR;
256 // Reserve space for the Check field.
257 if (out_size - *out_pos <= check_size)
258 return LZMA_BUF_ERROR;
260 out_size -= check_size;
262 // Do the actual compression.
263 const lzma_ret ret = block_encode_normal(block, allocator,
264 in, in_size, out, out_pos, out_size);
265 if (ret != LZMA_OK) {
266 // If the error was something else than output buffer
267 // becoming full, return the error now.
268 if (ret != LZMA_BUF_ERROR)
271 // The data was uncompressible (at least with the options
272 // given to us) or the output buffer was too small. Use the
273 // uncompressed chunks of LZMA2 to wrap the data into a valid
274 // Block. If we haven't been given enough output space, even
276 return_if_error(block_encode_uncompressed(block, in, in_size,
277 out, out_pos, out_size));
280 assert(*out_pos <= out_size);
282 // Block Padding. No buffer overflow here, because we already adjusted
283 // out_size so that (out_size - out_start) is a multiple of four.
284 // Thus, if the buffer is full, the loop body can never run.
285 for (size_t i = (size_t)(block->compressed_size); i & 3; ++i) {
286 assert(*out_pos < out_size);
287 out[(*out_pos)++] = 0x00;
290 // If there's no Check field, we are done now.
291 if (check_size > 0) {
292 // Calculate the integrity check. We reserved space for
293 // the Check field earlier so we don't need to check for
294 // available output space here.
295 lzma_check_state check;
296 lzma_check_init(&check, block->check);
297 lzma_check_update(&check, block->check, in, in_size);
298 lzma_check_finish(&check, block->check);
300 memcpy(out + *out_pos, check.buffer.u8, check_size);
301 *out_pos += check_size;