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