3 /**************************************************************************
4 * This file is property of and copyright by the ALICE HLT Project *
5 * All rights reserved. *
7 * Primary Author: Jenny Wagner (jwagner@cern.ch) *
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 **************************************************************************/
18 /** @file AliHLTCOMPHuffmanAltro.cxx
21 @brief The Huffman compressor
24 #include "AliHLTCOMPHuffmanAltro.h"
30 ClassImp(AliHLTCOMPHuffmanAltro)
32 /** construction without any arguments (used for isolated tests) */
33 AliHLTCOMPHuffmanAltro::AliHLTCOMPHuffmanAltro()
36 fCompressionSwitch(0),
37 fPointer2InData(NULL),
38 fPointer2OutData(NULL),
44 fTranslationTable(NULL)
46 // see header file for class documentation
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)
53 fCompressionSwitch(0),
54 fPointer2InData(NULL),
55 fPointer2OutData(NULL),
61 fTranslationTable(NULL)
63 // see header file for class documentation
64 // initialise member variables
65 fCompressionSwitch = compressionswitch;
66 fTrainingMode = trainingmode;
67 fTranslationTable = translationtable;
68 fNrcuTrailerwords = nrcutrailerwords;
72 /** EntropyEncoder destructor */
73 AliHLTCOMPHuffmanAltro::~AliHLTCOMPHuffmanAltro()
75 /* destructor, see header file for class documentation */
78 /** SetInputData takes input data pointer and input data size from component class */
79 void AliHLTCOMPHuffmanAltro::SetInputData(void* inputdata, unsigned long datasize)
81 // see header file for class documentation
82 fPointer2InData = (AliHLTUInt8_t*)inputdata;
83 fInputDataSize = datasize; // size in bytes
85 // error when inputdata = NULL
86 if (inputdata == NULL)
88 HLTError("Error! Pointer to input data == NULL");
91 // error when datasize < header + trailer
92 if (datasize <= 32 + fNrcuTrailerwords) // 8*32 (headerwords) = 8* 4*8 (headerbytes)
94 HLTError("Error! Size of input data less than header and trailer");
99 /** SetOuptputData takes output data pointer and outputsize from component class */
100 void AliHLTCOMPHuffmanAltro::SetOutputData(AliHLTUInt8_t* outputdata, unsigned long outputsize)
102 // see header file for class documentation
103 fPointer2OutData = (AliHLTUInt64_t*) outputdata;
104 fOutputDataSize = outputsize;
106 // error when outputdata = NULL
107 if (outputdata == NULL)
109 HLTError("Error! Pointer to output data == NULL");
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
117 if(outputsize < fInputDataSize)
119 HLTError("Error! Size of output data not equal to size of input data for compression: reserved memory space might be too small");
122 else // decompression
124 if(outputsize < (fInputDataSize << 1)) // smaller than inputdatasize * 2 not possible
126 HLTError("Error! Size of output data too small for decompression");
131 /** GetOutputDataSize delivers output data size for component class to arrange blocks for output writing */
132 unsigned long AliHLTCOMPHuffmanAltro::GetOutputDataSize()
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))
138 HLTError("Error! Calculated output data size is zero");
141 return fOutputDataSize;
144 /** Initialise training table */
145 void AliHLTCOMPHuffmanAltro::InitNewTrainingTable()
147 // see header file for class documentation
148 // define array for training table with amplitudes and abundances
149 fTrainingTable = new AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct[TIMEBINS];
151 //initialise this array:
152 for(Int_t ii = 0; ii < TIMEBINS; ii++)
155 fTrainingTable[ii].famplitude = ii;
157 fTrainingTable[ii].fabundance = 0;
159 fTrainingTable[ii].fcode = 2; //to assure that each leaf is assigned either 0 or 1!!!
164 /** write produced code and occurrence table to Huffman Data */
165 void AliHLTCOMPHuffmanAltro::SetHuffmanData(AliHLTCOMPHuffmanData* huffmandata)
167 // see header file for class documentation
168 huffmandata->InitHuffmanData(fTrainingTable, fTranslationTable);
171 /** GetTrainingTable delivers training table for statistics */
172 void AliHLTCOMPHuffmanAltro::GetTrainingTable(AliHLTCOMPHuffmanData* huffmandata)
174 // see header file for class documentation
175 // take translation table from HuffmanData
176 fTrainingTable = huffmandata->GetOccurrenceTable(fTrainingTable);
178 // print fTrainingTable to screen (non-zero entries only):
179 // for(Int_t jj = 0; jj < TIMEBINS; jj++)
181 // if(fTrainingTable[jj].fabundance != 0)
182 // cout << jj << " | " << fTrainingTable[jj].famplitude << " | " << fTrainingTable[jj].fabundance << endl;
185 // error when no training table available
186 if (fTrainingTable == NULL)
188 HLTError("Error! Pointer to training table = NULL");
192 /** initialisation of the code table for the Huffman compressor/ decompressor */
193 void AliHLTCOMPHuffmanAltro::GetTranslationTable(AliHLTCOMPHuffmanData* huffmandata)
195 // see header file for class documentation
196 // initialise fTranslationTable to be read from a file:
197 fTranslationTable = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[TIMEBINS];
199 for(Int_t kk = 0; kk < TIMEBINS; kk++)
201 fTranslationTable[kk].famplitude = 0;
202 fTranslationTable[kk].fhuffmancode = 0;
203 // fTranslationTable[kk].morecode = NULL;
204 fTranslationTable[kk].fvalidcodelength = 0;
207 // take translation table from HuffmanData
208 fTranslationTable = huffmandata->GetCodeTable(fTranslationTable);
210 // print fTranlsationTable to screen (non-zero entries only):
211 // for(Int_t jj = 0; jj < TIMEBINS; jj++)
213 // if(fTranslationTable[jj].fvalidcodelength != 0)
214 // cout << jj << " | " << fTranslationTable[jj].fhuffmancode << " | " << fTranslationTable[jj].fvalidcodelength << endl;
217 // error when fTranslationTable = NULL
218 if (fTranslationTable == NULL)
220 HLTError("Error! Pointer to Huffman coding table = NULL");
224 /** ProcessData function to process data compression or decompression */
225 void AliHLTCOMPHuffmanAltro::ProcessData()
227 // see header file for class documentation
228 // set mode to process:
229 if(fCompressionSwitch == kTRUE && fTrainingMode == kFALSE) // encoding without training
231 EntropyCompression();
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);
240 if(fCompressionSwitch == kTRUE && fTrainingMode == kTRUE) // encoding with training
244 // information about calculated entropy (contained in GetEntropy()) and compression ratio
248 else // decoding (no training possible, which is checked for errors by component)
250 EntropyDecompression();
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);
260 /** GetEntropy returns entropy and prints it to screen */
261 Double_t AliHLTCOMPHuffmanAltro::GetEntropy()
263 // see header file for class documentation
264 // Information about calculated entropy
265 HLTInfo("Calculated entropy = %f",fEntropy);
270 /** Compression: take raw input data, code table and put out entropy encoded data */
271 Int_t AliHLTCOMPHuffmanAltro::EntropyCompression()
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;
278 //first output word has to be initialised
279 pointeroutputprop[0] = 0;
281 // initialise output size
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
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;
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
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
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)
307 HLTError("Error! Input data size (bytes) %i cannot be divided into 32 bit words", fInputDataSize);
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)
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));
320 // last line of 32-bits which is to be encoded
321 UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
323 // write header to output (two 32-bits words input header in one 64-bits word output header):
325 UInt_t headwordcntr = 0;
327 while(headcntr != (headerwords >> 1))
329 // write first header word to the left
330 pointeroutputprop[headcntr] = ((AliHLTUInt64_t) pointer2InData[headwordcntr]);
332 // write second header word to the right
333 pointeroutputprop[headcntr] |= ( ((AliHLTUInt64_t) pointer2InData[headwordcntr+1]) << 32);
335 // goto next header line and next two header words
340 // EntropyCompression() for 10-bit values of ALTRO-Blocks:
341 while (idxwd < endNdx)
343 // write input data in data10 and cut out 10 bits with mask 0x3FFU = 0011 1111 1111
344 data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
347 // cout << "10 bit data cut out from data10 = " << data10 << endl;
349 // if number of bits left in read input less than 10, get remaining bits from next 32-bits word
353 // cout << "adding bits from next word at bit position " << bitpswd << endl;
355 data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
359 // cout << "complete 10-bits word = << data10 << endl;
363 // print first 100 10-bits words with resp.code and validcodelength to screen...
366 // cout << "read 10-bits word (HEX) = " << hex << data10 << dec <<" with code (DEC) = " << fTranslationTable[data10].fhuffmancode << " and validcodelength (DEC) = " << fTranslationTable[data10].fvalidcodelength << endl;
369 // start encoding of codes with less than 65 bits codelength
370 if(fTranslationTable[data10].fvalidcodelength < 65)
372 // error and abortion when validcodelength = 0
373 if (fTranslationTable[data10].fvalidcodelength == 0)
375 HLTError("Error! Valid codelength of read 10 bit word (DEC) %i is zero", data10);
382 // sumlength += fTranslationTable[data10].fvalidcodelength;
384 if(fTranslationTable[data10].fvalidcodelength + bitpsoutwd < 64) //if new code fits in current output line
387 // cout << "writing code (HEX) = " << hex << fTranslationTable[data10].fhuffmancode << dec << " to line (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
389 // shift line to right
390 pointeroutputprop[idxoutwd] <<= fTranslationTable[data10].fvalidcodelength;
392 // append code at left side of line
393 pointeroutputprop[idxoutwd] |= fTranslationTable[data10].fhuffmancode;
396 // cout << "code written and current line updated to (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
398 else //if not, write lowest bits to next line
401 // cout << "writing bits of code (HEX) = " << hex << fTranslationTable[data10].fhuffmancode << dec << " to line (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
403 // create temporary variable for performance gain:
404 Int_t restcode = fTranslationTable[data10].fvalidcodelength - 64 + bitpsoutwd;
406 // shift line completely to the right
407 pointeroutputprop[idxoutwd] <<= (64 - bitpsoutwd);
409 // append upper bits of code to this line
410 pointeroutputprop[idxoutwd] |= (fTranslationTable[data10].fhuffmancode >> (restcode));
413 // cout << "code bits written and current line updated to (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
415 // write lowest code bits to next line
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
424 pointeroutputprop[idxoutwd] = tempbuffer;
427 // cout << "code bits written and next line started as (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
430 else // if code is longer than 64 bits: use *morecode (not tested therefore left away)
432 HLTError("Error! Huffman Code Table does not contain codes with valid codelength longer than 64 bits");
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;
443 // calculate new positions
444 bitpsoutwd = (fTranslationTable[data10].fvalidcodelength + bitpsoutwd) & 0x3F;
446 ++idx10; // go on reading 10 bit word
448 // bit position word reads position in 32bit word when 10 bits are read out
449 bitpswd = (idx10 * 10) & 0x1F;
451 // index word reads position of 32bit word in input array
452 idxwd = ((idx10 * 10)>>5)+8;
455 //if(idxoutwd > 2635)
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;
465 }// end of encoding (while loop)
467 // if new line is already started
475 // fill rest of line with zeroes
476 pointeroutputprop[idxoutwd] <<= (64 - bitpsoutwd);
479 // next 32 bits are to memorise first bitposition after the code
480 UInt_t lastvalidbitps = bitpsoutwd;
483 // cout << "last bitpsoutwd = lastvalidbitps (DEC) = " << bitpsoutwd << endl;
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;
490 // start new line and write last valid bit position and trailer words there:
494 pointeroutputprop[idxoutwd] = lastvalidbitps;
497 // cout << "first trailer line with lastvalidbitps (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
498 // cout << "idxoutwd (DEC) = " << idxoutwd << endl;
500 // write first trailerword
502 pointeroutputprop[idxoutwd] <<= 32;
503 pointeroutputprop[idxoutwd] |= pointer2InData[endNdx];
506 // cout << "first trailer line with lastvalidbitpos and first trailerword (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
508 if(fNrcuTrailerwords > 1) // if there is more than one trailerword
513 pointeroutputprop[idxoutwd] = pointer2InData[endNdx + 1]; // write second
516 // cout << "last trailer line with second trailerword (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
517 // cout << "idxoutwd (DEC) = " << idxoutwd << endl;
519 if (fNrcuTrailerwords == 3) // write third
523 pointeroutputprop[idxoutwd] <<= 32;
524 pointeroutputprop[idxoutwd] |= pointer2InData[endNdx +2];
527 // cout << "last trailer line with last trailerword (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
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;
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));
545 // error and abortion when output data size for encoding is larger than input data size
546 if(fOutputDataSize > fInputDataSize)
548 HLTError("Error! Calculated data size for compressed output stream is larger than input data size");
554 // cout << "output data size (DEC) = " << fOutputDataSize << endl;
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)
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;
568 // error when unsorted array = NULL
569 if (unsortedarray == NULL)
571 HLTError("Error! Pointer to final merge sorted abundance array = NULL");
574 return unsortedarray;
578 // sort both halfs recursively:
579 Mergesort(unsortedarray, divlength); //left half
580 Mergesort(&unsortedarray[divlength], n-divlength); //right half
583 // create temporary result array:
584 AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct* temp = new AliHLTCOMPHuffmanOccurrenceData::AliHLTCOMPHuffmanDataStruct[n];
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;)
592 if (unsortedarray[ii].fabundance > unsortedarray[jj].fabundance)
594 temp[kk] = unsortedarray[ii];
599 temp[kk] = unsortedarray[jj];
607 // if one half is empty take elements of the other one:
608 while (ii < divlength)
610 temp[kk] = unsortedarray[ii];
617 temp[kk] = unsortedarray[jj];
622 // copy sorted temp array back into original data array
623 for (Int_t ll = 0; ll < n; ll++)
625 unsortedarray[ll] = temp[ll];
631 // return pointer to original data array (which is sorted now)
632 return unsortedarray;
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)
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;
644 // build Huffman tree while there are still elements in the list
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)
653 // cout << nextpointer->fleafcontents.fabundance << endl;
654 // nextpointer = nextpointer->fnext;
656 // cout << " end of list " << endl;
658 // create new tree element from last two entries in orderedarray
659 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* temptree = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct;
661 // initialise the new element:
662 temptree->fleafcontents.famplitude = TIMEBINS; //internal nodes mustn't be confused with real amplitudes (from 0 to bitsize)!
665 // cout <<"current abundance of last list element (DEC) = " << lastpointer->fleafcontents.fabundance << endl;
667 // initialise abundance starting with last element
668 temptree->fleafcontents.fabundance = lastpointer->fleafcontents.fabundance;
670 // code assignment small ones get 0, large ones get 1:
671 lastpointer->fleafcontents.fcode = 0;
673 // append smallest element on the left and set pointer temptree = parent
674 temptree->fleft = lastpointer;
675 lastpointer->fparent = temptree;
677 // go on to second last element and set abundance, code and append on right side of the new element
678 lastpointer = lastpointer->fprevious;
681 // cout << "current abundance of second last list element (DEC) = " << lastpointer->fleafcontents.fabundance << endl;
685 temptree->fleafcontents.fabundance += lastpointer->fleafcontents.fabundance;
686 lastpointer->fleafcontents.fcode = 1;
687 temptree->fright = lastpointer;
688 lastpointer->fparent = temptree;
690 temptree->fnext = NULL;
691 temptree->fprevious = NULL;
692 temptree->fparent = NULL;
695 // cout << "current abundance of temptree element = sum of leaf abundances (DEC) = " << temptree->fleafcontents.fabundance << endl;
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
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)
707 // cout << "abundance of new element (DEC) = " << temptree->fleafcontents.fabundance << " is larger than root abundance (DEC) = " << listroot[0].fleafcontents.fabundance << endl;
710 temptree->fnext = search;
711 search->fprevious = temptree;
712 //temptree->fprevious = NULL // for first list element is already done!
715 else //sort in at the suitable point in the list
717 search = listroot->fnext; // go one further than listroot!
719 while(search != NULL)
722 // cout << "current abundance of searchpointer (DEC) = " << searchpointer->fleafcontents.fabundance << endl;
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)
729 // cout << "abundance of searchpointer (DEC) = " << search->fleafcontents.fabundance << " is larger than temptree abundance (DEC) = " << temptree->fleafcontents.fabundance << endl;
731 sorting = search; // remember previous element
732 search = sorting->fnext; // goto next element
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
741 search = NULL; //stop sorting in
744 } //end of sorting in
746 // cut the two elements out of the list:
748 lastpointer = lastpointer->fprevious;
749 lastpointer->fnext = NULL;
752 // cout << "cutting out last two list elements, abundance of current last list element is (DEC) = " << lastpointer->fleafcontents.fabundance << endl;
759 // cout << "current list with new (temptree) element sorted in:" << endl;
761 // AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct * showpointer = listroot;
762 // while((showpointer->fnext != NULL) && (showpointer->fleafcontents.fabundance != 0))
764 // cout << "amplitude (DEC) = " << showpointer->fleafcontents.famplitude << " abundance (DEC) = " << showpointer->fleafcontents.fabundance << endl;
766 // showpointer = showpointer->fnext;
769 // cout << "amplitude (DEC) = " << showpointer->fleafcontents.famplitude << " abundance (DEC) = " << showpointer->fleafcontents.fabundance << endl;
772 // perform createHuffmanTree with n-1 elements:
776 // termination for n = 2:
778 // create new tree element from last two entries
779 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* temptree = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct;
781 // initialise the new element:
782 temptree->fleafcontents.famplitude = TIMEBINS; //internal nodes mustn't be confused with real event names (from 0 to TIMEBINS)!
785 // cout << "assemble last two elements to final tree:" << endl;
786 // cout << "abundance of last list element (DEC) = " << lastpointer->fleafcontents.fabundance << endl;
788 // initialise abundance starting with last element
789 temptree->fleafcontents.fabundance = lastpointer->fleafcontents.fabundance;
791 // code assignment small ones get 0, large ones get 1:
792 lastpointer->fleafcontents.fcode = 0;
794 // append smallest element on the left:
795 temptree->fleft = lastpointer;
796 lastpointer->fparent = temptree;
799 // cout << "abundance of first list element (DEC) = " << listroot->fleafcontents.fabundance << endl;
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;
809 temptree->fnext = NULL;
810 temptree->fprevious = NULL;
811 temptree->fparent = NULL;
814 // cout << " final abundance of tree root (DEC) = " << temptree->fleafcontents.fabundance << endl;
816 // error if temptree = NULL
817 if (temptree == NULL)
819 HLTError("Error! Pointer to root of Huffman binary tree = NULL");
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)
828 // see header file for class documentation
829 while ((treeroot->fleft != NULL) || (treeroot->fright != NULL))
831 // define pointer to go through tree
832 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* finder = treeroot;
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
838 AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* tempstruct = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[tempstructsize];
840 for(Int_t jj = 0; jj < tempstructsize; jj++)
842 tempstruct[jj].fhuffmancode = 0;
845 Int_t passednodes = 0;
847 // start searching for leaves
850 // if finder points at a leaf:
851 if (finder->fright == NULL && finder->fleft == NULL)
853 //if it is an internal node
854 if(finder->fleafcontents.famplitude == TIMEBINS)
857 // cout << "found internal node with following abundance to delete (DEC) = " << finder->fleafcontents.fabundance << endl;
859 //go back to parent and delete node with 256
860 if (finder->fleafcontents.fcode == 0) // node was left one
862 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent;
863 parent->fleft = NULL;
865 else // node was right one
867 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent;
868 parent->fright = NULL;
873 else // if it is a leaf
875 Int_t checkright = 0; // so leaf is left children
877 // leaf can also be a right leaf:
878 if (finder->fleafcontents.fcode == 1)
880 checkright = 1; // if code == 1, leaf is right children
883 // write collected data in the respective array:
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;
889 // cout << "found leaf with amplitude (DEC) = " << finder->fleafcontents.famplitude << endl;
891 HuffmanCodearray[finder->fleafcontents.famplitude].fvalidcodelength = passednodes;
894 // cout << "found leaf with validlength (DEC) = " << HuffmanCodearray[foundleaves].fvalidcodelength << endl;
897 HuffmanCodearray[finder->fleafcontents.famplitude].fhuffmancode = tempstruct[0].fhuffmancode;
900 //cout << "found leaf with code (HEX) = " << hex << HuffmanCodearray[finder->fleafcontents.famplitude].fhuffmancode << dec << endl;
902 if(passednodes > 64) // if there is more code to write (not usual in normal zero-suppressed data streams!)
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);
911 // cout << "found leaf written after passed nodes (DEC) = " << passednodes << endl;
913 // deleting found leaf from tree
914 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* parent = finder->fparent; // go one up and set pointer to leaf to zero:
917 // cout << "parent abundance from found leaf (DEC) = " << finder->fleafcontents.fabundance << endl;
919 if (checkright == 1) // if leaf is right children -> delete right
921 parent->fright = NULL;
923 else //else: delete fleft
925 parent->fleft = NULL;
931 // cout << " finder pointer at end of deleting the found leaf (DEC) = " << finder << endl;
933 else // if node is not a leaf
936 //cout << "finder pointer to left child (DEC) = " << finder->fleft << endl;
937 //cout << "finder pointer to right child (DEC) = " << finder->fright << endl;
939 if(finder->fleft != NULL)
941 finder = finder->fleft; // pointer to children
944 //cout << "left child has abundance (DEC) = " << finder->fleafcontents.fabundance << endl;
946 // shift left to arrange space for new code element which is zero (->left!)
947 // i.e. nothing further needed to create code
950 //cout << "code for left child is created as (DEC) = " << tempstruct->fhuffmancode << endl;
952 //problem if passednodes > 63 --> inserting another bit becomes tricky:
955 tempstruct[0].fhuffmancode = tempstruct[0].fhuffmancode << 1;
957 else // error as valid codelength should not exceed 64 bits
960 HLTError("Error! Valid codelength for current encoding process becomes larger than 64 bits, which is not usual for normal input data");
966 //cout << "code for left child has been written as (DEC) = " << tempstruct->fhuffmancode << endl;
972 finder = finder->fright; // goto right children
975 //cout << "right child has abundance (DEC) = " << finder->fleafcontents.fabundance << endl;
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
981 //cout << "code for right child is created as (DEC) = " << tempstruct->fhuffmancode << endl;
983 //problem if passednodes > 63 --> inserting another bit becomes tricky:
986 tempstruct[0].fhuffmancode = tempstruct[0].fhuffmancode << 1;
987 tempstruct[0].fhuffmancode = (tempstruct[0].fhuffmancode) | 1;
992 HLTError("Error! Valid codelength for current encoding process becomes larger than 64 bits, which is not usual for normal input data");
997 //cout << "code for right children has been written as (DEC) = " << tempstruct->fhuffmancode << endl;
1000 } // end of right children search
1001 } // end of no-leaf-search
1002 } // end of while-loop for leaf-search
1005 delete[] tempstruct;
1006 } // end of while-loop for tree != root only
1008 // error when there is an amplitude = TIMEBINS in the HuffmanArray
1009 for(int jj = 0; jj < TIMEBINS; jj++)
1011 if(HuffmanCodearray[jj].famplitude == TIMEBINS)
1013 HLTError("Error! Internal node from Huffman tree in Huffmanarray for 10 bit word (DEC) %i", jj);
1020 /** Training function to create the HuffmanCode from a binary tree */
1021 Int_t AliHLTCOMPHuffmanAltro::TrainingData()
1023 // see header file for class documentation
1024 // total number of events counted
1025 Int_t totalnumber = 0;
1027 // 10 BIT READ IN !!!
1028 AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*)fPointer2InData;
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)!
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;
1040 // check if the input data size is appropriate:
1041 // cout << "size of input data in bytes (DEC) = " << fInputDataSize << endl;
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)
1047 HLTError("Error! Input data size (bytes) %i cannot be divided into 32 bit words", fInputDataSize);
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)
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));
1060 // index word reads position of 32bit word in input array
1064 UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1066 // start reading input data (which are 10 bit words):
1067 while (idxwd < endNdx)
1069 // write input data in temp and cut out 10 bits with mask 0x3FF
1070 data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1072 // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1075 data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1079 // fill abundances in training table
1080 fTrainingTable[(Int_t)(data10)].fabundance += 1;
1082 // increase total number of events
1085 ++idx10; // go on reading 10 bit word
1087 // bit position word reads position in 32bit word when 10 bits are read out
1088 bitpswd = (idx10 * 10) & 0x1F;
1090 idxwd = ((idx10 * 10)>>5)+8;
1094 // cout << "abundance table is now filled " << endl;
1096 // set fOutputDataSize to zero as no output has been created:
1097 fOutputDataSize = 0;
1102 /** Create Huffman code table out of abundance table filled by training data in DoEvent function of component */
1103 Int_t AliHLTCOMPHuffmanAltro::CreateCodeTable()
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);
1109 // abort when there is no pointer to sorted array (error produced in Mergesort function)
1110 if(HuffmanArraySorted == NULL)
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++)
1119 if(HuffmanArraySorted[kk].fabundance < HuffmanArraySorted[kk+1].fabundance)
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);
1128 //cout << "merge sort for training table is now done " << endl;
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)
1135 // check how many 10 bit words are used ("missing channel problem)
1136 for(UInt_t kk = 0; kk < TIMEBINS; kk++)
1138 if((HuffmanArraySorted[kk].fabundance == 0))
1144 // -> new array size is "filled"
1146 // cout << "number of filled array entries (DEC) = " << filled << endl;
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)
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);
1154 // initialise leaves of the tree as list (= queue) ofAliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct,
1155 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct * HuffmanTreeList = new AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct[filled];
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;
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;
1168 // initialise 1 to filled-2 elements
1170 while(kk < filled-1)
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];
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;
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];
1192 // initialise pointer to last list element:
1193 AliHLTCOMPHuffmanData::AliHLTCOMPHuffmanTreeDataStruct* lastelement = &HuffmanTreeList[filled-1];
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;
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);
1202 // abort if root = NULL (error already produced in CreateHuffmanTree function)
1203 delete [] HuffmanTreeList;
1211 // cout << "binary tree is now created " << endl;
1213 // create an array for the HuffmanCode data:
1214 fTranslationTable = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[TIMEBINS];
1216 // initialise the array with validcodelengths 0 and codes = 0
1217 for(Int_t kk1 = 0; kk1 < TIMEBINS; kk1++)
1219 // validation test for correct HuffmanCode()
1220 // fTranslationTable[kk1].famplitude = TIMEBINS+1; // check if eventnames are written
1222 fTranslationTable[kk1].famplitude = kk1;
1223 fTranslationTable[kk1].fhuffmancode = 0;
1224 fTranslationTable[kk1].fvalidcodelength = 0;
1225 // fTranslationTable[kk1].morecode = NULL;
1228 // create HuffmanCode and abort when HuffmanCode produces errors
1229 if(HuffmanCode(root,fTranslationTable) == 1)
1235 // cout << "Huffman coding is now done " << endl;
1238 // print the Huffman code table to screen
1239 // for(Int_t kk = 0; kk < TIMEBINS; kk++)
1241 // if (fTranslationTable[kk].fvalidcodelength != 0)
1242 // cout << fTranslationTable[kk].famplitude << " | " << fTranslationTable[kk].fhuffmancode << " | " << fTranslationTable[kk].fvalidcodelength << endl;
1245 // findout maximal and minimal codelength and print them out
1246 UInt_t maxcodelength = fTranslationTable[0].fvalidcodelength;
1247 UInt_t mincodelength = TIMEBINS;
1249 for (Int_t kk2 = 0; kk2 < TIMEBINS; kk2++)
1251 // if(fTranslationTable[kk2].fvalidcodelength != 0) {cout << kk2 << " | " << fTranslationTable[kk2].fhuffmancode << " | " << fTranslation "Table[kk2].fvalidcodelength << endl;}
1253 if(fTranslationTable[kk2].fvalidcodelength > maxcodelength)
1254 { maxcodelength = fTranslationTable[kk2].fvalidcodelength;};
1255 if( (fTranslationTable[kk2].fvalidcodelength != 0) && (fTranslationTable[kk2].fvalidcodelength < mincodelength) )
1256 { mincodelength = fTranslationTable[kk2].fvalidcodelength;};
1259 // print results to screen
1260 HLTInfo("maximal codelength (DEC) = %i ", maxcodelength);
1261 HLTInfo("minimal codelength (DEC) = %i ", mincodelength);
1266 /** TTMergesort used by EntropyDecoding to sort translation table according to validcodelength from low to high */
1267 AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* AliHLTCOMPHuffmanAltro::TTMergesort(AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct *unsortedarray, Int_t n)
1269 // see heaeder file for class documentation
1270 //divide array into two halfs: left and right (fleft.size = divlength)
1271 Int_t divlength = n >> 1;
1275 // error when unsorted array = NULL
1276 if (unsortedarray == NULL)
1278 HLTError("Error! Pointer to final merge sorted code table = NULL");
1281 return unsortedarray;
1285 // sort both halfs recursively:
1286 TTMergesort(unsortedarray, divlength); //left half
1287 TTMergesort(&unsortedarray[divlength], n-divlength); //right half
1290 // create temporary result array:
1291 AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct* temp = new AliHLTCOMPHuffmanCodeData::AliHLTCOMPHuffmanCodeStruct[n];
1296 // if left and right halves both have elements: chose the smaller one:
1297 for (ii = 0, jj = divlength, kk = 0; ii < divlength && jj < n;)
1299 if (unsortedarray[ii].fvalidcodelength < unsortedarray[jj].fvalidcodelength)
1301 temp[kk] = unsortedarray[ii];
1306 temp[kk] = unsortedarray[jj];
1314 // if one half is empty take elements of the other one:
1315 while (ii < divlength)
1317 temp[kk] = unsortedarray[ii];
1324 temp[kk] = unsortedarray[jj];
1329 // copy sorted temp array back into original data array
1330 for (Int_t ll = 0; ll < n; ll++)
1332 unsortedarray[ll] = temp[ll];
1338 // return pointer to original data array (which is sorted now)
1339 return unsortedarray;
1343 /** function for the entropy decoding, needed input: code table, input data pointer and size and pointer where to write decoded data */
1344 Int_t AliHLTCOMPHuffmanAltro::EntropyDecompression()
1346 // see heaeder file for class documentation
1348 // print translation table to screen
1349 // for(int kk= 0; kk < TIMEBINS; kk++)
1351 // cout << fTranslationTable[kk].famplitude << " | " << fTranslationTable[kk].fhuffmancode << " | " << fTranslationTable[kk].fvalidcodelength << endl;
1354 // sort translation table according to validcodelengths from low to high (codes that occur often are found quickly)
1355 fTranslationTable = TTMergesort(fTranslationTable, TIMEBINS);
1358 // print merge sorted translation table to screen
1359 // for(int kk= 0; kk < TIMEBINS; kk++)
1361 // cout << fTranslationTable[kk].famplitude << " | " << fTranslationTable[kk].fhuffmancode << " | " << fTranslationTable[kk].fvalidcodelength << endl;
1364 // do set output data first in order to know the size of the decompressed array!
1365 // take care of trailers and headers when decoding!
1367 // initialise reading pointer on compressed data
1368 AliHLTUInt64_t* pointerprop = (AliHLTUInt64_t*)fPointer2InData;
1370 // initialise writing pointer for decompressed output array
1371 AliHLTUInt64_t* pointeroutputprop = (AliHLTUInt64_t*) fPointer2OutData;
1373 // outputdata size initialised
1374 fOutputDataSize = 0;
1377 // cout << "input data size of encoded data (DEC) = " << fInputDataSize << endl;
1378 // cout << "output data size of decoded data (DEC) = " << fOutputDataSize << endl;
1380 // create temporary word to read out 1 bit from, maximal length: 64 bits */
1381 AliHLTUInt64_t codedata = 0;
1382 UInt_t codedatalength = 0;
1384 // number of 32-bit trailer and common data header words:
1385 UInt_t headerwords = 8;
1386 UInt_t header64 = headerwords >> 1;
1388 // initialise counter variables for input array:
1389 UInt_t idxwd = header64; // due to 8*32 = 4*64 bit header words
1392 // initialise counter variables for output array:
1393 UInt_t idxoutwd = header64; // due to 8*32 = 4*64 bit header words
1394 // UInt_t idx10out = 0; // only used for validation test
1395 UInt_t bitpsoutwd = 0;
1397 // write header to output (two words input header in one word output header):
1398 UInt_t head64cntr = 0;
1400 while(head64cntr < header64)
1402 pointeroutputprop[head64cntr] = pointerprop[head64cntr];
1405 //cout << "header line in output stream (HEX) = " << hex << pointeroutputprop[head64cntr] << dec << endl;
1410 // end of encoded ALTRO-blocks [Byte] = finputdatasize - (number of 32-bit-trailer-words + 1) / 4
1411 // match this with idxwd as number of 64-bit-words (endNdx[#64-bit-wds] = endNdx[#8-bit-wds]*8/64)
1412 UInt_t lastfullline = (fInputDataSize) >> 3;
1413 UInt_t lastbit = (fInputDataSize << 3) & 0x3F;
1414 UInt_t lastcodeline = lastfullline - ((fNrcuTrailerwords +1) >> 1);
1424 // initialise last valid bit position and trailer array
1425 AliHLTUInt32_t lastvalidbitpos = 0;
1426 AliHLTUInt64_t* trailer = new AliHLTUInt64_t[fNrcuTrailerwords];
1429 // cout << "last bit (DEC) = " << lastbit << endl;
1430 // cout << "lastfullline (DEC) = " << lastfullline << endl;
1431 // cout << "lastcodeline(DEC) = " << lastcodeline << endl;
1432 // cout << "second last code line data (HEX) = " << hex << pointerprop[lastcodeline-1] << dec << endl;
1433 // cout << "last code line data (HEX) = " << hex << pointerprop[lastcodeline] << dec << endl;
1434 // cout << "last full line data (HEX) = " << hex << pointerprop[lastfullline] << dec << endl;
1436 // get last valid bit position (first 32 bit word in first trailer line after code
1438 if (fNrcuTrailerwords < 3) // then lastfullline = only trailerline
1440 lastvalidbitpos = (pointerprop[lastfullline] >> 32);
1442 // first trailerword
1443 trailer[0] = ((pointerprop[lastfullline] << 32 ) >> 32);
1445 // second trailerword
1446 if(fNrcuTrailerwords == 2)
1448 trailer[1] = ((pointerprop[lastfullline+1] << 32) >> 32);
1453 lastvalidbitpos = (pointerprop[lastfullline-1] >> 32);
1455 // first trailerword
1456 trailer[0] = ((pointerprop[lastfullline-1] << 32 ) >> 32);
1458 //second trailerword
1459 trailer[1] = (pointerprop[lastfullline] >> 32);
1461 // third trailerword
1462 trailer[2] =((pointerprop[lastfullline] << 32 ) >> 32);
1466 // cout << "last valid bit position (DEC) = " << lastvalidbitpos << endl;
1468 // warning if one of the trailer words is zero:
1469 for (UInt_t kk = 0; kk < fNrcuTrailerwords; kk++)
1471 if(trailer[kk] == 0)
1473 HLTWarning("Warning! Trailer word %i is zero",kk+1);
1478 // print trailer array to screen
1479 // for(Int_t ii=0; ii < fNrcuTrailerwords; ii++)
1481 // cout << "trailerword " << ii+1 << " after getting whole trailer (HEX) = " << hex << trailer[ii] << dec << endl;
1484 // find minmal validcodelength from first entry of translation table and
1485 // read in minimal validcodelength bits if codedata is zero...
1486 UInt_t minimalcodelength = fTranslationTable[0].fvalidcodelength;
1489 // cout << "minimal codelength (DEC) = " << minimalcodelength << endl;
1491 Int_t readnewcode = 1; // read new code = 1; go on with old code = 0
1494 // NEW (bitpswd >= lastvalidbitpos) instead of (bitpswd > lastvalidbitpos)
1495 while (!((idxwd >= lastcodeline) && (bitpswd >= lastvalidbitpos)) )
1497 if((idxwd == lastcodeline+1) && (bitpswd == 0)) break; // abortion when lastvalidbitpos = 64
1499 if (codedatalength < 64) // if codedata can still get one further bit
1501 // if new code word is read before end position
1502 if((readnewcode == 1) && !((idxwd >= lastcodeline) && (bitpswd + minimalcodelength > lastvalidbitpos)))
1504 // codedata gets next bits from encoded input file:
1505 codedata <<= minimalcodelength; //shift bits left
1507 if (bitpswd + minimalcodelength < 65) // all bits in the same line
1509 codedata |= ((pointerprop[idxwd] << bitpswd)) >> (64 - minimalcodelength); //append bits from input file to the right
1511 else // some of this bits in the next line
1513 // append bits of current line to the right end of codedata
1514 codedata |= (((pointerprop[idxwd] << bitpswd)) >> (bitpswd)) << (minimalcodelength - 64 + bitpswd);
1516 // append bits of next line to the right end of codedata
1517 codedata |= (pointerprop[idxwd+1] >> (128 - minimalcodelength - bitpswd)); // 128 - mcl - bitpswd = 64 - (mcl - (64 - bitpswd))
1520 codedatalength += minimalcodelength;
1522 // new code is read, set readnewcode back to 0 again
1525 // go and get next input bit
1526 bitpswd += minimalcodelength;
1530 // codedata gets on bit after another from encoded input file:
1531 codedata <<= 1; //shift one bit left
1532 codedata |= ((pointerprop[idxwd] << bitpswd)) >> 63; //append next bit from input file to the right
1536 // go and get next input bit
1540 // go and get next input bit
1544 bitpswd = bitpswd & 0x3F;
1547 // compare if new codedata is in translation table:
1548 for(UInt_t kk = 0; kk < TIMEBINS; kk++)
1550 // stopping when current codedatalength smaller than lookup validcodelength (i.e. current code not in table, read next bit)
1551 if(fTranslationTable[kk].fvalidcodelength > codedatalength)
1556 if(fTranslationTable[kk].fhuffmancode == codedata) //lookup bit pattern
1558 if(fTranslationTable[kk].fvalidcodelength == codedatalength) //lookup correct codelength
1561 // if( idxoutwd >= 2636)
1563 // cout << "write 10 bit word to decoded output (DEC) = " << fTranslationTable[kk].famplitude << endl;
1564 // cout << "current idxwd (DEC) = " << idxwd << endl;
1565 // cout << "current idxoutwd (DEC) = " << idxoutwd << endl;
1567 if(bitpsoutwd + 10 < 65) //fits in old line
1569 // valdidation test for end of decoded data
1570 // print all relevant quantities to screen
1573 // cout << "current input in codedata (HEX) = " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1574 // cout << "current idxwd (DEC) = " << idxwd << endl;
1575 // cout << "current bitpswd (DEC) = " << bitpswd << endl;
1576 // cout << "current idxoutwd (DEC) = " << idxoutwd << endl;
1577 // cout << "current bitpsoutwd (DEC) = " << bitpsoutwd << endl;
1578 // cout << "decoding value (DEC) = " << codedata << endl;
1579 // cout << "value length (DEC) = " << codedatalength << endl;
1580 // cout << "10 bit value (HEX) = " << hex << fTranslationTable[kk].famplitude << dec << endl;
1583 pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << bitpsoutwd;
1586 // if (idxoutwd > 362880)
1588 // cout << "updated output line (HEX) = " <<hex << pointeroutputprop[idxoutwd] <<dec << endl;
1591 // goto next 10-bits output position
1594 if(bitpsoutwd == 64) {bitpsoutwd = 0; ++idxoutwd;};
1597 else //needs start of new line
1600 pointeroutputprop[idxoutwd] |= ((AliHLTUInt64_t)(fTranslationTable[kk].famplitude)) << (bitpsoutwd);
1602 ++idxoutwd; //start new line
1607 // cout << "current input in codedata (HEX) = " << hex << (pointerprop[idxwd] << bitpswd) << dec << endl;
1608 // cout << "current idxwd (DEC) = " << idxwd << endl;
1609 // cout << "current bitpswd (DEC) = " << bitpswd << endl;
1610 // cout << "current idxoutwd (DEC) = " << idxoutwd << endl;
1611 // cout << "current bitpsoutwd (DEC) = " << bitpsoutwd << endl;
1612 // cout << "decoding value (DEC) = " << codedata << endl;
1613 // cout << "value length (DEC) = " << codedatalength << endl;
1614 // cout << "10 bit value (HEX) = " << hex << fTranslationTable[kk].famplitude << dec << endl;
1618 AliHLTUInt64_t buffer = fTranslationTable[kk].famplitude;
1619 buffer >>= (64 - bitpsoutwd);
1621 pointeroutputprop[idxoutwd] = buffer;
1624 // if (idxoutwd > 362880)
1626 // cout << "new line (HEX) = " << hex << pointeroutputprop[idxoutwd] << dec << endl;
1629 // go to next bit position
1633 // set buffers to zero again
1637 // prepare codedata to read new code word
1643 // go on with next code bits from input
1649 else // if *morecode is used
1652 HLTError("Error! Valid codelength for current decoding is larger than 64 bits, error in recognising the correct code");
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)
1664 // cout << "bit position after decoding (DEC) = " << bitpsoutwd << endl;
1665 // cout << "line position after decoding (DEC) = " << idxoutwd << endl;
1667 // warning if byte position is not 8-bits aligned
1668 if ((bitpsoutwd & 0x07) != 0 )
1670 HLTWarning("Warning! Bit position after decoding %i is not aligned to 8 bits", bitpsoutwd);
1673 if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1675 pointeroutputprop[idxoutwd] <<= 32;
1677 pointeroutputprop[idxoutwd] |= trailer[0];
1683 pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1684 pointeroutputprop[idxoutwd]|= (trailer[0] >> (bitpsoutwd - 32));
1689 // get rid of upper, already written bits
1690 trailer[0] <<= 96 - bitpsoutwd;
1691 trailer[0] >>= 96 - bitpsoutwd;
1693 pointeroutputprop[idxoutwd] = trailer[0]; // write lower bits to next line
1698 if(fNrcuTrailerwords > 1)
1701 if(bitpsoutwd == 64)
1707 for(UInt_t ii = 1; ii < fNrcuTrailerwords; ii++)
1709 // write second trailer to output data
1710 if(bitpsoutwd + 32 < 65) // trailer fits in current line, append on the right
1712 pointeroutputprop[idxoutwd] <<= 32;
1714 pointeroutputprop[idxoutwd] |= trailer[ii];
1718 if(bitpsoutwd == 64)
1726 pointeroutputprop[idxoutwd] <<= 64 - bitpsoutwd;
1727 pointeroutputprop[idxoutwd]|= (trailer[ii] >> (bitpsoutwd - 32));
1732 // get rid of upper, already written bits
1733 trailer[ii] <<= 96 - bitpsoutwd;
1734 trailer[ii] >>= 96 - bitpsoutwd;
1736 pointeroutputprop[idxoutwd] = trailer[ii]; // write lower bits to next line
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;
1748 // write trailer to decoded output
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) );
1756 // error and abort when output data size smaller than input data size (impossible when decompressing)
1757 if(fOutputDataSize < fInputDataSize)
1759 HLTError("Error! Data size for decompressed output stream (bytes) %i is smaller than compressed input data size (bytes) %i", fOutputDataSize, fInputDataSize);
1765 // cout << "output data size (DEC) = " << fOutputDataSize << endl;
1770 /** CalcEntropy is to calculate entropy for 10 bits amplitudes of input data (per event only!) */
1771 Int_t AliHLTCOMPHuffmanAltro::CalcEntropy()
1773 // see heaeder file for class documentation
1774 // create result array with TIMEBINS entries according to their abundance in the input data:
1775 UInt_t* histogrammarray = new UInt_t[TIMEBINS];
1777 // initialise histrogramm:
1778 for(UInt_t jj = 0; jj < TIMEBINS; jj++)
1780 histogrammarray[jj] = 0;
1783 // total number of counted data
1784 UInt_t totalnumber = 0;
1788 // 10 BIT READ IN !!!
1789 AliHLTUInt32_t* pointer2InData = (AliHLTUInt32_t*)fPointer2InData;
1791 // initialise required variables for input reading:
1792 AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1793 UInt_t idxwd = 8; // because of common data header words (see below)!
1796 // number 32-bit trailer and common data header words:
1797 // Int_t fNrcuTrailerwords = 1; // determined by user input as argument
1798 UInt_t headerwords = 8;
1801 // check if the input data size is appropriate:
1802 // cout << "size of input data in bytes (DEC) = " << fInputDataSize << endl;
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)
1808 HLTError("Error! Input data size (bytes) %i cannot be divided into 32 bit words", fInputDataSize);
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)
1816 HLTError("Error! Input data without trailer and header words (bytes) %i cannot be divided into 10 bit words", fInputDataSize);
1821 // index to watch current bit position of 10 bits words
1824 // last valid bit for read in
1825 UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1827 // start reading and encoding input data (which are 10 bit words):
1828 while (idxwd < endNdx)
1830 // write input data in temp and cut out 10 bits with mask 0x3FF
1831 data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1833 // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1836 data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1841 // print first 10 bits words to screen
1844 // cout << "read 10 bits word (HEX) = " << hex << data10 << dec << endl;
1847 // store abundance of data10 in histogrammarray
1848 histogrammarray[(UInt_t) data10] += 1;
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;
1859 // print abundance table to screen
1860 // for (Int_t jj=0; jj < TIMEBINS; jj++)
1862 // cout << histogrammarray[jj] << endl;
1865 // save log(2) in special variable for performance gain:
1866 double l2 = log(2.0);
1868 // calculate the entropy of the array
1869 for(UInt_t jj = 0; jj < TIMEBINS; jj++)
1871 if (histogrammarray[jj] != 0)
1873 fEntropy += (- (Double_t) histogrammarray[jj] / (Double_t) totalnumber ) * log( ( (Double_t) histogrammarray[jj] / (Double_t) totalnumber )) / (l2);
1878 delete[] histogrammarray;
1883 /* CopyData is just a function for performance testing */
1884 Int_t AliHLTCOMPHuffmanAltro::CopyData()
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;
1892 //first output word has to be initialised
1893 pointeroutprop[0] = 0;
1895 fOutputDataSize = fInputDataSize;
1897 // initialise required variables for input reading:
1898 AliHLTUInt32_t data10 = 0; // temporary number to read out 10bit word with
1903 // number of 32-bit trailer and common data header words:
1904 // (taken out of compression!)
1905 // UInt_t headerwords = 8;
1907 // initialise required variables for ouput creation:
1908 UInt_t idxoutwd = 0;
1909 // Int_t bitcounter = 0; // additional test for number of read in 10 bit words
1910 // Int_t sumlength = 0; // additional test for length of encoded file
1912 UInt_t endNdx = (fInputDataSize>>2)-fNrcuTrailerwords;
1914 // start reading and encoding input data (which are 10 bit words):
1915 while (idxwd < endNdx)
1917 // write input data in temp and cut out 10 bits with mask 0x3FF
1918 data10 = (pointer2InData[idxwd] >> bitpswd ) & 0x3FFU;
1921 //cout << "current 10 bits word (DEC) = " << data10 << endl;
1923 // if number of bits left in read input less than ten, get remaining bits from next 32bit word
1926 data10 |= (pointer2InData[idxwd + 1]) << (32 - bitpswd);
1931 // print first 10 bits words to screen
1934 // cout << "read data: " << hex << data10 << dec << endl;
1937 // write data to 32 bit output:
1938 pointeroutprop[idxoutwd] |= (data10 << bitpswd);
1942 pointeroutprop[idxoutwd + 1] = (data10 >> (32 - bitpswd));
1946 // cout << "next bitpswd (DEC) = " << bitpswd << endl;
1948 ++idx10; // go on reading 10 bit word
1950 // index word reads position of 32bit word in input array
1951 idxoutwd = (idx10 * 10);
1952 bitpswd = idxoutwd & 0x1F;
1955 // bit position word reads position in 32bit word when 10 bits are read out
1959 // cout << "output data size (DEC) = " << fOutputDataSize << endl;
1960 // cout << "sum of codelengths (DEC) = " << sumlength << endl;
1961 // cout << "number of 10 bits words (DEC) = " << bitcounter << endl;