1 /*
2 * compress.cpp (C) 2006, Aurélien Croc (AP²C)
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the
15 * Free Software Foundation, Inc.,
16 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17 *
18 * $Id$
19 *
20 */
21 #include "compress.h"
22 #include <stdint.h>
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26
27
28 static int32_t ptrArray[0x40];
29 static uint32_t maxSizeArray[0x40];
30
31 #define COMPRESS_SAMPLE_RATE 0x800
32
33
_compare(const void * n1,const void * n2)34 static int _compare(const void *n1, const void *n2)
35 {
36 // n2 and n1 has been exchanged since the first
37 // element of the array MUST be the biggest
38 return *(uint32_t *)n2 - *(uint32_t *)n1;
39 }
40
calcOccurs(unsigned char * band,unsigned long bandHeight,unsigned long bandWidth,unsigned long number)41 int calcOccurs(unsigned char *band, unsigned long bandHeight,
42 unsigned long bandWidth, unsigned long number)
43 {
44 uint32_t occurs[COMPRESS_SAMPLE_RATE * 2];
45 size_t i, j, size;
46
47 size = bandWidth * bandHeight;
48
49 // Initialize buffers
50 for (i=0; i < COMPRESS_SAMPLE_RATE; i++) {
51 occurs[i*2] = 0;
52 occurs[i*2 + 1] = i;
53 }
54
55 // Calculate the byte occurrence
56 for (i=COMPRESS_SAMPLE_RATE; i < size; i += COMPRESS_SAMPLE_RATE) {
57 char b = band[i];
58
59 for (j=1; j < COMPRESS_SAMPLE_RATE; j++)
60 if (band[i - j] == b)
61 occurs[(j-1)*2]++;
62 }
63
64 // Order the array
65 qsort(occurs, COMPRESS_SAMPLE_RATE, sizeof(uint32_t)*2, _compare);
66
67 // Get the first 0x40 elements
68 for (i=0; i < 0x40; i++)
69 ptrArray[i] = ~occurs[i*2 + 1] - 1;
70
71 // Get the maximum length of a compressed data
72 if (number > 0x63 || !number) {
73 for (i=0; i < 0x40; i++)
74 maxSizeArray[i] = 0x202;
75 } else {
76 uint32_t l;
77
78 l = 0x6464 / (number << 6);
79 for (i=0; i < 0x40; i++) {
80 uint32_t v = 0x202 - l * i;
81
82 if (v < 3)
83 v = 3;
84 maxSizeArray[i] = v;
85 }
86 }
87
88 return 0;
89 }
90
compressBand(struct BandArray * bandArray,unsigned char * beginIn,unsigned long bandWidth,unsigned long bandHeight)91 int compressBand(struct BandArray *bandArray, unsigned char *beginIn,
92 unsigned long bandWidth, unsigned long bandHeight)
93 {
94 unsigned char *out, *endOut, *in, *endIn, *rawDataPtr = 0;
95 size_t max, repCnt, maxRepCnt, rawDataNr = 0;
96 int32_t lastPtr = 0;
97 size_t i, maxPtr;
98
99 // Initialize some variables
100 out = bandArray->next;
101 endOut = bandArray->next + bandWidth * bandHeight;
102 in = beginIn;
103 endIn = beginIn + bandWidth * bandHeight;
104
105 // Print the table
106 for (i=0; i < 0x40; i++) {
107 *(int16_t *)out = ~(int16_t)ptrArray[i];
108 out += 2;
109 if (ptrArray[i] < lastPtr)
110 lastPtr = ptrArray[i];
111 }
112
113 // Print the first uncompressed bytes
114 lastPtr = ~lastPtr;
115 if (lastPtr > 0x80)
116 lastPtr = 0x80;
117 *(uint32_t *)(bandArray->prev + 4) = lastPtr;
118 for (i=0; i < lastPtr; i++) {
119 *out = *in;
120 out++;
121 in++;
122 }
123
124 // Compress the data
125 do {
126 max = endIn - in > 0x202 ? 0x202 : endIn - in;
127
128 if (!max) {
129 if (rawDataNr)
130 *rawDataPtr = rawDataNr - 1;
131 bandArray->next = out;
132 return 0;
133 } else if (max >= 2) {
134 maxRepCnt = 0;
135 maxPtr = 0;
136
137 // Check the best similar piece of data
138 for (i=0; i < 0x40; i++) {
139 unsigned char *seq = in + ptrArray[i] + 1;
140
141 if (seq < beginIn)
142 continue;
143 if (in <= seq)
144 continue;
145 for (repCnt = 0; repCnt < max && repCnt < maxSizeArray[i];
146 repCnt++)
147 if (in[repCnt] != seq[repCnt])
148 break;
149 if (repCnt > maxRepCnt) {
150 maxRepCnt = repCnt;
151 maxPtr = i;
152 }
153 }
154
155 // If the piece is large enough, use it!
156 if (maxRepCnt > 2) {
157 maxRepCnt -= 3;
158 out[0] = 0x80 | maxRepCnt & 0x7F;
159 out[1] = ((maxRepCnt >> 1) & 0xC0) | maxPtr & 0x3F;
160 out += 2;
161 in += maxRepCnt + 3;
162 if (rawDataNr) {
163 *rawDataPtr = rawDataNr - 1;
164 rawDataNr = 0;
165 }
166 continue;
167 }
168 }
169
170 // Write the uncompressed data
171 rawDataNr++;
172 if (rawDataNr == 1) {
173 rawDataPtr = out;
174 out++;
175 } else if (rawDataNr == 0x80) {
176 *rawDataPtr = 0x7F;
177 rawDataNr = 0;
178 }
179 *out = *in;
180 out++;
181 in++;
182
183 } while (out <= endOut);
184
185 return -1;
186 }
187
188 /* vim: set expandtab tabstop=4 shiftwidth=4 smarttab tw=80 cin: */
189
190