- introduced module Ids for agents
[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[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   if(root == NULL)
1204     {
1205       return 1;
1206     };
1207
1208   // validation test
1209   // cout << "binary tree is now created " << endl;
1210
1211   // create an array for the HuffmanCode data:
1212   fTranslationTable = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[TIMEBINS];
1213
1214   // initialise the array with validcodelengths 0 and codes = 0
1215   for(Int_t kk = 0; kk < TIMEBINS; kk++)
1216     {
1217       // validation test for correct HuffmanCode()
1218       // fTranslationTable[kk].famplitude = TIMEBINS+1; // check if eventnames are written
1219
1220       fTranslationTable[kk].famplitude = kk;
1221       fTranslationTable[kk].fhuffmancode = 0;
1222       fTranslationTable[kk].fvalidcodelength = 0;
1223       // fTranslationTable[kk].morecode = NULL;
1224     }
1225
1226   // create HuffmanCode and abort when HuffmanCode produces errors
1227   if(HuffmanCode(root,fTranslationTable) == 1)
1228     {
1229       return 1;
1230     };
1231
1232   // validation test
1233   // cout << "Huffman coding is now done " << endl;
1234
1235   // validation test
1236   // print the Huffman code table to screen
1237   // for(Int_t kk = 0; kk < TIMEBINS; kk++)
1238   //  {
1239   //    if (fTranslationTable[kk].fvalidcodelength != 0)
1240   //     cout << fTranslationTable[kk].famplitude << "   |   " << fTranslationTable[kk].fhuffmancode << "   |   " << fTranslationTable[kk].fvalidcodelength << endl;
1241   //  }
1242   
1243   // findout maximal and minimal codelength and print them out
1244     Int_t maxcodelength = fTranslationTable[0].fvalidcodelength;
1245     Int_t mincodelength = TIMEBINS;
1246
1247     for (Int_t kk = 0; kk < TIMEBINS; kk++)
1248       {
1249         //      if(fTranslationTable[kk].fvalidcodelength != 0) {cout << kk << " |  " << fTranslationTable[kk].fhuffmancode << " |  " << fTranslation "Table[kk].fvalidcodelength << endl;}
1250
1251         if(fTranslationTable[kk].fvalidcodelength > maxcodelength)
1252           { maxcodelength = fTranslationTable[kk].fvalidcodelength;};
1253         if( (fTranslationTable[kk].fvalidcodelength != 0) && (fTranslationTable[kk].fvalidcodelength < mincodelength) )
1254           { mincodelength = fTranslationTable[kk].fvalidcodelength;};
1255       }
1256
1257     // print results to screen
1258     HLTInfo("maximal codelength (DEC) = %i ", maxcodelength);
1259     HLTInfo("minimal codelength (DEC) = %i ", mincodelength);
1260   
1261     return 0;
1262 }
1263
1264 /** TTMergesort used by EntropyDecoding to sort translation table according to validcodelength from low to high */
1265 AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* AliHLTCOMPHuffmanAltro::TTMergesort(AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct *unsortedarray, Int_t n)
1266 {
1267   // see heaeder file for class documentation
1268   //divide array into two halfs: left and right (fleft.size = divlength)
1269   Int_t divlength = n >> 1;
1270       
1271   if (n==1)
1272     {
1273       // error when unsorted array = NULL
1274       if (unsortedarray == NULL)
1275         {
1276           HLTError("Error! Pointer to final merge sorted code table = NULL");
1277         };
1278
1279       return unsortedarray;
1280     }
1281   else
1282     {
1283       // sort both halfs recursively:
1284       TTMergesort(unsortedarray, divlength);  //left half
1285       TTMergesort(&unsortedarray[divlength], n-divlength); //right half
1286
1287       // merge together:
1288       // create temporary result array:   
1289       AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* temp = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[n];
1290
1291       // counters:
1292       Int_t ii, jj, kk;
1293
1294       // if left and right halves both have elements: chose the smaller one:
1295       for (ii = 0, jj = divlength, kk = 0; ii < divlength && jj < n;)
1296         {
1297           if (unsortedarray[ii].fvalidcodelength < unsortedarray[jj].fvalidcodelength)
1298             { 
1299               temp[kk] = unsortedarray[ii];
1300               ++ii;
1301             }
1302           else 
1303             {
1304               temp[kk] = unsortedarray[jj];
1305               ++jj;
1306             }
1307           
1308           // increase kk
1309           ++kk;
1310         }     
1311       
1312       // if one half is empty take elements of the other one:
1313       while (ii < divlength)
1314         {
1315           temp[kk] = unsortedarray[ii];
1316           ++kk;
1317           ++ii;
1318         }
1319       
1320       while (jj < n) 
1321         {
1322           temp[kk] = unsortedarray[jj];
1323          ++kk;
1324          ++jj;
1325         }
1326       
1327       // copy sorted temp array back into original data array
1328       for (Int_t ll = 0; ll < n; ll++)
1329         {
1330           unsortedarray[ll] = temp[ll];
1331         }
1332    
1333       // free space
1334       delete[] temp;
1335          
1336       // return pointer to original data array (which is sorted now)
1337       return unsortedarray;
1338     }
1339 }
1340
1341 /** function for the entropy decoding, needed input: code table, input data pointer and size and pointer where to write decoded data */
1342 Int_t AliHLTCOMPHuffmanAltro::EntropyDecompression()
1343 {
1344   // see heaeder file for class documentation
1345   // validation test
1346   // print translation table to screen
1347   // for(int kk= 0; kk < TIMEBINS; kk++)
1348   // {
1349   //   cout << fTranslationTable[kk].famplitude << "  |  " << fTranslationTable[kk].fhuffmancode << "  |  " << fTranslationTable[kk].fvalidcodelength << endl;
1350   // }
1351   
1352   // sort translation table according to validcodelengths from low to high (codes that occur often are found quickly)
1353    fTranslationTable = TTMergesort(fTranslationTable, TIMEBINS);
1354
1355   // validation test
1356   // print merge sorted translation table to screen
1357   // for(int kk= 0; kk < TIMEBINS; kk++)
1358   // {
1359   //     cout << fTranslationTable[kk].famplitude << "  |  " << fTranslationTable[kk].fhuffmancode << "  |  " << fTranslationTable[kk].fvalidcodelength << endl;
1360   // }
1361
1362   // do set output data first in order to know the size of the decompressed array!
1363   // take care of trailers and headers when decoding!
1364
1365   // initialise reading pointer on compressed data 
1366   AliHLTUInt64_t* pointerprop = (AliHLTUInt64_t*)fPointer2InData;
1367
1368   // initialise writing pointer for decompressed output array
1369   AliHLTUInt64_t* pointeroutputprop = (AliHLTUInt64_t*) fPointer2OutData;
1370
1371   // outputdata size initialised
1372   fOutputDataSize = 0;
1373   
1374   // validation test
1375   // cout << "input data size of encoded data (DEC) =  " << fInputDataSize << endl;
1376   // cout << "output data size of decoded data (DEC) =  " << fOutputDataSize << endl;
1377
1378   // create temporary word to read out 1 bit from, maximal length: 64 bits */
1379   AliHLTUInt64_t codedata = 0;
1380   UInt_t codedatalength = 0;
1381
1382   // number of 32-bit trailer and common data header words:
1383   UInt_t headerwords = 8;
1384   UInt_t header64 = headerwords >> 1;
1385
1386   // initialise counter variables for input array:
1387   UInt_t idxwd = header64; // due to 8*32 = 4*64 bit header words
1388   UInt_t bitpswd = 0;
1389
1390   // initialise counter variables for output array:
1391   UInt_t idxoutwd = header64; // due to 8*32 = 4*64 bit header words
1392   // UInt_t idx10out = 0; // only used for validation test
1393   UInt_t bitpsoutwd = 0;
1394
1395   // write header to output (two words input header in one word output header):
1396   UInt_t head64cntr = 0;
1397   
1398   while(head64cntr < header64)
1399     {
1400       pointeroutputprop[head64cntr] = pointerprop[head64cntr];
1401
1402       // validation test
1403       //cout << "header line in output stream (HEX) =  " << hex << pointeroutputprop[head64cntr] << dec << endl;
1404     
1405       ++head64cntr;
1406     }
1407   
1408   // end of encoded ALTRO-blocks [Byte] = finputdatasize - (number of 32-bit-trailer-words + 1) / 4 
1409   // match this with idxwd as number of 64-bit-words (endNdx[#64-bit-wds] = endNdx[#8-bit-wds]*8/64)
1410   UInt_t lastfullline = (fInputDataSize) >> 3;
1411   UInt_t lastbit = (fInputDataSize << 3) & 0x3F;
1412   UInt_t lastcodeline = lastfullline - ((fNrcuTrailerwords +1) >> 1);
1413
1414   --lastfullline;
1415   --lastcodeline;
1416
1417   if (lastbit == 0)
1418     {
1419       lastbit = 64;
1420     }
1421
1422   // initialise last valid bit position and trailer array
1423   AliHLTUInt32_t lastvalidbitpos = 0;
1424   AliHLTUInt64_t* trailer = new AliHLTUInt64_t[fNrcuTrailerwords];
1425
1426   // validation test
1427   // cout << "last bit (DEC) =  " << lastbit << endl;
1428   // cout << "lastfullline (DEC) =  " << lastfullline << endl;
1429   // cout << "lastcodeline(DEC) =  " << lastcodeline << endl;
1430   // cout << "second last code line data (HEX) = " <<  hex << pointerprop[lastcodeline-1] << dec << endl;
1431   //  cout << "last code line data (HEX) =  " << hex << pointerprop[lastcodeline] << dec << endl;
1432   // cout << "last full line data (HEX) =  " << hex << pointerprop[lastfullline] << dec << endl;
1433  
1434   // get last valid bit position (first 32 bit word in first trailer line after code
1435   // and trailerwords
1436   if (fNrcuTrailerwords < 3) // then lastfullline = only trailerline
1437     {
1438       lastvalidbitpos = (pointerprop[lastfullline] >> 32);
1439
1440       // first trailerword
1441       trailer[0] = ((pointerprop[lastfullline] << 32 ) >> 32);
1442
1443       // second trailerword
1444       if(fNrcuTrailerwords == 2)
1445         {
1446           trailer[1] = ((pointerprop[lastfullline+1] << 32) >> 32);
1447         };
1448     }
1449   else
1450     {
1451       lastvalidbitpos = (pointerprop[lastfullline-1] >> 32);
1452
1453       // first trailerword
1454       trailer[0] = ((pointerprop[lastfullline-1] << 32 ) >> 32);
1455
1456       //second trailerword
1457       trailer[1] = (pointerprop[lastfullline] >> 32);
1458
1459       // third trailerword
1460       trailer[2] =((pointerprop[lastfullline] << 32 ) >> 32);
1461     }
1462
1463   // validation test
1464   // cout << "last valid bit position (DEC) =  " << lastvalidbitpos << endl;
1465
1466   // warning if one of the trailer words is zero:
1467   for (UInt_t kk = 0; kk < fNrcuTrailerwords; kk++)
1468     {
1469       if(trailer[kk] == 0)
1470         {
1471           HLTWarning("Warning! Trailer word %i is zero",kk+1);
1472         };
1473     }
1474
1475   // validation test
1476   // print trailer array to screen
1477   // for(Int_t ii=0; ii < fNrcuTrailerwords; ii++)
1478   // {
1479   // cout << "trailerword " << ii+1 << " after getting whole trailer (HEX) =  " << hex << trailer[ii] << dec << endl;
1480   //  }
1481
1482   // find minmal validcodelength from first entry of translation table and
1483   // read in minimal validcodelength bits if codedata is zero...
1484   UInt_t minimalcodelength = fTranslationTable[0].fvalidcodelength;
1485
1486   // validation test
1487   // cout << "minimal codelength (DEC) =  " << minimalcodelength << endl;
1488
1489   Int_t readnewcode = 1; // read new code = 1; go on with old code = 0
1490
1491   // start decoding
1492   // NEW  (bitpswd >= lastvalidbitpos) instead of  (bitpswd > lastvalidbitpos)
1493   while (!((idxwd >= lastcodeline) && (bitpswd >= lastvalidbitpos)) )
1494     {
1495       if((idxwd == lastcodeline+1) && (bitpswd == 0)) break; // abortion when lastvalidbitpos = 64
1496
1497       if (codedatalength < 64) // if codedata can still get one further bit
1498         {
1499           // if new code word is read before end position
1500           if((readnewcode == 1) && !((idxwd >= lastcodeline) && (bitpswd + minimalcodelength > lastvalidbitpos)))
1501             {
1502               // codedata gets next bits from encoded input file:
1503               codedata <<= minimalcodelength; //shift bits left
1504               
1505               if (bitpswd + minimalcodelength < 65) // all bits in the same line
1506                 {
1507                   codedata |= ((pointerprop[idxwd] << bitpswd)) >> (64 - minimalcodelength); //append bits from input file to the right
1508                 }
1509               else // some of this bits in the next line
1510                 {
1511                   // append bits of current line to the right end of codedata
1512                   codedata |= (((pointerprop[idxwd] << bitpswd)) >> (bitpswd)) << (minimalcodelength - 64 + bitpswd);
1513                   
1514                   // append bits of next line to the right end of codedata
1515                   codedata |= (pointerprop[idxwd+1] >> (128 - minimalcodelength - bitpswd)); // 128 - mcl - bitpswd = 64 - (mcl - (64 - bitpswd))
1516                 }
1517               
1518               codedatalength += minimalcodelength;
1519               
1520               // new code is read, set readnewcode back to 0 again
1521               readnewcode = 0;
1522               
1523               // go and get next input bit
1524               bitpswd += minimalcodelength;
1525             }
1526           else
1527             {
1528               // codedata gets on bit after another from encoded input file:
1529               codedata <<= 1; //shift one bit left
1530               codedata |= ((pointerprop[idxwd] << bitpswd)) >> 63; //append next bit from input file to the right
1531               
1532               ++codedatalength;
1533               
1534               // go and get next input bit
1535               ++bitpswd;
1536             }
1537           
1538           // go and get next input bit
1539           if(bitpswd > 63) 
1540             {
1541               ++idxwd;
1542               bitpswd = bitpswd & 0x3F;
1543             };
1544           
1545           // compare if new codedata is in translation table:
1546           for(UInt_t kk = 0; kk < TIMEBINS; kk++)
1547             {
1548               // stopping when current codedatalength smaller than lookup validcodelength (i.e. current code not in table, read next bit)
1549               if(fTranslationTable[kk].fvalidcodelength > codedatalength)
1550                 {
1551                   break;
1552                 };
1553
1554               if(fTranslationTable[kk].fhuffmancode == codedata) //lookup bit pattern
1555                 {
1556                   if(fTranslationTable[kk].fvalidcodelength == codedatalength) //lookup correct codelength
1557                     {
1558                       // validation test
1559                       // if( idxoutwd >= 2636)
1560                       //{
1561                       //  cout << "write 10 bit word to decoded output (DEC) =  " << fTranslationTable[kk].famplitude << endl;
1562                       //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1563                       //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1564                       //}
1565                       if(bitpsoutwd + 10 < 65) //fits in old line
1566                         {
1567                           // valdidation test for end of decoded data
1568                           // print all relevant quantities to screen
1569                           //if(idxwd > 2635)
1570                           // {
1571                           //   cout << "current input in codedata (HEX) =  " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1572                           //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1573                           //  cout << "current bitpswd (DEC) =  " << bitpswd << endl;
1574                           //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1575                           //  cout << "current bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
1576                           //  cout << "decoding value (DEC) =  " << codedata << endl;
1577                           //  cout << "value length (DEC) =  " << codedatalength << endl;
1578                           //  cout << "10 bit value (HEX) =  " << hex << fTranslationTable[kk].famplitude << dec << endl;
1579                           // }
1580                           
1581                           pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << bitpsoutwd;
1582                           
1583                           // validation test
1584                           // if (idxoutwd > 362880)
1585                           // {
1586                           //   cout << "updated output line (HEX) =  " <<hex << pointeroutputprop[idxoutwd] <<dec << endl;
1587                           // }
1588                           
1589                           // goto next 10-bits output position
1590                           bitpsoutwd += 10;
1591                           
1592                           if(bitpsoutwd == 64) {bitpsoutwd = 0; ++idxoutwd;};
1593                           
1594                         }
1595                       else //needs start of new line
1596                         {
1597                           
1598                           pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << (bitpsoutwd); 
1599                           
1600                           ++idxoutwd; //start new line
1601                           
1602                           // validation test
1603                           // if(idxwd > 2635)
1604                           //{
1605                           //  cout << "current input in codedata (HEX) =  " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1606                           //  cout << "current idxwd (DEC) =  " << idxwd << endl;
1607                           //  cout << "current bitpswd (DEC) =  " << bitpswd << endl;
1608                           //  cout << "current idxoutwd (DEC) =  " << idxoutwd << endl;
1609                           //  cout << "current bitpsoutwd (DEC) =  " << bitpsoutwd << endl;
1610                           //  cout << "decoding value (DEC) =  " << codedata << endl;
1611                           //  cout << "value length (DEC) =  " << codedatalength << endl;
1612                           //  cout << "10 bit value (HEX) =  " << hex << fTranslationTable[kk].famplitude << dec << endl;
1613                           //}
1614                           
1615                           // write next line
1616                           AliHLTUInt64_t buffer = fTranslationTable[kk].famplitude;       
1617                           buffer >>= (64 - bitpsoutwd);
1618                           
1619                           pointeroutputprop[idxoutwd] = buffer;
1620                       
1621                           // validation test
1622                           // if (idxoutwd > 362880)
1623                           // {
1624                           //   cout << "new line (HEX) =  " << hex << pointeroutputprop[idxoutwd] << dec << endl;
1625                           // }
1626
1627                           // go to next bit position
1628                           bitpsoutwd -= 54;
1629                         }
1630                       
1631                       // set buffers to zero again
1632                       codedata = 0;
1633                       codedatalength = 0;
1634                       
1635                       // prepare codedata to read new code word
1636                       readnewcode = 1;
1637
1638                       // validation test
1639                       // ++idx10out;
1640
1641                       // go on with next code bits from input
1642                       break;
1643                     };
1644                 };
1645             }   
1646         }
1647       else // if *morecode is used
1648         {
1649
1650           HLTError("Error! Valid codelength for current decoding is larger than 64 bits, error in recognising the correct code");
1651
1652           return 1;
1653
1654         }
1655     }
1656
1657   // last (incomplete) line from input encoded data
1658   // after all code is read, bitpsoutwd at lastvalidbitpos
1659   // -> go to next byte (i.e. start of trailer)
1660
1661   // validation test
1662   // cout << "bit position after decoding (DEC) =  " << bitpsoutwd << endl;
1663   // cout << "line position after decoding (DEC) =  " << idxoutwd << endl;
1664
1665   // warning if byte position is not 8-bits aligned
1666   if ((bitpsoutwd & 0x07) != 0 )
1667     {
1668       HLTWarning("Warning! Bit position after decoding %i is not aligned to 8 bits", bitpsoutwd);
1669     };
1670
1671   if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1672     {
1673       pointeroutputprop[idxoutwd] <<= 32;
1674
1675       pointeroutputprop[idxoutwd] |= trailer[0]; 
1676
1677       bitpsoutwd += 32;
1678     }
1679   else
1680     {
1681       pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1682       pointeroutputprop[idxoutwd]|= (trailer[0] >> (bitpsoutwd - 32));
1683
1684       // go to next line
1685       ++idxoutwd;
1686
1687       // get rid of upper, already written bits
1688       trailer[0] <<= 96 - bitpsoutwd;
1689       trailer[0] >>= 96 - bitpsoutwd;
1690
1691       pointeroutputprop[idxoutwd] = trailer[0]; // write lower bits to next line
1692
1693       bitpsoutwd -= 32;
1694     }
1695
1696   if(fNrcuTrailerwords > 1)
1697     {
1698
1699       if(bitpsoutwd == 64)
1700         {
1701           bitpsoutwd = 0;
1702           ++idxoutwd;
1703         }
1704
1705       for(int ii = 1; ii < fNrcuTrailerwords; ii++)
1706         {
1707           // write second trailer to output data
1708           if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1709             {
1710               pointeroutputprop[idxoutwd] <<= 32;
1711               
1712               pointeroutputprop[idxoutwd] |= trailer[ii]; 
1713
1714               bitpsoutwd += 32;
1715
1716               if(bitpsoutwd == 64)
1717                 {
1718                   bitpsoutwd = 0;
1719                   ++idxoutwd;
1720                 }
1721             }
1722           else
1723             {
1724               pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1725               pointeroutputprop[idxoutwd]|= (trailer[ii] >> (bitpsoutwd - 32));
1726               
1727               // go to next line
1728               ++idxoutwd;
1729               
1730               // get rid of upper, already written bits
1731               trailer[ii] <<= 96 - bitpsoutwd;
1732               trailer[ii] >>= 96 - bitpsoutwd;
1733               
1734               pointeroutputprop[idxoutwd] = trailer[ii]; // write lower bits to next line
1735               
1736               bitpsoutwd -= 32;
1737             }
1738         }
1739     }
1740       // validation test
1741   // cout << "bitpswd after decoding (DEC) =  " << bitpswd << endl;
1742   // cout << "bitpsoutwd after decoding (DEC) =  " << bitpsoutwd << endl;
1743   // cout << "idxwd after decoding (DEC) =  " << idxwd << endl;
1744   // cout << "idxoutwd after decoding (DEC) =  " << idxoutwd << endl;
1745
1746   // write trailer to decoded output
1747
1748   // set fOutputDataSize in byte:
1749   // idxoutwd*8 = number of whole 64 bits words in byte
1750   // bitpsoutwd/8 = number of wohle 8 bits words within last idxoutwd
1751   // (bitpsoutwd%8)?1:0 = determine whether one more byte has to be used for "left over" bits
1752   fOutputDataSize = (Int_t) ((idxoutwd << 3) + (bitpsoutwd >> 3) + ((bitpsoutwd & 0x7) ? 1 : 0) );
1753   
1754   // error and abort when output data size smaller than input data size (impossible when decompressing)
1755   if(fOutputDataSize < fInputDataSize)
1756     {
1757       HLTError("Error! Data size for decompressed output stream (bytes) %i is smaller than compressed input data size (bytes)  %i", fOutputDataSize, fInputDataSize);
1758
1759       return 1;
1760     };
1761
1762   // validation test
1763   // cout << "output data size (DEC) =  " << fOutputDataSize << endl;
1764   
1765   return 0;
1766 }
1767
1768 /** CalcEntropy is to calculate entropy for 10 bits amplitudes of input data (per event only!) */
1769 Int_t AliHLTCOMPHuffmanAltro::CalcEntropy()
1770 {
1771   // see heaeder file for class documentation
1772   // create result array with TIMEBINS entries according to their abundance in the input data:
1773   UInt_t* histogrammarray = new UInt_t[TIMEBINS];
1774
1775   // initialise histrogramm:
1776   for(UInt_t jj = 0; jj < TIMEBINS; jj++)
1777     {
1778       histogrammarray[jj] = 0;
1779     }
1780
1781   // total number of counted data
1782   UInt_t totalnumber = 0;
1783
1784   fEntropy = 0.0;
1785
1786   // 10 BIT READ IN !!!
1787   AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*)fPointer2InData;
1788   
1789   // initialise required variables for input reading:
1790   AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1791   UInt_t idxwd = 8; // because of common data header words (see below)!
1792   UInt_t bitpswd = 0;
1793
1794   // number 32-bit trailer and common data header words:
1795   // Int_t fNrcuTrailerwords = 1;   // determined by user input as argument
1796   UInt_t headerwords = 8;
1797   
1798   // validation test
1799   // check if the input data size is appropriate:
1800   // cout << "size of input data in bytes (DEC) =  " << fInputDataSize << endl;
1801   
1802   // error and abort when total number of bits cannot be divided by 32:
1803   // remember that fInputDataSize is given in BYTES!
1804   if (((fInputDataSize << 3) & 0x1F) != 0)
1805     {
1806       HLTError("Error! Input data size (bytes) %i cannot be divided into 32 bit words", fInputDataSize);
1807
1808       return 1;
1809     };
1810   
1811   // error and abort when input data without trailer words cannot be divided into 10 bit words:
1812   if ((( (fInputDataSize << 3) - (fNrcuTrailerwords << 5) - (headerwords << 5)) % 10) != 0)
1813     {
1814       HLTError("Error! Input data without trailer and header words (bytes) %i cannot be divided into 10 bit words", fInputDataSize);
1815
1816       return 1;
1817     };
1818
1819   // index to watch current bit position of 10 bits words
1820   UInt_t idx10 = 0;
1821  
1822   // last valid bit for read in
1823   UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1824
1825   // start reading and encoding input data (which are 10 bit words):
1826   while (idxwd < endNdx)
1827     {
1828       // write input data in temp and cut out 10 bits with mask 0x3FF
1829       data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1830
1831       // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1832       if(bitpswd > 21)
1833         {
1834           data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1835           data10 &= 0x3FFU;
1836         };
1837
1838       // validation test
1839       // print first 10 bits words to screen
1840       // if (idx10 < 100)
1841       //  {
1842       //    cout << "read 10 bits word (HEX) =  " << hex <<  data10 << dec << endl;
1843       //  };
1844       
1845       // store abundance of data10 in histogrammarray
1846       histogrammarray[(UInt_t) data10] += 1;
1847       
1848       ++totalnumber;
1849       
1850       idx10 += 1; // go on reading 10 bit word
1851       // bit position word reads position in 32bit word when 10 bits are read out  
1852       bitpswd = (idx10 * 10) & 0x1F;
1853       idxwd = ((idx10 * 10)>>5)+8;
1854     }
1855   
1856   // validation test
1857   // print abundance table to screen
1858   // for (Int_t jj=0; jj < TIMEBINS; jj++)
1859   //  {
1860   //    cout << histogrammarray[jj] << endl;
1861   //  }
1862
1863   // save log(2) in special variable for performance gain:
1864   double l2 = log(2.0);
1865
1866   // calculate the entropy of the array 
1867   for(UInt_t jj = 0; jj < TIMEBINS; jj++)
1868     {
1869       if (histogrammarray[jj] != 0)
1870         {
1871           fEntropy += (- (Double_t) histogrammarray[jj] / (Double_t) totalnumber ) * log( ( (Double_t) histogrammarray[jj] / (Double_t) totalnumber )) / (l2);
1872         };
1873     }
1874  
1875   // free space 
1876   delete[] histogrammarray;
1877   
1878   return 0;
1879 }
1880
1881 /* CopyData is just a function for performance testing */
1882 Int_t AliHLTCOMPHuffmanAltro::CopyData()
1883 {
1884   // see heaeder file for class documentation
1885   // output data: fPointer2OutData (to 8-bit words)
1886   // initialise propagation pointer for output array
1887   AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*) fPointer2InData;
1888   AliHLTUInt32_t* pointeroutprop = (AliHLTUInt32_t*) fPointer2OutData;
1889
1890   //first output word has to be initialised
1891   pointeroutprop[0] = 0;
1892
1893   fOutputDataSize = fInputDataSize;
1894
1895   // initialise required variables for input reading:
1896   AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1897   UInt_t idxwd = 8;
1898   UInt_t idx10 = 0;
1899   UInt_t bitpswd = 0;
1900
1901   // number of 32-bit trailer and common data header words:
1902   // (taken out of compression!)
1903   // UInt_t headerwords = 8;
1904
1905   // initialise required variables for ouput creation:
1906   UInt_t idxoutwd = 0;
1907   //  Int_t bitcounter = 0; // additional test for number of read in 10 bit words
1908   // Int_t sumlength = 0;   // additional test for length of encoded file
1909   
1910   UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1911
1912   // start reading and encoding input data (which are 10 bit words):  
1913   while (idxwd < endNdx)
1914     {
1915       // write input data in temp and cut out 10 bits with mask 0x3FF
1916       data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1917       
1918       // validation test
1919       //cout << "current 10 bits word (DEC) =  " << data10 << endl;
1920           
1921           // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1922           if(bitpswd > 21)
1923             {
1924               data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1925               data10 &= 0x3FFU;
1926             };
1927
1928           // validation test
1929           // print first 10 bits words to screen
1930           // if (idx10 < 100)
1931           // {
1932           //   cout << "read data:  " << hex << data10 << dec << endl;
1933           // };
1934
1935           // write data to 32 bit output:
1936           pointeroutprop[idxoutwd] |= (data10 << bitpswd);
1937
1938           if(bitpswd > 21)
1939             {
1940               pointeroutprop[idxoutwd + 1] = (data10 >> (32 - bitpswd));
1941             }
1942
1943           // validation test
1944           // cout << "next bitpswd (DEC) =  " << bitpswd << endl;
1945
1946           ++idx10; // go on reading 10 bit word
1947           
1948           // index word reads position of 32bit word in input array
1949           idxoutwd = (idx10 * 10);
1950           bitpswd = idxoutwd & 0x1F;
1951           idxoutwd >>= 5;
1952           idxwd = idxoutwd+8;
1953           // bit position word reads position in 32bit word when 10 bits are read out  
1954     }
1955
1956   // validation test
1957   // cout << "output data size (DEC) =  " << fOutputDataSize <<  endl;
1958   // cout << "sum of codelengths (DEC) =  " << sumlength << endl;
1959   // cout << "number of 10 bits words (DEC) =  " << bitcounter << endl;
1960    
1961   return 0;
1962 }