1 /* OpenCP Module Player 2 * copyright (c) 2021 Stian Skjelstad <stian.skjelstad@gmail.com> 3 * 4 * Code is partially based on unlzw implementation from gzip 1.6. That code 5 * again was directly derived from the public domain 'compress' written by 6 * Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies, 7 * Ken Turkowski, Dave Mack and Peter Jannesen. 8 * 9 * This program is free software; you can redistribute it and/or modify 10 * it under the terms of the GNU General Public License as published by 11 * the Free Software Foundation; either version 2 of the License, or 12 * (at your option) any later version. 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., 675 Mass Ave, Cambridge, MA 02139, USA. 22 */ 23 24 #define WSIZE 0x8000 /* window size--must be a power of two, and */ 25 /* at least 32K for 15 bit methods. */ 26 27 #define DIST_BUFSIZE 0x8000 /* we can look back 15 bits */ 28 29 typedef int_fast32_t code_int; 30 31 #ifndef MAX_BITS 32 # define MAX_BITS 16 33 #endif 34 #define INIT_BITS 9 /* Initial number of bits per code */ 35 36 struct lzw_handle_t 37 { 38 int state; 39 40 uint8_t block_mode; /* flags */ 41 uint8_t max_bits; /* 9 - 15 */ 42 43 uint32_t bitbuffer; 44 int bufferfill; 45 46 int writecodes; 47 int readcodes; 48 uint16_t codes[8]; /* input is aligned to 8 codes at a time. When increasing n_bits or CLEAR command, the remaining codes in the buffer is discarted */ 49 50 int finchar; 51 code_int oldcode; 52 unsigned bitmask; 53 code_int free_ent; 54 code_int maxcode; 55 code_int maxmaxcode; 56 int n_bits; 57 58 uint16_t tab_prefix[1L<<MAX_BITS]; 59 uint8_t tab_suffix[2L*WSIZE]; // window 60 61 int outpos; 62 int outlen; 63 uint8_t outbuf[DIST_BUFSIZE-1]; 64 }; 65 66 #define LZW_MAGIC "\037\235" /* Magic header for lzw files, 1F 9D */ 67 68 #define BIT_MASK 0x1f /* Mask for 'number of compression bits' */ 69 // MASK 0x20 /* reserved to mean a fourth header byte */ 70 // MASK 0x40 /* unused, but no checked in original software */ 71 #define LZW_RESERVED 0x60 /* reserved bits */ 72 #define BLOCK_MODE 0x80 /* Block compression: if table is full and 73 compression rate is dropping, clear the 74 dictionary. */ 75 76 #define CLEAR 256 /* flush the dictionary */ 77 #define FIRST (CLEAR+1) /* first free entry */ 78 79 #define MAXCODE(n) (1L << (n)) 80 81 static void unlzw_init (struct lzw_handle_t *h) 82 { 83 h->block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */ 84 h->state = 0; 85 h->bitbuffer = 0; 86 h->bufferfill = 0; 87 h->oldcode = -1; 88 h->finchar = 0; 89 h->outlen = 0; 90 h->n_bits = 9; 91 h->writecodes = 0; 92 h->readcodes = 8; 93 } 94 95 static signed int unlzw_feed (struct lzw_handle_t *h, uint8_t input) 96 { 97 int code; 98 99 switch (h->state) 100 { 101 default: 102 case 0: 103 if (input & LZW_RESERVED) 104 { /* reserved bits set */ 105 return -1; 106 } 107 h->block_mode = !!(input & BLOCK_MODE); 108 h->max_bits = input & BIT_MASK; 109 h->maxmaxcode = MAXCODE ( h->max_bits ); 110 if ((h->max_bits > MAX_BITS) || (h->max_bits < 9)) 111 { /* too many bits */ 112 return -1; 113 } 114 115 h->n_bits = INIT_BITS; 116 h->maxcode = MAXCODE ( h->n_bits ) - 1; 117 h->bitmask = ( 1 << h->n_bits ) - 1; 118 119 h->free_ent = h->block_mode ? FIRST : 256; 120 121 bzero (h->tab_prefix, 256*sizeof (h->tab_prefix[0])); 122 for (code = 0 ; code < 256 ; code++) 123 { 124 h->tab_suffix[code] = (uint8_t)code; 125 } fsReadDir_file(void * _token,struct ocpfile_t * file)126 h->state = 1; 127 return 0; 128 case 1: 129 if (h->bufferfill > 0) 130 { 131 h->bitbuffer |= (input << h->bufferfill); 132 } else { 133 h->bitbuffer = input; 134 } 135 h->bufferfill += 8; 136 137 if(h->bufferfill >= h->n_bits) 138 { 139 h->codes[h->writecodes++] = h->bitbuffer & h->bitmask; 140 h->bitbuffer >>= h->n_bits; 141 h->bufferfill -= h->n_bits; 142 143 if (h->writecodes >= 8) 144 { 145 /* each time this happens, bufferfill will be zero, since we 8 codes always is a multiply of 8 bits, also known as a byte */ 146 h->readcodes = 0; 147 return 1; 148 } 149 } 150 return 0; 151 } 152 } 153 154 static void unlzw_flush (struct lzw_handle_t *h) 155 { 156 h->readcodes = 0; 157 } 158 159 static signed int unlzw_digest (struct lzw_handle_t *h) 160 { 161 uint_fast32_t code; 162 code_int incode; 163 164 h->outpos = 0; 165 h->outlen = 0; 166 167 again: 168 if (h->readcodes >= h->writecodes) 169 { 170 if (h->writecodes == 8) 171 { 172 h->writecodes = 0; 173 } 174 h->outlen = 0; 175 return 0; 176 } 177 178 code = h->codes[h->readcodes++]; 179 180 if (h->oldcode == -1) 181 { 182 if (code >= 256) 183 { /* corrupt input */ 184 return -1; 185 } 186 h->oldcode = code; 187 h->finchar = code; 188 h->outbuf[0] = code; 189 h->outpos = 0; 190 h->outlen = 1; 191 192 return 1; 193 } 194 195 if (code == CLEAR && h->block_mode) 196 { 197 h->readcodes = 8; /* discard remaing codes in the buffer */ 198 199 bzero (h->tab_prefix, 256*sizeof (h->tab_prefix[0])); 200 h->free_ent = FIRST - 1; 201 202 h->n_bits = INIT_BITS; 203 h->maxcode = MAXCODE ( h->n_bits ) - 1; 204 h->bitmask = ( 1 << h->n_bits ) - 1; 205 206 goto again; 207 } 208 209 incode = code; 210 h->outpos = sizeof (h->outbuf); 211 h->outlen = 0; 212 213 if (code > h->free_ent) 214 { /* corrupt input */ 215 return -1; 216 } else if (code == h->free_ent) 217 { /* Special case for KwKwK string. */ 218 h->outpos--; 219 h->outbuf[h->outpos] = (uint8_t)h->finchar; 220 h->outlen++; 221 code = h->oldcode; 222 } 223 224 while (code >= 256) 225 { 226 h->outpos--; 227 h->outbuf[h->outpos] = h->tab_suffix[code]; 228 h->outlen++; 229 code = h->tab_prefix[code]; 230 } 231 h->finchar = h->tab_suffix[code]; 232 h->outpos--; 233 h->outbuf[h->outpos] = (uint8_t)(h->finchar); 234 h->outlen++; 235 236 if ((code = h->free_ent) < h->maxmaxcode) 237 { /* Generate the new entry. */ 238 239 h->tab_prefix[code] = (uint16_t)h->oldcode; 240 h->tab_suffix[code] = (uint8_t)h->finchar; 241 h->free_ent = code + 1; 242 } 243 h->oldcode = incode; /* Remember previous code. */ 244 245 if (h->free_ent > h->maxcode) 246 { 247 h->readcodes = 8; /* discard remaing codes in the buffer, if any */ 248 249 (h->n_bits)++; 250 if (h->n_bits >= h->max_bits) 251 { 252 h->n_bits = h->max_bits; 253 h->maxcode = h->maxmaxcode; 254 } else { 255 h->maxcode = MAXCODE(h->n_bits)-1; 256 } fsReadDir_dir(void * _token,struct ocpdir_t * dir)257 258 h->bitmask = (1 << h->n_bits)-1; 259 } 260 261 return 1; 262 } 263