diff -r 000000000000 -r bde4ae8d615e os/kernelhwsrv/userlibandfileserver/fileserver/fs_utils/bit_vector.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/os/kernelhwsrv/userlibandfileserver/fileserver/fs_utils/bit_vector.cpp Fri Jun 15 03:10:57 2012 +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 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<> 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; +} + + + + + + + + + + + + + + + + + + + + + +