From 768be5c3f21b58937ed9b086837d1980c81feaf1 Mon Sep 17 00:00:00 2001 From: richterm Date: Thu, 6 Mar 2008 00:07:23 +0000 Subject: [PATCH] added ALTRO data encoder and corresponding unit test --- HLT/RCU/AliHLTAltroEncoder.cxx | 225 ++++++++++++++ HLT/RCU/AliHLTAltroEncoder.h | 151 ++++++++++ HLT/RCU/Makefile.am | 2 + HLT/RCU/test/Makefile.am | 23 ++ HLT/RCU/test/testAliHLTAltroEncoder.C | 403 ++++++++++++++++++++++++++ HLT/configure.ac | 1 + HLT/libAliHLTRCU.pkg | 1 + 7 files changed, 806 insertions(+) create mode 100644 HLT/RCU/AliHLTAltroEncoder.cxx create mode 100644 HLT/RCU/AliHLTAltroEncoder.h create mode 100644 HLT/RCU/test/Makefile.am create mode 100644 HLT/RCU/test/testAliHLTAltroEncoder.C diff --git a/HLT/RCU/AliHLTAltroEncoder.cxx b/HLT/RCU/AliHLTAltroEncoder.cxx new file mode 100644 index 00000000000..6fa525716cc --- /dev/null +++ b/HLT/RCU/AliHLTAltroEncoder.cxx @@ -0,0 +1,225 @@ +// $Id$ + +//************************************************************************** +//* This file is property of and copyright by the ALICE HLT Project * +//* ALICE Experiment at CERN, All rights reserved. * +//* * +//* Primary Authors: Matthias Richter * +//* for The ALICE HLT Project. * +//* * +//* Permission to use, copy, modify and distribute this software and its * +//* documentation strictly for non-commercial purposes is hereby granted * +//* without fee, provided that the above copyright notice appears in all * +//* copies and that both the copyright notice and this permission notice * +//* appear in the supporting documentation. The authors make no claims * +//* about the suitability of this software for any purpose. It is * +//* provided "as is" without express or implied warranty. * +//************************************************************************** + +/** @file AliHLTAltroEncoder.cxx + @author Matthias Richter + @date + @brief Encoder class for 10/40bit Altro Data format +*/ + +#include +#include +#include "AliHLTAltroEncoder.h" + +/** ROOT macro for the implementation of ROOT specific class methods */ +ClassImp(AliHLTAltroEncoder) + +AliHLTAltroEncoder::AliHLTAltroEncoder() + : + fpBuffer(NULL), + fBufferSize(0), + fPrevTimebin(AliHLTUInt16MAX), + fBunchLength(0), + fChannelStart(0), + fChannel(AliHLTUInt16MAX), + fChannels(), + fOffset(0), + f10bitWords(0), + fOrder(kUnknownOrder) +{ + // see header file for class documentation + // or + // refer to README to build package + // or + // visit http://web.ift.uib.no/~kjeks/doc/alice-hlt +} + +AliHLTAltroEncoder::AliHLTAltroEncoder(AliHLTUInt8_t* pBuffer, int iSize) + : + fpBuffer(pBuffer), + fBufferSize(iSize), + fPrevTimebin(AliHLTUInt16MAX), + fBunchLength(0), + fChannelStart(0), + fChannel(AliHLTUInt16MAX), + fChannels(), + fOffset(0), + f10bitWords(0), + fOrder(kUnknownOrder) +{ + // see header file for class documentation +} + +AliHLTAltroEncoder::~AliHLTAltroEncoder() +{ + // see header file for class documentation +} + +int AliHLTAltroEncoder::SetBuffer(AliHLTUInt8_t* pBuffer, int iSize) +{ + // see header file for class documentation + fpBuffer=pBuffer; + fBufferSize=iSize; + + return 0; +} + +int AliHLTAltroEncoder::AddSignal(AliHLTUInt16_t signal, AliHLTUInt16_t timebin) +{ + // see header file for class documentation + int iResult=0; + if (fPrevTimebin!=AliHLTUInt16MAX) { + assert(fPrevTimebin!=timebin); + if (fOrder==kUnknownOrder) { + if (fPrevTimebin+1==timebin) fOrder=kAscending; + else if (fPrevTimebin==timebin+1) fOrder=kDescending; + } + if ((fOrder!=kAscending || fPrevTimebin+1!=timebin) && + (fOrder!=kDescending || fPrevTimebin!=timebin+1)) { + // Finalize bunch and start new one + iResult=SetBunch(); + } + } + + if (iResult>=0 && (iResult=Add10BitValue(signal))>=0) { + fBunchLength++; + } + assert(fOffset*4<=f10bitWords*5); + fPrevTimebin=timebin; + return iResult; +} + +int AliHLTAltroEncoder::SetChannel(AliHLTUInt16_t hwaddress) +{ + // see header file for class documentation + int iResult=0; + int added10BitWords=0; + if (!fpBuffer) return -ENODEV; + if (fOffset+5>=fBufferSize) { + HLTWarning("buffer too small too finalize channel: %d of %d byte(s) already used", fOffset, fBufferSize); + return -ENOSPC; + } + + if (iResult>=0 && + (iResult=SetBunch())>=0) { + AliHLTUInt16_t length=f10bitWords-fChannelStart; + if ((iResult=Pad40Bit())<0) return iResult; + // 2 words for the SetBunch (end time and length) and the + // padded words to fill 40bit word + added10BitWords=iResult+2; + assert((length+iResult)%4==0); + //HLTInfo("%d %x", hwaddress, hwaddress); + fpBuffer[fOffset++]=hwaddress&0xff; + fpBuffer[fOffset++]=0xa0 | (hwaddress>>8)&0xf; + fpBuffer[fOffset++]=length&0xff; + fpBuffer[fOffset++]=0xa8 | (length>>8)&0x3; + fpBuffer[fOffset++]=0xaa; + f10bitWords+=4; + fChannelStart=f10bitWords; + fChannels.push_back(hwaddress); + fPrevTimebin=AliHLTUInt16MAX; + } + if (iResult<0) return iResult; + return added10BitWords; +} + +int AliHLTAltroEncoder::AddChannelSignal(AliHLTUInt16_t signal, AliHLTUInt16_t timebin, AliHLTUInt16_t hwaddress) +{ + // see header file for class documentation + int iResult=0; + int added10BitWords=0; + if (fChannel==AliHLTUInt16MAX) { + fChannel=hwaddress; + } else if (fChannel!=hwaddress) { + iResult=SetChannel(fChannel); + added10BitWords=iResult; + fChannel=hwaddress; + } + + if (iResult>=0) { + if ((iResult=AddSignal(signal, timebin))>=0) + added10BitWords++; + } + + if (iResult<0) return iResult; + return added10BitWords; +} + +int AliHLTAltroEncoder::GetTotal40bitWords() +{ + // see header file for class documentation + if (fChannelStart!=f10bitWords) { + HLTWarning("unterminated channel found, check calling sequence"); + } + assert(fChannelStart%4==0); + + return fChannelStart; +} + +int AliHLTAltroEncoder::SetBunch() +{ + // see header file for class documentation + int iResult=0; + + // return if the bunch has already been set + if (fBunchLength==0) return 0; + + // fill time bin and bunch length + if ((iResult=Add10BitValue(fPrevTimebin))>=0) { + iResult=Add10BitValue(fBunchLength+2); + fBunchLength=0; + iResult=2; + } + return iResult; +} + +int AliHLTAltroEncoder::Add10BitValue(AliHLTUInt16_t value) +{ + // see header file for class documentation + int iResult=0; + if (!fpBuffer) return -ENODEV; + if (fOffset+2>=fBufferSize) { + HLTWarning("buffer too small too add 10bit word: %d of %d byte(s) already used", fOffset, fBufferSize); + return -ENOSPC; + } + + int bit=(f10bitWords%4)*10; + int shift=bit%8; + unsigned short maskLow=~((0xff<>8); + //unsigned short maskHigh=~((0xff<<((bit+10)%8))>>8); + fpBuffer[fOffset++]|=maskLow&(value<>(8-shift); + f10bitWords++; + if (f10bitWords%4==0) fOffset++; + + return iResult; +} + +int AliHLTAltroEncoder::Pad40Bit() +{ + // see header file for class documentation + int iResult=0; + int added10BitWords=0; + while (iResult>=0 && f10bitWords%4!=0) { + if ((iResult=Add10BitValue(0x2aa))>=0) { + added10BitWords++; + } + } + if (iResult<0) return iResult; + return added10BitWords; +} diff --git a/HLT/RCU/AliHLTAltroEncoder.h b/HLT/RCU/AliHLTAltroEncoder.h new file mode 100644 index 00000000000..058080797fe --- /dev/null +++ b/HLT/RCU/AliHLTAltroEncoder.h @@ -0,0 +1,151 @@ +//-*- Mode: C++ -*- +// $Id$ + +#ifndef ALIHLTALTROENCODER_H +#define ALIHLTALTROENCODER_H +//* This file is property of and copyright by the ALICE HLT Project * +//* ALICE Experiment at CERN, All rights reserved. * +//* See cxx source for full Copyright notice * + +/** @file AliHLTAltroEncoder.h + @author Matthias Richter + @date + @brief Encoder class for 10/40bit Altro Data format +*/ + +// see below for class documentation +// or +// refer to README to build package +// or +// visit http://web.ift.uib.no/~kjeks/doc/alice-hlt + +#include "AliHLTDataTypes.h" +#include "AliHLTLogging.h" +#include + +#define AliHLTUInt16MAX 0xffff + +/** + * @class AliHLTAltroEncoder + * Encoder of the RCU/Altro data format. + * The class allows to encodes data sets of channel, timebin and signal + * value into the 10bit/40bit Altro format. It works on a provided buffer. + * + * Signal values can be added by using the ::AddSignal function. This + * functions works on a 'current channel'. If data is supposed to go into + * a new channel, the ::SetChannel function has to be used. + */ +class AliHLTAltroEncoder : AliHLTLogging { + public: + /** default constructor */ + AliHLTAltroEncoder(); + /** constructor */ + AliHLTAltroEncoder(AliHLTUInt8_t* pBuffer, int iSize); + /** destructor */ + virtual ~AliHLTAltroEncoder(); + + /** + * Set the target buffer. + */ + int SetBuffer(AliHLTUInt8_t* pBuffer, int iSize); + + /** + * Add a signal value. + * If the timebin is a consecutive timebin, the signal is added to the + * current bunch. If not, the previous bunch is terminated and a new + * one opened. + * + * The first timebins decide whether the order is ascending or descending. + * @param signal 10bit signal value + * @param timebin 10bot time bin value + */ + int AddSignal(AliHLTUInt16_t signal, AliHLTUInt16_t timebin); + + /** + * Set and terminate the current channel. + * + * @param hwaddress Hardware address of the channel + */ + int SetChannel(AliHLTUInt16_t hwaddress); + + /** + * Add a signal value. + * The function is a combination of ::AddSignal and ::SetChannel. + * All signal of the same channel are added and if a new channel is detected, + * the current one is terminated and a new one created. + * + * @param signal 10bit signal value + * @param timebin 10bot time bin value + * @param hwaddress Hardware address of the channel + * @return number of 10bit words added + */ + int AddChannelSignal(AliHLTUInt16_t signal, AliHLTUInt16_t timebin, AliHLTUInt16_t hwaddress); + + /** + * Get total number of 40bit Altro words + */ + int GetTotal40bitWords(); + + enum { + kUnknownOrder = 0, + kAscending, + kDescending + }; + + protected: + + private: + /** copy constructor prohibited */ + AliHLTAltroEncoder(const AliHLTAltroEncoder&); + /** assignment operator prohibited */ + AliHLTAltroEncoder& operator=(const AliHLTAltroEncoder&); + + /** + * Add 10bit value to the buffer + */ + int Add10BitValue(AliHLTUInt16_t value); + + /** + * Fill with 0x2aa paddings to reach complete 40bit word + */ + int Pad40Bit(); + + /** + * Finalize the current bunch + */ + int SetBunch(); + + /// external data buffer + AliHLTUInt8_t* fpBuffer; //!transient + + /// size of the data buffer + int fBufferSize; //!transient + + /// the previous time bin + AliHLTUInt16_t fPrevTimebin; //!transient + + /// length of the current bunch + AliHLTUInt16_t fBunchLength; //!transient + + /// start of the current channel in 10bit word count + AliHLTUInt16_t fChannelStart; //!transient + + /// the current channel + AliHLTUInt16_t fChannel; //!transient + + /// list of already finished channels + vector fChannels; //!transient + + /// current byte offset + int fOffset; //!transient + + /// current 10bit word count + int f10bitWords; //!transient + + /// time bin order + int fOrder; //!transient + + ClassDef(AliHLTAltroEncoder, 0); +}; + +#endif diff --git a/HLT/RCU/Makefile.am b/HLT/RCU/Makefile.am index 51bf284b98a..f698935bdc0 100644 --- a/HLT/RCU/Makefile.am +++ b/HLT/RCU/Makefile.am @@ -8,6 +8,8 @@ # e.g. for libAliHLTRCU, MODULE=AliHLTRCU MODULE = AliHLTRCU +SUBDIRS = test + EXTRA_DIST = # library definition diff --git a/HLT/RCU/test/Makefile.am b/HLT/RCU/test/Makefile.am new file mode 100644 index 00000000000..8d4a5b37e6e --- /dev/null +++ b/HLT/RCU/test/Makefile.am @@ -0,0 +1,23 @@ +# $Id$ +# Makefile template Alice HLT RCU library test programs + +AM_CPPFLAGS = -I$(top_srcdir)/BASE \ + -I$(srcdir)/.. \ + @ALIROOT_CPPFLAGS@ \ + -I@ROOTINCDIR@ + +EXTRA_DIST = + +check_PROGRAMS = testAliHLTAltroEncoder + +testAliHLTAltroEncoder_SOURCES = testAliHLTAltroEncoder.C +testAliHLTAltroEncoder_LDADD = $(top_builddir)/BASE/libHLTbase.la \ + $(top_builddir)/RCU/libAliHLTRCU.la + +# linker flags +altro_encoder_LDFLAGS = -L@ROOTLIBDIR@ \ + @ROOTLIBS@ \ + @ALIROOT_LDFLAGS@ \ + @ALIROOT_LIBS@ + +TESTS = $(check_PROGRAMS) \ No newline at end of file diff --git a/HLT/RCU/test/testAliHLTAltroEncoder.C b/HLT/RCU/test/testAliHLTAltroEncoder.C new file mode 100644 index 00000000000..fd6df3dd244 --- /dev/null +++ b/HLT/RCU/test/testAliHLTAltroEncoder.C @@ -0,0 +1,403 @@ +// $Id$ + +/************************************************************************** + * This file is property of and copyright by the ALICE HLT Project * + * ALICE Experiment at CERN, All rights reserved. * + * * + * Primary Authors: Matthias Richter * + * for The ALICE HLT Project. * + * * + * Permission to use, copy, modify and distribute this software and its * + * documentation strictly for non-commercial purposes is hereby granted * + * without fee, provided that the above copyright notice appears in all * + * copies and that both the copyright notice and this permission notice * + * appear in the supporting documentation. The authors make no claims * + * about the suitability of this software for any purpose. It is * + * provided "as is" without express or implied warranty. * + **************************************************************************/ + +/** @file altro-encoder.C + @author Matthias Richter + @date + @brief Test macro/program for the AliHLTAltroEncoder + */ + +#ifndef __CINT__ +#include "TFile.h" +#include "TDatime.h" +#include "TRandom.h" +#include "TArrayI.h" +#include "TArrayC.h" +#include "TSystem.h" +#include "AliRawDataHeader.h" +#include "AliAltroDecoder.h" +#include "AliAltroData.h" +#include "AliAltroBunch.h" +#include "AliHLTAltroEncoder.h" +#include +#endif //__CINT__ + +#ifndef __CINT__ +const int sizeofAliRawDataHeader=sizeof(AliRawDataHeader); +#else +// cint does not handle sizeof correctly +const int sizeofAliRawDataHeader=32; +#endif + +///////////////////////////////////////////////////////////////// +///////////////////////////////////////////////////////////////// +///////////////////////////////////////////////////////////////// +// +// configuration of the test program +// + +// printouts or not +const bool bVerbose=false; + +// the encoder can be used in two different modes: using +// AddSignal and terminating each channel by explicitely calling +// SetChannel, or the combined version AddChannelSignal +const bool bUseAddChannelSignal=true; + +// some defaults +const int maxChannels=100; +const int maxBunches=50; +const int maxTimebin=1024; +const int maxSignal=1024; +const int maxEncodedDataSize=40000+sizeofAliRawDataHeader; + +// file dumps +const char* encDataDumpFile=NULL;//"/tmp/altro-enc.dat"; +const char* encodedDataFile="/tmp/altro-encoded.dat"; +const char* simulatedDataFile="/tmp/altro-simulated.dat"; + +///////////////////////////////////////////////////////////////// +///////////////////////////////////////////////////////////////// +///////////////////////////////////////////////////////////////// + +Bool_t seedSet=kFALSE; + +/** + * Get a random number in the given range. + */ +int GetRandom(int min, int max) +{ + if (max-min<2) return min; + static TRandom rand; + if (!seedSet) { + TDatime dt; + rand.SetSeed(dt.Get()); + seedSet=kTRUE; + } + return rand.Integer(max-min); +} + +/** + * Print the bunch information of a channel. + * The function goes recursively to the first bunch of the + * channel and prints this one first. + * @return number of 10bit words + */ +int DumpBunchRecursive(int nofBunches, int* pData, int size) +{ + if (!pData || size<2) return -1; + int pos=size; + int bunchLength=pData[--pos]; + int bunchEndTime=pData[--pos]; + int read=0; + if (bunchLength1) { + read=DumpBunchRecursive(nofBunches-1, pData, pos-bunchLength); + } + cout << " bunch length " << bunchLength << ", end time " << bunchEndTime << ":"; + + for (int time=bunchEndTime; time>bunchEndTime-bunchLength; time--) { + if (pos<1) { + pos=0; + cerr << "no data for bunch " << endl; + return -1; + } + //cout << " " << pData[--pos]; + } + cout << endl; + if (read<0) return read; + return read+2+bunchLength; +} + +/** + * Write the encoded data to a file. + */ +template +void DumpDataArray(T *array, const char* filename, int memberSize) +{ + if (array->GetSize()==0) return; + + ios::openmode filemode=(ios::openmode)0; + ofstream rawfile(filename, filemode); + if (rawfile.good()) { + rawfile.write(reinterpret_cast(array->GetArray()), array->GetSize()*memberSize); + } + rawfile.close(); +} + +/** + * Print the simulated data. + */ +void PrintSimulatedData(TArrayI& data) +{ + cout << endl << "****** readback *******" << endl << endl; + int dataPos=data.GetSize(); + while (dataPos>0) { + int channelAddress=data[--dataPos]; + int nofBunches=data[--dataPos]; + cout << " ------------------ new channel -------------------------" << endl; + if (nofBunches>0) { + int read=DumpBunchRecursive(nofBunches, data.GetArray(), dataPos); + if (read<0) return; + dataPos-=read; + } + cout << " channel " << channelAddress << ": number of bunches " << nofBunches << endl; + } +} + +int Compare(TArrayI& simData, TArrayC& encData) +{ + if (bVerbose) cout << endl << "****** compare *******" << endl << endl; + + // can not have a static AltroDecoder, crash when function + // is called. I had a similar problem in the AliHLTAltroChannelSelectorComponent + + int iResult=0; + AliAltroDecoder* decoder=new AliAltroDecoder; + if (iResult>=0 && decoder->SetMemory((UChar_t*)encData.GetArray(), (UInt_t)encData.GetSize())<0) { + cout << "error setting up decoder " << endl; + iResult=-1; + } + + if (iResult>=0 && !decoder->Decode()) { + cout << "error decoding data" << endl; + iResult=-1; + } + + AliAltroData altrochannel; + int dataPos=simData.GetSize(); + while (iResult>=0 && decoder->NextChannel(&altrochannel)) { + int hwadd=altrochannel.GetHadd(); + if (dataPos<2) { + cout << "missmatch in simulated data" << endl; + iResult=-1; + break; + } + int channelAddress=simData[--dataPos]; + int nofBunches=simData[--dataPos]; + if (channelAddress!=hwadd) { + cout << "channel address missmatch: simulated " << channelAddress << " encoded " << hwadd << endl; + iResult=-1; + break; + } + + if (bVerbose) cout << "comparing channel " << channelAddress << ", " << nofBunches << " bunche(s)" << endl; + + AliAltroBunch altrobunch; + while (iResult>=0 && altrochannel.NextBunch(&altrobunch) && nofBunches-->0) { + if (dataPos<2) { + cout << "error reading bunch size and time bin from simulated data" << endl; + iResult=-1; + break; + } + int bunchLength=simData[--dataPos]; + int bunchEndTime=simData[--dataPos]; + if (bunchLength!=(int)altrobunch.GetBunchSize()) { + cout << "bunch length missmatch: simulated " << bunchLength << " encoded " << altrobunch.GetBunchSize() << hex << " (" << altrobunch.GetBunchSize() << ")" << dec << endl; + iResult=-1; + break; + } + if (bunchEndTime!=(int)altrobunch.GetEndTimeBin()) { + cout << "bunch end time missmatch: simulated " << bunchEndTime << " encoded " << altrobunch.GetEndTimeBin() << endl; + iResult=-1; + break; + } + if (bVerbose) cout << " bunch length " << bunchLength << ", end time " << bunchEndTime << endl; + const UInt_t* bunchData=altrobunch.GetData(); + if (bunchLength>dataPos) { + cout << "error reading simulated bunch data, required "<< bunchLength << " available " << dataPos << endl; + iResult=-1; + break; + } + Int_t* pSim=simData.GetArray(); + for (int bin=0; binLoad("libAliHLTRCU.so"); +#endif + + AliHLTAltroEncoder encoder; + Char_t* pTgt=encData.GetArray(); + pTgt+=sizeofAliRawDataHeader; + encoder.SetBuffer((AliHLTUInt8_t*)pTgt, maxAltroDataSize); + + if (bVerbose) cout << "number of channels: " << nofChannels << endl; + int channelAddress=-1; + int lastChannel=-1; + int nof10BitWords=0; + // The nof10BitWords value is aligned to 4. In addition, one + // 40bit word is needed for the channel trailer + for (int channel=0; channel0; bunch++) { + bunchEndTime=GetRandom(0, bunchEndTime-1); + int bunchLength=GetRandom(0, bunchEndTime<10?bunchEndTime:10); + if (bunchLength==0) continue; + // check if there is enough space for all the signals, end time + // and bunch length. The value is aligned to 4. In addition, one + // 40bit word is needed for the channel trailer + if (((((nof10BitWords+bunchLength+2)/4)+2)*5)>=maxAltroDataSize) break; + totalBunches++; + + if (bVerbose) cout << " bunch " << bunch << ", length " << bunchLength << ", end time " << bunchEndTime << ":"; + + if (simData.GetSize()0) nof10BitWords+=added; + } + if (bVerbose) cout << endl; + simData[dataPos++]=bunchEndTime; + simData[dataPos++]=bunchLength; + } + if (simData.GetSize()0) { + simData[dataPos++]=totalBunches; + simData[dataPos++]=channelAddress; + } + + if (!bUseAddChannelSignal && lastChannel>=0) { + encoder.SetChannel(lastChannel); + } + + if (bVerbose) cout << " channel " << channelAddress << ": number of bunches " << totalBunches << endl; + + } + if (bUseAddChannelSignal && lastChannel>=0) encoder.SetChannel(lastChannel); + + int nof40bitWords=encoder.GetTotal40bitWords(); + pTgt+=nof40bitWords*5/4; + *((Int_t*)pTgt)=nof40bitWords; + int encDataSize=sizeofAliRawDataHeader+nof40bitWords*5/4+sizeof(Int_t); + encData.Set(encDataSize); + + if (bVerbose) cout << "simulated data array:" << simData.GetSize() << " , ALTRO block length: " << nof40bitWords << " ALTRO words -> encoded data: " << encData.GetSize() << endl; + + ///////////////////////////////////////////////////////// + // some debugging options + + if (encDataDumpFile) DumpDataArray(&encData, encDataDumpFile, 1); + + simData.Set(dataPos); + if (bVerbose) PrintSimulatedData(simData); + + ///////////////////////////////////////////////////////// + // read back end compare the encoded data + + if (simData.GetSize()>0 && Compare(simData, encData)<0) { + // dump files for further debugging + DumpDataArray(&encData, encodedDataFile, 1); + DumpDataArray(&simData, simulatedDataFile, 4); + return -1; + } else { + if (bVerbose) cout << "check successfully completed: " << nof40bitWords << " ALTRO words" << endl; + } + + return 0; +} + +int main(int argc, const char** argv) +{ +// CompareDumpFiles(); +// return 0; + + int iResult=0; + int iCount=10000; + for (int i=0; i