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