• R/O
  • SSH
  • HTTPS

jyeipegyuu: Commit


Commit MetaInfo

Révision8 (tree)
l'heure2009-09-04 02:46:23
Auteurberupon

Message de Log

ちょっとだけ圧縮率向上

Change Summary

Modification

--- misc.h (revision 7)
+++ misc.h (revision 8)
@@ -126,7 +126,7 @@
126126 return ret;
127127 }
128128
129- size_t nBytes() const { return src_ - initialSrc_; }
129+ size_t nBytes() const { return (src_ - initialSrc_) + (counter_ ? 1 : 0); }
130130
131131 private:
132132 unsigned char counter_;
@@ -174,16 +174,85 @@
174174 size_t shift_;
175175 };
176176
177+class ModifiedUnaryCoder
178+{
179+public:
180+ ModifiedUnaryCoder(size_t repeat)
181+ :
182+ repeat_(repeat)
183+ {
184+ }
185+
186+ template <typename T>
187+ size_t Encode(const T* values, BitWriter& writer)
188+ {
189+ size_t value = *values;
190+ size_t count = 0;
191+ for (; count<repeat_; ++count) {
192+ if (values[count] != 0) {
193+ break;
194+ }
195+ }
196+ if (count == repeat_ && values[repeat_] == 1) {
197+ writer.putBit(false);
198+ writer.putBit(false);
199+ writer.putBit(true);
200+ return repeat_+1;
201+ }else if (value == 0) {
202+ writer.putBit(true);
203+ return 1;
204+ }else if (value == 1) {
205+ writer.putBit(false);
206+ writer.putBit(true);
207+ return 1;
208+ }else {
209+ size_t value = *values;
210+ for (size_t i=0; i<value+1; ++i) {
211+ writer.putBit(false);
212+ }
213+ writer.putBit(true);
214+ return 1;
215+ }
216+ }
217+
218+ size_t Decode(BitReader& reader)
219+ {
220+ return 0;
221+ }
222+
223+private:
224+ size_t repeat_;
225+};
226+
227+
177228 enum RiceCoderFlag {
178229 None = 0xF,
179230 };
180231
232+template <typename T>
233+size_t modifiedUnaryEncode(
234+ const T* src, size_t srcLen,
235+ unsigned char* tmp
236+ )
237+{
238+ BitWriter writer(tmp);
239+ ModifiedUnaryCoder uc(7);
240+ size_t i=0;
241+ size_t pc = 0;
242+ while (i<srcLen) {
243+ size_t progress = uc.Encode(src+i, writer);
244+ if (progress != 1) ++pc;
245+ i += progress;
246+ }
247+ return writer.nBytes();
248+}
249+
181250 size_t repeationCompress(
182251 const unsigned char* src, size_t srcLen,
183252 unsigned char* tmp
184253 )
185254 {
186- int repeatHist[1024] = {0};
255+ int repeatHist[1024*4] = {0};
187256 int repeat = 0;
188257
189258 BitWriter bitWriter(tmp);
@@ -229,9 +298,46 @@
229298 return bitWriter.nBytes();
230299 }
231300
301+void findZeroOneInfos(
302+ size_t hBlockCount,
303+ size_t vBlockCount,
304+ const int* src,
305+ unsigned char* dst,
306+ size_t limit
307+ )
308+{
309+ const int totalBlockCount = static_cast<int>(hBlockCount * vBlockCount);
310+ const int* from = src;
311+
312+ // pass DC0
313+ from += totalBlockCount;
314+
315+ std::fill(dst, dst+totalBlockCount, 255);
316+
317+ for (size_t i=1; i<8; ++i) {
318+ unsigned char blockSize = 1 + i*2;
319+ if (i<limit) {
320+ from += blockSize * totalBlockCount;
321+ continue;
322+ }
323+ for (size_t j=0; j<totalBlockCount; ++j) {
324+ for (size_t k=0; k<blockSize; ++k) {
325+ int v = abs(from[k]);
326+ if (v > 1) {
327+ dst[j] = 0;
328+ break;
329+ }
330+ }
331+ from += blockSize;
332+ }
333+ }
334+}
335+
232336 size_t compressSub(
233337 ICompressor& compressor,
234- int* src, size_t srcLen,
338+ int* src,
339+ const unsigned char* pZeroOneInfos,
340+ size_t blockCount, size_t blockSize,
235341 unsigned char* dest, size_t destLen,
236342 unsigned char* tmp,
237343 unsigned char* tmp2
@@ -238,6 +344,7 @@
238344 )
239345 {
240346 unsigned char* initialDest = dest;
347+ size_t srcLen = blockCount * blockSize;
241348
242349 assert(destLen > 4);
243350
@@ -245,6 +352,8 @@
245352 int maxi = boost::integer_traits<int>::const_min;
246353
247354 int hists[1024] = {0};
355+ int zeroRepeat = 0;
356+ int zeroRepeatHist[1024*4] = {0};
248357 BitWriter signFlags(dest+4);
249358 for (size_t i=0; i<srcLen; ++i) {
250359 int val = src[i];
@@ -251,11 +360,11 @@
251360 mini = std::min(val, mini);
252361 maxi = std::max(val, maxi);
253362 if (val == 0) {
254- ;
255- }else if (val < 0) {
256- signFlags.putBit(false);
363+ ++zeroRepeat;
257364 }else {
258- signFlags.putBit(true);
365+ signFlags.putBit(val > 0);
366+ ++zeroRepeatHist[zeroRepeat];
367+ zeroRepeat = 0;
259368 }
260369 val = std::abs(val);
261370 src[i] = val;
@@ -262,7 +371,12 @@
262371
263372 ++hists[val];
264373 }
374+ if (zeroRepeat) {
375+ ++zeroRepeatHist[zeroRepeat];
376+ zeroRepeat = 0;
377+ }
265378
379+
266380 uint32_t signFlagBytes = signFlags.nBytes();
267381 *((size_t*)dest) = signFlagBytes;
268382
@@ -282,9 +396,9 @@
282396 b = 4;
283397 }else if (max > 128+64) {
284398 b = 3;
285- }else if (max > 128) {
399+ }else if (max > 96) {
286400 b = 2;
287- }else if (max > 64) {
401+ }else if (max > 32) {
288402 b = 1;
289403 }else {
290404 b = 0;
@@ -294,12 +408,35 @@
294408
295409 BitWriter bitWriter(tmp2);
296410 RiceCoder riceCoder(b);
297- for (size_t i=0; i<srcLen; ++i) {
298- riceCoder.Encode(src[i], bitWriter);
411+
412+ int* from = src;
413+ if (pZeroOneInfos) {
414+ for (size_t i=0; i<blockCount; ++i) {
415+ if (pZeroOneInfos[i]) {
416+ for (size_t j=0; j<blockSize; ++j) {
417+ bitWriter.putBit(src[i*blockSize+j] == 0);
418+ }
419+ }
420+ }
421+ for (size_t i=0; i<blockCount; ++i) {
422+ if (!pZeroOneInfos[i]) {
423+ for (size_t j=0; j<blockSize; ++j) {
424+ riceCoder.Encode(src[i*blockSize+j], bitWriter);
425+ }
426+ }
427+ }
428+ }else {
429+ for (size_t i=0; i<blockCount; ++i) {
430+ for (size_t j=0; j<blockSize; ++j) {
431+ riceCoder.Encode(*from++, bitWriter);
432+ }
433+ }
299434 }
300435 size_t bytesLen = bitWriter.nBytes();
301436
302437 size_t compressedLen = 0;
438+
439+ size_t modifiedUnaryEncodedLen = modifiedUnaryEncode(src, srcLen, dest);
303440
304441 compressedLen = compressor.Compress(tmp2, bytesLen, dest+6, -1);
305442 unsigned char* dest2 = (compressedLen < initialCompressedLen) ? tmp : (dest+6);
@@ -343,8 +480,10 @@
343480 ICompressor& compressor,
344481 size_t hBlockCount,
345482 size_t vBlockCount,
346- const int* src,
347- int* tmp,
483+ const unsigned char* pZeroOneInfos,
484+ size_t zeroOneLimit,
485+ int* src,
486+ unsigned char* tmp1,
348487 unsigned char* tmp2,
349488 unsigned char* tmp3,
350489 unsigned char* dest, size_t destLen
@@ -351,26 +490,16 @@
351490 )
352491 {
353492 const int totalBlockCount = static_cast<int>(hBlockCount * vBlockCount);
354- const size_t fromWidth = hBlockCount * 8;
355- const size_t fromWidth8 = fromWidth * 8;
493+
494+ int* from = src;
495+
496+ size_t progress = 0;
356497
357- const int* from = src;
358- int* to = tmp;
359-
360- int readPos;
361- // DC0
362- readPos = 0;
363- for (size_t y=0; y<vBlockCount; ++y) {
364- int fromPos = readPos;
365- for (size_t x=0; x<hBlockCount; ++x) {
366- *to++ = from[fromPos];
367- fromPos += 8;
368- }
369- readPos += fromWidth8;
370- }
498+ // DC
371499
372- // paeth prediction to DC0
373- to -= totalBlockCount;
500+ // paeth prediction
501+ int* to = (int*) tmp3;
502+ std::copy(from, from+totalBlockCount, to);
374503 // first row
375504 int left = *to;
376505 int above = 0;
@@ -391,7 +520,7 @@
391520 left = cur;
392521 upperLeft = above;
393522 ++to;
394- int fromPos = fromLineOffset + 8;
523+ int fromPos = fromLineOffset + 1;
395524 for (size_t x=1; x<hBlockCount; ++x) {
396525 above = from[fromPos];
397526 cur = *to;
@@ -399,15 +528,141 @@
399528 ++to;
400529 left = cur;
401530 upperLeft = above;
402- fromPos += 8;
531+ ++fromPos;
403532 }
404- fromLineOffset += fromWidth8;
533+ fromLineOffset += hBlockCount;
405534 }
535+
536+ to -= totalBlockCount;
537+ progress += compressSub(compressor, to, 0, totalBlockCount, 1, dest+progress, destLen-progress, tmp1, tmp2);
538+ from += totalBlockCount;
539+
540+ // zero one flags
541+ BitWriter bw(dest+progress);
542+ for (size_t i=0; i<totalBlockCount; ++i) {
543+ bw.putBit(pZeroOneInfos[i]);
544+ }
545+ progress += bw.nBytes();
546+
547+ // AC
548+ for (size_t i=1; i<8; ++i) {
549+ const unsigned char* p01 = (i < zeroOneLimit) ? 0 : pZeroOneInfos;
550+ size_t blockSize = 1 + i * 2;
551+ progress += compressSub(compressor, from, p01, totalBlockCount, blockSize, dest+progress, destLen-progress, tmp1, tmp2);
552+ from += totalBlockCount * blockSize;
553+ }
554+
555+ return progress;
556+}
406557
407- size_t progress = 0;
408- progress += compressSub(compressor, tmp, totalBlockCount, dest+progress, destLen-progress, tmp2, tmp3);
409- to = tmp;
558+size_t decompressSub(
559+ ICompressor& compressor,
560+ const unsigned char* src,
561+ const unsigned char* pZeroOneInfos,
562+ unsigned char* tmp,
563+ int* dest,
564+ size_t totalBlockCount,
565+ size_t blockSize)
566+{
567+ size_t destLen = totalBlockCount * blockSize;
410568
569+ const unsigned char* initialSrc = src;
570+
571+ size_t signFlagBytes = *(size_t*)src;
572+ src += 4;
573+ BitReader signFlags(src);
574+ src += signFlagBytes;
575+
576+ unsigned char compressFlag = *src++;
577+ unsigned char b = *src++;
578+ size_t len = *(size_t*)src;
579+ src += 4;
580+
581+ size_t len2 = 0;
582+ switch (compressFlag) {
583+ case 0:
584+ memcpy(tmp, src, len);
585+ len2 = len;
586+ break;
587+ case 1:
588+ len2 = compressor.Decompress(src, len, tmp, -1);
589+ break;
590+ case 2:
591+ len2 = repeationDecompress(src, len, tmp);
592+ break;
593+ }
594+
595+ if (b == RiceCoderFlag::None) {
596+ memcpy(dest, tmp, len2);
597+ for (size_t i=0; i<len2/4; ++i) {
598+ int val = dest[i];
599+ if (val != 0) {
600+ if (!signFlags.getBit()) {
601+ dest[i] = -val;
602+ }
603+ }
604+ }
605+
606+ }else {
607+ RiceCoder riceCoder(b);
608+ BitReader bitReader(tmp);
609+ if (pZeroOneInfos) {
610+ for (size_t i=0; i<totalBlockCount; ++i) {
611+ if (pZeroOneInfos[i]) {
612+ for (size_t j=0; j<blockSize; ++j) {
613+ dest[i*blockSize+j] = bitReader.getBit() ? 0 : 1;
614+ }
615+ }
616+ }
617+ for (size_t i=0; i<totalBlockCount; ++i) {
618+ if (!pZeroOneInfos[i]) {
619+ for (size_t j=0; j<blockSize; ++j) {
620+ dest[i*blockSize+j] = riceCoder.Decode(bitReader);
621+ }
622+ }
623+ }
624+ }else {
625+ for (size_t i=0; i<destLen; ++i) {
626+ dest[i] = riceCoder.Decode(bitReader);
627+ }
628+ }
629+ for (size_t i=0; i<destLen; ++i) {
630+ int val = dest[i];
631+ if (val != 0 && !signFlags.getBit()) {
632+ dest[i] = -val;
633+ }
634+ }
635+ }
636+// showMinus(dest, dest, destLen);
637+
638+ return 4 + signFlagBytes + + 6 + len;
639+}
640+
641+void reorderByFrequency(
642+ size_t hBlockCount,
643+ size_t vBlockCount,
644+ const int* src,
645+ int* dst
646+ )
647+{
648+ const size_t fromWidth = hBlockCount * 8;
649+ const size_t fromWidth8 = fromWidth * 8;
650+
651+ int readPos;
652+ const int* from = src;
653+ int* to = dst;
654+
655+ // DC0
656+ readPos = 0;
657+ for (size_t y=0; y<vBlockCount; ++y) {
658+ int fromPos = readPos;
659+ for (size_t x=0; x<hBlockCount; ++x) {
660+ *to++ = from[fromPos];
661+ fromPos += 8;
662+ }
663+ readPos += fromWidth8;
664+ }
665+
411666 // AC1
412667 readPos = 0;
413668 for (size_t y=0; y<vBlockCount; ++y) {
@@ -420,9 +675,7 @@
420675 }
421676 readPos += fromWidth8;
422677 }
423- progress += compressSub(compressor, tmp, totalBlockCount*3, dest+progress, destLen-progress, tmp2, tmp3);
424- to = tmp;
425-
678+
426679 // AC2
427680 readPos = 0;
428681 for (size_t y=0; y<vBlockCount; ++y) {
@@ -437,8 +690,6 @@
437690 }
438691 readPos += fromWidth8;
439692 }
440- progress += compressSub(compressor, tmp, totalBlockCount*5, dest+progress, destLen-progress, tmp2, tmp3);
441- to = tmp;
442693
443694 // AC3
444695 readPos = 0;
@@ -456,9 +707,7 @@
456707 }
457708 readPos += fromWidth8;
458709 }
459- progress += compressSub(compressor, tmp, totalBlockCount*7, dest+progress, destLen-progress, tmp2, tmp3);
460- to = tmp;
461-
710+
462711 // AC4
463712 readPos = 0;
464713 for (size_t y=0; y<vBlockCount; ++y) {
@@ -477,9 +726,8 @@
477726 }
478727 readPos += fromWidth8;
479728 }
480- progress += compressSub(compressor, tmp, totalBlockCount*9, dest+progress, destLen-progress, tmp2, tmp3);
481- to = tmp;
482-
729+
730+
483731 // AC5
484732 readPos = 0;
485733 for (size_t y=0; y<vBlockCount; ++y) {
@@ -500,9 +748,7 @@
500748 }
501749 readPos += fromWidth8;
502750 }
503- progress += compressSub(compressor, tmp, totalBlockCount*11, dest+progress, destLen-progress, tmp2, tmp3);
504- to = tmp;
505-
751+
506752 // AC6
507753 readPos = 0;
508754 for (size_t y=0; y<vBlockCount; ++y) {
@@ -525,9 +771,7 @@
525771 }
526772 readPos += fromWidth8;
527773 }
528- progress += compressSub(compressor, tmp, totalBlockCount*13, dest+progress, destLen-progress, tmp2, tmp3);
529- to = tmp;
530-
774+
531775 // AC7
532776 readPos = 0;
533777 for (size_t y=0; y<vBlockCount; ++y) {
@@ -552,68 +796,10 @@
552796 }
553797 readPos += fromWidth8;
554798 }
555- progress += compressSub(compressor, tmp, totalBlockCount*15, dest+progress, destLen-progress, tmp2, tmp3);
556799
557- return progress;
558800 }
559801
560-size_t decompressSub(ICompressor& compressor, const unsigned char* src, unsigned char* tmp, int* dest, size_t destLen)
561-{
562- const unsigned char* initialSrc = src;
563-
564- size_t signFlagBytes = *(size_t*)src;
565- src += 4;
566- BitReader signFlags(src);
567- src += signFlagBytes;
568-
569- unsigned char compressFlag = *src++;
570- unsigned char b = *src++;
571- size_t len = *(size_t*)src;
572- src += 4;
573-
574- size_t len2 = 0;
575- switch (compressFlag) {
576- case 0:
577- memcpy(tmp, src, len);
578- len2 = len;
579- break;
580- case 1:
581- len2 = compressor.Decompress(src, len, tmp, -1);
582- break;
583- case 2:
584- len2 = repeationDecompress(src, len, tmp);
585- break;
586- }
587-
588- if (b == RiceCoderFlag::None) {
589- memcpy(dest, tmp, len2);
590- for (size_t i=0; i<len2/4; ++i) {
591- int val = dest[i];
592- if (val != 0) {
593- if (!signFlags.getBit()) {
594- dest[i] = -val;
595- }
596- }
597- }
598802
599- }else {
600- RiceCoder riceCoder(b);
601- BitReader bitReader(tmp);
602- for (size_t i=0; i<destLen; ++i) {
603- int val = riceCoder.Decode(bitReader);
604- if (val != 0) {
605- if (!signFlags.getBit()) {
606- val = -val;
607- }
608- }
609- dest[i] = val;
610- }
611- }
612-// showMinus(dest, dest, destLen);
613-
614- return 4 + signFlagBytes + + 6 + len;
615-}
616-
617803 void decompress(
618804 ICompressor& decompressor,
619805 size_t hBlockCount,
@@ -635,7 +821,7 @@
635821
636822 int writePos;
637823
638- src += decompressSub(decompressor, src, tmp, from, totalBlockCount);
824+ src += decompressSub(decompressor, src, 0, tmp, from, totalBlockCount, 1);
639825 // DC0
640826 writePos = 0;
641827 for (size_t y=0; y<vBlockCount; ++y) {
@@ -686,7 +872,16 @@
686872 toLineOffset += toWidth8;
687873 }
688874
689- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*3);
875+ // zero one flags
876+ BitReader reader(src);
877+ std::vector<unsigned char> zeroOneFlags(totalBlockCount);
878+ unsigned char* pZeroOneFlags = &zeroOneFlags[0];
879+ for (size_t i=0; i<totalBlockCount; ++i) {
880+ zeroOneFlags[i] = reader.getBit();
881+ }
882+ src += reader.nBytes();
883+
884+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 3);
690885 // AC1
691886 writePos = 0;
692887 for (size_t y=0; y<vBlockCount; ++y) {
@@ -701,7 +896,7 @@
701896 writePos += toWidth8;
702897 }
703898
704- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*5);
899+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 5);
705900 // AC2
706901 writePos = 0;
707902 for (size_t y=0; y<vBlockCount; ++y) {
@@ -717,7 +912,7 @@
717912 writePos += toWidth8;
718913 }
719914
720- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*7);
915+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 7);
721916 // AC3
722917 writePos = 0;
723918 for (size_t y=0; y<vBlockCount; ++y) {
@@ -735,7 +930,7 @@
735930 writePos += toWidth8;
736931 }
737932
738- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*9);
933+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 9);
739934 // AC4
740935 writePos = 0;
741936 for (size_t y=0; y<vBlockCount; ++y) {
@@ -755,7 +950,7 @@
755950 writePos += toWidth8;
756951 }
757952
758- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*11);
953+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 11);
759954 // AC5
760955 writePos = 0;
761956 for (size_t y=0; y<vBlockCount; ++y) {
@@ -777,7 +972,7 @@
777972 writePos += toWidth8;
778973 }
779974
780- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*13);
975+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 13);
781976 // AC6
782977 writePos = 0;
783978 for (size_t y=0; y<vBlockCount; ++y) {
@@ -801,7 +996,7 @@
801996 writePos += toWidth8;
802997 }
803998
804- src += decompressSub(decompressor, src, tmp, from, totalBlockCount*15);
999+ src += decompressSub(decompressor, src, pZeroOneFlags, tmp, from, totalBlockCount, 15);
8051000 // AC7
8061001 writePos = 0;
8071002 for (size_t y=0; y<vBlockCount; ++y) {
--- main.cpp (revision 7)
+++ main.cpp (revision 8)
@@ -86,6 +86,13 @@
8686
8787 int* pWork = &work[0];
8888
89+ reorderByFrequency(hBlockCount, vBlockCount, &work[0], &work2[0]);
90+
91+ std::vector<unsigned char> zeroOneInfos(totalBlockCount);
92+ unsigned char* pZeroOneInfos = &zeroOneInfos[0];
93+ size_t zeroOneLimit = 1;
94+ findZeroOneInfos(hBlockCount, vBlockCount, &work2[0], &zeroOneInfos[0], zeroOneLimit);
95+
8996 BZip2Compressor compressor;
9097 size_t compressedLen = 0;
9198
@@ -93,7 +100,7 @@
93100 std::vector<unsigned char> work3(storageSize);
94101 std::vector<unsigned char> work4(storageSize);
95102 std::vector<unsigned char> compressed(storageSize);
96- compressedLen = compress(compressor, hBlockCount, vBlockCount, &work[0], &work2[0], &work3[0], &work4[0], &compressed[0], compressed.size());
103+ compressedLen = compress(compressor, hBlockCount, vBlockCount, pZeroOneInfos, zeroOneLimit, &work2[0], (unsigned char*)&work[0], &work3[0], &work4[0], &compressed[0], compressed.size());
97104
98105 std::fill(work.begin(), work.end(), 0);
99106 std::fill(work2.begin(), work2.end(), 0);
Afficher sur ancien navigateur de dépôt.