1207753Smm/////////////////////////////////////////////////////////////////////////////// 2207753Smm// 3207753Smm/// \file lzma2_encoder.c 4207753Smm/// \brief LZMA2 encoder 5207753Smm/// 6207753Smm// Authors: Igor Pavlov 7207753Smm// Lasse Collin 8207753Smm// 9207753Smm// This file has been put into the public domain. 10207753Smm// You can do whatever you want with this file. 11207753Smm// 12207753Smm/////////////////////////////////////////////////////////////////////////////// 13207753Smm 14207753Smm#include "lz_encoder.h" 15207753Smm#include "lzma_encoder.h" 16207753Smm#include "fastpos.h" 17207753Smm#include "lzma2_encoder.h" 18207753Smm 19207753Smm 20312518Sdelphijtypedef struct { 21207753Smm enum { 22207753Smm SEQ_INIT, 23207753Smm SEQ_LZMA_ENCODE, 24207753Smm SEQ_LZMA_COPY, 25207753Smm SEQ_UNCOMPRESSED_HEADER, 26207753Smm SEQ_UNCOMPRESSED_COPY, 27207753Smm } sequence; 28207753Smm 29207753Smm /// LZMA encoder 30312518Sdelphij void *lzma; 31207753Smm 32207753Smm /// LZMA options currently in use. 33207753Smm lzma_options_lzma opt_cur; 34207753Smm 35207753Smm bool need_properties; 36207753Smm bool need_state_reset; 37207753Smm bool need_dictionary_reset; 38207753Smm 39207753Smm /// Uncompressed size of a chunk 40207753Smm size_t uncompressed_size; 41207753Smm 42207753Smm /// Compressed size of a chunk (excluding headers); this is also used 43207753Smm /// to indicate the end of buf[] in SEQ_LZMA_COPY. 44207753Smm size_t compressed_size; 45207753Smm 46207753Smm /// Read position in buf[] 47207753Smm size_t buf_pos; 48207753Smm 49207753Smm /// Buffer to hold the chunk header and LZMA compressed data 50207753Smm uint8_t buf[LZMA2_HEADER_MAX + LZMA2_CHUNK_MAX]; 51312518Sdelphij} lzma_lzma2_coder; 52207753Smm 53207753Smm 54207753Smmstatic void 55312518Sdelphijlzma2_header_lzma(lzma_lzma2_coder *coder) 56207753Smm{ 57207753Smm assert(coder->uncompressed_size > 0); 58207753Smm assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX); 59207753Smm assert(coder->compressed_size > 0); 60207753Smm assert(coder->compressed_size <= LZMA2_CHUNK_MAX); 61207753Smm 62207753Smm size_t pos; 63207753Smm 64207753Smm if (coder->need_properties) { 65207753Smm pos = 0; 66207753Smm 67207753Smm if (coder->need_dictionary_reset) 68207753Smm coder->buf[pos] = 0x80 + (3 << 5); 69207753Smm else 70207753Smm coder->buf[pos] = 0x80 + (2 << 5); 71207753Smm } else { 72207753Smm pos = 1; 73207753Smm 74207753Smm if (coder->need_state_reset) 75207753Smm coder->buf[pos] = 0x80 + (1 << 5); 76207753Smm else 77207753Smm coder->buf[pos] = 0x80; 78207753Smm } 79207753Smm 80207753Smm // Set the start position for copying. 81207753Smm coder->buf_pos = pos; 82207753Smm 83207753Smm // Uncompressed size 84207753Smm size_t size = coder->uncompressed_size - 1; 85207753Smm coder->buf[pos++] += size >> 16; 86207753Smm coder->buf[pos++] = (size >> 8) & 0xFF; 87207753Smm coder->buf[pos++] = size & 0xFF; 88207753Smm 89207753Smm // Compressed size 90207753Smm size = coder->compressed_size - 1; 91207753Smm coder->buf[pos++] = size >> 8; 92207753Smm coder->buf[pos++] = size & 0xFF; 93207753Smm 94207753Smm // Properties, if needed 95207753Smm if (coder->need_properties) 96207753Smm lzma_lzma_lclppb_encode(&coder->opt_cur, coder->buf + pos); 97207753Smm 98207753Smm coder->need_properties = false; 99207753Smm coder->need_state_reset = false; 100207753Smm coder->need_dictionary_reset = false; 101207753Smm 102207753Smm // The copying code uses coder->compressed_size to indicate the end 103207753Smm // of coder->buf[], so we need add the maximum size of the header here. 104207753Smm coder->compressed_size += LZMA2_HEADER_MAX; 105207753Smm 106207753Smm return; 107207753Smm} 108207753Smm 109207753Smm 110207753Smmstatic void 111312518Sdelphijlzma2_header_uncompressed(lzma_lzma2_coder *coder) 112207753Smm{ 113207753Smm assert(coder->uncompressed_size > 0); 114207753Smm assert(coder->uncompressed_size <= LZMA2_CHUNK_MAX); 115207753Smm 116207753Smm // If this is the first chunk, we need to include dictionary 117207753Smm // reset indicator. 118207753Smm if (coder->need_dictionary_reset) 119207753Smm coder->buf[0] = 1; 120207753Smm else 121207753Smm coder->buf[0] = 2; 122207753Smm 123207753Smm coder->need_dictionary_reset = false; 124207753Smm 125207753Smm // "Compressed" size 126207753Smm coder->buf[1] = (coder->uncompressed_size - 1) >> 8; 127207753Smm coder->buf[2] = (coder->uncompressed_size - 1) & 0xFF; 128207753Smm 129207753Smm // Set the start position for copying. 130207753Smm coder->buf_pos = 0; 131207753Smm return; 132207753Smm} 133207753Smm 134207753Smm 135207753Smmstatic lzma_ret 136312518Sdelphijlzma2_encode(void *coder_ptr, lzma_mf *restrict mf, 137207753Smm uint8_t *restrict out, size_t *restrict out_pos, 138207753Smm size_t out_size) 139207753Smm{ 140312518Sdelphij lzma_lzma2_coder *restrict coder = coder_ptr; 141312518Sdelphij 142207753Smm while (*out_pos < out_size) 143207753Smm switch (coder->sequence) { 144207753Smm case SEQ_INIT: 145207753Smm // If there's no input left and we are flushing or finishing, 146207753Smm // don't start a new chunk. 147207753Smm if (mf_unencoded(mf) == 0) { 148207753Smm // Write end of payload marker if finishing. 149207753Smm if (mf->action == LZMA_FINISH) 150207753Smm out[(*out_pos)++] = 0; 151207753Smm 152207753Smm return mf->action == LZMA_RUN 153207753Smm ? LZMA_OK : LZMA_STREAM_END; 154207753Smm } 155207753Smm 156207753Smm if (coder->need_state_reset) 157207753Smm return_if_error(lzma_lzma_encoder_reset( 158207753Smm coder->lzma, &coder->opt_cur)); 159207753Smm 160207753Smm coder->uncompressed_size = 0; 161207753Smm coder->compressed_size = 0; 162207753Smm coder->sequence = SEQ_LZMA_ENCODE; 163207753Smm 164207753Smm // Fall through 165207753Smm 166207753Smm case SEQ_LZMA_ENCODE: { 167207753Smm // Calculate how much more uncompressed data this chunk 168207753Smm // could accept. 169207753Smm const uint32_t left = LZMA2_UNCOMPRESSED_MAX 170207753Smm - coder->uncompressed_size; 171207753Smm uint32_t limit; 172207753Smm 173207753Smm if (left < mf->match_len_max) { 174207753Smm // Must flush immediately since the next LZMA symbol 175207753Smm // could make the uncompressed size of the chunk too 176207753Smm // big. 177207753Smm limit = 0; 178207753Smm } else { 179207753Smm // Calculate maximum read_limit that is OK from point 180207753Smm // of view of LZMA2 chunk size. 181207753Smm limit = mf->read_pos - mf->read_ahead 182207753Smm + left - mf->match_len_max; 183207753Smm } 184207753Smm 185207753Smm // Save the start position so that we can update 186207753Smm // coder->uncompressed_size. 187207753Smm const uint32_t read_start = mf->read_pos - mf->read_ahead; 188207753Smm 189207753Smm // Call the LZMA encoder until the chunk is finished. 190207753Smm const lzma_ret ret = lzma_lzma_encode(coder->lzma, mf, 191207753Smm coder->buf + LZMA2_HEADER_MAX, 192207753Smm &coder->compressed_size, 193207753Smm LZMA2_CHUNK_MAX, limit); 194207753Smm 195207753Smm coder->uncompressed_size += mf->read_pos - mf->read_ahead 196207753Smm - read_start; 197207753Smm 198207753Smm assert(coder->compressed_size <= LZMA2_CHUNK_MAX); 199207753Smm assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX); 200207753Smm 201207753Smm if (ret != LZMA_STREAM_END) 202207753Smm return LZMA_OK; 203207753Smm 204207753Smm // See if the chunk compressed. If it didn't, we encode it 205207753Smm // as uncompressed chunk. This saves a few bytes of space 206207753Smm // and makes decoding faster. 207207753Smm if (coder->compressed_size >= coder->uncompressed_size) { 208207753Smm coder->uncompressed_size += mf->read_ahead; 209207753Smm assert(coder->uncompressed_size 210207753Smm <= LZMA2_UNCOMPRESSED_MAX); 211207753Smm mf->read_ahead = 0; 212207753Smm lzma2_header_uncompressed(coder); 213207753Smm coder->need_state_reset = true; 214207753Smm coder->sequence = SEQ_UNCOMPRESSED_HEADER; 215207753Smm break; 216207753Smm } 217207753Smm 218207753Smm // The chunk did compress at least by one byte, so we store 219207753Smm // the chunk as LZMA. 220207753Smm lzma2_header_lzma(coder); 221207753Smm 222207753Smm coder->sequence = SEQ_LZMA_COPY; 223207753Smm } 224207753Smm 225207753Smm // Fall through 226207753Smm 227207753Smm case SEQ_LZMA_COPY: 228207753Smm // Copy the compressed chunk along its headers to the 229207753Smm // output buffer. 230207753Smm lzma_bufcpy(coder->buf, &coder->buf_pos, 231207753Smm coder->compressed_size, 232207753Smm out, out_pos, out_size); 233207753Smm if (coder->buf_pos != coder->compressed_size) 234207753Smm return LZMA_OK; 235207753Smm 236207753Smm coder->sequence = SEQ_INIT; 237207753Smm break; 238207753Smm 239207753Smm case SEQ_UNCOMPRESSED_HEADER: 240207753Smm // Copy the three-byte header to indicate uncompressed chunk. 241207753Smm lzma_bufcpy(coder->buf, &coder->buf_pos, 242207753Smm LZMA2_HEADER_UNCOMPRESSED, 243207753Smm out, out_pos, out_size); 244207753Smm if (coder->buf_pos != LZMA2_HEADER_UNCOMPRESSED) 245207753Smm return LZMA_OK; 246207753Smm 247207753Smm coder->sequence = SEQ_UNCOMPRESSED_COPY; 248207753Smm 249207753Smm // Fall through 250207753Smm 251207753Smm case SEQ_UNCOMPRESSED_COPY: 252207753Smm // Copy the uncompressed data as is from the dictionary 253207753Smm // to the output buffer. 254207753Smm mf_read(mf, out, out_pos, out_size, &coder->uncompressed_size); 255207753Smm if (coder->uncompressed_size != 0) 256207753Smm return LZMA_OK; 257207753Smm 258207753Smm coder->sequence = SEQ_INIT; 259207753Smm break; 260207753Smm } 261207753Smm 262207753Smm return LZMA_OK; 263207753Smm} 264207753Smm 265207753Smm 266207753Smmstatic void 267312518Sdelphijlzma2_encoder_end(void *coder_ptr, const lzma_allocator *allocator) 268207753Smm{ 269312518Sdelphij lzma_lzma2_coder *coder = coder_ptr; 270207753Smm lzma_free(coder->lzma, allocator); 271207753Smm lzma_free(coder, allocator); 272207753Smm return; 273207753Smm} 274207753Smm 275207753Smm 276207753Smmstatic lzma_ret 277312518Sdelphijlzma2_encoder_options_update(void *coder_ptr, const lzma_filter *filter) 278207753Smm{ 279312518Sdelphij lzma_lzma2_coder *coder = coder_ptr; 280312518Sdelphij 281207753Smm // New options can be set only when there is no incomplete chunk. 282207753Smm // This is the case at the beginning of the raw stream and right 283207753Smm // after LZMA_SYNC_FLUSH. 284207753Smm if (filter->options == NULL || coder->sequence != SEQ_INIT) 285207753Smm return LZMA_PROG_ERROR; 286207753Smm 287207753Smm // Look if there are new options. At least for now, 288207753Smm // only lc/lp/pb can be changed. 289207753Smm const lzma_options_lzma *opt = filter->options; 290207753Smm if (coder->opt_cur.lc != opt->lc || coder->opt_cur.lp != opt->lp 291207753Smm || coder->opt_cur.pb != opt->pb) { 292207753Smm // Validate the options. 293207753Smm if (opt->lc > LZMA_LCLP_MAX || opt->lp > LZMA_LCLP_MAX 294207753Smm || opt->lc + opt->lp > LZMA_LCLP_MAX 295207753Smm || opt->pb > LZMA_PB_MAX) 296207753Smm return LZMA_OPTIONS_ERROR; 297207753Smm 298207753Smm // The new options will be used when the encoder starts 299207753Smm // a new LZMA2 chunk. 300207753Smm coder->opt_cur.lc = opt->lc; 301207753Smm coder->opt_cur.lp = opt->lp; 302207753Smm coder->opt_cur.pb = opt->pb; 303207753Smm coder->need_properties = true; 304207753Smm coder->need_state_reset = true; 305207753Smm } 306207753Smm 307207753Smm return LZMA_OK; 308207753Smm} 309207753Smm 310207753Smm 311207753Smmstatic lzma_ret 312292588Sdelphijlzma2_encoder_init(lzma_lz_encoder *lz, const lzma_allocator *allocator, 313207753Smm const void *options, lzma_lz_options *lz_options) 314207753Smm{ 315207753Smm if (options == NULL) 316207753Smm return LZMA_PROG_ERROR; 317207753Smm 318312518Sdelphij lzma_lzma2_coder *coder = lz->coder; 319312518Sdelphij if (coder == NULL) { 320312518Sdelphij coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator); 321312518Sdelphij if (coder == NULL) 322207753Smm return LZMA_MEM_ERROR; 323207753Smm 324312518Sdelphij lz->coder = coder; 325207753Smm lz->code = &lzma2_encode; 326207753Smm lz->end = &lzma2_encoder_end; 327207753Smm lz->options_update = &lzma2_encoder_options_update; 328207753Smm 329312518Sdelphij coder->lzma = NULL; 330207753Smm } 331207753Smm 332312518Sdelphij coder->opt_cur = *(const lzma_options_lzma *)(options); 333207753Smm 334312518Sdelphij coder->sequence = SEQ_INIT; 335312518Sdelphij coder->need_properties = true; 336312518Sdelphij coder->need_state_reset = false; 337312518Sdelphij coder->need_dictionary_reset 338312518Sdelphij = coder->opt_cur.preset_dict == NULL 339312518Sdelphij || coder->opt_cur.preset_dict_size == 0; 340207753Smm 341207753Smm // Initialize LZMA encoder 342312518Sdelphij return_if_error(lzma_lzma_encoder_create(&coder->lzma, allocator, 343312518Sdelphij &coder->opt_cur, lz_options)); 344207753Smm 345207753Smm // Make sure that we will always have enough history available in 346207753Smm // case we need to use uncompressed chunks. They are used when the 347207753Smm // compressed size of a chunk is not smaller than the uncompressed 348207753Smm // size, so we need to have at least LZMA2_COMPRESSED_MAX bytes 349207753Smm // history available. 350207753Smm if (lz_options->before_size + lz_options->dict_size < LZMA2_CHUNK_MAX) 351207753Smm lz_options->before_size 352207753Smm = LZMA2_CHUNK_MAX - lz_options->dict_size; 353207753Smm 354207753Smm return LZMA_OK; 355207753Smm} 356207753Smm 357207753Smm 358207753Smmextern lzma_ret 359292588Sdelphijlzma_lzma2_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 360207753Smm const lzma_filter_info *filters) 361207753Smm{ 362207753Smm return lzma_lz_encoder_init( 363207753Smm next, allocator, filters, &lzma2_encoder_init); 364207753Smm} 365207753Smm 366207753Smm 367207753Smmextern uint64_t 368207753Smmlzma_lzma2_encoder_memusage(const void *options) 369207753Smm{ 370207753Smm const uint64_t lzma_mem = lzma_lzma_encoder_memusage(options); 371207753Smm if (lzma_mem == UINT64_MAX) 372207753Smm return UINT64_MAX; 373207753Smm 374312518Sdelphij return sizeof(lzma_lzma2_coder) + lzma_mem; 375207753Smm} 376207753Smm 377207753Smm 378207753Smmextern lzma_ret 379207753Smmlzma_lzma2_props_encode(const void *options, uint8_t *out) 380207753Smm{ 381207753Smm const lzma_options_lzma *const opt = options; 382213700Smm uint32_t d = my_max(opt->dict_size, LZMA_DICT_SIZE_MIN); 383207753Smm 384223935Smm // Round up to the next 2^n - 1 or 2^n + 2^(n - 1) - 1 depending 385207753Smm // on which one is the next: 386207753Smm --d; 387207753Smm d |= d >> 2; 388207753Smm d |= d >> 3; 389207753Smm d |= d >> 4; 390207753Smm d |= d >> 8; 391207753Smm d |= d >> 16; 392207753Smm 393207753Smm // Get the highest two bits using the proper encoding: 394207753Smm if (d == UINT32_MAX) 395207753Smm out[0] = 40; 396207753Smm else 397292588Sdelphij out[0] = get_dist_slot(d + 1) - 24; 398207753Smm 399207753Smm return LZMA_OK; 400207753Smm} 401292588Sdelphij 402292588Sdelphij 403292588Sdelphijextern uint64_t 404292588Sdelphijlzma_lzma2_block_size(const void *options) 405292588Sdelphij{ 406292588Sdelphij const lzma_options_lzma *const opt = options; 407292588Sdelphij 408292588Sdelphij // Use at least 1 MiB to keep compression ratio better. 409292588Sdelphij return my_max((uint64_t)(opt->dict_size) * 3, UINT64_C(1) << 20); 410292588Sdelphij} 411