src/RLE.h

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2003-2008 aMule Team ( admin@amule.org / http://www.amule.org )
   5 //
   6 // Any parts of this program derived from the xMule, lMule or eMule project,
   7 // or contributed by third-party developers are copyrighted by their
   8 // respective authors.
   9 //
  10 // This program is free software; you can redistribute it and/or modify
  11 // it under the terms of the GNU General Public License as published by
  12 // the Free Software Foundation; either version 2 of the License, or
  13 // (at your option) any later version.
  14 //
  15 // This program is distributed in the hope that it will be useful,
  16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 // GNU General Public License for more details.
  19 //
  20 // You should have received a copy of the GNU General Public License
  21 // along with this program; if not, write to the Free Software
  22 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301, USA
  23 //
  24
  25 #ifndef RLE_H
  26 #define RLE_H
  27
  28
  29 #include "Types.h"
  30
  31 /*!
  32  * General purpose RLE implementation. Just encode or create
  33  * differential data with previous
  34  */
  35 class RLE_Data
  36 {
  37 public:
  38         RLE_Data(int len, bool use_diff);
  39
  40         // those constructors are for stl containers
  41         RLE_Data();
  42         RLE_Data(const RLE_Data &);
  43         RLE_Data &operator=(const RLE_Data &);
  44
  45         ~RLE_Data();
  46
  47         const unsigned char *Encode(unsigned char *data, int &outlen)
  48         {
  49                 return EncodeT<unsigned char *>(data, m_len, outlen);
  50         }
  51
  52         const unsigned char *Encode(ArrayOfUInts16 &data, int &outlen)
  53         {
  54                 return EncodeT<ArrayOfUInts16>(data, data.size(), outlen);
  55         }
  56
  57         const unsigned char *Decode(const unsigned char *data, int len);
  58
  59         void ResetEncoder()
  60         {
  61                 memset(m_buff, 0, m_len);
  62         }
  63
  64         // change size of internal buffers
  65         void Realloc(int size);
  66
  67         // decoder will need access to data
  68         const unsigned char *Buffer() { return m_buff; }
  69         int Size() { return m_len; }
  70
  71 private:
  72         unsigned char *m_buff, *m_enc_buff;
  73         bool m_use_diff;
  74         int m_len, m_enc_len;
  75
  76         // data is bounded by srclen. everything above considered == 0
  77         template <class T> const unsigned char *EncodeT(T &buff, int srclen, int &outlen)
  78         {
  79                 //
  80                 // calculate difference from prev
  81                 //
  82                 if ( m_use_diff ) {
  83                         for (int i = 0; i < m_len; i++) {
  84                                 m_buff[i] ^= (i < srclen ) ? ((unsigned char)buff[i]) : 0;
  85                         }
  86                 } else {
  87                         //
  88                         // can't use memcpy - in case of generic class T this
  89                         // will rely on "operator []" implementation
  90                         for(int i = 0; i < m_len;i++) {
  91                                 m_buff[i] = (i < srclen ) ? ((unsigned char)buff[i]) : 0;
  92                         }
  93                 }
  94
  95                 //
  96                 // now RLE
  97                 //
  98                 int i = 0, j = 0;
  99                 while ( i != m_len ) {
 100                         unsigned char curr_val = m_buff[i];
 101                         int seq_start = i;
 102                         while ( (i != m_len) && (curr_val == m_buff[i]) && ((i - seq_start) < 0xff)) {
 103                                 i++;
 104                         }
 105                         if (i - seq_start > 1) {
 106                                 // if there's 2 or more equal vals - put it twice in stream
 107                                 m_enc_buff[j++] = curr_val;
 108                                 m_enc_buff[j++] = curr_val;
 109                                 m_enc_buff[j++] = i - seq_start;
 110                         } else {
 111                                 // single value - put it as is
 112                                 m_enc_buff[j++] = curr_val;
 113                         }
 114                 }
 115
 116                 outlen = j;
 117
 118                 //
 119                 // If using differential encoder, remember current data for
 120                 // later use
 121                 if ( m_use_diff ) {
 122                         //
 123                         // can't use memcpy - in case of generic class T this
 124                         // will rely on "operator []" implementation
 125                         for(int k = 0; k < m_len;k++) {
 126                                 m_buff[k] = (k < srclen ) ? ((unsigned char)buff[k]) : 0;
 127                         }
 128                 }
 129
 130                 return m_enc_buff;
 131         }
 132 };
 133
 134
 135 /*
 136  * Another implementation of RLE, optimized for bit-vector. In this RLE flavor we
 137  * have only 2 values, so we don't need to transmit the value itself. Since most
 138  * of the time, bitmap will contail all zeros with few 1's, only zeros will be encoded.
 139  * Meaning that '0000110010000' is encoded as '4024'
 140  */
 141 class RLE_Data_BV
 142 {
 143 public:
 144         RLE_Data_BV(int len);
 145         RLE_Data_BV();
 146         RLE_Data_BV(const RLE_Data_BV &);
 147
 148         ~RLE_Data_BV();
 149
 150         RLE_Data_BV &operator=(const RLE_Data_BV &);
 151
 152         int Encode(std::vector<bool> &data);
 153         void Decode(unsigned char *data, int datalen, std::vector<bool> &outbuff);
 154
 155         const unsigned char *Buffer() { return m_buff; }
 156 private:
 157         // maximum file size in amule is 4G since it uses uint32 as filesize. So, it
 158         // can be up to 4Gb/PARTSIZE=442 parts. Worst case is 1/0 interleaving,
 159         // producing 221 byte RLE encoded output.
 160         static unsigned char m_buff[256];
 161
 162         std::vector<bool> m_last_buff;
 163
 164         void Realloc(int size);
 165 };
 166
 167
 168 /*!
 169  * Data difference is different for each EC client
 170  */
 171 class PartFileEncoderData {
 172 public:
 173         RLE_Data m_part_status;
 174         RLE_Data m_gap_status;
 175
 176         //
 177         // Encoder may reset history if full info requested
 178         void ResetEncoder()
 179         {
 180                 m_part_status.ResetEncoder();
 181                 m_gap_status.ResetEncoder();
 182         }
 183
 184         //
 185         // decoder side - can be used everywhere
 186         void Decode(unsigned char *gapdata, int gaplen, unsigned char *partdata, int partlen);
 187
 188         PartFileEncoderData() { }
 189         PartFileEncoderData(int part_count, int gap_count) :
 190                 m_part_status(part_count, true), m_gap_status(gap_count*sizeof(uint64), true)
 191         {
 192         }
 193
 194         // for stl
 195         PartFileEncoderData(const PartFileEncoderData &obj) :
 196                 m_part_status(obj.m_part_status), m_gap_status(obj.m_gap_status)
 197         {
 198         }
 199
 200         PartFileEncoderData &operator=(const PartFileEncoderData &obj)
 201         {
 202                 m_part_status = obj.m_part_status;
 203                 m_gap_status = obj.m_gap_status;
 204                 return *this;
 205         }
 206 };
 207
 208 #endif
 209
 210 // File_checked_for_headers