35 cout <<"myassertion failed" << endl; |
35 cout <<"myassertion failed" << endl; |
36 } |
36 } |
37 } |
37 } |
38 #endif |
38 #endif |
39 |
39 |
|
40 void CBytePair::SortN(TUint16 *a, TInt n) |
|
41 { |
|
42 //bubble sort |
|
43 TInt i,j; |
|
44 TUint16 tmp; |
|
45 for (i=0;i<n-1;i++){ |
|
46 for (j=i+1;j<=n-1;j++){ |
|
47 if (a[j]<a[i]) { |
|
48 tmp = a[j]; |
|
49 a[j]=a[i]; |
|
50 a[i]=tmp; |
|
51 } |
|
52 } |
|
53 } |
|
54 } |
|
55 void CBytePair::InsertN(TUint16 *a, TInt n, TUint16 v) |
|
56 { |
|
57 TInt i; |
|
58 for (i=n-1;i>=0;i--){ |
|
59 if (a[i] > v) |
|
60 a[i+1]=a[i]; |
|
61 else{ |
|
62 break; |
|
63 } |
|
64 } |
|
65 a[i+1] = v; |
|
66 } |
|
67 |
|
68 |
|
69 TInt CBytePair::PosN(TUint16 index, TInt n){ |
|
70 myassert(n<=PairCount[PairBuffer[index].Pair].Count); |
|
71 TUint16 FirstN[1+3+0x1000/256+1]; |
|
72 TInt i = 0; |
|
73 TUint16 posindex; |
|
74 posindex = PairBuffer[index].Pos; |
|
75 |
|
76 while (i<n) { |
|
77 FirstN[i] = PairPos[posindex].Pos; |
|
78 posindex = PairPos[posindex].Next; |
|
79 i++; |
|
80 } |
|
81 SortN(FirstN, n); |
|
82 while (posindex!=PosEnd){ |
|
83 InsertN(FirstN, n, PairPos[posindex].Pos); |
|
84 posindex=PairPos[posindex].Next; |
|
85 } |
|
86 return FirstN[n-1]; |
|
87 } |
|
88 |
40 void CBytePair::Initialize(TUint8* data, TInt size) |
89 void CBytePair::Initialize(TUint8* data, TInt size) |
41 { |
90 { |
42 TUint32 *p; |
91 #if defined(WIN32) |
43 p = (TUint32*)PairCount; |
92 TUint32 *p = reinterpret_cast<TUint32*>(PairCount); |
44 while(p < (TUint32*)PairCount+0x10000) { |
93 TUint32 *end = p + 0x10000; |
45 *p = 0xffff0000; |
94 while(p < end) { |
46 p ++; |
95 *p++ = 0xffff0000; |
47 } |
96 } |
48 p = (TUint32*)PairBuffer; |
97 #else |
49 while (p < (TUint32*)PairBuffer + sizeof(PairBuffer) / 4) { |
98 for(int i = 0 ; i < 0x10000 ; i ++){ |
50 *p = 0xffffffff; |
99 PairCount[i].Count = 0 ; |
51 p++; |
100 PairCount[i].Index = 0xffff; |
52 } |
101 } |
|
102 #endif |
|
103 memset(reinterpret_cast<char*>(PairBuffer),0xff, sizeof(PairBuffer)); |
53 PairBufferNext = 0; |
104 PairBufferNext = 0; |
54 p = (TUint32*)PairPos; |
105 memset(reinterpret_cast<char*>(PairPos),0xff, sizeof(PairPos)); |
55 while (p < (TUint32*)PairPos + sizeof(PairPos) /4 ) { |
|
56 *p = 0xffffffff; |
|
57 p ++; |
|
58 } |
|
59 PairPosNext = 0; |
106 PairPosNext = 0; |
60 p = (TUint32*)PairLists; |
107 memset(reinterpret_cast<char*>(PairLists),0xff, sizeof(PairLists)); |
61 while (p < (TUint32*)PairLists + sizeof(PairLists) / 4) { |
|
62 *p = 0xffffffff; |
|
63 p ++; |
|
64 } |
|
65 PairListHigh = 0; |
108 PairListHigh = 0; |
66 |
109 |
67 CountBytes(data,size); |
110 CountBytes(data,size); |
68 marker = -1; |
111 marker = -1; |
69 LeastCommonByte(marker); |
112 markerCount = LeastCommonByte(marker); |
70 ByteUsed(marker); |
113 ByteUsed(marker); |
71 |
114 |
72 TUint8 *pData, *pMask; |
115 TUint8 *pData, *pMask; |
73 TUint16 pair; |
116 TUint16 pair; |
74 pData=data, pMask=Mask; |
117 pData=data, pMask=Mask; |
103 *pMask = ByteMarked; |
146 *pMask = ByteMarked; |
104 else |
147 else |
105 *pMask = ByteTail; |
148 *pMask = ByteTail; |
106 } |
149 } |
107 |
150 |
108 TInt CBytePair::MostCommonPair(TInt& pair) |
151 TInt CBytePair::MostCommonPair(TInt& pair, TInt minFrequency) |
109 { |
152 { |
110 TUint16 index = PairLists[PairListHigh]; |
153 TUint16 index = PairLists[PairListHigh]; |
111 TUint16 tmpindex = index; |
154 TUint16 tmpindex = index; |
112 TUint16 p = PairBuffer[index].Pair; |
155 TUint16 p = PairBuffer[index].Pair; |
113 TInt tieBreak, bestTieBreak; |
156 TInt tieBreak, bestTieBreak; |
148 TInt CBytePair::Compress(TUint8* dst, TUint8* src, TInt size) |
198 TInt CBytePair::Compress(TUint8* dst, TUint8* src, TInt size) |
149 { |
199 { |
150 clock_t ClockStart = clock(); |
200 clock_t ClockStart = clock(); |
151 TUint8 tokens[0x100*3]; |
201 TUint8 tokens[0x100*3]; |
152 TInt tokenCount = 0; |
202 TInt tokenCount = 0; |
153 TInt overhead; |
|
154 |
203 |
155 TUint8 * dst2 = dst + size*2; |
204 TUint8 * dst2 = dst + size*2; |
156 memcpy (dst2, src, size); |
205 memcpy (dst2, src, size); |
157 Initialize (dst2, size); |
206 Initialize (dst2, size); |
158 //DumpList(dst2, size); |
207 TInt overhead = 1+3+markerCount; |
159 for(TInt r=256; r>0; --r) |
208 for(TInt r=256; r>0; --r) |
160 { |
209 { |
161 TInt byte; |
210 TInt byte; |
162 TInt byteCount = LeastCommonByte(byte); |
211 TInt byteCount = LeastCommonByte(byte); |
163 if (iFastCompress && byteCount) break; |
|
164 //if(byteCount) break; |
|
165 TInt pair; |
212 TInt pair; |
166 TInt pairCount = MostCommonPair(pair); |
213 TInt pairCount = MostCommonPair(pair, overhead+1); |
167 TInt saving = pairCount-byteCount; |
214 TInt saving = pairCount-byteCount; |
168 |
215 if(saving<=overhead) |
169 //cout << "byte: <" << hex << setw(2) << setfill('0') << byte << ">" << byteCount << endl; |
216 break; |
170 //cout << "pair: <" << hex << setw(4) << setfill('0') << pair << ">" << pairCount << endl; |
217 |
171 overhead = 3; |
218 overhead = 3; |
172 if(tokenCount>=32) |
219 if(tokenCount>=32) |
173 overhead = 2; |
220 overhead = 2; |
174 if(saving<=overhead) |
|
175 break; |
|
176 |
221 |
177 TUint8* d=tokens+3*tokenCount; |
222 TUint8* d=tokens+3*tokenCount; |
178 ++tokenCount; |
223 ++tokenCount; |
179 *d++ = (TUint8)byte; |
224 *d++ = (TUint8)byte; |
180 ByteUsed(byte); |
225 ByteUsed(byte); |
181 *d++ = (TUint8)pair; |
226 *d++ = (TUint8)pair; |
182 ByteUsed(pair&0xff); |
227 ByteUsed(pair&0xff); |
183 *d++ = (TUint8)(pair>>8); |
228 *d++ = (TUint8)(pair>>8); |
184 ByteUsed(pair>>8); |
229 ByteUsed(pair>>8); |
185 //++GlobalPairs[pair]; |
230 |
186 |
|
187 //clock_t ClockReplace1 ,ClockReplace2; |
|
188 TUint16 index = PairCount[pair].Index; |
231 TUint16 index = PairCount[pair].Index; |
189 TUint16 count = PairCount[pair].Count; |
232 TUint16 count = PairCount[pair].Count; |
190 TUint16 posindex = PairBuffer[index].Pos; |
233 TUint16 posindex = PairBuffer[index].Pos; |
191 TUint16 headpos, tailpos, tmppos, bytepos; |
234 TUint16 headpos, tailpos, tmppos, tmpposprev, bytepos; |
192 TUint16 tmppair; |
235 TUint16 tmppair; |
193 // Remove pairs |
236 // Remove pairs |
194 while (posindex != PosEnd) { |
237 while (posindex != PosEnd) { |
195 headpos = PairPos[posindex].Pos; |
238 headpos = PairPos[posindex].Pos; |
196 tailpos = (TUint16)(headpos + 1); |
239 tailpos = (TUint16)(headpos + 1); |
274 |
317 |
275 GetPairForward(dst2, lastpos, size, tmppos, tmppair); |
318 GetPairForward(dst2, lastpos, size, tmppos, tmppair); |
276 if (tmppos != PosEnd) { |
319 if (tmppos != PosEnd) { |
277 Mask[lastpos] = ByteHead; |
320 Mask[lastpos] = ByteHead; |
278 InsertPair(tmppair, tmppos); |
321 InsertPair(tmppair, tmppos); |
|
322 // Potential new pair after the new one |
|
323 tmppos = (TUint16)(lastpos+1); |
|
324 while(Mask[tmppos]==ByteRemoved) |
|
325 tmppos ++; |
|
326 if (Mask[tmppos]==ByteTail){ |
|
327 tmpposprev = tmppos; |
|
328 tmppos ++; |
|
329 while (tmppos<size){ |
|
330 if (Mask[tmppos]==ByteRemoved){ |
|
331 tmppos++; |
|
332 continue; |
|
333 } |
|
334 if (Mask[tmppos]==ByteMarked) |
|
335 break; |
|
336 if (dst2[tmppos]!=dst2[tmpposprev]) |
|
337 break; |
|
338 if (Mask[tmpposprev]==ByteTail){ |
|
339 //myassert(Mask[tmppos]==ByteHead); |
|
340 InsertPair((TUint16)(dst2[tmppos]|dst2[tmppos]<<8), tmpposprev); |
|
341 Mask[tmpposprev]=ByteHead; |
|
342 }else{ |
|
343 myassert(Mask[tmpposprev]==ByteHead); |
|
344 RemovePair((TUint16)(dst2[tmppos]|dst2[tmppos]<<8), tmpposprev); |
|
345 Mask[tmpposprev]=ByteTail; |
|
346 } |
|
347 tmpposprev = tmppos; |
|
348 tmppos ++; |
|
349 } |
|
350 } |
279 }else { |
351 }else { |
280 Mask[lastpos] = ByteTail; |
352 Mask[lastpos] = ByteTail; |
281 } |
353 } |
282 GetPairBackward(dst2, firstpos, tmppos, tmppair); |
354 GetPairBackward(dst2, firstpos, tmppos, tmppair); |
283 if (tmppos != PosEnd) { |
355 if (tmppos != PosEnd) { |
326 PairBuffer[index].Next = PosEnd; |
398 PairBuffer[index].Next = PosEnd; |
327 PairBuffer[index].Prev = PosEnd; |
399 PairBuffer[index].Prev = PosEnd; |
328 PairCount[pair].Count = 0; |
400 PairCount[pair].Count = 0; |
329 PairCount[pair].Index = PosEnd; |
401 PairCount[pair].Index = PosEnd; |
330 |
402 |
331 //cout << "Pair: <" << pair << "> completed" << endl; |
|
332 //DumpList(dst2,size); |
|
333 //for (int i=0;i<100;i++) |
|
334 // cout << " "; |
|
335 //cout << endl; |
|
336 } |
403 } |
337 |
404 |
338 // sort tokens with a bubble sort... |
405 // sort tokens with a bubble sort... |
339 for(TInt x=0; x<tokenCount-1; x++) |
406 for(TInt x=0; x<tokenCount-1; x++) |
340 for(TInt y=x+1; y<tokenCount; y++) |
407 for(TInt y=x+1; y<tokenCount; y++) |