lz77comp.h

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 1996-2006 by Autodesk, Inc.
00003 //
00004 //  By using this code, you are agreeing to the terms and conditions of
00005 //  the License Agreement included in the documentation for this code.
00006 //
00007 //  AUTODESK MAKES NO WARRANTIES, EXPRESS OR IMPLIED, AS TO THE CORRECTNESS
00008 //  OF THIS CODE OR ANY DERIVATIVE WORKS WHICH INCORPORATE IT. AUTODESK
00009 //  PROVIDES THE CODE ON AN "AS-IS" BASIS AND EXPLICITLY DISCLAIMS ANY
00010 //  LIABILITY, INCLUDING CONSEQUENTIAL AND INCIDENTAL DAMAGES FOR ERRORS,
00011 //  OMISSIONS, AND OTHER PROBLEMS IN THE CODE.
00012 //
00013 //  Use, duplication, or disclosure by the U.S. Government is subject to
00014 //  restrictions set forth in FAR 52.227-19 (Commercial Computer Software
00015 //  Restricted Rights) and DFAR 252.227-7013(c)(1)(ii) (Rights in Technical
00016 //  Data and Computer Software), as applicable.
00017 //
00018 
00022 
00023 #if !defined LZ77COMP_HEADER
00024 #define LZ77COMP_HEADER
00025 
00026 #include "whiptk/whipcore.h"
00027 #include "whiptk/fifo.h"
00028 #include "whiptk/file.h"
00029 #include "whiptk/lzdefs.h"
00030 
00031 #ifdef    DWFCORE_BUILD_ZLIB
00032 #include "dwfcore/zlib/zlib.h"
00033 #else
00034 #include <zlib.h>
00035 #endif
00036 
00037 #define WD_LZ_BYTES_USED_FOR_HASH                4
00038 #define WD_MAX_HASH_ENTRIES_TO_SEARCH            64
00039 #define WD_LZ_HASH_TABLE_SIZE                    65536
00040 #define WD_MAXIMUM_MATCH_LENGTH                  (255 + 15 + WD_LZ_COMPRESSION_AND_OFFSET_CODE_BYTES)
00041 #define WD_MAX_LITERAL_DATA_STREAM               (255 + 15)
00042 
00044 
00045 class WT_History_Item
00046 {
00047 private:
00048     WT_Byte                 m_value;
00049     WT_History_Item *       m_next;
00050     WT_History_Item **      m_backlink;
00051 
00052 /* FIXME:  The copy constructor and assignment operators should not be public, but private!
00053    Unfortunately, when private, we generate the following error:
00054 
00055     ../../inc\whiptk\fifo.h(155) : error C2248: 'WT_History_Item::operator`='' : cannot access private member declared in class 'WT_History_Item'
00056             ../../inc\whiptk\lz77comp.h(56) : see declaration of 'WT_History_Item::operator`=''
00057             ../../inc\whiptk\lz77comp.h(36) : see declaration of 'WT_History_Item'
00058             ../../inc\whiptk\fifo.h(54) : while compiling class-template member function 'WT_Result WT_FIFO<_ItemType>::add(int,const _ItemType *)'
00059             with
00060             [
00061                 _ItemType=WT_History_Item
00062             ]
00063             ../../inc\whiptk\lz77comp.h(103) : see reference to class template instantiation 'WT_FIFO<_ItemType>' being compiled
00064             with
00065             [
00066                 _ItemType=WT_History_Item
00067             ]
00068     Alternatively, a proper definition of these members could be supplied, although it's difficult to ascertain what that should be.
00069 */
00070 public:
00071     WT_History_Item (WT_History_Item const &)
00072         : m_value(0)
00073         , m_next(WD_Null)
00074         , m_backlink(WD_Null)
00075     {
00076         WD_Complain ("cannot copy WT_History_Item");
00077     } // prohibited
00078 
00079 
00080     WT_History_Item & operator= (WT_History_Item const &)
00081     {
00082         WD_Complain ("cannot assign WT_History_Item");
00083         return *this;
00084     } // prohibited
00085 
00086 public:
00087     // Constructors, Destructors
00088 
00089     WT_History_Item()
00090         : m_value(0)
00091         , m_next(WD_Null)
00092         , m_backlink(WD_Null)
00093     { }
00094 
00095     ~WT_History_Item()
00096     { }
00097 
00098     void unlink()
00099     {
00100         if ((*m_backlink = m_next) != WD_Null)
00101             m_next->set_backlink(m_backlink);
00102     }
00103 
00104     void set_value(WT_Byte data)
00105     {    m_value = data;    }
00106     WT_Byte    value() const
00107     {    return m_value;    }
00108 
00109     void set_next(WT_History_Item * next)
00110     {    m_next = next;    }
00111     WT_History_Item * & next()
00112     {    return m_next;    }
00113 
00114     void set_backlink(WT_History_Item ** backlink)
00115     {    m_backlink = backlink;    }
00116     WT_History_Item ** & backlink()
00117     {    return m_backlink;    }
00118 };
00119 
00120 
00122 
00123 class WT_LZ_Compressor : public WT_Compressor
00124 {
00125 private:
00126     WT_FIFO<WT_Byte>            m_candidate;
00127     WT_FIFO<WT_History_Item>    m_history;
00128     WT_History_Item *           m_hash_table[WD_LZ_HASH_TABLE_SIZE];
00129     WT_Boolean                  m_at_least_one_extendible;
00130     WT_FIFO<WT_Byte>            m_literal_output_buf;
00131     WT_File &                   m_file;
00132     WT_Boolean                  m_compression_started;
00133     int                         m_best_match_length;
00134     WT_History_Item *           m_best_match;
00135     WT_Boolean                  m_best_match_extendible;
00136     int                         m_hash_entries_searched;
00137 
00138     void    preload_history_buffer();
00139 
00140 #ifdef DEBUG_ASSERTIONS
00141     int                            m_total_literal_bytes;
00142     int                            m_total_literal_strings;
00143     int                            m_num_literal_string_overflows;
00144     int                            m_total_compressed_bytes;
00145     int                            m_total_compression_codes;
00146     int                            m_biggest_compressed_string;
00147     int                            m_hash_misses;
00148     int                            m_hash_hits;
00149 #endif
00150 
00151 //    WT_LZ_Compressor(WT_LZ_Compressor const & other)
00152 //        : WT_Compressor()
00153 //        , m_candidate()
00154 //        , m_history()
00155 //        , m_at_least_one_extendible()
00156 //        , m_literal_output_buf()
00157 //        , m_file(other.m_file) //_WT_File_g_none)
00158 //        , m_compression_started()
00159 //        , m_best_match_length()
00160 //        , m_best_match()
00161 //        , m_best_match_extendible()
00162 //        , m_hash_entries_searched()
00163 //#ifdef DEBUG_ASSERTIONS
00164 //        , m_total_literal_bytes()
00165 //        , m_total_literal_strings()
00166 //        , m_num_literal_string_overflows()
00167 //        , m_total_compressed_bytes()
00168 //        , m_total_compression_codes()
00169 //        , m_biggest_compressed_string()
00170 //        , m_hash_misses()
00171 //        , m_hash_hits()
00172 //#endif
00173 //    {
00174 //        WD_Complain ("cannot copy WT_LZ_Compressor");
00175 //    } // prohibited
00176 
00177     //WT_LZ_Compressor operator= (WT_LZ_Compressor const &)
00178     //{
00179     //    WD_Complain ("cannot assign WT_LZ_Compressor");
00180     //    return *this;
00181     //} // prohibited
00182 
00183 public:
00184 
00185     // Constructors, Destructors
00186 
00187     WT_LZ_Compressor(WT_File & file)
00188         : m_history(WD_LZ_HISTORY_BUFFER_SIZE)
00189         , m_at_least_one_extendible(WD_False)
00190         , m_literal_output_buf()
00191         , m_file(file)
00192         , m_compression_started(WD_False)
00193         , m_best_match_length(WD_LZ_COMPRESSION_AND_OFFSET_CODE_BYTES)
00194         , m_best_match(WD_Null)
00195         , m_best_match_extendible(WD_False)
00196         , m_hash_entries_searched(0)
00197 
00198 #ifdef DEBUG_ASSERTIONS
00199         , m_total_literal_bytes(0)
00200         , m_total_literal_strings(0)
00201         , m_num_literal_string_overflows(0)
00202         , m_total_compressed_bytes(0)
00203         , m_total_compression_codes(0)
00204         , m_biggest_compressed_string(0)
00205         , m_hash_misses(0)
00206         , m_hash_hits(0)
00207 #endif
00208     { }
00209 
00210     ~WT_LZ_Compressor()
00211     { }
00212 
00213     WT_Result    compress(int in_size, void const * in_buf);
00214              WT_Result    output_match();
00215              void        extend_best_match_length();
00216              void        find_better_match(WT_History_Item * history_item);
00217     WT_Result    start();
00218     WT_Boolean   is_compression_started() { return m_compression_started; }
00219     WT_Result    stop();
00220     WT_Result    add_to_history_buffer(WT_Byte a_byte, WT_Boolean output);
00221 };
00222 
00223 
00225 
00226 class WT_ZLib_Compressor : public WT_Compressor
00227 {
00228 private:
00229     WT_File &                   m_file;
00230     WT_Boolean                  m_compression_started;
00231     z_stream                    m_zlib_stream; /* compression stream */
00232     WT_Byte                     m_zlib_output_buffer[WD_ZLIB_COMPRESSION_OUTPUT_BUFFER_SIZE];
00233 
00234     WT_Result   preload_history_buffer();
00235 
00236     //WT_ZLib_Compressor(WT_ZLib_Compressor const & other)
00237     //    : WT_Compressor()
00238     //    , m_file(other.m_file)//_WT_File_g_none)
00239     //    , m_compression_started(WD_False)
00240     //    , m_zlib_stream()
00241     //{
00242     //    WD_Complain ("cannot copy WT_ZLib_Compressor");
00243     //} // prohibited
00244 
00245     WT_ZLib_Compressor & operator= (WT_ZLib_Compressor const &)
00246     {
00247         WD_Complain ("cannot assign WT_ZLib_Compressor");
00248         return *this;
00249     } // prohibited
00250 
00251 
00252 public:
00253 
00254     // Constructors, Destructors
00255 
00256     WT_ZLib_Compressor(WT_File & file)
00257         : m_file(file)
00258         , m_compression_started(WD_False)
00259     { }
00260 
00261     ~WT_ZLib_Compressor()
00262     { }
00263 
00264     WT_Result    start();
00265     WT_Boolean   is_compression_started() { return m_compression_started; }
00266     WT_Result    stop();
00267     WT_Result    compress(int in_size, void const * in_buf);
00268 };
00269 
00270 #endif // LZ77COMP_HEADER

Generated on Tue Jan 6 22:41:13 2009 for Autodesk DWF Whip 2D Toolkit by  doxygen 1.4.5