X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=src%2Flzms_compress.c;h=ef67edb213f79fa2c1bf2b1057568a28e93d7fa5;hb=de58d5f57732df8129fbfd71d46ae5968ac59646;hp=caa93130c75ca44f656a1d8464621985d6eb3bd1;hpb=dadccd777e56b473128d87e485fcf8565b8cb93b;p=wimlib diff --git a/src/lzms_compress.c b/src/lzms_compress.c index caa93130..ef67edb2 100644 --- a/src/lzms_compress.c +++ b/src/lzms_compress.c @@ -173,7 +173,7 @@ struct lzms_item { static inline void check_that_powers_fit_in_bitfield(void) { - BUILD_BUG_ON(LZMS_NUM_DELTA_POWER_SYMS > (1 << (31 - DELTA_SOURCE_POWER_SHIFT))); + STATIC_ASSERT(LZMS_NUM_DELTA_POWER_SYMS <= (1 << (31 - DELTA_SOURCE_POWER_SHIFT))); } /* A stripped-down version of the adaptive state in LZMS which excludes the @@ -307,7 +307,8 @@ struct lzms_compressor { u32 next_delta_hashes[NUM_POWERS_TO_CONSIDER]; /* The per-byte graph nodes for near-optimal parsing */ - struct lzms_optimum_node optimum_nodes[NUM_OPTIM_NODES + MAX_FAST_LENGTH]; + struct lzms_optimum_node optimum_nodes[NUM_OPTIM_NODES + MAX_FAST_LENGTH + + 1 + MAX_FAST_LENGTH]; /* Table: length => current cost for small match lengths */ u32 fast_length_cost_tab[MAX_FAST_LENGTH + 1]; @@ -327,14 +328,7 @@ struct lzms_compressor { unsigned lz_rep_states[LZMS_NUM_LZ_REP_DECISIONS]; unsigned delta_state; unsigned delta_rep_states[LZMS_NUM_DELTA_REP_DECISIONS]; - struct lzms_probability_entry main_probs[LZMS_NUM_MAIN_PROBS]; - struct lzms_probability_entry match_probs[LZMS_NUM_MATCH_PROBS]; - struct lzms_probability_entry lz_probs[LZMS_NUM_LZ_PROBS]; - struct lzms_probability_entry lz_rep_probs[LZMS_NUM_LZ_REP_DECISIONS] - [LZMS_NUM_LZ_REP_PROBS]; - struct lzms_probability_entry delta_probs[LZMS_NUM_DELTA_PROBS]; - struct lzms_probability_entry delta_rep_probs[LZMS_NUM_DELTA_REP_DECISIONS] - [LZMS_NUM_DELTA_REP_PROBS]; + struct lzms_probabilites probs; /* Huffman codes */ @@ -586,42 +580,42 @@ static void lzms_encode_main_bit(struct lzms_compressor *c, int bit) { lzms_encode_bit(bit, &c->main_state, LZMS_NUM_MAIN_PROBS, - c->main_probs, &c->rc); + c->probs.main, &c->rc); } static void lzms_encode_match_bit(struct lzms_compressor *c, int bit) { lzms_encode_bit(bit, &c->match_state, LZMS_NUM_MATCH_PROBS, - c->match_probs, &c->rc); + c->probs.match, &c->rc); } static void lzms_encode_lz_bit(struct lzms_compressor *c, int bit) { lzms_encode_bit(bit, &c->lz_state, LZMS_NUM_LZ_PROBS, - c->lz_probs, &c->rc); + c->probs.lz, &c->rc); } static void lzms_encode_lz_rep_bit(struct lzms_compressor *c, int bit, int idx) { lzms_encode_bit(bit, &c->lz_rep_states[idx], LZMS_NUM_LZ_REP_PROBS, - c->lz_rep_probs[idx], &c->rc); + c->probs.lz_rep[idx], &c->rc); } static void lzms_encode_delta_bit(struct lzms_compressor *c, int bit) { lzms_encode_bit(bit, &c->delta_state, LZMS_NUM_DELTA_PROBS, - c->delta_probs, &c->rc); + c->probs.delta, &c->rc); } static void lzms_encode_delta_rep_bit(struct lzms_compressor *c, int bit, int idx) { lzms_encode_bit(bit, &c->delta_rep_states[idx], LZMS_NUM_DELTA_REP_PROBS, - c->delta_rep_probs[idx], &c->rc); + c->probs.delta_rep[idx], &c->rc); } /****************************************************************************** @@ -946,7 +940,7 @@ lzms_encode_item_list(struct lzms_compressor *c, } /****************************************************************************** - * Cost evalution * + * Cost evaluation * ******************************************************************************/ /* @@ -981,7 +975,7 @@ static inline void check_cost_shift(void) { /* lzms_bit_costs is hard-coded to the current COST_SHIFT. */ - BUILD_BUG_ON(COST_SHIFT != 6); + STATIC_ASSERT(COST_SHIFT == 6); } #if 0 @@ -1022,7 +1016,7 @@ lzms_bit_1_cost(unsigned state, const struct lzms_probability_entry *probs) static inline u32 lzms_literal_cost(struct lzms_compressor *c, unsigned main_state, unsigned literal) { - return lzms_bit_0_cost(main_state, c->main_probs) + + return lzms_bit_0_cost(main_state, c->probs.main) + ((u32)c->literal_lens[literal] << COST_SHIFT); } @@ -1126,7 +1120,7 @@ lzms_update_lru_queues(struct lzms_adaptive_state *state) static inline void lzms_update_state(u8 *state_p, int bit, unsigned num_states) { - *state_p = ((*state_p << 1) | bit) % num_states; + *state_p = ((*state_p << 1) | bit) & (num_states - 1); } static inline void @@ -1186,7 +1180,7 @@ static void lzms_init_delta_matchfinder(struct lzms_compressor *c) { /* Set all entries to use an invalid power, which will never match. */ - BUILD_BUG_ON(NUM_POWERS_TO_CONSIDER >= (1 << (32 - DELTA_SOURCE_POWER_SHIFT))); + STATIC_ASSERT(NUM_POWERS_TO_CONSIDER < (1 << (32 - DELTA_SOURCE_POWER_SHIFT))); memset(c->delta_hash_table, 0xFF, sizeof(c->delta_hash_table)); /* Initialize the next hash code for each power. We can just use zeroes @@ -1201,7 +1195,7 @@ lzms_init_delta_matchfinder(struct lzms_compressor *c) * delta context with the specified @span. */ static inline u32 -lzms_delta_hash(const u8 *p, u32 span) +lzms_delta_hash(const u8 *p, const u32 pos, u32 span) { /* A delta match has a certain span and an offset that is a multiple of * that span. To reduce wasted space we use a single combined hash @@ -1209,11 +1203,11 @@ lzms_delta_hash(const u8 *p, u32 span) * include in the hash code computation the span and the low-order bits * of the current position. */ - BUILD_BUG_ON(NBYTES_HASHED_FOR_DELTA != 3); + STATIC_ASSERT(NBYTES_HASHED_FOR_DELTA == 3); u8 d0 = *(p + 0) - *(p + 0 - span); u8 d1 = *(p + 1) - *(p + 1 - span); u8 d2 = *(p + 2) - *(p + 2 - span); - u32 v = ((span + ((u32)(uintptr_t)p & (span - 1))) << 24) | + u32 v = ((span + (pos & (span - 1))) << 24) | ((u32)d2 << 16) | ((u32)d1 << 8) | d0; return lz_hash(v, DELTA_HASH_ORDER); } @@ -1249,12 +1243,12 @@ lzms_delta_matchfinder_skip_bytes(struct lzms_compressor *c, const u32 span = (u32)1 << power; if (unlikely(pos < span)) continue; - const u32 next_hash = lzms_delta_hash(in_next + 1, span); + const u32 next_hash = lzms_delta_hash(in_next + 1, pos + 1, span); const u32 hash = c->next_delta_hashes[power]; c->delta_hash_table[hash] = (power << DELTA_SOURCE_POWER_SHIFT) | pos; c->next_delta_hashes[power] = next_hash; - prefetch(&c->delta_hash_table[next_hash]); + prefetchw(&c->delta_hash_table[next_hash]); } } while (in_next++, pos++, --count); } @@ -1286,10 +1280,10 @@ lzms_skip_bytes(struct lzms_compressor *c, u32 count, const u8 *in_next) * can be reached using a match or literal from the current position. This is * essentially Dijkstra's algorithm in disguise: the graph nodes are positions, * the graph edges are possible matches/literals to code, and the cost of each - * edge is the estimated number of bits that will be required to output the - * corresponding match or literal. But one difference is that we actually - * compute the lowest-cost path in pieces, where each piece is terminated when - * there are no choices to be made. + * edge is the estimated number of bits (scaled up by COST_SHIFT) that will be + * required to output the corresponding match or literal. But one difference is + * that we actually compute the lowest-cost path in pieces, where each piece is + * terminated when there are no choices to be made. * * The costs of literals and matches are estimated using the range encoder * states and the semi-adaptive Huffman codes. Except for range encoding @@ -1379,19 +1373,19 @@ begin: u32 base_cost = cur_node->cost + lzms_bit_1_cost(cur_node->state.main_state, - c->main_probs) + + c->probs.main) + lzms_bit_0_cost(cur_node->state.match_state, - c->match_probs) + + c->probs.match) + lzms_bit_1_cost(cur_node->state.lz_state, - c->lz_probs); + c->probs.lz); for (int i = 0; i < rep_idx; i++) base_cost += lzms_bit_1_cost(cur_node->state.lz_rep_states[i], - c->lz_rep_probs[i]); + c->probs.lz_rep[i]); if (rep_idx < LZMS_NUM_LZ_REP_DECISIONS) base_cost += lzms_bit_0_cost(cur_node->state.lz_rep_states[rep_idx], - c->lz_rep_probs[rep_idx]); + c->probs.lz_rep[rep_idx]); u32 len = 2; do { @@ -1441,10 +1435,10 @@ begin: main_state = ((main_state << 1) | 0) % LZMS_NUM_MAIN_PROBS; /* add LZ-rep0 cost */ - cost += lzms_bit_1_cost(main_state, c->main_probs) + - lzms_bit_0_cost(match_state, c->match_probs) + - lzms_bit_1_cost(lz_state, c->lz_probs) + - lzms_bit_0_cost(lz_rep0_state, c->lz_rep_probs[0]) + + cost += lzms_bit_1_cost(main_state, c->probs.main) + + lzms_bit_0_cost(match_state, c->probs.match) + + lzms_bit_1_cost(lz_state, c->probs.lz) + + lzms_bit_0_cost(lz_rep0_state, c->probs.lz_rep[0]) + lzms_fast_length_cost(c, rep0_len); const u32 total_len = rep_len + 1 + rep0_len; @@ -1531,19 +1525,19 @@ begin: u32 base_cost = cur_node->cost + lzms_bit_1_cost(cur_node->state.main_state, - c->main_probs) + + c->probs.main) + lzms_bit_1_cost(cur_node->state.match_state, - c->match_probs) + + c->probs.match) + lzms_bit_1_cost(cur_node->state.delta_state, - c->delta_probs); + c->probs.delta); for (int i = 0; i < rep_idx; i++) base_cost += lzms_bit_1_cost(cur_node->state.delta_rep_states[i], - c->delta_rep_probs[i]); + c->probs.delta_rep[i]); if (rep_idx < LZMS_NUM_DELTA_REP_DECISIONS) base_cost += lzms_bit_0_cost(cur_node->state.delta_rep_states[rep_idx], - c->delta_rep_probs[rep_idx]); + c->probs.delta_rep[rep_idx]); u32 len = 2; do { @@ -1600,11 +1594,11 @@ begin: u32 base_cost = cur_node->cost + lzms_bit_1_cost(cur_node->state.main_state, - c->main_probs) + + c->probs.main) + lzms_bit_0_cost(cur_node->state.match_state, - c->match_probs) + + c->probs.match) + lzms_bit_0_cost(cur_node->state.lz_state, - c->lz_probs); + c->probs.lz); if (c->try_lzmatch_lit_lzrep0 && likely(in_end - (in_next + c->matches[0].length) >= 3)) @@ -1660,11 +1654,11 @@ begin: main_state = ((main_state << 1) | 0) % LZMS_NUM_MAIN_PROBS; /* add LZ-rep0 cost */ - cost += lzms_bit_1_cost(main_state, c->main_probs) + - lzms_bit_0_cost(match_state, c->match_probs) + - lzms_bit_1_cost(lz_state, c->lz_probs) + + cost += lzms_bit_1_cost(main_state, c->probs.main) + + lzms_bit_0_cost(match_state, c->probs.match) + + lzms_bit_1_cost(lz_state, c->probs.lz) + lzms_bit_0_cost(cur_node->state.lz_rep_states[0], - c->lz_rep_probs[0]) + + c->probs.lz_rep[0]) + lzms_fast_length_cost(c, rep0_len); const u32 total_len = len + 1 + rep0_len; @@ -1718,7 +1712,7 @@ begin: const u32 pos = in_next - c->in_buffer; /* Consider each possible power (log2 of span) */ - BUILD_BUG_ON(NUM_POWERS_TO_CONSIDER > LZMS_NUM_DELTA_POWER_SYMS); + STATIC_ASSERT(NUM_POWERS_TO_CONSIDER <= LZMS_NUM_DELTA_POWER_SYMS); for (u32 power = 0; power < NUM_POWERS_TO_CONSIDER; power++) { const u32 span = (u32)1 << power; @@ -1726,13 +1720,13 @@ begin: if (unlikely(pos < span)) continue; - const u32 next_hash = lzms_delta_hash(in_next + 1, span); + const u32 next_hash = lzms_delta_hash(in_next + 1, pos + 1, span); const u32 hash = c->next_delta_hashes[power]; const u32 cur_match = c->delta_hash_table[hash]; c->delta_hash_table[hash] = (power << DELTA_SOURCE_POWER_SHIFT) | pos; c->next_delta_hashes[power] = next_hash; - prefetch(&c->delta_hash_table[next_hash]); + prefetchw(&c->delta_hash_table[next_hash]); if (power != cur_match >> DELTA_SOURCE_POWER_SHIFT) continue; @@ -1747,7 +1741,7 @@ begin: /* Check the first 3 bytes before entering the * extension loop. */ - BUILD_BUG_ON(NBYTES_HASHED_FOR_DELTA != 3); + STATIC_ASSERT(NBYTES_HASHED_FOR_DELTA == 3); if (((u8)(*(in_next + 0) - *(in_next + 0 - span)) != (u8)(*(matchptr + 0) - *(matchptr + 0 - span))) || ((u8)(*(in_next + 1) - *(in_next + 1 - span)) != @@ -1759,11 +1753,16 @@ begin: /* Extend the delta match to its full length. */ const u32 len = lzms_extend_delta_match(in_next, matchptr, - 3, + NBYTES_HASHED_FOR_DELTA, in_end - in_next, span); const u32 raw_offset = offset >> power; + + if (unlikely(raw_offset > DELTA_SOURCE_RAW_OFFSET_MASK - + (LZMS_NUM_DELTA_REPS - 1))) + continue; + const u32 pair = (power << DELTA_SOURCE_POWER_SHIFT) | raw_offset; const u32 source = DELTA_SOURCE_TAG | @@ -1794,11 +1793,11 @@ begin: u32 base_cost = cur_node->cost + lzms_bit_1_cost(cur_node->state.main_state, - c->main_probs) + + c->probs.main) + lzms_bit_1_cost(cur_node->state.match_state, - c->match_probs) + + c->probs.match) + lzms_bit_0_cost(cur_node->state.delta_state, - c->delta_probs) + + c->probs.delta) + lzms_delta_source_cost(c, power, raw_offset); u32 l = NBYTES_HASHED_FOR_DELTA; @@ -1852,13 +1851,13 @@ begin: /* Add cost of LZ-rep0 */ const u32 cost = cur_and_lit_cost + - lzms_bit_1_cost(main_state, c->main_probs) + + lzms_bit_1_cost(main_state, c->probs.main) + lzms_bit_0_cost(cur_node->state.match_state, - c->match_probs) + + c->probs.match) + lzms_bit_1_cost(cur_node->state.lz_state, - c->lz_probs) + + c->probs.lz) + lzms_bit_0_cost(cur_node->state.lz_rep_states[0], - c->lz_rep_probs[0]) + + c->probs.lz_rep[0]) + lzms_fast_length_cost(c, rep0_len); const u32 total_len = 1 + rep0_len; @@ -1889,7 +1888,7 @@ begin: * Finalize the adaptive state that results from taking this * lowest-cost path. */ struct lzms_item item_to_take = cur_node->item; - struct lzms_optimum_node *source_node = cur_node - (item_to_take.length); + struct lzms_optimum_node *source_node = cur_node - item_to_take.length; int next_item_idx = -1; for (unsigned i = 0; i < cur_node->num_extra_items; i++) { item_to_take = cur_node->extra_items[i]; @@ -1916,9 +1915,9 @@ begin: if (source >= LZMS_NUM_DELTA_REPS) { /* Explicit offset delta match */ - u32 pair = source - (LZMS_NUM_DELTA_REPS - 1); lzms_update_delta_state(&cur_node->state, 0); - cur_node->state.upcoming_delta_pair = pair; + cur_node->state.upcoming_delta_pair = + source - (LZMS_NUM_DELTA_REPS - 1); } else { /* Repeat offset delta match */ int rep_idx = source; @@ -2017,14 +2016,7 @@ lzms_init_states_and_probabilities(struct lzms_compressor *c) for (int i = 0; i < LZMS_NUM_DELTA_REP_DECISIONS; i++) c->delta_rep_states[i] = 0; - lzms_init_probability_entries(c->main_probs, LZMS_NUM_MAIN_PROBS); - lzms_init_probability_entries(c->match_probs, LZMS_NUM_MATCH_PROBS); - lzms_init_probability_entries(c->lz_probs, LZMS_NUM_LZ_PROBS); - for (int i = 0; i < LZMS_NUM_LZ_REP_DECISIONS; i++) - lzms_init_probability_entries(c->lz_rep_probs[i], LZMS_NUM_LZ_REP_PROBS); - lzms_init_probability_entries(c->delta_probs, LZMS_NUM_DELTA_PROBS); - for (int i = 0; i < LZMS_NUM_DELTA_REP_DECISIONS; i++) - lzms_init_probability_entries(c->delta_rep_probs[i], LZMS_NUM_DELTA_REP_PROBS); + lzms_init_probabilities(&c->probs); } static void @@ -2174,8 +2166,8 @@ oom0: } static size_t -lzms_compress(const void *in, size_t in_nbytes, - void *out, size_t out_nbytes_avail, void *_c) +lzms_compress(const void *restrict in, size_t in_nbytes, + void *restrict out, size_t out_nbytes_avail, void *restrict _c) { struct lzms_compressor *c = _c; size_t result;