|
1 /* |
|
2 * Copyright (c) 2005-2009 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 #include "byte_pair.h" |
|
20 #define __BREAKPOINT() |
|
21 |
|
22 #undef ASSERT |
|
23 #define ASSERT(c) if(!(c)) \ |
|
24 { \ |
|
25 __BREAKPOINT() \ |
|
26 } |
|
27 |
|
28 #include <ctime> |
|
29 clock_t ClockCompress = 0; |
|
30 |
|
31 //#define DEBUG_ASSERT |
|
32 #ifdef DEBUG_ASSERT |
|
33 void myassert(int c) { |
|
34 if (!(c)) { |
|
35 cout <<"myassertion failed" << endl; |
|
36 } |
|
37 } |
|
38 #endif |
|
39 |
|
40 void CBytePair::Initialize(TUint8* data, TInt size) |
|
41 { |
|
42 TUint32 *p; |
|
43 p = (TUint32*)PairCount; |
|
44 while(p < (TUint32*)PairCount+0x10000) { |
|
45 *p = 0xffff0000; |
|
46 p ++; |
|
47 } |
|
48 p = (TUint32*)PairBuffer; |
|
49 while (p < (TUint32*)PairBuffer + sizeof(PairBuffer) / 4) { |
|
50 *p = 0xffffffff; |
|
51 p++; |
|
52 } |
|
53 PairBufferNext = 0; |
|
54 p = (TUint32*)PairPos; |
|
55 while (p < (TUint32*)PairPos + sizeof(PairPos) /4 ) { |
|
56 *p = 0xffffffff; |
|
57 p ++; |
|
58 } |
|
59 PairPosNext = 0; |
|
60 p = (TUint32*)PairLists; |
|
61 while (p < (TUint32*)PairLists + sizeof(PairLists) / 4) { |
|
62 *p = 0xffffffff; |
|
63 p ++; |
|
64 } |
|
65 PairListHigh = 0; |
|
66 |
|
67 CountBytes(data,size); |
|
68 marker = -1; |
|
69 LeastCommonByte(marker); |
|
70 ByteUsed(marker); |
|
71 |
|
72 TUint8 *pData, *pMask; |
|
73 TUint16 pair; |
|
74 pData=data, pMask=Mask; |
|
75 if (*pData == marker) |
|
76 *pMask = ByteMarked; |
|
77 else if (*(pData+1) == marker) |
|
78 *pMask = ByteTail; |
|
79 else { |
|
80 *pMask = ByteHead; |
|
81 pair = (TUint16)(*pData | *(pData+1) << 8); |
|
82 InsertPair(pair, 0); |
|
83 } |
|
84 |
|
85 for (pData++, pMask++; pData < data+size-1; pData++, pMask++) { |
|
86 if (*pData == marker){ |
|
87 *pMask = ByteMarked; |
|
88 continue; |
|
89 } |
|
90 if (*(pData+1) == marker){ |
|
91 *pMask = ByteTail; |
|
92 continue; |
|
93 } |
|
94 if ((*pData == *(pData+1)) && (*pData == *(pData-1))&& (*(pMask-1) == ByteHead)){ |
|
95 *pMask = ByteTail; |
|
96 continue; |
|
97 } |
|
98 *pMask = ByteHead; |
|
99 pair = (TUint16)(*pData | *(pData+1) << 8); |
|
100 InsertPair(pair,(TUint16)(pData-data)); |
|
101 } |
|
102 if (*pData == marker) |
|
103 *pMask = ByteMarked; |
|
104 else |
|
105 *pMask = ByteTail; |
|
106 } |
|
107 |
|
108 TInt CBytePair::MostCommonPair(TInt& pair) |
|
109 { |
|
110 TUint16 index = PairLists[PairListHigh]; |
|
111 TUint16 tmpindex = index; |
|
112 TUint16 p = PairBuffer[index].Pair; |
|
113 TInt tieBreak, bestTieBreak; |
|
114 bestTieBreak = -ByteCount[p&0xff] - ByteCount[p>>8]; |
|
115 while(PairBuffer[tmpindex].Next != PosEnd) { |
|
116 tmpindex = PairBuffer[tmpindex].Next; |
|
117 p = PairBuffer[tmpindex].Pair; |
|
118 tieBreak = -ByteCount[p&0xff]-ByteCount[p>>8]; |
|
119 if(tieBreak>bestTieBreak) |
|
120 { |
|
121 index = tmpindex; |
|
122 bestTieBreak = tieBreak; |
|
123 } |
|
124 } |
|
125 pair = PairBuffer[index].Pair; |
|
126 return PairListHigh; |
|
127 } |
|
128 |
|
129 TInt CBytePair::LeastCommonByte(TInt& byte) |
|
130 { |
|
131 TInt bestCount = 0xffff; |
|
132 TInt bestByte = -1; |
|
133 TInt b; |
|
134 for(b=0; b<0x100; b++) |
|
135 { |
|
136 TInt f = ByteCount[b]; |
|
137 if(f<bestCount) |
|
138 { |
|
139 bestCount = f; |
|
140 bestByte = b; |
|
141 } |
|
142 } |
|
143 byte = bestByte; |
|
144 return bestCount; |
|
145 } |
|
146 |
|
147 |
|
148 TInt CBytePair::Compress(TUint8* dst, TUint8* src, TInt size) |
|
149 { |
|
150 clock_t ClockStart = clock(); |
|
151 TUint8 tokens[0x100*3]; |
|
152 TInt tokenCount = 0; |
|
153 TInt overhead; |
|
154 |
|
155 TUint8 * dst2 = dst + size*2; |
|
156 memcpy (dst2, src, size); |
|
157 Initialize (dst2, size); |
|
158 //DumpList(dst2, size); |
|
159 for(TInt r=256; r>0; --r) |
|
160 { |
|
161 TInt byte; |
|
162 TInt byteCount = LeastCommonByte(byte); |
|
163 if (iFastCompress && byteCount) break; |
|
164 //if(byteCount) break; |
|
165 TInt pair; |
|
166 TInt pairCount = MostCommonPair(pair); |
|
167 TInt saving = pairCount-byteCount; |
|
168 |
|
169 //cout << "byte: <" << hex << setw(2) << setfill('0') << byte << ">" << byteCount << endl; |
|
170 //cout << "pair: <" << hex << setw(4) << setfill('0') << pair << ">" << pairCount << endl; |
|
171 overhead = 3; |
|
172 if(tokenCount>=32) |
|
173 overhead = 2; |
|
174 if(saving<=overhead) |
|
175 break; |
|
176 |
|
177 TUint8* d=tokens+3*tokenCount; |
|
178 ++tokenCount; |
|
179 *d++ = (TUint8)byte; |
|
180 ByteUsed(byte); |
|
181 *d++ = (TUint8)pair; |
|
182 ByteUsed(pair&0xff); |
|
183 *d++ = (TUint8)(pair>>8); |
|
184 ByteUsed(pair>>8); |
|
185 //++GlobalPairs[pair]; |
|
186 |
|
187 //clock_t ClockReplace1 ,ClockReplace2; |
|
188 TUint16 index = PairCount[pair].Index; |
|
189 TUint16 count = PairCount[pair].Count; |
|
190 TUint16 posindex = PairBuffer[index].Pos; |
|
191 TUint16 headpos, tailpos, tmppos, bytepos; |
|
192 TUint16 tmppair; |
|
193 // Remove pairs |
|
194 while (posindex != PosEnd) { |
|
195 headpos = PairPos[posindex].Pos; |
|
196 tailpos = (TUint16)(headpos + 1); |
|
197 while (Mask[tailpos] == ByteRemoved){ |
|
198 tailpos ++; |
|
199 myassert(tailpos < MaxBlockSize); |
|
200 } |
|
201 GetPairBackward(dst2, headpos, tmppos, tmppair); |
|
202 if ((tmppos != PosEnd) && (Mask[tmppos] == ByteHead)) { |
|
203 RemovePair(tmppair, tmppos); |
|
204 Mask[tmppos] = ByteTail; |
|
205 } |
|
206 if (Mask[tailpos] == ByteHead) { |
|
207 GetPairForward(dst2, tailpos, size, tmppos, tmppair); |
|
208 myassert(tmppos!=PosEnd); |
|
209 RemovePair(tmppair, tmppos); |
|
210 Mask[tmppos] = ByteTail; |
|
211 } |
|
212 posindex = PairPos[posindex].Next; |
|
213 } |
|
214 if (byteCount) { |
|
215 bytepos = ByteIndex[byte]; |
|
216 while(bytepos != PosEnd){ |
|
217 if (Mask[bytepos] == ByteRemoved) { |
|
218 bytepos = BytePos[bytepos]; |
|
219 continue; |
|
220 } |
|
221 GetPairBackward(dst2, bytepos, tmppos, tmppair); |
|
222 if ((tmppos != PosEnd) && (Mask[tmppos] == ByteHead)) { |
|
223 RemovePair(tmppair, tmppos); |
|
224 Mask[tmppos] = ByteTail; |
|
225 } |
|
226 if (Mask[bytepos] == ByteHead) { |
|
227 GetPairForward(dst2, bytepos, size, tmppos, tmppair); |
|
228 myassert(tmppos!=PosEnd); |
|
229 RemovePair(tmppair, tmppos); |
|
230 Mask[tmppos] = ByteTail; |
|
231 } |
|
232 bytepos = BytePos[bytepos]; |
|
233 } |
|
234 } |
|
235 |
|
236 // Update buffer |
|
237 posindex = PairBuffer[index].Pos; |
|
238 while (posindex != PosEnd){ |
|
239 headpos = PairPos[posindex].Pos; |
|
240 tailpos = (TUint16)(headpos + 1); |
|
241 while (Mask[tailpos] == ByteRemoved){ |
|
242 tailpos ++; |
|
243 myassert(tailpos < MaxBlockSize); |
|
244 } |
|
245 dst2[headpos] = (TUint8)byte; |
|
246 dst2[tailpos] = 0xff; |
|
247 Mask[headpos] = ByteNew; |
|
248 Mask[tailpos] = ByteRemoved; |
|
249 posindex = PairPos[posindex].Next; |
|
250 } |
|
251 if (byteCount) { |
|
252 bytepos = ByteIndex[byte]; |
|
253 while(bytepos != PosEnd) { |
|
254 Mask[bytepos] = ByteMarked; |
|
255 bytepos = BytePos[bytepos]; |
|
256 } |
|
257 } |
|
258 |
|
259 // Insert new pairs |
|
260 posindex = PairBuffer[index].Pos; |
|
261 TUint16 firstpos, lastpos; |
|
262 while (posindex != PosEnd){ |
|
263 firstpos = PairPos[posindex].Pos; |
|
264 lastpos = firstpos; |
|
265 if (Mask[firstpos] == ByteNew) { |
|
266 while ((firstpos > 0) && ((Mask[firstpos] == ByteNew) || (Mask[firstpos] == ByteRemoved))) |
|
267 firstpos --; |
|
268 while (Mask[firstpos] != ByteNew) |
|
269 firstpos ++; |
|
270 while ((lastpos < MaxBlockSize-1) && ((Mask[lastpos] == ByteNew)||(Mask[lastpos] == ByteRemoved))) |
|
271 lastpos ++; |
|
272 while (Mask[lastpos] != ByteNew) |
|
273 lastpos --; |
|
274 |
|
275 GetPairForward(dst2, lastpos, size, tmppos, tmppair); |
|
276 if (tmppos != PosEnd) { |
|
277 Mask[lastpos] = ByteHead; |
|
278 InsertPair(tmppair, tmppos); |
|
279 }else { |
|
280 Mask[lastpos] = ByteTail; |
|
281 } |
|
282 GetPairBackward(dst2, firstpos, tmppos, tmppair); |
|
283 if (tmppos != PosEnd) { |
|
284 Mask[tmppos] = ByteHead; |
|
285 InsertPair(tmppair, tmppos); |
|
286 } |
|
287 |
|
288 while (firstpos < lastpos) { |
|
289 tmppair = (TUint16)(dst2[firstpos] | dst2[firstpos]<<8); |
|
290 InsertPair(tmppair, firstpos); |
|
291 Mask[firstpos] = ByteHead; |
|
292 tmppos = (TUint16)(firstpos + 1); |
|
293 while (Mask[tmppos] == ByteRemoved) |
|
294 tmppos ++; |
|
295 myassert(tmppos <= lastpos); |
|
296 if (tmppos == lastpos) |
|
297 break; |
|
298 Mask[tmppos] = ByteTail; |
|
299 firstpos = (TUint16)(tmppos + 1); |
|
300 while ((firstpos < lastpos) && (Mask[firstpos] == ByteRemoved)) |
|
301 firstpos ++; |
|
302 } |
|
303 } |
|
304 posindex = PairPos[posindex].Next; |
|
305 } |
|
306 |
|
307 // Remove the pair from PairLists |
|
308 if (PairBuffer[index].Prev == PosHead){ |
|
309 if (PairBuffer[index].Next == PosEnd) { |
|
310 PairLists[count] = PosEnd; |
|
311 } else { |
|
312 PairLists[count] = PairBuffer[index].Next; |
|
313 PairBuffer[PairBuffer[index].Next].Prev = PosHead; |
|
314 } |
|
315 } else { |
|
316 if (PairBuffer[index].Next == PosEnd){ |
|
317 PairBuffer[PairBuffer[index].Prev].Next = PosEnd; |
|
318 } else { |
|
319 PairBuffer[PairBuffer[index].Prev].Next = PairBuffer[index].Next; |
|
320 PairBuffer[PairBuffer[index].Next].Prev = PairBuffer[index].Prev; |
|
321 } |
|
322 } |
|
323 while (PairLists[PairListHigh] == PosEnd) |
|
324 PairListHigh --; |
|
325 myassert(PairListHigh >= 1); |
|
326 PairBuffer[index].Next = PosEnd; |
|
327 PairBuffer[index].Prev = PosEnd; |
|
328 PairCount[pair].Count = 0; |
|
329 PairCount[pair].Index = PosEnd; |
|
330 |
|
331 //cout << "Pair: <" << pair << "> completed" << endl; |
|
332 //DumpList(dst2,size); |
|
333 //for (int i=0;i<100;i++) |
|
334 // cout << " "; |
|
335 //cout << endl; |
|
336 } |
|
337 |
|
338 // sort tokens with a bubble sort... |
|
339 for(TInt x=0; x<tokenCount-1; x++) |
|
340 for(TInt y=x+1; y<tokenCount; y++) |
|
341 if(tokens[x*3]>tokens[y*3]) |
|
342 { |
|
343 TInt z = tokens[x*3]; |
|
344 tokens[x*3] = tokens[y*3]; |
|
345 tokens[y*3] = (TUint8)z; |
|
346 z = tokens[x*3+1]; |
|
347 tokens[x*3+1] = tokens[y*3+1]; |
|
348 tokens[y*3+1] = (TUint8)z; |
|
349 z = tokens[x*3+2]; |
|
350 tokens[x*3+2] = tokens[y*3+2]; |
|
351 tokens[y*3+2] = (TUint8)z; |
|
352 } |
|
353 |
|
354 |
|
355 TUint8* originalDst = dst; |
|
356 |
|
357 *dst++ = (TUint8)tokenCount; |
|
358 TInt tmpTokenCount = tokenCount; |
|
359 if(tokenCount) |
|
360 { |
|
361 *dst++ = (TUint8)marker; |
|
362 if(tokenCount<32) |
|
363 { |
|
364 memcpy(dst,tokens,tokenCount*3); |
|
365 dst += tokenCount*3; |
|
366 } |
|
367 else |
|
368 { |
|
369 TUint8* bitMask = dst; |
|
370 memset(bitMask,0,32); |
|
371 dst += 32; |
|
372 TUint8* d=tokens; |
|
373 do |
|
374 { |
|
375 TInt t=*d++; |
|
376 bitMask[t>>3] |= (1<<(t&7)); |
|
377 *dst++ = *d++; |
|
378 *dst++ = *d++; |
|
379 } |
|
380 while(--tokenCount); |
|
381 } |
|
382 } |
|
383 |
|
384 if (tmpTokenCount == 0) { |
|
385 memcpy(dst,dst2,size); |
|
386 dst += size; |
|
387 } else { |
|
388 TUint16 pos = 0; |
|
389 for (TUint8 *p=dst2; p < dst2+size; p++, pos++) { |
|
390 if (Mask[pos] == ByteRemoved) |
|
391 continue; |
|
392 if (Mask[pos]== ByteMarked){ |
|
393 *dst++ = (TUint8)marker; |
|
394 } |
|
395 *dst++ = *p; |
|
396 } |
|
397 } |
|
398 |
|
399 ClockCompress += clock() - ClockStart; |
|
400 return (dst-originalDst); |
|
401 } |
|
402 |
|
403 |
|
404 TInt CBytePair::Decompress(TUint8* dst, TInt dstSize, TUint8* src, TInt srcSize, TUint8*& srcNext) |
|
405 { |
|
406 |
|
407 TUint8* dstStart = dst; |
|
408 TUint8* dstEnd = dst+dstSize; |
|
409 TUint8* srcEnd = src+srcSize; |
|
410 |
|
411 TUint32 LUT[0x100/2]; |
|
412 TUint8* LUT0 = (TUint8*)LUT; |
|
413 TUint8* LUT1 = LUT0+0x100; |
|
414 |
|
415 TUint8 stack[0x100]; |
|
416 TUint8* stackStart = stack+sizeof(stack); |
|
417 TUint8* sp = stackStart; |
|
418 |
|
419 TUint32 marker = ~0u; |
|
420 TInt numTokens; |
|
421 TUint32 p1; |
|
422 TUint32 p2; |
|
423 |
|
424 TUint32* l = (TUint32*)LUT; |
|
425 TUint32 b = 0x03020100; |
|
426 TUint32 step = 0x04040404; |
|
427 do |
|
428 { |
|
429 *l++ = b; |
|
430 b += step; |
|
431 } |
|
432 while(b>step); |
|
433 |
|
434 if(src>=srcEnd) |
|
435 goto error; |
|
436 numTokens = *src++; |
|
437 if(numTokens) |
|
438 { |
|
439 if(src>=srcEnd) |
|
440 goto error; |
|
441 marker = *src++; |
|
442 LUT0[marker] = (TUint8)~marker; |
|
443 |
|
444 if(numTokens<32) |
|
445 { |
|
446 TUint8* tokenEnd = src+3*numTokens; |
|
447 if(tokenEnd>srcEnd) |
|
448 goto error; |
|
449 do |
|
450 { |
|
451 TInt b = *src++; |
|
452 TInt p1 = *src++; |
|
453 TInt p2 = *src++; |
|
454 LUT0[b] = (TUint8)p1; |
|
455 LUT1[b] = (TUint8)p2; |
|
456 } |
|
457 while(src<tokenEnd); |
|
458 } |
|
459 else |
|
460 { |
|
461 TUint8* bitMask = src; |
|
462 src += 32; |
|
463 if(src>srcEnd) |
|
464 goto error; |
|
465 TInt b=0; |
|
466 do |
|
467 { |
|
468 TUint8 mask = bitMask[b>>3]; |
|
469 if(mask&(1<<(b&7))) |
|
470 { |
|
471 if(src>srcEnd) |
|
472 goto error; |
|
473 TInt p1 = *src++; |
|
474 if(src>srcEnd) |
|
475 goto error; |
|
476 TInt p2 = *src++; |
|
477 LUT0[b] = (TUint8)p1; |
|
478 LUT1[b] = (TUint8)p2; |
|
479 --numTokens; |
|
480 } |
|
481 ++b; |
|
482 } |
|
483 while(b<0x100); |
|
484 if(numTokens) |
|
485 goto error; |
|
486 } |
|
487 } |
|
488 |
|
489 if(src>=srcEnd) |
|
490 goto error; |
|
491 b = *src++; |
|
492 if(dst>=dstEnd) |
|
493 goto error; |
|
494 p1 = LUT0[b]; |
|
495 if(p1!=b) |
|
496 goto not_single; |
|
497 next: |
|
498 if(src>=srcEnd) |
|
499 goto done_s; |
|
500 b = *src++; |
|
501 *dst++ = (TUint8)p1; |
|
502 if(dst>=dstEnd) |
|
503 goto done_d; |
|
504 p1 = LUT0[b]; |
|
505 if(p1==b) |
|
506 goto next; |
|
507 |
|
508 not_single: |
|
509 if(b==marker) |
|
510 goto do_marker; |
|
511 |
|
512 do_pair: |
|
513 p2 = LUT1[b]; |
|
514 b = p1; |
|
515 p1 = LUT0[b]; |
|
516 if(sp<=stack) |
|
517 goto error; |
|
518 *--sp = (TUint8)p2; |
|
519 |
|
520 recurse: |
|
521 if(b!=p1) |
|
522 goto do_pair; |
|
523 |
|
524 if(sp==stackStart) |
|
525 goto next; |
|
526 b = *sp++; |
|
527 if(dst>=dstEnd) |
|
528 goto error; |
|
529 *dst++ = (TUint8)p1; |
|
530 p1 = LUT0[b]; |
|
531 goto recurse; |
|
532 |
|
533 do_marker: |
|
534 if(src>=srcEnd) |
|
535 goto error; |
|
536 p1 = *src++; |
|
537 goto next; |
|
538 |
|
539 error: |
|
540 srcNext = 0; |
|
541 return KErrCorrupt; |
|
542 |
|
543 done_s: |
|
544 *dst++ = (TUint8)p1; |
|
545 srcNext = src; |
|
546 return dst-dstStart; |
|
547 |
|
548 done_d: |
|
549 if(dst>=dstEnd) |
|
550 --src; |
|
551 srcNext = src; |
|
552 return dst-dstStart; |
|
553 } |
|
554 |
|
555 |
|
556 TInt BytePairCompress(TUint8* dst, TUint8* src, TInt size, CBytePair *aBPE) |
|
557 { |
|
558 TUint8 PakBuffer[MaxBlockSize*4]; |
|
559 TUint8 UnpakBuffer[MaxBlockSize]; |
|
560 ASSERT(size<=MaxBlockSize); |
|
561 TInt compressedSize = aBPE->Compress(PakBuffer,src,size); |
|
562 TUint8* pakEnd; |
|
563 TInt us = aBPE->Decompress(UnpakBuffer,MaxBlockSize,PakBuffer,compressedSize,pakEnd); |
|
564 ASSERT(us==size) |
|
565 ASSERT(pakEnd==PakBuffer+compressedSize) |
|
566 ASSERT(!memcmp(src,UnpakBuffer,size)) |
|
567 if(compressedSize>=size) |
|
568 return KErrTooBig; |
|
569 memcpy(dst,PakBuffer,compressedSize); |
|
570 return compressedSize; |
|
571 } |