1//cc png.m -std=c99 -framework AppKit 2// Utility for converting .PNG images into compact LZSS-packed format 3// with CLUT tables. 4// 5 6#import <Foundation/Foundation.h> 7#import <AppKit/AppKit.h> 8#import <stdlib.h> 9#import <stdint.h> 10#import <string.h> 11 12/************************************************************** 13LZSS.C -- A Data Compression Program 14*************************************************************** 15 4/6/1989 Haruhiko Okumura 16 Use, distribute, and modify this program freely. 17 Please send me your improved versions. 18 PC-VAN SCIENCE 19 NIFTY-Serve PAF01022 20 CompuServe 74050,1022 21**************************************************************/ 22#define N 4096 /* size of ring buffer - must be power of 2 */ 23#define F 18 /* upper limit for match_length */ 24#define THRESHOLD 2 /* encode string into position and length 25 if match_length is greater than this */ 26#define NIL N /* index for root of binary search trees */ 27 28struct encode_state { 29 /* 30 * left & right children & parent. These constitute binary search trees. 31 */ 32 int lchild[N + 1], rchild[N + 257], parent[N + 1]; 33 /* ring buffer of size N, with extra F-1 bytes to aid string comparison */ 34 u_int8_t text_buf[N + F - 1]; 35 /* 36 * match_length of longest match. 37 * These are set by the insert_node() procedure. 38 */ 39 int match_position, match_length; 40}; 41 42/* 43 * initialize state, mostly the trees 44 * 45 * For i = 0 to N - 1, rchild[i] and lchild[i] will be the right and left 46 * children of node i. These nodes need not be initialized. Also, parent[i] 47 * is the parent of node i. These are initialized to NIL (= N), which stands 48 * for 'not used.' For i = 0 to 255, rchild[N + i + 1] is the root of the 49 * tree for strings that begin with character i. These are initialized to NIL. 50 * Note there are 256 trees. 51 */ 52static void init_state(struct encode_state *sp) 53{ 54 int i; 55 bzero(sp, sizeof(*sp)); 56 for (i = 0; i < N - F; i++) 57 sp->text_buf[i] = ' '; 58 for (i = N + 1; i <= N + 256; i++) 59 sp->rchild[i] = NIL; 60 for (i = 0; i < N; i++) 61 sp->parent[i] = NIL; 62} 63 64/* 65 * Inserts string of length F, text_buf[r..r+F-1], into one of the trees 66 * (text_buf[r]'th tree) and returns the longest-match position and length 67 * via the global variables match_position and match_length. 68 * If match_length = F, then removes the old node in favor of the new one, 69 * because the old one will be deleted sooner. Note r plays double role, 70 * as tree node and position in buffer. 71 */ 72static void insert_node(struct encode_state *sp, int r) 73{ 74 int i, p, cmp; 75 u_int8_t *key; 76 cmp = 1; 77 key = &sp->text_buf[r]; 78 p = N + 1 + key[0]; 79 sp->rchild[r] = sp->lchild[r] = NIL; 80 sp->match_length = 0; 81 for ( ; ; ) { 82 if (cmp >= 0) { 83 if (sp->rchild[p] != NIL) 84 p = sp->rchild[p]; 85 else { 86 sp->rchild[p] = r; 87 sp->parent[r] = p; 88 return; 89 } 90 } else { 91 if (sp->lchild[p] != NIL) 92 p = sp->lchild[p]; 93 else { 94 sp->lchild[p] = r; 95 sp->parent[r] = p; 96 return; 97 } 98 } 99 for (i = 1; i < F; i++) { 100 if ((cmp = key[i] - sp->text_buf[p + i]) != 0) 101 break; 102 } 103 if (i > sp->match_length) { 104 sp->match_position = p; 105 if ((sp->match_length = i) >= F) 106 break; 107 } 108 } 109 sp->parent[r] = sp->parent[p]; 110 sp->lchild[r] = sp->lchild[p]; 111 sp->rchild[r] = sp->rchild[p]; 112 sp->parent[sp->lchild[p]] = r; 113 sp->parent[sp->rchild[p]] = r; 114 if (sp->rchild[sp->parent[p]] == p) 115 sp->rchild[sp->parent[p]] = r; 116 else 117 sp->lchild[sp->parent[p]] = r; 118 sp->parent[p] = NIL; /* remove p */ 119} 120 121/* deletes node p from tree */ 122static void delete_node(struct encode_state *sp, int p) 123{ 124 int q; 125 126 if (sp->parent[p] == NIL) 127 return; /* not in tree */ 128 if (sp->rchild[p] == NIL) 129 q = sp->lchild[p]; 130 else if (sp->lchild[p] == NIL) 131 q = sp->rchild[p]; 132 else { 133 q = sp->lchild[p]; 134 if (sp->rchild[q] != NIL) { 135 do { 136 q = sp->rchild[q]; 137 } while (sp->rchild[q] != NIL); 138 sp->rchild[sp->parent[q]] = sp->lchild[q]; 139 sp->parent[sp->lchild[q]] = sp->parent[q]; 140 sp->lchild[q] = sp->lchild[p]; 141 sp->parent[sp->lchild[p]] = q; 142 } 143 sp->rchild[q] = sp->rchild[p]; 144 sp->parent[sp->rchild[p]] = q; 145 } 146 sp->parent[q] = sp->parent[p]; 147 if (sp->rchild[sp->parent[p]] == p) 148 sp->rchild[sp->parent[p]] = q; 149 else 150 sp->lchild[sp->parent[p]] = q; 151 sp->parent[p] = NIL; 152} 153 154u_int8_t *compress_lzss( 155 u_int8_t * dst, 156 u_int32_t dstlen, 157 u_int8_t * src, 158 u_int32_t srclen) 159{ 160 u_int8_t * result = NULL; 161 /* Encoding state, mostly tree but some current match stuff */ 162 struct encode_state *sp; 163 int i, c, len, r, s, last_match_length, code_buf_ptr; 164 u_int8_t code_buf[17], mask; 165 u_int8_t * srcend = src + srclen; 166 u_int8_t *dstend = dst + dstlen; 167 /* initialize trees */ 168 sp = (struct encode_state *) malloc(sizeof(*sp)); 169 if (!sp) goto finish; 170 init_state(sp); 171 /* 172 * code_buf[1..16] saves eight units of code, and code_buf[0] works 173 * as eight flags, "1" representing that the unit is an unencoded 174 * letter (1 byte), "0" a position-and-length pair (2 bytes). 175 * Thus, eight units require at most 16 bytes of code. 176 */ 177 code_buf[0] = 0; 178 code_buf_ptr = mask = 1; 179 /* Clear the buffer with any character that will appear often. */ 180 s = 0; r = N - F; 181 /* Read F bytes into the last F bytes of the buffer */ 182 for (len = 0; len < F && src < srcend; len++) 183 sp->text_buf[r + len] = *src++; 184 if (!len) 185 goto finish; 186 /* 187 * Insert the F strings, each of which begins with one or more 188 * 'space' characters. Note the order in which these strings are 189 * inserted. This way, degenerate trees will be less likely to occur. 190 */ 191 for (i = 1; i <= F; i++) 192 insert_node(sp, r - i); 193 /* 194 * Finally, insert the whole string just read. 195 * The global variables match_length and match_position are set. 196 */ 197 insert_node(sp, r); 198 do { 199 /* match_length may be spuriously long near the end of text. */ 200 if (sp->match_length > len) 201 sp->match_length = len; 202 if (sp->match_length <= THRESHOLD) { 203 sp->match_length = 1; /* Not long enough match. Send one byte. */ 204 code_buf[0] |= mask; /* 'send one byte' flag */ 205 code_buf[code_buf_ptr++] = sp->text_buf[r]; /* Send uncoded. */ 206 } else { 207 /* Send position and length pair. Note match_length > THRESHOLD. */ 208 code_buf[code_buf_ptr++] = (u_int8_t) sp->match_position; 209 code_buf[code_buf_ptr++] = (u_int8_t) 210 ( ((sp->match_position >> 4) & 0xF0) 211 | (sp->match_length - (THRESHOLD + 1)) ); 212 } 213 if ((mask <<= 1) == 0) { /* Shift mask left one bit. */ 214 /* Send at most 8 units of code together */ 215 for (i = 0; i < code_buf_ptr; i++) 216 if (dst < dstend) 217 *dst++ = code_buf[i]; 218 else 219 goto finish; 220 code_buf[0] = 0; 221 code_buf_ptr = mask = 1; 222 } 223 last_match_length = sp->match_length; 224 for (i = 0; i < last_match_length && src < srcend; i++) { 225 delete_node(sp, s); /* Delete old strings and */ 226 c = *src++; 227 sp->text_buf[s] = c; /* read new bytes */ 228 /* 229 * If the position is near the end of buffer, extend the buffer 230 * to make string comparison easier. 231 */ 232 if (s < F - 1) 233 sp->text_buf[s + N] = c; 234 /* Since this is a ring buffer, increment the position modulo N. */ 235 s = (s + 1) & (N - 1); 236 r = (r + 1) & (N - 1); 237 /* Register the string in text_buf[r..r+F-1] */ 238 insert_node(sp, r); 239 } 240 while (i++ < last_match_length) { 241 delete_node(sp, s); 242 /* After the end of text, no need to read, */ 243 s = (s + 1) & (N - 1); 244 r = (r + 1) & (N - 1); 245 /* but buffer may not be empty. */ 246 if (--len) 247 insert_node(sp, r); 248 } 249 } while (len > 0); /* until length of string to be processed is zero */ 250 if (code_buf_ptr > 1) { /* Send remaining code. */ 251 for (i = 0; i < code_buf_ptr; i++) 252 if (dst < dstend) 253 *dst++ = code_buf[i]; 254 else 255 goto finish; 256 } 257 result = dst; 258finish: 259 if (sp) free(sp); 260 return result; 261} 262 263#define MAX_COLORS 256 264 265typedef struct { 266 uint8_t r; 267 uint8_t g; 268 uint8_t b; 269} pixel_t; 270 271static uint8_t clut_size = 0; 272static pixel_t clut[MAX_COLORS]; 273 274static uint8_t 275lookup_color(uint8_t r, uint8_t g, uint8_t b) 276{ 277 uint8_t i; 278 279 for (i = 0; i <= clut_size; i++) { 280 if (clut[i].r == r && 281 clut[i].g == g && 282 clut[i].b == b) 283 return i; 284 } 285 if (clut_size == MAX_COLORS - 1) { 286 printf("Image must have no more than 256 unique pixel colors\n"); 287 exit(1); 288 } 289 clut_size++; 290 clut[clut_size].r = r; 291 clut[clut_size].g = g; 292 clut[clut_size].b = b; 293// printf("added color %d:%d:%d\n", r, g, b); 294 return clut_size; 295} 296 297 #include "/sandbox//xnu/pexpert/pexpert/GearImage.h" 298 299int main (int argc, char * argv[]) 300{ 301 int i, size = 0; 302 uint8_t *unpacked = NULL; 303 uint8_t *packed = NULL; 304 uint8_t *lastbyte; 305 uint8_t *byte; 306 uint8_t color; 307 char *tag; 308 bool mono; 309 NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init]; 310 311 if (argc <= 1) { 312 printf("usage: PackImage <filename.png>\n"); 313 return 1; 314 } 315 316 NSString* filePath = [NSString stringWithUTF8String:argv[1]]; 317 318 NSData* fileData = [NSData dataWithContentsOfFile:filePath]; 319 NSBitmapImageRep* bitmapImageRep = [[NSBitmapImageRep alloc] initWithData:fileData]; 320 321 NSSize imageSize = [bitmapImageRep size]; 322 323 // Get a file name without .png extension 324 tag = strstr(argv[1], ".png"); 325 if (tag != NULL) { 326 *tag = '\0'; 327 tag = (char *)argv[1]; 328 } else { 329 printf("PackImage only supports .png images \n"); 330 return 1; 331 } 332 mono = true; 333 334 unpacked = malloc((int)imageSize.width * (int)imageSize.height); 335 packed = malloc(1000000); 336 337 if (unpacked == NULL || packed == NULL) { 338 printf("out of memory\n"); 339 return 1; 340 } 341 342 bzero(clut, sizeof(clut)); 343 clut[0].r = 0xff; 344 clut[0].g = 0xff; 345 clut[0].b = 0xff; 346 347 printf("/*\n"); 348 printf(" * This file was generated using PackImage utility.\n"); 349 printf(" * Please don't modify it.\n"); 350 printf(" */\n"); 351 352 for (int y=0; y<imageSize.height; y++) { 353 for (int x=0; x<imageSize.width; x++) { 354 NSUInteger pixel[4] = {}; 355 [bitmapImageRep getPixel:pixel atX:x y:y]; 356 357 if (0xff != (uint8_t)pixel[3]) { 358 fprintf(stderr, "has alpha\n"); 359 exit(1); 360 } 361 if (1) 362 { 363 color = pixel[0]; 364 if ((color != (uint8_t)pixel[1]) || (color != (uint8_t)pixel[2])) { 365 fprintf(stderr, "has colors\n"); 366 exit(1); 367 } 368 } 369 else color = lookup_color((uint8_t)pixel[0], 370 (uint8_t)pixel[1], 371 (uint8_t)pixel[2]); 372 373 unpacked[size++] = color; 374 375 376 color = gGearPict[y*(int)imageSize.width + x]; 377 color = (0xbf * color + 0xff) >> 8; 378 pixel[0] = pixel[1] = pixel[2] = color; 379 [bitmapImageRep setPixel:pixel atX:x y:y]; 380 } 381 } 382 383 fileData = [bitmapImageRep representationUsingType:NSPNGFileType properties:nil]; 384 filePath = [NSString stringWithUTF8String:"/tmp/x.png"]; 385 [fileData writeToFile:filePath options:0 error:NULL]; 386 387 exit(0); 388 389 printf("\n"); 390 printf("#define k%sWidth (%d)\n", tag, (int)imageSize.width); 391 printf("#define k%sHeight (%d)\n", tag, (int)imageSize.height); 392 printf("#define k%sUnpackedSize (%d)\n", tag, size); 393 if (!mono) printf("#define k%sClutSize (%d)\n", tag, clut_size); 394 395 printf("\nconst uint8_t g%sPacked[] = {\n ", tag); 396 397 lastbyte = compress_lzss(packed, 1000000, unpacked, size); 398 399 // Dump LZSS-compressed image data 400 for (byte = packed, i = 0; byte < lastbyte; byte++, i++) { 401 if ((i > 0) && (i % 16) == 0) 402 printf("\n "); 403 printf("0x%02x,", *byte); 404 } 405 406 printf("\n};\n\n"); 407 408 if (!mono) { 409 // Dump clut table 410 printf("const uint8_t g%sClut[ 256 * 3 ] =\n{\n ", tag); 411 for (i = 0; i < 256; i++) { 412 if ((i > 0) && (i % 4) == 0) 413 printf("\n "); 414 printf("0x%02x,0x%02x,0x%02x, ", clut[i].r, clut[i].g, clut[i].b); 415 } 416 printf("\n};\n"); 417 } 418 [pool drain]; 419 return 0; 420} 421
