home *** CD-ROM | disk | FTP | other *** search
/ Computer Shopper 275 / DPCS0111DVD.ISO / Toolkit / Audio-Visual / VirtualDub / Source / VirtualDub-1.9.10-src.7z / src / Meia / source / encode_png.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2009-09-14  |  29.5 KB  |  1,147 lines
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <numeric>
  4. #include <vd2/system/zip.h>
  5. #include <vd2/system/error.h>
  6. #include <vd2/system/binary.h>
  7. #include <vd2/Kasumi/pixmap.h>
  8. #include <vd2/Kasumi/pixmapops.h>
  9. #include <vd2/Kasumi/pixmaputils.h>
  10. #include <vd2/Meia/encode_png.h>
  11. #include "common_png.h"
  12.  
  13. #ifndef VDFORCEINLINE
  14.     #ifdef _MSC_VER
  15.         #define VDFORCEINLINE __forceinline
  16.     #else
  17.         #define VDFORCEINLINE
  18.     #endif
  19. #endif
  20.  
  21. namespace {
  22.     const uint8 kPNGSignature[8]={137,80,78,71,13,10,26,10};
  23.  
  24.     const unsigned len_tbl[32]={
  25.         3,4,5,6,7,8,9,10,
  26.         11,13,15,17,19,23,27,31,
  27.         35,43,51,59,67,83,99,115,
  28.         131,163,195,227,258,259
  29.     };
  30.  
  31.     const unsigned char len_bits_tbl[32]={
  32.         0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0
  33.     };
  34.  
  35.     const unsigned char dist_bits_tbl[]={
  36.         0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13
  37.     };
  38.  
  39.     const unsigned dist_tbl[]={
  40.         1,2,3,4,5,7,9,13,
  41.         17,25,33,49,65,97,129,193,
  42.         257,385,513,769,1025,1537,2049,3073,
  43.         4097,6145,8193,12289,16385,24577,
  44.         32769
  45.     };
  46.  
  47.     const unsigned char hclen_tbl[]={
  48.         16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15
  49.     };
  50.  
  51.     int PNGPaethPredictor(int a, int b, int c) {
  52.         int p  = a + b - c;
  53.         int pa = abs(p - a);
  54.         int pb = abs(p - b);
  55.         int pc = abs(p - c);
  56.  
  57.         if (pa <= pb && pa <= pc)
  58.             return a;
  59.         else if (pb <= pc)
  60.             return b;
  61.         else
  62.             return c;
  63.     }
  64.  
  65.     void PNGPredictEncodeNone(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) {
  66.         memcpy(dst, row, rowbytes);
  67.     }
  68.  
  69.     void PNGPredictEncodeSub(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) {
  70.         for(uint32 i=0; i<bpp; ++i)
  71.             dst[i] = row[i];
  72.  
  73.         for(uint32 i=bpp; i<rowbytes; ++i)
  74.             dst[i] = row[i] - row[i-bpp];
  75.     }
  76.  
  77.     void PNGPredictEncodeUp(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) {
  78.         if (prevrow) {
  79.             for(uint32 i=0; i<rowbytes; ++i)
  80.                 dst[i] = row[i] - prevrow[i];
  81.         } else {
  82.             memcpy(dst, row, rowbytes);
  83.         }
  84.     }
  85.  
  86.     void PNGPredictEncodeAverage(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) {
  87.         if (prevrow) {
  88.             for(uint32 i=0; i<bpp; ++i)
  89.                 dst[i] = row[i] - (prevrow[i]>>1);
  90.  
  91.             for(uint32 j=bpp; j<rowbytes; ++j)
  92.                 dst[j] = row[j] - ((prevrow[j] + row[j-bpp])>>1);
  93.         } else {
  94.             for(uint32 i=0; i<bpp; ++i)
  95.                 dst[i] = row[i];
  96.  
  97.             for(uint32 j=bpp; j<rowbytes; ++j)
  98.                 dst[j] = row[j] - (row[j-bpp]>>1);
  99.         }
  100.     }
  101.  
  102.     void PNGPredictEncodePaeth(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) {
  103.         if (prevrow) {
  104.             for(uint32 i=0; i<bpp; ++i)
  105.                 dst[i] = row[i] - PNGPaethPredictor(0, prevrow[i], 0);
  106.             for(uint32 j=bpp; j<rowbytes; ++j)
  107.                 dst[j] = row[j] - PNGPaethPredictor(row[j-bpp], prevrow[j], prevrow[j-bpp]);
  108.         } else {
  109.             for(uint32 i=0; i<bpp; ++i)
  110.                 dst[i] = row[i];
  111.             for(uint32 j=bpp; j<rowbytes; ++j)
  112.                 dst[j] = row[j] - PNGPaethPredictor(row[j-bpp], 0, 0);
  113.         }
  114.     }
  115.  
  116.     uint32 ComputeSumAbsoluteSignedBytes(const sint8 *src, uint32 len) {
  117.         uint32 sum = 0;
  118.         do {
  119.             sint8 c = *src++;
  120.             sint8 mask = c>>7;
  121.  
  122.             sum += (c + mask) ^ mask;
  123.         } while(--len);
  124.  
  125.         return sum;
  126.     }
  127. }
  128.  
  129. struct VDHuffmanHistoSorterData {
  130.     VDHuffmanHistoSorterData(const int pHisto[288]) {
  131.         for(int i=0; i<288; ++i) {
  132.             mHisto[i] = (pHisto[i] << 9) + 287 - i;
  133.         }
  134.     }
  135.  
  136.     int mHisto[288];
  137. };
  138.  
  139. struct VDHuffmanHistoSorter {
  140.     VDHuffmanHistoSorter(const VDHuffmanHistoSorterData& data) : mpHisto(data.mHisto) {}
  141.  
  142.     // We want to sort by descending probability first, then by ascending code point.
  143.     bool operator()(int f1, int f2) const {
  144.         return mpHisto[f1] > mpHisto[f2];
  145.     }
  146.  
  147.     const int *mpHisto;
  148. };
  149.  
  150. class VDPNGHuffmanTable {
  151. public:
  152.     VDPNGHuffmanTable();
  153.  
  154.     void Init();
  155.  
  156.     inline void Tally(int c) {
  157.         ++mHistogram[c];
  158.     }
  159.  
  160.     inline void Tally(int c, int count) {
  161.         mHistogram[c] += count;
  162.     }
  163.  
  164.     void BuildCode(int depth_limit = 15);
  165.     void BuildEncodingTable(uint16 *p, int *l, int limit);
  166.     void BuildStaticLengthEncodingTable(uint16 *p, int *l);
  167.     void BuildStaticDistanceEncodingTable(uint16 *p, int *l);
  168.  
  169.     uint32 GetCodeCount(int limit) const;
  170.     uint32 GetOutputSize() const;
  171.     uint32 GetStaticOutputSize() const;
  172.  
  173.     const uint16 *GetDHTSegment() { return mDHT; }
  174.     int GetDHTSegmentLen() const { return mDHTLength; }
  175.  
  176. private:
  177.     int mHistogram[288];
  178.     int mHistogram2[288];
  179.     uint16 mDHT[288+16];
  180.     int mDHTLength;
  181. };
  182.  
  183. VDPNGHuffmanTable::VDPNGHuffmanTable() {
  184.     Init();
  185. }
  186.  
  187. void VDPNGHuffmanTable::Init() {
  188.     std::fill(mHistogram, mHistogram+288, 0);
  189. }
  190.  
  191. void VDPNGHuffmanTable::BuildCode(int depth_limit) {
  192.     int i;
  193.     int nonzero_codes = 0;
  194.  
  195.     for(i=0; i<288; ++i) {
  196.         mDHT[i+16] = i;
  197.         if (mHistogram[i])
  198.             ++nonzero_codes;
  199.         mHistogram2[i] = mHistogram[i];
  200.     }
  201.  
  202.     // Codes are stored in the second half of the DHT segment in decreasing
  203.     // order of frequency.
  204.  
  205.     std::sort(&mDHT[16], &mDHT[16+288], VDHuffmanHistoSorter(VDHuffmanHistoSorterData(mHistogram)));
  206.     mDHTLength = 16 + nonzero_codes;
  207.  
  208.     // Sort histogram in increasing order.
  209.  
  210.     std::sort(mHistogram, mHistogram+288);
  211.  
  212.     int *A = mHistogram+288 - nonzero_codes;
  213.  
  214.     // Begin merging process (from "In-place calculation of minimum redundancy codes" by A. Moffat and J. Katajainen)
  215.     //
  216.     // There are three merging possibilities:
  217.     //
  218.     // 1) Leaf node with leaf node.
  219.     // 2) Leaf node with internal node.
  220.     // 3) Internal node with internal node.
  221.  
  222.     int leaf = 2;                    // Next, smallest unattached leaf node.
  223.     int internal = 0;                // Next, smallest unattached internal node.
  224.  
  225.     // Merging always creates one internal node and eliminates one node from
  226.     // the total, so we will always be doing N-1 merges.
  227.  
  228.     A[0] += A[1];        // First merge is always two leaf nodes.
  229.     for(int next=1; next<nonzero_codes-1; ++next) {        // 'next' is the value that receives the next unattached internal node.
  230.         int a, b;
  231.  
  232.         // Pick first node.
  233.         if (leaf < nonzero_codes && A[leaf] <= A[internal]) {
  234.             A[next] = a=A[leaf++];            // begin new internal node with P of smallest leaf node
  235.         } else {
  236.             A[next] = a=A[internal];        // begin new internal node with P of smallest internal node
  237.             A[internal++] = next;                    // hook smallest internal node as child of new node
  238.         }
  239.  
  240.         // Pick second node.
  241.         if (internal >= next || (leaf < nonzero_codes && A[leaf] <= A[internal])) {
  242.             A[next] += b=A[leaf++];            // complete new internal node with P of smallest leaf node
  243.         } else {
  244.             A[next] += b=A[internal];        // complete new internal node with P of smallest internal node
  245.             A[internal++] = next;                    // hook smallest internal node as child of new node
  246.         }
  247.     }
  248.  
  249.     // At this point, we have a binary tree composed entirely of pointers to
  250.     // parents, partially sorted such that children are always before their
  251.     // parents in the array.  Traverse the array backwards, replacing each
  252.     // node with its depth in the tree.
  253.  
  254.     A[nonzero_codes-2] = 0;        // root has height 0 (0 bits)
  255.     for(i = nonzero_codes-3; i>=0; --i)
  256.         A[i] = A[A[i]]+1;        // child height is 1+height(parent).
  257.  
  258.     // Compute canonical tree bit depths for first part of DHT segment.
  259.     // For each internal node at depth N, add two counts at depth N+1
  260.     // and subtract one count at depth N.  Essentially, we are splitting
  261.     // as we go.  We traverse backwards to ensure that no counts will drop
  262.     // below zero at any time.
  263.  
  264.     std::fill(mDHT, mDHT+16, 0);
  265.  
  266.     int overallocation = 0;
  267.  
  268.     mDHT[0] = 2;        // 2 codes at depth 1 (1 bit)
  269.     for(i = nonzero_codes-3; i>=0; --i) {
  270.         int depth = A[i];
  271.  
  272.         // The optimal Huffman tree for N nodes can have a depth of N-1,
  273.         // but we have to constrain ourselves at depth 15.  We simply
  274.         // pile up counts at depth 15.  This causes us to overallocate the
  275.         // codespace, but we will compensate for that later.
  276.  
  277.         if (depth >= depth_limit) {
  278.             ++mDHT[depth_limit-1];
  279.         } else {
  280.             --mDHT[depth-1];
  281.             ++mDHT[depth];
  282.             ++mDHT[depth];
  283.         }
  284.     }
  285.  
  286.     // Remove the extra code point.
  287.     for(i=15; i>=0; --i) {
  288.         if (mDHT[i])
  289.             overallocation += mDHT[i] * (0x8000 >> i);
  290.     }
  291.     overallocation -= 0x10000;
  292.  
  293.     // We may have overallocated the codespace if we were forced to shorten
  294.     // some codewords.
  295.  
  296.     if (overallocation > 0) {
  297.         // Codespace is overallocated.  Begin lengthening codes from bit depth
  298.         // 15 down until we are under the limit.
  299.  
  300.         i = depth_limit-2;
  301.         while(overallocation > 0) {
  302.             if (mDHT[i]) {
  303.                 --mDHT[i];
  304.                 ++mDHT[i+1];
  305.                 overallocation -= 0x4000 >> i;
  306.                 if (i < depth_limit-2)
  307.                     ++i;
  308.             } else
  309.                 --i;
  310.         }
  311.  
  312.         // We may be undercommitted at this point.  Raise codes from bit depth
  313.         // 1 up until we are at the desired limit.
  314.  
  315.         int underallocation = -overallocation;
  316.  
  317.         i = 1;
  318.         while(underallocation > 0) {
  319.             if (mDHT[i] && (0x8000>>i) <= underallocation) {
  320.                 underallocation -= (0x8000>>i);
  321.                 --mDHT[i];
  322.                 --i;
  323.                 ++mDHT[i];
  324.             } else {
  325.                 ++i;
  326.             }
  327.         }
  328.     }
  329. }
  330.  
  331. uint32 VDPNGHuffmanTable::GetOutputSize() const {
  332.     const uint16 *pCodes = mDHT+16;
  333.  
  334.     uint32 size = 0;
  335.  
  336.     for(int len=0; len<16; ++len) {
  337.         int count = mDHT[len];
  338.  
  339.         uint32 points = 0;
  340.         while(count--) {
  341.             int code = *pCodes++;
  342.  
  343.             points += mHistogram2[code];
  344.         }
  345.  
  346.         size += points * (len + 1);
  347.     }
  348.  
  349.     return size;
  350. }
  351.  
  352. uint32 VDPNGHuffmanTable::GetCodeCount(int limit) const {
  353.     return std::accumulate(mHistogram2, mHistogram2+limit, 0);
  354. }
  355.  
  356. uint32 VDPNGHuffmanTable::GetStaticOutputSize() const {
  357.     uint32 sum7 = 0;
  358.     uint32 sum8 = 0;
  359.     uint32 sum9 = 0;
  360.     sum8 = std::accumulate(mHistogram2+  0, mHistogram2+144, sum8);
  361.     sum9 = std::accumulate(mHistogram2+144, mHistogram2+256, sum9);
  362.     sum7 = std::accumulate(mHistogram2+256, mHistogram2+280, sum7);
  363.     sum8 = std::accumulate(mHistogram2+280, mHistogram2+288, sum8);
  364.  
  365.     return 7*sum7 + 8*sum8 + 9*sum9;
  366. }
  367.  
  368. static unsigned revword15(unsigned x) {
  369.     unsigned y = 0;
  370.     for(int i=0; i<15; ++i) {
  371.         y = y + y + (x&1);
  372.         x >>= 1;
  373.     }
  374.     return y;
  375. }
  376.  
  377. void VDPNGHuffmanTable::BuildEncodingTable(uint16 *p, int *l, int limit) {
  378.     const uint16 *pCodes = mDHT+16;
  379.  
  380.     uint16 total = 0;
  381.     uint16 inc = 0x4000;
  382.  
  383.     for(int len=0; len<16; ++len) {
  384.         int count = mDHT[len];
  385.  
  386.         while(count--) {
  387.             int code = *pCodes++;
  388.  
  389.             l[code] = len+1;
  390.         }
  391.  
  392.         for(int k=0; k<limit; ++k) {
  393.             if (l[k] == len+1) {
  394.                 p[k] = revword15(total) << (16 - (len+1));
  395.                 total += inc;
  396.             }
  397.         }
  398.         inc >>= 1;
  399.     }
  400. }
  401.  
  402. void VDPNGHuffmanTable::BuildStaticLengthEncodingTable(uint16 *p, int *l) {
  403.     memset(mDHT, 0, sizeof(mDHT[0])*16);
  404.     mDHT[6] = 24;
  405.     mDHT[7] = 152;
  406.     mDHT[8] = 112;
  407.  
  408.     uint16 *dst = mDHT + 16;
  409.     for(int i=256; i<280; ++i)
  410.         *dst++ = i;
  411.     for(int i=0; i<144; ++i)
  412.         *dst++ = i;
  413.     for(int i=280; i<288; ++i)
  414.         *dst++ = i;
  415.     for(int i=144; i<256; ++i)
  416.         *dst++ = i;
  417.  
  418.     BuildEncodingTable(p, l, 288);
  419. }
  420.  
  421. void VDPNGHuffmanTable::BuildStaticDistanceEncodingTable(uint16 *p, int *l) {
  422.     memset(mDHT, 0, sizeof(mDHT[0])*16);
  423.     mDHT[4] = 32;
  424.  
  425.     for(int i=0; i<32; ++i)
  426.         mDHT[i+16] = i;
  427.  
  428.     BuildEncodingTable(p, l, 32);
  429. }
  430.  
  431. class VDPNGDeflateEncoder {
  432. public:
  433.     VDPNGDeflateEncoder();
  434.     VDPNGDeflateEncoder(const VDPNGDeflateEncoder&);
  435.     ~VDPNGDeflateEncoder();
  436.  
  437.     VDPNGDeflateEncoder& operator=(const VDPNGDeflateEncoder&);
  438.  
  439.     void Init(bool quick);
  440.     void Write(const void *src, size_t len);
  441.     void ForceNewBlock();
  442.     void Finish();
  443.  
  444.     uint32 EstimateOutputSize();
  445.  
  446.     vdfastvector<uint8>& GetOutput() { return mOutput; }
  447.  
  448. protected:
  449.     void EndBlock(bool term);
  450.     void Compress(bool flush);
  451.     void VDFORCEINLINE PutBits(uint32 encoding, int enclen);
  452.     void FlushBits();
  453.     uint32 Flush(int n, int ndists, bool term, bool test);
  454.  
  455.     uint32    mAccum;
  456.     int        mAccBits;
  457.     uint32    mHistoryPos;
  458.     uint32    mHistoryTail;
  459.     uint32    mHistoryBase;
  460.     uint32    mHistoryBlockStart;
  461.     uint32    mLenExtraBits;
  462.     uint32    mPendingLen;
  463.     uint8    *mpLen;
  464.     uint16    *mpCode;
  465.     uint16    *mpDist;
  466.  
  467.     uint32    mWindowLimit;
  468.  
  469.     vdfastvector<uint8> mOutput;
  470.     VDAdler32Checker mAdler32;
  471.  
  472.     // Block coding tables
  473.     uint16    mCodeEnc[288];
  474.     int        mCodeLen[288];
  475.  
  476.     uint16    mDistEnc[32];
  477.     int        mDistLen[32];
  478.  
  479.     uint8    mHistoryBuffer[65536+6];
  480.     sint32    mHashNext[32768];
  481.     sint32    mHashTable[65536];
  482.     uint8    mLenBuf[32769];
  483.     uint16    mCodeBuf[32769];
  484.     uint16    mDistBuf[32769];
  485. };
  486.  
  487. VDPNGDeflateEncoder::VDPNGDeflateEncoder()
  488. {
  489. }
  490.  
  491. VDPNGDeflateEncoder::VDPNGDeflateEncoder(const VDPNGDeflateEncoder& src) {
  492.     *this = src;
  493. }
  494.  
  495. VDPNGDeflateEncoder::~VDPNGDeflateEncoder() {
  496. }
  497.  
  498. VDPNGDeflateEncoder& VDPNGDeflateEncoder::operator=(const VDPNGDeflateEncoder& src) {
  499.     if (this != &src) {
  500.         mAccum            = src.mAccum;
  501.         mAccBits        = src.mAccBits;
  502.         mHistoryPos        = src.mHistoryPos;
  503.         mHistoryTail    = src.mHistoryTail;
  504.         mHistoryBase    = src.mHistoryBase;
  505.         mHistoryBlockStart = src.mHistoryBlockStart;
  506.         mLenExtraBits = src.mLenExtraBits;
  507.         mPendingLen        = src.mPendingLen;
  508.         mpLen            = mLenBuf + (src.mpLen - src.mLenBuf);
  509.         mpCode            = mCodeBuf + (src.mpCode - src.mCodeBuf);
  510.         mpDist            = mDistBuf + (src.mpDist - src.mDistBuf);
  511.         mWindowLimit    = src.mWindowLimit;
  512.         mOutput            = src.mOutput;
  513.         mAdler32        = src.mAdler32;
  514.  
  515.         memcpy(mHistoryBuffer, src.mHistoryBuffer, mHistoryTail);
  516.         memcpy(mHashNext, src.mHashNext, sizeof mHashNext);
  517.         memcpy(mHashTable, src.mHashTable, sizeof mHashTable);
  518.         memcpy(mLenBuf, src.mLenBuf, sizeof(mLenBuf[0]) * (src.mpLen - src.mLenBuf));
  519.         memcpy(mCodeBuf, src.mCodeBuf, sizeof(mCodeBuf[0]) * (src.mpCode - src.mCodeBuf));
  520.         memcpy(mDistBuf, src.mDistBuf, sizeof(mDistBuf[0]) * (src.mpDist - src.mDistBuf));
  521.     }
  522.     return *this;
  523. }
  524.  
  525. void VDPNGDeflateEncoder::Init(bool quick) {
  526.     std::fill(mHashNext, mHashNext+32768, -0x20000);
  527.     std::fill(mHashTable, mHashTable+65536, -0x20000);
  528.  
  529.     mWindowLimit = quick ? 1024 : 32768;
  530.  
  531.     mpLen = mLenBuf;
  532.     mpCode = mCodeBuf;
  533.     mpDist = mDistBuf;
  534.     mHistoryPos = 0;
  535.     mHistoryTail = 0;
  536.     mHistoryBase = 0;
  537.     mHistoryBlockStart = 0;
  538.     mLenExtraBits = 0;
  539.     mPendingLen = 0;
  540.     mAccum = 0;
  541.     mAccBits = 0;
  542.  
  543.     mOutput.push_back(0x78);    // 32K window, Deflate
  544.     mOutput.push_back(0xDA);    // maximum compression, no dictionary, check offset = 0x1A
  545. }
  546.  
  547. void VDPNGDeflateEncoder::Write(const void *src, size_t len) {
  548.     while(len > 0) {
  549.         uint32 tc = sizeof mHistoryBuffer - mHistoryTail;
  550.  
  551.         if (!tc) {
  552.             Compress(false);
  553.             continue;
  554.         }
  555.  
  556.         if ((size_t)tc > len)
  557.             tc = (uint32)len;
  558.  
  559.         mAdler32.Process(src, tc);
  560.         memcpy(mHistoryBuffer + mHistoryTail, src, tc);
  561.  
  562.         mHistoryTail += tc;
  563.         src = (const char *)src + tc;
  564.         len -= tc;
  565.     }
  566. }
  567.  
  568. void VDPNGDeflateEncoder::ForceNewBlock() {
  569.     Compress(false);
  570.     EndBlock(false);
  571. }
  572.  
  573. #define HASH(pos) (((uint32)hist[(pos)] ^ ((uint32)hist[(pos)+1] << 2) ^ ((uint32)hist[(pos)+2] << 4) ^ ((uint32)hist[(pos)+3] << 6) ^ ((uint32)hist[(pos)+4] << 7) ^ ((uint32)hist[(pos)+5] << 8)) & 0xffff)
  574.  
  575. void VDPNGDeflateEncoder::EndBlock(bool term) {
  576.     if (mpCode > mCodeBuf) {
  577.         if (mPendingLen) {
  578.             const uint8 *hist = mHistoryBuffer - mHistoryBase;
  579.             int bestlen = mPendingLen - 1;
  580.             mPendingLen = 0;
  581.  
  582.             while(bestlen-- > 0) {
  583.                 int hval = HASH(mHistoryPos);
  584.                 mHashNext[mHistoryPos & 0x7fff] = mHashTable[hval];
  585.                 mHashTable[hval] = mHistoryPos;
  586.                 ++mHistoryPos;
  587.             }
  588.         }
  589.  
  590.         *mpCode++ = 256;
  591.         Flush(mpCode - mCodeBuf, mpDist - mDistBuf, term, false);
  592.         mpCode = mCodeBuf;
  593.         mpDist = mDistBuf;
  594.         mpLen = mLenBuf;
  595.         mHistoryBlockStart = mHistoryPos;
  596.         mLenExtraBits = 0;
  597.     }
  598. }
  599.  
  600. void VDPNGDeflateEncoder::Compress(bool flush) {
  601.     uint8    *lenptr = mpLen;
  602.     uint16    *codeptr = mpCode;
  603.     uint16    *distptr = mpDist;
  604.  
  605.     const uint8 *hist = mHistoryBuffer - mHistoryBase;
  606.  
  607.     uint32 pos = mHistoryPos;
  608.     uint32 len = mHistoryBase + mHistoryTail;
  609.     uint32 maxpos = flush ? len : len > 258+6 ? len - (258+6) : 0;        // +6 is for the 6-byte hash.
  610.     while(pos < maxpos) {
  611.         if (codeptr >= mCodeBuf + 32768) {
  612.             mpCode = codeptr;
  613.             mpDist = distptr;
  614.             mpLen = lenptr;
  615.             mHistoryPos = pos;
  616.             EndBlock(false);
  617.             pos = mHistoryPos;
  618.             codeptr = mpCode;
  619.             distptr = mpDist;
  620.             lenptr = mpLen;
  621.  
  622.             // Note that it's possible for the EndBlock() to have flushed out a pending
  623.             // run and pushed us all the way to maxpos.
  624.             VDASSERT(pos <= mHistoryBase + mHistoryTail);
  625.             continue;
  626.         }
  627.  
  628.         uint8 c = hist[pos];
  629.         uint32 hcode = HASH(pos);
  630.  
  631.         sint32 hpos = mHashTable[hcode];
  632.         uint32 limit = 258;
  633.         if (limit > len-pos)
  634.             limit = len-pos;
  635.  
  636.         sint32 hlimit = pos - mWindowLimit;        // note that our initial hash table values are low enough to avoid colliding with this.
  637.         if (hlimit < 0)
  638.             hlimit = 0;
  639.  
  640.         uint32 bestlen = 5;
  641.         uint32 bestoffset = 0;
  642.  
  643.         if (hpos >= hlimit && limit >= 6) {
  644.             sint32 hstart = hpos;
  645.             const unsigned char *s2 = hist + pos;
  646.             uint32 matchWord1 = *(const uint32 *)s2;
  647.             uint16 matchWord2 = *(const uint16 *)(s2 + 4);
  648.             do {
  649.                 const unsigned char *s1 = hist + hpos - bestlen + 5;
  650.                 uint32 mlen = 0;
  651.  
  652.                 if (s1[bestlen] == s2[bestlen] && *(const uint32 *)s1 == matchWord1 && *(const uint16 *)(s1 + 4) == matchWord2) {
  653.                     mlen = 6;
  654.                     while(mlen < limit && s1[mlen] == s2[mlen])
  655.                         ++mlen;
  656.  
  657.                     if (mlen > bestlen) {
  658.                         bestoffset = pos - hpos + bestlen - 5;
  659.                         // hop hash chains!
  660.                         hpos += mlen - bestlen;
  661.                         if (hpos == pos)
  662.                             hpos = hstart;
  663.                         else
  664.                             hpos = mHashNext[(hpos + mlen - bestlen) & 0x7fff];
  665.                         hlimit += (mlen - bestlen);
  666.  
  667.                         bestlen = mlen;
  668.                         continue;
  669.                     }
  670.                 }
  671.  
  672.                 hpos = mHashNext[hpos & 0x7fff];
  673.             } while(hpos >= hlimit);
  674.         }
  675.  
  676.         // Normally, we'd accept any match of longer 3 or greater. However, the savings for this aren't
  677.         // enough to match the decrease in the effectiveness of the Huffman encoding, so it's usually
  678.         // better to keep only longer matches. We follow the lead of zlib's Z_FILTERED and only accept
  679.         // matches of length 6 or longer. It turns out that we can greatly speed up compression when
  680.         // this is the case since we can use a longer hash -- the PNG filtering often means a very
  681.         // skewed distribution which hinders the effectiveness of a 3-byte hash.
  682.         if (bestlen >= 6) {
  683.             // check for an illegal match
  684.             VDASSERT((uint32)(bestoffset-1) < 32768U);
  685.             VDASSERT(bestlen < 259);
  686.             VDASSERT(!memcmp(hist+pos, hist+pos-bestoffset, bestlen));
  687.             VDASSERT(pos >= bestoffset);
  688.             VDASSERT(pos+bestlen <= len);
  689.             VDASSERT(pos-bestoffset >= mHistoryBase);
  690.  
  691.             unsigned lcode = 0;
  692.             while(bestlen >= len_tbl[lcode+1])
  693.                 ++lcode;
  694.             *codeptr++ = lcode + 257;
  695.             *distptr++ = bestoffset;
  696.             *lenptr++ = bestlen - 3;
  697.             mLenExtraBits += len_bits_tbl[lcode];
  698.         } else {
  699.             *codeptr++ = c;
  700.             bestlen = 1;
  701.         }
  702.  
  703.         // Lazy matching.
  704.         //
  705.         //    prev    current        compare        action
  706.         //    ======================================
  707.         //    lit        lit                        append
  708.         //    lit        match                    stash
  709.         //    match    lit                        retire
  710.         //    match    match        shorter        retire
  711.         //    match    match        longer        obsolete
  712.         VDASSERT(pos+bestlen <= mHistoryBase + mHistoryTail);
  713.  
  714.         if (!mPendingLen) {
  715.             if (bestlen > 1) {
  716.                 mPendingLen = bestlen;
  717.                 bestlen = 1;
  718.             }
  719.         } else {
  720.             if (bestlen > mPendingLen) {
  721.                 codeptr[-2] = hist[pos - 1];
  722.                 distptr[-2] = distptr[-1];
  723.                 --distptr;
  724.                 lenptr[-2] = lenptr[-1];
  725.                 --lenptr;
  726.                 mPendingLen = bestlen;
  727.                 bestlen = 1;
  728.             } else {
  729.                 --codeptr;
  730.                 if (bestlen > 1) {
  731.                     --distptr;
  732.                     --lenptr;
  733.                 }
  734.  
  735.                 bestlen = mPendingLen - 1;
  736.                 mPendingLen = 0;
  737.             }
  738.         }
  739.  
  740.         VDASSERT(pos+bestlen <= mHistoryBase + mHistoryTail);
  741.  
  742.         if (bestlen > 0) {
  743.             mHashNext[pos & 0x7fff] = mHashTable[hcode];
  744.             mHashTable[hcode] = pos;
  745.             ++pos;
  746.  
  747.             while(--bestlen) {
  748.                 uint32 hcode = HASH(pos);
  749.                 mHashNext[pos & 0x7fff] = mHashTable[hcode];
  750.                 mHashTable[hcode] = pos;
  751.                 ++pos;
  752.             }
  753.         }
  754.     }
  755.  
  756.     // shift down by 32K
  757.     if (pos - mHistoryBase >= 49152) {
  758.         uint32 delta = (pos - 32768) - mHistoryBase;
  759.         memmove(mHistoryBuffer, mHistoryBuffer + delta, mHistoryTail - delta);
  760.         mHistoryBase += delta;
  761.         mHistoryTail -= delta;
  762.     }
  763.  
  764.     mHistoryPos = pos;
  765.     mpLen = lenptr;
  766.     mpCode = codeptr;
  767.     mpDist = distptr;
  768. }
  769.  
  770. void VDPNGDeflateEncoder::Finish() {
  771.     while(mHistoryPos != mHistoryBase + mHistoryTail)
  772.         Compress(true);
  773.  
  774.     VDASSERT(mpCode != mCodeBuf);
  775.     EndBlock(true);
  776.  
  777.     FlushBits();
  778.  
  779.     // write Adler32 checksum
  780.     uint8 crc[4];
  781.     VDWriteUnalignedBEU32(crc, mAdler32.Adler32());
  782.  
  783.     mOutput.insert(mOutput.end(), crc, crc+4);
  784. }
  785.  
  786. uint32 VDPNGDeflateEncoder::EstimateOutputSize() {
  787.     Compress(false);
  788.  
  789.     return mOutput.size() * 8 + mAccBits + Flush(mpCode - mCodeBuf, mpDist - mDistBuf, false, true);
  790. }
  791.  
  792. void VDFORCEINLINE VDPNGDeflateEncoder::PutBits(uint32 encoding, int enclen) {
  793.     mAccum >>= enclen;
  794.     mAccum += encoding;
  795.     mAccBits += enclen;
  796.  
  797.     if (mAccBits >= 16) {
  798.         mAccBits -= 16;
  799. //        uint8 c[2] = { mAccum >> (16-mAccBits), mAccum >> (24-mAccBits) };
  800.  
  801. //        mOutput.insert(mOutput.end(), c, c+2);
  802.         mOutput.push_back(mAccum >> (16-mAccBits));
  803.         mOutput.push_back(mAccum >> (24-mAccBits));
  804.     }        
  805. }
  806.  
  807. void VDPNGDeflateEncoder::FlushBits() {
  808.     while(mAccBits > 0) {
  809.         mOutput.push_back(0xff & (mAccum >> (32-mAccBits)));
  810.         mAccBits -= 8;
  811.     }
  812. }
  813.  
  814. uint32 VDPNGDeflateEncoder::Flush(int n, int ndists, bool term, bool test) {
  815.     const uint16 *codes = mCodeBuf;
  816.     const uint8 *lens = mLenBuf;
  817.     const uint16 *dists = mDistBuf;
  818.  
  819.     VDPNGHuffmanTable htcodes, htdists, htlens;
  820.     int i;
  821.  
  822.     memset(mCodeLen, 0, sizeof mCodeLen);
  823.     memset(mDistLen, 0, sizeof mDistLen);
  824.  
  825.     for(i=0; i<n; ++i)
  826.         htcodes.Tally(codes[i]);
  827.  
  828.     htcodes.BuildCode(15);
  829.  
  830.     for(i=0; i<ndists; ++i) {
  831.         int c=0;
  832.         while(dists[i] >= dist_tbl[c+1])
  833.             ++c;
  834.  
  835.         htdists.Tally(c);
  836.     }
  837.  
  838.     htdists.BuildCode(15);
  839.  
  840.     int totalcodes = 286;
  841.     int totaldists = 30;
  842.     int totallens = totalcodes + totaldists;
  843.  
  844.     htcodes.BuildEncodingTable(mCodeEnc, mCodeLen, 288);
  845.     htdists.BuildEncodingTable(mDistEnc, mDistLen, 32);
  846.  
  847.     // RLE the length table
  848.     uint8 lenbuf[286+30+1];
  849.     uint8 *lendst = lenbuf;
  850.     uint8 rlebuf[286+30+1];
  851.     uint8 *rledst = rlebuf;
  852.  
  853.     for(i=0; i<totalcodes; ++i)
  854.         *lendst++ = mCodeLen[i];
  855.  
  856.     for(i=0; i<totaldists; ++i)
  857.         *lendst++ = mDistLen[i];
  858.  
  859.     *lendst = 255;        // avoid match
  860.  
  861.     int last = -1;
  862.     uint32 treeExtraBits = 0;
  863.     i=0;
  864.     while(i<totallens) {
  865.         if (!lenbuf[i] && !lenbuf[i+1] && !lenbuf[i+2]) {
  866.             int j;
  867.             for(j=3; j<138 && !lenbuf[i+j]; ++j)
  868.                 ;
  869.             if (j < 11) {
  870.                 *rledst++ = 17;
  871.                 *rledst++ = j-3;
  872.                 treeExtraBits += 3;
  873.             } else {
  874.                 *rledst++ = 18;
  875.                 *rledst++ = j-11;
  876.                 treeExtraBits += 7;
  877.             }
  878.             htlens.Tally(rledst[-2]);
  879.             i += j;
  880.             last = 0;
  881.         } else if (lenbuf[i] == last && lenbuf[i+1] == last && lenbuf[i+2] == last) {
  882.             int j;
  883.             for(j=3; j<6 && lenbuf[i+j] == last; ++j)
  884.                 ;
  885.             *rledst++ = 16;
  886.             htlens.Tally(16);
  887.             *rledst++ = j-3;
  888.             treeExtraBits += 2;
  889.             i += j;
  890.         } else {
  891.             htlens.Tally(*rledst++ = lenbuf[i++]);
  892.             last = lenbuf[i-1];
  893.         }
  894.     }
  895.  
  896.     htlens.BuildCode(7);
  897.  
  898.     // compute bits for dynamic encoding
  899.     uint32 blockSize = mHistoryPos - mHistoryBlockStart;
  900.     uint32 alignBits = -(mAccBits+3) & 7;
  901.     uint32 dynamicBlockBits = htcodes.GetOutputSize() + htdists.GetOutputSize() + mLenExtraBits + htlens.GetOutputSize() + 14 + 19*3 + treeExtraBits;
  902.     uint32 staticBlockBits = htcodes.GetStaticOutputSize() + htdists.GetCodeCount(32)*5 + mLenExtraBits;
  903.     uint32 storeBlockBits = blockSize*8 + 32 + alignBits;
  904.  
  905.     if (storeBlockBits < dynamicBlockBits && storeBlockBits < staticBlockBits) {
  906.         if (test)
  907.             return storeBlockBits;
  908.  
  909.         PutBits((term ? 0x20000000 : 0) + (0 << 30), 3);
  910.  
  911.         // align to byte boundary
  912.         PutBits(0, alignBits);
  913.  
  914.         // write block size
  915.         PutBits((blockSize << 16) & 0xffff0000, 16);
  916.         PutBits((~blockSize << 16) & 0xffff0000, 16);
  917.  
  918.         // write the block.
  919.         FlushBits();
  920.  
  921.         const uint8 *base = &mHistoryBuffer[mHistoryBlockStart - mHistoryBase];
  922.         mOutput.insert(mOutput.end(), base, base+blockSize);
  923.     } else {
  924.         if (dynamicBlockBits < staticBlockBits) {
  925.             if (test)
  926.                 return dynamicBlockBits;
  927.  
  928.             PutBits((term ? 0x20000000 : 0) + (2 << 30), 3);
  929.  
  930.             PutBits((totalcodes - 257) << 27, 5);    // code count - 257
  931.             PutBits((totaldists - 1) << 27, 5);    // dist count - 1
  932.             PutBits(0xf0000000, 4);    // ltbl count - 4
  933.  
  934.             uint16 hlenc[19];
  935.             int hllen[19]={0};
  936.             htlens.BuildEncodingTable(hlenc, hllen, 19);
  937.  
  938.             for(i=0; i<19; ++i) {
  939.                 int k = hclen_tbl[i];
  940.  
  941.                 PutBits(hllen[k] << 29, 3);
  942.             }
  943.  
  944.             uint8 *rlesrc = rlebuf;
  945.             while(rlesrc < rledst) {
  946.                 uint8 c = *rlesrc++;
  947.                 PutBits((uint32)hlenc[c] << 16, hllen[c]);
  948.  
  949.                 if (c == 16)
  950.                     PutBits((uint32)*rlesrc++ << 30, 2);
  951.                 else if (c == 17)
  952.                     PutBits((uint32)*rlesrc++ << 29, 3);
  953.                 else if (c == 18)
  954.                     PutBits((uint32)*rlesrc++ << 25, 7);
  955.             }
  956.         } else {
  957.             if (test)
  958.                 return staticBlockBits;
  959.  
  960.             PutBits((term ? 0x20000000 : 0) + (1 << 30), 3);
  961.  
  962.             memset(mCodeLen, 0, sizeof(mCodeLen));
  963.             memset(mDistLen, 0, sizeof(mDistLen));
  964.             htcodes.BuildStaticLengthEncodingTable(mCodeEnc, mCodeLen);
  965.             htdists.BuildStaticDistanceEncodingTable(mDistEnc, mDistLen);
  966.         }
  967.  
  968.         for(i=0; i<n; ++i) {
  969.             unsigned code = *codes++;
  970.             unsigned clen = mCodeLen[code];
  971.  
  972.             PutBits((uint32)mCodeEnc[code] << 16, clen);
  973.  
  974.             if (code >= 257) {
  975.                 unsigned extralenbits = len_bits_tbl[code-257];
  976.                 unsigned len = *lens++ + 3;
  977.  
  978.                 VDASSERT(len >= len_tbl[code-257]);
  979.                 VDASSERT(len < len_tbl[code-256]);
  980.  
  981.                 if (extralenbits)
  982.                     PutBits((len - len_tbl[code-257]) << (32 - extralenbits), extralenbits);
  983.  
  984.                 unsigned dist = *dists++;
  985.                 int dcode=0;
  986.                 while(dist >= dist_tbl[dcode+1])
  987.                     ++dcode;
  988.  
  989.                 PutBits((uint32)mDistEnc[dcode] << 16, mDistLen[dcode]);
  990.  
  991.                 unsigned extradistbits = dist_bits_tbl[dcode];
  992.  
  993.                 if (extradistbits)
  994.                     PutBits((dist - dist_tbl[dcode]) << (32 - extradistbits), extradistbits);
  995.             }
  996.         }
  997.     }
  998.  
  999.     return 0;
  1000. }
  1001.  
  1002. class VDImageEncoderPNG : public IVDImageEncoderPNG {
  1003. public:
  1004.     VDImageEncoderPNG();
  1005.     ~VDImageEncoderPNG();
  1006.  
  1007.     void Encode(const VDPixmap& px, const void *&p, uint32& len, bool quick);
  1008.  
  1009. protected:
  1010.     vdfastvector<uint8>    mOutput;
  1011. };
  1012.  
  1013. VDImageEncoderPNG::VDImageEncoderPNG() {
  1014. }
  1015.  
  1016. VDImageEncoderPNG::~VDImageEncoderPNG() {
  1017. }
  1018.  
  1019. void VDImageEncoderPNG::Encode(const VDPixmap& px, const void *&p, uint32& len, bool quick) {
  1020.     mOutput.assign(kPNGSignature, kPNGSignature + 8);
  1021.  
  1022.     struct IHDR {
  1023.         uint32    mChunkLength;
  1024.         uint32    mChunkType;
  1025.         uint32    mWidth;
  1026.         uint32    mHeight;
  1027.         uint8    mDepth;
  1028.         uint8    mColorType;
  1029.         uint8    mCompression;
  1030.         uint8    mFilterMethod;
  1031.         uint8    mInterlaceMethod;
  1032.     } ihdr;
  1033.  
  1034.     ihdr.mChunkLength        = VDToBE32(13);
  1035.     ihdr.mChunkType            = VDMAKEFOURCC('I', 'H', 'D', 'R');
  1036.     ihdr.mWidth                = VDToBE32(px.w);
  1037.     ihdr.mHeight            = VDToBE32(px.h);
  1038.     ihdr.mDepth                = 8;
  1039.     ihdr.mColorType            = 2;        // truecolor
  1040.     ihdr.mCompression        = 0;        // Deflate
  1041.     ihdr.mFilterMethod        = 0;        // basic adaptive filtering
  1042.     ihdr.mInterlaceMethod    = 0;        // no interlacing
  1043.  
  1044.     VDCRCChecker crc;
  1045.     uint32 ihdr_crc = VDToBE32(crc.CRC(VDCRCChecker::kCRC32, &ihdr.mChunkType, 17));
  1046.  
  1047.     mOutput.insert(mOutput.end(), (const uint8 *)&ihdr, (const uint8 *)&ihdr + 21);
  1048.     mOutput.insert(mOutput.end(), (const uint8 *)&ihdr_crc, (const uint8 *)&ihdr_crc + 4);
  1049.  
  1050.     VDPixmapBuffer pxtmp(px.w, px.h, nsVDPixmap::kPixFormat_RGB888);
  1051.     VDPixmapBlt(pxtmp, px);
  1052.  
  1053.     vdautoptr<VDPNGDeflateEncoder> enc(new VDPNGDeflateEncoder);    // way too big for stack
  1054.  
  1055.     vdautoptr<VDPNGDeflateEncoder> tempenc[5]={
  1056.         vdautoptr<VDPNGDeflateEncoder>(new VDPNGDeflateEncoder),
  1057.         vdautoptr<VDPNGDeflateEncoder>(new VDPNGDeflateEncoder),
  1058.         vdautoptr<VDPNGDeflateEncoder>(new VDPNGDeflateEncoder),
  1059.         vdautoptr<VDPNGDeflateEncoder>(new VDPNGDeflateEncoder),
  1060.         vdautoptr<VDPNGDeflateEncoder>(new VDPNGDeflateEncoder)
  1061.     };
  1062.  
  1063.     const uint32 w = pxtmp.w;
  1064.     const uint32 rowbytes = w*3;
  1065.     vdfastvector<uint8> temprowbuf(rowbytes*5);
  1066.     uint8 *tempmem = temprowbuf.data();
  1067.     const uint8 *prevrow = NULL;
  1068.  
  1069.     enc->Init(quick);
  1070.  
  1071.     int lastcomp = -1;
  1072.     for(uint32 y=0; y<(uint32)pxtmp.h; ++y) {
  1073.         // swap red and blue for this row
  1074.         uint8 *dst = (uint8 *)pxtmp.data + pxtmp.pitch * y;
  1075.         const uint8 *src = dst;
  1076.         for(uint32 x=w; x; --x) {
  1077.             uint8 b = dst[0];
  1078.             uint8 r = dst[2];
  1079.             dst[0] = r;
  1080.             dst[2] = b;
  1081.             dst += 3;
  1082.         }
  1083.  
  1084.         // try all predictors
  1085.         static void (*const predictors[])(uint8 *dst, const uint8 *row, const uint8 *prevrow, uint32 rowbytes, uint32 bpp) = {
  1086.             PNGPredictEncodeNone,
  1087.             PNGPredictEncodeSub,
  1088.             PNGPredictEncodeUp,
  1089.             PNGPredictEncodeAverage,
  1090.             PNGPredictEncodePaeth,
  1091.         };
  1092.  
  1093.         uint32 best = 0;
  1094.         uint32 bestscore = 0xFFFFFFFF;
  1095.  
  1096.         for(int i=0; i<5; ++i) {
  1097.             uint8 *dst = tempmem + rowbytes * i;
  1098.             predictors[i](dst, src, prevrow, rowbytes, 3);
  1099.  
  1100.             uint32 score = ComputeSumAbsoluteSignedBytes((const sint8*)dst, rowbytes);
  1101.             if (score < bestscore) {
  1102.                 best = i;
  1103.                 bestscore = score;
  1104.             }
  1105.         }
  1106.  
  1107.         const uint8 comp = best;
  1108.         enc->Write(&comp, 1);
  1109.         enc->Write(tempmem + rowbytes * best, rowbytes);
  1110.  
  1111.         prevrow = src;
  1112.     }
  1113.     enc->Finish();
  1114.     vdfastvector<uint8>& encoutput = enc->GetOutput();
  1115.  
  1116.     struct IDAT {
  1117.         uint32    mChunkLength;
  1118.         uint32    mChunkType;
  1119.     } idat;
  1120.     idat.mChunkLength        = VDToBE32(encoutput.size());
  1121.     idat.mChunkType            = VDMAKEFOURCC('I', 'D', 'A', 'T');
  1122.  
  1123.     mOutput.insert(mOutput.end(), (const uint8 *)&idat, (const uint8 *)&idat + 8);
  1124.     mOutput.insert(mOutput.end(), encoutput.begin(), encoutput.end());
  1125.  
  1126.     crc.Init(VDCRCChecker::kCRC32);
  1127.     crc.Process(&idat.mChunkType, 4);
  1128.     crc.Process(encoutput.data(), encoutput.size());
  1129.     uint32 idat_crc = VDToBE32(crc.CRC());
  1130.     mOutput.insert(mOutput.end(), (const uint8 *)&idat_crc, (const uint8 *)&idat_crc + 4);
  1131.  
  1132.     uint8 footer[]={
  1133.         0, 0, 0, 0, 'I', 'E', 'N', 'D', 0, 0, 0, 0
  1134.     };
  1135.  
  1136.     VDWriteUnalignedBEU32(footer+8, crc.CRC(VDCRCChecker::kCRC32, footer + 4, 4));
  1137.  
  1138.     mOutput.insert(mOutput.end(), footer, footer+12);
  1139.  
  1140.     p = mOutput.data();
  1141.     len = mOutput.size();
  1142. }
  1143.  
  1144. IVDImageEncoderPNG *VDCreateImageEncoderPNG() {
  1145.     return new VDImageEncoderPNG;
  1146. }
  1147.