123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727 |
- #ifndef BOOST_BEAST_ZLIB_DETAIL_DEFLATE_STREAM_HPP
- #define BOOST_BEAST_ZLIB_DETAIL_DEFLATE_STREAM_HPP
- #include <boost/beast/zlib/error.hpp>
- #include <boost/beast/zlib/zlib.hpp>
- #include <boost/beast/zlib/detail/ranges.hpp>
- #include <boost/assert.hpp>
- #include <boost/config.hpp>
- #include <boost/optional.hpp>
- #include <boost/throw_exception.hpp>
- #include <cstdint>
- #include <cstdlib>
- #include <cstring>
- #include <memory>
- #include <stdexcept>
- #include <type_traits>
- namespace boost {
- namespace beast {
- namespace zlib {
- namespace detail {
- class deflate_stream
- {
- protected:
-
- static std::uint8_t constexpr maxBits = 15;
-
- static std::uint16_t constexpr lengthCodes = 29;
-
- static std::uint16_t constexpr literals = 256;
-
- static std::uint16_t constexpr lCodes = literals + 1 + lengthCodes;
-
- static std::uint16_t constexpr dCodes = 30;
-
- static std::uint16_t constexpr blCodes = 19;
-
- static std::uint16_t constexpr distCodeLen = 512;
-
- static std::uint8_t constexpr maxBlBits= 7;
- static std::uint16_t constexpr minMatch = 3;
- static std::uint16_t constexpr maxMatch = 258;
-
- BOOST_STATIC_ASSERT(minMatch == 3);
-
- static std::uint16_t constexpr END_BLOCK = 256;
-
- static std::uint8_t constexpr REP_3_6 = 16;
-
- static std::uint8_t constexpr REPZ_3_10 = 17;
-
- static std::uint8_t constexpr REPZ_11_138 = 18;
-
- static std::uint8_t constexpr STORED_BLOCK = 0;
- static std::uint8_t constexpr STATIC_TREES = 1;
- static std::uint8_t constexpr DYN_TREES = 2;
-
- static std::uint8_t constexpr max_mem_level = 9;
-
- static std::uint8_t constexpr DEF_MEM_LEVEL = max_mem_level;
-
-
- static std::uint16_t constexpr HEAP_SIZE = 2 * lCodes + 1;
-
- static std::uint8_t constexpr Buf_size = 16;
-
- static std::size_t constexpr kTooFar = 4096;
-
- static std::size_t constexpr kMinLookahead = maxMatch + minMatch+1;
-
- static std::size_t constexpr kWinInit = maxMatch;
-
- struct ct_data
- {
- std::uint16_t fc;
- std::uint16_t dl;
- bool
- operator==(ct_data const& rhs) const
- {
- return fc == rhs.fc && dl == rhs.dl;
- }
- };
- struct static_desc
- {
- ct_data const* static_tree;
- std::uint8_t const* extra_bits;
- std::uint16_t extra_base;
- std::uint16_t elems;
- std::uint8_t max_length;
- };
- struct lut_type
- {
-
- std::uint8_t const extra_lbits[lengthCodes] = {
- 0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0
- };
-
- std::uint8_t const extra_dbits[dCodes] = {
- 0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
- };
-
- std::uint8_t const extra_blbits[blCodes] = {
- 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7
- };
-
-
-
- std::uint8_t const bl_order[blCodes] = {
- 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
- };
- ct_data ltree[lCodes + 2];
- ct_data dtree[dCodes];
-
-
-
- std::uint8_t dist_code[distCodeLen];
- std::uint8_t length_code[maxMatch-minMatch+1];
- std::uint8_t base_length[lengthCodes];
- std::uint16_t base_dist[dCodes];
- static_desc l_desc = {
- ltree, extra_lbits, literals+1, lCodes, maxBits
- };
- static_desc d_desc = {
- dtree, extra_dbits, 0, dCodes, maxBits
- };
- static_desc bl_desc =
- {
- nullptr, extra_blbits, 0, blCodes, maxBlBits
- };
- };
- struct tree_desc
- {
- ct_data *dyn_tree;
- int max_code;
- static_desc const* stat_desc;
- };
- enum block_state
- {
- need_more,
- block_done,
- finish_started,
- finish_done
- };
-
- enum StreamStatus
- {
- EXTRA_STATE = 69,
- NAME_STATE = 73,
- COMMENT_STATE = 91,
- HCRC_STATE = 103,
- BUSY_STATE = 113,
- FINISH_STATE = 666
- };
-
- using IPos = unsigned;
- using self = deflate_stream;
- typedef block_state(self::*compress_func)(z_params& zs, Flush flush);
-
- lut_type const& lut_;
- bool inited_ = false;
- std::size_t buf_size_;
- std::unique_ptr<std::uint8_t[]> buf_;
- int status_;
- Byte* pending_buf_;
- std::uint32_t
- pending_buf_size_;
- Byte* pending_out_;
- uInt pending_;
- boost::optional<Flush>
- last_flush_;
- uInt w_size_;
- uInt w_bits_;
- uInt w_mask_;
-
- Byte *window_ = nullptr;
-
- std::uint32_t window_size_;
-
- std::uint16_t* prev_;
- std::uint16_t* head_;
- uInt ins_h_;
- uInt hash_size_;
- uInt hash_bits_;
- uInt hash_mask_;
-
- uInt hash_shift_;
-
- long block_start_;
- uInt match_length_;
- IPos prev_match_;
- int match_available_;
- uInt strstart_;
- uInt match_start_;
- uInt lookahead_;
-
- uInt prev_length_;
-
- uInt max_chain_length_;
-
- uInt max_lazy_match_;
- int level_;
- Strategy strategy_;
-
- uInt good_match_;
- int nice_match_;
- ct_data dyn_ltree_[
- HEAP_SIZE];
- ct_data dyn_dtree_[
- 2*dCodes+1];
- ct_data bl_tree_[
- 2*blCodes+1];
- tree_desc l_desc_;
- tree_desc d_desc_;
- tree_desc bl_desc_;
-
- std::uint16_t bl_count_[maxBits+1];
-
- static std::size_t constexpr kSmallest = 1;
-
- int heap_[2*lCodes+1];
- int heap_len_;
- int heap_max_;
-
- std::uint8_t depth_[2*lCodes+1];
- std::uint8_t *l_buf_;
-
- uInt lit_bufsize_;
- uInt last_lit_;
-
- std::uint16_t* d_buf_;
- std::uint32_t opt_len_;
- std::uint32_t static_len_;
- uInt matches_;
- uInt insert_;
-
- std::uint16_t bi_buf_;
-
- int bi_valid_;
-
- std::uint32_t high_water_;
-
- deflate_stream()
- : lut_(get_lut())
- {
- }
-
- std::size_t
- max_dist() const
- {
- return w_size_ - kMinLookahead;
- }
- void
- put_byte(std::uint8_t c)
- {
- pending_buf_[pending_++] = c;
- }
- void
- put_short(std::uint16_t w)
- {
- put_byte(w & 0xff);
- put_byte(w >> 8);
- }
-
- void
- send_bits(int value, int length)
- {
- if(bi_valid_ > (int)Buf_size - length)
- {
- bi_buf_ |= (std::uint16_t)value << bi_valid_;
- put_short(bi_buf_);
- bi_buf_ = (std::uint16_t)value >> (Buf_size - bi_valid_);
- bi_valid_ += length - Buf_size;
- }
- else
- {
- bi_buf_ |= (std::uint16_t)(value) << bi_valid_;
- bi_valid_ += length;
- }
- }
-
- void
- send_code(int value, ct_data const* tree)
- {
- send_bits(tree[value].fc, tree[value].dl);
- }
-
- std::uint8_t
- d_code(unsigned dist)
- {
- if(dist < 256)
- return lut_.dist_code[dist];
- return lut_.dist_code[256+(dist>>7)];
- }
-
- void
- update_hash(uInt& h, std::uint8_t c)
- {
- h = ((h << hash_shift_) ^ c) & hash_mask_;
- }
-
- void
- clear_hash()
- {
- head_[hash_size_-1] = 0;
- std::memset((Byte *)head_, 0,
- (unsigned)(hash_size_-1)*sizeof(*head_));
- }
-
- bool
- smaller(ct_data const* tree, int n, int m)
- {
- return tree[n].fc < tree[m].fc ||
- (tree[n].fc == tree[m].fc &&
- depth_[n] <= depth_[m]);
- }
-
- void
- insert_string(IPos& hash_head)
- {
- update_hash(ins_h_, window_[strstart_ + (minMatch-1)]);
- hash_head = prev_[strstart_ & w_mask_] = head_[ins_h_];
- head_[ins_h_] = (std::uint16_t)strstart_;
- }
-
-
- struct config
- {
- std::uint16_t good_length;
- std::uint16_t max_lazy;
- std::uint16_t nice_length;
- std::uint16_t max_chain;
- compress_func func;
- config(
- std::uint16_t good_length_,
- std::uint16_t max_lazy_,
- std::uint16_t nice_length_,
- std::uint16_t max_chain_,
- compress_func func_)
- : good_length(good_length_)
- , max_lazy(max_lazy_)
- , nice_length(nice_length_)
- , max_chain(max_chain_)
- , func(func_)
- {
- }
- };
- static
- config
- get_config(std::size_t level)
- {
- switch(level)
- {
-
- case 0: return { 0, 0, 0, 0, &self::deflate_stored};
- case 1: return { 4, 4, 8, 4, &self::deflate_fast};
- case 2: return { 4, 5, 16, 8, &self::deflate_fast};
- case 3: return { 4, 6, 32, 32, &self::deflate_fast};
- case 4: return { 4, 4, 16, 16, &self::deflate_slow};
- case 5: return { 8, 16, 32, 32, &self::deflate_slow};
- case 6: return { 8, 16, 128, 128, &self::deflate_slow};
- case 7: return { 8, 32, 128, 256, &self::deflate_slow};
- case 8: return { 32, 128, 258, 1024, &self::deflate_slow};
- default:
- case 9: return { 32, 258, 258, 4096, &self::deflate_slow};
- }
- }
- void
- maybe_init()
- {
- if(! inited_)
- init();
- }
- template<class Unsigned>
- static
- Unsigned
- bi_reverse(Unsigned code, unsigned len);
- BOOST_BEAST_DECL
- static
- void
- gen_codes(ct_data *tree, int max_code, std::uint16_t *bl_count);
- BOOST_BEAST_DECL
- static
- lut_type const&
- get_lut();
- BOOST_BEAST_DECL void doReset (int level, int windowBits, int memLevel, Strategy strategy);
- BOOST_BEAST_DECL void doReset ();
- BOOST_BEAST_DECL void doClear ();
- BOOST_BEAST_DECL std::size_t doUpperBound (std::size_t sourceLen) const;
- BOOST_BEAST_DECL void doTune (int good_length, int max_lazy, int nice_length, int max_chain);
- BOOST_BEAST_DECL void doParams (z_params& zs, int level, Strategy strategy, error_code& ec);
- BOOST_BEAST_DECL void doWrite (z_params& zs, boost::optional<Flush> flush, error_code& ec);
- BOOST_BEAST_DECL void doDictionary (Byte const* dict, uInt dictLength, error_code& ec);
- BOOST_BEAST_DECL void doPrime (int bits, int value, error_code& ec);
- BOOST_BEAST_DECL void doPending (unsigned* value, int* bits);
- BOOST_BEAST_DECL void init ();
- BOOST_BEAST_DECL void lm_init ();
- BOOST_BEAST_DECL void init_block ();
- BOOST_BEAST_DECL void pqdownheap (ct_data const* tree, int k);
- BOOST_BEAST_DECL void pqremove (ct_data const* tree, int& top);
- BOOST_BEAST_DECL void gen_bitlen (tree_desc *desc);
- BOOST_BEAST_DECL void build_tree (tree_desc *desc);
- BOOST_BEAST_DECL void scan_tree (ct_data *tree, int max_code);
- BOOST_BEAST_DECL void send_tree (ct_data *tree, int max_code);
- BOOST_BEAST_DECL int build_bl_tree ();
- BOOST_BEAST_DECL void send_all_trees (int lcodes, int dcodes, int blcodes);
- BOOST_BEAST_DECL void compress_block (ct_data const* ltree, ct_data const* dtree);
- BOOST_BEAST_DECL int detect_data_type ();
- BOOST_BEAST_DECL void bi_windup ();
- BOOST_BEAST_DECL void bi_flush ();
- BOOST_BEAST_DECL void copy_block (char *buf, unsigned len, int header);
- BOOST_BEAST_DECL void tr_init ();
- BOOST_BEAST_DECL void tr_align ();
- BOOST_BEAST_DECL void tr_flush_bits ();
- BOOST_BEAST_DECL void tr_stored_block (char *bu, std::uint32_t stored_len, int last);
- BOOST_BEAST_DECL void tr_tally_dist (std::uint16_t dist, std::uint8_t len, bool& flush);
- BOOST_BEAST_DECL void tr_tally_lit (std::uint8_t c, bool& flush);
- BOOST_BEAST_DECL void tr_flush_block (z_params& zs, char *buf, std::uint32_t stored_len, int last);
- BOOST_BEAST_DECL void fill_window (z_params& zs);
- BOOST_BEAST_DECL void flush_pending (z_params& zs);
- BOOST_BEAST_DECL void flush_block (z_params& zs, bool last);
- BOOST_BEAST_DECL int read_buf (z_params& zs, Byte *buf, unsigned size);
- BOOST_BEAST_DECL uInt longest_match (IPos cur_match);
- BOOST_BEAST_DECL block_state f_stored (z_params& zs, Flush flush);
- BOOST_BEAST_DECL block_state f_fast (z_params& zs, Flush flush);
- BOOST_BEAST_DECL block_state f_slow (z_params& zs, Flush flush);
- BOOST_BEAST_DECL block_state f_rle (z_params& zs, Flush flush);
- BOOST_BEAST_DECL block_state f_huff (z_params& zs, Flush flush);
- block_state
- deflate_stored(z_params& zs, Flush flush)
- {
- return f_stored(zs, flush);
- }
- block_state
- deflate_fast(z_params& zs, Flush flush)
- {
- return f_fast(zs, flush);
- }
- block_state
- deflate_slow(z_params& zs, Flush flush)
- {
- return f_slow(zs, flush);
- }
- block_state
- deflate_rle(z_params& zs, Flush flush)
- {
- return f_rle(zs, flush);
- }
- block_state
- deflate_huff(z_params& zs, Flush flush)
- {
- return f_huff(zs, flush);
- }
- };
- template<class Unsigned>
- Unsigned
- deflate_stream::
- bi_reverse(Unsigned code, unsigned len)
- {
- BOOST_STATIC_ASSERT(std::is_unsigned<Unsigned>::value);
- BOOST_ASSERT(len <= 8 * sizeof(unsigned));
- Unsigned res = 0;
- do
- {
- res |= code & 1;
- code >>= 1;
- res <<= 1;
- }
- while(--len > 0);
- return res >> 1;
- }
- }
- }
- }
- }
- #ifdef BOOST_BEAST_HEADER_ONLY
- #include <boost/beast/zlib/detail/deflate_stream.ipp>
- #endif
- #endif
|