From e58d736165f5348b0381043db8250e290eefc414 Mon Sep 17 00:00:00 2001 From: "Steinar H. Gunderson" Date: Fri, 29 Nov 2019 18:14:28 +0100 Subject: [PATCH] Add a faster compressor. --- compress_fast.cpp | 181 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 181 insertions(+) create mode 100644 compress_fast.cpp diff --git a/compress_fast.cpp b/compress_fast.cpp new file mode 100644 index 0000000..95a042e --- /dev/null +++ b/compress_fast.cpp @@ -0,0 +1,181 @@ +// See compress.cpp; this is a version that's much faster, but also _much_ worse +// (5% larger files or so). It's still not optimal by any means. +// +// Same copyright and license (GPLv3). + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace std; + +static uint16_t read16(const char *ptr) +{ + // We don't care about the endianness, so native is fine. + uint16_t result; + memcpy(&result, ptr, sizeof(result)); + return result; +} + +static uint32_t read24(const char *ptr) +{ + // We don't care about the endianness, so native is fine. + uint32_t result = 0; + memcpy(&result, ptr, 3); + return result; +} + +static int find_match_length(const char *s1, const char *s2, int max_length) +{ + int length = 0; + while (length < max_length && *s1++ == *s2++) { + ++length; + } + return length; +} + +enum TagType { NOT_SET, LONG_MATCH, SHORT_MATCH, ONE_BYTE_LITERAL, LONG_LITERAL }; // EOF is handled separately. + +struct Output { + string data; + int control_bits_used = 8; + string::size_type control_byte_pos = string::npos; + + void emit_control_bit(int bit); + void emit_literal(const char *ptr, int length); + void emit_literal_internal(const char *ptr, int length); + void emit_match(int length, int distance); + void emit_eof(); +}; + +void Output::emit_control_bit(int bit) +{ + if (control_bits_used == 8) { + // We need to output a new control byte for the next eight tags. + data.push_back('\0'); + control_bits_used = 0; + control_byte_pos = data.size() - 1; + } + data[control_byte_pos] |= (bit << control_bits_used); + ++control_bits_used; +} + +void Output::emit_literal(const char *ptr, int length) +{ + while (length > 0) { + int ll = min(length, 70); + emit_literal_internal(ptr, ll); + ptr += ll; + length -= ll; + } +} + +void Output::emit_literal_internal(const char *ptr, int length) +{ + assert(length <= 70); + if (length <= 8) { + for (int i = 0; i < length; ++i) { + emit_control_bit(0); + data.push_back(*ptr++); + } + } else { + emit_control_bit(1); + data.push_back(0xc0 | (length - 8)); + data.insert(data.end(), ptr, ptr + length); + } +} + +void Output::emit_match(int length, int distance) +{ + if (length <= 5 && distance <= 16) { + // Short match. + emit_control_bit(1); + data.push_back(0x80 | ((length - 2) << 4) | (distance - 1)); + } else { + // Long match. + assert(length >= 3 && length <= 34 && distance <= 1023); + emit_control_bit(1); + data.push_back(((length - 3) << 2) | (distance >> 8)); + data.push_back(distance & 0xff); + } +} + +void Output::emit_eof() +{ + emit_control_bit(1); + data.push_back(0xff); +} + +string compress_konamilz77(const string &input) +{ + unordered_map match_to_pos; + + Output output; + int unemitted_literal_bytes = 0; + for (int pos = 0; pos < int(input.size()); ++pos) { + int bytes_left = input.size() - pos; + + if (bytes_left < 3) { + // Can't start a match here. + ++unemitted_literal_bytes; + continue; + } + + // See if we can find a short match. + int best_match_length = 0; + int best_match_distance = -1; + uint16_t val16 = read16(&input[pos]); + for (int distance = 1; distance <= min(pos, 16); ++distance) { + if (read16(&input[pos - distance]) == val16) { + // A 2-byte match; see if we can extend it. + int match_length = 2 + find_match_length(&input[pos] + 2, &input[pos - distance] + 2, std::min(bytes_left, 34) - 2); + if (match_length > best_match_length) { + best_match_length = match_length; // Note: Could now be a long match. + best_match_distance = distance; + } + } + } + + uint32_t val24 = read24(&input[pos]); + const auto match_it = match_to_pos.find(val24); + if (match_it != match_to_pos.end()) { + int distance = pos - match_it->second; + if (distance <= 1023) { + // A 3-byte match; see if we can extend it. + int match_length = 3 + find_match_length(&input[pos] + 3, &input[pos - distance] + 3, std::min(bytes_left, 34) - 3); + if (match_length > best_match_length) { + best_match_length = match_length; + best_match_distance = distance; + } + } + } + match_to_pos[val24] = pos; + + if (best_match_length == 0) { + ++unemitted_literal_bytes; + } else { + // We have a match! First, output the pending literal if there's any. + if (unemitted_literal_bytes > 0) { + output.emit_literal(&input[pos - unemitted_literal_bytes], unemitted_literal_bytes); + unemitted_literal_bytes = 0; + } + output.emit_match(best_match_length, best_match_distance); + pos += best_match_length - 1; + } + } + + // Output the final literal, if any. + if (unemitted_literal_bytes > 0) { + output.emit_literal(&input[input.size() - unemitted_literal_bytes], unemitted_literal_bytes); + } + output.emit_eof(); + + return output.data; +} -- 2.39.5