Добавлена четвертая задача пятой главы

5 files changed, 556 insertions, 0 deletions

diff --git a/Занимательное программирование/5/4_sound/.gitignore b/Занимательное программирование/5/4_sound/.gitignore
new file mode 100644
index 0000000..2e9f768
--- /dev/null
+++ b/Занимательное программирование/5/4_sound/.gitignore
@@ -0,0 +1,3 @@
+.ninja_log
+build/
+*.wav
diff --git a/Занимательное программирование/5/4_sound/build.ninja b/Занимательное программирование/5/4_sound/build.ninja
new file mode 100644
index 0000000..10de752
--- /dev/null
+++ b/Занимательное программирование/5/4_sound/build.ninja
@@ -0,0 +1,12 @@
+cxxflags =
+
+rule cxx
+  command = g++ $cxxflags -c -o $out $in
+
+rule ld
+  command = g++ $cxxflags $in -o $out
+
+build build/huffman.o: cxx huffman.cpp | huffman.hpp
+build build/sound: ld main.cpp build/huffman.o
+
+default build/sound
diff --git a/Занимательное программирование/5/4_sound/huffman.cpp b/Занимательное программирование/5/4_sound/huffman.cpp
new file mode 100644
index 0000000..fef1974
--- /dev/null
+++ b/Занимательное программирование/5/4_sound/huffman.cpp
@@ -0,0 +1,315 @@
+#include <array>
+#include <cstdint>
+#include <iostream>
+#include <vector>
+#include <memory>
+#include <string>
+#include <algorithm>
+#include <bitset>
+#include "huffman.hpp"
+#include <arpa/inet.h>
+
+huffman_tree::huffman_tree(const std::string& value)
+    : _value(value), _left(nullptr), _right(nullptr)
+{
+}
+
+huffman_tree::huffman_tree(std::shared_ptr<huffman_tree> left, std::shared_ptr<huffman_tree> right)
+    : _value(""), _left(left), _right(right)
+{
+}
+
+std::uint8_t huffman_tree::value() const
+{
+    return _value.front();
+}
+
+std::shared_ptr<huffman_tree> huffman_tree::left() const
+{
+    return _left;
+}
+
+std::shared_ptr<huffman_tree> huffman_tree::right() const
+{
+    return _right;
+}
+
+bool huffman_tree::is_leaf() const
+{
+    return !(this->left() || this->right());
+}
+
+huffman_probability::huffman_probability(const std::string& bytes, double probability)
+        : bytes(bytes), probability(probability), tree(std::make_shared<huffman_tree>(bytes))
+    {
+    }
+
+huffman_probability huffman_probability::operator+(const huffman_probability& that) const
+{
+    huffman_probability result{ this->bytes + that.bytes, this->probability + that.probability };
+    result.tree = std::make_shared<huffman_tree>(this->tree, that.tree);
+
+    return result;
+}
+
+bool huffman_probability::operator<(const huffman_probability& that) const
+{
+    return this->probability < that.probability;
+}
+
+bool huffman_probability::operator>(const huffman_probability& that) const
+{
+    return this->probability > that.probability;
+}
+
+bool huffman_probability::operator<=(const huffman_probability& that) const
+{
+    return this->probability <= that.probability;
+}
+
+bool huffman_probability::operator>=(const huffman_probability& that) const
+{
+    return this->probability >= that.probability;
+}
+
+std::pair<std::bitset<8>, std::size_t> encode_coding(const coding& input, std::ostream& output,
+        std::bitset<8> bitset, std::size_t index)
+{
+    for (const bool bit: input)
+    {
+        bitset[index] = bit;
+
+        if (index == 7)
+        {
+            output.put(static_cast<std::ostream::char_type>(bitset.to_ulong()));
+            index = 0;
+            bitset = std::bitset<8>();
+        }
+        else
+        {
+            ++index;
+        }
+    }
+    return { bitset, index };
+}
+
+void huffman_table::create_table(std::shared_ptr<huffman_tree> tree, coding path)
+{
+    if (tree->is_leaf())
+    {
+        insert(tree->value(), std::move(path));
+    }
+    else
+    {
+        coding new_path;
+
+        new_path = path;
+        new_path.push_back(false);
+        create_table(tree->left(), std::move(new_path));
+
+        new_path = path;
+        new_path.push_back(true);
+        create_table(tree->right(), std::move(new_path));
+    }
+}
+
+huffman_table::huffman_table(std::shared_ptr<huffman_tree> tree)
+{
+    create_table(tree, coding());
+}
+
+huffman_table::huffman_table(std::vector<std::uint8_t>::const_iterator& coding_stream)
+{
+    std::size_t table_size = *coding_stream;
+
+    std::advance(coding_stream, 1);
+
+    for (std::uint8_t i = 0; i < table_size; ++i)
+    {
+        auto coded_symbol = static_cast<std::byte>(*coding_stream);
+
+        std::advance(coding_stream, 1);
+        std::uint8_t bits_in_coding = *coding_stream;
+
+        std::advance(coding_stream, 1);
+        coding current_coding;
+        std::size_t current_bit{ 0 };
+
+        for (std::uint8_t j = 0; j < bits_in_coding; ++j)
+        {
+            std::bitset<8> current_bitset{ *coding_stream };
+
+            current_coding.push_back(current_bitset[current_bit]);
+
+            if (current_bit == 7)
+            {
+                current_bit = 0;
+                std::advance(coding_stream, 1);
+            }
+            else
+            {
+                ++current_bit;
+            }
+        }
+        if (current_bit != 0)
+        {
+            std::advance(coding_stream, 1);
+        }
+        this->payload.insert({ coded_symbol, current_coding });
+    }
+}
+
+void huffman_table::insert(std::uint8_t byte, coding&& path)
+{
+    this->payload.insert({ static_cast<std::byte>(byte), std::move(path) });
+}
+
+const coding& huffman_table::operator[](std::uint8_t byte) const
+{
+    return this->payload.at(static_cast<std::byte>(byte));
+}
+
+std::size_t huffman_table::size() const
+{
+    return this->payload.size();
+}
+
+void huffman_table::encode(std::ostream& output) const
+{
+    // The first byte is the table size.
+    output.put(static_cast<std::ostream::char_type>(size()));
+
+    for (const std::pair<std::byte, coding>& entry: this->payload)
+    {
+        // For each entry write the byte encoded.
+        output.put(static_cast<std::ostream::char_type>(entry.first));
+        output.put(static_cast<std::ostream::char_type>(entry.second.size()));
+
+        auto rest = encode_coding(entry.second, output, {}, 0);
+        if (rest.second > 0)
+        {
+            output << static_cast<std::ostream::char_type>(rest.first.to_ulong());
+        }
+    }
+}
+
+std::unordered_map<std::byte, coding>::iterator huffman_table::begin()
+{
+    return this->payload.begin();
+}
+
+std::unordered_map<std::byte, coding>::iterator huffman_table::end()
+{
+    return this->payload.end();
+}
+
+std::unordered_map<std::byte, coding>::const_iterator huffman_table::begin() const
+{
+    return this->payload.cbegin();
+}
+
+std::unordered_map<std::byte, coding>::const_iterator huffman_table::end() const
+{
+    return this->payload.cend();
+}
+
+std::shared_ptr<huffman_tree> create_tree(probability_list& probabilities)
+{
+    while (probabilities.size() > 1)
+    {
+        std::sort(std::begin(probabilities), std::end(probabilities), std::greater());
+        auto last = probabilities.back();
+
+        probabilities.pop_back();
+        probabilities.back() = probabilities.back() + last;
+    }
+    return probabilities.front().tree;
+}
+
+probability_list adapt_probabilities(const std::vector<std::uint8_t>& input)
+{
+    std::array<std::size_t, 256> counts = {};
+    probability_list result;
+
+    for (auto byte: input)
+    {
+        ++counts[byte];
+    }
+    for (std::array<std::size_t, 256>::const_iterator count = std::cbegin(counts); count != std::cend(counts); ++count)
+    {
+        if (*count > 0)
+        {
+            result.push_back({
+                    std::string(1, static_cast<char>(std::distance(std::cbegin(counts), count))),
+                    *count / 256.0
+            });
+        }
+    }
+    return result;
+}
+
+void encode(const huffman_table& table, const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    std::pair<std::bitset<8>, std::size_t> rest{ {}, 0 };
+    auto input_size = htonl(input.size());
+
+    // Write the number of elements.
+    output.write(reinterpret_cast<const char *>(&input_size), 4);
+
+    table.encode(output);
+    for (const std::uint8_t character: input)
+    {
+        rest = encode_coding(table[character], output, rest.first, rest.second);
+    }
+    if (rest.second > 0)
+    {
+        output << static_cast<std::ostream::char_type>(rest.first.to_ulong());
+    }
+}
+
+void compress(const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    probability_list probabilities = adapt_probabilities(input);
+    std::shared_ptr<huffman_tree> tree = create_tree(probabilities);
+    huffman_table table{ tree };
+
+    encode(table, input, output);
+}
+
+void decompress(const std::vector<std::uint8_t>& input, std::ostream& output)
+{
+    auto input_size = ntohl(*reinterpret_cast<const std::uint32_t *>(input.data()));
+    auto table_iterator = std::cbegin(input) + 4;
+    huffman_table table{ table_iterator };
+    std::unordered_map<coding, std::byte> reverse_table;
+
+    for (auto entry: table)
+    {
+        reverse_table.insert({ entry.second, entry.first });
+    }
+    std::vector<bool> bit_input;
+    std::size_t element_count{ 0 };
+
+    while (table_iterator != std::cend(input))
+    {
+        std::bitset<8> current_bitset{ *table_iterator };
+
+        for (auto j = 0; j < current_bitset.size(); ++j)
+        {
+            bit_input.push_back(current_bitset[j]);
+            auto lookup_result = reverse_table.find(bit_input);
+
+            if (lookup_result != std::cend(reverse_table))
+            {
+                output << static_cast<unsigned char>(lookup_result->second);
+                bit_input.clear();
+                if (++element_count == input_size)
+                {
+                    break;
+                }
+            }
+        }
+
+        std::advance(table_iterator, 1);
+    }
+}
diff --git a/Занимательное программирование/5/4_sound/huffman.hpp b/Занимательное программирование/5/4_sound/huffman.hpp
new file mode 100644
index 0000000..6e297f0
--- /dev/null
+++ b/Занимательное программирование/5/4_sound/huffman.hpp
@@ -0,0 +1,69 @@
+#include <string>
+#include <memory>
+#include <vector>
+#include <unordered_map>
+#include <cstdint>
+
+class huffman_tree
+{
+    std::string _value;
+    std::shared_ptr<huffman_tree> _left;
+    std::shared_ptr<huffman_tree> _right;
+
+public:
+    huffman_tree(const std::string& value);
+    huffman_tree(std::shared_ptr<huffman_tree> left, std::shared_ptr<huffman_tree> right);
+
+    std::uint8_t value() const;
+    std::shared_ptr<huffman_tree> left() const;
+    std::shared_ptr<huffman_tree> right() const;
+
+    bool is_leaf() const;
+};
+
+struct huffman_probability
+{
+    std::string bytes;
+    double probability;
+    std::shared_ptr<huffman_tree> tree;
+
+    huffman_probability(const std::string& bytes, double probability);
+
+    huffman_probability operator+(const huffman_probability& that) const;
+    bool operator<(const huffman_probability& that) const;
+    bool operator>(const huffman_probability& that) const;
+    bool operator<=(const huffman_probability& that) const;
+    bool operator>=(const huffman_probability& that) const;
+};
+
+using coding = std::vector<bool>;
+using probability_list = std::vector<huffman_probability>;
+using probability_iterator = probability_list::iterator;
+using probability_const_iterator = probability_list::const_iterator;
+
+class huffman_table
+{
+    std::unordered_map<std::byte, coding> payload;
+
+    void create_table(std::shared_ptr<huffman_tree> tree, coding path);
+
+public:
+    huffman_table(std::shared_ptr<huffman_tree> tree);
+    huffman_table(std::vector<std::uint8_t>::const_iterator& coding_stream);
+    huffman_table() = default;
+
+    void insert(std::uint8_t byte, coding&& path);
+    void encode(std::ostream& output) const;
+    std::size_t size() const;
+    std::unordered_map<std::byte, coding>::iterator begin();
+    std::unordered_map<std::byte, coding>::iterator end();
+    std::unordered_map<std::byte, coding>::const_iterator begin() const;
+    std::unordered_map<std::byte, coding>::const_iterator end() const;
+
+    const coding& operator[](std::uint8_t byte) const;
+};
+
+std::shared_ptr<huffman_tree> create_tree(probability_list& probabilities);
+probability_list adapt_probabilities(const std::vector<std::uint8_t>& input);
+void compress(const std::vector<std::uint8_t>& input, std::ostream& output);
+void decompress(const std::vector<std::uint8_t>& input, std::ostream& output);
diff --git a/Занимательное программирование/5/4_sound/main.cpp b/Занимательное программирование/5/4_sound/main.cpp
new file mode 100644
index 0000000..b12bdae
--- /dev/null
+++ b/Занимательное программирование/5/4_sound/main.cpp
@@ -0,0 +1,157 @@
+#include <iostream>
+#include <fstream>
+#include <cstring>
+#include <array>
+#include <list>
+#include <vector>
+#include <cstdint>
+#include <sstream>
+#include "huffman.hpp"
+
+int show_usage()
+{
+    std::cerr << "Usage: sound (compress|decompress) input_file output_file." << std::endl;
+    return 1;
+}
+
+std::array<char, 44> read_header(std::ifstream& input_file)
+{
+    std::array<char, 44> wav_header;
+
+    input_file.read(wav_header.data(), wav_header.size());
+
+    return wav_header;
+}
+
+std::list<char> read_first_context(std::istreambuf_iterator<char>& input_iterator)
+{
+    std::list<char> result;
+
+    result.push_back(*input_iterator);
+    ++input_iterator;
+    result.push_back(*input_iterator);
+    ++input_iterator;
+
+    return result;
+}
+
+int fc(const std::list<char>& context)
+{
+    auto c1 = context.front();
+    auto c2 = context.back();
+
+    return c1 + (c1 - c2);
+}
+
+int archive(const char *input_name, const char *output_name)
+{
+    std::ifstream input_file{ input_name, std::ios::binary | std::ios::in };
+    input_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    std::array<char, 44> wav_header = read_header(input_file);
+
+    if (input_file.gcount() != 44)
+    {
+        // Not enough bytes available to read the header.
+        return 2;
+    }
+    std::istreambuf_iterator<char> wav_iterator(input_file), input_end;
+    std::list<char> context = read_first_context(wav_iterator);
+
+    std::ofstream output_file{ output_name, std::ios::binary | std::ios::trunc | std::ios::in };
+    output_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    output_file.write(wav_header.data(), wav_header.size());
+    output_file.write(&context.front(), 1);
+    output_file.write(&context.back(), 1);
+
+    std::vector<std::uint8_t> encoding;
+
+    while (wav_iterator != input_end)
+    {
+        int guess = fc(context);
+        int error = *wav_iterator - guess;
+
+        // Update the context.
+        context.pop_back();
+        context.push_back(*wav_iterator);
+
+        encoding.push_back(error >> 8);
+        encoding.push_back(error);
+
+        ++wav_iterator;
+    }
+    compress(encoding, output_file);
+    return 0;
+}
+
+int unarchive(const char *input_name, const char *output_name)
+{
+    std::ifstream input_file{ input_name, std::ios::binary | std::ios::in };
+    input_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    std::array<char, 44> wav_header = read_header(input_file);
+
+    if (input_file.gcount() != 44)
+    {
+        // Not enough bytes available to read the header.
+        return 2;
+    }
+    std::istreambuf_iterator<char> wav_iterator(input_file), input_end;
+    std::list<char> context = read_first_context(wav_iterator);
+    std::stringstream encoding_stream;
+    std::vector<std::uint8_t> encoded_wav{ wav_iterator, input_end };
+
+    decompress(encoded_wav, encoding_stream);
+
+    std::ofstream output_file{ output_name, std::ios::binary | std::ios::trunc | std::ios::in };
+    output_file.exceptions(std::ios::badbit | std::ios::failbit);
+
+    output_file.write(wav_header.data(), wav_header.size());
+    output_file.write(&context.front(), 1);
+    output_file.write(&context.back(), 1);
+
+    std::string encoding = encoding_stream.str();
+    auto current_encoding = std::cbegin(encoding);
+
+    while (current_encoding != std::cend(encoding))
+    {
+        std::uint8_t first_byte = *current_encoding;
+        ++current_encoding;
+        std::uint8_t second_byte = *current_encoding;
+        ++current_encoding;
+        int error = (first_byte << 8) | second_byte;
+
+        int guess = fc(context);
+        char element = error + guess;
+
+        // Update the context.
+        context.pop_back();
+        context.push_back(element);
+
+        output_file.write(&element, 1);
+    }
+
+    return 0;
+}
+
+int main(int argc, char **argv)
+{
+    if (argc != 4)
+    {
+        return show_usage();
+    }
+    if (std::strcmp(argv[1], "compress") == 0)
+    {
+        return archive(argv[2], argv[3]);
+    }
+    else if (std::strcmp(argv[1], "decompress") == 0)
+    {
+        return unarchive(argv[2], argv[3]);
+    }
+    else
+    {
+        return show_usage();
+    }
+    return 0;
+}