1 /////////////////////////////////////////////////////////////////////////////// 2 // 3 /// \file lzma2_encoder.c 4 /// \brief LZMA2 encoder 5 /// 6 // Authors: Igor Pavlov 7 // Lasse Collin 8 // 9 // This file has been put into the public domain. 10 // You can do whatever you want with this file. 11 // 12 /////////////////////////////////////////////////////////////////////////////// 13 14 #include "lz_encoder.h" 15 #include "lzma_encoder.h" 16 #include "fastpos.h" 17 #include "lzma2_encoder.h" 18 19 20 typedef struct { 21 enum { 22 SEQ_INIT, 23 SEQ_LZMA_ENCODE, 24 SEQ_LZMA_COPY, 25 SEQ_UNCOMPRESSED_HEADER, 26 SEQ_UNCOMPRESSED_COPY, 27 } sequence; 28 29 /// LZMA encoder 30 void *lzma; 31 32 /// LZMA options currently in use. 33 lzma_options_lzma opt_cur; 34 35 bool need_properties; 36 bool need_state_reset; 37 bool need_dictionary_reset; 38 39 /// Uncompressed size of a chunk 40 size_t uncompressed_size; 41 42 /// Compressed size of a chunk (excluding headers); this is also used 43 /// to indicate the end of buf[] in SEQ_LZMA_COPY. 44 size_t compressed_size; 45 46 /// Read position in buf[] 47 size_t buf_pos; 48 49 /// Buffer to hold the chunk header and LZMA compressed data 50 uint8_t buf[LZMA2_HEADER_MAX + LZMA2_CHUNK_MAX]; 51 } lzma_lzma2_coder; 52 53 54 static void 55 lzma2_header_lzma(lzma_lzma2_coder *coder) 56 { 57 assert(coder->uncompressed_size > 0); 58 assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX); 59 assert(coder->compressed_size > 0); 60 assert(coder->compressed_size <= LZMA2_CHUNK_MAX); 61 62 size_t pos; 63 64 if (coder->need_properties) { 65 pos = 0; 66 67 if (coder->need_dictionary_reset) 68 coder->buf[pos] = 0x80 + (3 << 5); 69 else 70 coder->buf[pos] = 0x80 + (2 << 5); 71 } else { 72 pos = 1; 73 74 if (coder->need_state_reset) 75 coder->buf[pos] = 0x80 + (1 << 5); 76 else 77 coder->buf[pos] = 0x80; 78 } 79 80 // Set the start position for copying. 81 coder->buf_pos = pos; 82 83 // Uncompressed size 84 size_t size = coder->uncompressed_size - 1; 85 coder->buf[pos++] += size >> 16; 86 coder->buf[pos++] = (size >> 8) & 0xFF; 87 coder->buf[pos++] = size & 0xFF; 88 89 // Compressed size 90 size = coder->compressed_size - 1; 91 coder->buf[pos++] = size >> 8; 92 coder->buf[pos++] = size & 0xFF; 93 94 // Properties, if needed 95 if (coder->need_properties) 96 lzma_lzma_lclppb_encode(&coder->opt_cur, coder->buf + pos); 97 98 coder->need_properties = false; 99 coder->need_state_reset = false; 100 coder->need_dictionary_reset = false; 101 102 // The copying code uses coder->compressed_size to indicate the end 103 // of coder->buf[], so we need add the maximum size of the header here. 104 coder->compressed_size += LZMA2_HEADER_MAX; 105 106 return; 107 } 108 109 110 static void 111 lzma2_header_uncompressed(lzma_lzma2_coder *coder) 112 { 113 assert(coder->uncompressed_size > 0); 114 assert(coder->uncompressed_size <= LZMA2_CHUNK_MAX); 115 116 // If this is the first chunk, we need to include dictionary 117 // reset indicator. 118 if (coder->need_dictionary_reset) 119 coder->buf[0] = 1; 120 else 121 coder->buf[0] = 2; 122 123 coder->need_dictionary_reset = false; 124 125 // "Compressed" size 126 coder->buf[1] = (coder->uncompressed_size - 1) >> 8; 127 coder->buf[2] = (coder->uncompressed_size - 1) & 0xFF; 128 129 // Set the start position for copying. 130 coder->buf_pos = 0; 131 return; 132 } 133 134 135 static lzma_ret 136 lzma2_encode(void *coder_ptr, lzma_mf *restrict mf, 137 uint8_t *restrict out, size_t *restrict out_pos, 138 size_t out_size) 139 { 140 lzma_lzma2_coder *restrict coder = coder_ptr; 141 142 while (*out_pos < out_size) 143 switch (coder->sequence) { 144 case SEQ_INIT: 145 // If there's no input left and we are flushing or finishing, 146 // don't start a new chunk. 147 if (mf_unencoded(mf) == 0) { 148 // Write end of payload marker if finishing. 149 if (mf->action == LZMA_FINISH) 150 out[(*out_pos)++] = 0; 151 152 return mf->action == LZMA_RUN 153 ? LZMA_OK : LZMA_STREAM_END; 154 } 155 156 if (coder->need_state_reset) 157 return_if_error(lzma_lzma_encoder_reset( 158 coder->lzma, &coder->opt_cur)); 159 160 coder->uncompressed_size = 0; 161 coder->compressed_size = 0; 162 coder->sequence = SEQ_LZMA_ENCODE; 163 164 // Fall through 165 166 case SEQ_LZMA_ENCODE: { 167 // Calculate how much more uncompressed data this chunk 168 // could accept. 169 const uint32_t left = LZMA2_UNCOMPRESSED_MAX 170 - coder->uncompressed_size; 171 uint32_t limit; 172 173 if (left < mf->match_len_max) { 174 // Must flush immediately since the next LZMA symbol 175 // could make the uncompressed size of the chunk too 176 // big. 177 limit = 0; 178 } else { 179 // Calculate maximum read_limit that is OK from point 180 // of view of LZMA2 chunk size. 181 limit = mf->read_pos - mf->read_ahead 182 + left - mf->match_len_max; 183 } 184 185 // Save the start position so that we can update 186 // coder->uncompressed_size. 187 const uint32_t read_start = mf->read_pos - mf->read_ahead; 188 189 // Call the LZMA encoder until the chunk is finished. 190 const lzma_ret ret = lzma_lzma_encode(coder->lzma, mf, 191 coder->buf + LZMA2_HEADER_MAX, 192 &coder->compressed_size, 193 LZMA2_CHUNK_MAX, limit); 194 195 coder->uncompressed_size += mf->read_pos - mf->read_ahead 196 - read_start; 197 198 assert(coder->compressed_size <= LZMA2_CHUNK_MAX); 199 assert(coder->uncompressed_size <= LZMA2_UNCOMPRESSED_MAX); 200 201 if (ret != LZMA_STREAM_END) 202 return LZMA_OK; 203 204 // See if the chunk compressed. If it didn't, we encode it 205 // as uncompressed chunk. This saves a few bytes of space 206 // and makes decoding faster. 207 if (coder->compressed_size >= coder->uncompressed_size) { 208 coder->uncompressed_size += mf->read_ahead; 209 assert(coder->uncompressed_size 210 <= LZMA2_UNCOMPRESSED_MAX); 211 mf->read_ahead = 0; 212 lzma2_header_uncompressed(coder); 213 coder->need_state_reset = true; 214 coder->sequence = SEQ_UNCOMPRESSED_HEADER; 215 break; 216 } 217 218 // The chunk did compress at least by one byte, so we store 219 // the chunk as LZMA. 220 lzma2_header_lzma(coder); 221 222 coder->sequence = SEQ_LZMA_COPY; 223 } 224 225 // Fall through 226 227 case SEQ_LZMA_COPY: 228 // Copy the compressed chunk along its headers to the 229 // output buffer. 230 lzma_bufcpy(coder->buf, &coder->buf_pos, 231 coder->compressed_size, 232 out, out_pos, out_size); 233 if (coder->buf_pos != coder->compressed_size) 234 return LZMA_OK; 235 236 coder->sequence = SEQ_INIT; 237 break; 238 239 case SEQ_UNCOMPRESSED_HEADER: 240 // Copy the three-byte header to indicate uncompressed chunk. 241 lzma_bufcpy(coder->buf, &coder->buf_pos, 242 LZMA2_HEADER_UNCOMPRESSED, 243 out, out_pos, out_size); 244 if (coder->buf_pos != LZMA2_HEADER_UNCOMPRESSED) 245 return LZMA_OK; 246 247 coder->sequence = SEQ_UNCOMPRESSED_COPY; 248 249 // Fall through 250 251 case SEQ_UNCOMPRESSED_COPY: 252 // Copy the uncompressed data as is from the dictionary 253 // to the output buffer. 254 mf_read(mf, out, out_pos, out_size, &coder->uncompressed_size); 255 if (coder->uncompressed_size != 0) 256 return LZMA_OK; 257 258 coder->sequence = SEQ_INIT; 259 break; 260 } 261 262 return LZMA_OK; 263 } 264 265 266 static void 267 lzma2_encoder_end(void *coder_ptr, const lzma_allocator *allocator) 268 { 269 lzma_lzma2_coder *coder = coder_ptr; 270 lzma_free(coder->lzma, allocator); 271 lzma_free(coder, allocator); 272 return; 273 } 274 275 276 static lzma_ret 277 lzma2_encoder_options_update(void *coder_ptr, const lzma_filter *filter) 278 { 279 lzma_lzma2_coder *coder = coder_ptr; 280 281 // New options can be set only when there is no incomplete chunk. 282 // This is the case at the beginning of the raw stream and right 283 // after LZMA_SYNC_FLUSH. 284 if (filter->options == NULL || coder->sequence != SEQ_INIT) 285 return LZMA_PROG_ERROR; 286 287 // Look if there are new options. At least for now, 288 // only lc/lp/pb can be changed. 289 const lzma_options_lzma *opt = filter->options; 290 if (coder->opt_cur.lc != opt->lc || coder->opt_cur.lp != opt->lp 291 || coder->opt_cur.pb != opt->pb) { 292 // Validate the options. 293 if (opt->lc > LZMA_LCLP_MAX || opt->lp > LZMA_LCLP_MAX 294 || opt->lc + opt->lp > LZMA_LCLP_MAX 295 || opt->pb > LZMA_PB_MAX) 296 return LZMA_OPTIONS_ERROR; 297 298 // The new options will be used when the encoder starts 299 // a new LZMA2 chunk. 300 coder->opt_cur.lc = opt->lc; 301 coder->opt_cur.lp = opt->lp; 302 coder->opt_cur.pb = opt->pb; 303 coder->need_properties = true; 304 coder->need_state_reset = true; 305 } 306 307 return LZMA_OK; 308 } 309 310 311 static lzma_ret 312 lzma2_encoder_init(lzma_lz_encoder *lz, const lzma_allocator *allocator, 313 lzma_vli id lzma_attribute((__unused__)), const void *options, 314 lzma_lz_options *lz_options) 315 { 316 if (options == NULL) 317 return LZMA_PROG_ERROR; 318 319 lzma_lzma2_coder *coder = lz->coder; 320 if (coder == NULL) { 321 coder = lzma_alloc(sizeof(lzma_lzma2_coder), allocator); 322 if (coder == NULL) 323 return LZMA_MEM_ERROR; 324 325 lz->coder = coder; 326 lz->code = &lzma2_encode; 327 lz->end = &lzma2_encoder_end; 328 lz->options_update = &lzma2_encoder_options_update; 329 330 coder->lzma = NULL; 331 } 332 333 coder->opt_cur = *(const lzma_options_lzma *)(options); 334 335 coder->sequence = SEQ_INIT; 336 coder->need_properties = true; 337 coder->need_state_reset = false; 338 coder->need_dictionary_reset 339 = coder->opt_cur.preset_dict == NULL 340 || coder->opt_cur.preset_dict_size == 0; 341 342 // Initialize LZMA encoder 343 return_if_error(lzma_lzma_encoder_create(&coder->lzma, allocator, 344 LZMA_FILTER_LZMA2, &coder->opt_cur, lz_options)); 345 346 // Make sure that we will always have enough history available in 347 // case we need to use uncompressed chunks. They are used when the 348 // compressed size of a chunk is not smaller than the uncompressed 349 // size, so we need to have at least LZMA2_COMPRESSED_MAX bytes 350 // history available. 351 if (lz_options->before_size + lz_options->dict_size < LZMA2_CHUNK_MAX) 352 lz_options->before_size 353 = LZMA2_CHUNK_MAX - lz_options->dict_size; 354 355 return LZMA_OK; 356 } 357 358 359 extern lzma_ret 360 lzma_lzma2_encoder_init(lzma_next_coder *next, const lzma_allocator *allocator, 361 const lzma_filter_info *filters) 362 { 363 return lzma_lz_encoder_init( 364 next, allocator, filters, &lzma2_encoder_init); 365 } 366 367 368 extern uint64_t 369 lzma_lzma2_encoder_memusage(const void *options) 370 { 371 const uint64_t lzma_mem = lzma_lzma_encoder_memusage(options); 372 if (lzma_mem == UINT64_MAX) 373 return UINT64_MAX; 374 375 return sizeof(lzma_lzma2_coder) + lzma_mem; 376 } 377 378 379 extern lzma_ret 380 lzma_lzma2_props_encode(const void *options, uint8_t *out) 381 { 382 if (options == NULL) 383 return LZMA_PROG_ERROR; 384 385 const lzma_options_lzma *const opt = options; 386 uint32_t d = my_max(opt->dict_size, LZMA_DICT_SIZE_MIN); 387 388 // Round up to the next 2^n - 1 or 2^n + 2^(n - 1) - 1 depending 389 // on which one is the next: 390 --d; 391 d |= d >> 2; 392 d |= d >> 3; 393 d |= d >> 4; 394 d |= d >> 8; 395 d |= d >> 16; 396 397 // Get the highest two bits using the proper encoding: 398 if (d == UINT32_MAX) 399 out[0] = 40; 400 else 401 out[0] = get_dist_slot(d + 1) - 24; 402 403 return LZMA_OK; 404 } 405 406 407 extern uint64_t 408 lzma_lzma2_block_size(const void *options) 409 { 410 const lzma_options_lzma *const opt = options; 411 412 if (!IS_ENC_DICT_SIZE_VALID(opt->dict_size)) 413 return UINT64_MAX; 414 415 // Use at least 1 MiB to keep compression ratio better. 416 return my_max((uint64_t)(opt->dict_size) * 3, UINT64_C(1) << 20); 417 } 418