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)        { setup(len, use_diff); }
  39
  40         // those constructors are for stl containers
  41         RLE_Data()      { setup(0, 0); }
  42         RLE_Data(const RLE_Data & obj)  { setup(obj.m_len, obj.m_use_diff, obj.m_buff); }
  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         void setup(int len, bool use_diff, unsigned char * content = 0);
  73
  74         unsigned char *m_buff, *m_enc_buff;
  75         bool m_use_diff;
  76         int m_len, m_enc_len;
  77
  78         // data is bounded by srclen. everything above considered == 0
  79         template <class T> const unsigned char *EncodeT(T &buff, int srclen, int &outlen)
  80         {
  81                 //
  82                 // calculate difference from prev
  83                 //
  84                 if ( m_use_diff ) {
  85                         for (int i = 0; i < m_len; i++) {
  86                                 m_buff[i] ^= (i < srclen ) ? ((unsigned char)buff[i]) : 0;
  87                         }
  88                 } else {
  89                         //
  90                         // can't use memcpy - in case of generic class T this
  91                         // will rely on "operator []" implementation
  92                         for(int i = 0; i < m_len;i++) {
  93                                 m_buff[i] = (i < srclen ) ? ((unsigned char)buff[i]) : 0;
  94                         }
  95                 }
  96
  97                 //
  98                 // now RLE
  99                 //
 100                 int i = 0, j = 0;
 101                 while ( i != m_len ) {
 102                         unsigned char curr_val = m_buff[i];
 103                         int seq_start = i;
 104                         while ( (i != m_len) && (curr_val == m_buff[i]) && ((i - seq_start) < 0xff)) {
 105                                 i++;
 106                         }
 107                         if (i - seq_start > 1) {
 108                                 // if there's 2 or more equal vals - put it twice in stream
 109                                 m_enc_buff[j++] = curr_val;
 110                                 m_enc_buff[j++] = curr_val;
 111                                 m_enc_buff[j++] = i - seq_start;
 112                         } else {
 113                                 // single value - put it as is
 114                                 m_enc_buff[j++] = curr_val;
 115                         }
 116                 }
 117
 118                 outlen = j;
 119
 120                 //
 121                 // If using differential encoder, remember current data for
 122                 // later use
 123                 if ( m_use_diff ) {
 124                         //
 125                         // can't use memcpy - in case of generic class T this
 126                         // will rely on "operator []" implementation
 127                         for(int k = 0; k < m_len;k++) {
 128                                 m_buff[k] = (k < srclen ) ? ((unsigned char)buff[k]) : 0;
 129                         }
 130                 }
 131
 132                 return m_enc_buff;
 133         }
 134 };
 135
 136
 137 /*
 138  * Another implementation of RLE, optimized for bit-vector. In this RLE flavor we
 139  * have only 2 values, so we don't need to transmit the value itself. Since most
 140  * of the time, bitmap will contail all zeros with few 1's, only zeros will be encoded.
 141  * Meaning that '0000110010000' is encoded as '4024'
 142  */
 143 class RLE_Data_BV
 144 {
 145 public:
 146         RLE_Data_BV(int len);
 147         RLE_Data_BV();
 148         RLE_Data_BV(const RLE_Data_BV &);
 149
 150         ~RLE_Data_BV();
 151
 152         RLE_Data_BV &operator=(const RLE_Data_BV &);
 153
 154         int Encode(std::vector<bool> &data);
 155         void Decode(unsigned char *data, int datalen, std::vector<bool> &outbuff);
 156
 157         const unsigned char *Buffer() { return m_buff; }
 158 private:
 159         // maximum file size in amule is 4G since it uses uint32 as filesize. So, it
 160         // can be up to 4Gb/PARTSIZE=442 parts. Worst case is 1/0 interleaving,
 161         // producing 221 byte RLE encoded output.
 162         static unsigned char m_buff[256];
 163
 164         std::vector<bool> m_last_buff;
 165
 166         void Realloc(int size);
 167 };
 168
 169
 170 /*!
 171  * Data difference is different for each EC client
 172  */
 173 class PartFileEncoderData {
 174 public:
 175         RLE_Data m_part_status;
 176         RLE_Data m_gap_status;
 177
 178         //
 179         // Encoder may reset history if full info requested
 180         void ResetEncoder()
 181         {
 182                 m_part_status.ResetEncoder();
 183                 m_gap_status.ResetEncoder();
 184         }
 185
 186         //
 187         // decoder side - can be used everywhere
 188         void Decode(unsigned char *gapdata, int gaplen, unsigned char *partdata, int partlen);
 189
 190         PartFileEncoderData() { }
 191         PartFileEncoderData(int part_count, int gap_count) :
 192                 m_part_status(part_count, true), m_gap_status(gap_count*sizeof(uint64), true)
 193         {
 194         }
 195
 196         // for stl
 197         PartFileEncoderData(const PartFileEncoderData &obj) :
 198                 m_part_status(obj.m_part_status), m_gap_status(obj.m_gap_status)
 199         {
 200         }
 201
 202         PartFileEncoderData &operator=(const PartFileEncoderData &obj)
 203         {
 204                 m_part_status = obj.m_part_status;
 205                 m_gap_status = obj.m_gap_status;
 206                 return *this;
 207         }
 208 };
 209
 210 #endif
 211
 212 // File_checked_for_headers