src/RLE.cpp

   1 //
   2 // This file is part of the aMule Project.
   3 //
   4 // Copyright (c) 2003-2011 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 #include "RLE.h"
  26 #include "ArchSpecific.h"
  27 #include "ScopedPtr.h"
  28 #include <ec/cpp/ECTag.h>               // Needed for CECTag
  29
  30 /*
  31  * RLE encoder implementation. This is RLE implementation for very specific
  32  * purpose: encode DIFFERENCE between subsequent states of status bar.
  33  *
  34  * This difference is calculated by xor-ing with previous data
  35  *
  36  * We can't use implementation with "control char" since this encoder
  37  * will process binary data - not ascii (or unicode) strings
  38  */
  39 void RLE_Data::setup(int len, bool use_diff, uint8 * content)
  40 {
  41         m_len = len;
  42         m_use_diff = use_diff;
  43
  44         if (m_len) {
  45                 m_buff = new uint8[m_len];
  46                 if (content) {
  47                         memcpy(m_buff, content, m_len);
  48                 } else {
  49                         memset(m_buff, 0, m_len);
  50                 }
  51                 //
  52         } else {
  53                 m_buff = 0;
  54         }
  55 }
  56
  57 RLE_Data &RLE_Data::operator=(const RLE_Data &obj)
  58 {
  59         if (this == &obj)
  60                 return *this;
  61
  62         delete [] m_buff;
  63         setup(obj.m_len, obj.m_use_diff, obj.m_buff);
  64
  65         return *this;
  66 }
  67
  68 RLE_Data::~RLE_Data()
  69 {
  70         delete [] m_buff;
  71 }
  72
  73 void RLE_Data::ResetEncoder()
  74 {
  75         delete m_buff;
  76         m_len = 0;
  77         m_buff = 0;
  78 }
  79
  80 bool RLE_Data::Realloc(int size)
  81 {
  82         if ( size == m_len ) {
  83                 return false;
  84         }
  85         if (size == 0) {
  86                 delete [] m_buff;
  87                 m_buff = 0;
  88                 m_len = 0;
  89                 return true;
  90         }
  91         uint8 *buff = new uint8[size];
  92         if (m_len == 0) {
  93                 memset(buff, 0, size);
  94         } else if ( size > m_len ) {
  95                 memset(buff + m_len, 0, size - m_len);
  96                 memcpy(buff, m_buff, m_len);
  97         } else {
  98                 memcpy(buff, m_buff, size);
  99         }
 100         delete [] m_buff;
 101         m_buff = buff;
 102
 103         m_len = size;
 104         return true;
 105 }
 106
 107 const uint8 *RLE_Data::Decode(const uint8 *buff, int len)
 108 {
 109         uint8 * decBuf = m_len ? new uint8[m_len] : 0;
 110
 111         // If data exceeds the buffer, switch to counting only.
 112         // Then resize and make a second pass.
 113         for (bool overrun = true; overrun;) {
 114                 overrun = false;
 115                 int j = 0;
 116                 for (int i = 0; i < len;) {
 117                         if (i < len - 2 && buff[i+1] == buff[i]) {
 118                                 // This is a sequence.
 119                                 uint8 seqLen = buff[i + 2];
 120                                 if (j + seqLen <= m_len) {
 121                                         memset(decBuf + j, buff[i], seqLen);
 122                                 }
 123                                 j += seqLen;
 124                                 i += 3;
 125                         } else {
 126                                 // This is a single byte.
 127                                 if (j < m_len) {
 128                                         decBuf[j] = buff[i];
 129                                 }
 130                                 j++;
 131                                 i++;
 132                         }
 133                 }
 134                 if (j != m_len) {
 135                         overrun = j > m_len;    // overrun, make a second pass
 136                         Realloc(j);                             // size has changed, adjust
 137                         if (overrun) {
 138                                 delete[] decBuf;
 139                                 decBuf = new uint8[m_len];
 140                         }
 141                 }
 142         }
 143         //
 144         // Recreate data from diff
 145         //
 146         if ( m_use_diff ) {
 147                 for (int k = 0; k < m_len; k++) {
 148                         m_buff[k] ^= decBuf[k];
 149                 }
 150         } else {
 151                 memcpy(m_buff, decBuf, m_len);
 152         }
 153         delete[] decBuf;
 154         return m_buff;
 155 }
 156
 157 const uint8 * RLE_Data::Encode(const uint8 *data, int inlen, int &outlen, bool &changed)
 158 {
 159         changed = Realloc(inlen);               // adjust size if necessary
 160
 161         if (m_len == 0) {
 162                 outlen = 0;
 163                 return NULL;
 164         }
 165         //
 166         // calculate difference from prev
 167         //
 168         if ( m_use_diff ) {
 169                 for (int i = 0; i < m_len; i++) {
 170                         m_buff[i] ^= data[i];
 171                         if (m_buff[i]) {
 172                                 changed = true;
 173                         }
 174                 }
 175         } else {
 176                 memcpy(m_buff, data, m_len);
 177                 changed = true;
 178         }
 179
 180         //
 181         // now RLE
 182         //
 183         // In worst case 2-byte sequence is encoded as 3. So, data can grow by 50%.
 184         uint8 * enc_buff = new uint8[m_len * 3/2 + 1];
 185         int i = 0, j = 0;
 186         while ( i != m_len ) {
 187                 uint8 curr_val = m_buff[i];
 188                 int seq_start = i;
 189                 while ( (i != m_len) && (curr_val == m_buff[i]) && ((i - seq_start) < 0xff)) {
 190                         i++;
 191                 }
 192                 if (i - seq_start > 1) {
 193                         // if there's 2 or more equal vals - put it twice in stream
 194                         enc_buff[j++] = curr_val;
 195                         enc_buff[j++] = curr_val;
 196                         enc_buff[j++] = i - seq_start;
 197                 } else {
 198                         // single value - put it as is
 199                         enc_buff[j++] = curr_val;
 200                 }
 201         }
 202
 203         outlen = j;
 204
 205         //
 206         // If using differential encoder, remember current data for
 207         // later use
 208         if ( m_use_diff ) {
 209                 memcpy(m_buff, data, m_len);
 210         }
 211
 212         return enc_buff;
 213 }
 214
 215 const uint8 * RLE_Data::Encode(const ArrayOfUInts16 &data, int &outlen, bool &changed)
 216 {
 217         // To encode, first copy the UInts16 to a uint8 array
 218         // and limit them to 0xff.
 219         // The encoded size is the size of data.
 220         int size = (int) data.size();
 221         if (size == 0) {
 222                 return Encode(0, 0, outlen, changed);
 223         }
 224         CScopedArray<uint8> buf(size);
 225         uint8 * bufPtr = buf.get();
 226
 227         for (int i = 0; i < size; i++) {
 228                 uint16 ui = data[i];
 229                 bufPtr[i] = (ui > 0xff) ? 0xff : (uint8) ui;
 230         }
 231         return Encode(bufPtr, size, outlen, changed);
 232 }
 233
 234 const uint8 * RLE_Data::Encode(const ArrayOfUInts64 &data, int &outlen, bool &changed)
 235 {
 236         // uint64 is copied to a uint8 buffer
 237         // first all low bytes, then all second low bytes and so on
 238         // so inital RLE will benefit from high bytes being equal (zero)
 239         // 0x000003045A6A7A8A, 0x000003045B6B7B8B
 240         // 8A8B7A7B6A6B5A5B0404030300000000
 241         int size = (int) data.size();
 242         if (size == 0) {
 243                 return Encode(0, 0, outlen, changed);
 244         }
 245         CScopedArray<uint8> buf(size * 8);
 246         uint8 * bufPtr = buf.get();
 247         for (int i = 0; i < size; i++) {
 248                 uint64 u = data[i];
 249                 for (int j = 0; j < 8; j++) {
 250                         bufPtr[i + j * size] = u & 0xff;
 251                         u >>= 8;
 252                 }
 253         }
 254         return Encode(bufPtr, size * 8, outlen, changed);
 255 }
 256
 257 void RLE_Data::Decode(const uint8 *data, int len, ArrayOfUInts64 &outdata)
 258 {
 259         const uint8 * decoded = Decode(data, len);
 260         wxASSERT(m_len % 8 == 0);
 261         int size = m_len / 8;
 262         outdata.resize(size);
 263         for (int i = 0; i < size; i++) {
 264                 uint64 u = 0;
 265                 for (int j = 8; j--;) {
 266                         u <<= 8;
 267                         u |= decoded[i + j * size];
 268                 }
 269                 outdata[i] = u;
 270         }
 271 }
 272
 273 void PartFileEncoderData::DecodeParts(const CECTag * tag, ArrayOfUInts16 &outdata)
 274 {
 275         const uint8 * buf = m_part_status.Decode((uint8 *)tag->GetTagData(), tag->GetTagDataLen());
 276         int size = m_part_status.Size();
 277         outdata.resize(size);
 278         for (int i = 0; i < size; i++) {
 279                 outdata[i] = buf[i];
 280         }
 281 }
 282
 283 void PartFileEncoderData::DecodeGaps(const CECTag * tag, ArrayOfUInts64 &outdata)
 284 {
 285         m_gap_status.Decode((uint8 *)tag->GetTagData(), tag->GetTagDataLen(), outdata);
 286 }
 287
 288 void PartFileEncoderData::DecodeReqs(const CECTag * tag, ArrayOfUInts64 &outdata)
 289 {
 290         m_req_status.Decode((uint8 *)tag->GetTagData(), tag->GetTagDataLen(), outdata);
 291 }
 292
 293
 294 // File_checked_for_headers