--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/userlibandfileserver/fileserver/fs_utils/bit_vector.cpp Mon Jan 18 21:31:10 2010 +0200
@@ -0,0 +1,883 @@
+// Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
+// All rights reserved.
+// This component and the accompanying materials are made available
+// under the terms of the License "Eclipse Public License v1.0"
+// which accompanies this distribution, and is available
+// at the URL "http://www.eclipse.org/legal/epl-v10.html".
+//
+// Initial Contributors:
+// Nokia Corporation - initial contribution.
+//
+// Contributors:
+//
+// Description:
+//
+// Collection of common constants, utility functions, etc. for the file server and file systems.
+// Definitions here must be filesystem-agnostic, i.e. generic enougs to be used by every file system
+//
+// This is the internal file and must not be exported.
+
+/**
+ @file
+ @internalTechnology
+*/
+
+#include "bit_vector.h"
+
+
+//#######################################################################################################################################
+//# RBitVector class implementation
+//#######################################################################################################################################
+
+const TUint32 K_FFFF = 0xFFFFFFFF; //-- all one bits, beware rigth shifts of signed integers!
+
+RBitVector::RBitVector()
+ :iNumBits(0), ipData(NULL), iNumWords(0)
+ {
+ }
+
+
+RBitVector::~RBitVector()
+ {
+ Close();
+ }
+
+/**
+ Panics.
+ @param aPanicCode a panic code
+*/
+void RBitVector::Panic(TPanicCode aPanicCode) const
+ {
+ _LIT(KPanicCat,"RBitVector");
+ User::Panic(KPanicCat, aPanicCode);
+ }
+
+/** explicitly closes the object and deallocates memory */
+void RBitVector::Close()
+ {
+ iNumBits = 0;
+ iNumWords =0;
+ User::Free(ipData);
+ ipData = NULL;
+ }
+
+//-----------------------------------------------------------------------------
+
+/**
+ Comparison perator.
+ @param aRhs a vector to compate with.
+ @panic ESizeMismatch in the case of different vector sizes
+*/
+TBool RBitVector::operator==(const RBitVector& aRhs) const
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
+
+
+ if(!iNumBits)
+ return ETrue; //-- comparing 0-lenght arrays
+
+ if(this == &aRhs)
+ {//-- comparing with itself, potential source of errors
+ ASSERT(0);
+ return ETrue;
+ }
+
+ if(iNumWords >= 1)
+ {
+ const TUint32 cntBytes = (iNumBits >> 5) << 2; //-- bytes to compare
+ if(memcompare((const TUint8*)ipData, cntBytes, (const TUint8*)aRhs.ipData, cntBytes))
+ return EFalse;
+ }
+
+ const TUint32 bitsRest = iNumBits & 0x1F;
+ if(bitsRest)
+ {
+ const TUint32 mask = K_FFFF >> (32-bitsRest);
+ return ( (ipData[iNumWords-1] & mask) == (aRhs.ipData[iNumWords-1] & mask) );
+ }
+
+ return ETrue;
+ }
+
+TBool RBitVector::operator!=(const RBitVector& aRhs) const
+ {
+ return ! ((*this) == aRhs);
+ }
+
+//-----------------------------------------------------------------------------
+
+/** The same as Create(), but leaves on error */
+void RBitVector::CreateL(TUint32 aNumBits)
+ {
+ User::LeaveIfError(Create(aNumBits));
+ }
+
+
+/**
+ Create the vector with the size of aNumBits bits.
+ @return system-wide error codes:
+ KErrNoMemory unable to allocate sufficient amount of memory for the array
+ KErrInUse an attempt to call Create() for non-empty vector. Close it first.
+ KErrArgument invalid aNumBits value == 0
+*/
+TInt RBitVector::Create(TUint32 aNumBits)
+ {
+
+ if(ipData)
+ return KErrInUse; //-- array is already in use. Close it first.
+
+ if(!aNumBits)
+ return KErrArgument;
+
+ //-- memory is allocated by word (32 bit) quiantities
+ const TUint32 numWords = (aNumBits >> 5) + ((aNumBits & 0x1F) > 0 ? 1:0);
+ ipData = (TUint32*)User::AllocZ(numWords << 2);
+
+ if(!ipData)
+ return KErrNoMemory;
+
+ iNumBits = aNumBits;
+ iNumWords = numWords;
+
+ return KErrNone;
+ }
+
+
+/**
+ Fill a bit vector with a given bit value
+ @param aVal a bit value
+*/
+void RBitVector::Fill(TBool aVal)
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ memset(ipData, (aVal ? 0xFF : 0x00), iNumWords << 2);
+ }
+
+/** Invert all bits in a bit vector */
+void RBitVector::Invert()
+{
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ for(TUint32 i=0; i<iNumWords; ++i)
+ ipData[i] ^= K_FFFF;
+}
+
+
+/**
+ Perform "And" operation between 2 vectors. They shall be the same size.
+ @param aRhs a vector from the right hand side
+ @panic ESizeMismatch in the case of different vector sizes
+*/
+void RBitVector::And(const RBitVector& aRhs)
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
+ for(TUint32 i=0; i<iNumWords; ++i)
+ {
+ ipData[i] &= aRhs.ipData[i];
+ }
+ }
+
+/**
+ Perform "Or" operation between 2 vectors. They shall be the same size.
+ @param aRhs a vector from the right hand side
+ @panic ESizeMismatch in the case of different vector sizes
+*/
+void RBitVector::Or(const RBitVector& aRhs)
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
+ for(TUint32 i=0; i<iNumWords; ++i)
+ {
+ ipData[i] |= aRhs.ipData[i];
+ }
+ }
+
+/**
+ Perform "Xor" operation between 2 vectors. They shall be the same size.
+ @param aRhs a vector from the right hand side
+ @panic ESizeMismatch in the case of different vector sizes
+*/
+void RBitVector::Xor(const RBitVector& aRhs)
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
+ for(TUint32 i=0; i<iNumWords; ++i)
+ {
+ ipData[i] ^= aRhs.ipData[i];
+ }
+ }
+
+//-----------------------------------------------------------------------------
+/**
+ Fill a range from bit number "aIndexFrom" to "aIndexTo" inclusively with the value of aVal
+
+ @param aIndexFrom start bit number (inclusive)
+ @param aIndexTo end bit number (inclusive)
+ @param aVal the value to be used to fill the range (0s or 1s)
+*/
+void RBitVector::Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal)
+ {
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+
+ //-- swap indexes if they are not in order
+ if(aIndexFrom > aIndexTo)
+ {
+ const TUint32 tmp = aIndexFrom;
+ aIndexFrom = aIndexTo;
+ aIndexTo = tmp;
+ }
+
+ __ASSERT_ALWAYS((aIndexFrom < iNumBits) && (aIndexTo < iNumBits), Panic(EIndexOutOfRange));
+
+ const TUint32 wordStart = WordNum(aIndexFrom);
+ const TUint32 wordTo = WordNum(aIndexTo);
+
+ if(aVal)
+ {//-- filling a range with '1'
+
+ TUint32 shift = BitInWord(aIndexFrom);
+ const TUint32 mask1 = (K_FFFF >> shift) << shift;
+
+ TUint32 mask2 = K_FFFF;
+ shift = 1+BitInWord(aIndexTo);
+ if(shift < 32)
+ {
+ mask2 = ~((mask2 >> shift) << shift);
+ }
+
+ if(wordTo == wordStart)
+ {//-- a special case, filling is in the same word
+ ipData[wordStart] |= (mask1 & mask2);
+ }
+ else
+ {
+ ipData[wordStart] |= mask1;
+ ipData[wordTo] |= mask2;
+
+ const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled
+
+ if(wholeWordsBetween)
+ memset(ipData+wordStart+1, 0xFF, wholeWordsBetween << 2);
+
+ }
+ }
+ else
+ {//-- filling a range with '0'
+
+ TUint32 shift = BitInWord(aIndexFrom);
+ const TUint32 mask1 = ~((K_FFFF >> shift) << shift);
+
+ TUint32 mask2 = 0;
+ shift = 1+BitInWord(aIndexTo);
+ if(shift < 32)
+ {
+ mask2 = ((K_FFFF >> shift) << shift);
+ }
+
+ if(wordTo == wordStart)
+ {//-- a special case, filling is in the same word
+ ipData[wordStart] &= (mask1 | mask2);
+ }
+ else
+ {
+ ipData[wordStart] &= mask1;
+ ipData[wordTo] &= mask2;
+
+ const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled
+
+ if(wholeWordsBetween)
+ memset(ipData+wordStart+1, 0x00, wholeWordsBetween << 2);
+
+ }
+ }
+
+ }
+
+//-----------------------------------------------------------------------------
+
+/**
+ Search for a specified bit value ('0' or '1') in the vector from the given position.
+ @param aStartPos zero-based index; from this position the search will start. This position isn't included to the search.
+ On return may contain a new position if the specified bit is found in specified direction.
+ @param aBitVal zero or non-zero bit to search.
+ @param aDir Specifies the search direction
+
+ @return ETrue if the specified bit value is found; aStartPos gets updated.
+ EFalse otherwise.
+
+*/
+TBool RBitVector::Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const
+ {
+ __ASSERT_ALWAYS(aStartPos < iNumBits, Panic(EIndexOutOfRange));
+ ASSERT(iNumWords && ipData);
+
+ switch(aDir)
+ {
+ case ERight: //-- Search from the given position to the right
+ return FindToRight(aStartPos, aBitVal);
+
+ case ELeft: //-- Search from the given position to the left (towards lower index)
+ return FindToLeft(aStartPos, aBitVal);
+
+ case ENearestL: //-- Search for the nearest value in both directions starting from left
+ return FindNearest(aStartPos, aBitVal, ETrue);
+
+ case ENearestR: //-- Search for the nearest value in both directions starting from right
+ return FindNearest(aStartPos, aBitVal, EFalse);
+
+ default:
+ Panic(EWrondFindDirection);
+ return EFalse;
+
+ };
+
+ }
+
+//-----------------------------------------------------------------------------
+/**
+ Internal method to look for a given bit value in the right direction.
+ see TBool RBitVector::Find(...)
+*/
+TBool RBitVector::FindToRight(TUint32& aStartPos, TBool aBitVal) const
+ {
+ if(aStartPos >= iNumBits-1)
+ return EFalse; //-- no way to the right
+
+ const TUint32 startPos = aStartPos+1;
+ const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
+
+ TUint32 wordNum = WordNum(startPos);
+ TUint32 val = ipData[wordNum] ^ fInvert;
+
+ if(wordNum == iNumWords-1)
+ {//-- process the last word in the array, some higher bits might not belong to the bit vector
+ val = MaskLastWord(val);
+ }
+
+ const TUint32 shift = BitInWord(startPos);
+ val = (val >> shift) << shift; //-- mask unused low bits
+
+ if(val)
+ {//-- there are '1' bits in the current word
+ goto found;
+ }
+ else
+ {//-- search in higher words
+ wordNum++;
+
+ while(iNumWords-wordNum > 1)
+ {
+ val = ipData[wordNum] ^ fInvert;
+ if(val)
+ goto found;
+
+ wordNum++;
+ }
+
+ if(wordNum == iNumWords-1)
+ {//-- process the last word in the array, some higher bith might not belong to the bit vector
+ val = ipData[wordNum] ^ fInvert;
+ val = MaskLastWord(val);
+
+ if(val)
+ goto found;
+ }
+ }
+
+ return EFalse; //-- haven't found anything
+
+ found:
+
+ val &= (~val+1); //-- select rightmost bit
+ aStartPos = (wordNum << 5)+Log2(val);
+ return ETrue;
+ }
+
+
+//-----------------------------------------------------------------------------
+
+/**
+ Internal method to look for a given bit value in the left direction.
+ see TBool RBitVector::Find(...)
+*/
+TBool RBitVector::FindToLeft(TUint32& aStartPos, TBool aBitVal) const
+{
+ if(!aStartPos)
+ return EFalse; //-- no way to the left
+
+ const TUint32 startPos=aStartPos-1;
+ const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
+
+ TUint32 wordNum = WordNum(startPos);
+ TUint32 val = ipData[wordNum] ^ fInvert;
+
+ const TUint32 shift = 31-(BitInWord(startPos));
+ val = (val << shift) >> shift; //-- mask unused high bits
+
+ if(val)
+ {//-- there are '1' bits in the current word
+ goto found;
+ }
+ else
+ {//-- search in the lower words
+ while(wordNum)
+ {
+ wordNum--;
+ val=ipData[wordNum] ^ fInvert;
+ if(val)
+ goto found;
+ }
+ }
+
+ return EFalse; //-- nothing found
+
+ found:
+ aStartPos = (wordNum << 5)+Log2(val);
+ return ETrue;
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ Internal method to look for a given bit value in the both directions.
+ see TBool RBitVector::Find(...)
+*/
+TBool RBitVector::FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const
+{
+ if(iNumBits < 2)
+ return EFalse;
+
+ if(aStartPos == 0)
+ return FindToRight(aStartPos, aBitVal);
+
+ if(aStartPos == iNumBits-1)
+ return FindToLeft(aStartPos, aBitVal);
+
+
+ const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
+
+ TUint32 wordNum = WordNum(aStartPos);
+ TUint32 l_Idx; //-- index of the word to the left
+ TUint32 r_Idx; //-- index of the word to the right
+
+ l_Idx = r_Idx = wordNum;
+
+ TBool noWayLeft = (wordNum == 0); //-- if we are in the first word
+ TBool noWayRight = (wordNum == iNumWords-1); //-- if we are in the last word
+
+ //-- look in the current word first
+ TUint32 val = ipData[wordNum] ^ fInvert;
+
+ if(noWayRight)
+ { //-- this is the last word in the array, mask unused high bits in the last word
+ val = MaskLastWord(val);
+ }
+
+ const TUint32 bitPos = aStartPos & 0x1F;
+ val &= ~(1<<bitPos); //-- mask the bit at current position
+
+ if(val == 0)
+ {//-- no '1' bits in the current word
+ noWayLeft = ItrLeft(l_Idx);
+ noWayRight = ItrRight(r_Idx);
+ }
+ else if(bitPos == 0)
+ {
+ noWayLeft = ItrLeft(l_Idx); //-- move to the previous word
+ }
+ else if(bitPos == 31)
+ {
+ noWayRight = ItrRight(r_Idx); //-- move to the next word
+ }
+ else
+ {//-- look in the current word, in both halves to the left and right from the start position
+
+ const TUint32 shift1 = 32-bitPos;
+ const TUint32 partLo = (val << shift1) >> shift1; //-- towards lower bits
+
+ const TUint32 shift2 = bitPos+1;
+ const TUint32 partHi = (val >> shift2) << shift2; //-- towards higher bits
+
+
+ if(partLo && !partHi) //-- only lower part has '1' bits
+ {
+ aStartPos = (wordNum << 5)+Log2(partLo);
+ return ETrue;
+ }
+ else if(!partLo && partHi) //-- only higher part has '1' bits
+ {
+ aStartPos = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );
+ return ETrue;
+ }
+ else if(partLo && partHi) //-- both parts contain '1' bits, select the nearest one
+ {
+ const TUint32 posL = (wordNum << 5)+Log2(partLo);
+ const TUint32 posR = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );
+
+ ASSERT(aStartPos > posL);
+ ASSERT(posR > aStartPos);
+ const TUint32 distL = aStartPos-posL;
+ const TUint32 distR = posR-aStartPos;
+
+ if(distL < distR)
+ {
+ aStartPos = posL;
+ return ETrue;
+ }
+ else if(distL > distR)
+ {
+ aStartPos = posR;
+ return ETrue;
+ }
+ else
+ {//-- distL == distR, take into account search priority
+ aStartPos = aToLeft ? posL : posR;
+ return ETrue;
+ }
+ }
+ else //-- (!partLo && !partHi), nothing in the current word
+ {
+ ASSERT(0);
+ }
+
+ }// if(bitPos > 0 && bitPos < 31)
+
+ //-- now we are processing separate words from both sides of the search position
+ for(;;)
+ {
+ TUint32 wL = ipData[l_Idx] ^ fInvert;
+ TUint32 wR = ipData[r_Idx] ^ fInvert;
+ if(r_Idx == iNumWords-1)
+ { //-- this is the last word in the array, mask unused high bits in the last word
+ wR = MaskLastWord(wR);
+ }
+
+ if(wL && !wR)
+ {
+ aStartPos = (l_Idx << 5)+Log2(wL);
+ return ETrue;
+ }
+ else if(!wL && wR)
+ {
+ aStartPos = (r_Idx << 5)+Log2( (wR & (~wR+1)) );
+ return ETrue;
+ }
+ else if(wL && wR)
+ {
+ const TUint32 posL = (l_Idx << 5)+Log2(wL);
+ const TUint32 posR = (r_Idx << 5)+Log2( (wR & (~wR+1)) );
+
+ ASSERT(aStartPos > posL);
+ ASSERT(posR > aStartPos);
+ const TUint32 distL = aStartPos-posL;
+ const TUint32 distR = posR-aStartPos;
+
+ if(distL < distR)
+ {
+ aStartPos = posL;
+ return ETrue;
+ }
+ else if(distL > distR)
+ {
+ aStartPos = posR;
+ return ETrue;
+ }
+ else
+ {//-- distL == distR, take into account search priority
+ aStartPos = aToLeft ? posL : posR;
+ return ETrue;
+ }
+
+ }//else if(wL && wR)
+
+
+ if(noWayLeft)
+ {
+ aStartPos = r_Idx << 5;
+ return FindToRight(aStartPos, aBitVal);
+ }
+ else
+ {
+ noWayLeft = ItrLeft(l_Idx);
+ }
+
+ if(noWayRight)
+ {
+ aStartPos = l_Idx << 5;
+ return FindToLeft(aStartPos, aBitVal);
+ }
+ else
+ {
+ noWayRight = ItrRight(r_Idx);
+ }
+
+ }//for(;;)
+
+ //return EFalse;
+}
+
+//-----------------------------------------------------------------------------
+/**
+ Find out if two vectors are different.
+
+ @param aRhs vector to compare with
+ @param aDiffIndex if there is a differene, here will be the number of the first different bit
+ @return ETrue if vectors differ, EFalse, if they are identical.
+*/
+TBool RBitVector::Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const
+{
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
+ ASSERT(iNumWords > 0);
+
+ TUint32 diffWord=0;
+ TUint32 wordNum=0;
+
+ //-- compare all but the last word in the array
+ for(wordNum=0; wordNum < iNumWords-1; ++wordNum)
+ {
+ diffWord = ipData[wordNum] ^ aRhs.ipData[wordNum];
+ if(diffWord)
+ break; //-- found difference
+ }
+
+ //-- process the last word in the array
+ if(!diffWord)
+ {
+ diffWord = MaskLastWord(ipData[wordNum]) ^ MaskLastWord(aRhs.ipData[wordNum]);
+ }
+
+ if(!diffWord)
+ return EFalse; //-- vectors are the same
+
+ //-- calculate the position of the bit that different.
+ diffWord &= (~diffWord+1); //-- select rightmost bit
+ aDiffIndex = (wordNum << 5)+Log2(diffWord);
+
+ return ETrue;
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ Iterate to the left (towards lower index) in the array of words ipData
+
+ @param aIdx index within ipData array to be decremented; if it's possible to move left, it will be decreased
+ @return ETrue if there is no way left i.e. aIdx is 0. EFalse otherwise and aIdx decreased.
+*/
+TBool RBitVector::ItrLeft(TUint32& aIdx) const
+{
+ if(aIdx == 0)
+ return ETrue;
+ else
+ {
+ aIdx--;
+ return EFalse;
+ }
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ Iterate to the right (towards higher index) in the array of words ipData
+
+ @param aIdx index within ipData array to be incremented; if it's possible to move right, it will be increased
+ @return ETrue if there is no way right i.e. aIdx corresponds to the last word. EFalse otherwise and aIdx increased.
+*/
+TBool RBitVector::ItrRight(TUint32& aIdx) const
+{
+ if(aIdx < iNumWords-1)
+ {
+ aIdx++;
+ return EFalse;
+ }
+ else
+ return ETrue;
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ Import data to the internal bit vector representation.
+ Just replaces number of bytes from apData to the ipData.
+
+ @param aStartBit starting bit number. Must have 8-bit alignment.
+ @param aNumBits number of bits to import; granularity: 1 bit, i.e. it can be 177, for example.
+ @param apData pointer to the data (bitstream) to import.
+
+*/
+void RBitVector::DoImportData(TUint32 aStartBit, TUint32 aNumBits, const TAny* apData)
+{
+ ASSERT(aNumBits);
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+
+ //-- check parameters granularity. aStartBit must have 8-bit alignment
+ __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment));
+
+
+ __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= iNumBits), Panic(EIndexOutOfRange));
+
+ const TUint bitsTail = aNumBits & 0x07;
+ const TUint32 nBytes = aNumBits >> 3;
+
+ if(nBytes)
+ {//-- copy full array of bytes
+ const TUint32 startByte = aStartBit >> 3;
+ Mem::Copy(((TUint8*)ipData) + startByte, apData, nBytes);
+ }
+
+ if(bitsTail)
+ {//-- we need to copy trailing bits from the input data to the corresponding byte of the internal array
+ const TUint8 mask = (TUint8)(0xFF >> (8-bitsTail));
+ const TUint8 orMask = (TUint8)( *((const TUint8*)apData + nBytes) & mask);
+ const TUint8 andMask= (TUint8)~mask;
+
+ TUint8* pbData = (TUint8*)ipData + nBytes;
+ *pbData &= andMask;
+ *pbData |= orMask;
+ }
+
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ Export data from the internal bit vector buffer to the external one.
+
+ @param aStartBit starting bit number. Must have 8-bit alignment.
+ @param aNumBits number of bits to export, must comprise the whole byte, i.e. be multiple of 8.
+ The client is responsible for masking extra bits it doesn't need.
+ Another implication: e.g. if the bitvector consists of 3 bits, this value must be 8.
+ The value of bits 3-7 in the aData[0] will be undefined.
+
+ @param aData destination data descriptor
+*/
+void RBitVector::DoExportData(TUint32 aStartBit, TUint32 aNumBits, TDes8& aData) const
+{
+ ASSERT(aNumBits);
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+
+ //-- check parameters granularity.
+ __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment)); //-- aStartBit must have 8-bit alignment
+ __ASSERT_ALWAYS(!(aNumBits & 0x07), Panic(EDataAlignment)); //-- number of bits shall comprise a byte
+
+ __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= (iNumWords << (KBitsInByteLog2+sizeof(TUint32))) ), Panic(EIndexOutOfRange));
+
+ const TUint32 nBytes = aNumBits >> 3;
+ const TUint32 startByte = aStartBit >> 3;
+
+ aData.SetLength(nBytes);
+ aData.Copy(((const TUint8*)ipData) + startByte, nBytes);
+}
+
+//-----------------------------------------------------------------------------
+
+/**
+ @return number of bits set to '1' in the vector
+*/
+TUint32 RBitVector::Num1Bits() const
+{
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ if(!iNumBits)
+ return 0;
+
+ TUint32 cntBits = 0;
+
+ TUint32 wordNum;
+ for(wordNum=0; wordNum < iNumWords-1; ++wordNum)
+ {
+ cntBits += Count1Bits(ipData[wordNum]);
+ }
+
+ //-- process the last word, it shall be masked
+ cntBits += Count1Bits(MaskLastWord(ipData[wordNum]));
+
+ return cntBits;
+}
+
+//-----------------------------------------------------------------------------
+/**
+ @return number of bits set to '0' in the vector
+*/
+TUint32 RBitVector::Num0Bits() const
+{
+ return iNumBits - Num1Bits();
+}
+
+
+//-----------------------------------------------------------------------------
+/**
+ Calculate number of '1' bits in the range from aIndexFrom to aIndexTo inclusively
+
+ @param aIndexFrom starting index; bit[aIndexFrom] is included to the search
+ @param aIndexTo ending index; bit[aIndexTo] is included to the search
+ @return number of bits set to '1' in the slice
+*/
+TUint32 RBitVector::Num1Bits(TUint32 aIndexFrom, TUint32 aIndexTo) const
+{
+ __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
+ __ASSERT_ALWAYS(aIndexTo < iNumBits && aIndexFrom <= aIndexTo, Panic(EIndexOutOfRange));
+
+ const TUint32 wordFrom = WordNum(aIndexFrom); //?const
+ const TUint32 wordTo = WordNum(aIndexTo);
+
+ if(wordFrom == wordTo)
+ {//-- the same word
+ TUint32 word = ipData[wordFrom];
+
+ const TUint32 shMaskR = BitInWord(aIndexFrom);
+ word >>= shMaskR; word <<= shMaskR; //-- zero low bits
+
+ const TUint32 shMaskL = 31-BitInWord(aIndexTo);
+ word <<= shMaskL; //-- zero high bits
+
+ return Count1Bits(word);
+ }
+
+ TUint32 bitsCnt = 0;
+ TUint32 wordsBetween = wordTo - wordFrom - 1;
+
+ //-- count '1' bits in the termial words
+ TUint32 word = ipData[wordFrom];
+ const TUint32 shMaskR = BitInWord(aIndexFrom);
+ word >>= shMaskR; //-- zero low bits
+ bitsCnt += Count1Bits(word);
+
+ word = ipData[wordTo];
+ const TUint32 shMaskL = 31-BitInWord(aIndexTo);
+ word <<= shMaskL; //-- zero high bits
+ bitsCnt += Count1Bits(word);
+
+ //-- count '1' bits in the words between terminal ones
+ TUint32 wordIdx = wordFrom+1;
+ while(wordsBetween--)
+ {
+ bitsCnt += Count1Bits(ipData[wordIdx]);
+ }
+
+
+ return bitsCnt;
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+