1 /*
2 * tumble: build a PDF file from image files
3 *
4 * G4 compression
5 * Copyright 2003, 2017 Eric Smith <spacewar@gmail.com>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License version 2 as
9 * published by the Free Software Foundation. Note that permission is
10 * not granted to redistribute this program under the terms of any
11 * other version of the General Public License.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
21 *
22 * 2007-06-20 [JDB] Fixed a bug wherein "g4_get_pixel" is called with pixel
23 * index == width, causing an index off the end of the array
24 * if width % BITS_PER_WORD == 0.
25 */
26
27
28 #define G4_DEBUG 0
29
30
31 #include <stdbool.h>
32 #include <stdint.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36
37
38 #include "bitblt.h"
39 #include "bitblt_tables.h"
40 #include "pdf_util.h"
41
42
43 #include "g4_tables.h"
44
45
46 #define BIT_BUF_SIZE 4096
47
48 struct bit_buffer
49 {
50 FILE *f;
51 uint32_t byte_idx; /* index to next byte position in data buffer */
52 uint32_t bit_idx; /* one greater than the next bit position in data buffer,
53 8 = MSB, 1 = LSB */
54 uint8_t data [BIT_BUF_SIZE];
55 };
56
57
init_bit_buffer(struct bit_buffer * buf)58 static void init_bit_buffer (struct bit_buffer *buf)
59 {
60 buf->byte_idx = 0;
61 buf->bit_idx = 8;
62 memset (& buf->data [0], 0, BIT_BUF_SIZE);
63 }
64
65
flush_bits(struct bit_buffer * buf)66 static void flush_bits (struct bit_buffer *buf)
67 {
68 size_t s;
69 if (buf->bit_idx != 8)
70 {
71 buf->byte_idx++;
72 buf->bit_idx = 8;
73 }
74 s = fwrite (& buf->data [0], 1, buf->byte_idx, buf->f);
75 /* $$$ should check result */
76 init_bit_buffer (buf);
77 }
78
79
advance_byte(struct bit_buffer * buf)80 static void advance_byte (struct bit_buffer *buf)
81 {
82 buf->byte_idx++;
83 buf->bit_idx = 8;
84 if (buf->byte_idx == BIT_BUF_SIZE)
85 flush_bits (buf);
86 }
87
88
write_bits(struct bit_buffer * buf,uint32_t count,uint32_t bits)89 static void write_bits (struct bit_buffer *buf,
90 uint32_t count,
91 uint32_t bits)
92 {
93 while (count > buf->bit_idx)
94 {
95 buf->data [buf->byte_idx] |= bits >> (count - buf->bit_idx);
96 count -= buf->bit_idx;
97 advance_byte (buf);
98 }
99
100 bits &= ((1 << count) - 1);
101 buf->data [buf->byte_idx] |= bits << (buf->bit_idx - count);
102 buf->bit_idx -= count;
103 if (buf->bit_idx == 0)
104 advance_byte (buf);
105 }
106
107
g4_encode_horizontal_run(struct bit_buffer * buf,bool black,uint32_t run_length)108 static void g4_encode_horizontal_run (struct bit_buffer *buf,
109 bool black,
110 uint32_t run_length)
111 {
112 uint32_t i;
113
114 while (run_length >= 2560)
115 {
116 write_bits (buf, 12, 0x01f);
117 run_length -= 2560;
118 }
119
120 if (run_length >= 1792)
121 {
122 i = (run_length - 1792) >> 6;
123 write_bits (buf,
124 g4_long_makeup_code [i].count,
125 g4_long_makeup_code [i].bits);
126 run_length -= (1792 + (i << 6));
127 }
128 else if (run_length >= 64)
129 {
130 i = (run_length >> 6) - 1;
131 write_bits (buf,
132 g4_makeup_code [black] [i].count,
133 g4_makeup_code [black] [i].bits);
134 run_length -= (i + 1) << 6;
135 }
136
137 write_bits (buf,
138 g4_h_code [black] [run_length].count,
139 g4_h_code [black] [run_length].bits);
140 }
141
142
g4_get_pixel(uint8_t * buf,uint32_t x)143 static inline int g4_get_pixel (uint8_t *buf, uint32_t x)
144 {
145 return ((buf [x >> 3] >> (x & 7)) & 1);
146 }
147
148
149 #define not_aligned(p) (((word_t) p) & (sizeof (word_t) - 1))
150
151
g4_find_pixel(uint8_t * buf,uint32_t pos,uint32_t width,bool color)152 static uint32_t g4_find_pixel (uint8_t *buf,
153 uint32_t pos,
154 uint32_t width,
155 bool color)
156 {
157 uint8_t *p = buf + pos / 8;
158 int bit = pos & 7;
159 uint8_t *max_p = buf + (width - 1) / 8;
160 uint8_t d;
161
162 /* check first byte (may be partial) */
163 d = *p;
164 if (! color)
165 d = ~d;
166 bit += rle_tab [bit][d];
167 if (bit < 8)
168 goto done;
169 p++;
170
171 /* check individual bytes until we hit word alignment */
172 while ((p <= max_p) && not_aligned (p))
173 {
174 d = *p;
175 if (! color)
176 d = ~d;
177 if (d != 0)
178 goto found;
179 p++;
180 }
181
182 /* check aligned words in middle */
183 while ((p <= (max_p - sizeof (word_t))))
184 {
185 word_t w = *((word_t *) p);
186 if (! color)
187 w = ~w;
188 if (w != 0)
189 break;
190 p += sizeof (word_t);
191 }
192
193 /* check trailing bytes */
194 while (p <= max_p)
195 {
196 d = *p;
197 if (! color)
198 d = ~d;
199 if (d)
200 goto found;
201 p++;
202 }
203
204 goto not_found;
205
206 found:
207 bit = rle_tab [0][d];
208
209 done:
210 pos = ((p - buf) << 3) + bit;
211 if (pos < width)
212 return (pos);
213
214 not_found:
215 return (width);
216 }
217
218
g4_encode_row(struct bit_buffer * buf,uint32_t width,uint8_t * ref,uint8_t * row)219 static void g4_encode_row (struct bit_buffer *buf,
220 uint32_t width,
221 uint8_t *ref,
222 uint8_t *row)
223 {
224 uint32_t a0, a1, a2;
225 uint32_t b1, b2;
226 bool a0_c;
227
228 a0 = 0;
229 a0_c = 0;
230
231 a1 = g4_find_pixel (row, 0, width, 1);
232
233 b1 = g4_find_pixel (ref, 0, width, 1);
234
235 #if (G4_DEBUG & 1)
236 fprintf (stderr, "start of row\n");
237 if ((a1 != width) || (b1 != width))
238 {
239 fprintf (stderr, "a1 = %u, b1 = %u\n", a1, b1);
240 }
241 #endif
242
243 while (a0 < width)
244 {
245 b2 = g4_find_pixel (ref, b1 + 1, width, ! g4_get_pixel (ref, b1));
246
247 if (b2 < a1)
248 {
249 /* pass mode - 0001 */
250 write_bits (buf, 4, 0x1);
251 a0 = b2;
252 #if (G4_DEBUG & 1)
253 fprintf (stderr, "pass\n");
254 #endif
255 }
256 else if (abs (a1 - b1) <= 3)
257 {
258 /* vertical mode */
259 write_bits (buf,
260 g4_vert_code [3 + a1 - b1].count,
261 g4_vert_code [3 + a1 - b1].bits);
262 a0 = a1;
263 #if (G4_DEBUG & 1)
264 fprintf (stderr, "vertical %d\n", a1 - b1);
265 #endif
266 }
267 else
268 {
269 /* horizontal mode - 001 */
270 a2 = g4_find_pixel (row, a1 + 1, width, a0_c);
271 write_bits (buf, 3, 0x1);
272 g4_encode_horizontal_run (buf, a0_c, a1 - a0);
273 g4_encode_horizontal_run (buf, ! a0_c, a2 - a1);
274 #if (G4_DEBUG & 1)
275 fprintf (stderr, "horizontal %d %s, %d %s\n",
276 a1 - a0, a0_c ? "black" : "white",
277 a2 - a1, a0_c ? "white" : "black");
278 #endif
279 a0 = a2;
280 }
281
282 if (a0 >= width)
283 break;;
284
285 a0_c = g4_get_pixel (row, a0);
286
287 a1 = g4_find_pixel (row, a0 + 1, width, ! a0_c);
288 b1 = g4_find_pixel (ref, a0 + 1, width, ! g4_get_pixel (ref, a0));
289 if (g4_get_pixel (ref, b1) == a0_c)
290 b1 = g4_find_pixel (ref, b1 + 1, width, ! a0_c);
291 #if (G4_DEBUG & 1)
292 fprintf (stderr, "a1 = %u, b1 = %u\n", a1, b1);
293 #endif
294 }
295 }
296
297
bitblt_write_g4(Bitmap * bitmap,FILE * f)298 void bitblt_write_g4 (Bitmap *bitmap, FILE *f)
299 {
300 uint32_t width = bitmap->rect.max.x - bitmap->rect.min.x;
301 uint32_t row;
302 struct bit_buffer bb;
303
304 word_t *temp_buffer;
305
306 word_t *cur_line;
307 word_t *ref_line; /* reference (previous) row */
308
309 temp_buffer = pdf_calloc (width / BITS_PER_WORD + 1,
310 sizeof (word_t));
311
312 cur_line = bitmap->bits;
313 ref_line = temp_buffer;
314
315 init_bit_buffer (& bb);
316
317 bb.f = f;
318
319 for (row = bitmap->rect.min.y;
320 row < bitmap->rect.max.y;
321 row++)
322 {
323 g4_encode_row (& bb,
324 width,
325 (uint8_t *) ref_line,
326 (uint8_t *) cur_line);
327 ref_line = cur_line;
328 cur_line += bitmap->row_words;
329 }
330
331
332 /* write EOFB code */
333 write_bits (& bb, 24, 0x001001);
334
335 flush_bits (& bb);
336
337 free (temp_buffer);
338 }
339
340
341