1 // Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 //

    15 //  Collection of common constants, utility functions, etc. for the file server and file systems.

    16 //  Definitions here must be filesystem-agnostic, i.e. generic enougs to be used by every file system

    17 //

    18 //  This is the internal file and must not be exported.

    19 

    20 /**

    21     @file

    22     @internalTechnology

    23 */

    24 

    25 #include "bit_vector.h"

    26 

    27 

    28 //#######################################################################################################################################

    29 //#   RBitVector class implementation

    30 //#######################################################################################################################################

    31 

    32 const TUint32 K_FFFF = 0xFFFFFFFF; //-- all one bits, beware rigth shifts of signed integers!

    33 

    34 RBitVector::RBitVector()

    35           :iNumBits(0), ipData(NULL), iNumWords(0)

    36     {

    37     }

    38 

    39 

    40 RBitVector::~RBitVector()

    41     {

    42     Close();

    43     }

    44 

    45 /**

    46     Panics.

    47     @param aPanicCode   a panic code

    48 */

    49 void RBitVector::Panic(TPanicCode aPanicCode) const

    50     {

    51     _LIT(KPanicCat,"RBitVector");

    52     User::Panic(KPanicCat, aPanicCode);

    53     }

    54 

    55 /** explicitly closes the object and deallocates memory */

    56 void RBitVector::Close()

    57     {

    58     iNumBits = 0;

    59     iNumWords =0;

    60     User::Free(ipData);

    61     ipData = NULL;

    62     }

    63 

    64 //-----------------------------------------------------------------------------

    65 

    66 /**

    67     Comparison perator.

    68     @param  aRhs a vector to compate with.

    69     @panic ESizeMismatch in the case of different vector sizes

    70 */

    71 TBool RBitVector::operator==(const RBitVector& aRhs) const

    72     {

    73     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

    74     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

    75 

    76 

    77     if(!iNumBits)

    78         return ETrue; //-- comparing 0-lenght arrays

    79 

    80     if(this == &aRhs)

    81         {//-- comparing with itself, potential source of errors

    82         ASSERT(0);

    83         return ETrue; 

    84         }

    85     

    86     if(iNumWords >= 1)

    87         {

    88         const TUint32 cntBytes = (iNumBits >> 5) << 2; //-- bytes to compare

    89         if(memcompare((const TUint8*)ipData, cntBytes, (const TUint8*)aRhs.ipData, cntBytes))

    90             return EFalse;

    91         }

    92 

    93     const TUint32 bitsRest  = iNumBits & 0x1F;

    94     if(bitsRest)

    95         {

    96         const TUint32 mask = K_FFFF >> (32-bitsRest);

    97         return ( (ipData[iNumWords-1] & mask) == (aRhs.ipData[iNumWords-1] & mask) );

    98         }

    99     

   100     return ETrue;

   101     }

   102 

   103 TBool RBitVector::operator!=(const RBitVector& aRhs) const  

   104     {

   105     return ! ((*this) == aRhs);

   106     } 

   107 

   108 //-----------------------------------------------------------------------------

   109 

   110 /** The same as Create(), but leaves on error */

   111 void RBitVector::CreateL(TUint32 aNumBits)

   112     {

   113     User::LeaveIfError(Create(aNumBits));

   114     }

   115 

   116 

   117 /**

   118     Create the vector with the size of aNumBits bits.

   119     @return system-wide error codes:

   120         KErrNoMemory    unable to allocate sufficient amount of memory for the array

   121         KErrInUse       an attempt to call Create() for non-empty vector. Close it first.

   122         KErrArgument    invalid aNumBits value == 0

   123 */

   124 TInt RBitVector::Create(TUint32 aNumBits)

   125     {

   126 

   127     if(ipData)

   128         return KErrInUse; //-- array is already in use. Close it first.

   129 

   130     if(!aNumBits)

   131         return KErrArgument;

   132 

   133     //-- memory is allocated by word (32 bit) quiantities

   134     const TUint32 numWords = (aNumBits >> 5) + ((aNumBits & 0x1F) > 0 ? 1:0);

   135     ipData = (TUint32*)User::AllocZ(numWords << 2);

   136 

   137     if(!ipData)

   138         return KErrNoMemory;

   139 

   140     iNumBits  = aNumBits;

   141     iNumWords = numWords;

   142 

   143     return KErrNone;

   144     }

   145 

   146 

   147 /**

   148     Fill a bit vector with a given bit value

   149     @param aVal a bit value

   150 */

   151 void RBitVector::Fill(TBool aVal)

   152     {

   153     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   154     memset(ipData, (aVal ? 0xFF : 0x00), iNumWords << 2);

   155     }

   156 

   157 /** Invert all bits in a bit vector */

   158 void RBitVector::Invert()

   159 {

   160     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   161     for(TUint32 i=0; i<iNumWords; ++i)

   162         ipData[i] ^= K_FFFF;

   163 }

   164 

   165 

   166 /**

   167     Perform "And" operation between 2 vectors. They shall be the same size.

   168     @param  aRhs a vector from the right hand side

   169     @panic ESizeMismatch in the case of different vector sizes

   170 */

   171 void RBitVector::And(const RBitVector& aRhs)

   172     {

   173     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   174     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   175     for(TUint32 i=0; i<iNumWords; ++i)

   176         {

   177         ipData[i] &= aRhs.ipData[i];

   178         }

   179     }

   180 

   181 /**

   182     Perform "Or" operation between 2 vectors. They shall be the same size.    

   183     @param  aRhs a vector from the right hand side

   184     @panic ESizeMismatch in the case of different vector sizes

   185 */

   186 void RBitVector::Or(const RBitVector& aRhs)

   187     {

   188     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   189     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   190     for(TUint32 i=0; i<iNumWords; ++i)

   191         {

   192         ipData[i] |= aRhs.ipData[i];

   193         }

   194     }

   195 

   196 /**

   197     Perform "Xor" operation between 2 vectors. They shall be the same size.    

   198     @param  aRhs a vector from the right hand side

   199     @panic ESizeMismatch in the case of different vector sizes

   200 */

   201 void RBitVector::Xor(const RBitVector& aRhs)

   202     {

   203     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   204     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   205     for(TUint32 i=0; i<iNumWords; ++i)

   206         {

   207         ipData[i] ^= aRhs.ipData[i];

   208         }

   209     }

   210 

   211 //-----------------------------------------------------------------------------

   212 /**

   213     Fill a range from bit number "aIndexFrom" to "aIndexTo" inclusively with the value of aVal

   214     

   215     @param  aIndexFrom  start bit number (inclusive)

   216     @param  aIndexTo    end bit number (inclusive)

   217     @param  aVal        the value to be used to fill the range (0s or 1s)

   218 */

   219 void RBitVector::Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal)

   220     {

   221     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   222 

   223     //-- swap indexes if they are not in order

   224     if(aIndexFrom > aIndexTo)

   225         {

   226         const TUint32 tmp = aIndexFrom;

   227         aIndexFrom = aIndexTo;

   228         aIndexTo = tmp;

   229         }

   230 

   231     __ASSERT_ALWAYS((aIndexFrom < iNumBits) && (aIndexTo < iNumBits), Panic(EIndexOutOfRange));

   232 

   233     const TUint32 wordStart = WordNum(aIndexFrom);

   234     const TUint32 wordTo    = WordNum(aIndexTo);

   235 

   236     if(aVal)

   237         {//-- filling a range with '1'

   238         

   239         TUint32 shift = BitInWord(aIndexFrom);

   240         const TUint32 mask1 = (K_FFFF >> shift) << shift;

   241 

   242         TUint32 mask2 = K_FFFF;

   243         shift = 1+BitInWord(aIndexTo);

   244         if(shift < 32)

   245             {

   246             mask2 = ~((mask2 >> shift) << shift);

   247             }

   248 

   249         if(wordTo == wordStart)

   250             {//-- a special case, filling is in the same word

   251             ipData[wordStart] |= (mask1 & mask2);

   252             }

   253         else

   254             {

   255             ipData[wordStart] |= mask1; 

   256             ipData[wordTo]    |= mask2;

   257             

   258             const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled

   259 

   260             if(wholeWordsBetween)

   261                 memset(ipData+wordStart+1, 0xFF, wholeWordsBetween << 2);

   262                             

   263             }

   264         }

   265     else

   266         {//-- filling a range with '0'

   267         

   268         TUint32 shift = BitInWord(aIndexFrom);

   269         const TUint32 mask1 = ~((K_FFFF >> shift) << shift);

   270 

   271         TUint32 mask2 = 0;

   272         shift = 1+BitInWord(aIndexTo);

   273         if(shift < 32)

   274             {

   275             mask2 = ((K_FFFF >> shift) << shift);

   276             }

   277 

   278         if(wordTo == wordStart)

   279             {//-- a special case, filling is in the same word

   280             ipData[wordStart] &= (mask1 | mask2);

   281             }

   282         else

   283             {

   284             ipData[wordStart] &= mask1; 

   285             ipData[wordTo]    &= mask2;

   286             

   287             const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled

   288 

   289             if(wholeWordsBetween)

   290                 memset(ipData+wordStart+1, 0x00, wholeWordsBetween << 2);

   291                             

   292             }

   293         }

   294 

   295     }

   296 

   297 //-----------------------------------------------------------------------------

   298 

   299 /**

   300     Search for a specified bit value ('0' or '1') in the vector from the given position.

   301     @param  aStartPos   zero-based index; from this position the search will start. This position isn't included to the search.

   302                         On return may contain a new position if the specified bit is found in specified direction.

   303     @param  aBitVal     zero or non-zero bit to search.

   304     @param  aDir        Specifies the search direction

   305 

   306     @return ETrue if the specified bit value is found; aStartPos gets updated.

   307             EFalse otherwise.

   308 

   309 */

   310 TBool RBitVector::Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const

   311     {

   312     __ASSERT_ALWAYS(aStartPos < iNumBits, Panic(EIndexOutOfRange));

   313     ASSERT(iNumWords && ipData);

   314 

   315     switch(aDir)

   316         {

   317         case ERight:    //-- Search from the given position to the right

   318             return FindToRight(aStartPos, aBitVal);

   319 

   320         case ELeft:     //-- Search from the given position to the left (towards lower index)

   321             return FindToLeft(aStartPos, aBitVal);

   322 

   323         case ENearestL: //-- Search for the nearest value in both directions starting from left

   324             return FindNearest(aStartPos, aBitVal, ETrue);

   325 

   326         case ENearestR: //-- Search for the nearest value in both directions starting from right

   327             return FindNearest(aStartPos, aBitVal, EFalse);

   328 

   329         default:

   330             Panic(EWrondFindDirection);

   331             return EFalse;

   332 

   333         };

   334     

   335     }

   336 

   337 //-----------------------------------------------------------------------------

   338 /**

   339     Internal method to look for a given bit value in the right direction.

   340     see TBool RBitVector::Find(...)

   341 */

   342 TBool RBitVector::FindToRight(TUint32& aStartPos, TBool aBitVal) const

   343     {

   344     if(aStartPos >= iNumBits-1)

   345         return EFalse; //-- no way to the right

   346 

   347     const TUint32 startPos = aStartPos+1;

   348     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   349 

   350     TUint32 wordNum = WordNum(startPos);

   351     TUint32 val = ipData[wordNum] ^ fInvert;

   352 

   353     if(wordNum == iNumWords-1)

   354         {//-- process the last word in the array, some higher bits might not belong to the bit vector

   355         val = MaskLastWord(val);

   356         }

   357 

   358     const TUint32 shift = BitInWord(startPos);

   359     val = (val >> shift) << shift; //-- mask unused low bits

   360 

   361     if(val)

   362         {//-- there are '1' bits in the current word

   363         goto found;

   364         }

   365     else

   366         {//-- search in higher words

   367         wordNum++;

   368 

   369         while(iNumWords-wordNum > 1)

   370             {

   371             val = ipData[wordNum] ^ fInvert;

   372             if(val)

   373                 goto found;

   374 

   375             wordNum++;

   376             }

   377 

   378         if(wordNum == iNumWords-1)

   379             {//-- process the last word in the array, some higher bith might not belong to the bit vector

   380             val = ipData[wordNum] ^ fInvert;

   381             val = MaskLastWord(val);

   382 

   383             if(val)

   384                 goto found;

   385             }

   386         }

   387 

   388     return EFalse; //-- haven't found anything

   389 

   390   found:

   391 

   392     val &= (~val+1); //-- select rightmost bit

   393     aStartPos = (wordNum << 5)+Log2(val);

   394     return ETrue;

   395     }

   396 

   397 

   398 //-----------------------------------------------------------------------------

   399 

   400 /**

   401     Internal method to look for a given bit value in the left direction.

   402     see TBool RBitVector::Find(...)

   403 */

   404 TBool RBitVector::FindToLeft(TUint32& aStartPos, TBool aBitVal) const

   405 {

   406     if(!aStartPos)

   407         return EFalse; //-- no way to the left

   408     

   409     const TUint32 startPos=aStartPos-1;

   410     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   411 

   412     TUint32 wordNum = WordNum(startPos);

   413     TUint32 val = ipData[wordNum] ^ fInvert;

   414 

   415     const TUint32 shift = 31-(BitInWord(startPos));

   416     val = (val << shift) >> shift; //-- mask unused high bits

   417 

   418     if(val)

   419     {//-- there are '1' bits in the current word

   420         goto found;

   421     }

   422     else

   423     {//-- search in the lower words

   424         while(wordNum)

   425         {

   426             wordNum--;

   427             val=ipData[wordNum] ^ fInvert;

   428             if(val)

   429                 goto found;

   430         }

   431     }

   432 

   433     return EFalse; //-- nothing found

   434 

   435  found:

   436     aStartPos = (wordNum << 5)+Log2(val);

   437     return ETrue;

   438 }

   439 

   440 //-----------------------------------------------------------------------------

   441 

   442 /**

   443     Internal method to look for a given bit value in the both directions.

   444     see TBool RBitVector::Find(...)

   445 */

   446 TBool RBitVector::FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const

   447 {

   448     if(iNumBits < 2)

   449         return EFalse;

   450 

   451     if(aStartPos == 0)

   452         return FindToRight(aStartPos, aBitVal);

   453 

   454     if(aStartPos == iNumBits-1)

   455         return FindToLeft(aStartPos, aBitVal);

   456 

   457     

   458     const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit

   459     

   460     TUint32 wordNum = WordNum(aStartPos);

   461     TUint32 l_Idx; //-- index of the word to the left

   462     TUint32 r_Idx; //-- index of the word to the right

   463     

   464     l_Idx = r_Idx = wordNum;

   465 

   466     TBool   noWayLeft  = (wordNum == 0);            //-- if we are in the first word

   467     TBool   noWayRight = (wordNum == iNumWords-1);  //-- if we are in the last word

   468 

   469     //-- look in the current word first

   470     TUint32 val = ipData[wordNum] ^ fInvert;

   471     

   472     if(noWayRight)

   473     {   //-- this is the last word in the array, mask unused high bits in the last word

   474         val = MaskLastWord(val);

   475     }

   476 

   477     const TUint32 bitPos = aStartPos & 0x1F;

   478     val &= ~(1<<bitPos); //-- mask the bit at current position

   479     

   480     if(val == 0)

   481     {//-- no '1' bits in the current word

   482         noWayLeft  = ItrLeft(l_Idx);

   483         noWayRight = ItrRight(r_Idx);

   484     }

   485     else if(bitPos == 0)

   486     {

   487         noWayLeft = ItrLeft(l_Idx); //-- move to the previous word

   488     }

   489     else if(bitPos == 31)

   490     {

   491         noWayRight = ItrRight(r_Idx); //-- move to the next word

   492     }

   493     else

   494     {//-- look in the current word, in both halves to the left and right from the start position

   495         

   496         const TUint32 shift1 = 32-bitPos;

   497         const TUint32 partLo = (val << shift1) >> shift1; //-- towards lower bits

   498 

   499         const TUint32 shift2 = bitPos+1;

   500         const TUint32 partHi = (val >> shift2) << shift2; //-- towards higher bits 

   501         

   502 

   503         if(partLo && !partHi) //-- only lower part has '1' bits   

   504         {

   505             aStartPos = (wordNum << 5)+Log2(partLo);

   506             return ETrue;

   507         }

   508         else if(!partLo && partHi) //-- only higher part has '1' bits

   509         {

   510             aStartPos = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );

   511             return ETrue;

   512         }

   513         else if(partLo && partHi) //-- both parts contain '1' bits, select the nearest one

   514         {

   515             const TUint32 posL = (wordNum << 5)+Log2(partLo);

   516             const TUint32 posR = (wordNum << 5)+Log2( (partHi & (~partHi+1)) );

   517         

   518             ASSERT(aStartPos > posL);

   519             ASSERT(posR > aStartPos);

   520             const TUint32 distL = aStartPos-posL;

   521             const TUint32 distR = posR-aStartPos;

   522 

   523             if(distL < distR)

   524             {

   525                 aStartPos = posL;

   526                 return ETrue;

   527             }

   528             else if(distL > distR)

   529             {

   530                 aStartPos = posR;

   531                 return ETrue;

   532             }

   533             else

   534             {//-- distL == distR, take into account search priority

   535                 aStartPos = aToLeft ? posL : posR;

   536                 return ETrue;

   537             }

   538         }

   539         else //-- (!partLo && !partHi), nothing in the current word

   540         {

   541             ASSERT(0);

   542         }

   543 

   544     }// if(bitPos > 0 && bitPos < 31)

   545 

   546     //-- now we are processing separate words from both sides of the search position

   547     for(;;)

   548     { 

   549         TUint32 wL = ipData[l_Idx] ^ fInvert;

   550         TUint32 wR = ipData[r_Idx] ^ fInvert;

   551         if(r_Idx == iNumWords-1)

   552         {   //-- this is the last word in the array, mask unused high bits in the last word

   553             wR = MaskLastWord(wR);

   554         }

   555 

   556         if(wL && !wR)

   557         {

   558             aStartPos = (l_Idx << 5)+Log2(wL);

   559             return ETrue;

   560         }

   561         else if(!wL && wR)

   562         {

   563             aStartPos = (r_Idx << 5)+Log2( (wR & (~wR+1)) );

   564             return ETrue;

   565         }

   566         else if(wL && wR)

   567         {

   568             const TUint32 posL = (l_Idx << 5)+Log2(wL);

   569             const TUint32 posR = (r_Idx << 5)+Log2( (wR & (~wR+1)) );

   570         

   571             ASSERT(aStartPos > posL);

   572             ASSERT(posR > aStartPos);

   573             const TUint32 distL = aStartPos-posL;

   574             const TUint32 distR = posR-aStartPos;

   575 

   576             if(distL < distR)

   577             {

   578                 aStartPos = posL;

   579                 return ETrue;

   580             }

   581             else if(distL > distR)

   582             {

   583                 aStartPos = posR;

   584                 return ETrue;

   585             }

   586             else

   587             {//-- distL == distR, take into account search priority

   588                 aStartPos = aToLeft ? posL : posR;

   589                 return ETrue;

   590             }

   591 

   592         }//else if(wL && wR)

   593 

   594 

   595         if(noWayLeft)

   596         {

   597             aStartPos = r_Idx << 5;

   598             return FindToRight(aStartPos, aBitVal);

   599         }

   600         else

   601         {

   602             noWayLeft  = ItrLeft(l_Idx);

   603         }

   604 

   605         if(noWayRight)

   606         {

   607             aStartPos = l_Idx << 5;

   608             return FindToLeft(aStartPos, aBitVal);

   609         }

   610         else

   611         {    

   612             noWayRight = ItrRight(r_Idx);

   613         }

   614 

   615    }//for(;;)

   616 

   617     //return EFalse;

   618 }

   619 

   620 //-----------------------------------------------------------------------------

   621 /**

   622     Find out if two vectors are different.

   623 

   624     @param  aRhs        vector to compare with

   625     @param  aDiffIndex  if there is a differene, here will be the number of the first different bit

   626     @return ETrue if vectors differ, EFalse, if they are identical.

   627 */

   628 TBool RBitVector::Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const

   629 {

   630     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   631     __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch));

   632     ASSERT(iNumWords > 0);

   633 

   634     TUint32 diffWord=0;

   635     TUint32 wordNum=0;

   636 

   637     //-- compare all but the last word in the array

   638     for(wordNum=0; wordNum < iNumWords-1; ++wordNum)

   639     {

   640         diffWord = ipData[wordNum] ^ aRhs.ipData[wordNum];

   641         if(diffWord)

   642             break;  //-- found difference

   643     }

   644 

   645     //-- process the last word in the array

   646     if(!diffWord)

   647     {

   648         diffWord = MaskLastWord(ipData[wordNum]) ^ MaskLastWord(aRhs.ipData[wordNum]);

   649     }

   650 

   651     if(!diffWord)

   652         return EFalse; //-- vectors are the same

   653 

   654     //-- calculate the position of the bit that different.

   655     diffWord &= (~diffWord+1); //-- select rightmost bit

   656     aDiffIndex = (wordNum << 5)+Log2(diffWord);

   657     

   658     return ETrue;

   659 }

   660 

   661 //-----------------------------------------------------------------------------

   662 

   663 /**

   664     Iterate to the left (towards lower index) in the array of words ipData

   665 

   666     @param  aIdx index within ipData array to be decremented; if it's possible to move left, it will be decreased

   667     @return ETrue if there is no way left i.e. aIdx is 0. EFalse otherwise and aIdx decreased.

   668 */

   669 TBool RBitVector::ItrLeft(TUint32& aIdx) const

   670 {

   671     if(aIdx == 0)

   672         return ETrue;

   673     else

   674     {

   675         aIdx--;

   676         return EFalse;

   677     }

   678 }

   679 

   680 //-----------------------------------------------------------------------------

   681 

   682 /**

   683     Iterate to the right (towards higher index) in the array of words ipData

   684 

   685     @param  aIdx index within ipData array to be incremented; if it's possible to move right, it will be increased

   686     @return ETrue if there is no way right i.e. aIdx corresponds to the last word. EFalse otherwise and aIdx increased.

   687 */

   688 TBool RBitVector::ItrRight(TUint32& aIdx) const

   689 {

   690     if(aIdx < iNumWords-1)

   691     {

   692         aIdx++;

   693         return EFalse;

   694     }

   695     else

   696         return ETrue;

   697 }

   698 

   699 //-----------------------------------------------------------------------------

   700 

   701 /**

   702     Import data to the internal bit vector representation.

   703     Just replaces number of bytes from apData to the ipData.

   704 

   705     @param aStartBit starting bit number. Must have 8-bit alignment.

   706     @param aNumBits  number of bits to import; granularity: 1 bit, i.e. it can be 177, for example.

   707     @param apData    pointer to the data (bitstream) to import.

   708 

   709 */

   710 void RBitVector::DoImportData(TUint32 aStartBit, TUint32 aNumBits, const TAny* apData)

   711 {

   712     ASSERT(aNumBits);

   713     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   714     

   715     //-- check parameters granularity. aStartBit must have 8-bit alignment

   716     __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment));

   717 

   718 

   719     __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= iNumBits), Panic(EIndexOutOfRange));

   720 

   721     const TUint     bitsTail = aNumBits & 0x07;

   722     const TUint32   nBytes = aNumBits >> 3;

   723  

   724     if(nBytes)

   725     {//-- copy full array of bytes

   726         const TUint32   startByte = aStartBit >> 3;

   727         Mem::Copy(((TUint8*)ipData) + startByte, apData, nBytes);

   728     }

   729 

   730     if(bitsTail)

   731     {//-- we need to copy trailing bits from the input data to the corresponding byte of the internal array

   732         const TUint8 mask   = (TUint8)(0xFF >> (8-bitsTail));

   733         const TUint8 orMask = (TUint8)( *((const TUint8*)apData + nBytes) & mask);

   734         const TUint8 andMask= (TUint8)~mask;

   735 

   736         TUint8* pbData = (TUint8*)ipData + nBytes;

   737         *pbData &= andMask;

   738         *pbData |= orMask;

   739     }

   740 

   741 }

   742 

   743 //-----------------------------------------------------------------------------

   744 

   745 /**

   746     Export data from the internal bit vector buffer to the external one.

   747 

   748     @param aStartBit starting bit number. Must have 8-bit alignment.

   749     @param aNumBits  number of bits to export, must comprise the whole byte, i.e. be multiple of 8.

   750                      The client is responsible for masking extra bits it doesn't need. 

   751                      Another implication: e.g. if the bitvector consists of 3 bits, this value must be 8.

   752                      The value of bits 3-7 in the aData[0] will be undefined.

   753 

   754     @param aData     destination data descriptor   

   755 */

   756 void  RBitVector::DoExportData(TUint32 aStartBit, TUint32 aNumBits, TDes8& aData) const

   757 {

   758     ASSERT(aNumBits);

   759     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   760 

   761     //-- check parameters granularity.

   762     __ASSERT_ALWAYS(!(aStartBit & 0x07), Panic(EDataAlignment)); //-- aStartBit must have 8-bit alignment

   763     __ASSERT_ALWAYS(!(aNumBits & 0x07), Panic(EDataAlignment));  //-- number of bits shall comprise a byte

   764 

   765     __ASSERT_ALWAYS(iNumWords && (aStartBit+aNumBits <= (iNumWords << (KBitsInByteLog2+sizeof(TUint32))) ), Panic(EIndexOutOfRange));

   766 

   767     const TUint32 nBytes = aNumBits >> 3;

   768     const TUint32 startByte = aStartBit >> 3;

   769     

   770     aData.SetLength(nBytes);

   771     aData.Copy(((const TUint8*)ipData) + startByte, nBytes);

   772 }

   773 

   774 //-----------------------------------------------------------------------------

   775 

   776 /**

   777     @return number of bits set to '1' in the vector

   778 */

   779 TUint32 RBitVector::Num1Bits() const

   780 {

   781     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   782     if(!iNumBits)

   783         return 0;

   784 

   785     TUint32 cntBits = 0;

   786 

   787     TUint32 wordNum;

   788     for(wordNum=0; wordNum < iNumWords-1; ++wordNum)

   789     {

   790         cntBits += Count1Bits(ipData[wordNum]);

   791     }

   792 

   793     //-- process the last word, it shall be masked

   794     cntBits += Count1Bits(MaskLastWord(ipData[wordNum]));

   795     

   796     return cntBits;

   797 }

   798 

   799 //-----------------------------------------------------------------------------

   800 /**

   801     @return number of bits set to '0' in the vector

   802 */

   803 TUint32 RBitVector::Num0Bits() const

   804 {

   805     return iNumBits - Num1Bits();

   806 }

   807 

   808 

   809 //-----------------------------------------------------------------------------

   810 /**

   811     Calculate number of '1' bits in the range from aIndexFrom to aIndexTo inclusively

   812 

   813     @param  aIndexFrom  starting index; bit[aIndexFrom] is included to the search

   814     @param  aIndexTo    ending index;   bit[aIndexTo] is included to the search

   815     @return number of bits set to '1' in the slice

   816 */

   817 TUint32 RBitVector::Num1Bits(TUint32 aIndexFrom, TUint32 aIndexTo) const

   818 {

   819     __ASSERT_ALWAYS(ipData, Panic(ENotInitialised));

   820     __ASSERT_ALWAYS(aIndexTo < iNumBits && aIndexFrom <= aIndexTo, Panic(EIndexOutOfRange));

   821 

   822     const TUint32 wordFrom = WordNum(aIndexFrom); //?const

   823     const TUint32 wordTo   = WordNum(aIndexTo);

   824 

   825     if(wordFrom == wordTo)

   826     {//-- the same word

   827         TUint32 word = ipData[wordFrom];

   828 

   829         const TUint32 shMaskR = BitInWord(aIndexFrom);

   830         word >>= shMaskR; word <<= shMaskR; //-- zero low bits

   831 

   832         const TUint32 shMaskL = 31-BitInWord(aIndexTo);

   833         word <<= shMaskL;  //-- zero high bits

   834 

   835         return Count1Bits(word);

   836     } 

   837 

   838     TUint32 bitsCnt = 0;

   839     TUint32 wordsBetween = wordTo - wordFrom - 1;

   840 

   841     //-- count '1' bits in the termial words

   842     TUint32 word = ipData[wordFrom];

   843     const TUint32 shMaskR = BitInWord(aIndexFrom);

   844     word >>= shMaskR; //-- zero low bits

   845     bitsCnt += Count1Bits(word);

   846 

   847     word = ipData[wordTo];

   848     const TUint32 shMaskL = 31-BitInWord(aIndexTo);

   849     word <<= shMaskL;  //-- zero high bits

   850     bitsCnt += Count1Bits(word);

   851 

   852     //-- count '1' bits in the words between terminal ones

   853     TUint32 wordIdx = wordFrom+1;

   854     while(wordsBetween--)

   855     {

   856         bitsCnt += Count1Bits(ipData[wordIdx]);

   857     }

   858     

   859 

   860     return bitsCnt;

   861 }

   862 

   863 

   864 

   865 

   866 

   867 

   868 

   869 

   870 

   871 

   872 

   873 

   874 

   875 

   876 

   877 

   878 

   879 

   880 

   881 

   882 

   883