1 /* Copyright (C) 1995, 1996, 1997, 1998 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: srle.c,v 1.4 2002/02/21 22:24:54 giles Exp $ */ 18 /* RunLengthEncode filter */ 19 #include "stdio_.h" /* includes std.h */ 20 #include "memory_.h" 21 #include "strimpl.h" 22 #include "srlx.h" 23 24 /* ------ RunLengthEncode ------ */ 25 26 private_st_RLE_state(); 27 28 /* Set defaults */ 29 private void 30 s_RLE_set_defaults(stream_state * st) 31 { 32 stream_RLE_state *const ss = (stream_RLE_state *) st; 33 34 s_RLE_set_defaults_inline(ss); 35 } 36 37 /* Initialize */ 38 private int 39 s_RLE_init(stream_state * st) 40 { 41 stream_RLE_state *const ss = (stream_RLE_state *) st; 42 43 return s_RLE_init_inline(ss); 44 } 45 46 /* Process a buffer */ 47 private int 48 s_RLE_process(stream_state * st, stream_cursor_read * pr, 49 stream_cursor_write * pw, bool last) 50 { 51 stream_RLE_state *const ss = (stream_RLE_state *) st; 52 register const byte *p = pr->ptr; 53 register byte *q = pw->ptr; 54 const byte *rlimit = pr->limit; 55 byte *wlimit = pw->limit; 56 int status = 0; 57 ulong rleft = ss->record_left; 58 59 /* 60 * We thought that the Genoa CET demands that the output from this 61 * filter be not just legal, but optimal, so we went to the trouble 62 * of ensuring this. It turned out that this wasn't actually 63 * necessary, but we didn't want to change the code back. 64 * 65 * For optimal output, we can't just break runs at buffer 66 * boundaries: unless we hit a record boundary or the end of the 67 * input, we have to look ahead far enough to know that we aren't 68 * breaking a run prematurely. 69 */ 70 71 /* Check for leftover output. */ 72 copy: 73 if (ss->copy_left) { 74 uint rcount = rlimit - p; 75 uint wcount = wlimit - q; 76 uint count = ss->copy_left; 77 78 if (rcount < count) 79 count = rcount; 80 if (wcount < count) 81 count = wcount; 82 if (rleft < count) 83 count = rleft; 84 memcpy(q + 1, p + 1, count); 85 pr->ptr = p += count; 86 pw->ptr = q += count; 87 if ((ss->record_left = rleft -= count) == 0) 88 ss->record_left = rleft = ss->record_size; 89 if ((ss->copy_left -= count) != 0) 90 return (rcount == 0 ? 0 : 1); 91 } 92 while (p < rlimit) { 93 const byte *beg = p; 94 const byte *p1; 95 uint count = rlimit - p; 96 bool end = last; 97 byte next; 98 99 if (count > rleft) 100 count = rleft, end = true; 101 if (count > 128) 102 count = 128, end = true; 103 p1 = p + count - 1; 104 if (count < 3) { 105 if (!end || count == 0) 106 break; /* can't look ahead far enough */ 107 if (count == 1) { 108 if (wlimit - q < 2) { 109 status = 1; 110 break; 111 } 112 *++q = 0; 113 } else { /* count == 2 */ 114 if (p[1] == p[2]) { 115 if (wlimit - q < 2) { 116 status = 1; 117 break; 118 } 119 *++q = 255; 120 } else { 121 if (wlimit - q < 3) { 122 status = 1; 123 break; 124 } 125 *++q = 1; 126 *++q = p[1]; 127 } 128 } 129 *++q = p1[1]; 130 p = p1 + 1; 131 } else if ((next = p[1]) == p[2] && next == p[3]) { 132 if (wlimit - q < 2) { 133 status = 1; 134 break; 135 } 136 /* Recognize leading repeated byte */ 137 do { 138 p++; 139 } 140 while (p < p1 && p[2] == next); 141 if (p == p1 && !end) { 142 p = beg; /* need to look ahead further */ 143 break; 144 } 145 p++; 146 *++q = (byte) (257 - (p - beg)); 147 *++q = next; 148 } else { 149 p1--; 150 while (p < p1 && (p[2] != p[1] || p[3] != p[1])) 151 p++; 152 if (p == p1) { 153 if (!end) { 154 p = beg; /* need to look ahead further */ 155 break; 156 } 157 p += 2; 158 } 159 count = p - beg; 160 if (wlimit - q < count + 1) { 161 p = beg; 162 if (q >= wlimit) { 163 status = 1; 164 break; 165 } 166 /* Copy some now and some later. */ 167 *++q = count - 1; 168 ss->copy_left = count; 169 goto copy; 170 } 171 *++q = count - 1; 172 memcpy(q + 1, beg + 1, count); 173 q += count; 174 } 175 rleft -= p - beg; 176 if (rleft == 0) 177 rleft = ss->record_size; 178 } 179 if (last && status == 0 && ss->EndOfData) { 180 if (q < wlimit) 181 *++q = 128; 182 else 183 status = 1; 184 } 185 pr->ptr = p; 186 pw->ptr = q; 187 ss->record_left = rleft; 188 return status; 189 } 190 191 /* Stream template */ 192 const stream_template s_RLE_template = { 193 &st_RLE_state, s_RLE_init, s_RLE_process, 129, 2, NULL, 194 s_RLE_set_defaults, s_RLE_init 195 }; 196