diff options
Diffstat (limited to 'coding')
-rw-r--r-- | coding/bwt_coder.hpp | 12 | ||||
-rw-r--r-- | coding/huffman.cpp | 17 | ||||
-rw-r--r-- | coding/huffman.hpp | 59 |
3 files changed, 60 insertions, 28 deletions
diff --git a/coding/bwt_coder.hpp b/coding/bwt_coder.hpp index 59d66c2d94..0a9a5e6398 100644 --- a/coding/bwt_coder.hpp +++ b/coding/bwt_coder.hpp @@ -43,7 +43,7 @@ public: template <typename Sink> static void EncodeAndWriteBlock(Sink & sink, size_t n, uint8_t const * s) { - vector<uint8_t> bwtBuffer; + std::vector<uint8_t> bwtBuffer; EncodeAndWriteBlock(sink, n, s, bwtBuffer); } @@ -59,14 +59,14 @@ public: WriteVarUint(sink, numBlocks); for (size_t i = 0; i < n; i += params.m_blockSize) { - auto const m = min(n - i, params.m_blockSize); + auto const m = std::min(n - i, params.m_blockSize); EncodeAndWriteBlock(sink, m, s + i, bwtBuffer); } } template <typename Source, typename OutIt> - static OutIt ReadAndDecodeBlock(Source & source, vector<uint8_t> & bwtBuffer, - vector<uint8_t> & revBuffer, OutIt it) + static OutIt ReadAndDecodeBlock(Source & source, std::vector<uint8_t> & bwtBuffer, + std::vector<uint8_t> & revBuffer, OutIt it) { auto const start = ReadVarUint<uint64_t, Source>(source); @@ -95,8 +95,8 @@ public: template <typename Source, typename OutIt> static OutIt ReadAndDecodeBlock(Source & source, OutIt it) { - vector<uint8_t> bwtBuffer; - vector<uint8_t> revBuffer; + std::vector<uint8_t> bwtBuffer; + std::vector<uint8_t> revBuffer; return ReadAndDecodeBlock(source, bwtBuffer, revBuffer, it); } diff --git a/coding/huffman.cpp b/coding/huffman.cpp index 83d60039a3..aa92e8ad49 100644 --- a/coding/huffman.cpp +++ b/coding/huffman.cpp @@ -61,12 +61,6 @@ void HuffmanCoder::DeleteHuffmanTree(Node * root) void HuffmanCoder::BuildHuffmanTree(Freqs const & freqs) { - // One would need more than 2^32 symbols to build a code that long. - // On the other hand, 32 is short enough for our purposes, so do not - // try to shrink the trees beyond this threshold. - - uint32_t const kMaxDepth = 32; - priority_queue<Node *, vector<Node *>, NodeComparator> pq; for (auto const & e : freqs.GetTable()) pq.push(new Node(e.first, e.second, true /* isLeaf */)); @@ -89,24 +83,27 @@ void HuffmanCoder::BuildHuffmanTree(Freqs const & freqs) auto ab = new Node(a->symbol, a->freq + b->freq, false /* isLeaf */); ab->l = a; ab->r = b; - CHECK_LESS_OR_EQUAL(a->depth, kMaxDepth, ()); - CHECK_LESS_OR_EQUAL(b->depth, kMaxDepth, ()); pq.push(ab); } m_root = pq.top(); pq.pop(); - SetDepths(m_root, 0); + SetDepths(m_root, 0 /* depth */); } void HuffmanCoder::SetDepths(Node * root, uint32_t depth) { + // One would need more than 2^32 symbols to build a code that long. + // On the other hand, 32 is short enough for our purposes, so do not + // try to shrink the trees beyond this threshold. + uint32_t const kMaxDepth = 32; + if (!root) return; + CHECK_LESS_OR_EQUAL(depth, kMaxDepth, ()); root->depth = depth; SetDepths(root->l, depth + 1); SetDepths(root->r, depth + 1); } - } // namespace coding diff --git a/coding/huffman.hpp b/coding/huffman.hpp index 5beaef4033..a9356253aa 100644 --- a/coding/huffman.hpp +++ b/coding/huffman.hpp @@ -4,12 +4,15 @@ #include "coding/varint.hpp" #include "base/assert.hpp" +#include "base/checked_cast.hpp" #include "base/string_utils.hpp" #include "std/algorithm.hpp" #include "std/iterator.hpp" #include "std/map.hpp" #include "std/queue.hpp" +#include "std/type_traits.hpp" +#include "std/unique_ptr.hpp" #include "std/vector.hpp" namespace coding @@ -34,23 +37,38 @@ public: void Add(string const & s) { Add(s.begin(), s.end()); } + template <typename T> + void Add(T const * begin, T const * const end) + { + static_assert(is_integral<T>::value, ""); + AddImpl(begin, end); + } + template <typename It> - void Add(It begin, It end) + void Add(It begin, It const end) { - for (; begin != end; ++begin) - ++m_table[static_cast<uint32_t>(*begin)]; + static_assert(is_integral<typename It::value_type>::value, ""); + AddImpl(begin, end); } template <typename T> void Add(vector<T> const & v) { for (auto const & e : v) - Add(e); + Add(begin(e), end(e)); } Table const & GetTable() const { return m_table; } private: + template <typename It> + void AddImpl(It begin, It const end) + { + static_assert(sizeof(*begin) <= 4, ""); + for (; begin != end; ++begin) + ++m_table[static_cast<uint32_t>(*begin)]; + } + Table m_table; }; @@ -149,16 +167,18 @@ public: bool Encode(uint32_t symbol, Code & code) const; bool Decode(Code const & code, uint32_t & symbol) const; + template <typename TWriter, typename T> + uint32_t EncodeAndWrite(TWriter & writer, T const * begin, T const * end) const + { + static_assert(is_integral<T>::value, ""); + return EncodeAndWriteImpl(writer, begin, end); + } + template <typename TWriter, typename It> uint32_t EncodeAndWrite(TWriter & writer, It begin, It end) const { - size_t const d = distance(begin, end); - BitWriter<TWriter> bitWriter(writer); - WriteVarUint(writer, d); - uint32_t sz = 0; - for (; begin != end; ++begin) - sz += EncodeAndWrite(bitWriter, static_cast<uint32_t>(*begin)); - return sz; + static_assert(is_integral<typename It::value_type>::value, ""); + return EncodeAndWriteImpl(writer, begin, end); } template <typename TWriter> @@ -176,13 +196,14 @@ public: } template <typename TSource, typename OutIt> - void ReadAndDecode(TSource & src, OutIt out) const + OutIt ReadAndDecode(TSource & src, OutIt out) const { BitReader<TSource> bitReader(src); size_t sz = static_cast<size_t>(ReadVarUint<uint32_t, TSource>(src)); vector<strings::UniChar> v(sz); for (size_t i = 0; i < sz; ++i) *out++ = ReadAndDecode(bitReader); + return out; } template <typename TSource> @@ -236,6 +257,20 @@ private: return code.len; } + template <typename TWriter, typename It> + uint32_t EncodeAndWriteImpl(TWriter & writer, It begin, It end) const + { + static_assert(sizeof(*begin) <= 4, ""); + + size_t const d = base::asserted_cast<size_t>(distance(begin, end)); + BitWriter<TWriter> bitWriter(writer); + WriteVarUint(writer, d); + uint32_t sz = 0; + for (; begin != end; ++begin) + sz += EncodeAndWrite(bitWriter, static_cast<uint32_t>(*begin)); + return sz; + } + template <typename TSource> uint32_t ReadAndDecode(BitReader<TSource> & bitReader) const { |