]>
Commit | Line | Data |
---|---|---|
c2440081 | 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 | } |