9 int alloc_image(struct image *img, int x, int y, int bpp)
11 memset(img, 0, sizeof *img);
15 img->scansz = img->pitch = x * (bpp == 15 ? 16 : bpp) / 8;
17 if(!(img->pixels = malloc(y * img->scansz))) {
18 fprintf(stderr, "failed to allocate %dx%d (%dbpp) pixel buffer\n", x, y, bpp);
22 /* just a guess, assume the user will fill the details, but set up reasonable
23 * defaults just in case...
27 img->cmap_ncolors = 1 << bpp;
28 } else if(bpp <= 24) {
36 int load_image(struct image *img, const char *fname)
42 int chan_bits, color_type;
45 unsigned char **scanline;
48 if(!(fp = fopen(fname, "rb"))) {
49 fprintf(stderr, "failed to open: %s: %s\n", fname, strerror(errno));
53 if(!(png = png_create_read_struct(PNG_LIBPNG_VER_STRING, 0, 0, 0))) {
57 if(!(info = png_create_info_struct(png))) {
59 png_destroy_read_struct(&png, 0, 0);
62 if(setjmp(png_jmpbuf(png))) {
64 png_destroy_read_struct(&png, &info, 0);
69 png_read_png(png, info, 0, 0);
71 png_get_IHDR(png, info, &xsz, &ysz, &chan_bits, &color_type, 0, 0, 0);
74 img->nchan = png_get_channels(png, info);
75 img->bpp = img->nchan * chan_bits;
76 img->scansz = img->pitch = xsz * img->bpp / 8;
77 img->cmap_ncolors = 0;
79 if(color_type == PNG_COLOR_TYPE_PALETTE) {
80 png_get_PLTE(png, info, &palette, &img->cmap_ncolors);
81 memcpy(img->cmap, palette, img->cmap_ncolors * sizeof *img->cmap);
84 if(!(img->pixels = malloc(ysz * img->scansz))) {
85 perror("failed to allocate pixel buffer");
87 png_destroy_read_struct(&png, &info, 0);
92 scanline = (unsigned char**)png_get_rows(png, info);
93 for(i=0; i<ysz; i++) {
94 memcpy(dptr, scanline[i], img->scansz);
99 png_destroy_read_struct(&png, &info, 0);
103 int save_image(struct image *img, const char *fname)
108 if(!(fp = fopen(fname, "wb"))) {
109 fprintf(stderr, "save_image: failed to open: %s: %s\n", fname, strerror(errno));
112 res = save_image_file(img, fp);
117 int save_image_file(struct image *img, FILE *fp)
119 int i, chan_bits, coltype;
123 unsigned char **scanline = 0;
126 if(!(png = png_create_write_struct(PNG_LIBPNG_VER_STRING, 0, 0, 0))) {
130 if(!(info = png_create_info_struct(png))) {
131 png_destroy_write_struct(&png, 0);
136 txt.compression = PNG_TEXT_COMPRESSION_NONE;
137 txt.key = "Software";
138 txt.text = "pngdump";
141 if(setjmp(png_jmpbuf(png))) {
142 png_destroy_write_struct(&png, &info);
150 if(img->cmap_ncolors > 0) {
151 coltype = PNG_COLOR_TYPE_PALETTE;
153 coltype = PNG_COLOR_TYPE_GRAY;
157 coltype = PNG_COLOR_TYPE_GRAY_ALPHA;
160 coltype = PNG_COLOR_TYPE_RGB;
163 coltype = PNG_COLOR_TYPE_RGB_ALPHA;
167 chan_bits = img->bpp / img->nchan;
168 png_set_IHDR(png, info, img->width, img->height, chan_bits, coltype, PNG_INTERLACE_NONE,
169 PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
170 png_set_text(png, info, &txt, 1);
172 if(img->cmap_ncolors > 0) {
173 png_set_PLTE(png, info, (png_color*)img->cmap, img->cmap_ncolors);
176 if(!(scanline = malloc(img->height * sizeof *scanline))) {
177 png_destroy_write_struct(&png, &info);
183 for(i=0; i<img->height; i++) {
187 png_set_rows(png, info, scanline);
189 png_init_io(png, fp);
190 png_write_png(png, info, 0, 0);
191 png_destroy_write_struct(&png, &info);
197 int cmp_image(struct image *a, struct image *b)
200 unsigned char *aptr = a->pixels;
201 unsigned char *bptr = b->pixels;
203 if(a->width != b->width || a->height != b->height || a->bpp != b->bpp || a->nchan != b->nchan) {
207 for(i=0; i<a->height; i++) {
208 if(memcmp(aptr, bptr, a->scansz) != 0) {
217 void blit(struct image *src, int sx, int sy, int w, int h, struct image *dst, int dx, int dy)
220 unsigned char *sptr, *dptr;
222 assert(src->bpp == dst->bpp);
223 assert(src->nchan == dst->nchan);
225 if(sx < 0) { w += sx; sx = 0; }
226 if(sy < 0) { h += sy; sy = 0; }
227 if(dx < 0) { w += dx; sx -= dx; dx = 0; }
228 if(dy < 0) { h += dy; sy -= dy; dy = 0; }
229 if(sx + w >= src->width) w = src->width - sx;
230 if(sy + h >= src->height) h = src->height - sy;
231 if(dx + w >= dst->width) w = dst->width - dx;
232 if(dy + h >= dst->height) h = dst->height - dy;
234 if(w <= 0 || h <= 0) return;
236 sptr = src->pixels + sy * src->pitch + sx * src->bpp / 8;
237 dptr = dst->pixels + dy * dst->pitch + dx * dst->bpp / 8;
240 memcpy(dptr, sptr, w * dst->bpp / 8);
246 unsigned int get_pixel(struct image *img, int x, int y)
248 unsigned int r, g, b;
250 unsigned short *pptr16;
251 unsigned int *pptr32;
255 pptr = img->pixels + y * img->pitch + x / 2;
256 return x & 1 ? *pptr & 0xf : *pptr >> 4;
258 pptr = img->pixels + y * img->pitch + x;
262 pptr16 = (unsigned short*)(img->pixels + y * img->pitch + x * 2);
265 pptr = img->pixels + y * img->pitch + x * 3;
269 return r | (g << 8) | (b << 16);
271 pptr32 = (unsigned int*)(img->pixels + y * img->pitch + x * 4);
275 fprintf(stderr, "get_pixel not implemented for %d bpp\n", img->bpp);
281 unsigned int get_pixel_rgb(struct image *img, int x, int y, unsigned int *rgb)
283 unsigned int pix = get_pixel(img, x, y);
287 rgb[0] = (pix & 0x7c00) >> 7;
288 rgb[1] = (pix & 0x03e0) >> 2;
289 rgb[2] = (pix & 0x001f) << 3;
290 rgb[0] |= ((rgb[0] & 8) >> 1) | ((rgb[0] & 8) >> 2) | ((rgb[0] & 8) >> 3);
291 rgb[1] |= ((rgb[1] & 8) >> 1) | ((rgb[1] & 8) >> 2) | ((rgb[1] & 8) >> 3);
292 rgb[2] |= ((rgb[2] & 8) >> 1) | ((rgb[2] & 8) >> 2) | ((rgb[2] & 8) >> 3);
296 rgb[0] = (pix & 0xf800) >> 8;
297 rgb[1] = (pix & 0x07e0) >> 3;
298 rgb[2] = (pix & 0x001f) << 3;
299 rgb[0] |= ((rgb[0] & 8) >> 1) | ((rgb[0] & 8) >> 2) | ((rgb[0] & 8) >> 3);
300 rgb[1] |= ((rgb[1] & 4) >> 1) | ((rgb[1] & 4) >> 2);
301 rgb[2] |= ((rgb[2] & 8) >> 1) | ((rgb[2] & 8) >> 2) | ((rgb[2] & 8) >> 3);
307 rgb[1] = (pix >> 8) & 0xff;
308 rgb[2] = (pix >> 16) & 0xff;
312 assert(pix >= 0 && pix < img->cmap_ncolors);
313 rgb[0] = img->cmap[pix].r;
314 rgb[1] = img->cmap[pix].g;
315 rgb[2] = img->cmap[pix].b;
321 void put_pixel(struct image *img, int x, int y, unsigned int pix)
324 unsigned short *pptr16;
328 pptr = img->pixels + y * img->pitch + x / 2;
330 *pptr = (*pptr & 0xf0) | pix;
332 *pptr = (*pptr & 0xf) | (pix << 4);
337 pptr = img->pixels + y * img->pitch + x;
343 pptr16 = (unsigned short*)(img->pixels + y * img->pitch + x * 2);
348 fprintf(stderr, "put_pixel not implemented for %d bpp\n", img->bpp);
352 void overlay_key(struct image *src, unsigned int key, struct image *dst)
357 assert(src->bpp == dst->bpp);
358 assert(src->width == dst->width);
359 assert(src->height == dst->height);
361 for(i=0; i<dst->height; i++) {
362 for(j=0; j<dst->width; j++) {
363 pix = get_pixel(src, j, i);
365 put_pixel(dst, j, i, pix);
372 /* ---- color quantization ---- */
376 struct octnode *root;
377 struct octnode *levn[8];
386 struct octnode *sub[8];
387 struct octnode *next;
390 static void add_color(struct octree *ot, int r, int g, int b);
391 static void reduce_colors(struct octree *ot);
392 static int assign_colors(struct octnode *on, int next, struct cmapent *cmap);
393 static int lookup_color(struct octree *ot, int r, int g, int b);
394 static struct octnode *new_node(struct octree *ot, int lvl);
395 static void del_node(struct octnode *on, int lvl);
396 static void print_tree(struct octnode *n, int lvl);
397 static int count_leaves(struct octnode *n);
399 void quantize_image(struct image *img, int maxcol)
403 struct octree ot = {0};
404 struct image newimg = *img;
409 newimg.scansz = newimg.width;
410 newimg.pitch = 8 * img->pitch / img->bpp;
413 ot.root = new_node(&ot, 0);
416 for(i=0; i<img->height; i++) {
417 for(j=0; j<img->width; j++) {
418 get_pixel_rgb(img, j, i, rgb);
419 add_color(&ot, rgb[0], rgb[1], rgb[2]);
421 while(count_leaves(ot.root) > ot.maxcol) {
422 //while(ot.ncol > ot.maxcol) {
428 /* use created octree to generate the palette */
429 newimg.cmap_ncolors = assign_colors(ot.root, 0, newimg.cmap);
431 /* replace image pixels */
432 for(i=0; i<img->height; i++) {
433 for(j=0; j<img->width; j++) {
434 get_pixel_rgb(img, j, i, rgb);
435 cidx = lookup_color(&ot, rgb[0], rgb[1], rgb[2]);
436 assert(cidx >= 0 && cidx < maxcol);
437 put_pixel(&newimg, j, i, cidx);
444 static int subidx(int bit, int r, int g, int b)
446 assert(bit >= 0 && bit < 8);
448 return ((r >> bit) & 1) | ((g >> (bit - 1)) & 2) | ((b >> (bit - 2)) & 4);
451 static int tree_height(struct octnode *on)
453 int i, subh, max = 0;
458 subh = tree_height(on->sub[i]);
459 if(subh > max) max = subh;
464 static void add_color(struct octree *ot, int r, int g, int b)
471 idx = subidx(i, r, g, b);
474 on->sub[idx] = new_node(ot, i + 1);
476 /* this only adds a color if the parent node was previously not
477 * a leaf. Otherwise the new one just takes the parent's place
498 static int count_nodes(struct octnode *n)
508 static int count_leaves(struct octnode *n)
513 if(n->nsub <= 0) return 1;
517 cnt += count_leaves(n->sub[i]);
522 static void reduce_colors(struct octree *ot)
524 int i, lvl, best_nref;
525 struct octnode *n, *best;
534 if(n->nref < best_nref && n->nsub) {
544 del_node(best->sub[i], lvl + 1);
549 /* this wasn't previously a leaf, but now it is */
558 static int assign_colors(struct octnode *on, int next, struct cmapent *cmap)
565 assert(next < on->tree->maxcol);
566 cmap[next].r = on->r / on->nref;
567 cmap[next].g = on->g / on->nref;
568 cmap[next].b = on->b / on->nref;
573 next = assign_colors(on->sub[i], next, cmap);
578 static int lookup_color(struct octree *ot, int r, int g, int b)
581 struct octnode *on = ot->root;
584 idx = subidx(i, r, g, b);
585 if(!on->sub[idx]) break;
592 static int have_node(struct octnode *list, struct octnode *n)
595 if(list == n) return 1;
601 static struct octnode *new_node(struct octree *ot, int lvl)
605 if(!(on = calloc(1, sizeof *on))) {
606 perror("failed to allocate octree node");
614 if(have_node(ot->levn[lvl], on)) {
615 fprintf(stderr, "double-insertion!\n");
618 on->next = ot->levn[lvl];
624 static void del_node(struct octnode *on, int lvl)
628 struct octnode dummy, *prev;
634 ot->ncol--; /* removing a leaf removes a color */
638 del_node(on->sub[i], lvl + 1);
642 dummy.next = ot->levn[lvl];
646 if(prev->next == on) {
647 prev->next = on->next;
652 ot->levn[lvl] = dummy.next;
658 static void print_tree(struct octnode *n, int lvl)
664 for(i=0; i<lvl; i++) {
668 printf("+-%p: <%d %d %d> #%d", (void*)n, n->r, n->g, n->b, n->nref);
669 if(n->palidx >= 0) printf(" [%d]\n", n->palidx);
673 print_tree(n->sub[i], lvl + 1);