X-Git-Url: https://wimlib.net/git/?p=wimlib;a=blobdiff_plain;f=src%2Flzms_compress.c;h=ef67edb213f79fa2c1bf2b1057568a28e93d7fa5;hp=88f39b300a9a16458451de80b5bf8729284c2f76;hb=de58d5f57732df8129fbfd71d46ae5968ac59646;hpb=c2e4e0f6e5ab9369704d4d0727cf84a69dc31da8 diff --git a/src/lzms_compress.c b/src/lzms_compress.c index 88f39b30..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 @@ -328,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 */ @@ -587,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); } /****************************************************************************** @@ -982,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 @@ -1023,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); } @@ -1127,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 @@ -1187,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 @@ -1210,7 +1203,7 @@ lzms_delta_hash(const u8 *p, const u32 pos, 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); @@ -1255,7 +1248,7 @@ lzms_delta_matchfinder_skip_bytes(struct lzms_compressor *c, 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); } @@ -1287,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 @@ -1380,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 { @@ -1442,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; @@ -1532,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 { @@ -1601,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)) @@ -1661,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; @@ -1719,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; @@ -1733,7 +1726,7 @@ begin: 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; @@ -1748,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)) != @@ -1760,7 +1753,7 @@ 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); @@ -1800,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; @@ -1858,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; @@ -1895,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]; @@ -1922,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; @@ -2023,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 @@ -2180,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;