HLT/comp/AliHLTCOMPHuffmanAltro.cxx

   1 //-*- Mode: C++ -*-
   2 // $Id$
   3
   4 ///**************************************************************************
   5 ///* This file is property of and copyright by the ALICE HLT Project        *
   6 ///* All rights reserved.                                                   *
   7 ///*                                                                        *
   8 ///* Primary Author: Jenny Wagner  (jwagner@cern.ch)                        *
   9 ///*                                                                        *
  10 ///* Permission to use, copy, modify and distribute this software and its   *
  11 ///* documentation strictly for non-commercial purposes is hereby granted   *
  12 ///* without fee, provided that the above copyright notice appears in all   *
  13 ///* copies and that both the copyright notice and this permission notice   *
  14 ///* appear in the supporting documentation. The authors make no claims     *
  15 ///* about the suitability of this software for any purpose. It is          *
  16 ///* provided "as is" without express or implied warranty.                  *
  17 ///**************************************************************************
  18
  19 /// @file   AliHLTCOMPHuffmanAltro.cxx
  20 /// @author Jenny Wagner
  21 /// @date   29-08-2007
  22 /// @brief  The Huffman compressor
  23 ///
  24
  25 #include "AliHLTCOMPHuffmanAltro.h"
  26 #include "AliRawReaderMemory.h"
  27 #include "AliAltroRawStreamV3.h"
  28 #include <memory>
  29
  30 #if __GNUC__ >= 3
  31 using namespace std;
  32 #endif
  33
  34 #include <numeric>
  35 using std::accumulate;
  36
  37 namespace
  38 {
  39   // Helper class for std::accumulate algorithm.
  40   class AliHLTCOMPHuffmanOccurrenceSum {
  41   public:
  42     typedef int first_argument_type;
  43     typedef AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct second_argument_type;
  44     typedef bool result_type;
  45     int operator() (int a, AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct b) {
  46       return a+b.fabundance;
  47     }
  48   };
  49 } // end of namespace
  50
  51 /** ROOT macro for the implementation of ROOT specific class methods */
  52 ClassImp(AliHLTCOMPHuffmanAltro)
  53
  54 AliHLTCOMPHuffmanAltro::AliHLTCOMPHuffmanAltro()
  55   : TObject(), AliHLTLogging()
  56   , fpRawReader(NULL)
  57   , fpAltroRawStream(NULL)
  58   , fTrainingMode(0)
  59   , fCompressionSwitch(0)
  60   , fPointer2InData(NULL)
  61   , fPointer2OutData(NULL)
  62   , fInputDataSize(0)
  63   , fOutputDataSize(0)
  64   , fNrcuTrailerwords(0)
  65   , fEntropy(0.0)
  66   , fVerbosity(0)
  67   , fTrainingTable(NULL)
  68   , fTranslationTable(NULL)
  69 {
  70   // standard constructor
  71 }
  72
  73 AliHLTCOMPHuffmanAltro::AliHLTCOMPHuffmanAltro(Bool_t compressionswitch, Bool_t trainingmode, AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* translationtable, Int_t nrcutrailerwords)
  74   : TObject(), AliHLTLogging()
  75   , fpRawReader(NULL)
  76   , fpAltroRawStream(NULL)
  77   , fTrainingMode(trainingmode)
  78   , fCompressionSwitch(compressionswitch)
  79   , fPointer2InData(NULL)
  80   , fPointer2OutData(NULL)
  81   , fInputDataSize(0)
  82   , fOutputDataSize(0)
  83   , fNrcuTrailerwords(nrcutrailerwords)
  84   , fEntropy(0.0)
  85   , fVerbosity(0)
  86   , fTrainingTable(NULL)
  87   , fTranslationTable(translationtable)
  88 {
  89   // constructor
  90 }
  91
  92 AliHLTCOMPHuffmanAltro::~AliHLTCOMPHuffmanAltro()
  93 {
  94   /// destructor
  95   if (fpAltroRawStream) delete fpAltroRawStream;
  96   fpAltroRawStream=NULL;
  97   if (fpRawReader) delete fpRawReader;
  98   fpRawReader=NULL;
  99
 100   if (fTrainingTable) delete [] fTrainingTable;
 101   fTrainingTable=NULL;
 102 }
 103
 104 int AliHLTCOMPHuffmanAltro::AddInputData(UChar_t* memory, ULong_t datasize, Int_t equipmentId)
 105 {
 106   /// SetInputData takes input data pointer and input data size from component class
 107   if (memory == NULL) {
 108     return -EINVAL;
 109   };
 110
 111   // check datasize < header + trailer
 112   if (datasize <= 32 + fNrcuTrailerwords) { // 8*32 (headerwords) = 8* 4*8 (headerbytes)
 113     HLTError("Error! Size of input data less than header and trailer");
 114     return -ENODATA;
 115   }
 116
 117   // FIXME: fPointer2InData is obsolete
 118   fPointer2InData = (AliHLTUInt8_t*)memory;
 119   fInputDataSize = datasize; // size in bytes
 120
 121   if (!fpRawReader) {
 122     std::auto_ptr<AliRawReaderMemory> rawReader(new AliRawReaderMemory);
 123     std::auto_ptr<AliAltroRawStreamV3> rawStream(new AliAltroRawStreamV3(rawReader.get()));
 124
 125     if (!rawReader.get() || !rawStream.get()) {
 126       return -ENOMEM;
 127     }
 128
 129     fpRawReader=rawReader.release();
 130     fpAltroRawStream=rawStream.release();
 131   }
 132
 133   fpRawReader->AddBuffer(memory, datasize, equipmentId);
 134
 135   return 0;
 136 }
 137
 138 int AliHLTCOMPHuffmanAltro::Reset()
 139 {
 140   /// Reset and prepare for new event
 141   if (fpRawReader) {
 142     fpRawReader->ClearBuffers();
 143   }
 144   if (fpAltroRawStream) {
 145     fpAltroRawStream->Reset();
 146   }
 147
 148   InitNewTrainingTable();
 149
 150   return 0;
 151 }
 152
 153 int AliHLTCOMPHuffmanAltro::SetOutputData(AliHLTUInt8_t* outputdata, unsigned long outputsize)
 154 {
 155   /// SetOuptputData takes output data pointer and outputsize from component class
 156   if (outputdata == NULL) {
 157     return -EINVAL;
 158   };
 159
 160   fPointer2OutData = (AliHLTUInt64_t*) outputdata;
 161   fOutputDataSize = outputsize;
 162
 163   // errors: compression: when outputdatasize < inputdatasize
 164   //         decompress.: when outputdatasize < inputMultiplier * inputdatasize
 165   // this should not happen with current config in component (inputMultiplier = 4.0 for decomp and 1.0 for comp)
 166   if (fCompressionSwitch) { // compression
 167     if(outputsize < fInputDataSize) {
 168       HLTError("Error! Size of output data not equal to size of input data for compression: reserved memory space might be too small");
 169       return -ENOSPC;
 170     }
 171   } else { // decompression
 172     if(outputsize < (fInputDataSize << 1)) { // smaller than inputdatasize * 2 not possible
 173       HLTError("Error! Size of output data too small for decompression");
 174       return -ENOSPC;
 175     }
 176   }
 177
 178   return 0;
 179 }
 180
 181 unsigned long AliHLTCOMPHuffmanAltro::GetOutputDataSize()
 182 {
 183   // GetOutputDataSize delivers output data size for component class to arrange blocks for output writing
 184   // error when fOuputDataSize = 0; (not by training as there is no output when training)
 185   if((fOutputDataSize == 0) && (fTrainingMode == kFALSE)) {
 186     HLTError("Error! Calculated output data size is zero");
 187   };
 188
 189   return fOutputDataSize;
 190 }
 191
 192 int AliHLTCOMPHuffmanAltro::InitNewTrainingTable()
 193 {
 194   // Initialise training table
 195   if (!fTrainingTable) fTrainingTable =  new AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct[TIMEBINS];
 196   if (!fTrainingTable) return -ENOMEM;
 197
 198   //initialise this array:
 199   for(Int_t ii = 0; ii < TIMEBINS; ii++) {
 200     fTrainingTable[ii].famplitude = ii;
 201     fTrainingTable[ii].fabundance = 0;
 202     fTrainingTable[ii].fcode = 2; //to assure that each leaf is assigned either 0 or 1!!!
 203   }
 204
 205   return 0;
 206 }
 207
 208 int AliHLTCOMPHuffmanAltro::SetHuffmanData(AliHLTCOMPHuffmanData* huffmandata) const
 209 {
 210   // write produced code and occurrence table to Huffman Data
 211   return huffmandata->InitHuffmanData(fTrainingTable, fTranslationTable);
 212 }
 213
 214 int AliHLTCOMPHuffmanAltro::GetTrainingTable(const AliHLTCOMPHuffmanData* huffmandata)
 215 {
 216   // take translation table from HuffmanData
 217   huffmandata->GetOccurrenceTable(fTrainingTable);
 218   if (fVerbosity>0) Print("trainingtable");
 219
 220   return 0;
 221 }
 222
 223 int AliHLTCOMPHuffmanAltro::GetTranslationTable(const AliHLTCOMPHuffmanData* huffmandata)
 224 {
 225   // initialise fTranslationTable
 226   if (fTranslationTable) delete fTranslationTable;
 227   fTranslationTable = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[TIMEBINS];
 228   if (!fTranslationTable) return -ENOMEM;
 229
 230   for(Int_t kk = 0; kk < TIMEBINS; kk++) {
 231     fTranslationTable[kk].famplitude = 0;
 232     fTranslationTable[kk].fhuffmancode = 0;
 233     fTranslationTable[kk].fvalidcodelength = 0;
 234   }
 235
 236   // take translation table from HuffmanData
 237   huffmandata->GetCodeTable(fTranslationTable);
 238   if (fVerbosity>0) Print("translationtable");
 239
 240   return 0;
 241 }
 242
 243 /** ProcessData function to process data compression or decompression */
 244 void AliHLTCOMPHuffmanAltro::ProcessData()
 245 {
 246   // see header file for class documentation
 247   // set mode to process:
 248   if(fCompressionSwitch == kTRUE && fTrainingMode == kFALSE) // encoding without training
 249     {
 250       EntropyCompression();
 251
 252       // information about compression ratio
 253        HLTDebug("original filesize (bytes) = %d", fInputDataSize);
 254        HLTDebug("compressed filesize (bytes) = %d", fOutputDataSize);
 255        HLTDebug("compression ratio after Huffman encoding is %f", ((Double_t) fOutputDataSize)/fInputDataSize);
 256     }
 257   else
 258     {
 259       if(fCompressionSwitch == kTRUE && fTrainingMode == kTRUE) // encoding with training
 260         {
 261           TrainingData();
 262
 263           // information about calculated entropy (contained in GetEntropy()) and compression ratio
 264            CalcEntropy();
 265            GetEntropy();
 266         }
 267       else // decoding (no training possible, which is checked for errors by component)
 268         {
 269          EntropyDecompression();
 270
 271          // information about compression ratio
 272          HLTDebug("compressed filesize (bytes) = %d", fInputDataSize);
 273          HLTDebug("filesize after decoding (bytes) = %d", fOutputDataSize);
 274          HLTDebug("compression ratio calculated from Huffman decompressing has been %f",((Double_t) fInputDataSize)/fOutputDataSize);
 275         }
 276     }
 277 }
 278
 279 Double_t AliHLTCOMPHuffmanAltro::GetEntropy()
 280 {
 281   // Information about calculated entropy
 282   if (fVerbosity>0) HLTInfo("Calculated entropy =  %f",fEntropy);
 283
 284   return fEntropy;
 285 }
 286
 287 /** Compression: take raw input data, code table and put out entropy encoded data */
 288 Int_t AliHLTCOMPHuffmanAltro::EntropyCompression()
 289 {
 290   // see header file for class documentation
 291   // initialise input and output pointers
 292   AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*) fPointer2InData;
 293   AliHLTUInt64_t* pointeroutputprop = fPointer2OutData;
 294
 295   //first output word has to be initialised
 296   pointeroutputprop[0] = 0;
 297
 298   // initialise output size
 299   fOutputDataSize = 0;
 300
 301   // initialise required variables for input reading
 302   AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word
 303   UInt_t idxwd = 8;           // counts lines in input array (start after 8 x 32 bits header words)
 304   UInt_t idx10 = 0;           // counts 10-bits words
 305   UInt_t bitpswd = 0;         // counts current bitposition in idxwd
 306
 307   // number of 32-bits trailer and 32-bits common data header words:
 308   // (taken out of compression!)
 309   // UInt_t fNrcuTrailerwords = 1; // determined by user input as argument
 310   UInt_t headerwords = 8;
 311
 312   // initialise required variables for ouput creation:
 313   UInt_t idxoutwd = headerwords >> 1;  // counts lines in output array (start after header words)
 314   UInt_t bitpsoutwd = 0;               // counts current bitposition in idxoutwd
 315
 316   // validation test variables:
 317   //  Int_t bitcounter = 0;           // additional test for number of read in 10 bit words
 318   // Int_t sumlength = 0;             // additional test for length of encoded file
 319
 320   // error and abort when total number of bits cannot be divided by 32:
 321   // remember that fInputDataSize is given in BYTES!
 322   if (((fInputDataSize << 3) & 0x1F) != 0)
 323     {
 324       HLTError("Error! Input data size (bytes) %i cannot be divided into 32 bit words", fInputDataSize);
 325
 326       return 1;
 327     };
 328
 329   // error and abort when input data without trailer words cannot be divided into 10 bit words:
 330   if ((( (fInputDataSize << 3) - (fNrcuTrailerwords << 5) - (headerwords << 5)) % 10) != 0)
 331     {
 332       HLTError("Error! Input data (bytes) %i without trailer (bytes) %i and header words (bytes) %i cannot be divided into 10 bit words", fInputDataSize, (fNrcuTrailerwords << 2),(headerwords << 2));
 333
 334       return 1;
 335     };
 336
 337   // last line of 32-bits which is to be encoded
 338   UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
 339
 340   // write header to output (two 32-bits words input header in one 64-bits word output header):
 341   UInt_t headcntr = 0;
 342   UInt_t headwordcntr = 0;
 343
 344   while(headcntr != (headerwords >> 1))
 345     {
 346       // write first header word to the left
 347       pointeroutputprop[headcntr] = ((AliHLTUInt64_t) pointer2InData[headwordcntr]);
 348
 349       // write second header word to the right
 350       pointeroutputprop[headcntr] |= ( ((AliHLTUInt64_t) pointer2InData[headwordcntr+1]) << 32);
 351
 352       // goto next header line and next two header words
 353        ++headcntr;
 354        headwordcntr += 2;
 355     }
 356
 357     // EntropyCompression() for 10-bit values of ALTRO-Blocks:
 358     while (idxwd < endNdx)
 359       {
 360         // write input data in data10 and cut out 10 bits with mask 0x3FFU = 0011 1111 1111
 361         data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
 362
 363         // validation test
 364         // cout << "10 bit data cut out from data10 =  " << data10 << endl;
 365
 366         // if number of bits left in read input less than 10, get remaining bits from next 32-bits word
 367         if(bitpswd > 21)
 368           {
 369             // validation test
 370             // cout << "adding bits from next word at bit position  " << bitpswd << endl;
 371
 372             data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
 373             data10 &= 0x3FFU;
 374
 375             // validation test
 376             // cout << "complete 10-bits word = << data10 << endl;
 377           };
 378
 379         // validation test
 380         // print first 100 10-bits words with resp.code and validcodelength to screen...
 381         // if (idx10 < 101)
 382         //  {
 383         //    cout << "read 10-bits word (HEX) =  " << hex << data10 << dec <<" with code (DEC) =  " << fTranslationTable[data10].fhuffmancode << "  and validcodelength (DEC) =  " << fTranslationTable[data10].fvalidcodelength << endl;
 384         // };
 385
 386           // start encoding of codes with less than 65 bits codelength
 387           if(fTranslationTable[data10].fvalidcodelength < 65)
 388             {
 389               // error and abortion when validcodelength = 0
 390               if (fTranslationTable[data10].fvalidcodelength == 0)
 391                 {
 392                   HLTError("Error! Valid codelength of read 10 bit word (DEC) %i is zero", data10);
 393
 394                   return 1;
 395                 }
 396
 397               // validation test
 398               // bitcounter += 1;
 399               // sumlength += fTranslationTable[data10].fvalidcodelength;
 400
 401               if(fTranslationTable[data10].fvalidcodelength + bitpsoutwd < 64) //if new code fits in current output line
 402                 {
 403                   // validation test
 404                   // cout << "writing code (HEX) =  " << hex << fTranslationTable[data10].fhuffmancode << dec << " to line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 405
 406                   // shift line to right
 407                   pointeroutputprop[idxoutwd] <<= fTranslationTable[data10].fvalidcodelength;
 408
 409                   // append code at left side of line
 410                   pointeroutputprop[idxoutwd] |= fTranslationTable[data10].fhuffmancode;
 411
 412                   // validation test
 413                   // cout << "code written and current line updated to (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 414                 }
 415               else //if not, write lowest bits to next line
 416                 {
 417                   // validation test
 418                    // cout << "writing bits of code (HEX) =  " << hex << fTranslationTable[data10].fhuffmancode << dec << " to line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 419
 420                   // create temporary variable for performance gain:
 421                   Int_t restcode = fTranslationTable[data10].fvalidcodelength - 64 + bitpsoutwd;
 422
 423                   // shift line completely to the right
 424                   pointeroutputprop[idxoutwd] <<= (64 - bitpsoutwd);
 425
 426                   // append upper bits of code to this line
 427                   pointeroutputprop[idxoutwd] |= (fTranslationTable[data10].fhuffmancode >> (restcode));
 428
 429                   // validation test
 430                   // cout << "code bits written and current line updated to (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 431
 432                   // write lowest code bits to next line
 433
 434                   ++idxoutwd;
 435
 436                   // trick to cut out already written bits from code
 437                   AliHLTUInt64_t tempbuffer = fTranslationTable[data10].fhuffmancode;
 438                   tempbuffer <<= 64-bitpsoutwd; // shift away written code
 439                   tempbuffer >>= 64-bitpsoutwd; // shift back to get lowest bits
 440
 441                   pointeroutputprop[idxoutwd] = tempbuffer;
 442
 443                   // validation test
 444                   // cout << "code bits written and next line started as (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 445                 }
 446             }
 447           else   // if code is longer than 64 bits: use *morecode (not tested therefore left away)
 448             {
 449               HLTError("Error! Huffman Code Table does not contain codes with valid codelength longer than 64 bits");
 450
 451               return 1;
 452
 453             }
 454
 455           // validation test
 456           // cout << " current positions:" << endl;
 457           // cout << "input :  idxwd (DEC) =  " << idxwd << "   bitpswd (DEC) =  " << bitpswd << "   idx10 (DEC) =  " << idx10 << endl;
 458           // cout << "output :  idxoutwd (DEC) =  " << idxoutwd << "   bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
 459
 460           // calculate new positions
 461           bitpsoutwd = (fTranslationTable[data10].fvalidcodelength + bitpsoutwd) & 0x3F;
 462
 463           ++idx10; // go on reading 10 bit word
 464
 465           // bit position word reads position in 32bit word when 10 bits are read out
 466           bitpswd = (idx10 * 10) & 0x1F;
 467
 468           // index word reads position of 32bit word in input array
 469           idxwd = ((idx10 * 10)>>5)+8;
 470
 471           // validation test
 472           //if(idxoutwd > 2635)
 473           // {
 474           //   cout << " encoding value (HEX) = " << hex << data10 << dec << endl;
 475           //   cout << " code (HEX) = " << hex << fTranslationTable[data10].fhuffmancode << dec << endl;
 476           //   cout << " valid code length (DEC) = " << fTranslationTable[data10].fvalidcodelength << endl;
 477           //   cout << " new positions:" << endl;
 478           //   cout << "input :  idxwd (DEC) =  " << idxwd << "   bitpswd (DEC) =  " << bitpswd << "   idx10 (DEC) =  " << idx10 << endl;
 479           //   cout << "output :  idxoutwd (DEC) =  " << idxoutwd << "   bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
 480           // }
 481
 482       }// end of encoding (while loop)
 483
 484     // if new line is already started
 485     if(bitpsoutwd == 0)
 486       {
 487         --idxoutwd;
 488         bitpsoutwd = 64;
 489       }
 490     else
 491       {
 492         // fill rest of line with zeroes
 493         pointeroutputprop[idxoutwd] <<= (64 - bitpsoutwd);
 494       }
 495
 496     // next 32 bits are to memorise first bitposition after the code
 497     UInt_t lastvalidbitps = bitpsoutwd;
 498
 499     // validation test
 500     // cout << "last bitpsoutwd = lastvalidbitps (DEC) =  " << bitpsoutwd << endl;
 501
 502     // validation test
 503     // cout << "second last code line (HEX) = " <<  hex << pointeroutputprop[idxoutwd-1] << dec << endl;
 504     // cout << "last code line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 505     // cout << "idxoutwd (DEC) =  " << idxoutwd << endl;
 506
 507     // start new line and write last valid bit position and trailer words there:
 508     bitpsoutwd = 32;
 509     ++idxoutwd;
 510
 511     pointeroutputprop[idxoutwd] = lastvalidbitps;
 512
 513     // validation test
 514     // cout << "first trailer line with lastvalidbitps (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 515     // cout << "idxoutwd (DEC) =  " << idxoutwd << endl;
 516
 517     // write first trailerword
 518     bitpsoutwd = 64;
 519     pointeroutputprop[idxoutwd] <<= 32;
 520     pointeroutputprop[idxoutwd] |= pointer2InData[endNdx];
 521
 522     // validation test
 523     // cout << "first trailer line with lastvalidbitpos and first trailerword (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 524
 525     if(fNrcuTrailerwords > 1) // if there is more than one trailerword
 526       {
 527         ++idxoutwd;
 528         bitpsoutwd = 32;
 529
 530         pointeroutputprop[idxoutwd] = pointer2InData[endNdx + 1];  // write second
 531
 532         // validation test
 533         // cout << "last trailer line with second trailerword (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 534         // cout << "idxoutwd (DEC) =  " << idxoutwd << endl;
 535
 536         if (fNrcuTrailerwords == 3) // write third
 537           {
 538             bitpsoutwd = 64;
 539
 540             pointeroutputprop[idxoutwd] <<= 32;
 541             pointeroutputprop[idxoutwd] |= pointer2InData[endNdx +2];
 542
 543             // validation test
 544             // cout << "last trailer line with last trailerword (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 545           }
 546       }
 547
 548     // validation tests
 549     // cout << "file ended at current positions:" << endl;
 550     // cout << "input :  idxwd (DEC) =  " << idxwd << "   bitpswd (DEC) =  " << bitpswd << "   idx10 (DEC) =  " << idx10 << endl;
 551     // cout << "output :  idxoutwd (DEC) =  " << idxoutwd << "   bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
 552     // cout << "current output line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
 553     // cout << "sum of codelengths (DEC) =  " << sumlength << endl;
 554     // cout << "number of read 10 bit data (DEC) =  " << bitcounter << endl;
 555     // cout << "first input trailer (HEX) =  " << hex << pointer2InData[endNdx] << dec << endl;
 556
 557     // set fOutputDataSize in byte:
 558     // idxoutwd*8 = number of whole 64 bits words in byte
 559     // bitpsoutwd/8 = number of wohle 8 bits words within last idxoutwd
 560      fOutputDataSize = (Int_t) ((idxoutwd << 3) + (bitpsoutwd >> 3));
 561
 562     // error and abortion when output data size for encoding is larger than input data size
 563     if(fOutputDataSize > fInputDataSize)
 564       {
 565         HLTError("Error! Calculated data size for compressed output stream is larger than input data size");
 566
 567         return 1;
 568       };
 569
 570     // validation test
 571     // cout << "output data size (DEC) =  " << fOutputDataSize << endl;
 572
 573     return 0;
 574 }
 575
 576 /** Mergesort used by TrainingData to sort an array with n entries from high abundance to low abundance */
 577 AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct* AliHLTCOMPHuffmanAltro::Mergesort(AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct *unsortedarray, Int_t n)
 578 {
 579   // see header file for class documentation
 580   //divide array into two halfs: left and right (fleft.size = divlength)
 581   Int_t divlength = n >> 1;
 582
 583   if (n==1)
 584     {
 585       // error when unsorted array = NULL
 586       if (unsortedarray == NULL)
 587         {
 588           HLTError("Error! Pointer to final merge sorted abundance array = NULL");
 589         };
 590
 591       return unsortedarray;
 592     }
 593   else
 594     {
 595       // sort both halfs recursively:
 596       Mergesort(unsortedarray, divlength);  //left half
 597       Mergesort(&unsortedarray[divlength], n-divlength); //right half
 598
 599       // merge together:
 600       // create temporary result array:
 601       AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct* temp = new AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct[n];
 602
 603       // counters:
 604       Int_t ii, jj, kk;
 605
 606       // if left and right halves both have elements: chose the smaller one:
 607       for (ii = 0, jj = divlength, kk = 0; ii < divlength && jj < n;)
 608         {
 609           if (unsortedarray[ii].fabundance > unsortedarray[jj].fabundance)
 610             {
 611               temp[kk] = unsortedarray[ii];
 612               ++ii;
 613             }
 614           else
 615             {
 616               temp[kk] = unsortedarray[jj];
 617               ++jj;
 618             }
 619
 620           // increase kk
 621           ++kk;
 622         }
 623
 624       // if one half is empty take elements of the other one:
 625       while (ii < divlength)
 626         {
 627           temp[kk] = unsortedarray[ii];
 628           ++kk;
 629           ++ii;
 630         }
 631
 632       while (jj < n)
 633         {
 634           temp[kk] = unsortedarray[jj];
 635          ++kk;
 636          ++jj;
 637         }
 638
 639       // copy sorted temp array back into original data array
 640       for (Int_t ll = 0; ll < n; ll++)
 641         {
 642           unsortedarray[ll] = temp[ll];
 643         }
 644
 645       // free space
 646       delete[] temp;
 647
 648       // return pointer to original data array (which is sorted now)
 649       return unsortedarray;
 650     }
 651 }
 652
 653 /** CreateHuffmanTree used by TrainingData to create the binary Huffman tree */
 654 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* AliHLTCOMPHuffmanAltro::CreateHuffmanTree(AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* listroot,AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* lastelement, Int_t n)
 655 {
 656   // see header file for class documentation
 657   // initialise pointer to go through list
 658   //AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* nextpointer = listroot; // pointer for validation test below
 659  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* lastpointer = lastelement;
 660
 661   // build Huffman tree while there are still elements in the list
 662   while(n > 2)
 663     {
 664       // validation test
 665       // cout << "current number of remaining list elements n (DEC) =  " << n << endl;
 666       // cout << "current abundance of last list element (DEC) =  " << lastpointer->fleafcontents.fabundance << endl;
 667       // cout << "print all list elements from high to low to screen:" << endl;
 668       // while(nextpointer != NULL)
 669       //    {
 670       //      cout << nextpointer->fleafcontents.fabundance << endl;
 671       //      nextpointer = nextpointer->fnext;
 672       //    }
 673       // cout << " end of list " << endl;
 674
 675       // create new tree element from last two entries in orderedarray
 676      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* temptree = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct;
 677      // error if temptree = NULL
 678      if (temptree == NULL)
 679        {
 680          HLTError("Error! Allocation of Huffman binary tree failed");
 681          return NULL;
 682        };
 683
 684       // initialise the new element:
 685       temptree->fleafcontents.famplitude = TIMEBINS; //internal nodes mustn't be confused with real amplitudes (from 0 to bitsize)!
 686
 687       // validation test
 688       // cout <<"current abundance of last list element (DEC) =  " << lastpointer->fleafcontents.fabundance << endl;
 689
 690       // initialise abundance starting with last element
 691       temptree->fleafcontents.fabundance = lastpointer->fleafcontents.fabundance;
 692
 693       // code assignment small ones get 0, large ones get 1:
 694       lastpointer->fleafcontents.fcode = 0;
 695
 696       // append smallest element on the left and set pointer temptree = parent
 697       temptree->fleft = lastpointer;
 698       lastpointer->fparent = temptree;
 699
 700       // go on to second last element and set abundance, code and append on right side of the new element
 701       lastpointer = lastpointer->fprevious;
 702
 703       // validation test
 704       //  cout << "current abundance of second last list element (DEC) =  " << lastpointer->fleafcontents.fabundance << endl;
 705
 706       cout.flush();
 707
 708       temptree->fleafcontents.fabundance += lastpointer->fleafcontents.fabundance;
 709       lastpointer->fleafcontents.fcode = 1;
 710       temptree->fright = lastpointer;
 711       lastpointer->fparent = temptree;
 712
 713       temptree->fnext = NULL;
 714       temptree->fprevious = NULL;
 715       temptree->fparent = NULL;
 716
 717       // validation test
 718       // cout <<   "current abundance of temptree element = sum of leaf abundances (DEC) =  " << temptree->fleafcontents.fabundance << endl;
 719
 720       // write temptree at the suitable place according to its abundance in the list
 721       // initialise searchpointer to go through list
 722      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* search = listroot;
 723      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* sorting = listroot; // pointer from previous element
 724
 725       // check if listroot[0].fleafcontents.fabundance < temptree.fleafcontents.fabundance,
 726       // if so, make temptree new root of list
 727       if (temptree->fleafcontents.fabundance > listroot[0].fleafcontents.fabundance)
 728         {
 729           // validation test
 730           // cout << "abundance of new element (DEC) =  " << temptree->fleafcontents.fabundance << "   is larger than root abundance (DEC) =  " << listroot[0].fleafcontents.fabundance << endl;
 731
 732           // temptree = root
 733           temptree->fnext = search;
 734           search->fprevious = temptree;
 735           //temptree->fprevious = NULL // for first list element is already done!
 736           listroot = temptree;
 737         }
 738       else //sort in at the suitable point in the list
 739         {
 740           search = listroot->fnext; // go one further than listroot!
 741
 742           while(search != NULL)
 743             {
 744               // validation test
 745               // cout << "current abundance of searchpointer (DEC) =  " << searchpointer->fleafcontents.fabundance << endl;
 746
 747               // if abundance of list entry > abundance of new element, go to next element,
 748               // else sort in at that point
 749               if(search->fleafcontents.fabundance > temptree->fleafcontents.fabundance)
 750                 {
 751                   // validation test
 752                   // cout << "abundance of searchpointer (DEC) =  " << search->fleafcontents.fabundance << "   is larger than temptree abundance (DEC) =  " << temptree->fleafcontents.fabundance << endl;
 753
 754                   sorting = search;        // remember previous element
 755                   search = sorting->fnext;  // goto next element
 756                 }
 757               else
 758                 {
 759                   sorting->fnext = temptree;     //insert temptree to previous
 760                   search->fprevious = temptree;  //insert temptree to next
 761                   temptree->fprevious = sorting; // insert temptree to previous
 762                   temptree->fnext = search;      //insert temptree to next
 763
 764                   search = NULL;                //stop sorting in
 765                 }
 766             }
 767         } //end of sorting in
 768
 769       // cut the two elements out of the list:
 770
 771       lastpointer = lastpointer->fprevious;
 772       lastpointer->fnext = NULL;
 773
 774       // validation test
 775       // cout << "cutting out last two list elements, abundance of current last list element is (DEC) =  " << lastpointer->fleafcontents.fabundance << endl;
 776
 777       cout.flush();
 778
 779       // validation test
 780       // if(n <= 15)
 781       // {
 782       //   cout << "current list with new (temptree) element sorted in:" << endl;
 783
 784       //  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct * showpointer = listroot;
 785       //   while((showpointer->fnext != NULL) && (showpointer->fleafcontents.fabundance != 0))
 786       //    {
 787       //      cout << "amplitude (DEC) =  " << showpointer->fleafcontents.famplitude << "   abundance (DEC) =  " <<  showpointer->fleafcontents.fabundance << endl;
 788
 789       //      showpointer = showpointer->fnext;
 790       //    }
 791
 792       //   cout << "amplitude (DEC) =  " << showpointer->fleafcontents.famplitude << "   abundance (DEC) =  " <<  showpointer->fleafcontents.fabundance << endl;
 793       // };
 794
 795       // perform createHuffmanTree with n-1 elements:
 796       --n;
 797     }
 798
 799   // termination for n = 2:
 800
 801   // create new tree element from last two entries
 802  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* temptree = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct;
 803   // error if temptree = NULL
 804   if (temptree == NULL)
 805     {
 806       HLTError("Error! Pointer to root of Huffman binary tree = NULL");
 807       return NULL;
 808     };
 809
 810   // initialise the new element:
 811   temptree->fleafcontents.famplitude = TIMEBINS; //internal nodes mustn't be confused with real event names (from 0 to TIMEBINS)!
 812
 813   // validation test
 814   // cout << "assemble last two elements to final tree:" << endl;
 815   // cout << "abundance of last list element (DEC) =  " << lastpointer->fleafcontents.fabundance << endl;
 816
 817   // initialise abundance starting with last element
 818   temptree->fleafcontents.fabundance = lastpointer->fleafcontents.fabundance;
 819
 820   // code assignment small ones get 0, large ones get 1:
 821   lastpointer->fleafcontents.fcode = 0;
 822
 823   // append smallest element on the left:
 824   temptree->fleft = lastpointer;
 825   lastpointer->fparent = temptree;
 826
 827   // validation test
 828   // cout << "abundance of first list element (DEC) =  " << listroot->fleafcontents.fabundance << endl;
 829
 830   cout.flush();
 831
 832   // go on to second last element and set abundance, code and append on right side of the new element
 833   temptree->fleafcontents.fabundance +=listroot->fleafcontents.fabundance;
 834   listroot->fleafcontents.fcode = 1;
 835   temptree->fright = listroot;
 836   listroot->fparent = temptree;
 837
 838   temptree->fnext = NULL;
 839   temptree->fprevious = NULL;
 840   temptree->fparent = NULL;
 841
 842   // validation test
 843   // cout << "  final abundance of tree root (DEC) =  " << temptree->fleafcontents.fabundance << endl;
 844
 845   return temptree;
 846 }
 847
 848 /** HuffmanCode used by TrainingData to create the Huffman code for all leaves of the HuffmanTree */
 849 Int_t AliHLTCOMPHuffmanAltro::HuffmanCode(AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* treeroot, AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* HuffmanCodearray)
 850 {
 851   // see header file for class documentation
 852   while ((treeroot->fleft != NULL) || (treeroot->fright != NULL))
 853     {
 854       // define pointer to go through tree
 855      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* finder = treeroot;
 856
 857       // define temporary HuffmanCode struct to sort into the Huffmanarray later
 858       // array necessary for codelengths > 64 bits
 859       Int_t tempstructsize = (Int_t) ceil((double) TIMEBINS/64); // maximal codelength: TIMEBINS
 860
 861       AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* tempstruct = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[tempstructsize];
 862       if (!tempstruct) return -1;
 863
 864       for(Int_t jj = 0; jj < tempstructsize; jj++)
 865         {
 866           tempstruct[jj].fhuffmancode = 0;
 867         }
 868
 869       Int_t passednodes = 0;
 870
 871       // start searching for leaves
 872       while (1)
 873         {
 874           // if finder points at a leaf:
 875           if (finder->fright == NULL && finder->fleft == NULL)
 876             {
 877               //if it is an internal node
 878               if(finder->fleafcontents.famplitude == TIMEBINS)
 879                 {
 880                   // validation test
 881                   // cout << "found internal node with following abundance to delete (DEC) =  " << finder->fleafcontents.fabundance <<  endl;
 882
 883                   //go back to parent and delete node with 256
 884                   if (finder->fleafcontents.fcode == 0) // node was left one
 885                     {
 886                      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent;
 887                       parent->fleft = NULL;
 888                     }
 889                   else // node was right one
 890                     {
 891                      AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent;
 892                       parent->fright = NULL;
 893                     }
 894
 895                   break;
 896                 }
 897               else // if it is a leaf
 898                 {
 899                   Int_t checkright = 0; // so leaf is left children
 900
 901                   // leaf can also be a right leaf:
 902                   if (finder->fleafcontents.fcode == 1)
 903                     {
 904                       checkright = 1; // if code == 1, leaf is right children
 905                     };
 906
 907                   // write collected data in the respective array:
 908
 909                   // validation test if amplitudes are correctly found (after being initialised to TIMEBINS+1 in TrainingData()
 910                   // HuffmanCodearray[finder->fleafcontents.famplitude].famplitude = finder->fleafcontents.famplitude;
 911
 912                   // validation test
 913                   // cout << "found leaf with amplitude (DEC) =  " << finder->fleafcontents.famplitude << endl;
 914
 915                   HuffmanCodearray[finder->fleafcontents.famplitude].fvalidcodelength = passednodes;
 916
 917                   // validation test
 918                   // cout << "found leaf with validlength (DEC) =  " << HuffmanCodearray[foundleaves].fvalidcodelength << endl;
 919
 920                   //write code:
 921                   HuffmanCodearray[finder->fleafcontents.famplitude].fhuffmancode = tempstruct[0].fhuffmancode;
 922
 923                   // validation test
 924                   //cout << "found leaf with code (HEX) =  " << hex << HuffmanCodearray[finder->fleafcontents.famplitude].fhuffmancode << dec << endl;
 925
 926                   if(passednodes > 64) // if there is more code to write (not usual in normal zero-suppressed data streams!)
 927                     {
 928
 929                       HLTError("Error! Valid codelength for datum (DEC) %d is larger than 64 bits, which is not usual for normal input data", finder->fleafcontents.famplitude);
 930
 931                       delete[] tempstruct;
 932                       return 1;
 933                     }
 934
 935                   // validation test
 936                   // cout << "found leaf written after passed nodes (DEC) =  " << passednodes << endl;
 937
 938                   // deleting found leaf from tree
 939                  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent; // go one up and set pointer to leaf to zero:
 940
 941                    // validation test
 942                    // cout << "parent abundance from found leaf (DEC) =  " << finder->fleafcontents.fabundance << endl;
 943
 944                   if (checkright == 1) // if leaf is right children -> delete right
 945                     {
 946                       parent->fright = NULL;
 947                     }
 948                   else  //else: delete fleft
 949                     {
 950                       parent->fleft = NULL;
 951                     }
 952
 953                   break;
 954                 }
 955               // validation test
 956               // cout << " finder pointer at end of deleting the found leaf (DEC) =  " << finder << endl;
 957             }
 958           else // if node is not a leaf
 959             {
 960               // validation test
 961               //cout << "finder pointer to left child (DEC) =  " << finder->fleft << endl;
 962               //cout << "finder pointer to right child (DEC) =  " << finder->fright << endl;
 963
 964               if(finder->fleft != NULL)
 965                 {
 966                   finder = finder->fleft;  // pointer to children
 967
 968                   // validation test
 969                   //cout << "left child has abundance (DEC) =  " << finder->fleafcontents.fabundance << endl;
 970
 971                   // shift left to arrange space for new code element which is zero (->left!)
 972                   // i.e. nothing further needed to create code
 973
 974                   // validation test
 975                   //cout << "code for left child is created as (DEC) =  " << tempstruct->fhuffmancode << endl;
 976
 977                   //problem if passednodes > 63 --> inserting another bit becomes tricky:
 978                   if(passednodes < 64)
 979                     {
 980                       tempstruct[0].fhuffmancode = tempstruct[0].fhuffmancode << 1;
 981                     }
 982                   else // error as valid codelength should not exceed 64 bits
 983                     {
 984
 985                       HLTError("Error! Valid codelength for current encoding process becomes larger than 64 bits, which is not usual for normal input data");
 986
 987                       delete[] tempstruct;
 988                       return 1;
 989                     }
 990
 991                   // validation test
 992                   //cout << "code for left child has been written as (DEC) =  " << tempstruct->fhuffmancode << endl;
 993
 994                  ++passednodes;
 995                 }
 996               else
 997                 {
 998                   finder = finder->fright; // goto right children
 999
1000                   // validation test
1001                   //cout << "right child has abundance (DEC) =  " << finder->fleafcontents.fabundance << endl;
1002
1003                   // shift left to arrange space for new code element which is one (->right!)
1004                   // i.e. append 1 at the right end of the code via OR-function
1005
1006                   // validation test
1007                   //cout << "code for right child is created as (DEC) =  " << tempstruct->fhuffmancode << endl;
1008
1009                   //problem if passednodes > 63 --> inserting another bit becomes tricky:
1010                   if(passednodes < 64)
1011                     {
1012                       tempstruct[0].fhuffmancode = tempstruct[0].fhuffmancode << 1;
1013                       tempstruct[0].fhuffmancode = (tempstruct[0].fhuffmancode) | 1;
1014                     }
1015                   else
1016                     {
1017
1018                       HLTError("Error! Valid codelength for current encoding process becomes larger than 64 bits, which is not usual for normal input data");
1019
1020                     }
1021
1022                   // validation test
1023                   //cout << "code for right children has been written as (DEC) =  " << tempstruct->fhuffmancode << endl;
1024
1025                   ++passednodes;
1026                 } // end of right children search
1027             } // end of no-leaf-search
1028         } // end of while-loop for leaf-search
1029
1030       //freespace
1031       delete[] tempstruct;
1032     } // end of while-loop for tree != root only
1033
1034     // error when there is an amplitude = TIMEBINS in the HuffmanArray
1035     for(int jj = 0; jj < TIMEBINS; jj++)
1036       {
1037         if(HuffmanCodearray[jj].famplitude == TIMEBINS)
1038           {
1039             HLTError("Error! Internal node from Huffman tree in Huffmanarray for 10 bit word (DEC) %i", jj);
1040           };
1041       }
1042
1043     return 0;
1044 }
1045
1046 Int_t AliHLTCOMPHuffmanAltro::TrainingData()
1047 {
1048   // fill training data to create the HuffmanCode from a binary tree
1049   int iResult=0;
1050
1051   // total number of events counted
1052   Int_t totalnumber = 0;
1053
1054   if (!fpAltroRawStream) return -ENODATA;
1055   fpAltroRawStream->Reset();
1056
1057   // initialise required variables for input reading:
1058   AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1059
1060   if (!fTrainingTable && (iResult=InitNewTrainingTable())<=0)
1061     return -iResult;
1062
1063   // read altro data
1064   while (fpAltroRawStream->NextDDL()) {
1065     while (fpAltroRawStream->NextChannel()) {
1066       int iNofBunches=0;
1067       // include payload size in training table
1068       data10=fpAltroRawStream->GetChannelPayloadSize();
1069       //fTrainingTable[(Int_t)(data10)].fabundance += 1;
1070       if (fpAltroRawStream->NextBunch()) {
1071         do {
1072           // include bunch length in training table
1073           int iBunchLen=fpAltroRawStream->GetBunchLength();
1074           data10=iBunchLen;
1075           fTrainingTable[(Int_t)(data10)].fabundance += 1;
1076
1077           // include start time in training table
1078           int iStartTime=fpAltroRawStream->GetStartTimeBin();
1079           data10=iStartTime;
1080           //fTrainingTable[(Int_t)(data10)].fabundance += 1;
1081
1082           const UShort_t* signals=fpAltroRawStream->GetSignals();
1083           for (int sigpos=0; sigpos<iBunchLen-2; sigpos++) {
1084             data10=signals[sigpos];
1085             // include signals in training table
1086             fTrainingTable[(Int_t)(data10)].fabundance += 1;
1087           }
1088           iNofBunches++;
1089         } while (fpAltroRawStream->NextBunch());
1090       }
1091
1092       // increase total number of events
1093       totalnumber += 1;
1094     }
1095   }
1096
1097   fOutputDataSize = 0;
1098
1099   return 0;
1100 }
1101
1102 /** Create Huffman code table out of abundance table filled by training data in DoEvent function of component */
1103 Int_t AliHLTCOMPHuffmanAltro::CreateCodeTable()
1104 {
1105   // see header file for class documentation
1106   // using merge sort to sort the list: (stable algorithm, quick even in worst case O(nlogn))
1107   AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct* HuffmanArraySorted = Mergesort(fTrainingTable, TIMEBINS);
1108
1109   // abort when there is no pointer to sorted array (error produced in Mergesort function)
1110   if(HuffmanArraySorted == NULL)
1111     {
1112       return 1;
1113     }
1114
1115   // error and abort if list not properly sorted:
1116   // go through list and watch if current abundance of HuffmanData is always larger than next element
1117   for(int kk = 0; kk < TIMEBINS - 1; kk++)
1118     {
1119       if(HuffmanArraySorted[kk].fabundance < HuffmanArraySorted[kk+1].fabundance)
1120         {
1121           HLTError("Error! List of 10 bit word abundances not properly sorted by merge sort", "Element with 10 bit word (DEC) %i has abundance %i which is smaller than element with 10 bit word (DEC) %i with abundance %i",HuffmanArraySorted[kk].famplitude, HuffmanArraySorted[kk].fabundance, HuffmanArraySorted[kk+1].famplitude, HuffmanArraySorted[kk+1].fabundance);
1122
1123           return 1;
1124         };
1125     }
1126
1127   // validation test
1128   //cout << "merge sort for training table is now done " << endl;
1129
1130   // after mergesorting, zero arrays are last ones in array with abundance = 0
1131   //  -> count filled array entries
1132   UInt_t filled = TIMEBINS; // to ensure that every amplitude (no matter if it appears in training or not) gets a code
1133   UInt_t zeroentries = 0;  // number of non used 10 bit words (with abundance = 0)
1134
1135   // check how many 10 bit words are used ("missing channel problem)
1136   for(UInt_t kk = 0; kk < TIMEBINS; kk++)
1137     {
1138       if((HuffmanArraySorted[kk].fabundance == 0))
1139         {
1140           ++zeroentries;
1141         };
1142     }
1143
1144   // -> new array size is "filled"
1145   // validation test
1146   // cout << "number of filled array entries (DEC) =  " << filled << endl;
1147
1148   // warning when there are a lot of non used 10 bit words -> this training table cannot be used in general case and taken to encode other files
1149   if(zeroentries > 50)
1150     {
1151       HLTWarning("Warning! Only %i different 10 bit words out of %i are used, i.e. created Huffman Code table might not be optimal to encode other data", TIMEBINS-zeroentries, TIMEBINS);
1152     }
1153
1154   // FIXME use auto_ptr, use size of HuffmanArraySorted instead of TIMEBINS
1155   // initialise leaves of the tree as list (= queue) ofAliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct,
1156  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct * HuffmanTreeList = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct[filled];
1157
1158   // initialise first element
1159   HuffmanTreeList[0].fleafcontents = HuffmanArraySorted[0];
1160   HuffmanTreeList[0].fleft = NULL;
1161   HuffmanTreeList[0].fright = NULL;
1162   HuffmanTreeList[0].fnext =  &HuffmanTreeList[1];
1163   HuffmanTreeList[0].fprevious = NULL;
1164
1165   // validation test
1166   // write list to screen
1167   // cout <<"Amplitude  " << HuffmanTreeList[0].fleafcontents.famplitude << " | " << "Abundance   "<<  HuffmanTreeList[0].fleafcontents.fabundance << " | " << "Left " << HuffmanTreeList[0].fleft << " | " << "Right " << HuffmanTreeList[0].fright << " | " << "Next " << HuffmanTreeList[0].fnext << endl;
1168
1169   // initialise 1 to filled-2 elements
1170   UInt_t kk = 1;
1171   while(kk < filled-1)
1172     {
1173       HuffmanTreeList[kk].fleafcontents = HuffmanArraySorted[kk];
1174       HuffmanTreeList[kk].fleft = NULL;
1175       HuffmanTreeList[kk].fright = NULL;
1176       HuffmanTreeList[kk].fnext =  &HuffmanTreeList[kk+1];
1177       HuffmanTreeList[kk].fprevious = &HuffmanTreeList[kk-1];
1178
1179       // validation test
1180       // write list to screen
1181       // cout <<"Amplitude  " << HuffmanTreeList[kk].fleafcontents.famplitude << " | " << "Abundance   "<<  HuffmanTreeList[kk].fleafcontents.fabundance << " | " << "Left " << HuffmanTreeList[kk].fleft << " | " << "Right " << HuffmanTreeList[kk].fright << " | " << "Next " << HuffmanTreeList[kk].fnext << endl;
1182
1183       kk += 1;
1184     }
1185
1186   // initialise last list entry with next pointer to NULL
1187   HuffmanTreeList[filled-1].fleafcontents = HuffmanArraySorted[filled-1];
1188   HuffmanTreeList[filled-1].fleft = NULL;
1189   HuffmanTreeList[filled-1].fright = NULL;
1190   HuffmanTreeList[filled-1].fnext = NULL;
1191   HuffmanTreeList[filled-1].fprevious = &HuffmanTreeList[filled-2];
1192
1193   // initialise pointer to last list element:
1194  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* lastelement = &HuffmanTreeList[filled-1];
1195
1196   // validation test
1197   // write last element to screen
1198   //  cout <<"Amplitude  " << HuffmanTreeList[filled-1].fleafcontents.famplitude << " | " << "Abundance   "<<  HuffmanTreeList[filled-1].fleafcontents.fabundance << " | " << "Left " << HuffmanTreeList[filled-1].fleft << " | " << "Right " << HuffmanTreeList[filled-1].fright << " | " << "Next " << HuffmanTreeList[filled-1].fnext << endl;
1199
1200   //use this sorted list to build up the binary tree with root pointer to the beginning:
1201  AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* root = CreateHuffmanTree(HuffmanTreeList, lastelement, filled);
1202
1203   // abort if root = NULL (error already produced in CreateHuffmanTree function)
1204  delete [] HuffmanTreeList;
1205
1206   if(root == NULL)
1207     {
1208       return 1;
1209     };
1210
1211   // validation test
1212   // cout << "binary tree is now created " << endl;
1213
1214   // create an array for the HuffmanCode data:
1215   fTranslationTable = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[TIMEBINS];
1216
1217   // initialise the array with validcodelengths 0 and codes = 0
1218   for(Int_t kk1 = 0; kk1 < TIMEBINS; kk1++)
1219     {
1220       // validation test for correct HuffmanCode()
1221       // fTranslationTable[kk1].famplitude = TIMEBINS+1; // check if eventnames are written
1222
1223       fTranslationTable[kk1].famplitude = kk1;
1224       fTranslationTable[kk1].fhuffmancode = 0;
1225       fTranslationTable[kk1].fvalidcodelength = 0;
1226       // fTranslationTable[kk1].morecode = NULL;
1227     }
1228
1229   // create HuffmanCode and abort when HuffmanCode produces errors
1230   if(HuffmanCode(root,fTranslationTable) == 1)
1231     {
1232       return 1;
1233     };
1234
1235   // validation test
1236   // cout << "Huffman coding is now done " << endl;
1237
1238   // validation test
1239   // print the Huffman code table to screen
1240   // for(Int_t kk = 0; kk < TIMEBINS; kk++)
1241   //  {
1242   //    if (fTranslationTable[kk].fvalidcodelength != 0)
1243   //     cout << fTranslationTable[kk].famplitude << "   |   " << fTranslationTable[kk].fhuffmancode << "   |   " << fTranslationTable[kk].fvalidcodelength << endl;
1244   //  }
1245
1246   // findout maximal and minimal codelength and print them out
1247     UInt_t maxcodelength = fTranslationTable[0].fvalidcodelength;
1248     UInt_t mincodelength = TIMEBINS;
1249
1250     for (Int_t kk2 = 0; kk2 < TIMEBINS; kk2++)
1251       {
1252         //      if(fTranslationTable[kk2].fvalidcodelength != 0) {cout << kk2 << " |  " << fTranslationTable[kk2].fhuffmancode << " |  " << fTranslation "Table[kk2].fvalidcodelength << endl;}
1253
1254         if(fTranslationTable[kk2].fvalidcodelength > maxcodelength)
1255           { maxcodelength = fTranslationTable[kk2].fvalidcodelength;};
1256         if( (fTranslationTable[kk2].fvalidcodelength != 0) && (fTranslationTable[kk2].fvalidcodelength < mincodelength) )
1257           { mincodelength = fTranslationTable[kk2].fvalidcodelength;};
1258       }
1259
1260     // print results to screen
1261     HLTInfo("maximal codelength (DEC) = %i ", maxcodelength);
1262     HLTInfo("minimal codelength (DEC) = %i ", mincodelength);
1263
1264     return 0;
1265 }
1266
1267 /** TTMergesort used by EntropyDecoding to sort translation table according to validcodelength from low to high */
1268 AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* AliHLTCOMPHuffmanAltro::TTMergesort(AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct *unsortedarray, Int_t n)
1269 {
1270   // see heaeder file for class documentation
1271   //divide array into two halfs: left and right (fleft.size = divlength)
1272   Int_t divlength = n >> 1;
1273
1274   if (n==1)
1275     {
1276       // error when unsorted array = NULL
1277       if (unsortedarray == NULL)
1278         {
1279           HLTError("Error! Pointer to final merge sorted code table = NULL");
1280         };
1281
1282       return unsortedarray;
1283     }
1284   else
1285     {
1286       // sort both halfs recursively:
1287       TTMergesort(unsortedarray, divlength);  //left half
1288       TTMergesort(&unsortedarray[divlength], n-divlength); //right half
1289
1290       // merge together:
1291       // create temporary result array:
1292       AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* temp = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[n];
1293
1294       // counters:
1295       Int_t ii, jj, kk;
1296
1297       // if left and right halves both have elements: chose the smaller one:
1298       for (ii = 0, jj = divlength, kk = 0; ii < divlength && jj < n;)
1299         {
1300           if (unsortedarray[ii].fvalidcodelength < unsortedarray[jj].fvalidcodelength)
1301             {
1302               temp[kk] = unsortedarray[ii];
1303               ++ii;
1304             }
1305           else
1306             {
1307               temp[kk] = unsortedarray[jj];
1308               ++jj;
1309             }
1310
1311           // increase kk
1312           ++kk;
1313         }
1314
1315       // if one half is empty take elements of the other one:
1316       while (ii < divlength)
1317         {
1318           temp[kk] = unsortedarray[ii];
1319           ++kk;
1320           ++ii;
1321         }
1322
1323       while (jj < n)
1324         {
1325           temp[kk] = unsortedarray[jj];
1326          ++kk;
1327          ++jj;
1328         }
1329
1330       // copy sorted temp array back into original data array
1331       for (Int_t ll = 0; ll < n; ll++)
1332         {
1333           unsortedarray[ll] = temp[ll];
1334         }
1335
1336       // free space
1337       delete[] temp;
1338
1339       // return pointer to original data array (which is sorted now)
1340       return unsortedarray;
1341     }
1342 }
1343
1344 /** function for the entropy decoding, needed input: code table, input data pointer and size and pointer where to write decoded data */
1345 Int_t AliHLTCOMPHuffmanAltro::EntropyDecompression()
1346 {
1347   // see heaeder file for class documentation
1348   // validation test
1349   // print translation table to screen
1350   // for(int kk= 0; kk < TIMEBINS; kk++)
1351   // {
1352   //   cout << fTranslationTable[kk].famplitude << "  |  " << fTranslationTable[kk].fhuffmancode << "  |  " << fTranslationTable[kk].fvalidcodelength << endl;
1353   // }
1354
1355   // sort translation table according to validcodelengths from low to high (codes that occur often are found quickly)
1356    fTranslationTable = TTMergesort(fTranslationTable, TIMEBINS);
1357
1358   // validation test
1359   // print merge sorted translation table to screen
1360   // for(int kk= 0; kk < TIMEBINS; kk++)
1361   // {
1362   //     cout << fTranslationTable[kk].famplitude << "  |  " << fTranslationTable[kk].fhuffmancode << "  |  " << fTranslationTable[kk].fvalidcodelength << endl;
1363   // }
1364
1365   // do set output data first in order to know the size of the decompressed array!
1366   // take care of trailers and headers when decoding!
1367
1368   // initialise reading pointer on compressed data
1369   AliHLTUInt64_t* pointerprop = (AliHLTUInt64_t*)fPointer2InData;
1370
1371   // initialise writing pointer for decompressed output array
1372   AliHLTUInt64_t* pointeroutputprop = (AliHLTUInt64_t*) fPointer2OutData;
1373
1374   // outputdata size initialised
1375   fOutputDataSize = 0;
1376
1377   // validation test
1378   // cout << "input data size of encoded data (DEC) =  " << fInputDataSize << endl;
1379   // cout << "output data size of decoded data (DEC) =  " << fOutputDataSize << endl;
1380
1381   // create temporary word to read out 1 bit from, maximal length: 64 bits */
1382   AliHLTUInt64_t codedata = 0;
1383   UInt_t codedatalength = 0;
1384
1385   // number of 32-bit trailer and common data header words:
1386   UInt_t headerwords = 8;
1387   UInt_t header64 = headerwords >> 1;
1388
1389   // initialise counter variables for input array:
1390   UInt_t idxwd = header64; // due to 8*32 = 4*64 bit header words
1391   UInt_t bitpswd = 0;
1392
1393   // initialise counter variables for output array:
1394   UInt_t idxoutwd = header64; // due to 8*32 = 4*64 bit header words
1395   // UInt_t idx10out = 0; // only used for validation test
1396   UInt_t bitpsoutwd = 0;
1397
1398   // write header to output (two words input header in one word output header):
1399   UInt_t head64cntr = 0;
1400
1401   while(head64cntr < header64)
1402     {
1403       pointeroutputprop[head64cntr] = pointerprop[head64cntr];
1404
1405       // validation test
1406       //cout << "header line in output stream (HEX) =  " << hex << pointeroutputprop[head64cntr] << dec << endl;
1407
1408       ++head64cntr;
1409     }
1410
1411   // end of encoded ALTRO-blocks [Byte] = finputdatasize - (number of 32-bit-trailer-words + 1) / 4
1412   // match this with idxwd as number of 64-bit-words (endNdx[#64-bit-wds] = endNdx[#8-bit-wds]*8/64)
1413   UInt_t lastfullline = (fInputDataSize) >> 3;
1414   UInt_t lastbit = (fInputDataSize << 3) & 0x3F;
1415   UInt_t lastcodeline = lastfullline - ((fNrcuTrailerwords +1) >> 1);
1416
1417   --lastfullline;
1418   --lastcodeline;
1419
1420   if (lastbit == 0)
1421     {
1422       lastbit = 64;
1423     }
1424
1425   // initialise last valid bit position and trailer array
1426   AliHLTUInt32_t lastvalidbitpos = 0;
1427   AliHLTUInt64_t* trailer = new AliHLTUInt64_t[fNrcuTrailerwords];
1428   if (!trailer) return -1;
1429
1430   // validation test
1431   // cout << "last bit (DEC) =  " << lastbit << endl;
1432   // cout << "lastfullline (DEC) =  " << lastfullline << endl;
1433   // cout << "lastcodeline(DEC) =  " << lastcodeline << endl;
1434   // cout << "second last code line data (HEX) = " <<  hex << pointerprop[lastcodeline-1] << dec << endl;
1435   //  cout << "last code line data (HEX) =  " << hex << pointerprop[lastcodeline] << dec << endl;
1436   // cout << "last full line data (HEX) =  " << hex << pointerprop[lastfullline] << dec << endl;
1437
1438   // get last valid bit position (first 32 bit word in first trailer line after code
1439   // and trailerwords
1440   if (fNrcuTrailerwords < 3) // then lastfullline = only trailerline
1441     {
1442       lastvalidbitpos = (pointerprop[lastfullline] >> 32);
1443
1444       // first trailerword
1445       trailer[0] = ((pointerprop[lastfullline] << 32 ) >> 32);
1446
1447       // second trailerword
1448       if(fNrcuTrailerwords == 2)
1449         {
1450           trailer[1] = ((pointerprop[lastfullline+1] << 32) >> 32);
1451         };
1452     }
1453   else
1454     {
1455       lastvalidbitpos = (pointerprop[lastfullline-1] >> 32);
1456
1457       // first trailerword
1458       trailer[0] = ((pointerprop[lastfullline-1] << 32 ) >> 32);
1459
1460       //second trailerword
1461       trailer[1] = (pointerprop[lastfullline] >> 32);
1462
1463       // third trailerword
1464       trailer[2] =((pointerprop[lastfullline] << 32 ) >> 32);
1465     }
1466
1467   // validation test
1468   // cout << "last valid bit position (DEC) =  " << lastvalidbitpos << endl;
1469
1470   // warning if one of the trailer words is zero:
1471   for (UInt_t kk = 0; kk < fNrcuTrailerwords; kk++)
1472     {
1473       if(trailer[kk] == 0)
1474         {
1475           HLTWarning("Warning! Trailer word %i is zero",kk+1);
1476         };
1477     }
1478
1479   // validation test
1480   // print trailer array to screen
1481   // for(Int_t ii=0; ii < fNrcuTrailerwords; ii++)
1482   // {
1483   // cout << "trailerword " << ii+1 << " after getting whole trailer (HEX) =  " << hex << trailer[ii] << dec << endl;
1484   //  }
1485
1486   // find minmal validcodelength from first entry of translation table and
1487   // read in minimal validcodelength bits if codedata is zero...
1488   UInt_t minimalcodelength = fTranslationTable[0].fvalidcodelength;
1489
1490   // validation test
1491   // cout << "minimal codelength (DEC) =  " << minimalcodelength << endl;
1492
1493   Int_t readnewcode = 1; // read new code = 1; go on with old code = 0
1494
1495   // start decoding
1496   // NEW  (bitpswd >= lastvalidbitpos) instead of  (bitpswd > lastvalidbitpos)
1497   while (!((idxwd >= lastcodeline) && (bitpswd >= lastvalidbitpos)) )
1498     {
1499       if((idxwd == lastcodeline+1) && (bitpswd == 0)) break; // abortion when lastvalidbitpos = 64
1500
1501       if (codedatalength < 64) // if codedata can still get one further bit
1502         {
1503           // if new code word is read before end position
1504           if((readnewcode == 1) && !((idxwd >= lastcodeline) && (bitpswd + minimalcodelength > lastvalidbitpos)))
1505             {
1506               // codedata gets next bits from encoded input file:
1507               codedata <<= minimalcodelength; //shift bits left
1508
1509               if (bitpswd + minimalcodelength < 65) // all bits in the same line
1510                 {
1511                   codedata |= ((pointerprop[idxwd] << bitpswd)) >> (64 - minimalcodelength); //append bits from input file to the right
1512                 }
1513               else // some of this bits in the next line
1514                 {
1515                   // append bits of current line to the right end of codedata
1516                   codedata |= (((pointerprop[idxwd] << bitpswd)) >> (bitpswd)) << (minimalcodelength - 64 + bitpswd);
1517
1518                   // append bits of next line to the right end of codedata
1519                   codedata |= (pointerprop[idxwd+1] >> (128 - minimalcodelength - bitpswd)); // 128 - mcl - bitpswd = 64 - (mcl - (64 - bitpswd))
1520                 }
1521
1522               codedatalength += minimalcodelength;
1523
1524               // new code is read, set readnewcode back to 0 again
1525               readnewcode = 0;
1526
1527               // go and get next input bit
1528               bitpswd += minimalcodelength;
1529             }
1530           else
1531             {
1532               // codedata gets on bit after another from encoded input file:
1533               codedata <<= 1; //shift one bit left
1534               codedata |= ((pointerprop[idxwd] << bitpswd)) >> 63; //append next bit from input file to the right
1535
1536               ++codedatalength;
1537
1538               // go and get next input bit
1539               ++bitpswd;
1540             }
1541
1542           // go and get next input bit
1543           if(bitpswd > 63)
1544             {
1545               ++idxwd;
1546               bitpswd = bitpswd & 0x3F;
1547             };
1548
1549           // compare if new codedata is in translation table:
1550           for(UInt_t kk = 0; kk < TIMEBINS; kk++)
1551             {
1552               // stopping when current codedatalength smaller than lookup validcodelength (i.e. current code not in table, read next bit)
1553               if(fTranslationTable[kk].fvalidcodelength > codedatalength)
1554                 {
1555                   break;
1556                 };
1557
1558               if(fTranslationTable[kk].fhuffmancode == codedata) //lookup bit pattern
1559                 {
1560                   if(fTranslationTable[kk].fvalidcodelength == codedatalength) //lookup correct codelength
1561                     {
1562                       // validation test
1563                       // if( idxoutwd >= 2636)
1564                       //{
1565                       //  cout << "write 10 bit word to decoded output (DEC) =  " << fTranslationTable[kk].famplitude << endl;
1566                       //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1567                       //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1568                       //}
1569                       if(bitpsoutwd + 10 < 65) //fits in old line
1570                         {
1571                           // valdidation test for end of decoded data
1572                           // print all relevant quantities to screen
1573                           //if(idxwd > 2635)
1574                           // {
1575                           //   cout << "current input in codedata (HEX) =  " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1576                           //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1577                           //  cout << "current bitpswd (DEC) =  " << bitpswd << endl;
1578                           //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1579                           //  cout << "current bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
1580                           //  cout << "decoding value (DEC) =  " << codedata << endl;
1581                           //  cout << "value length (DEC) =  " << codedatalength << endl;
1582                           //  cout << "10 bit value (HEX) =  " << hex << fTranslationTable[kk].famplitude << dec << endl;
1583                           // }
1584
1585                           pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << bitpsoutwd;
1586
1587                           // validation test
1588                           // if (idxoutwd > 362880)
1589                           // {
1590                           //   cout << "updated output line (HEX) =  " <<hex << pointeroutputprop[idxoutwd] <<dec << endl;
1591                           // }
1592
1593                           // goto next 10-bits output position
1594                           bitpsoutwd += 10;
1595
1596                           if(bitpsoutwd == 64) {bitpsoutwd = 0; ++idxoutwd;};
1597
1598                         }
1599                       else //needs start of new line
1600                         {
1601
1602                           pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << (bitpsoutwd);
1603
1604                           ++idxoutwd; //start new line
1605
1606                           // validation test
1607                           // if(idxwd > 2635)
1608                           //{
1609                           //  cout << "current input in codedata (HEX) =  " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1610                           //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1611                           //  cout << "current bitpswd (DEC) =  " << bitpswd << endl;
1612                           //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1613                           //  cout << "current bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
1614                           //  cout << "decoding value (DEC) =  " << codedata << endl;
1615                           //  cout << "value length (DEC) =  " << codedatalength << endl;
1616                           //  cout << "10 bit value (HEX) =  " << hex << fTranslationTable[kk].famplitude << dec << endl;
1617                           //}
1618
1619                           // write next line
1620                           AliHLTUInt64_t buffer = fTranslationTable[kk].famplitude;
1621                           buffer >>= (64 - bitpsoutwd);
1622
1623                           pointeroutputprop[idxoutwd] = buffer;
1624
1625                           // validation test
1626                           // if (idxoutwd > 362880)
1627                           // {
1628                           //   cout << "new line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
1629                           // }
1630
1631                           // go to next bit position
1632                           bitpsoutwd -= 54;
1633                         }
1634
1635                       // set buffers to zero again
1636                       codedata = 0;
1637                       codedatalength = 0;
1638
1639                       // prepare codedata to read new code word
1640                       readnewcode = 1;
1641
1642                       // validation test
1643                       // ++idx10out;
1644
1645                       // go on with next code bits from input
1646                       break;
1647                     };
1648                 };
1649             }
1650         }
1651       else // if *morecode is used
1652         {
1653
1654           HLTError("Error! Valid codelength for current decoding is larger than 64 bits, error in recognising the correct code");
1655
1656           delete [] trailer;
1657           return 1;
1658
1659         }
1660     }
1661
1662   // last (incomplete) line from input encoded data
1663   // after all code is read, bitpsoutwd at lastvalidbitpos
1664   // -> go to next byte (i.e. start of trailer)
1665
1666   // validation test
1667   // cout << "bit position after decoding (DEC) =  " << bitpsoutwd << endl;
1668   // cout << "line position after decoding (DEC) =  " << idxoutwd << endl;
1669
1670   // warning if byte position is not 8-bits aligned
1671   if ((bitpsoutwd & 0x07) != 0 )
1672     {
1673       HLTWarning("Warning! Bit position after decoding %i is not aligned to 8 bits", bitpsoutwd);
1674     };
1675
1676   if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1677     {
1678       pointeroutputprop[idxoutwd] <<= 32;
1679
1680       pointeroutputprop[idxoutwd] |= trailer[0];
1681
1682       bitpsoutwd += 32;
1683     }
1684   else
1685     {
1686       pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1687       pointeroutputprop[idxoutwd]|= (trailer[0] >> (bitpsoutwd - 32));
1688
1689       // go to next line
1690       ++idxoutwd;
1691
1692       // get rid of upper, already written bits
1693       trailer[0] <<= 96 - bitpsoutwd;
1694       trailer[0] >>= 96 - bitpsoutwd;
1695
1696       pointeroutputprop[idxoutwd] = trailer[0]; // write lower bits to next line
1697
1698       bitpsoutwd -= 32;
1699     }
1700
1701   if(fNrcuTrailerwords > 1)
1702     {
1703
1704       if(bitpsoutwd == 64)
1705         {
1706           bitpsoutwd = 0;
1707           ++idxoutwd;
1708         }
1709
1710       for(UInt_t ii = 1; ii < fNrcuTrailerwords; ii++)
1711         {
1712           // write second trailer to output data
1713           if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1714             {
1715               pointeroutputprop[idxoutwd] <<= 32;
1716
1717               pointeroutputprop[idxoutwd] |= trailer[ii];
1718
1719               bitpsoutwd += 32;
1720
1721               if(bitpsoutwd == 64)
1722                 {
1723                   bitpsoutwd = 0;
1724                   ++idxoutwd;
1725                 }
1726             }
1727           else
1728             {
1729               pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1730               pointeroutputprop[idxoutwd]|= (trailer[ii] >> (bitpsoutwd - 32));
1731
1732               // go to next line
1733               ++idxoutwd;
1734
1735               // get rid of upper, already written bits
1736               trailer[ii] <<= 96 - bitpsoutwd;
1737               trailer[ii] >>= 96 - bitpsoutwd;
1738
1739               pointeroutputprop[idxoutwd] = trailer[ii]; // write lower bits to next line
1740
1741               bitpsoutwd -= 32;
1742             }
1743         }
1744     }
1745       // validation test
1746   // cout << "bitpswd after decoding (DEC) =  " << bitpswd << endl;
1747   // cout << "bitpsoutwd after decoding (DEC) =  " << bitpsoutwd << endl;
1748   // cout << "idxwd after decoding (DEC) =  " << idxwd << endl;
1749   // cout << "idxoutwd after decoding (DEC) =  " << idxoutwd << endl;
1750
1751   // write trailer to decoded output
1752
1753   // set fOutputDataSize in byte:
1754   // idxoutwd*8 = number of whole 64 bits words in byte
1755   // bitpsoutwd/8 = number of wohle 8 bits words within last idxoutwd
1756   // (bitpsoutwd%8)?1:0 = determine whether one more byte has to be used for "left over" bits
1757   fOutputDataSize = (Int_t) ((idxoutwd << 3) + (bitpsoutwd >> 3) + ((bitpsoutwd & 0x7) ? 1 : 0) );
1758
1759   delete [] trailer;
1760   // error and abort when output data size smaller than input data size (impossible when decompressing)
1761   if(fOutputDataSize < fInputDataSize)
1762     {
1763       HLTError("Error! Data size for decompressed output stream (bytes) %i is smaller than compressed input data size (bytes)  %i", fOutputDataSize, fInputDataSize);
1764
1765       return 1;
1766     };
1767
1768   // validation test
1769   // cout << "output data size (DEC) =  " << fOutputDataSize << endl;
1770
1771   return 0;
1772 }
1773
1774 Int_t AliHLTCOMPHuffmanAltro::CalcEntropy(const AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct* occurrencetable)
1775 {
1776   // calculate entropy of 10 bit values
1777   if (!occurrencetable) occurrencetable=fTrainingTable;
1778   if (!occurrencetable) return -ENODATA;
1779
1780   int totalnumber=accumulate(occurrencetable, occurrencetable+TIMEBINS, int(0), AliHLTCOMPHuffmanOccurrenceSum());
1781   if (totalnumber<1) {
1782     HLTWarning("can not calculate entropy from empty table");
1783     fEntropy=0.0;
1784     return 0;
1785   }
1786
1787   double entropy=0.0;
1788   const double l2 = log(2.0);
1789   for(UInt_t jj = 0; jj < TIMEBINS; jj++) {
1790     double value=occurrencetable[jj].fabundance;
1791     if (value<1.0) continue;
1792     entropy += (- (Double_t) value / (Double_t) totalnumber ) * log( ( (Double_t) value / (Double_t) totalnumber )) / (l2);
1793   }
1794
1795   fEntropy=entropy;
1796   return 0;
1797 }
1798
1799 /* CopyData is just a function for performance testing */
1800 Int_t AliHLTCOMPHuffmanAltro::CopyData()
1801 {
1802   // see heaeder file for class documentation
1803   // output data: fPointer2OutData (to 8-bit words)
1804   // initialise propagation pointer for output array
1805   AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*) fPointer2InData;
1806   AliHLTUInt32_t* pointeroutprop = (AliHLTUInt32_t*) fPointer2OutData;
1807
1808   //first output word has to be initialised
1809   pointeroutprop[0] = 0;
1810
1811   fOutputDataSize = fInputDataSize;
1812
1813   // initialise required variables for input reading:
1814   AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1815   UInt_t idxwd = 8;
1816   UInt_t idx10 = 0;
1817   UInt_t bitpswd = 0;
1818
1819   // number of 32-bit trailer and common data header words:
1820   // (taken out of compression!)
1821   // UInt_t headerwords = 8;
1822
1823   // initialise required variables for ouput creation:
1824   UInt_t idxoutwd = 0;
1825   //  Int_t bitcounter = 0; // additional test for number of read in 10 bit words
1826   // Int_t sumlength = 0;   // additional test for length of encoded file
1827
1828   UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1829
1830   // start reading and encoding input data (which are 10 bit words):
1831   while (idxwd < endNdx)
1832     {
1833       // write input data in temp and cut out 10 bits with mask 0x3FF
1834       data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1835
1836       // validation test
1837       //cout << "current 10 bits word (DEC) =  " << data10 << endl;
1838
1839           // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1840           if(bitpswd > 21)
1841             {
1842               data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1843               data10 &= 0x3FFU;
1844             };
1845
1846           // validation test
1847           // print first 10 bits words to screen
1848           // if (idx10 < 100)
1849           // {
1850           //   cout << "read data:  " << hex << data10 << dec << endl;
1851           // };
1852
1853           // write data to 32 bit output:
1854           pointeroutprop[idxoutwd] |= (data10 << bitpswd);
1855
1856           if(bitpswd > 21)
1857             {
1858               pointeroutprop[idxoutwd + 1] = (data10 >> (32 - bitpswd));
1859             }
1860
1861           // validation test
1862           // cout << "next bitpswd (DEC) =  " << bitpswd << endl;
1863
1864           ++idx10; // go on reading 10 bit word
1865
1866           // index word reads position of 32bit word in input array
1867           idxoutwd = (idx10 * 10);
1868           bitpswd = idxoutwd & 0x1F;
1869           idxoutwd >>= 5;
1870           idxwd = idxoutwd+8;
1871           // bit position word reads position in 32bit word when 10 bits are read out
1872     }
1873
1874   // validation test
1875   // cout << "output data size (DEC) =  " << fOutputDataSize <<  endl;
1876   // cout << "sum of codelengths (DEC) =  " << sumlength << endl;
1877   // cout << "number of 10 bits words (DEC) =  " << bitcounter << endl;
1878
1879   return 0;
1880 }
1881
1882 void AliHLTCOMPHuffmanAltro::Print(Option_t* option) const
1883 {
1884   // print content
1885
1886   if (strcmp(option, "trainingtable")==0) {
1887     // print fTrainingTable to screen (non-zero entries only):
1888     if (!fTrainingTable) {
1889       cout << "no training table" << endl;
1890       return;
1891     }
1892     for(Int_t jj = 0; jj < TIMEBINS; jj++) {
1893       if(fTrainingTable[jj].fabundance != 0)
1894         cout << jj << "  |  " << fTrainingTable[jj].famplitude << "  |  " << fTrainingTable[jj].fabundance << endl;
1895     }
1896     return;
1897   }
1898
1899   if (strcmp(option, "translationtable")==0) {
1900     // print fTranslationTable to screen (non-zero entries only):
1901     if (!fTranslationTable) {
1902       cout << "no translation table" << endl;
1903       return;
1904     }
1905     for(Int_t jj = 0; jj < TIMEBINS; jj++) {
1906       if(fTranslationTable[jj].fvalidcodelength != 0)
1907         cout << jj << "  |  " << fTranslationTable[jj].fhuffmancode << "  |  " << fTranslationTable[jj].fvalidcodelength << endl;
1908     }
1909     return;
1910   }
1911
1912   if (strcmp(option, "entropy")==0) {
1913     cout << "Calculated entropy = " << fEntropy << endl;
1914     return;
1915   }
1916 }