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