bitblt_g4.c

Mon, 14 Dec 2009 16:18:21 +0000

author
Philip Pemberton <philpem@philpem.me.uk>
date
Mon, 14 Dec 2009 16:18:21 +0000
changeset 172
2fae6df568f6
parent 125
e2ef1c2f9eca
permissions
-rw-r--r--

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 }