bitblt_g4.c

Wed, 12 Mar 2003 10:59:29 +0000

author
eric
date
Wed, 12 Mar 2003 10:59:29 +0000
changeset 110
cb75ec9430b4
parent 95
851a04fa5324
child 115
dba0804a5871
permissions
-rw-r--r--

optimized g4_find_pixel().

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