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