Line data Source code
1 : // $Id$
2 :
3 : //**************************************************************************
4 : //* This file is property of and copyright by the ALICE HLT Project *
5 : //* ALICE Experiment at CERN, All rights reserved. *
6 : //* *
7 : //* Primary Authors: Thorsten Kollegger <kollegge@ikf.uni-frankfurt.de> *
8 : //* for The ALICE HLT Project. *
9 : //* *
10 : //* Permission to use, copy, modify and distribute this software and its *
11 : //* documentation strictly for non-commercial purposes is hereby granted *
12 : //* without fee, provided that the above copyright notice appears in all *
13 : //* copies and that both the copyright notice and this permission notice *
14 : //* appear in the supporting documentation. The authors make no claims *
15 : //* about the suitability of this software for any purpose. It is *
16 : //* provided "as is" without express or implied warranty. *
17 : //**************************************************************************
18 :
19 : /// @file AliHLTDataDeflaterHuffman.cxx
20 : /// @author Thorsten Kollegger, Matthias Richter
21 : /// @date 2011-08-10
22 : /// @brief Deflater implementation using huffman code
23 :
24 : #include "AliHLTDataDeflaterHuffman.h"
25 : #include "AliHLTHuffman.h"
26 : #include "TObjArray.h"
27 : #include "TList.h"
28 : #include "TString.h"
29 : #include "TFile.h"
30 : #include <memory>
31 : #include <algorithm>
32 : #include <cmath>
33 : #include <iostream>
34 :
35 : /** ROOT macro for the implementation of ROOT specific class methods */
36 126 : ClassImp(AliHLTDataDeflaterHuffman)
37 :
38 : AliHLTDataDeflaterHuffman::AliHLTDataDeflaterHuffman(bool bTrainingMode)
39 0 : : AliHLTDataDeflater()
40 0 : , fReferenceLength()
41 0 : , fHuffmanCoders()
42 0 : , fHuffmanCoderList(NULL)
43 0 : , fTrainingMode(bTrainingMode)
44 0 : , fParameterClusterCount()
45 0 : , fBitCount()
46 0 : {
47 : // see header file for class documentation
48 : // or
49 : // refer to README to build package
50 : // or
51 : // visit http://web.ift.uib.no/~kjeks/doc/alice-hlt
52 0 : if (bTrainingMode) {
53 0 : HLTInfo("using DataDeflaterHuffman in training mode");
54 : }
55 0 : }
56 :
57 : AliHLTDataDeflaterHuffman::~AliHLTDataDeflaterHuffman()
58 0 : {
59 : // destructor
60 0 : if (fHuffmanCoderList) delete fHuffmanCoderList;
61 0 : fHuffmanCoderList=NULL;
62 :
63 0 : Clear();
64 0 : }
65 :
66 : int AliHLTDataDeflaterHuffman::AddParameterDefinition(const char* name, unsigned bitLength, unsigned refLength)
67 : {
68 : /// search a parameter definition in the decoder configuration, and set the index
69 : /// array, return reference id
70 0 : if (IsTrainingMode())
71 0 : return AddTrainingParameter(name, bitLength);
72 :
73 0 : if (!name) return -EINVAL;
74 0 : if (!fHuffmanCoderList) return -ENODEV;
75 0 : TObject* pObj=fHuffmanCoderList->FindObject(name);
76 0 : if (!pObj) {
77 0 : HLTError("can not find decoder of id '%s'", name);
78 0 : return -ENOENT;
79 : }
80 0 : AliHLTHuffman* pHuffman=dynamic_cast<AliHLTHuffman*>(pObj);
81 0 : if (!pHuffman) {
82 0 : HLTError("object %s has wrong type, expected AliHLTHuffman", name);
83 0 : return -EBADF;
84 : }
85 0 : if (pHuffman->GetMaxBits()!=bitLength) {
86 0 : HLTError("mismatch in bitlengt: can not use decoder %s of length %d for encoding of %d bits", pHuffman->GetName(), pHuffman->GetMaxBits(), bitLength);
87 0 : return -EPERM;
88 : }
89 :
90 0 : fReferenceLength.push_back(refLength>0?refLength:bitLength);
91 0 : fHuffmanCoders.push_back(pHuffman);
92 0 : fParameterClusterCount.push_back(0);
93 0 : fBitCount.push_back(0);
94 :
95 0 : int memberId=fHuffmanCoders.size()-1;
96 0 : if (DoStatistics()) {
97 0 : AddHistogram(memberId, name, bitLength);
98 0 : }
99 :
100 : return memberId;
101 0 : }
102 :
103 : int AliHLTDataDeflaterHuffman::InitDecoders(TList* decoderlist)
104 : {
105 : /// init list of decoders
106 : /// expects to be an external pointer, valid throughout the livetime of
107 : /// the instance
108 0 : if (!decoderlist) return -EINVAL;
109 0 : if (!fHuffmanCoderList) {
110 0 : fHuffmanCoderList=new TList;
111 0 : } else {
112 0 : if (fHuffmanCoderList->GetEntries()>0 && fHuffmanCoderList->IsOwner()) {
113 0 : HLTWarning("list of decoders owns already %d object(s), but disabling ownership now because of new external pointers");
114 : }
115 : }
116 0 : if (!fHuffmanCoderList) return -ENOMEM;
117 0 : fHuffmanCoderList->SetOwner(kFALSE);
118 0 : TIter next(decoderlist);
119 : TObject* pObj=NULL;
120 0 : while ((pObj=next())!=NULL) {
121 0 : if (dynamic_cast<AliHLTHuffman*>(pObj)==NULL) continue;
122 0 : if (fHuffmanCoderList->FindObject(pObj->GetName())) {
123 0 : HLTError("duplicate entry of name '%s'", pObj->GetName());
124 0 : return -EEXIST;
125 : }
126 0 : fHuffmanCoderList->Add(pObj);
127 : }
128 :
129 0 : return fHuffmanCoderList->GetEntries();
130 0 : }
131 :
132 : bool AliHLTDataDeflaterHuffman::OutputParameterBits( int memberId, AliHLTUInt64_t const & value )
133 : {
134 : // write huffman encoded bit pattern of a member to the current byte and position
135 0 : if (IsTrainingMode())
136 0 : return AddTrainingValue(memberId, value);
137 :
138 0 : if (memberId>=(int)fHuffmanCoders.size()) {
139 0 : return false;
140 : }
141 :
142 0 : fParameterClusterCount[memberId]++;
143 :
144 0 : AliHLTUInt64_t length = 0;
145 0 : const std::bitset<64>& v=fHuffmanCoders[memberId]->Encode((value>fHuffmanCoders[memberId]->GetMaxValue())?fHuffmanCoders[memberId]->GetMaxValue():value, length);
146 : //cout << fHuffmanCoders[memberId]->GetName() << " value " << value << ": code lenght " << length << " " << v << endl;
147 0 : if (DoStatistics()) {
148 : float weight=0.0;
149 0 : unsigned parameterLength=fHuffmanCoders[memberId]->GetMaxBits();
150 0 : if (memberId<(int)fReferenceLength.size() && fReferenceLength[memberId]>0)
151 0 : parameterLength=fReferenceLength[memberId];
152 0 : if (parameterLength>0) {
153 0 : weight=length;
154 0 : weight/=parameterLength;
155 0 : }
156 0 : FillStatistics(memberId, value, 0, -1.0);
157 0 : fBitCount[memberId]+=length;
158 0 : }
159 :
160 0 : if (length>0) {
161 0 : return OutputBits(v, length);
162 : }
163 :
164 0 : return false;
165 0 : }
166 :
167 : int AliHLTDataDeflaterHuffman::AddTrainingParameter(const char* name, unsigned bitLength)
168 : {
169 : /// add a parameter definition for huffman training
170 :
171 : /// returns index in the array
172 0 : if (!fHuffmanCoderList) {
173 0 : fHuffmanCoderList=new TList;
174 0 : if (!fHuffmanCoderList) return -ENOMEM;
175 : // always set ownership for the new list since it is supposed to
176 : // contain only internal pointers
177 0 : fHuffmanCoderList->SetOwner();
178 0 : } else if (!fHuffmanCoderList->IsOwner()) {
179 : // not sure about the pointers which are already in the list
180 0 : if (fHuffmanCoderList->GetEntries()>0) {
181 0 : HLTWarning("skip setting ownership because list contains already %d object(s), possible memory leak at cleanup");
182 : } else {
183 0 : fHuffmanCoderList->SetOwner();
184 : }
185 : }
186 0 : AliHLTHuffman* pHuffman=new AliHLTHuffman(name, bitLength);
187 0 : if (!pHuffman) return -ENOMEM;
188 0 : fHuffmanCoderList->Add(pHuffman);
189 :
190 0 : fHuffmanCoders.push_back(pHuffman);
191 0 : return fHuffmanCoders.size()-1;
192 0 : }
193 :
194 : bool AliHLTDataDeflaterHuffman::AddTrainingValue( int memberId, AliHLTUInt64_t const & value )
195 : {
196 : /// add a training value for the specified parameter
197 0 : if (memberId>=(int)fHuffmanCoders.size()) {
198 0 : return false;
199 : }
200 0 : return fHuffmanCoders[memberId]->AddTrainingValue(value);
201 0 : }
202 :
203 : const TList* AliHLTDataDeflaterHuffman::GenerateHuffmanTree()
204 : {
205 : /// generate the huffman tree
206 0 : for (unsigned i=0; i<fHuffmanCoders.size(); i++) {
207 0 : if (!fHuffmanCoders[i]->GenerateHuffmanTree()) {
208 0 : HLTError("failed to generate huffman tree for parameter %s", fHuffmanCoders[i]->GetName());
209 : }
210 : }
211 0 : return fHuffmanCoderList;
212 : }
213 :
214 : void AliHLTDataDeflaterHuffman::Clear(Option_t * option)
215 : {
216 : // internal cleanup
217 :
218 0 : AliHLTDataDeflater::Clear(option);
219 0 : }
220 :
221 : void AliHLTDataDeflaterHuffman::Print(Option_t *option) const
222 : {
223 : // print info
224 0 : Print(cout, option);
225 0 : }
226 :
227 : void AliHLTDataDeflaterHuffman::Print(ostream& out, Option_t * option) const
228 : {
229 : // print to stream
230 0 : out << "AliHLTDataDeflaterHuffman: " << fHuffmanCoders.size() << " instance(s)" << endl;
231 0 : std::string stroption(option);
232 0 : if (stroption.find("instances")!=stroption.npos) {
233 0 : for (vector<AliHLTHuffman*>::const_iterator it=fHuffmanCoders.begin();
234 0 : it!=fHuffmanCoders.end(); it++) {
235 0 : (*it)->Print("short"); cout << endl;
236 : }
237 0 : if (fHuffmanCoders.size()==0 && fHuffmanCoderList && fHuffmanCoderList->GetEntries()>0) {
238 0 : TIter next(fHuffmanCoderList);
239 : TObject* pObj=NULL;
240 0 : while ((pObj=next())) {
241 0 : pObj->Print("short"); cout << endl;
242 : }
243 0 : }
244 : }
245 0 : AliHLTDataDeflater::Print(out, option);
246 0 : }
247 :
248 : TObject *AliHLTDataDeflaterHuffman::FindObject(const char *name) const
249 : {
250 : /// find object: 'DeflaterConfiguration'
251 0 : if (strcmp(name, "DeflaterConfiguration")==0) {
252 0 : for (unsigned i=0; i<fHuffmanCoders.size(); i++) {
253 0 : if (!fHuffmanCoders[i]->GenerateHuffmanTree()) {
254 0 : HLTError("generation of huffman tree for parameter '%s' failed", fHuffmanCoders[i]->GetName());
255 0 : return NULL;
256 : }
257 0 : if (!fHuffmanCoders[i]->CheckConsistency()) {
258 0 : HLTError("consistency check of huffman tree for parameter '%s' failed", fHuffmanCoders[i]->GetName());
259 : }
260 : }
261 :
262 0 : return fHuffmanCoderList;
263 : }
264 :
265 0 : return NULL;
266 0 : }
267 :
268 : void AliHLTDataDeflaterHuffman::SaveAs(const char *filename, Option_t *option) const
269 : {
270 : /// save data according to option
271 0 : TString remainingOptions;
272 : bool bWriteHuffmanConf=false; // write the huffman configuration
273 0 : TString strOption(option);
274 0 : std::auto_ptr<TObjArray> tokens(strOption.Tokenize(" "));
275 0 : if (tokens.get()) {
276 0 : for (int i=0; i<tokens->GetEntriesFast(); i++) {
277 0 : if (!tokens->At(i)) continue;
278 : const char* key="";
279 0 : TString arg=tokens->At(i)->GetName();
280 :
281 : key="huffmanconf";
282 0 : if (arg.BeginsWith(key)) {
283 : bWriteHuffmanConf=true;
284 0 : continue;
285 : }
286 :
287 0 : if (!remainingOptions.IsNull()) remainingOptions+=" ";
288 0 : remainingOptions+=arg;
289 0 : }
290 0 : }
291 :
292 0 : if (bWriteHuffmanConf) {
293 0 : std::auto_ptr<TFile> output(TFile::Open(filename, "RECREATE"));
294 0 : if (!output.get() || output->IsZombie()) {
295 0 : HLTError("can not open file %s from writing", filename);
296 0 : return;
297 : }
298 :
299 0 : if (!fHuffmanCoderList || fHuffmanCoderList->GetEntries()==0) {
300 0 : HLTError("no huffman instances available for writing");
301 0 : return;
302 : }
303 :
304 0 : for (unsigned i=0; i<fHuffmanCoders.size(); i++) {
305 0 : if (!fHuffmanCoders[i]->GenerateHuffmanTree()) {
306 0 : HLTError("generation of huffman tree for parameter '%s' failed", fHuffmanCoders[i]->GetName());
307 : }
308 : }
309 :
310 0 : output->cd();
311 0 : fHuffmanCoderList->Write("DeflaterConfiguration", TObject::kSingleKey);
312 0 : output->Close();
313 0 : return;
314 0 : }
315 :
316 0 : return AliHLTDataDeflater::SaveAs(filename, remainingOptions);
317 0 : }
318 :
319 : int AliHLTDataDeflaterHuffman::StartEncoder()
320 : {
321 : int memberId=0;
322 0 : for (vector<unsigned>::iterator it = fBitCount.begin(); it!=fBitCount.end(); it++, memberId++) {
323 0 : *it=0;
324 0 : fParameterClusterCount[memberId]=0;
325 : }
326 0 : return 0;
327 : }
328 :
329 : int AliHLTDataDeflaterHuffman::StopEncoder()
330 : {
331 : int memberId=0;
332 0 : for (vector<unsigned>::iterator it = fBitCount.begin(); it!=fBitCount.end(); it++, memberId++) {
333 0 : if (fParameterClusterCount[memberId]==0) continue;
334 0 : UInt_t outputByteCount = (*it+7)/8;
335 :
336 0 : float weight=outputByteCount*8.0;
337 0 : weight/=fParameterClusterCount[memberId];
338 0 : unsigned parameterSize=(unsigned)ceil(weight);
339 0 : weight/=fReferenceLength[memberId];
340 0 : FillStatistics(memberId, ~(AliHLTUInt64_t)0, parameterSize, weight);
341 0 : }
342 0 : return GetBitDataOutputSizeBytes();
343 : }
344 :
345 : ostream& operator<<(ostream &out, const AliHLTDataDeflaterHuffman& me)
346 : {
347 0 : me.Print(out);
348 0 : return out;
349 : }
350 :
|
