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