1 #include "mupdf/fitz.h"
2
3 /* Fax G3/G4 tables */
4
5 typedef struct
6 {
7 unsigned short code;
8 unsigned short nbits;
9 } cfe_code;
10
11 typedef struct {
12 cfe_code termination[64];
13 cfe_code makeup[41];
14 } cf_runs;
15
16 /* Define the end-of-line code. */
17 static const cfe_code cf_run_eol = {1, 12};
18
19 /* Define the 2-D run codes. */
20 static const cfe_code cf2_run_pass = {0x1, 4};
21 static const cfe_code cf2_run_vertical[7] =
22 {
23 {0x3, 7},
24 {0x3, 6},
25 {0x3, 3},
26 {0x1, 1},
27 {0x2, 3},
28 {0x2, 6},
29 {0x2, 7}
30 };
31 static const cfe_code cf2_run_horizontal = {1, 3};
32
33 /* White run codes. */
34 static const cf_runs cf_white_runs =
35 {
36 /* Termination codes */
37 {
38 {0x35, 8}, {0x7, 6}, {0x7, 4}, {0x8, 4},
39 {0xb, 4}, {0xc, 4}, {0xe, 4}, {0xf, 4},
40 {0x13, 5}, {0x14, 5}, {0x7, 5}, {0x8, 5},
41 {0x8, 6}, {0x3, 6}, {0x34, 6}, {0x35, 6},
42 {0x2a, 6}, {0x2b, 6}, {0x27, 7}, {0xc, 7},
43 {0x8, 7}, {0x17, 7}, {0x3, 7}, {0x4, 7},
44 {0x28, 7}, {0x2b, 7}, {0x13, 7}, {0x24, 7},
45 {0x18, 7}, {0x2, 8}, {0x3, 8}, {0x1a, 8},
46 {0x1b, 8}, {0x12, 8}, {0x13, 8}, {0x14, 8},
47 {0x15, 8}, {0x16, 8}, {0x17, 8}, {0x28, 8},
48 {0x29, 8}, {0x2a, 8}, {0x2b, 8}, {0x2c, 8},
49 {0x2d, 8}, {0x4, 8}, {0x5, 8}, {0xa, 8},
50 {0xb, 8}, {0x52, 8}, {0x53, 8}, {0x54, 8},
51 {0x55, 8}, {0x24, 8}, {0x25, 8}, {0x58, 8},
52 {0x59, 8}, {0x5a, 8}, {0x5b, 8}, {0x4a, 8},
53 {0x4b, 8}, {0x32, 8}, {0x33, 8}, {0x34, 8}
54 },
55
56 /* Make-up codes */
57 {
58 {0, 0} /* dummy */ , {0x1b, 5}, {0x12, 5}, {0x17, 6},
59 {0x37, 7}, {0x36, 8}, {0x37, 8}, {0x64, 8},
60 {0x65, 8}, {0x68, 8}, {0x67, 8}, {0xcc, 9},
61 {0xcd, 9}, {0xd2, 9}, {0xd3, 9}, {0xd4, 9},
62 {0xd5, 9}, {0xd6, 9}, {0xd7, 9}, {0xd8, 9},
63 {0xd9, 9}, {0xda, 9}, {0xdb, 9}, {0x98, 9},
64 {0x99, 9}, {0x9a, 9}, {0x18, 6}, {0x9b, 9},
65 {0x8, 11}, {0xc, 11}, {0xd, 11}, {0x12, 12},
66 {0x13, 12}, {0x14, 12}, {0x15, 12}, {0x16, 12},
67 {0x17, 12}, {0x1c, 12}, {0x1d, 12}, {0x1e, 12},
68 {0x1f, 12}
69 }
70 };
71
72 /* Black run codes. */
73 static const cf_runs cf_black_runs =
74 {
75 /* Termination codes */
76 {
77 {0x37, 10}, {0x2, 3}, {0x3, 2}, {0x2, 2},
78 {0x3, 3}, {0x3, 4}, {0x2, 4}, {0x3, 5},
79 {0x5, 6}, {0x4, 6}, {0x4, 7}, {0x5, 7},
80 {0x7, 7}, {0x4, 8}, {0x7, 8}, {0x18, 9},
81 {0x17, 10}, {0x18, 10}, {0x8, 10}, {0x67, 11},
82 {0x68, 11}, {0x6c, 11}, {0x37, 11}, {0x28, 11},
83 {0x17, 11}, {0x18, 11}, {0xca, 12}, {0xcb, 12},
84 {0xcc, 12}, {0xcd, 12}, {0x68, 12}, {0x69, 12},
85 {0x6a, 12}, {0x6b, 12}, {0xd2, 12}, {0xd3, 12},
86 {0xd4, 12}, {0xd5, 12}, {0xd6, 12}, {0xd7, 12},
87 {0x6c, 12}, {0x6d, 12}, {0xda, 12}, {0xdb, 12},
88 {0x54, 12}, {0x55, 12}, {0x56, 12}, {0x57, 12},
89 {0x64, 12}, {0x65, 12}, {0x52, 12}, {0x53, 12},
90 {0x24, 12}, {0x37, 12}, {0x38, 12}, {0x27, 12},
91 {0x28, 12}, {0x58, 12}, {0x59, 12}, {0x2b, 12},
92 {0x2c, 12}, {0x5a, 12}, {0x66, 12}, {0x67, 12}
93 },
94
95 /* Make-up codes. */
96 {
97 {0, 0} /* dummy */ , {0xf, 10}, {0xc8, 12}, {0xc9, 12},
98 {0x5b, 12}, {0x33, 12}, {0x34, 12}, {0x35, 12},
99 {0x6c, 13}, {0x6d, 13}, {0x4a, 13}, {0x4b, 13},
100 {0x4c, 13}, {0x4d, 13}, {0x72, 13}, {0x73, 13},
101 {0x74, 13}, {0x75, 13}, {0x76, 13}, {0x77, 13},
102 {0x52, 13}, {0x53, 13}, {0x54, 13}, {0x55, 13},
103 {0x5a, 13}, {0x5b, 13}, {0x64, 13}, {0x65, 13},
104 {0x8, 11}, {0xc, 11}, {0xd, 11}, {0x12, 12},
105 {0x13, 12}, {0x14, 12}, {0x15, 12}, {0x16, 12},
106 {0x17, 12}, {0x1c, 12}, {0x1d, 12}, {0x1e, 12},
107 {0x1f, 12}
108 }
109 };
110
111 static inline int
getbit(const unsigned char * buf,int x)112 getbit(const unsigned char *buf, int x)
113 {
114 /* Invert bit to handle BlackIs1=false */
115 return ( ( buf[x >> 3] >> ( 7 - (x & 7) ) ) & 1 ) ^ 1;
116 }
117
118 static inline int
find_changing(const unsigned char * line,int x,int w)119 find_changing(const unsigned char *line, int x, int w)
120 {
121 int a, b;
122
123 if (!line || x >= w)
124 return w;
125
126 if (x == -1)
127 {
128 a = 0;
129 x = 0;
130 }
131 else
132 {
133 a = getbit(line, x);
134 x++;
135 }
136 while (x < w)
137 {
138 b = getbit(line, x);
139 if (a != b)
140 break;
141 x++;
142 }
143
144 return x;
145 }
146
147 static inline int
find_changing_color(const unsigned char * line,int x,int w,int color)148 find_changing_color(const unsigned char *line, int x, int w, int color)
149 {
150 if (!line || x >= w)
151 return w;
152 x = find_changing(line, x, w);
153 if (x < w && getbit(line, x) != color)
154 x = find_changing(line, x, w);
155 return x;
156 }
157
158 static inline int
getrun(const unsigned char * line,int x,int w,int c)159 getrun(const unsigned char *line, int x, int w, int c)
160 {
161 int z = x;
162 while (z < w)
163 {
164 int b = getbit(line, z);
165 if (c != b)
166 break;
167 ++z;
168 }
169 return z - x;
170 }
171
172 static inline void
putcode(fz_context * ctx,fz_buffer * out,const cfe_code * run)173 putcode(fz_context *ctx, fz_buffer *out, const cfe_code *run)
174 {
175 fz_append_bits(ctx, out, run->code, run->nbits);
176 }
177
178 static void
putrun(fz_context * ctx,fz_buffer * out,int run,int c)179 putrun(fz_context *ctx, fz_buffer *out, int run, int c)
180 {
181 const cf_runs *codetable = c ? &cf_black_runs : &cf_white_runs;
182 if (run > 63)
183 {
184 int m = run >> 6;
185 while (m > 40)
186 {
187 putcode(ctx, out, &codetable->makeup[40]);
188 m -= 40;
189 }
190 if (m > 0)
191 putcode(ctx, out, &codetable->makeup[m]);
192 putcode(ctx, out, &codetable->termination[run & 63]);
193 }
194 else
195 {
196 putcode(ctx, out, &codetable->termination[run]);
197 }
198 }
199
200 fz_buffer *
fz_compress_ccitt_fax_g4(fz_context * ctx,const unsigned char * src,int columns,int rows)201 fz_compress_ccitt_fax_g4(fz_context *ctx, const unsigned char *src, int columns, int rows)
202 {
203 int stride = (columns + 7) >> 3;
204 fz_buffer *out = fz_new_buffer(ctx, (stride * rows) >> 3);
205 const unsigned char *ref = NULL;
206
207 fz_try(ctx)
208 {
209 while (rows-- > 0)
210 {
211 int a0 = -1;
212 int c = 0;
213
214 while (a0 < columns)
215 {
216 int a1 = find_changing(src, a0, columns);
217 int b1 = find_changing_color(ref, a0, columns, c^1);
218 int b2 = find_changing(ref, b1, columns);
219 int diff = b1 - a1;
220 if (a0 < 0)
221 a0 = 0;
222
223 /* pass mode */
224 if (b2 < a1)
225 {
226 putcode(ctx, out, &cf2_run_pass);
227 a0 = b2;
228 }
229
230 /* vertical mode */
231 else if (diff >= -3 && diff <= 3)
232 {
233 putcode(ctx, out, &cf2_run_vertical[diff + 3]);
234 a0 = a1;
235 c = c^1;
236 }
237
238 /* horizontal mode */
239 else
240 {
241 int a2 = find_changing(src, a1, columns);
242 putcode(ctx, out, &cf2_run_horizontal);
243 putrun(ctx, out, a1 - a0, c);
244 putrun(ctx, out, a2 - a1, c^1);
245 a0 = a2;
246 }
247 }
248
249 ref = src;
250 src += stride;
251 }
252
253 putcode(ctx, out, &cf_run_eol);
254 putcode(ctx, out, &cf_run_eol);
255 }
256 fz_catch(ctx)
257 {
258 fz_drop_buffer(ctx, out);
259 fz_rethrow(ctx);
260 }
261
262 return out;
263 }
264
265 fz_buffer *
fz_compress_ccitt_fax_g3(fz_context * ctx,const unsigned char * src,int columns,int rows)266 fz_compress_ccitt_fax_g3(fz_context *ctx, const unsigned char *src, int columns, int rows)
267 {
268 int stride = (columns + 7) >> 3;
269 fz_buffer *out = fz_new_buffer(ctx, (stride * rows) >> 3);
270 int i;
271
272 fz_try(ctx)
273 {
274 while (rows-- > 0)
275 {
276 int a0 = 0;
277 int c = 0;
278 while (a0 < columns)
279 {
280 int run = getrun(src, a0, columns, c);
281 putrun(ctx, out, run, c);
282 a0 += run;
283 c = c^1;
284 }
285 src += stride;
286 }
287
288 for (i = 0; i < 6; ++i)
289 putcode(ctx, out, &cf_run_eol);
290 }
291 fz_catch(ctx)
292 {
293 fz_drop_buffer(ctx, out);
294 fz_rethrow(ctx);
295 }
296
297 return out;
298 }
299