1 /* Copyright (C) 2001-2019 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, 8 modified or distributed except as expressly authorized under the terms 9 of the license contained in the file LICENSE in this distribution. 10 11 Refer to licensing information at http://www.artifex.com or contact 12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato, 13 CA 94945, U.S.A., +1(415)492-9861, for further information. 14 */ 15 16 17 /* Common definitions for CCITTFax encoding and decoding filters */ 18 19 #ifndef scf_INCLUDED 20 # define scf_INCLUDED 21 22 #include "shc.h" 23 24 /* 25 * The CCITT Group 3 (T.4) and Group 4 (T.6) fax specifications map 26 * run lengths to Huffman codes. White and black have different mappings. 27 * If the run length is 64 or greater, two or more codes are needed: 28 * - One or more 'make-up' codes for 2560 pixels; 29 * - A 'make-up' code that encodes the multiple of 64; 30 * - A 'termination' code for the remainder. 31 * For runs of 63 or less, only the 'termination' code is needed. 32 */ 33 34 /* ------ Encoding tables ------ */ 35 36 /* 37 * The maximum possible length of a scan line is determined by the 38 * requirement that 3 runs have to fit into the stream buffer. 39 * A run of length N requires approximately ceil(N / 2560) makeup codes, 40 * hence 1.5 * ceil(N / 2560) bytes. Taking the largest safe stream 41 * buffer size as 32K, we arrive at the following maximum width: 42 */ 43 #if ARCH_SIZEOF_INT > 2 44 # define cfe_max_width (2560 * 32000 * 2 / 3) 45 #else 46 # define cfe_max_width (max_int - 40) /* avoid overflows */ 47 #endif 48 /* The +5 in cfe_max_code_bytes is a little conservative. */ 49 #define cfe_max_code_bytes(width) ((width) / 2560 * 3 / 2 + 5) 50 51 typedef hce_code cfe_run; 52 53 /* Codes common to 1-D and 2-D encoding. */ 54 /* The decoding algorithms know that EOL is 0....01. */ 55 #define run_eol_code_length 12 56 #define run_eol_code_value 1 57 extern const cfe_run cf_run_eol; 58 typedef struct cf_runs_s { 59 cfe_run termination[64]; 60 cfe_run make_up[41]; 61 } cf_runs; 62 extern const cf_runs 63 cf_white_runs, cf_black_runs; 64 extern const cfe_run cf_uncompressed[6]; 65 extern const cfe_run cf_uncompressed_exit[10]; /* indexed by 2 x length of */ 66 67 /* white run + (1 if next run black, 0 if white) */ 68 /* 1-D encoding. */ 69 extern const cfe_run cf1_run_uncompressed; 70 71 /* 2-D encoding. */ 72 extern const cfe_run cf2_run_pass; 73 74 #define cf2_run_pass_length 4 75 #define cf2_run_pass_value 0x1 76 #define cf2_run_vertical_offset 3 77 extern const cfe_run cf2_run_vertical[7]; /* indexed by b1 - a1 + offset */ 78 extern const cfe_run cf2_run_horizontal; 79 80 #define cf2_run_horizontal_value 1 81 #define cf2_run_horizontal_length 3 82 extern const cfe_run cf2_run_uncompressed; 83 84 /* 2-D Group 3 encoding. */ 85 extern const cfe_run cf2_run_eol_1d; 86 extern const cfe_run cf2_run_eol_2d; 87 88 /* ------ Decoding tables ------ */ 89 90 typedef hcd_code cfd_node; 91 92 #define run_length value 93 94 /* 95 * The value in the decoding tables is either a white or black run length, 96 * or a (negative) exceptional value. 97 */ 98 #define run_error (-1) 99 #define run_zeros (-2) /* EOL follows, possibly with more padding first */ 100 #define run_uncompressed (-3) 101 /* 2-D codes */ 102 #define run2_pass (-4) 103 #define run2_horizontal (-5) 104 105 #define cfd_white_initial_bits 8 106 #define cfd_white_min_bits 4 /* shortest white run */ 107 extern const cfd_node cf_white_decode[]; 108 109 #define cfd_black_initial_bits 7 110 #define cfd_black_min_bits 2 /* shortest black run */ 111 extern const cfd_node cf_black_decode[]; 112 113 #define cfd_2d_initial_bits 7 114 #define cfd_2d_min_bits 4 /* shortest non-H/V 2-D run */ 115 extern const cfd_node cf_2d_decode[]; 116 117 #define cfd_uncompressed_initial_bits 6 /* must be 6 */ 118 extern const cfd_node cf_uncompressed_decode[]; 119 120 /* ------ Run detection macros ------ */ 121 122 /* 123 * For the run detection macros: 124 * white_byte is 0 or 0xff for BlackIs1 or !BlackIs1 respectively; 125 * data holds p[-1], inverted if !BlackIs1; 126 * count is the number of valid bits remaining in the scan line. 127 */ 128 129 /* Aliases for bit processing tables. */ 130 #define cf_byte_run_length byte_bit_run_length_neg 131 #define cf_byte_run_length_0 byte_bit_run_length_0 132 133 /* Skip over white pixels to find the next black pixel in the input. */ 134 /* Store the run length in rlen, and update data, p, and count. */ 135 /* There are many more white pixels in typical input than black pixels, */ 136 /* and the runs of white pixels tend to be much longer, so we use */ 137 /* substantially different loops for the two cases. */ 138 139 /* As an experiment, various different versions of this macro were tried. 140 * Firstly, this macro was updated to use native int sized accesses. 141 * Sadly, in our tests, this did not result in a speedup, presumably because 142 * we did not have long enough runs to make this a win. We therefore disable 143 * this version of the macro here, but leave it in the source code in case it 144 * becomes useful in future. 145 */ 146 #undef SKIP_PIXELS_USING_INTS 147 148 /* Secondly, as a stepping stone towards the int version, the macro was 149 * updated to make more explicit use of pointer arithmetic, and to remove the 150 * 'load 4 bytes, combine and test' section. This version is expected to be 151 * better on platforms such as ARM. 152 */ 153 #undef SKIP_PIXELS_USING_POINTER_ARITHMETIC 154 155 #if defined(SKIP_PIXELS_USING_INTS) && (ARCH_LOG2_SIZEOF_INT >= 2) && (ARCH_ALIGN_INT_MOD <= 4) && (ARCH_LOG2_SIZEOF_SHORT >= 1) && (ARCH_ALIGN_SHORT_MOD <= 2) 156 157 #if ARCH_IS_BIG_ENDIAN 158 #define BYTE0OF2(S) ((byte)(S>>8)) 159 #define BYTE1OF2(S) ((byte)S) 160 #define BYTE0OF4(S) ((byte)(S>>24)) 161 #define BYTE1OF4(S) ((byte)(S>>16)) 162 #define BYTE2OF4(S) ((byte)(S>>8)) 163 #define BYTE3OF4(S) ((byte)S) 164 #else 165 #define BYTE0OF2(S) ((byte)S) 166 #define BYTE1OF2(S) ((byte)(S>>8)) 167 #define BYTE0OF4(S) ((byte)S) 168 #define BYTE1OF4(S) ((byte)(S>>8)) 169 #define BYTE2OF4(S) ((byte)(S>>16)) 170 #define BYTE3OF4(S) ((byte)(S>>24)) 171 #endif 172 173 #define skip_white_pixels(data, p, count, white_byte, rlen)\ 174 BEGIN\ 175 rlen = cf_byte_run_length[count & 7][data ^ 0xff];\ 176 if ( rlen >= 8 ) { /* run extends past byte boundary */\ 177 if ( white_byte == 0 ) {\ 178 register short s;\ 179 if ( (data = *p++) ) { rlen -= 8; }\ 180 else if ( (data = *p++) ) { }\ 181 else if ((((int)p) & 1) && (rlen += 8, (data = *p++))) { }\ 182 else if ((((int)p) & 2) && (rlen += 16, p += 2, (s = *(short *)(void *)(p-2)))) {\ 183 if ((data = BYTE0OF2(s))) {rlen -= 8; p--;} else data = BYTE1OF2(s); }\ 184 else {\ 185 register int i;\ 186 while ((p += 4, (i = *(int *)(void *)(p-4))) == 0) rlen += 32; \ 187 if ( (data = BYTE0OF4(i)) ) { rlen += 8; p -= 3; }\ 188 else if ( (data = BYTE1OF4(i)) ) { rlen += 16; p -= 2; }\ 189 else if ( (data = BYTE2OF4(i)) ) { rlen += 24; p -= 1; }\ 190 else { data = BYTE3OF4(i); rlen += 32; }\ 191 }\ 192 } else {\ 193 register short s;\ 194 if ( (data = (byte)~*p++) ) { rlen -= 8; }\ 195 else if ( (data = (byte)~*p++) ) { }\ 196 else if ((((int)p) & 1) && (rlen += 8, data = (byte)~*p++)) { }\ 197 else if ((((int)p) & 2) && (rlen += 16, p += 2, s = (short)~*(short *)(void *)(p-2))) {\ 198 if ((data = BYTE0OF2(s))) {rlen -= 8; p--;} else data = BYTE1OF2(s); }\ 199 else {\ 200 register int i;\ 201 while ((p += 4, (i = ~*(int *)(void *)(p-4))) == 0) rlen += 32; \ 202 if ( (data = BYTE0OF4(i)) ) { rlen += 8; p -= 3; }\ 203 else if ( (data = BYTE1OF4(i)) ) { rlen += 16; p -= 2; }\ 204 else if ( (data = BYTE2OF4(i)) ) { rlen += 24; p -= 1; }\ 205 else { data = BYTE3OF4(i); rlen += 32; }\ 206 }\ 207 }\ 208 rlen += cf_byte_run_length_0[data ^ 0xff];\ 209 }\ 210 count -= rlen;\ 211 END 212 213 #elif defined(SKIP_PIXELS_USING_PTR_ARITHMETIC) 214 215 #define skip_white_pixels(data, p, count, white_byte, rlen)\ 216 BEGIN\ 217 rlen = cf_byte_run_length[count & 7][data ^ 0xff];\ 218 if ( rlen >= 8 ) { /* run extends past byte boundary */\ 219 if ( white_byte == 0 ) {\ 220 if ( data = *p++ ) { rlen -= 8; }\ 221 else if ( data = *p++ ) { }\ 222 else {\ 223 do {\ 224 if ( data = *p++ ) { rlen += 8; break; }\ 225 else if ( data = *p++ ) { rlen += 16; break; }\ 226 else if ( data = *p++ ) { rlen += 24; break; }\ 227 else { rlen += 32; if (data = *p++) break; }\ 228 } while (1);\ 229 }\ 230 } else {\ 231 if ( data = (byte)~*p++ ) { rlen -= 8; }\ 232 else if ( data = (byte)~*p++ ) { }\ 233 else {\ 234 do {\ 235 if ( data = (byte)~*p++ ) { rlen += 8; break; }\ 236 else if ( data = (byte)~*p++ ) { rlen += 16; break; }\ 237 else if ( data = (byte)~*p++ ) { rlen += 24; break; }\ 238 else { rlen += 32; if (data = (byte)~*p++) break; }\ 239 } while (1);\ 240 }\ 241 }\ 242 rlen += cf_byte_run_length_0[data ^ 0xff];\ 243 }\ 244 count -= rlen;\ 245 END 246 247 #else 248 249 /* Original version */ 250 #define skip_white_pixels(data, p, count, white_byte, rlen)\ 251 BEGIN\ 252 rlen = cf_byte_run_length[count & 7][data ^ 0xff];\ 253 if ( rlen >= 8 ) { /* run extends past byte boundary */\ 254 if ( white_byte == 0 ) {\ 255 if ( p[0] ) { data = p[0]; p += 1; rlen -= 8; }\ 256 else if ( p[1] ) { data = p[1]; p += 2; }\ 257 else {\ 258 while ( !(p[2] | p[3] | p[4] | p[5]) )\ 259 p += 4, rlen += 32;\ 260 if ( p[2] ) {\ 261 data = p[2]; p += 3; rlen += 8;\ 262 } else if ( p[3] ) {\ 263 data = p[3]; p += 4; rlen += 16;\ 264 } else if ( p[4] ) {\ 265 data = p[4]; p += 5; rlen += 24;\ 266 } else /* p[5] */ {\ 267 data = p[5]; p += 6; rlen += 32;\ 268 }\ 269 }\ 270 } else {\ 271 if ( p[0] != 0xff ) { data = (byte)~p[0]; p += 1; rlen -= 8; }\ 272 else if ( p[1] != 0xff ) { data = (byte)~p[1]; p += 2; }\ 273 else {\ 274 while ( (p[2] & p[3] & p[4] & p[5]) == 0xff )\ 275 p += 4, rlen += 32;\ 276 if ( p[2] != 0xff ) {\ 277 data = (byte)~p[2]; p += 3; rlen += 8;\ 278 } else if ( p[3] != 0xff ) {\ 279 data = (byte)~p[3]; p += 4; rlen += 16;\ 280 } else if ( p[4] != 0xff ) {\ 281 data = (byte)~p[4]; p += 5; rlen += 24;\ 282 } else /* p[5] != 0xff */ {\ 283 data = (byte)~p[5]; p += 6; rlen += 32;\ 284 }\ 285 }\ 286 }\ 287 rlen += cf_byte_run_length_0[data ^ 0xff];\ 288 }\ 289 count -= rlen;\ 290 END 291 #endif 292 293 /* Skip over black pixels to find the next white pixel in the input. */ 294 /* Store the run length in rlen, and update data, p, and count. */ 295 296 #define skip_black_pixels(data, p, count, white_byte, rlen)\ 297 BEGIN\ 298 rlen = cf_byte_run_length[count & 7][data];\ 299 if ( rlen >= 8 ) {\ 300 if ( white_byte == 0 )\ 301 for ( ; ; p += 4, rlen += 32 ) {\ 302 if ( p[0] != 0xff ) { data = p[0]; p += 1; rlen -= 8; break; }\ 303 if ( p[1] != 0xff ) { data = p[1]; p += 2; break; }\ 304 if ( p[2] != 0xff ) { data = p[2]; p += 3; rlen += 8; break; }\ 305 if ( p[3] != 0xff ) { data = p[3]; p += 4; rlen += 16; break; }\ 306 }\ 307 else\ 308 for ( ; ; p += 4, rlen += 32 ) {\ 309 if ( p[0] ) { data = (byte)~p[0]; p += 1; rlen -= 8; break; }\ 310 if ( p[1] ) { data = (byte)~p[1]; p += 2; break; }\ 311 if ( p[2] ) { data = (byte)~p[2]; p += 3; rlen += 8; break; }\ 312 if ( p[3] ) { data = (byte)~p[3]; p += 4; rlen += 16; break; }\ 313 }\ 314 rlen += cf_byte_run_length_0[data];\ 315 }\ 316 count -= rlen;\ 317 END 318 319 #endif /* scf_INCLUDED */ 320