|
1 // Copyright (c) 1996-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 |
|
16 #include "sl_std.h" |
|
17 |
|
18 //----------------------------------------------------------------------------- |
|
19 /** |
|
20 Removes trailing dots from aName. |
|
21 @return new string descriptor that may have its length adjusted |
|
22 */ |
|
23 TPtrC RemoveTrailingDots(const TDesC& aName) |
|
24 { |
|
25 TInt len = aName.Length(); |
|
26 |
|
27 while(len > 0) |
|
28 { |
|
29 if(aName[len-1] == '.') |
|
30 len--; |
|
31 else |
|
32 break; |
|
33 } |
|
34 |
|
35 TPtrC ptrNoDots(aName.Ptr(), len); |
|
36 return ptrNoDots; |
|
37 } |
|
38 |
|
39 |
|
40 TUint32 Log2(TUint32 aVal) |
|
41 { |
|
42 __ASSERT_COMPILE(sizeof(TUint32) == 4); |
|
43 ASSERT(aVal); |
|
44 |
|
45 TUint32 bitPos=31; |
|
46 |
|
47 if(!(aVal >> 16)) {bitPos-=16; aVal<<=16;} |
|
48 if(!(aVal >> 24)) {bitPos-=8; aVal<<=8 ;} |
|
49 if(!(aVal >> 28)) {bitPos-=4; aVal<<=4 ;} |
|
50 if(!(aVal >> 30)) {bitPos-=2; aVal<<=2 ;} |
|
51 if(!(aVal >> 31)) {bitPos-=1;} |
|
52 |
|
53 return bitPos; |
|
54 } |
|
55 |
|
56 |
|
57 TTime DosTimeToTTime(TInt aDosTime,TInt aDosDate) |
|
58 // |
|
59 // Deciphers the dos time/date entry information and converts to TTime |
|
60 // |
|
61 { |
|
62 TInt secMask=0x1F; |
|
63 TInt minMask=0x07E0; |
|
64 TInt hrMask=0xF800; |
|
65 TInt dayMask=0x1F; |
|
66 TInt monthMask=0x01E0; |
|
67 TInt yearMask=0xFE00; |
|
68 |
|
69 TInt secs=(aDosTime&secMask)*2; |
|
70 TInt mins=(aDosTime&minMask)>>5; |
|
71 TInt hrs=(aDosTime&hrMask)>>11; |
|
72 TInt days=(aDosDate&dayMask)-1; |
|
73 TMonth months=(TMonth)(((aDosDate&monthMask)>>5)-1); |
|
74 TInt years=((aDosDate&yearMask)>>9)+1980; |
|
75 |
|
76 TDateTime datetime; |
|
77 TInt ret=datetime.Set(years,months,days,hrs,mins,secs,0); |
|
78 if (ret==KErrNone) |
|
79 return(TTime(datetime)); |
|
80 return(TTime(0)); |
|
81 } |
|
82 |
|
83 TInt DosTimeFromTTime(const TTime& aTime) |
|
84 // |
|
85 // Converts a TTime to a dos time |
|
86 // |
|
87 { |
|
88 TDateTime dateTime=aTime.DateTime(); |
|
89 TInt dosSecs=dateTime.Second()/2; |
|
90 TInt dosMins=dateTime.Minute()<<5; |
|
91 TInt dosHrs=dateTime.Hour()<<11; |
|
92 return dosSecs|dosMins|dosHrs; |
|
93 } |
|
94 |
|
95 TInt DosDateFromTTime(const TTime& aTime) |
|
96 // |
|
97 // Converts a TTime to a dos date |
|
98 // |
|
99 { |
|
100 |
|
101 TDateTime dateTime=aTime.DateTime(); |
|
102 TInt dosDays=dateTime.Day()+1; |
|
103 TInt dosMonths=(dateTime.Month()+1)<<5; |
|
104 TInt dosYears=(dateTime.Year()-1980)<<9; |
|
105 return dosDays|dosMonths|dosYears; |
|
106 } |
|
107 |
|
108 TBuf8<12> DosNameToStdFormat(const TDesC8& aDosName) |
|
109 // |
|
110 // Converts xxx.yyy to standard format aaaaaaaayyy |
|
111 // |
|
112 { |
|
113 |
|
114 __ASSERT_DEBUG(aDosName.Length()>=0 && aDosName.Length()<=12,Fault(EFatBadDosFormatName)); |
|
115 TBuf8<12> result; |
|
116 Mem::Fill((TUint8*)result.Ptr(),result.MaxSize(),' '); |
|
117 TInt dotPos=aDosName.Locate('.'); |
|
118 if (dotPos==KErrNotFound) |
|
119 { |
|
120 result=aDosName; |
|
121 result.SetLength(11); |
|
122 return result; |
|
123 } |
|
124 result=aDosName.Left(dotPos); |
|
125 result.SetLength(11); |
|
126 TPtr8 ext(&result[8],3); |
|
127 ext=aDosName.Right(aDosName.Length()-dotPos-1); |
|
128 return result; |
|
129 } |
|
130 |
|
131 TBuf8<12> DosNameFromStdFormat(const TDesC8& aStdFormatName) |
|
132 // |
|
133 // Converts aaaaaaaayyy to dos name format xxx.yyy |
|
134 // |
|
135 { |
|
136 |
|
137 __ASSERT_DEBUG(aStdFormatName.Length()==11,Fault(EFatBadStdFormatName)); |
|
138 TBuf8<12> result; |
|
139 TInt nameLen=aStdFormatName.Locate(' '); |
|
140 if (nameLen>8 || nameLen==KErrNotFound) |
|
141 nameLen=8; |
|
142 result=aStdFormatName.Left(nameLen); |
|
143 TPtrC8 ext(&aStdFormatName[8],3); |
|
144 TInt extLen=ext.Locate(' '); |
|
145 if (extLen) |
|
146 result.Append(TChar('.')); |
|
147 if (extLen==KErrNotFound) |
|
148 extLen=3; |
|
149 result.Append(ext.Left(extLen)); |
|
150 if(result.Length() && result[0]==0x05 ) |
|
151 { |
|
152 result[0]=0xE5; |
|
153 } |
|
154 return result; |
|
155 } |
|
156 |
|
157 TInt NumberOfVFatEntries(TInt aNameLength) |
|
158 // |
|
159 // Return the number of VFat entries required to describe a filename of length aNameLength |
|
160 // |
|
161 { |
|
162 TInt numberOfEntries=0; |
|
163 if (aNameLength%KMaxVFatEntryName) |
|
164 aNameLength++; // Include a zero terminator |
|
165 // If aNameLength is a exact multiple of KMaxVFatEntryName, don't bother |
|
166 // with a zero terminator - it just adds an unnecessary directory entry |
|
167 |
|
168 numberOfEntries=(1+(aNameLength/KMaxVFatEntryName)); |
|
169 |
|
170 if (aNameLength%KMaxVFatEntryName) |
|
171 numberOfEntries++; |
|
172 |
|
173 return(numberOfEntries); |
|
174 } |
|
175 |
|
176 //----------------------------------------------------------------------------- |
|
177 /** |
|
178 Calculate DOS short name checksum |
|
179 @param aShortName short name descriptor (must be at least 11 bytes long) |
|
180 @return checksum |
|
181 */ |
|
182 TUint8 CalculateShortNameCheckSum(const TDesC8& aShortName) |
|
183 { |
|
184 |
|
185 ASSERT(aShortName.Length() >= KFatDirNameSize); |
|
186 const TUint8* pName = aShortName.Ptr(); |
|
187 |
|
188 const TUint32 w0 = ((const TUint32*)pName)[0]; |
|
189 const TUint32 w1 = ((const TUint32*)pName)[1]; |
|
190 |
|
191 TUint32 chkSum = w0 & 0xFF; |
|
192 |
|
193 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ((w0 << 16) >> 24)); |
|
194 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ((w0 << 8) >> 24)); |
|
195 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ( w0 >> 24)); |
|
196 |
|
197 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + (w1) & 0xFF); |
|
198 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ((w1 << 16) >> 24)); |
|
199 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ((w1 << 8) >> 24)); |
|
200 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + ( w1 >> 24)); |
|
201 |
|
202 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + pName[8]); |
|
203 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + pName[9]); |
|
204 chkSum = (TUint8)(((chkSum<<7) | (chkSum>>1)) + pName[10]); |
|
205 |
|
206 return (TUint8)chkSum; |
|
207 } |
|
208 |
|
209 //----------------------------------------------------------------------------- |
|
210 |
|
211 const TUint32 K_FFFF = 0xFFFFFFFF; //-- all one bits, beware rigth shifts of signed integers! |
|
212 |
|
213 |
|
214 RBitVector::RBitVector() |
|
215 :iNumBits(0), ipData(NULL), iNumWords(0) |
|
216 { |
|
217 } |
|
218 |
|
219 |
|
220 RBitVector::~RBitVector() |
|
221 { |
|
222 Close(); |
|
223 } |
|
224 |
|
225 /** |
|
226 Panics. |
|
227 @param aPanicCode a panic code |
|
228 */ |
|
229 void RBitVector::Panic(TPanicCode aPanicCode) const |
|
230 { |
|
231 _LIT(KPanicCat,"RBitVector"); |
|
232 User::Panic(KPanicCat, aPanicCode); |
|
233 } |
|
234 |
|
235 /** explicitly closes the object and deallocates memory */ |
|
236 void RBitVector::Close() |
|
237 { |
|
238 iNumBits = 0; |
|
239 iNumWords =0; |
|
240 User::Free(ipData); |
|
241 ipData = NULL; |
|
242 } |
|
243 |
|
244 //----------------------------------------------------------------------------- |
|
245 |
|
246 /** |
|
247 Comparison perator. |
|
248 @param aRhs a vector to compate with. |
|
249 @panic ESizeMismatch in the case of different vector sizes |
|
250 */ |
|
251 TBool RBitVector::operator==(const RBitVector& aRhs) const |
|
252 { |
|
253 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
254 __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch)); |
|
255 |
|
256 |
|
257 if(!iNumBits) |
|
258 return ETrue; //-- comparing 0-lenght arrays |
|
259 |
|
260 if(this == &aRhs) |
|
261 return ETrue; //-- comparing with itself |
|
262 |
|
263 if(iNumWords >= 1) |
|
264 { |
|
265 const TUint32 cntBytes = (iNumBits >> 5) << 2; //-- bytes to compare |
|
266 if(memcompare((const TUint8*)ipData, cntBytes, (const TUint8*)aRhs.ipData, cntBytes)) |
|
267 return EFalse; |
|
268 } |
|
269 |
|
270 const TUint32 bitsRest = iNumBits & 0x1F; |
|
271 if(bitsRest) |
|
272 { |
|
273 const TUint32 mask = K_FFFF >> (32-bitsRest); |
|
274 return ( (ipData[iNumWords-1] & mask) == (aRhs.ipData[iNumWords-1] & mask) ); |
|
275 } |
|
276 |
|
277 return ETrue; |
|
278 } |
|
279 |
|
280 TBool RBitVector::operator!=(const RBitVector& aRhs) const |
|
281 { |
|
282 return ! ((*this) == aRhs); |
|
283 } |
|
284 |
|
285 //----------------------------------------------------------------------------- |
|
286 |
|
287 /** The same as Create(), but leaves on error */ |
|
288 void RBitVector::CreateL(TUint32 aNumBits) |
|
289 { |
|
290 User::LeaveIfError(Create(aNumBits)); |
|
291 } |
|
292 |
|
293 |
|
294 /** |
|
295 Create the vector with the size of aNumBits bits. |
|
296 @return system-wide error codes: |
|
297 KErrNoMemory unable to allocate sufficient amount of memory for the array |
|
298 KErrInUse an attempt to call Create() for non-empty vector. Close it first. |
|
299 KErrArgument invalid aNumBits value == 0 |
|
300 */ |
|
301 TInt RBitVector::Create(TUint32 aNumBits) |
|
302 { |
|
303 |
|
304 if(ipData) |
|
305 return KErrInUse; //-- array is already in use. Close it first. |
|
306 |
|
307 if(!aNumBits) |
|
308 return KErrArgument; |
|
309 |
|
310 //-- memory is allocated by word (32 bit) quiantities |
|
311 const TUint32 numWords = (aNumBits >> 5) + ((aNumBits & 0x1F) > 0 ? 1:0); |
|
312 ipData = (TUint32*)User::AllocZ(numWords << 2); |
|
313 |
|
314 if(!ipData) |
|
315 return KErrNoMemory; |
|
316 |
|
317 iNumBits = aNumBits; |
|
318 iNumWords = numWords; |
|
319 |
|
320 return KErrNone; |
|
321 } |
|
322 |
|
323 |
|
324 /** |
|
325 Fill a bit vector with a given bit value |
|
326 @param aVal a bit value |
|
327 */ |
|
328 void RBitVector::Fill(TBool aVal) |
|
329 { |
|
330 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
331 memset(ipData, (aVal ? 0xFF : 0x00), iNumWords << 2); |
|
332 } |
|
333 |
|
334 /** Invert all bits in a bit vector */ |
|
335 void RBitVector::Invert() |
|
336 { |
|
337 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
338 for(TUint32 i=0; i<iNumWords; ++i) |
|
339 ipData[i] ^= K_FFFF; |
|
340 } |
|
341 |
|
342 |
|
343 /** |
|
344 Perform "And" operation between 2 vectors. They shall be the same size. |
|
345 @param aRhs a vector from the right hand side |
|
346 @panic ESizeMismatch in the case of different vector sizes |
|
347 */ |
|
348 void RBitVector::And(const RBitVector& aRhs) |
|
349 { |
|
350 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
351 __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch)); |
|
352 for(TUint32 i=0; i<iNumWords; ++i) |
|
353 { |
|
354 ipData[i] &= aRhs.ipData[i]; |
|
355 } |
|
356 } |
|
357 |
|
358 /** |
|
359 Perform "Or" operation between 2 vectors. They shall be the same size. |
|
360 @param aRhs a vector from the right hand side |
|
361 @panic ESizeMismatch in the case of different vector sizes |
|
362 */ |
|
363 void RBitVector::Or(const RBitVector& aRhs) |
|
364 { |
|
365 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
366 __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch)); |
|
367 for(TUint32 i=0; i<iNumWords; ++i) |
|
368 { |
|
369 ipData[i] |= aRhs.ipData[i]; |
|
370 } |
|
371 } |
|
372 |
|
373 /** |
|
374 Perform "Xor" operation between 2 vectors. They shall be the same size. |
|
375 @param aRhs a vector from the right hand side |
|
376 @panic ESizeMismatch in the case of different vector sizes |
|
377 */ |
|
378 void RBitVector::Xor(const RBitVector& aRhs) |
|
379 { |
|
380 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
381 __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch)); |
|
382 for(TUint32 i=0; i<iNumWords; ++i) |
|
383 { |
|
384 ipData[i] ^= aRhs.ipData[i]; |
|
385 } |
|
386 } |
|
387 |
|
388 //----------------------------------------------------------------------------- |
|
389 /** |
|
390 Fill a range from bit number "aIndexFrom" to "aIndexTo" inclusively with the value of aVal |
|
391 |
|
392 @param aIndexFrom start bit number (inclusive) |
|
393 @param aIndexTo end bit number (inclusive) |
|
394 @param aVal the value to be used to fill the range (0s or 1s) |
|
395 */ |
|
396 void RBitVector::Fill(TUint32 aIndexFrom, TUint32 aIndexTo, TBool aVal) |
|
397 { |
|
398 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
399 |
|
400 //-- swap indexes if they are not in order |
|
401 if(aIndexFrom > aIndexTo) |
|
402 { |
|
403 const TUint32 tmp = aIndexFrom; |
|
404 aIndexFrom = aIndexTo; |
|
405 aIndexTo = tmp; |
|
406 } |
|
407 |
|
408 __ASSERT_ALWAYS((aIndexFrom < iNumBits) && (aIndexTo < iNumBits), Panic(EIndexOutOfRange)); |
|
409 |
|
410 const TUint32 wordStart = WordNum(aIndexFrom); |
|
411 const TUint32 wordTo = WordNum(aIndexTo); |
|
412 |
|
413 if(aVal) |
|
414 {//-- filling a range with '1' |
|
415 |
|
416 TUint32 shift = BitInWord(aIndexFrom); |
|
417 const TUint32 mask1 = (K_FFFF >> shift) << shift; |
|
418 |
|
419 TUint32 mask2 = K_FFFF; |
|
420 shift = 1+BitInWord(aIndexTo); |
|
421 if(shift < 32) |
|
422 { |
|
423 mask2 = ~((mask2 >> shift) << shift); |
|
424 } |
|
425 |
|
426 if(wordTo == wordStart) |
|
427 {//-- a special case, filling is in the same word |
|
428 ipData[wordStart] |= (mask1 & mask2); |
|
429 } |
|
430 else |
|
431 { |
|
432 ipData[wordStart] |= mask1; |
|
433 ipData[wordTo] |= mask2; |
|
434 |
|
435 const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled |
|
436 |
|
437 if(wholeWordsBetween) |
|
438 memset(ipData+wordStart+1, 0xFF, wholeWordsBetween << 2); |
|
439 |
|
440 } |
|
441 } |
|
442 else |
|
443 {//-- filling a range with '0' |
|
444 |
|
445 //-- if you need this functionality, remove the panic and uncomment the code below. |
|
446 |
|
447 Panic(ENotImplemented); |
|
448 |
|
449 /* |
|
450 TUint32 shift = BitInWord(aIndexFrom); |
|
451 const TUint32 mask1 = ~((K_FFFF >> shift) << shift); |
|
452 |
|
453 TUint32 mask2 = 0; |
|
454 shift = 1+BitInWord(aIndexTo); |
|
455 if(shift < 32) |
|
456 { |
|
457 mask2 = ((K_FFFF >> shift) << shift); |
|
458 } |
|
459 |
|
460 if(wordTo == wordStart) |
|
461 {//-- a special case, filling is in the same word |
|
462 ipData[wordStart] &= (mask1 | mask2); |
|
463 } |
|
464 else |
|
465 { |
|
466 ipData[wordStart] &= mask1; |
|
467 ipData[wordTo] &= mask2; |
|
468 |
|
469 const TUint32 wholeWordsBetween = wordTo - wordStart - 1; //-- whole words that can be bulk filled |
|
470 |
|
471 if(wholeWordsBetween) |
|
472 memset(ipData+wordStart+1, 0x00, wholeWordsBetween << 2); |
|
473 |
|
474 } |
|
475 */ |
|
476 } |
|
477 |
|
478 } |
|
479 |
|
480 //----------------------------------------------------------------------------- |
|
481 |
|
482 /** |
|
483 Search for a specified bit value ('0' or '1') in the vector from the given position. |
|
484 @param aStartPos zero-based index; from this position the search will start. This position isn't included to the search. |
|
485 On return may contain a new position if the specified bit is found in specified direction. |
|
486 @param aBitVal zero or non-zero bit to search. |
|
487 @param aDir Specifies the search direction |
|
488 |
|
489 @return ETrue if the specified bit value is found; aStartPos gets updated. |
|
490 EFalse otherwise. |
|
491 |
|
492 */ |
|
493 TBool RBitVector::Find(TUint32& aStartPos, TBool aBitVal, TFindDirection aDir) const |
|
494 { |
|
495 __ASSERT_ALWAYS(aStartPos < iNumBits, Panic(EIndexOutOfRange)); |
|
496 ASSERT(iNumWords && ipData); |
|
497 |
|
498 switch(aDir) |
|
499 { |
|
500 case ERight: //-- Search from the given position to the right |
|
501 return FindToRight(aStartPos, aBitVal); |
|
502 |
|
503 case ELeft: //-- Search from the given position to the left (towards lower index) |
|
504 return FindToLeft(aStartPos, aBitVal); |
|
505 |
|
506 case ENearestL: //-- Search for the nearest value in both directions starting from left |
|
507 return FindNearest(aStartPos, aBitVal, ETrue); |
|
508 |
|
509 case ENearestR: //-- Search for the nearest value in both directions starting from right |
|
510 return FindNearest(aStartPos, aBitVal, EFalse); |
|
511 |
|
512 default: |
|
513 Panic(EWrondFindDirection); |
|
514 return EFalse; |
|
515 |
|
516 }; |
|
517 |
|
518 } |
|
519 |
|
520 //----------------------------------------------------------------------------- |
|
521 /** |
|
522 Internal method to look for a given bit value in the right direction. |
|
523 see TBool RBitVector::Find(...) |
|
524 */ |
|
525 TBool RBitVector::FindToRight(TUint32& aStartPos, TBool aBitVal) const |
|
526 { |
|
527 if(aStartPos >= iNumBits-1) |
|
528 return EFalse; //-- no way to the right |
|
529 |
|
530 const TUint32 startPos = aStartPos+1; |
|
531 const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit |
|
532 |
|
533 TUint32 wordNum = WordNum(startPos); |
|
534 TUint32 val = ipData[wordNum] ^ fInvert; |
|
535 |
|
536 if(wordNum == iNumWords-1) |
|
537 {//-- process the last word in the array, some higher bits might not belong to the bit vector |
|
538 val = MaskLastWord(val); |
|
539 } |
|
540 |
|
541 const TUint32 shift = BitInWord(startPos); |
|
542 val = (val >> shift) << shift; //-- mask unused low bits |
|
543 |
|
544 if(val) |
|
545 {//-- there are '1' bits in the current word |
|
546 goto found; |
|
547 } |
|
548 else |
|
549 {//-- search in higher words |
|
550 wordNum++; |
|
551 |
|
552 while(iNumWords-wordNum > 1) |
|
553 { |
|
554 val = ipData[wordNum] ^ fInvert; |
|
555 if(val) |
|
556 goto found; |
|
557 |
|
558 wordNum++; |
|
559 } |
|
560 |
|
561 if(wordNum == iNumWords-1) |
|
562 {//-- process the last word in the array, some higher bith might not belong to the bit vector |
|
563 val = ipData[wordNum] ^ fInvert; |
|
564 val = MaskLastWord(val); |
|
565 |
|
566 if(val) |
|
567 goto found; |
|
568 } |
|
569 } |
|
570 |
|
571 return EFalse; //-- haven't found anything |
|
572 |
|
573 found: |
|
574 |
|
575 val &= (~val+1); //-- select rightmost bit |
|
576 aStartPos = (wordNum << 5)+Log2(val); |
|
577 return ETrue; |
|
578 } |
|
579 |
|
580 |
|
581 //----------------------------------------------------------------------------- |
|
582 |
|
583 /** |
|
584 Internal method to look for a given bit value in the left direction. |
|
585 see TBool RBitVector::Find(...) |
|
586 */ |
|
587 TBool RBitVector::FindToLeft(TUint32& aStartPos, TBool aBitVal) const |
|
588 { |
|
589 if(!aStartPos) |
|
590 return EFalse; //-- no way to the left |
|
591 |
|
592 const TUint32 startPos=aStartPos-1; |
|
593 const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit |
|
594 |
|
595 TUint32 wordNum = WordNum(startPos); |
|
596 TUint32 val = ipData[wordNum] ^ fInvert; |
|
597 |
|
598 const TUint32 shift = 31-(BitInWord(startPos)); |
|
599 val = (val << shift) >> shift; //-- mask unused high bits |
|
600 |
|
601 if(val) |
|
602 {//-- there are '1' bits in the current word |
|
603 goto found; |
|
604 } |
|
605 else |
|
606 {//-- search in the lower words |
|
607 while(wordNum) |
|
608 { |
|
609 wordNum--; |
|
610 val=ipData[wordNum] ^ fInvert; |
|
611 if(val) |
|
612 goto found; |
|
613 } |
|
614 } |
|
615 |
|
616 return EFalse; //-- nothing found |
|
617 |
|
618 found: |
|
619 aStartPos = (wordNum << 5)+Log2(val); |
|
620 return ETrue; |
|
621 } |
|
622 |
|
623 //----------------------------------------------------------------------------- |
|
624 |
|
625 /** |
|
626 Internal method to look for a given bit value in the both directions. |
|
627 see TBool RBitVector::Find(...) |
|
628 */ |
|
629 TBool RBitVector::FindNearest(TUint32& aStartPos, TBool aBitVal, TBool aToLeft) const |
|
630 { |
|
631 if(iNumBits < 2) |
|
632 return EFalse; |
|
633 |
|
634 if(aStartPos == 0) |
|
635 return FindToRight(aStartPos, aBitVal); |
|
636 |
|
637 if(aStartPos == iNumBits-1) |
|
638 return FindToLeft(aStartPos, aBitVal); |
|
639 |
|
640 |
|
641 const TUint32 fInvert = aBitVal ? 0 : K_FFFF; //-- invert everything if we are looking for '0' bit |
|
642 |
|
643 TUint32 wordNum = WordNum(aStartPos); |
|
644 TUint32 l_Idx; //-- index of the word to the left |
|
645 TUint32 r_Idx; //-- index of the word to the right |
|
646 |
|
647 l_Idx = r_Idx = wordNum; |
|
648 |
|
649 TBool noWayLeft = (wordNum == 0); //-- if we are in the first word |
|
650 TBool noWayRight = (wordNum == iNumWords-1); //-- if we are in the last word |
|
651 |
|
652 //-- look in the current word first |
|
653 TUint32 val = ipData[wordNum] ^ fInvert; |
|
654 |
|
655 if(noWayRight) |
|
656 { //-- this is the last word in the array, mask unused high bits in the last word |
|
657 val = MaskLastWord(val); |
|
658 } |
|
659 |
|
660 const TUint32 bitPos = aStartPos & 0x1F; |
|
661 val &= ~(1<<bitPos); //-- mask the bit at current position |
|
662 |
|
663 if(val == 0) |
|
664 {//-- no '1' bits in the current word |
|
665 noWayLeft = ItrLeft(l_Idx); |
|
666 noWayRight = ItrRight(r_Idx); |
|
667 } |
|
668 else if(bitPos == 0) |
|
669 { |
|
670 noWayLeft = ItrLeft(l_Idx); //-- move to the previous word |
|
671 } |
|
672 else if(bitPos == 31) |
|
673 { |
|
674 noWayRight = ItrRight(r_Idx); //-- move to the next word |
|
675 } |
|
676 else |
|
677 {//-- look in the current word, in both halves to the left and right from the start position |
|
678 |
|
679 const TUint32 shift1 = 32-bitPos; |
|
680 const TUint32 partLo = (val << shift1) >> shift1; //-- towards lower bits |
|
681 |
|
682 const TUint32 shift2 = bitPos+1; |
|
683 const TUint32 partHi = (val >> shift2) << shift2; //-- towards higher bits |
|
684 |
|
685 |
|
686 if(partLo && !partHi) //-- only lower part has '1' bits |
|
687 { |
|
688 aStartPos = (wordNum << 5)+Log2(partLo); |
|
689 return ETrue; |
|
690 } |
|
691 else if(!partLo && partHi) //-- only higher part has '1' bits |
|
692 { |
|
693 aStartPos = (wordNum << 5)+Log2( (partHi & (~partHi+1)) ); |
|
694 return ETrue; |
|
695 } |
|
696 else if(partLo && partHi) //-- both parts contain '1' bits, select the nearest one |
|
697 { |
|
698 const TUint32 posL = (wordNum << 5)+Log2(partLo); |
|
699 const TUint32 posR = (wordNum << 5)+Log2( (partHi & (~partHi+1)) ); |
|
700 |
|
701 ASSERT(aStartPos > posL); |
|
702 ASSERT(posR > aStartPos); |
|
703 const TUint32 distL = aStartPos-posL; |
|
704 const TUint32 distR = posR-aStartPos; |
|
705 |
|
706 if(distL < distR) |
|
707 { |
|
708 aStartPos = posL; |
|
709 return ETrue; |
|
710 } |
|
711 else if(distL > distR) |
|
712 { |
|
713 aStartPos = posR; |
|
714 return ETrue; |
|
715 } |
|
716 else |
|
717 {//-- distL == distR, take into account search priority |
|
718 aStartPos = aToLeft ? posL : posR; |
|
719 return ETrue; |
|
720 } |
|
721 } |
|
722 else //-- (!partLo && !partHi), nothing in the current word |
|
723 { |
|
724 ASSERT(0); |
|
725 } |
|
726 |
|
727 }// if(bitPos > 0 && bitPos < 31) |
|
728 |
|
729 //-- now we are processing separate words from both sides of the search position |
|
730 for(;;) |
|
731 { |
|
732 TUint32 wL = ipData[l_Idx] ^ fInvert; |
|
733 TUint32 wR = ipData[r_Idx] ^ fInvert; |
|
734 if(r_Idx == iNumWords-1) |
|
735 { //-- this is the last word in the array, mask unused high bits in the last word |
|
736 wR = MaskLastWord(wR); |
|
737 } |
|
738 |
|
739 if(wL && !wR) |
|
740 { |
|
741 aStartPos = (l_Idx << 5)+Log2(wL); |
|
742 return ETrue; |
|
743 } |
|
744 else if(!wL && wR) |
|
745 { |
|
746 aStartPos = (r_Idx << 5)+Log2( (wR & (~wR+1)) ); |
|
747 return ETrue; |
|
748 } |
|
749 else if(wL && wR) |
|
750 { |
|
751 const TUint32 posL = (l_Idx << 5)+Log2(wL); |
|
752 const TUint32 posR = (r_Idx << 5)+Log2( (wR & (~wR+1)) ); |
|
753 |
|
754 ASSERT(aStartPos > posL); |
|
755 ASSERT(posR > aStartPos); |
|
756 const TUint32 distL = aStartPos-posL; |
|
757 const TUint32 distR = posR-aStartPos; |
|
758 |
|
759 if(distL < distR) |
|
760 { |
|
761 aStartPos = posL; |
|
762 return ETrue; |
|
763 } |
|
764 else if(distL > distR) |
|
765 { |
|
766 aStartPos = posR; |
|
767 return ETrue; |
|
768 } |
|
769 else |
|
770 {//-- distL == distR, take into account search priority |
|
771 aStartPos = aToLeft ? posL : posR; |
|
772 return ETrue; |
|
773 } |
|
774 |
|
775 }//else if(wL && wR) |
|
776 |
|
777 |
|
778 if(noWayLeft) |
|
779 { |
|
780 aStartPos = r_Idx << 5; |
|
781 return FindToRight(aStartPos, aBitVal); |
|
782 } |
|
783 else |
|
784 { |
|
785 noWayLeft = ItrLeft(l_Idx); |
|
786 } |
|
787 |
|
788 if(noWayRight) |
|
789 { |
|
790 aStartPos = l_Idx << 5; |
|
791 return FindToLeft(aStartPos, aBitVal); |
|
792 } |
|
793 else |
|
794 { |
|
795 noWayRight = ItrRight(r_Idx); |
|
796 } |
|
797 |
|
798 }//for(;;) |
|
799 |
|
800 //return EFalse; |
|
801 } |
|
802 |
|
803 //----------------------------------------------------------------------------- |
|
804 /** |
|
805 Find out if two vectors are different. |
|
806 |
|
807 @param aRhs vector to compare with |
|
808 @param aDiffIndex if there is a differene, here will be the number of the first different bit |
|
809 @return ETrue if vectors differ, EFalse, if they are identical. |
|
810 */ |
|
811 TBool RBitVector::Diff(const RBitVector& aRhs, TUint32& aDiffIndex) const |
|
812 { |
|
813 __ASSERT_ALWAYS(ipData, Panic(ENotInitialised)); |
|
814 __ASSERT_ALWAYS(iNumBits == aRhs.iNumBits, Panic(ESizeMismatch)); |
|
815 ASSERT(iNumWords > 0); |
|
816 |
|
817 TUint32 diffWord=0; |
|
818 TUint32 wordNum=0; |
|
819 |
|
820 //-- compare all but the last word in the array |
|
821 for(wordNum=0; wordNum < iNumWords-1; ++wordNum) |
|
822 { |
|
823 diffWord = ipData[wordNum] ^ aRhs.ipData[wordNum]; |
|
824 if(diffWord) |
|
825 break; //-- found difference |
|
826 } |
|
827 |
|
828 //-- process the last word in the array |
|
829 if(!diffWord) |
|
830 { |
|
831 diffWord = MaskLastWord(ipData[wordNum]) ^ MaskLastWord(aRhs.ipData[wordNum]); |
|
832 } |
|
833 |
|
834 if(!diffWord) |
|
835 return EFalse; //-- vectors are the same |
|
836 |
|
837 //-- calculate the position of the bit that different. |
|
838 diffWord &= (~diffWord+1); //-- select rightmost bit |
|
839 aDiffIndex = (wordNum << 5)+Log2(diffWord); |
|
840 |
|
841 return ETrue; |
|
842 } |
|
843 //----------------------------------------------------------------------------- |
|
844 |
|
845 /** |
|
846 Iterate to the left (towards lower index) in the array of words ipData |
|
847 |
|
848 @param aIdx index within ipData array to be decremented; if it's possible to move left, it will be decreased |
|
849 @return ETrue if there is no way left i.e. aIdx is 0. EFalse otherwise and aIdx decreased. |
|
850 */ |
|
851 TBool RBitVector::ItrLeft(TUint32& aIdx) const |
|
852 { |
|
853 if(aIdx == 0) |
|
854 return ETrue; |
|
855 else |
|
856 { |
|
857 aIdx--; |
|
858 return EFalse; |
|
859 } |
|
860 } |
|
861 |
|
862 |
|
863 /** |
|
864 Iterate to the right (towards higher index) in the array of words ipData |
|
865 |
|
866 @param aIdx index within ipData array to be incremented; if it's possible to move right, it will be increased |
|
867 @return ETrue if there is no way right i.e. aIdx corresponds to the last word. EFalse otherwise and aIdx increased. |
|
868 */ |
|
869 TBool RBitVector::ItrRight(TUint32& aIdx) const |
|
870 { |
|
871 if(aIdx < iNumWords-1) |
|
872 { |
|
873 aIdx++; |
|
874 return EFalse; |
|
875 } |
|
876 else |
|
877 return ETrue; |
|
878 } |
|
879 |
|
880 |
|
881 |
|
882 |
|
883 |
|
884 |
|
885 |
|
886 |