1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/userlibandfileserver/fileserver/fs_utils/bit_vector.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,883 @@
1.4 +// Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +//
1.18 +// Collection of common constants, utility functions, etc. for the file server and file systems.
1.19 +// Definitions here must be filesystem-agnostic, i.e. generic enougs to be used by every file system
1.20 +//
1.21 +// This is the internal file and must not be exported.
1.22 +
1.23 +/**
1.24 + @file
1.25 + @internalTechnology
1.26 +*/
1.27 +
1.28 +#include "bit_vector.h"
1.29 +
1.30 +
1.31 +//#######################################################################################################################################
1.32 +//# RBitVector class implementation
1.33 +//#######################################################################################################################################
1.34 +
1.35 +const TUint32 K_FFFF = 0xFFFFFFFF; //-- all one bits, beware rigth shifts of signed integers!
1.36 +
1.37 +RBitVector::RBitVector()
1.38 + :iNumBits(0), ipData(NULL), iNumWords(0)
1.39 + {
1.40 + }
1.41 +
1.42 +
1.43 +RBitVector::~RBitVector()
1.44 + {
1.45 + Close();
1.46 + }
1.47 +
1.48 +/**
1.49 + Panics.
1.50 + @param aPanicCode a panic code
1.51 +*/
1.52 +void RBitVector::Panic(TPanicCode aPanicCode) const
1.53 + {
1.54 + _LIT(KPanicCat,"RBitVector");
1.55 + User::Panic(KPanicCat, aPanicCode);
1.56 + }
1.57 +
1.58 +/** explicitly closes the object and deallocates memory */
1.59 +void RBitVector::Close()
1.60 + {
1.61 + iNumBits = 0;
1.62 + iNumWords =0;
1.63 + User::Free(ipData);
1.64 + ipData = NULL;
1.65 + }
1.66 +
1.67 +//-----------------------------------------------------------------------------
1.68 +
1.69 +/**
1.70 + Comparison perator.
1.71 + @param aRhs a vector to compate with.
1.72 + @panic ESizeMismatch in the case of different vector sizes
1.73 +*/
1.74 +TBool RBitVector::operator==(const RBitVector& aRhs) const
1.75 + {
1.76 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.77 + __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
1.78 +
1.79 +
1.80 + if(!iNumBits)
1.81 + return ETrue; //-- comparing 0-lenght arrays
1.82 +
1.83 + if(this == &aRhs)
1.84 + {//-- comparing with itself, potential source of errors
1.85 + ASSERT(0);
1.86 + return ETrue;
1.87 + }
1.88 +
1.89 + if(iNumWords >= 1)
1.90 + {
1.91 + const TUint32 cntBytes = (iNumBits >> 5) << 2; //-- bytes to compare
1.92 + if(memcompare((const TUint8*)ipData, cntBytes, (const TUint8*)aRhs.ipData, cntBytes))
1.93 + return EFalse;
1.94 + }
1.95 +
1.96 + const TUint32 bitsRest = iNumBits & 0x1F;
1.97 + if(bitsRest)
1.98 + {
1.99 + const TUint32 mask = K_FFFF >> (32-bitsRest);
1.100 + return ( (ipData[iNumWords-1] & mask) == (aRhs.ipData[iNumWords-1] & mask) );
1.101 + }
1.102 +
1.103 + return ETrue;
1.104 + }
1.105 +
1.106 +TBool RBitVector::operator!=(const RBitVector& aRhs) const
1.107 + {
1.108 + return ! ((*this) == aRhs);
1.109 + }
1.110 +
1.111 +//-----------------------------------------------------------------------------
1.112 +
1.113 +/** The same as Create(), but leaves on error */
1.114 +void RBitVector::CreateL(TUint32 aNumBits)
1.115 + {
1.116 + User::LeaveIfError(Create(aNumBits));
1.117 + }
1.118 +
1.119 +
1.120 +/**
1.121 + Create the vector with the size of aNumBits bits.
1.122 + @return system-wide error codes:
1.123 + KErrNoMemory unable to allocate sufficient amount of memory for the array
1.124 + KErrInUse an attempt to call Create() for non-empty vector. Close it first.
1.125 + KErrArgument invalid aNumBits value == 0
1.126 +*/
1.127 +TInt RBitVector::Create(TUint32 aNumBits)
1.128 + {
1.129 +
1.130 + if(ipData)
1.131 + return KErrInUse; //-- array is already in use. Close it first.
1.132 +
1.133 + if(!aNumBits)
1.134 + return KErrArgument;
1.135 +
1.136 + //-- memory is allocated by word (32 bit) quiantities
1.137 + const TUint32 numWords = (aNumBits >> 5) + ((aNumBits & 0x1F) > 0 ? 1:0);
1.138 + ipData = (TUint32*)User::AllocZ(numWords << 2);
1.139 +
1.140 + if(!ipData)
1.141 + return KErrNoMemory;
1.142 +
1.143 + iNumBits = aNumBits;
1.144 + iNumWords = numWords;
1.145 +
1.146 + return KErrNone;
1.147 + }
1.148 +
1.149 +
1.150 +/**
1.151 + Fill a bit vector with a given bit value
1.152 + @param aVal a bit value
1.153 +*/
1.154 +void RBitVector::Fill(TBool aVal)
1.155 + {
1.156 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.157 + memset(ipData, (aVal ? 0xFF : 0x00), iNumWords << 2);
1.158 + }
1.159 +
1.160 +/** Invert all bits in a bit vector */
1.161 +void RBitVector::Invert()
1.162 +{
1.163 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.164 + for(TUint32 i=0; i<iNumWords; ++i)
1.165 + ipData[i] ^= K_FFFF;
1.166 +}
1.167 +
1.168 +
1.169 +/**
1.170 + Perform "And" operation between 2 vectors. They shall be the same size.
1.171 + @param aRhs a vector from the right hand side
1.172 + @panic ESizeMismatch in the case of different vector sizes
1.173 +*/
1.174 +void RBitVector::And(const RBitVector& aRhs)
1.175 + {
1.176 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.177 + __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
1.178 + for(TUint32 i=0; i<iNumWords; ++i)
1.179 + {
1.180 + ipData[i] &= aRhs.ipData[i];
1.181 + }
1.182 + }
1.183 +
1.184 +/**
1.185 + Perform "Or" operation between 2 vectors. They shall be the same size.
1.186 + @param aRhs a vector from the right hand side
1.187 + @panic ESizeMismatch in the case of different vector sizes
1.188 +*/
1.189 +void RBitVector::Or(const RBitVector& aRhs)
1.190 + {
1.191 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.192 + __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
1.193 + for(TUint32 i=0; i<iNumWords; ++i)
1.194 + {
1.195 + ipData[i] |= aRhs.ipData[i];
1.196 + }
1.197 + }
1.198 +
1.199 +/**
1.200 + Perform "Xor" operation between 2 vectors. They shall be the same size.
1.201 + @param aRhs a vector from the right hand side
1.202 + @panic ESizeMismatch in the case of different vector sizes
1.203 +*/
1.204 +void RBitVector::Xor(const RBitVector& aRhs)
1.205 + {
1.206 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.207 + __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
1.208 + for(TUint32 i=0; i<iNumWords; ++i)
1.209 + {
1.210 + ipData[i] ^= aRhs.ipData[i];
1.211 + }
1.212 + }
1.213 +
1.214 +//-----------------------------------------------------------------------------
1.215 +/**
1.216 + Fill a range from bit number "aIndexFrom" to "aIndexTo" inclusively with the value of aVal
1.217 +
1.218 + @param aIndexFrom start bit number (inclusive)
1.219 + @param aIndexTo end bit number (inclusive)
1.220 + @param aVal the value to be used to fill the range (0s or 1s)
1.221 +*/
1.222 +void RBitVector::Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal)
1.223 + {
1.224 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.225 +
1.226 + //-- swap indexes if they are not in order
1.227 + if(aIndexFrom > aIndexTo)
1.228 + {
1.229 + const TUint32 tmp = aIndexFrom;
1.230 + aIndexFrom = aIndexTo;
1.231 + aIndexTo = tmp;
1.232 + }
1.233 +
1.234 + __ASSERT_ALWAYS((aIndexFrom < iNumBits) && (aIndexTo < iNumBits), Panic(EIndexOutOfRange));
1.235 +
1.236 + const TUint32 wordStart = WordNum(aIndexFrom);
1.237 + const TUint32 wordTo = WordNum(aIndexTo);
1.238 +
1.239 + if(aVal)
1.240 + {//-- filling a range with '1'
1.241 +
1.242 + TUint32 shift = BitInWord(aIndexFrom);
1.243 + const TUint32 mask1 = (K_FFFF >> shift) << shift;
1.244 +
1.245 + TUint32 mask2 = K_FFFF;
1.246 + shift = 1+BitInWord(aIndexTo);
1.247 + if(shift < 32)
1.248 + {
1.249 + mask2 = ~((mask2 >> shift) << shift);
1.250 + }
1.251 +
1.252 + if(wordTo == wordStart)
1.253 + {//-- a special case, filling is in the same word
1.254 + ipData[wordStart] |= (mask1 & mask2);
1.255 + }
1.256 + else
1.257 + {
1.258 + ipData[wordStart] |= mask1;
1.259 + ipData[wordTo] |= mask2;
1.260 +
1.261 + const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled
1.262 +
1.263 + if(wholeWordsBetween)
1.264 + memset(ipData+wordStart+1, 0xFF, wholeWordsBetween << 2);
1.265 +
1.266 + }
1.267 + }
1.268 + else
1.269 + {//-- filling a range with '0'
1.270 +
1.271 + TUint32 shift = BitInWord(aIndexFrom);
1.272 + const TUint32 mask1 = ~((K_FFFF >> shift) << shift);
1.273 +
1.274 + TUint32 mask2 = 0;
1.275 + shift = 1+BitInWord(aIndexTo);
1.276 + if(shift < 32)
1.277 + {
1.278 + mask2 = ((K_FFFF >> shift) << shift);
1.279 + }
1.280 +
1.281 + if(wordTo == wordStart)
1.282 + {//-- a special case, filling is in the same word
1.283 + ipData[wordStart] &= (mask1 | mask2);
1.284 + }
1.285 + else
1.286 + {
1.287 + ipData[wordStart] &= mask1;
1.288 + ipData[wordTo] &= mask2;
1.289 +
1.290 + const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled
1.291 +
1.292 + if(wholeWordsBetween)
1.293 + memset(ipData+wordStart+1, 0x00, wholeWordsBetween << 2);
1.294 +
1.295 + }
1.296 + }
1.297 +
1.298 + }
1.299 +
1.300 +//-----------------------------------------------------------------------------
1.301 +
1.302 +/**
1.303 + Search for a specified bit value ('0' or '1') in the vector from the given position.
1.304 + @param aStartPos zero-based index; from this position the search will start. This position isn't included to the search.
1.305 + On return may contain a new position if the specified bit is found in specified direction.
1.306 + @param aBitVal zero or non-zero bit to search.
1.307 + @param aDir Specifies the search direction
1.308 +
1.309 + @return ETrue if the specified bit value is found; aStartPos gets updated.
1.310 + EFalse otherwise.
1.311 +
1.312 +*/
1.313 +TBool RBitVector::Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const
1.314 + {
1.315 + __ASSERT_ALWAYS(aStartPos < iNumBits, Panic(EIndexOutOfRange));
1.316 + ASSERT(iNumWords && ipData);
1.317 +
1.318 + switch(aDir)
1.319 + {
1.320 + case ERight: //-- Search from the given position to the right
1.321 + return FindToRight(aStartPos, aBitVal);
1.322 +
1.323 + case ELeft: //-- Search from the given position to the left (towards lower index)
1.324 + return FindToLeft(aStartPos, aBitVal);
1.325 +
1.326 + case ENearestL: //-- Search for the nearest value in both directions starting from left
1.327 + return FindNearest(aStartPos, aBitVal, ETrue);
1.328 +
1.329 + case ENearestR: //-- Search for the nearest value in both directions starting from right
1.330 + return FindNearest(aStartPos, aBitVal, EFalse);
1.331 +
1.332 + default:
1.333 + Panic(EWrondFindDirection);
1.334 + return EFalse;
1.335 +
1.336 + };
1.337 +
1.338 + }
1.339 +
1.340 +//-----------------------------------------------------------------------------
1.341 +/**
1.342 + Internal method to look for a given bit value in the right direction.
1.343 + see TBool RBitVector::Find(...)
1.344 +*/
1.345 +TBool RBitVector::FindToRight(TUint32& aStartPos, TBool aBitVal) const
1.346 + {
1.347 + if(aStartPos >= iNumBits-1)
1.348 + return EFalse; //-- no way to the right
1.349 +
1.350 + const TUint32 startPos = aStartPos+1;
1.351 + const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
1.352 +
1.353 + TUint32 wordNum = WordNum(startPos);
1.354 + TUint32 val = ipData[wordNum] ^ fInvert;
1.355 +
1.356 + if(wordNum == iNumWords-1)
1.357 + {//-- process the last word in the array, some higher bits might not belong to the bit vector
1.358 + val = MaskLastWord(val);
1.359 + }
1.360 +
1.361 + const TUint32 shift = BitInWord(startPos);
1.362 + val = (val >> shift) << shift; //-- mask unused low bits
1.363 +
1.364 + if(val)
1.365 + {//-- there are '1' bits in the current word
1.366 + goto found;
1.367 + }
1.368 + else
1.369 + {//-- search in higher words
1.370 + wordNum++;
1.371 +
1.372 + while(iNumWords-wordNum > 1)
1.373 + {
1.374 + val = ipData[wordNum] ^ fInvert;
1.375 + if(val)
1.376 + goto found;
1.377 +
1.378 + wordNum++;
1.379 + }
1.380 +
1.381 + if(wordNum == iNumWords-1)
1.382 + {//-- process the last word in the array, some higher bith might not belong to the bit vector
1.383 + val = ipData[wordNum] ^ fInvert;
1.384 + val = MaskLastWord(val);
1.385 +
1.386 + if(val)
1.387 + goto found;
1.388 + }
1.389 + }
1.390 +
1.391 + return EFalse; //-- haven't found anything
1.392 +
1.393 + found:
1.394 +
1.395 + val &= (~val+1); //-- select rightmost bit
1.396 + aStartPos = (wordNum << 5)+Log2(val);
1.397 + return ETrue;
1.398 + }
1.399 +
1.400 +
1.401 +//-----------------------------------------------------------------------------
1.402 +
1.403 +/**
1.404 + Internal method to look for a given bit value in the left direction.
1.405 + see TBool RBitVector::Find(...)
1.406 +*/
1.407 +TBool RBitVector::FindToLeft(TUint32& aStartPos, TBool aBitVal) const
1.408 +{
1.409 + if(!aStartPos)
1.410 + return EFalse; //-- no way to the left
1.411 +
1.412 + const TUint32 startPos=aStartPos-1;
1.413 + const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
1.414 +
1.415 + TUint32 wordNum = WordNum(startPos);
1.416 + TUint32 val = ipData[wordNum] ^ fInvert;
1.417 +
1.418 + const TUint32 shift = 31-(BitInWord(startPos));
1.419 + val = (val << shift) >> shift; //-- mask unused high bits
1.420 +
1.421 + if(val)
1.422 + {//-- there are '1' bits in the current word
1.423 + goto found;
1.424 + }
1.425 + else
1.426 + {//-- search in the lower words
1.427 + while(wordNum)
1.428 + {
1.429 + wordNum--;
1.430 + val=ipData[wordNum] ^ fInvert;
1.431 + if(val)
1.432 + goto found;
1.433 + }
1.434 + }
1.435 +
1.436 + return EFalse; //-- nothing found
1.437 +
1.438 + found:
1.439 + aStartPos = (wordNum << 5)+Log2(val);
1.440 + return ETrue;
1.441 +}
1.442 +
1.443 +//-----------------------------------------------------------------------------
1.444 +
1.445 +/**
1.446 + Internal method to look for a given bit value in the both directions.
1.447 + see TBool RBitVector::Find(...)
1.448 +*/
1.449 +TBool RBitVector::FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const
1.450 +{
1.451 + if(iNumBits < 2)
1.452 + return EFalse;
1.453 +
1.454 + if(aStartPos == 0)
1.455 + return FindToRight(aStartPos, aBitVal);
1.456 +
1.457 + if(aStartPos == iNumBits-1)
1.458 + return FindToLeft(aStartPos, aBitVal);
1.459 +
1.460 +
1.461 + const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit
1.462 +
1.463 + TUint32 wordNum = WordNum(aStartPos);
1.464 + TUint32 l_Idx; //-- index of the word to the left
1.465 + TUint32 r_Idx; //-- index of the word to the right
1.466 +
1.467 + l_Idx = r_Idx = wordNum;
1.468 +
1.469 + TBool noWayLeft = (wordNum == 0); //-- if we are in the first word
1.470 + TBool noWayRight = (wordNum == iNumWords-1); //-- if we are in the last word
1.471 +
1.472 + //-- look in the current word first
1.473 + TUint32 val = ipData[wordNum] ^ fInvert;
1.474 +
1.475 + if(noWayRight)
1.476 + { //-- this is the last word in the array, mask unused high bits in the last word
1.477 + val = MaskLastWord(val);
1.478 + }
1.479 +
1.480 + const TUint32 bitPos = aStartPos & 0x1F;
1.481 + val &= ~(1<<bitPos); //-- mask the bit at current position
1.482 +
1.483 + if(val == 0)
1.484 + {//-- no '1' bits in the current word
1.485 + noWayLeft = ItrLeft(l_Idx);
1.486 + noWayRight = ItrRight(r_Idx);
1.487 + }
1.488 + else if(bitPos == 0)
1.489 + {
1.490 + noWayLeft = ItrLeft(l_Idx); //-- move to the previous word
1.491 + }
1.492 + else if(bitPos == 31)
1.493 + {
1.494 + noWayRight = ItrRight(r_Idx); //-- move to the next word
1.495 + }
1.496 + else
1.497 + {//-- look in the current word, in both halves to the left and right from the start position
1.498 +
1.499 + const TUint32 shift1 = 32-bitPos;
1.500 + const TUint32 partLo = (val << shift1) >> shift1; //-- towards lower bits
1.501 +
1.502 + const TUint32 shift2 = bitPos+1;
1.503 + const TUint32 partHi = (val >> shift2) << shift2; //-- towards higher bits
1.504 +
1.505 +
1.506 + if(partLo && !partHi) //-- only lower part has '1' bits
1.507 + {
1.508 + aStartPos = (wordNum << 5)+Log2(partLo);
1.509 + return ETrue;
1.510 + }
1.511 + else if(!partLo && partHi) //-- only higher part has '1' bits
1.512 + {
1.513 + aStartPos = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );
1.514 + return ETrue;
1.515 + }
1.516 + else if(partLo && partHi) //-- both parts contain '1' bits, select the nearest one
1.517 + {
1.518 + const TUint32 posL = (wordNum << 5)+Log2(partLo);
1.519 + const TUint32 posR = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );
1.520 +
1.521 + ASSERT(aStartPos > posL);
1.522 + ASSERT(posR > aStartPos);
1.523 + const TUint32 distL = aStartPos-posL;
1.524 + const TUint32 distR = posR-aStartPos;
1.525 +
1.526 + if(distL < distR)
1.527 + {
1.528 + aStartPos = posL;
1.529 + return ETrue;
1.530 + }
1.531 + else if(distL > distR)
1.532 + {
1.533 + aStartPos = posR;
1.534 + return ETrue;
1.535 + }
1.536 + else
1.537 + {//-- distL == distR, take into account search priority
1.538 + aStartPos = aToLeft ? posL : posR;
1.539 + return ETrue;
1.540 + }
1.541 + }
1.542 + else //-- (!partLo && !partHi), nothing in the current word
1.543 + {
1.544 + ASSERT(0);
1.545 + }
1.546 +
1.547 + }// if(bitPos > 0 && bitPos < 31)
1.548 +
1.549 + //-- now we are processing separate words from both sides of the search position
1.550 + for(;;)
1.551 + {
1.552 + TUint32 wL = ipData[l_Idx] ^ fInvert;
1.553 + TUint32 wR = ipData[r_Idx] ^ fInvert;
1.554 + if(r_Idx == iNumWords-1)
1.555 + { //-- this is the last word in the array, mask unused high bits in the last word
1.556 + wR = MaskLastWord(wR);
1.557 + }
1.558 +
1.559 + if(wL && !wR)
1.560 + {
1.561 + aStartPos = (l_Idx << 5)+Log2(wL);
1.562 + return ETrue;
1.563 + }
1.564 + else if(!wL && wR)
1.565 + {
1.566 + aStartPos = (r_Idx << 5)+Log2( (wR & (~wR+1)) );
1.567 + return ETrue;
1.568 + }
1.569 + else if(wL && wR)
1.570 + {
1.571 + const TUint32 posL = (l_Idx << 5)+Log2(wL);
1.572 + const TUint32 posR = (r_Idx << 5)+Log2( (wR & (~wR+1)) );
1.573 +
1.574 + ASSERT(aStartPos > posL);
1.575 + ASSERT(posR > aStartPos);
1.576 + const TUint32 distL = aStartPos-posL;
1.577 + const TUint32 distR = posR-aStartPos;
1.578 +
1.579 + if(distL < distR)
1.580 + {
1.581 + aStartPos = posL;
1.582 + return ETrue;
1.583 + }
1.584 + else if(distL > distR)
1.585 + {
1.586 + aStartPos = posR;
1.587 + return ETrue;
1.588 + }
1.589 + else
1.590 + {//-- distL == distR, take into account search priority
1.591 + aStartPos = aToLeft ? posL : posR;
1.592 + return ETrue;
1.593 + }
1.594 +
1.595 + }//else if(wL && wR)
1.596 +
1.597 +
1.598 + if(noWayLeft)
1.599 + {
1.600 + aStartPos = r_Idx << 5;
1.601 + return FindToRight(aStartPos, aBitVal);
1.602 + }
1.603 + else
1.604 + {
1.605 + noWayLeft = ItrLeft(l_Idx);
1.606 + }
1.607 +
1.608 + if(noWayRight)
1.609 + {
1.610 + aStartPos = l_Idx << 5;
1.611 + return FindToLeft(aStartPos, aBitVal);
1.612 + }
1.613 + else
1.614 + {
1.615 + noWayRight = ItrRight(r_Idx);
1.616 + }
1.617 +
1.618 + }//for(;;)
1.619 +
1.620 + //return EFalse;
1.621 +}
1.622 +
1.623 +//-----------------------------------------------------------------------------
1.624 +/**
1.625 + Find out if two vectors are different.
1.626 +
1.627 + @param aRhs vector to compare with
1.628 + @param aDiffIndex if there is a differene, here will be the number of the first different bit
1.629 + @return ETrue if vectors differ, EFalse, if they are identical.
1.630 +*/
1.631 +TBool RBitVector::Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const
1.632 +{
1.633 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.634 + __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));
1.635 + ASSERT(iNumWords > 0);
1.636 +
1.637 + TUint32 diffWord=0;
1.638 + TUint32 wordNum=0;
1.639 +
1.640 + //-- compare all but the last word in the array
1.641 + for(wordNum=0; wordNum < iNumWords-1; ++wordNum)
1.642 + {
1.643 + diffWord = ipData[wordNum] ^ aRhs.ipData[wordNum];
1.644 + if(diffWord)
1.645 + break; //-- found difference
1.646 + }
1.647 +
1.648 + //-- process the last word in the array
1.649 + if(!diffWord)
1.650 + {
1.651 + diffWord = MaskLastWord(ipData[wordNum]) ^ MaskLastWord(aRhs.ipData[wordNum]);
1.652 + }
1.653 +
1.654 + if(!diffWord)
1.655 + return EFalse; //-- vectors are the same
1.656 +
1.657 + //-- calculate the position of the bit that different.
1.658 + diffWord &= (~diffWord+1); //-- select rightmost bit
1.659 + aDiffIndex = (wordNum << 5)+Log2(diffWord);
1.660 +
1.661 + return ETrue;
1.662 +}
1.663 +
1.664 +//-----------------------------------------------------------------------------
1.665 +
1.666 +/**
1.667 + Iterate to the left (towards lower index) in the array of words ipData
1.668 +
1.669 + @param aIdx index within ipData array to be decremented; if it's possible to move left, it will be decreased
1.670 + @return ETrue if there is no way left i.e. aIdx is 0. EFalse otherwise and aIdx decreased.
1.671 +*/
1.672 +TBool RBitVector::ItrLeft(TUint32& aIdx) const
1.673 +{
1.674 + if(aIdx == 0)
1.675 + return ETrue;
1.676 + else
1.677 + {
1.678 + aIdx--;
1.679 + return EFalse;
1.680 + }
1.681 +}
1.682 +
1.683 +//-----------------------------------------------------------------------------
1.684 +
1.685 +/**
1.686 + Iterate to the right (towards higher index) in the array of words ipData
1.687 +
1.688 + @param aIdx index within ipData array to be incremented; if it's possible to move right, it will be increased
1.689 + @return ETrue if there is no way right i.e. aIdx corresponds to the last word. EFalse otherwise and aIdx increased.
1.690 +*/
1.691 +TBool RBitVector::ItrRight(TUint32& aIdx) const
1.692 +{
1.693 + if(aIdx < iNumWords-1)
1.694 + {
1.695 + aIdx++;
1.696 + return EFalse;
1.697 + }
1.698 + else
1.699 + return ETrue;
1.700 +}
1.701 +
1.702 +//-----------------------------------------------------------------------------
1.703 +
1.704 +/**
1.705 + Import data to the internal bit vector representation.
1.706 + Just replaces number of bytes from apData to the ipData.
1.707 +
1.708 + @param aStartBit starting bit number. Must have 8-bit alignment.
1.709 + @param aNumBits number of bits to import; granularity: 1 bit, i.e. it can be 177, for example.
1.710 + @param apData pointer to the data (bitstream) to import.
1.711 +
1.712 +*/
1.713 +void RBitVector::DoImportData(TUint32 aStartBit, TUint32 aNumBits, const TAny* apData)
1.714 +{
1.715 + ASSERT(aNumBits);
1.716 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.717 +
1.718 + //-- check parameters granularity. aStartBit must have 8-bit alignment
1.719 + __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment));
1.720 +
1.721 +
1.722 + __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= iNumBits), Panic(EIndexOutOfRange));
1.723 +
1.724 + const TUint bitsTail = aNumBits & 0x07;
1.725 + const TUint32 nBytes = aNumBits >> 3;
1.726 +
1.727 + if(nBytes)
1.728 + {//-- copy full array of bytes
1.729 + const TUint32 startByte = aStartBit >> 3;
1.730 + Mem::Copy(((TUint8*)ipData) + startByte, apData, nBytes);
1.731 + }
1.732 +
1.733 + if(bitsTail)
1.734 + {//-- we need to copy trailing bits from the input data to the corresponding byte of the internal array
1.735 + const TUint8 mask = (TUint8)(0xFF >> (8-bitsTail));
1.736 + const TUint8 orMask = (TUint8)( *((const TUint8*)apData + nBytes) & mask);
1.737 + const TUint8 andMask= (TUint8)~mask;
1.738 +
1.739 + TUint8* pbData = (TUint8*)ipData + nBytes;
1.740 + *pbData &= andMask;
1.741 + *pbData |= orMask;
1.742 + }
1.743 +
1.744 +}
1.745 +
1.746 +//-----------------------------------------------------------------------------
1.747 +
1.748 +/**
1.749 + Export data from the internal bit vector buffer to the external one.
1.750 +
1.751 + @param aStartBit starting bit number. Must have 8-bit alignment.
1.752 + @param aNumBits number of bits to export, must comprise the whole byte, i.e. be multiple of 8.
1.753 + The client is responsible for masking extra bits it doesn't need.
1.754 + Another implication: e.g. if the bitvector consists of 3 bits, this value must be 8.
1.755 + The value of bits 3-7 in the aData[0] will be undefined.
1.756 +
1.757 + @param aData destination data descriptor
1.758 +*/
1.759 +void RBitVector::DoExportData(TUint32 aStartBit, TUint32 aNumBits, TDes8& aData) const
1.760 +{
1.761 + ASSERT(aNumBits);
1.762 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.763 +
1.764 + //-- check parameters granularity.
1.765 + __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment)); //-- aStartBit must have 8-bit alignment
1.766 + __ASSERT_ALWAYS(!(aNumBits & 0x07), Panic(EDataAlignment)); //-- number of bits shall comprise a byte
1.767 +
1.768 + __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= (iNumWords << (KBitsInByteLog2+sizeof(TUint32))) ), Panic(EIndexOutOfRange));
1.769 +
1.770 + const TUint32 nBytes = aNumBits >> 3;
1.771 + const TUint32 startByte = aStartBit >> 3;
1.772 +
1.773 + aData.SetLength(nBytes);
1.774 + aData.Copy(((const TUint8*)ipData) + startByte, nBytes);
1.775 +}
1.776 +
1.777 +//-----------------------------------------------------------------------------
1.778 +
1.779 +/**
1.780 + @return number of bits set to '1' in the vector
1.781 +*/
1.782 +TUint32 RBitVector::Num1Bits() const
1.783 +{
1.784 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.785 + if(!iNumBits)
1.786 + return 0;
1.787 +
1.788 + TUint32 cntBits = 0;
1.789 +
1.790 + TUint32 wordNum;
1.791 + for(wordNum=0; wordNum < iNumWords-1; ++wordNum)
1.792 + {
1.793 + cntBits += Count1Bits(ipData[wordNum]);
1.794 + }
1.795 +
1.796 + //-- process the last word, it shall be masked
1.797 + cntBits += Count1Bits(MaskLastWord(ipData[wordNum]));
1.798 +
1.799 + return cntBits;
1.800 +}
1.801 +
1.802 +//-----------------------------------------------------------------------------
1.803 +/**
1.804 + @return number of bits set to '0' in the vector
1.805 +*/
1.806 +TUint32 RBitVector::Num0Bits() const
1.807 +{
1.808 + return iNumBits - Num1Bits();
1.809 +}
1.810 +
1.811 +
1.812 +//-----------------------------------------------------------------------------
1.813 +/**
1.814 + Calculate number of '1' bits in the range from aIndexFrom to aIndexTo inclusively
1.815 +
1.816 + @param aIndexFrom starting index; bit[aIndexFrom] is included to the search
1.817 + @param aIndexTo ending index; bit[aIndexTo] is included to the search
1.818 + @return number of bits set to '1' in the slice
1.819 +*/
1.820 +TUint32 RBitVector::Num1Bits(TUint32 aIndexFrom, TUint32 aIndexTo) const
1.821 +{
1.822 + __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));
1.823 + __ASSERT_ALWAYS(aIndexTo < iNumBits && aIndexFrom <= aIndexTo, Panic(EIndexOutOfRange));
1.824 +
1.825 + const TUint32 wordFrom = WordNum(aIndexFrom); //?const
1.826 + const TUint32 wordTo = WordNum(aIndexTo);
1.827 +
1.828 + if(wordFrom == wordTo)
1.829 + {//-- the same word
1.830 + TUint32 word = ipData[wordFrom];
1.831 +
1.832 + const TUint32 shMaskR = BitInWord(aIndexFrom);
1.833 + word >>= shMaskR; word <<= shMaskR; //-- zero low bits
1.834 +
1.835 + const TUint32 shMaskL = 31-BitInWord(aIndexTo);
1.836 + word <<= shMaskL; //-- zero high bits
1.837 +
1.838 + return Count1Bits(word);
1.839 + }
1.840 +
1.841 + TUint32 bitsCnt = 0;
1.842 + TUint32 wordsBetween = wordTo - wordFrom - 1;
1.843 +
1.844 + //-- count '1' bits in the termial words
1.845 + TUint32 word = ipData[wordFrom];
1.846 + const TUint32 shMaskR = BitInWord(aIndexFrom);
1.847 + word >>= shMaskR; //-- zero low bits
1.848 + bitsCnt += Count1Bits(word);
1.849 +
1.850 + word = ipData[wordTo];
1.851 + const TUint32 shMaskL = 31-BitInWord(aIndexTo);
1.852 + word <<= shMaskL; //-- zero high bits
1.853 + bitsCnt += Count1Bits(word);
1.854 +
1.855 + //-- count '1' bits in the words between terminal ones
1.856 + TUint32 wordIdx = wordFrom+1;
1.857 + while(wordsBetween--)
1.858 + {
1.859 + bitsCnt += Count1Bits(ipData[wordIdx]);
1.860 + }
1.861 +
1.862 +
1.863 + return bitsCnt;
1.864 +}
1.865 +
1.866 +
1.867 +
1.868 +
1.869 +
1.870 +
1.871 +
1.872 +
1.873 +
1.874 +
1.875 +
1.876 +
1.877 +
1.878 +
1.879 +
1.880 +
1.881 +
1.882 +
1.883 +
1.884 +
1.885 +
1.886 +