1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file block_buffer_encoder.c 4207753Smm/// \brief Single-call .xz Block encoder 5207753Smm// 6207753Smm// Author: Lasse Collin 7207753Smm// 8207753Smm// This file has been put into the public domain. 9207753Smm// You can do whatever you want with this file. 10207753Smm// 11207753Smm/////////////////////////////////////////////////////////////////////////////// 12207753Smm 13207753Smm#include "block_encoder.h" 14207753Smm#include "filter_encoder.h" 15207753Smm#include "lzma2_encoder.h" 16207753Smm#include "check.h" 17207753Smm 18207753Smm 19207753Smm/// Estimate the maximum size of the Block Header and Check fields for 20207753Smm/// a Block that uses LZMA2 uncompressed chunks. We could use 21207753Smm/// lzma_block_header_size() but this is simpler. 22207753Smm/// 23207753Smm/// Block Header Size + Block Flags + Compressed Size 24207753Smm/// + Uncompressed Size + Filter Flags for LZMA2 + CRC32 + Check 25207753Smm/// and round up to the next multiple of four to take Header Padding 26207753Smm/// into account. 27207753Smm#define HEADERS_BOUND ((1 + 1 + 2 * LZMA_VLI_BYTES_MAX + 3 + 4 \ 28207753Smm + LZMA_CHECK_SIZE_MAX + 3) & ~3) 29207753Smm 30207753Smm 31207753Smmstatic lzma_vli 32207753Smmlzma2_bound(lzma_vli uncompressed_size) 33207753Smm{ 34207753Smm // Prevent integer overflow in overhead calculation. 35207753Smm if (uncompressed_size > COMPRESSED_SIZE_MAX) 36207753Smm return 0; 37207753Smm 38207753Smm // Calculate the exact overhead of the LZMA2 headers: Round 39207753Smm // uncompressed_size up to the next multiple of LZMA2_CHUNK_MAX, 40207753Smm // multiply by the size of per-chunk header, and add one byte for 41207753Smm // the end marker. 42207753Smm const lzma_vli overhead = ((uncompressed_size + LZMA2_CHUNK_MAX - 1) 43207753Smm / LZMA2_CHUNK_MAX) 44207753Smm * LZMA2_HEADER_UNCOMPRESSED + 1; 45207753Smm 46207753Smm // Catch the possible integer overflow. 47207753Smm if (COMPRESSED_SIZE_MAX - overhead < uncompressed_size) 48207753Smm return 0; 49207753Smm 50207753Smm return uncompressed_size + overhead; 51207753Smm} 52207753Smm 53207753Smm 54207753Smmextern LZMA_API(size_t) 55207753Smmlzma_block_buffer_bound(size_t uncompressed_size) 56207753Smm{ 57207753Smm // For now, if the data doesn't compress, we always use uncompressed 58207753Smm // chunks of LZMA2. In future we may use Subblock filter too, but 59207753Smm // but for simplicity we probably will still use the same bound 60207753Smm // calculation even though Subblock filter would have slightly less 61207753Smm // overhead. 62207753Smm lzma_vli lzma2_size = lzma2_bound(uncompressed_size); 63207753Smm if (lzma2_size == 0) 64207753Smm return 0; 65207753Smm 66207753Smm // Take Block Padding into account. 67207753Smm lzma2_size = (lzma2_size + 3) & ~LZMA_VLI_C(3); 68207753Smm 69207753Smm#if SIZE_MAX < LZMA_VLI_MAX 70207753Smm // Catch the possible integer overflow on 32-bit systems. There's no 71207753Smm // overflow on 64-bit systems, because lzma2_bound() already takes 72207753Smm // into account the size of the headers in the Block. 73207753Smm if (SIZE_MAX - HEADERS_BOUND < lzma2_size) 74207753Smm return 0; 75207753Smm#endif 76207753Smm 77207753Smm return HEADERS_BOUND + lzma2_size; 78207753Smm} 79207753Smm 80207753Smm 81207753Smmstatic lzma_ret 82207753Smmblock_encode_uncompressed(lzma_block *block, const uint8_t *in, size_t in_size, 83207753Smm uint8_t *out, size_t *out_pos, size_t out_size) 84207753Smm{ 85207753Smm // TODO: Figure out if the last filter is LZMA2 or Subblock and use 86207753Smm // that filter to encode the uncompressed chunks. 87207753Smm 88207753Smm // Use LZMA2 uncompressed chunks. We wouldn't need a dictionary at 89207753Smm // all, but LZMA2 always requires a dictionary, so use the minimum 90207753Smm // value to minimize memory usage of the decoder. 91207753Smm lzma_options_lzma lzma2 = { 92207753Smm .dict_size = LZMA_DICT_SIZE_MIN, 93207753Smm }; 94207753Smm 95207753Smm lzma_filter filters[2]; 96207753Smm filters[0].id = LZMA_FILTER_LZMA2; 97207753Smm filters[0].options = &lzma2; 98207753Smm filters[1].id = LZMA_VLI_UNKNOWN; 99207753Smm 100207753Smm // Set the above filter options to *block temporarily so that we can 101207753Smm // encode the Block Header. 102207753Smm lzma_filter *filters_orig = block->filters; 103207753Smm block->filters = filters; 104207753Smm 105207753Smm if (lzma_block_header_size(block) != LZMA_OK) { 106207753Smm block->filters = filters_orig; 107207753Smm return LZMA_PROG_ERROR; 108207753Smm } 109207753Smm 110207753Smm // Check that there's enough output space. The caller has already 111207753Smm // set block->compressed_size to what lzma2_bound() has returned, 112207753Smm // so we can reuse that value. We know that compressed_size is a 113207753Smm // known valid VLI and header_size is a small value so their sum 114207753Smm // will never overflow. 115207753Smm assert(block->compressed_size == lzma2_bound(in_size)); 116207753Smm if (out_size - *out_pos 117207753Smm < block->header_size + block->compressed_size) { 118207753Smm block->filters = filters_orig; 119207753Smm return LZMA_BUF_ERROR; 120207753Smm } 121207753Smm 122207753Smm if (lzma_block_header_encode(block, out + *out_pos) != LZMA_OK) { 123207753Smm block->filters = filters_orig; 124207753Smm return LZMA_PROG_ERROR; 125207753Smm } 126207753Smm 127207753Smm block->filters = filters_orig; 128207753Smm *out_pos += block->header_size; 129207753Smm 130207753Smm // Encode the data using LZMA2 uncompressed chunks. 131207753Smm size_t in_pos = 0; 132207753Smm uint8_t control = 0x01; // Dictionary reset 133207753Smm 134207753Smm while (in_pos < in_size) { 135207753Smm // Control byte: Indicate uncompressed chunk, of which 136207753Smm // the first resets the dictionary. 137207753Smm out[(*out_pos)++] = control; 138207753Smm control = 0x02; // No dictionary reset 139207753Smm 140207753Smm // Size of the uncompressed chunk 141207753Smm const size_t copy_size 142213700Smm = my_min(in_size - in_pos, LZMA2_CHUNK_MAX); 143207753Smm out[(*out_pos)++] = (copy_size - 1) >> 8; 144207753Smm out[(*out_pos)++] = (copy_size - 1) & 0xFF; 145207753Smm 146207753Smm // The actual data 147207753Smm assert(*out_pos + copy_size <= out_size); 148207753Smm memcpy(out + *out_pos, in + in_pos, copy_size); 149207753Smm 150207753Smm in_pos += copy_size; 151207753Smm *out_pos += copy_size; 152207753Smm } 153207753Smm 154207753Smm // End marker 155207753Smm out[(*out_pos)++] = 0x00; 156207753Smm assert(*out_pos <= out_size); 157207753Smm 158207753Smm return LZMA_OK; 159207753Smm} 160207753Smm 161207753Smm 162207753Smmstatic lzma_ret 163207753Smmblock_encode_normal(lzma_block *block, lzma_allocator *allocator, 164207753Smm const uint8_t *in, size_t in_size, 165207753Smm uint8_t *out, size_t *out_pos, size_t out_size) 166207753Smm{ 167207753Smm // Find out the size of the Block Header. 168207753Smm block->compressed_size = lzma2_bound(in_size); 169207753Smm if (block->compressed_size == 0) 170207753Smm return LZMA_DATA_ERROR; 171207753Smm 172207753Smm block->uncompressed_size = in_size; 173207753Smm return_if_error(lzma_block_header_size(block)); 174207753Smm 175207753Smm // Reserve space for the Block Header and skip it for now. 176207753Smm if (out_size - *out_pos <= block->header_size) 177207753Smm return LZMA_BUF_ERROR; 178207753Smm 179207753Smm const size_t out_start = *out_pos; 180207753Smm *out_pos += block->header_size; 181207753Smm 182207753Smm // Limit out_size so that we stop encoding if the output would grow 183207753Smm // bigger than what uncompressed Block would be. 184207753Smm if (out_size - *out_pos > block->compressed_size) 185207753Smm out_size = *out_pos + block->compressed_size; 186207753Smm 187207753Smm // TODO: In many common cases this could be optimized to use 188207753Smm // significantly less memory. 189207753Smm lzma_next_coder raw_encoder = LZMA_NEXT_CODER_INIT; 190207753Smm lzma_ret ret = lzma_raw_encoder_init( 191207753Smm &raw_encoder, allocator, block->filters); 192207753Smm 193207753Smm if (ret == LZMA_OK) { 194207753Smm size_t in_pos = 0; 195207753Smm ret = raw_encoder.code(raw_encoder.coder, allocator, 196207753Smm in, &in_pos, in_size, out, out_pos, out_size, 197207753Smm LZMA_FINISH); 198207753Smm } 199207753Smm 200207753Smm // NOTE: This needs to be run even if lzma_raw_encoder_init() failed. 201207753Smm lzma_next_end(&raw_encoder, allocator); 202207753Smm 203207753Smm if (ret == LZMA_STREAM_END) { 204207753Smm // Compression was successful. Write the Block Header. 205207753Smm block->compressed_size 206207753Smm = *out_pos - (out_start + block->header_size); 207207753Smm ret = lzma_block_header_encode(block, out + out_start); 208207753Smm if (ret != LZMA_OK) 209207753Smm ret = LZMA_PROG_ERROR; 210207753Smm 211207753Smm } else if (ret == LZMA_OK) { 212207753Smm // Output buffer became full. 213207753Smm ret = LZMA_BUF_ERROR; 214207753Smm } 215207753Smm 216207753Smm // Reset *out_pos if something went wrong. 217207753Smm if (ret != LZMA_OK) 218207753Smm *out_pos = out_start; 219207753Smm 220207753Smm return ret; 221207753Smm} 222207753Smm 223207753Smm 224207753Smmextern LZMA_API(lzma_ret) 225207753Smmlzma_block_buffer_encode(lzma_block *block, lzma_allocator *allocator, 226207753Smm const uint8_t *in, size_t in_size, 227207753Smm uint8_t *out, size_t *out_pos, size_t out_size) 228207753Smm{ 229223935Smm // Validate the arguments. 230223935Smm if (block == NULL || (in == NULL && in_size != 0) || out == NULL 231207753Smm || out_pos == NULL || *out_pos > out_size) 232207753Smm return LZMA_PROG_ERROR; 233207753Smm 234223935Smm // The contents of the structure may depend on the version so 235223935Smm // check the version before validating the contents of *block. 236207753Smm if (block->version != 0) 237207753Smm return LZMA_OPTIONS_ERROR; 238207753Smm 239223935Smm if ((unsigned int)(block->check) > LZMA_CHECK_ID_MAX 240223935Smm || block->filters == NULL) 241223935Smm return LZMA_PROG_ERROR; 242223935Smm 243223935Smm if (!lzma_check_is_supported(block->check)) 244223935Smm return LZMA_UNSUPPORTED_CHECK; 245223935Smm 246207753Smm // Size of a Block has to be a multiple of four, so limit the size 247207753Smm // here already. This way we don't need to check it again when adding 248207753Smm // Block Padding. 249207753Smm out_size -= (out_size - *out_pos) & 3; 250207753Smm 251207753Smm // Get the size of the Check field. 252207753Smm const size_t check_size = lzma_check_size(block->check); 253223935Smm assert(check_size != UINT32_MAX); 254207753Smm 255207753Smm // Reserve space for the Check field. 256207753Smm if (out_size - *out_pos <= check_size) 257207753Smm return LZMA_BUF_ERROR; 258207753Smm 259207753Smm out_size -= check_size; 260207753Smm 261207753Smm // Do the actual compression. 262207753Smm const lzma_ret ret = block_encode_normal(block, allocator, 263207753Smm in, in_size, out, out_pos, out_size); 264207753Smm if (ret != LZMA_OK) { 265207753Smm // If the error was something else than output buffer 266207753Smm // becoming full, return the error now. 267207753Smm if (ret != LZMA_BUF_ERROR) 268207753Smm return ret; 269207753Smm 270207753Smm // The data was uncompressible (at least with the options 271207753Smm // given to us) or the output buffer was too small. Use the 272207753Smm // uncompressed chunks of LZMA2 to wrap the data into a valid 273207753Smm // Block. If we haven't been given enough output space, even 274207753Smm // this may fail. 275207753Smm return_if_error(block_encode_uncompressed(block, in, in_size, 276207753Smm out, out_pos, out_size)); 277207753Smm } 278207753Smm 279207753Smm assert(*out_pos <= out_size); 280207753Smm 281207753Smm // Block Padding. No buffer overflow here, because we already adjusted 282207753Smm // out_size so that (out_size - out_start) is a multiple of four. 283207753Smm // Thus, if the buffer is full, the loop body can never run. 284207753Smm for (size_t i = (size_t)(block->compressed_size); i & 3; ++i) { 285207753Smm assert(*out_pos < out_size); 286207753Smm out[(*out_pos)++] = 0x00; 287207753Smm } 288207753Smm 289207753Smm // If there's no Check field, we are done now. 290207753Smm if (check_size > 0) { 291207753Smm // Calculate the integrity check. We reserved space for 292207753Smm // the Check field earlier so we don't need to check for 293207753Smm // available output space here. 294207753Smm lzma_check_state check; 295207753Smm lzma_check_init(&check, block->check); 296207753Smm lzma_check_update(&check, block->check, in, in_size); 297207753Smm lzma_check_finish(&check, block->check); 298207753Smm 299207753Smm memcpy(block->raw_check, check.buffer.u8, check_size); 300207753Smm memcpy(out + *out_pos, check.buffer.u8, check_size); 301207753Smm *out_pos += check_size; 302207753Smm } 303207753Smm 304207753Smm return LZMA_OK; 305207753Smm} 306