1 // **************************************************************************
2 // * This file is property of and copyright by the ALICE HLT Project *
3 // * All rights reserved. *
5 // * Primary Authors: *
6 // * Copyright 2009 Matthias Kretz <kretz@kde.org> *
8 // * Permission to use, copy, modify and distribute this software and its *
9 // * documentation strictly for non-commercial purposes is hereby granted *
10 // * without fee, provided that the above copyright notice appears in all *
11 // * copies and that both the copyright notice and this permission notice *
12 // * appear in the supporting documentation. The authors make no claims *
13 // * about the suitability of this software for any purpose. It is *
14 // * provided "as is" without express or implied warranty. *
15 // **************************************************************************
17 #include "AliHLTTPCCASliceData.h"
18 #include "AliHLTTPCCAClusterData.h"
19 #include "AliHLTTPCCAMath.h"
20 #include "AliHLTArray.h"
21 #include "AliHLTTPCCAHit.h"
22 #include "AliHLTTPCCAParam.h"
23 #include "MemoryAssignmentHelpers.h"
26 // calculates an approximation for 1/sqrt(x)
27 // Google for 0x5f3759df :)
28 static inline float fastInvSqrt( float _x )
30 // the function calculates fast inverse sqrt
32 union { float f; int i; } x = { _x };
33 const float xhalf = 0.5f * x.f;
34 x.i = 0x5f3759df - ( x.i >> 1 );
35 x.f = x.f * ( 1.5f - xhalf * x.f * x.f );
39 inline void AliHLTTPCCASliceData::CreateGrid( AliHLTTPCCARow *row, const AliHLTTPCCAClusterData &data )
43 if ( row->NHits() <= 0 ) { // no hits or invalid data
44 // grid coordinates don't matter, since there are no hits
45 row->fGrid.CreateEmpty();
53 for ( int i = row->fHitNumberOffset; i < row->fHitNumberOffset + row->fNHits; ++i ) {
54 const float y = data.Y( i );
55 const float z = data.Z( i );
56 if ( yMax < y ) yMax = y;
57 if ( yMin > y ) yMin = y;
58 if ( zMax < z ) zMax = z;
59 if ( zMin > z ) zMin = z;
62 const float norm = fastInvSqrt( row->fNHits );
63 row->fGrid.Create( yMin, yMax, zMin, zMax,
64 CAMath::Max( ( yMax - yMin ) * norm, 2.f ),
65 CAMath::Max( ( zMax - zMin ) * norm, 2.f ) );
68 inline void AliHLTTPCCASliceData::PackHitData( AliHLTTPCCARow *row, const AliHLTArray<AliHLTTPCCAHit> &binSortedHits )
72 static const float shortPackingConstant = 1.f / 65535.f;
73 const float y0 = row->fGrid.YMin();
74 const float z0 = row->fGrid.ZMin();
75 const float stepY = ( row->fGrid.YMax() - y0 ) * shortPackingConstant;
76 const float stepZ = ( row->fGrid.ZMax() - z0 ) * shortPackingConstant;
77 const float stepYi = 1.f / stepY;
78 const float stepZi = 1.f / stepZ;
84 row->fHstepYi = stepYi;
85 row->fHstepZi = stepZi;
87 for ( int hitIndex = 0; hitIndex < row->fNHits; ++hitIndex ) {
89 const int globalHitIndex = row->fHitNumberOffset + hitIndex;
90 const AliHLTTPCCAHit &hh = binSortedHits[globalHitIndex];
91 const float xx = ( ( hh.Y() - y0 ) * stepYi ) + .5 ;
92 const float yy = ( ( hh.Z() - z0 ) * stepZi ) + .5 ;
93 if ( xx < 0 || yy < 0 || xx >= 65536 || yy >= 65536 ) {
94 std::cout << "!!!! hit packing error!!! " << xx << " " << yy << " " << std::endl;
96 // HitData is bin sorted
97 fHitDataY[row->fHitNumberOffset + hitIndex] = xx;
98 fHitDataZ[row->fHitNumberOffset + hitIndex] = yy;
102 void AliHLTTPCCASliceData::Clear()
107 void AliHLTTPCCASliceData::InitializeRows( const AliHLTTPCCAParam &p )
109 // initialisation of rows
111 for ( int i = 0; i < p.NRows(); ++i ) {
112 fRows[i].fX = p.RowX( i );
113 fRows[i].fMaxY = CAMath::Tan( p.DAlpha() / 2. ) * fRows[i].fX;
117 GPUh() char* AliHLTTPCCASliceData::SetGPUSliceDataMemory(char* pGPUMemory, const AliHLTTPCCAClusterData *data)
119 fMemory = (char*) pGPUMemory;
120 return(pGPUMemory + SetPointers(data, false));
123 size_t AliHLTTPCCASliceData::SetPointers(const AliHLTTPCCAClusterData *data, bool allocate)
125 const int numberOfRows = data->LastRow() - data->FirstRow();
126 enum { kVectorAlignment = sizeof( int ) };
127 const int numberOfHitsPlusAlignment = NextMultipleOf < kVectorAlignment / sizeof( int ) > ( fNumberOfHits );
128 const int memorySize =
130 numberOfHitsPlusAlignment * 4 * sizeof( short ) +
132 NextMultipleOf<kVectorAlignment>( ( 23 * numberOfRows + 4 * fNumberOfHits + 3 ) * sizeof( int ) ) +
133 // HitWeights, ClusterDataIndex
134 numberOfHitsPlusAlignment * 2 * sizeof( int );
136 if ( fMemorySize < memorySize ) {
137 fMemorySize = memorySize;
141 fMemory = new char[fMemorySize + 4];// kVectorAlignment];
146 AssignMemory( fLinkUpData, mem, numberOfHitsPlusAlignment );
147 AssignMemory( fLinkDownData, mem, numberOfHitsPlusAlignment );
148 AssignMemory( fHitDataY, mem, numberOfHitsPlusAlignment );
149 AssignMemory( fHitDataZ, mem, numberOfHitsPlusAlignment );
150 AssignMemory( fFirstHitInBin, mem, 23 * numberOfRows + 4 * fNumberOfHits + 3 );
151 AssignMemory( fHitWeights, mem, numberOfHitsPlusAlignment );
152 AssignMemory( fClusterDataIndex, mem, numberOfHitsPlusAlignment );
153 return(mem - fMemory);
156 void AliHLTTPCCASliceData::InitFromClusterData( const AliHLTTPCCAClusterData &data )
158 // initialisation from cluster data
160 ////////////////////////////////////
162 ////////////////////////////////////
164 //const int numberOfRows = data.LastRow() - data.FirstRow();
165 fNumberOfHits = data.NumberOfClusters();
167 /* TODO Vectorization
168 for ( int rowIndex = data.FirstRow(); rowIndex <= data.LastRow(); ++rowIndex ) {
169 int NumberOfClusters( int rowIndex ) const;
171 const int memorySize = fNumberOfHits * sizeof( short_v::Type )
173 SetPointers(&data, true);
175 ////////////////////////////////////
176 // 2. fill HitData and FirstHitInBin
177 ////////////////////////////////////
179 for ( int rowIndex = 0; rowIndex < data.FirstRow(); ++rowIndex ) {
180 AliHLTTPCCARow &row = fRows[rowIndex];
181 row.fGrid.CreateEmpty();
184 row.fHitNumberOffset = 0;
185 row.fFirstHitInBinOffset = 0;
194 for ( int rowIndex = data.LastRow() + 1; rowIndex < 160; ++rowIndex ) {
195 AliHLTTPCCARow &row = fRows[rowIndex];
196 row.fGrid.CreateEmpty();
199 row.fHitNumberOffset = 0;
200 row.fFirstHitInBinOffset = 0;
211 AliHLTResizableArray<AliHLTTPCCAHit> binSortedHits( fNumberOfHits );
213 int gridContentOffset = 0;
215 int binCreationMemorySize = 103 * 2 + fNumberOfHits;
216 AliHLTResizableArray<unsigned short> binCreationMemory( binCreationMemorySize );
218 for ( int rowIndex = data.FirstRow(); rowIndex <= data.LastRow(); ++rowIndex ) {
219 AliHLTTPCCARow &row = fRows[rowIndex];
220 row.fNHits = data.NumberOfClusters( rowIndex );
221 assert( row.fNHits < ( 1 << sizeof( unsigned short ) * 8 ) );
222 row.fHitNumberOffset = data.RowOffset( rowIndex );
223 row.fFirstHitInBinOffset = gridContentOffset;
225 CreateGrid( &row, data );
226 const AliHLTTPCCAGrid &grid = row.fGrid;
227 const int numberOfBins = grid.N();
229 int binCreationMemorySizeNew;
230 if ( ( binCreationMemorySizeNew = numberOfBins * 2 + 6 + row.fNHits ) > binCreationMemorySize ) {
231 binCreationMemorySize = binCreationMemorySizeNew;
232 binCreationMemory.Resize( binCreationMemorySize );
235 AliHLTArray<unsigned short> c = binCreationMemory; // number of hits in all previous bins
236 AliHLTArray<unsigned short> bins = c + ( numberOfBins + 3 ); // cache for the bin index for every hit in this row
237 AliHLTArray<unsigned short> filled = bins + row.fNHits; // counts how many hits there are per bin
239 for ( unsigned int bin = 0; bin < row.fGrid.N() + 3; ++bin ) {
240 filled[bin] = 0; // initialize filled[] to 0
243 for ( int hitIndex = 0; hitIndex < row.fNHits; ++hitIndex ) {
244 const int globalHitIndex = row.fHitNumberOffset + hitIndex;
245 const unsigned short bin = row.fGrid.GetBin( data.Y( globalHitIndex ), data.Z( globalHitIndex ) );
246 bins[hitIndex] = bin;
250 unsigned short n = 0;
251 for ( int bin = 0; bin < numberOfBins + 3; ++bin ) {
256 for ( int hitIndex = 0; hitIndex < row.fNHits; ++hitIndex ) {
257 const unsigned short bin = bins[hitIndex];
259 const unsigned short ind = c[bin] + filled[bin]; // generate an index for this hit that is >= c[bin] and < c[bin + 1]
260 const int globalBinsortedIndex = row.fHitNumberOffset + ind;
261 const int globalHitIndex = row.fHitNumberOffset + hitIndex;
263 // allows to find the global hit index / coordinates from a global bin sorted hit index
264 fClusterDataIndex[globalBinsortedIndex] = globalHitIndex;
265 binSortedHits[globalBinsortedIndex].SetY( data.Y( globalHitIndex ) );
266 binSortedHits[globalBinsortedIndex].SetZ( data.Z( globalHitIndex ) );
269 PackHitData( &row, binSortedHits );
271 for ( int i = 0; i < numberOfBins; ++i ) {
272 fFirstHitInBin[row.fFirstHitInBinOffset + i] = c[i]; // global bin-sorted hit index
274 const unsigned short a = c[numberOfBins];
275 // grid.N is <= row.fNHits
276 const int nn = numberOfBins + grid.Ny() + 3;
277 for ( int i = numberOfBins; i < nn; ++i ) {
278 assert( row.fFirstHitInBinOffset + i < 23 * numberOfRows + 4 * fNumberOfHits + 3 );
279 fFirstHitInBin[row.fFirstHitInBinOffset + i] = a;
283 gridContentOffset += nn;
287 //SG cell finder - test code
289 if ( fTmpHitInputIDs ) delete[] fTmpHitInputIDs;
290 fTmpHitInputIDs = new int [NHits];
291 const float areaY = .5;
292 const float areaZ = .5;
293 int newRowNHitsTotal = 0;
294 bool *usedHits = new bool [NHits];
295 for ( int iHit = 0; iHit < NHits; iHit++ ) usedHits[iHit] = 0;
296 for ( int iRow = 0; iRow < fParam.NRows(); iRow++ ) {
297 rowHeaders[iRow*2 ] = newRowNHitsTotal; // new first hit
298 rowHeaders[iRow*2+1] = 0; // new N hits
300 int oldRowFirstHit = RowFirstHit[iRow];
301 int oldRowLastHit = oldRowFirstHit + RowNHits[iRow];
302 for ( int iHit = oldRowFirstHit; iHit < oldRowLastHit; iHit++ ) {
303 if ( usedHits[iHit] ) continue;
312 if ( 0 ) for ( int jHit = iHit + 1; jHit < oldRowLastHit; jHit++ ) {//SG!!!
313 //if( usedHits[jHit] ) continue;
314 float dy = Y[jHit] - y0;
315 float dz = Z[jHit] - z0;
316 if ( CAMath::Abs( dy ) < areaY && CAMath::Abs( dz ) < areaZ ) {
324 int id = newRowNHitsTotal + newRowNHits;
325 hitsXYZ[id*3+0 ] = cx / nclu;
326 hitsXYZ[id*3+1 ] = cy / nclu;
327 hitsXYZ[id*3+2 ] = cz / nclu;
328 fTmpHitInputIDs[id] = iHit;
331 rowHeaders[iRow*2+1] = newRowNHits;
332 newRowNHitsTotal += newRowNHits;
334 NHitsTotal() = newRowNHitsTotal;
335 reinterpret_cast<int*>( fInputEvent )[1+fParam.NRows()*2] = newRowNHitsTotal;
341 void AliHLTTPCCASliceData::ClearHitWeights()
345 #ifdef ENABLE_VECTORIZATION
346 const int_v v0( Zero );
347 const int *const end = fHitWeights + fNumberOfHits;
348 for ( int *mem = fHitWeights; mem < end; mem += v0.Size ) {
352 for ( int i = 0; i < fNumberOfHits; ++i ) {
358 void AliHLTTPCCASliceData::ClearLinks()
362 #ifdef ENABLE_VECTORIZATION
363 const short_v v0( -1 );
364 const short *const end1 = fLinkUpData + fNumberOfHits;
365 for ( short *mem = fLinkUpData; mem < end; mem += v0.Size ) {
368 const short *const end2 = fLinkDownData + fNumberOfHits;
369 for ( short *mem = fLinkDownData; mem < end; mem += v0.Size ) {
373 for ( int i = 0; i < fNumberOfHits; ++i ) {
376 for ( int i = 0; i < fNumberOfHits; ++i ) {
377 fLinkDownData[i] = -1;