1 /////////////////////////////////////////////////////////////////////////////// 2 // 3 /// \file block_buffer_encoder.c 4 /// \brief Single-call .xz Block encoder 5 // 6 // Author: Lasse Collin 7 // 8 // This file has been put into the public domain. 9 // You can do whatever you want with this file. 10 // 11 /////////////////////////////////////////////////////////////////////////////// 12 13 #include "block_encoder.h" 14 #include "filter_encoder.h" 15 #include "lzma2_encoder.h" 16 #include "check.h" 17 18 19 /// Estimate the maximum size of the Block Header and Check fields for 20 /// a Block that uses LZMA2 uncompressed chunks. We could use 21 /// lzma_block_header_size() but this is simpler. 22 /// 23 /// Block Header Size + Block Flags + Compressed Size 24 /// + Uncompressed Size + Filter Flags for LZMA2 + CRC32 + Check 25 /// and round up to the next multiple of four to take Header Padding 26 /// into account. 27 #define HEADERS_BOUND ((1 + 1 + 2 * LZMA_VLI_BYTES_MAX + 3 + 4 \ 28 + LZMA_CHECK_SIZE_MAX + 3) & ~3) 29 30 31 static lzma_vli 32 lzma2_bound(lzma_vli uncompressed_size) 33 { 34 // Prevent integer overflow in overhead calculation. 35 if (uncompressed_size > COMPRESSED_SIZE_MAX) 36 return 0; 37 38 // Calculate the exact overhead of the LZMA2 headers: Round 39 // uncompressed_size up to the next multiple of LZMA2_CHUNK_MAX, 40 // multiply by the size of per-chunk header, and add one byte for 41 // the end marker. 42 const lzma_vli overhead = ((uncompressed_size + LZMA2_CHUNK_MAX - 1) 43 / LZMA2_CHUNK_MAX) 44 * LZMA2_HEADER_UNCOMPRESSED + 1; 45 46 // Catch the possible integer overflow. 47 if (COMPRESSED_SIZE_MAX - overhead < uncompressed_size) 48 return 0; 49 50 return uncompressed_size + overhead; 51 } 52 53 54 extern LZMA_API(size_t) 55 lzma_block_buffer_bound(size_t uncompressed_size) 56 { 57 // For now, if the data doesn't compress, we always use uncompressed 58 // chunks of LZMA2. In future we may use Subblock filter too, but 59 // but for simplicity we probably will still use the same bound 60 // calculation even though Subblock filter would have slightly less 61 // overhead. 62 lzma_vli lzma2_size = lzma2_bound(uncompressed_size); 63 if (lzma2_size == 0) 64 return 0; 65 66 // Take Block Padding into account. 67 lzma2_size = (lzma2_size + 3) & ~LZMA_VLI_C(3); 68 69 #if SIZE_MAX < LZMA_VLI_MAX 70 // Catch the possible integer overflow on 32-bit systems. There's no 71 // overflow on 64-bit systems, because lzma2_bound() already takes 72 // into account the size of the headers in the Block. 73 if (SIZE_MAX - HEADERS_BOUND < lzma2_size) 74 return 0; 75 #endif 76 77 return HEADERS_BOUND + lzma2_size; 78 } 79 80 81 static lzma_ret 82 block_encode_uncompressed(lzma_block *block, const uint8_t *in, size_t in_size, 83 uint8_t *out, size_t *out_pos, size_t out_size) 84 { 85 // TODO: Figure out if the last filter is LZMA2 or Subblock and use 86 // that filter to encode the uncompressed chunks. 87 88 // Use LZMA2 uncompressed chunks. We wouldn't need a dictionary at 89 // all, but LZMA2 always requires a dictionary, so use the minimum 90 // value to minimize memory usage of the decoder. 91 lzma_options_lzma lzma2 = { 92 .dict_size = LZMA_DICT_SIZE_MIN, 93 }; 94 95 lzma_filter filters[2]; 96 filters[0].id = LZMA_FILTER_LZMA2; 97 filters[0].options = &lzma2; 98 filters[1].id = LZMA_VLI_UNKNOWN; 99 100 // Set the above filter options to *block temporarily so that we can 101 // encode the Block Header. 102 lzma_filter *filters_orig = block->filters; 103 block->filters = filters; 104 105 if (lzma_block_header_size(block) != LZMA_OK) { 106 block->filters = filters_orig; 107 return LZMA_PROG_ERROR; 108 } 109 110 // Check that there's enough output space. The caller has already 111 // set block->compressed_size to what lzma2_bound() has returned, 112 // so we can reuse that value. We know that compressed_size is a 113 // known valid VLI and header_size is a small value so their sum 114 // will never overflow. 115 assert(block->compressed_size == lzma2_bound(in_size)); 116 if (out_size - *out_pos 117 < block->header_size + block->compressed_size) { 118 block->filters = filters_orig; 119 return LZMA_BUF_ERROR; 120 } 121 122 if (lzma_block_header_encode(block, out + *out_pos) != LZMA_OK) { 123 block->filters = filters_orig; 124 return LZMA_PROG_ERROR; 125 } 126 127 block->filters = filters_orig; 128 *out_pos += block->header_size; 129 130 // Encode the data using LZMA2 uncompressed chunks. 131 size_t in_pos = 0; 132 uint8_t control = 0x01; // Dictionary reset 133 134 while (in_pos < in_size) { 135 // Control byte: Indicate uncompressed chunk, of which 136 // the first resets the dictionary. 137 out[(*out_pos)++] = control; 138 control = 0x02; // No dictionary reset 139 140 // Size of the uncompressed chunk 141 const size_t copy_size 142 = my_min(in_size - in_pos, LZMA2_CHUNK_MAX); 143 out[(*out_pos)++] = (copy_size - 1) >> 8; 144 out[(*out_pos)++] = (copy_size - 1) & 0xFF; 145 146 // The actual data 147 assert(*out_pos + copy_size <= out_size); 148 memcpy(out + *out_pos, in + in_pos, copy_size); 149 150 in_pos += copy_size; 151 *out_pos += copy_size; 152 } 153 154 // End marker 155 out[(*out_pos)++] = 0x00; 156 assert(*out_pos <= out_size); 157 158 return LZMA_OK; 159 } 160 161 162 static lzma_ret 163 block_encode_normal(lzma_block *block, lzma_allocator *allocator, 164 const uint8_t *in, size_t in_size, 165 uint8_t *out, size_t *out_pos, size_t out_size) 166 { 167 // Find out the size of the Block Header. 168 block->compressed_size = lzma2_bound(in_size); 169 if (block->compressed_size == 0) 170 return LZMA_DATA_ERROR; 171 172 block->uncompressed_size = in_size; 173 return_if_error(lzma_block_header_size(block)); 174 175 // Reserve space for the Block Header and skip it for now. 176 if (out_size - *out_pos <= block->header_size) 177 return LZMA_BUF_ERROR; 178 179 const size_t out_start = *out_pos; 180 *out_pos += block->header_size; 181 182 // Limit out_size so that we stop encoding if the output would grow 183 // bigger than what uncompressed Block would be. 184 if (out_size - *out_pos > block->compressed_size) 185 out_size = *out_pos + block->compressed_size; 186 187 // TODO: In many common cases this could be optimized to use 188 // significantly less memory. 189 lzma_next_coder raw_encoder = LZMA_NEXT_CODER_INIT; 190 lzma_ret ret = lzma_raw_encoder_init( 191 &raw_encoder, allocator, block->filters); 192 193 if (ret == LZMA_OK) { 194 size_t in_pos = 0; 195 ret = raw_encoder.code(raw_encoder.coder, allocator, 196 in, &in_pos, in_size, out, out_pos, out_size, 197 LZMA_FINISH); 198 } 199 200 // NOTE: This needs to be run even if lzma_raw_encoder_init() failed. 201 lzma_next_end(&raw_encoder, allocator); 202 203 if (ret == LZMA_STREAM_END) { 204 // Compression was successful. Write the Block Header. 205 block->compressed_size 206 = *out_pos - (out_start + block->header_size); 207 ret = lzma_block_header_encode(block, out + out_start); 208 if (ret != LZMA_OK) 209 ret = LZMA_PROG_ERROR; 210 211 } else if (ret == LZMA_OK) { 212 // Output buffer became full. 213 ret = LZMA_BUF_ERROR; 214 } 215 216 // Reset *out_pos if something went wrong. 217 if (ret != LZMA_OK) 218 *out_pos = out_start; 219 220 return ret; 221 } 222 223 224 extern LZMA_API(lzma_ret) 225 lzma_block_buffer_encode(lzma_block *block, lzma_allocator *allocator, 226 const uint8_t *in, size_t in_size, 227 uint8_t *out, size_t *out_pos, size_t out_size) 228 { 229 // Validate the arguments. 230 if (block == NULL || (in == NULL && in_size != 0) || out == NULL 231 || out_pos == NULL || *out_pos > out_size) 232 return LZMA_PROG_ERROR; 233 234 // The contents of the structure may depend on the version so 235 // check the version before validating the contents of *block. 236 if (block->version != 0) 237 return LZMA_OPTIONS_ERROR; 238 239 if ((unsigned int)(block->check) > LZMA_CHECK_ID_MAX 240 || block->filters == NULL) 241 return LZMA_PROG_ERROR; 242 243 if (!lzma_check_is_supported(block->check)) 244 return LZMA_UNSUPPORTED_CHECK; 245 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 248 // Block Padding. 249 out_size -= (out_size - *out_pos) & 3; 250 251 // Get the size of the Check field. 252 const size_t check_size = lzma_check_size(block->check); 253 assert(check_size != UINT32_MAX); 254 255 // Reserve space for the Check field. 256 if (out_size - *out_pos <= check_size) 257 return LZMA_BUF_ERROR; 258 259 out_size -= check_size; 260 261 // Do the actual compression. 262 const lzma_ret ret = block_encode_normal(block, allocator, 263 in, in_size, out, out_pos, out_size); 264 if (ret != LZMA_OK) { 265 // If the error was something else than output buffer 266 // becoming full, return the error now. 267 if (ret != LZMA_BUF_ERROR) 268 return ret; 269 270 // The data was uncompressible (at least with the options 271 // given to us) or the output buffer was too small. Use the 272 // uncompressed chunks of LZMA2 to wrap the data into a valid 273 // Block. If we haven't been given enough output space, even 274 // this may fail. 275 return_if_error(block_encode_uncompressed(block, in, in_size, 276 out, out_pos, out_size)); 277 } 278 279 assert(*out_pos <= out_size); 280 281 // Block Padding. No buffer overflow here, because we already adjusted 282 // out_size so that (out_size - out_start) is a multiple of four. 283 // Thus, if the buffer is full, the loop body can never run. 284 for (size_t i = (size_t)(block->compressed_size); i & 3; ++i) { 285 assert(*out_pos < out_size); 286 out[(*out_pos)++] = 0x00; 287 } 288 289 // If there's no Check field, we are done now. 290 if (check_size > 0) { 291 // Calculate the integrity check. We reserved space for 292 // the Check field earlier so we don't need to check for 293 // available output space here. 294 lzma_check_state check; 295 lzma_check_init(&check, block->check); 296 lzma_check_update(&check, block->check, in, in_size); 297 lzma_check_finish(&check, block->check); 298 299 memcpy(block->raw_check, check.buffer.u8, check_size); 300 memcpy(out + *out_pos, check.buffer.u8, check_size); 301 *out_pos += check_size; 302 } 303 304 return LZMA_OK; 305 } 306