src/RLE.cpp

   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 #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 bool RLE_Data::Realloc(int size)
  74 {
  75         if ( size == m_len ) {
  76                 return false;
  77         }
  78         if (size == 0) {
  79                 delete [] m_buff;
  80                 m_buff = 0;
  81                 m_len = 0;
  82                 return true;
  83         }
  84         uint8 *buff = new uint8[size];
  85         if (m_len == 0) {
  86                 memset(buff, 0, size);
  87         } else if ( size > m_len ) {
  88                 memset(buff + m_len, 0, size - m_len);
  89                 memcpy(buff, m_buff, m_len);
  90         } else {
  91                 memcpy(buff, m_buff, size);
  92         }
  93         delete [] m_buff;
  94         m_buff = buff;
  95
  96         m_len = size;
  97         return true;
  98 }
  99
 100 const uint8 *RLE_Data::Decode(const uint8 *buff, int len)
 101 {
 102         uint8 * decBuf = m_len ? new uint8[m_len] : 0;
 103
 104         // If data exceeds the buffer, switch to counting only.
 105         // Then resize and make a second pass.
 106         for (bool overrun = true; overrun;) {
 107                 overrun = false;
 108                 int j = 0;
 109                 for (int i = 0; i < len;) {
 110                         if (i < len - 2 && buff[i+1] == buff[i]) {
 111                                 // This is a sequence.
 112                                 uint8 seqLen = buff[i + 2];
 113                                 if (j + seqLen <= m_len) {
 114                                         memset(decBuf + j, buff[i], seqLen);
 115                                 }
 116                                 j += seqLen;
 117                                 i += 3;
 118                         } else {
 119                                 // This is a single byte.
 120                                 if (j < m_len) {
 121                                         decBuf[j] = buff[i];
 122                                 }
 123                                 j++;
 124                                 i++;
 125                         }
 126                 }
 127                 if (j != m_len) {
 128                         overrun = j > m_len;    // overrun, make a second pass
 129                         Realloc(j);                             // size has changed, adjust
 130                         if (overrun) {
 131                                 delete[] decBuf;
 132                                 decBuf = new uint8[m_len];
 133                         }
 134                 }
 135         }
 136         //
 137         // Recreate data from diff
 138         //
 139         if ( m_use_diff ) {
 140                 for (int k = 0; k < m_len; k++) {
 141                         m_buff[k] ^= decBuf[k];
 142                 }
 143         } else {
 144                 memcpy(m_buff, decBuf, m_len);
 145         }
 146         delete[] decBuf;
 147         return m_buff;
 148 }
 149
 150 const uint8 * RLE_Data::Encode(const uint8 *data, int inlen, int &outlen, bool &changed)
 151 {
 152         changed = Realloc(inlen);               // adjust size if necessary
 153
 154         if (m_len == 0) {
 155                 outlen = 0;
 156                 return NULL;
 157         }
 158         //
 159         // calculate difference from prev
 160         //
 161         if ( m_use_diff ) {
 162                 for (int i = 0; i < m_len; i++) {
 163                         m_buff[i] ^= data[i];
 164                         if (m_buff[i]) {
 165                                 changed = true;
 166                         }
 167                 }
 168         } else {
 169                 memcpy(m_buff, data, m_len);
 170                 changed = true;
 171         }
 172
 173         //
 174         // now RLE
 175         //
 176         // In worst case 2-byte sequence is encoded as 3. So, data can grow by 50%.
 177         uint8 * enc_buff = new uint8[m_len * 3/2 + 1];
 178         int i = 0, j = 0;
 179         while ( i != m_len ) {
 180                 uint8 curr_val = m_buff[i];
 181                 int seq_start = i;
 182                 while ( (i != m_len) && (curr_val == m_buff[i]) && ((i - seq_start) < 0xff)) {
 183                         i++;
 184                 }
 185                 if (i - seq_start > 1) {
 186                         // if there's 2 or more equal vals - put it twice in stream
 187                         enc_buff[j++] = curr_val;
 188                         enc_buff[j++] = curr_val;
 189                         enc_buff[j++] = i - seq_start;
 190                 } else {
 191                         // single value - put it as is
 192                         enc_buff[j++] = curr_val;
 193                 }
 194         }
 195
 196         outlen = j;
 197
 198         //
 199         // If using differential encoder, remember current data for
 200         // later use
 201         if ( m_use_diff ) {
 202                 memcpy(m_buff, data, m_len);
 203         }
 204
 205         return enc_buff;
 206 }
 207
 208 const uint8 * RLE_Data::Encode(const ArrayOfUInts16 &data, int &outlen, bool &changed)
 209 {
 210         // To encode, first copy the UInts16 to a uint8 array
 211         // and limit them to 0xff.
 212         // The encoded size is the size of data.
 213         int size = (int) data.size();
 214         if (size == 0) {
 215                 return Encode(0, 0, outlen, changed);
 216         }
 217         CScopedPtr<uint8> buf(new uint8[size]);
 218         uint8 * bufPtr = buf.get();
 219
 220         for (int i = 0; i < size; i++) {
 221                 uint16 ui = data[i];
 222                 bufPtr[i] = (ui > 0xff) ? 0xff : (uint8) ui;
 223         }
 224         return Encode(bufPtr, size, outlen, changed);
 225 }
 226
 227 const uint8 * RLE_Data::Encode(const ArrayOfUInts64 &data, int &outlen, bool &changed)
 228 {
 229         // uint64 is copied to a uint8 buffer
 230         // first all low bytes, then all second low bytes and so on
 231         // so inital RLE will benefit from high bytes being equal (zero)
 232         // 0x000003045A6A7A8A, 0x000003045B6B7B8B
 233         // 8A8B7A7B6A6B5A5B0404030300000000
 234         int size = (int) data.size();
 235         if (size == 0) {
 236                 return Encode(0, 0, outlen, changed);
 237         }
 238         CScopedPtr<uint8> buf(new uint8[size * 8]);
 239         uint8 * bufPtr = buf.get();
 240         for (int i = 0; i < size; i++) {
 241                 uint64 u = data[i];
 242                 for (int j = 0; j < 8; j++) {
 243                         bufPtr[i + j * size] = u & 0xff;
 244                         u >>= 8;
 245                 }
 246         }
 247         return Encode(bufPtr, size * 8, outlen, changed);
 248 }
 249
 250 void RLE_Data::Decode(const uint8 *data, int len, ArrayOfUInts64 &outdata)
 251 {
 252         const uint8 * decoded = Decode(data, len);
 253         wxASSERT(m_len % 8 == 0);
 254         int size = m_len / 8;
 255         outdata.resize(size);
 256         for (int i = 0; i < size; i++) {
 257                 uint64 u = 0;
 258                 for (int j = 8; j--;) {
 259                         u <<= 8;
 260                         u |= decoded[i + j * size];
 261                 }
 262                 outdata[i] = u;
 263         }
 264 }
 265
 266 void PartFileEncoderData::DecodeGaps(const CECTag * tag, ArrayOfUInts64 &outdata)
 267 {
 268         m_gap_status.Decode((uint8 *)tag->GetTagData(), tag->GetTagDataLen(), outdata);
 269 }
 270
 271
 272 // File_checked_for_headers