1 files changed, 189 insertions, 0 deletions
diff --git a/src/compress.cpp b/src/compress.cpp
new file mode 100644
index 0000000..4516e09
--- /dev/null
+++ b/src/compress.cpp
@@ -0,0 +1,189 @@
+/*
+ * 	compress.cpp	        	(C) 2006, Aurélien Croc (AP²C)
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; version 2 of the License.
+ * 
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the
+ *  Free Software Foundation, Inc.,
+ *  59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ *  $Id: compress.cpp 60 2006-12-14 01:03:17Z ap2c $
+ * 
+ */
+#include "compress.h"
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+
+static int32_t ptrArray[0x40];
+static uint32_t maxSizeArray[0x40];
+
+#define COMPRESS_SAMPLE_RATE   0x800
+
+
+static int _compare(const void *n1, const void *n2)
+{
+    // n2 and n1 has been exchanged since the first
+    // element of the array MUST be the biggest
+    return *(uint32_t *)n2 - *(uint32_t *)n1;
+}
+
+int calcOccurs(unsigned char *band, unsigned long bandHeight, 
+        unsigned long bandWidth, unsigned long number)
+{
+    uint32_t occurs[COMPRESS_SAMPLE_RATE * 2];
+    size_t i, j, size;
+
+    size = bandWidth * bandHeight;
+
+    // Initialize buffers
+    for (i=0; i < COMPRESS_SAMPLE_RATE; i++) {
+        occurs[i*2] = 0;
+        occurs[i*2 + 1] = i;
+    }
+
+    // Calculate the byte occurrence
+    for (i=COMPRESS_SAMPLE_RATE; i < size; i += COMPRESS_SAMPLE_RATE) {
+        char b = band[i];
+
+        for (j=1; j < COMPRESS_SAMPLE_RATE; j++)
+            if (band[i - j] == b)
+                occurs[(j-1)*2]++;
+    }
+
+    // Order the array
+    qsort(occurs, COMPRESS_SAMPLE_RATE, sizeof(uint32_t)*2, _compare);
+
+    // Get the first 0x40 elements
+    for (i=0; i < 0x40; i++)
+        ptrArray[i] = ~occurs[i*2 + 1] - 1;
+    
+    // Get the maximum length of a compressed data
+    if (number > 0x63  || !number) {
+        for (i=0; i < 0x40; i++)
+            maxSizeArray[i] = 0x202;
+    } else {
+        uint32_t l;
+
+        l = 0x6464 / (number << 6);
+        for (i=0; i < 0x40; i++) {
+            uint32_t v = 0x202 - l * i;
+
+            if (v < 3)
+                v = 3;
+            maxSizeArray[i] = v;
+        }
+    }
+
+	return 0;
+}
+
+int compressBand(struct BandArray *bandArray, unsigned char *beginIn,
+        unsigned long bandWidth, unsigned long bandHeight)
+{
+    unsigned char *out, *endOut, *in, *endIn, *rawDataPtr = 0;
+    size_t max, repCnt, maxRepCnt, rawDataNr = 0;
+    int32_t lastPtr = 0, si;
+    size_t i, maxPtr;
+
+    // Initialize some variables
+    out = bandArray->next;
+    endOut = bandArray->next + bandWidth * bandHeight;
+    in = beginIn;
+    endIn = beginIn + bandWidth * bandHeight;
+
+    // Print the table
+    for (i=0; i < 0x40; i++) {
+        *(int16_t *)out = ~(int16_t)ptrArray[i];
+        out += 2;
+        if (ptrArray[i] < lastPtr)
+            lastPtr = ptrArray[i];
+    }
+
+    // Print the first uncompressed bytes
+    lastPtr = ~lastPtr;
+    if (lastPtr > 0x80)
+        lastPtr = 0x80;
+    *(uint32_t *)(bandArray->prev + 4) = lastPtr;
+    for (si=0; si < lastPtr; si++) {
+        *out = *in;
+        out++;
+        in++;
+    }
+
+    // Compress the data
+    do {
+        max = endIn - in > 0x202 ? 0x202 : endIn - in;
+
+        if (!max) {
+            if (rawDataNr)
+                *rawDataPtr = rawDataNr - 1;
+            bandArray->next = out;
+            return 0;
+        } else if (max >= 2) {
+            maxRepCnt = 0;
+            maxPtr = 0;
+
+            // Check the best similar piece of data
+            for (i=0; i < 0x40; i++) {
+                unsigned char *seq = in + ptrArray[i] + 1;
+
+                if (seq < beginIn)
+                    continue;
+                if (in <= seq)
+                    continue;
+                for (repCnt = 0; repCnt < max && repCnt < maxSizeArray[i]; 
+                        repCnt++)
+                    if (in[repCnt] != seq[repCnt])
+                        break;
+                if (repCnt > maxRepCnt) {
+                    maxRepCnt = repCnt;
+                    maxPtr = i;
+                }
+            }
+
+            // If the piece is large enough, use it!
+            if (maxRepCnt > 2) {
+                maxRepCnt -= 3;
+                out[0] = 0x80 | maxRepCnt & 0x7F;
+                out[1] = ((maxRepCnt >> 1) & 0xC0) | maxPtr & 0x3F;
+                out += 2;
+                in += maxRepCnt + 3;
+                if (rawDataNr) {
+                    *rawDataPtr = rawDataNr - 1;
+                    rawDataNr = 0;
+                }
+                continue;
+            }
+        }
+
+        // Write the uncompressed data
+        rawDataNr++;
+        if (rawDataNr == 1) {
+            rawDataPtr = out;
+            out++;
+        } else if (rawDataNr == 0x80) {
+            *rawDataPtr = 0x7F;
+            rawDataNr = 0;
+        }
+        *out = *in;
+        out++;
+        in++;
+
+    } while (out <= endOut);
+
+    return -1;
+}
+
+/* vim: set expandtab tabstop=4 shiftwidth=4 smarttab tw=80 cin: */
+