12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /* pngrtran.c - transforms the data in a row for PNG readers
26 *
27 * This file is available under and governed by the GNU General Public
28 * License version 2 only, as published by the Free Software Foundation.
29 * However, the following notice accompanied the original version of this
30 * file and, per its terms, should not be removed:
31 *
32 * Last changed in libpng 1.6.24 [August 4, 2016]
33 * Copyright (c) 1998-2002,2004,2006-2016 Glenn Randers-Pehrson
34 * (Version 0.96 Copyright (c) 1996, 1997 Andreas Dilger)
35 * (Version 0.88 Copyright (c) 1995, 1996 Guy Eric Schalnat, Group 42, Inc.)
36 *
37 * This code is released under the libpng license.
38 * For conditions of distribution and use, see the disclaimer
39 * and license in png.h
40 *
41 * This file contains functions optionally called by an application
42 * in order to tell libpng how to handle data when reading a PNG.
43 * Transformations that are used in both reading and writing are
44 * in pngtrans.c.
45 */
46
47 #include "pngpriv.h"
48
49 #ifdef PNG_READ_SUPPORTED
50
51 /* Set the action on getting a CRC error for an ancillary or critical chunk. */
52 void PNGAPI
53 png_set_crc_action(png_structrp png_ptr, int crit_action, int ancil_action)
60 /* Tell libpng how we react to CRC errors in critical chunks */
61 switch (crit_action)
62 {
63 case PNG_CRC_NO_CHANGE: /* Leave setting as is */
64 break;
65
66 case PNG_CRC_WARN_USE: /* Warn/use data */
67 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
68 png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE;
69 break;
70
71 case PNG_CRC_QUIET_USE: /* Quiet/use data */
72 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
73 png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE |
74 PNG_FLAG_CRC_CRITICAL_IGNORE;
75 break;
76
77 case PNG_CRC_WARN_DISCARD: /* Not a valid action for critical data */
78 png_warning(png_ptr,
79 "Can't discard critical data on CRC error");
80 case PNG_CRC_ERROR_QUIT: /* Error/quit */
81
82 case PNG_CRC_DEFAULT:
83 default:
84 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
85 break;
86 }
87
88 /* Tell libpng how we react to CRC errors in ancillary chunks */
89 switch (ancil_action)
90 {
91 case PNG_CRC_NO_CHANGE: /* Leave setting as is */
92 break;
93
94 case PNG_CRC_WARN_USE: /* Warn/use data */
95 png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;
96 png_ptr->flags |= PNG_FLAG_CRC_ANCILLARY_USE;
97 break;
98
99 case PNG_CRC_QUIET_USE: /* Quiet/use data */
440 typedef png_dsort * png_dsortp;
441 typedef png_dsort * * png_dsortpp;
442
443 void PNGAPI
444 png_set_quantize(png_structrp png_ptr, png_colorp palette,
445 int num_palette, int maximum_colors, png_const_uint_16p histogram,
446 int full_quantize)
447 {
448 png_debug(1, "in png_set_quantize");
449
450 if (png_rtran_ok(png_ptr, 0) == 0)
451 return;
452
453 png_ptr->transformations |= PNG_QUANTIZE;
454
455 if (full_quantize == 0)
456 {
457 int i;
458
459 png_ptr->quantize_index = (png_bytep)png_malloc(png_ptr,
460 (png_uint_32)((png_uint_32)num_palette * (sizeof (png_byte))));
461 for (i = 0; i < num_palette; i++)
462 png_ptr->quantize_index[i] = (png_byte)i;
463 }
464
465 if (num_palette > maximum_colors)
466 {
467 if (histogram != NULL)
468 {
469 /* This is easy enough, just throw out the least used colors.
470 * Perhaps not the best solution, but good enough.
471 */
472
473 int i;
474
475 /* Initialize an array to sort colors */
476 png_ptr->quantize_sort = (png_bytep)png_malloc(png_ptr,
477 (png_uint_32)((png_uint_32)num_palette * (sizeof (png_byte))));
478
479 /* Initialize the quantize_sort array */
480 for (i = 0; i < num_palette; i++)
481 png_ptr->quantize_sort[i] = (png_byte)i;
482
483 /* Find the least used palette entries by starting a
484 * bubble sort, and running it until we have sorted
485 * out enough colors. Note that we don't care about
486 * sorting all the colors, just finding which are
487 * least used.
488 */
489
490 for (i = num_palette - 1; i >= maximum_colors; i--)
491 {
492 int done; /* To stop early if the list is pre-sorted */
493 int j;
494
495 done = 1;
496 for (j = 0; j < i; j++)
497 {
591 else
592 {
593 /* This is much harder to do simply (and quickly). Perhaps
594 * we need to go through a median cut routine, but those
595 * don't always behave themselves with only a few colors
596 * as input. So we will just find the closest two colors,
597 * and throw out one of them (chosen somewhat randomly).
598 * [We don't understand this at all, so if someone wants to
599 * work on improving it, be our guest - AED, GRP]
600 */
601 int i;
602 int max_d;
603 int num_new_palette;
604 png_dsortp t;
605 png_dsortpp hash;
606
607 t = NULL;
608
609 /* Initialize palette index arrays */
610 png_ptr->index_to_palette = (png_bytep)png_malloc(png_ptr,
611 (png_uint_32)((png_uint_32)num_palette * (sizeof (png_byte))));
612 png_ptr->palette_to_index = (png_bytep)png_malloc(png_ptr,
613 (png_uint_32)((png_uint_32)num_palette * (sizeof (png_byte))));
614
615 /* Initialize the sort array */
616 for (i = 0; i < num_palette; i++)
617 {
618 png_ptr->index_to_palette[i] = (png_byte)i;
619 png_ptr->palette_to_index[i] = (png_byte)i;
620 }
621
622 hash = (png_dsortpp)png_calloc(png_ptr, (png_uint_32)(769 *
623 (sizeof (png_dsortp))));
624
625 num_new_palette = num_palette;
626
627 /* Initial wild guess at how far apart the farthest pixel
628 * pair we will be eliminating will be. Larger
629 * numbers mean more areas will be allocated, Smaller
630 * numbers run the risk of not saving enough data, and
631 * having to do this all over again.
632 *
633 * I have not done extensive checking on this number.
634 */
635 max_d = 96;
636
637 while (num_new_palette > maximum_colors)
638 {
639 for (i = 0; i < num_new_palette - 1; i++)
640 {
641 int j;
642
643 for (j = i + 1; j < num_new_palette; j++)
644 {
645 int d;
646
647 d = PNG_COLOR_DIST(palette[i], palette[j]);
648
649 if (d <= max_d)
650 {
651
652 t = (png_dsortp)png_malloc_warn(png_ptr,
653 (png_uint_32)(sizeof (png_dsort)));
654
655 if (t == NULL)
656 break;
657
658 t->next = hash[d];
659 t->left = (png_byte)i;
660 t->right = (png_byte)j;
661 hash[d] = t;
662 }
663 }
664 if (t == NULL)
665 break;
666 }
667
668 if (t != NULL)
669 for (i = 0; i <= max_d; i++)
670 {
671 if (hash[i] != NULL)
672 {
673 png_dsortp p;
758 num_palette = maximum_colors;
759 }
760 if (png_ptr->palette == NULL)
761 {
762 png_ptr->palette = palette;
763 }
764 png_ptr->num_palette = (png_uint_16)num_palette;
765
766 if (full_quantize != 0)
767 {
768 int i;
769 png_bytep distance;
770 int total_bits = PNG_QUANTIZE_RED_BITS + PNG_QUANTIZE_GREEN_BITS +
771 PNG_QUANTIZE_BLUE_BITS;
772 int num_red = (1 << PNG_QUANTIZE_RED_BITS);
773 int num_green = (1 << PNG_QUANTIZE_GREEN_BITS);
774 int num_blue = (1 << PNG_QUANTIZE_BLUE_BITS);
775 png_size_t num_entries = ((png_size_t)1 << total_bits);
776
777 png_ptr->palette_lookup = (png_bytep)png_calloc(png_ptr,
778 (png_uint_32)(num_entries * (sizeof (png_byte))));
779
780 distance = (png_bytep)png_malloc(png_ptr, (png_uint_32)(num_entries *
781 (sizeof (png_byte))));
782
783 memset(distance, 0xff, num_entries * (sizeof (png_byte)));
784
785 for (i = 0; i < num_palette; i++)
786 {
787 int ir, ig, ib;
788 int r = (palette[i].red >> (8 - PNG_QUANTIZE_RED_BITS));
789 int g = (palette[i].green >> (8 - PNG_QUANTIZE_GREEN_BITS));
790 int b = (palette[i].blue >> (8 - PNG_QUANTIZE_BLUE_BITS));
791
792 for (ir = 0; ir < num_red; ir++)
793 {
794 /* int dr = abs(ir - r); */
795 int dr = ((ir > r) ? ir - r : r - ir);
796 int index_r = (ir << (PNG_QUANTIZE_BLUE_BITS +
797 PNG_QUANTIZE_GREEN_BITS));
798
799 for (ig = 0; ig < num_green; ig++)
800 {
1264 switch (png_ptr->bit_depth)
1265 {
1266 case 1:
1267 gray *= 0xff;
1268 trans_gray *= 0xff;
1269 break;
1270
1271 case 2:
1272 gray *= 0x55;
1273 trans_gray *= 0x55;
1274 break;
1275
1276 case 4:
1277 gray *= 0x11;
1278 trans_gray *= 0x11;
1279 break;
1280
1281 default:
1282
1283 case 8:
1284 /* FALL THROUGH (Already 8 bits) */
1285
1286 case 16:
1287 /* Already a full 16 bits */
1288 break;
1289 }
1290
1291 png_ptr->background.red = png_ptr->background.green =
1292 png_ptr->background.blue = (png_uint_16)gray;
1293
1294 if ((png_ptr->transformations & PNG_EXPAND_tRNS) == 0)
1295 {
1296 png_ptr->trans_color.red = png_ptr->trans_color.green =
1297 png_ptr->trans_color.blue = (png_uint_16)trans_gray;
1298 }
1299 }
1300 } /* background expand and (therefore) no alpha association. */
1301 #endif /* READ_EXPAND && READ_BACKGROUND */
1302 }
1303
1304 void /* PRIVATE */
2945 *(dp--) = *(sp - 1);
2946 *(dp--) = *(sp--);
2947 *(dp--) = *(sp--);
2948 }
2949 }
2950 }
2951 row_info->channels = (png_byte)(row_info->channels + 2);
2952 row_info->color_type |= PNG_COLOR_MASK_COLOR;
2953 row_info->pixel_depth = (png_byte)(row_info->channels *
2954 row_info->bit_depth);
2955 row_info->rowbytes = PNG_ROWBYTES(row_info->pixel_depth, row_width);
2956 }
2957 }
2958 #endif
2959
2960 #ifdef PNG_READ_RGB_TO_GRAY_SUPPORTED
2961 /* Reduce RGB files to grayscale, with or without alpha
2962 * using the equation given in Poynton's ColorFAQ of 1998-01-04 at
2963 * <http://www.inforamp.net/~poynton/> (THIS LINK IS DEAD June 2008 but
2964 * versions dated 1998 through November 2002 have been archived at
2965 * http://web.archive.org/web/20000816232553/http://www.inforamp.net/
2966 * ~poynton/notes/colour_and_gamma/ColorFAQ.txt )
2967 * Charles Poynton poynton at poynton.com
2968 *
2969 * Y = 0.212671 * R + 0.715160 * G + 0.072169 * B
2970 *
2971 * which can be expressed with integers as
2972 *
2973 * Y = (6969 * R + 23434 * G + 2365 * B)/32768
2974 *
2975 * Poynton's current link (as of January 2003 through July 2011):
2976 * <http://www.poynton.com/notes/colour_and_gamma/>
2977 * has changed the numbers slightly:
2978 *
2979 * Y = 0.2126*R + 0.7152*G + 0.0722*B
2980 *
2981 * which can be expressed with integers as
2982 *
2983 * Y = (6966 * R + 23436 * G + 2366 * B)/32768
2984 *
2985 * Historically, however, libpng uses numbers derived from the ITU-R Rec 709
4313
4314 dp--;
4315 }
4316 break;
4317 }
4318
4319 default:
4320 break;
4321 }
4322 row_info->bit_depth = 8;
4323 row_info->pixel_depth = 8;
4324 row_info->rowbytes = row_width;
4325 }
4326
4327 if (row_info->bit_depth == 8)
4328 {
4329 {
4330 if (num_trans > 0)
4331 {
4332 sp = row + (png_size_t)row_width - 1;
4333 dp = row + (png_size_t)(row_width << 2) - 1;
4334
4335 for (i = 0; i < row_width; i++)
4336 {
4337 if ((int)(*sp) >= num_trans)
4338 *dp-- = 0xff;
4339
4340 else
4341 *dp-- = trans_alpha[*sp];
4342
4343 *dp-- = palette[*sp].blue;
4344 *dp-- = palette[*sp].green;
4345 *dp-- = palette[*sp].red;
4346 sp--;
4347 }
4348 row_info->bit_depth = 8;
4349 row_info->pixel_depth = 32;
4350 row_info->rowbytes = row_width * 4;
4351 row_info->color_type = 6;
4352 row_info->channels = 4;
4353 }
4474 dp--;
4475 }
4476 break;
4477 }
4478
4479 default:
4480 break;
4481 }
4482
4483 row_info->bit_depth = 8;
4484 row_info->pixel_depth = 8;
4485 row_info->rowbytes = row_width;
4486 }
4487
4488 if (trans_color != NULL)
4489 {
4490 if (row_info->bit_depth == 8)
4491 {
4492 gray = gray & 0xff;
4493 sp = row + (png_size_t)row_width - 1;
4494 dp = row + (png_size_t)(row_width << 1) - 1;
4495
4496 for (i = 0; i < row_width; i++)
4497 {
4498 if ((*sp & 0xffU) == gray)
4499 *dp-- = 0;
4500
4501 else
4502 *dp-- = 0xff;
4503
4504 *dp-- = *sp--;
4505 }
4506 }
4507
4508 else if (row_info->bit_depth == 16)
4509 {
4510 unsigned int gray_high = (gray >> 8) & 0xff;
4511 unsigned int gray_low = gray & 0xff;
4512 sp = row + row_info->rowbytes - 1;
4513 dp = row + (row_info->rowbytes << 1) - 1;
4514 for (i = 0; i < row_width; i++)
4530 *dp-- = *sp--;
4531 }
4532 }
4533
4534 row_info->color_type = PNG_COLOR_TYPE_GRAY_ALPHA;
4535 row_info->channels = 2;
4536 row_info->pixel_depth = (png_byte)(row_info->bit_depth << 1);
4537 row_info->rowbytes = PNG_ROWBYTES(row_info->pixel_depth,
4538 row_width);
4539 }
4540 }
4541 else if (row_info->color_type == PNG_COLOR_TYPE_RGB &&
4542 trans_color != NULL)
4543 {
4544 if (row_info->bit_depth == 8)
4545 {
4546 png_byte red = (png_byte)(trans_color->red & 0xff);
4547 png_byte green = (png_byte)(trans_color->green & 0xff);
4548 png_byte blue = (png_byte)(trans_color->blue & 0xff);
4549 sp = row + (png_size_t)row_info->rowbytes - 1;
4550 dp = row + (png_size_t)(row_width << 2) - 1;
4551 for (i = 0; i < row_width; i++)
4552 {
4553 if (*(sp - 2) == red && *(sp - 1) == green && *(sp) == blue)
4554 *dp-- = 0;
4555
4556 else
4557 *dp-- = 0xff;
4558
4559 *dp-- = *sp--;
4560 *dp-- = *sp--;
4561 *dp-- = *sp--;
4562 }
4563 }
4564 else if (row_info->bit_depth == 16)
4565 {
4566 png_byte red_high = (png_byte)((trans_color->red >> 8) & 0xff);
4567 png_byte green_high = (png_byte)((trans_color->green >> 8) & 0xff);
4568 png_byte blue_high = (png_byte)((trans_color->blue >> 8) & 0xff);
4569 png_byte red_low = (png_byte)(trans_color->red & 0xff);
4570 png_byte green_low = (png_byte)(trans_color->green & 0xff);
4571 png_byte blue_low = (png_byte)(trans_color->blue & 0xff);
4572 sp = row + row_info->rowbytes - 1;
4573 dp = row + (png_size_t)(row_width << 3) - 1;
4574 for (i = 0; i < row_width; i++)
4575 {
4576 if (*(sp - 5) == red_high &&
4577 *(sp - 4) == red_low &&
4578 *(sp - 3) == green_high &&
4579 *(sp - 2) == green_low &&
4580 *(sp - 1) == blue_high &&
4581 *(sp ) == blue_low)
4582 {
4583 *dp-- = 0;
4584 *dp-- = 0;
4585 }
4586
4587 else
4588 {
4589 *dp-- = 0xff;
4590 *dp-- = 0xff;
4591 }
4592
4593 *dp-- = *sp--;
4612 * whole row to 16 bits. Has no effect otherwise.
4613 */
4614 static void
4615 png_do_expand_16(png_row_infop row_info, png_bytep row)
4616 {
4617 if (row_info->bit_depth == 8 &&
4618 row_info->color_type != PNG_COLOR_TYPE_PALETTE)
4619 {
4620 /* The row have a sequence of bytes containing [0..255] and we need
4621 * to turn it into another row containing [0..65535], to do this we
4622 * calculate:
4623 *
4624 * (input / 255) * 65535
4625 *
4626 * Which happens to be exactly input * 257 and this can be achieved
4627 * simply by byte replication in place (copying backwards).
4628 */
4629 png_byte *sp = row + row_info->rowbytes; /* source, last byte + 1 */
4630 png_byte *dp = sp + row_info->rowbytes; /* destination, end + 1 */
4631 while (dp > sp)
4632 dp[-2] = dp[-1] = *--sp, dp -= 2;
4633
4634 row_info->rowbytes *= 2;
4635 row_info->bit_depth = 16;
4636 row_info->pixel_depth = (png_byte)(row_info->channels * 16);
4637 }
4638 }
4639 #endif
4640
4641 #ifdef PNG_READ_QUANTIZE_SUPPORTED
4642 static void
4643 png_do_quantize(png_row_infop row_info, png_bytep row,
4644 png_const_bytep palette_lookup, png_const_bytep quantize_lookup)
4645 {
4646 png_bytep sp, dp;
4647 png_uint_32 i;
4648 png_uint_32 row_width=row_info->width;
4649
4650 png_debug(1, "in png_do_quantize");
4651
4652 if (row_info->bit_depth == 8)
|
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /* pngrtran.c - transforms the data in a row for PNG readers
26 *
27 * This file is available under and governed by the GNU General Public
28 * License version 2 only, as published by the Free Software Foundation.
29 * However, the following notice accompanied the original version of this
30 * file and, per its terms, should not be removed:
31 *
32 * Last changed in libpng 1.6.33 [September 28, 2017]
33 * Copyright (c) 1998-2002,2004,2006-2017 Glenn Randers-Pehrson
34 * (Version 0.96 Copyright (c) 1996, 1997 Andreas Dilger)
35 * (Version 0.88 Copyright (c) 1995, 1996 Guy Eric Schalnat, Group 42, Inc.)
36 *
37 * This code is released under the libpng license.
38 * For conditions of distribution and use, see the disclaimer
39 * and license in png.h
40 *
41 * This file contains functions optionally called by an application
42 * in order to tell libpng how to handle data when reading a PNG.
43 * Transformations that are used in both reading and writing are
44 * in pngtrans.c.
45 */
46
47 #include "pngpriv.h"
48
49 #ifdef PNG_READ_SUPPORTED
50
51 /* Set the action on getting a CRC error for an ancillary or critical chunk. */
52 void PNGAPI
53 png_set_crc_action(png_structrp png_ptr, int crit_action, int ancil_action)
60 /* Tell libpng how we react to CRC errors in critical chunks */
61 switch (crit_action)
62 {
63 case PNG_CRC_NO_CHANGE: /* Leave setting as is */
64 break;
65
66 case PNG_CRC_WARN_USE: /* Warn/use data */
67 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
68 png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE;
69 break;
70
71 case PNG_CRC_QUIET_USE: /* Quiet/use data */
72 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
73 png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE |
74 PNG_FLAG_CRC_CRITICAL_IGNORE;
75 break;
76
77 case PNG_CRC_WARN_DISCARD: /* Not a valid action for critical data */
78 png_warning(png_ptr,
79 "Can't discard critical data on CRC error");
80 /* FALLTHROUGH */
81 case PNG_CRC_ERROR_QUIT: /* Error/quit */
82
83 case PNG_CRC_DEFAULT:
84 default:
85 png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;
86 break;
87 }
88
89 /* Tell libpng how we react to CRC errors in ancillary chunks */
90 switch (ancil_action)
91 {
92 case PNG_CRC_NO_CHANGE: /* Leave setting as is */
93 break;
94
95 case PNG_CRC_WARN_USE: /* Warn/use data */
96 png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;
97 png_ptr->flags |= PNG_FLAG_CRC_ANCILLARY_USE;
98 break;
99
100 case PNG_CRC_QUIET_USE: /* Quiet/use data */
441 typedef png_dsort * png_dsortp;
442 typedef png_dsort * * png_dsortpp;
443
444 void PNGAPI
445 png_set_quantize(png_structrp png_ptr, png_colorp palette,
446 int num_palette, int maximum_colors, png_const_uint_16p histogram,
447 int full_quantize)
448 {
449 png_debug(1, "in png_set_quantize");
450
451 if (png_rtran_ok(png_ptr, 0) == 0)
452 return;
453
454 png_ptr->transformations |= PNG_QUANTIZE;
455
456 if (full_quantize == 0)
457 {
458 int i;
459
460 png_ptr->quantize_index = (png_bytep)png_malloc(png_ptr,
461 (png_alloc_size_t)((png_uint_32)num_palette * (sizeof (png_byte))));
462 for (i = 0; i < num_palette; i++)
463 png_ptr->quantize_index[i] = (png_byte)i;
464 }
465
466 if (num_palette > maximum_colors)
467 {
468 if (histogram != NULL)
469 {
470 /* This is easy enough, just throw out the least used colors.
471 * Perhaps not the best solution, but good enough.
472 */
473
474 int i;
475
476 /* Initialize an array to sort colors */
477 png_ptr->quantize_sort = (png_bytep)png_malloc(png_ptr,
478 (png_alloc_size_t)((png_uint_32)num_palette * (sizeof (png_byte))));
479
480 /* Initialize the quantize_sort array */
481 for (i = 0; i < num_palette; i++)
482 png_ptr->quantize_sort[i] = (png_byte)i;
483
484 /* Find the least used palette entries by starting a
485 * bubble sort, and running it until we have sorted
486 * out enough colors. Note that we don't care about
487 * sorting all the colors, just finding which are
488 * least used.
489 */
490
491 for (i = num_palette - 1; i >= maximum_colors; i--)
492 {
493 int done; /* To stop early if the list is pre-sorted */
494 int j;
495
496 done = 1;
497 for (j = 0; j < i; j++)
498 {
592 else
593 {
594 /* This is much harder to do simply (and quickly). Perhaps
595 * we need to go through a median cut routine, but those
596 * don't always behave themselves with only a few colors
597 * as input. So we will just find the closest two colors,
598 * and throw out one of them (chosen somewhat randomly).
599 * [We don't understand this at all, so if someone wants to
600 * work on improving it, be our guest - AED, GRP]
601 */
602 int i;
603 int max_d;
604 int num_new_palette;
605 png_dsortp t;
606 png_dsortpp hash;
607
608 t = NULL;
609
610 /* Initialize palette index arrays */
611 png_ptr->index_to_palette = (png_bytep)png_malloc(png_ptr,
612 (png_alloc_size_t)((png_uint_32)num_palette *
613 (sizeof (png_byte))));
614 png_ptr->palette_to_index = (png_bytep)png_malloc(png_ptr,
615 (png_alloc_size_t)((png_uint_32)num_palette *
616 (sizeof (png_byte))));
617
618 /* Initialize the sort array */
619 for (i = 0; i < num_palette; i++)
620 {
621 png_ptr->index_to_palette[i] = (png_byte)i;
622 png_ptr->palette_to_index[i] = (png_byte)i;
623 }
624
625 hash = (png_dsortpp)png_calloc(png_ptr, (png_alloc_size_t)(769 *
626 (sizeof (png_dsortp))));
627
628 num_new_palette = num_palette;
629
630 /* Initial wild guess at how far apart the farthest pixel
631 * pair we will be eliminating will be. Larger
632 * numbers mean more areas will be allocated, Smaller
633 * numbers run the risk of not saving enough data, and
634 * having to do this all over again.
635 *
636 * I have not done extensive checking on this number.
637 */
638 max_d = 96;
639
640 while (num_new_palette > maximum_colors)
641 {
642 for (i = 0; i < num_new_palette - 1; i++)
643 {
644 int j;
645
646 for (j = i + 1; j < num_new_palette; j++)
647 {
648 int d;
649
650 d = PNG_COLOR_DIST(palette[i], palette[j]);
651
652 if (d <= max_d)
653 {
654
655 t = (png_dsortp)png_malloc_warn(png_ptr,
656 (png_alloc_size_t)(sizeof (png_dsort)));
657
658 if (t == NULL)
659 break;
660
661 t->next = hash[d];
662 t->left = (png_byte)i;
663 t->right = (png_byte)j;
664 hash[d] = t;
665 }
666 }
667 if (t == NULL)
668 break;
669 }
670
671 if (t != NULL)
672 for (i = 0; i <= max_d; i++)
673 {
674 if (hash[i] != NULL)
675 {
676 png_dsortp p;
761 num_palette = maximum_colors;
762 }
763 if (png_ptr->palette == NULL)
764 {
765 png_ptr->palette = palette;
766 }
767 png_ptr->num_palette = (png_uint_16)num_palette;
768
769 if (full_quantize != 0)
770 {
771 int i;
772 png_bytep distance;
773 int total_bits = PNG_QUANTIZE_RED_BITS + PNG_QUANTIZE_GREEN_BITS +
774 PNG_QUANTIZE_BLUE_BITS;
775 int num_red = (1 << PNG_QUANTIZE_RED_BITS);
776 int num_green = (1 << PNG_QUANTIZE_GREEN_BITS);
777 int num_blue = (1 << PNG_QUANTIZE_BLUE_BITS);
778 png_size_t num_entries = ((png_size_t)1 << total_bits);
779
780 png_ptr->palette_lookup = (png_bytep)png_calloc(png_ptr,
781 (png_alloc_size_t)(num_entries * (sizeof (png_byte))));
782
783 distance = (png_bytep)png_malloc(png_ptr, (png_alloc_size_t)(num_entries *
784 (sizeof (png_byte))));
785
786 memset(distance, 0xff, num_entries * (sizeof (png_byte)));
787
788 for (i = 0; i < num_palette; i++)
789 {
790 int ir, ig, ib;
791 int r = (palette[i].red >> (8 - PNG_QUANTIZE_RED_BITS));
792 int g = (palette[i].green >> (8 - PNG_QUANTIZE_GREEN_BITS));
793 int b = (palette[i].blue >> (8 - PNG_QUANTIZE_BLUE_BITS));
794
795 for (ir = 0; ir < num_red; ir++)
796 {
797 /* int dr = abs(ir - r); */
798 int dr = ((ir > r) ? ir - r : r - ir);
799 int index_r = (ir << (PNG_QUANTIZE_BLUE_BITS +
800 PNG_QUANTIZE_GREEN_BITS));
801
802 for (ig = 0; ig < num_green; ig++)
803 {
1267 switch (png_ptr->bit_depth)
1268 {
1269 case 1:
1270 gray *= 0xff;
1271 trans_gray *= 0xff;
1272 break;
1273
1274 case 2:
1275 gray *= 0x55;
1276 trans_gray *= 0x55;
1277 break;
1278
1279 case 4:
1280 gray *= 0x11;
1281 trans_gray *= 0x11;
1282 break;
1283
1284 default:
1285
1286 case 8:
1287 /* FALLTHROUGH */ /* (Already 8 bits) */
1288
1289 case 16:
1290 /* Already a full 16 bits */
1291 break;
1292 }
1293
1294 png_ptr->background.red = png_ptr->background.green =
1295 png_ptr->background.blue = (png_uint_16)gray;
1296
1297 if ((png_ptr->transformations & PNG_EXPAND_tRNS) == 0)
1298 {
1299 png_ptr->trans_color.red = png_ptr->trans_color.green =
1300 png_ptr->trans_color.blue = (png_uint_16)trans_gray;
1301 }
1302 }
1303 } /* background expand and (therefore) no alpha association. */
1304 #endif /* READ_EXPAND && READ_BACKGROUND */
1305 }
1306
1307 void /* PRIVATE */
2948 *(dp--) = *(sp - 1);
2949 *(dp--) = *(sp--);
2950 *(dp--) = *(sp--);
2951 }
2952 }
2953 }
2954 row_info->channels = (png_byte)(row_info->channels + 2);
2955 row_info->color_type |= PNG_COLOR_MASK_COLOR;
2956 row_info->pixel_depth = (png_byte)(row_info->channels *
2957 row_info->bit_depth);
2958 row_info->rowbytes = PNG_ROWBYTES(row_info->pixel_depth, row_width);
2959 }
2960 }
2961 #endif
2962
2963 #ifdef PNG_READ_RGB_TO_GRAY_SUPPORTED
2964 /* Reduce RGB files to grayscale, with or without alpha
2965 * using the equation given in Poynton's ColorFAQ of 1998-01-04 at
2966 * <http://www.inforamp.net/~poynton/> (THIS LINK IS DEAD June 2008 but
2967 * versions dated 1998 through November 2002 have been archived at
2968 * https://web.archive.org/web/20000816232553/www.inforamp.net/
2969 * ~poynton/notes/colour_and_gamma/ColorFAQ.txt )
2970 * Charles Poynton poynton at poynton.com
2971 *
2972 * Y = 0.212671 * R + 0.715160 * G + 0.072169 * B
2973 *
2974 * which can be expressed with integers as
2975 *
2976 * Y = (6969 * R + 23434 * G + 2365 * B)/32768
2977 *
2978 * Poynton's current link (as of January 2003 through July 2011):
2979 * <http://www.poynton.com/notes/colour_and_gamma/>
2980 * has changed the numbers slightly:
2981 *
2982 * Y = 0.2126*R + 0.7152*G + 0.0722*B
2983 *
2984 * which can be expressed with integers as
2985 *
2986 * Y = (6966 * R + 23436 * G + 2366 * B)/32768
2987 *
2988 * Historically, however, libpng uses numbers derived from the ITU-R Rec 709
4316
4317 dp--;
4318 }
4319 break;
4320 }
4321
4322 default:
4323 break;
4324 }
4325 row_info->bit_depth = 8;
4326 row_info->pixel_depth = 8;
4327 row_info->rowbytes = row_width;
4328 }
4329
4330 if (row_info->bit_depth == 8)
4331 {
4332 {
4333 if (num_trans > 0)
4334 {
4335 sp = row + (png_size_t)row_width - 1;
4336 dp = row + ((png_size_t)row_width << 2) - 1;
4337
4338 for (i = 0; i < row_width; i++)
4339 {
4340 if ((int)(*sp) >= num_trans)
4341 *dp-- = 0xff;
4342
4343 else
4344 *dp-- = trans_alpha[*sp];
4345
4346 *dp-- = palette[*sp].blue;
4347 *dp-- = palette[*sp].green;
4348 *dp-- = palette[*sp].red;
4349 sp--;
4350 }
4351 row_info->bit_depth = 8;
4352 row_info->pixel_depth = 32;
4353 row_info->rowbytes = row_width * 4;
4354 row_info->color_type = 6;
4355 row_info->channels = 4;
4356 }
4477 dp--;
4478 }
4479 break;
4480 }
4481
4482 default:
4483 break;
4484 }
4485
4486 row_info->bit_depth = 8;
4487 row_info->pixel_depth = 8;
4488 row_info->rowbytes = row_width;
4489 }
4490
4491 if (trans_color != NULL)
4492 {
4493 if (row_info->bit_depth == 8)
4494 {
4495 gray = gray & 0xff;
4496 sp = row + (png_size_t)row_width - 1;
4497 dp = row + ((png_size_t)row_width << 1) - 1;
4498
4499 for (i = 0; i < row_width; i++)
4500 {
4501 if ((*sp & 0xffU) == gray)
4502 *dp-- = 0;
4503
4504 else
4505 *dp-- = 0xff;
4506
4507 *dp-- = *sp--;
4508 }
4509 }
4510
4511 else if (row_info->bit_depth == 16)
4512 {
4513 unsigned int gray_high = (gray >> 8) & 0xff;
4514 unsigned int gray_low = gray & 0xff;
4515 sp = row + row_info->rowbytes - 1;
4516 dp = row + (row_info->rowbytes << 1) - 1;
4517 for (i = 0; i < row_width; i++)
4533 *dp-- = *sp--;
4534 }
4535 }
4536
4537 row_info->color_type = PNG_COLOR_TYPE_GRAY_ALPHA;
4538 row_info->channels = 2;
4539 row_info->pixel_depth = (png_byte)(row_info->bit_depth << 1);
4540 row_info->rowbytes = PNG_ROWBYTES(row_info->pixel_depth,
4541 row_width);
4542 }
4543 }
4544 else if (row_info->color_type == PNG_COLOR_TYPE_RGB &&
4545 trans_color != NULL)
4546 {
4547 if (row_info->bit_depth == 8)
4548 {
4549 png_byte red = (png_byte)(trans_color->red & 0xff);
4550 png_byte green = (png_byte)(trans_color->green & 0xff);
4551 png_byte blue = (png_byte)(trans_color->blue & 0xff);
4552 sp = row + (png_size_t)row_info->rowbytes - 1;
4553 dp = row + ((png_size_t)row_width << 2) - 1;
4554 for (i = 0; i < row_width; i++)
4555 {
4556 if (*(sp - 2) == red && *(sp - 1) == green && *(sp) == blue)
4557 *dp-- = 0;
4558
4559 else
4560 *dp-- = 0xff;
4561
4562 *dp-- = *sp--;
4563 *dp-- = *sp--;
4564 *dp-- = *sp--;
4565 }
4566 }
4567 else if (row_info->bit_depth == 16)
4568 {
4569 png_byte red_high = (png_byte)((trans_color->red >> 8) & 0xff);
4570 png_byte green_high = (png_byte)((trans_color->green >> 8) & 0xff);
4571 png_byte blue_high = (png_byte)((trans_color->blue >> 8) & 0xff);
4572 png_byte red_low = (png_byte)(trans_color->red & 0xff);
4573 png_byte green_low = (png_byte)(trans_color->green & 0xff);
4574 png_byte blue_low = (png_byte)(trans_color->blue & 0xff);
4575 sp = row + row_info->rowbytes - 1;
4576 dp = row + ((png_size_t)row_width << 3) - 1;
4577 for (i = 0; i < row_width; i++)
4578 {
4579 if (*(sp - 5) == red_high &&
4580 *(sp - 4) == red_low &&
4581 *(sp - 3) == green_high &&
4582 *(sp - 2) == green_low &&
4583 *(sp - 1) == blue_high &&
4584 *(sp ) == blue_low)
4585 {
4586 *dp-- = 0;
4587 *dp-- = 0;
4588 }
4589
4590 else
4591 {
4592 *dp-- = 0xff;
4593 *dp-- = 0xff;
4594 }
4595
4596 *dp-- = *sp--;
4615 * whole row to 16 bits. Has no effect otherwise.
4616 */
4617 static void
4618 png_do_expand_16(png_row_infop row_info, png_bytep row)
4619 {
4620 if (row_info->bit_depth == 8 &&
4621 row_info->color_type != PNG_COLOR_TYPE_PALETTE)
4622 {
4623 /* The row have a sequence of bytes containing [0..255] and we need
4624 * to turn it into another row containing [0..65535], to do this we
4625 * calculate:
4626 *
4627 * (input / 255) * 65535
4628 *
4629 * Which happens to be exactly input * 257 and this can be achieved
4630 * simply by byte replication in place (copying backwards).
4631 */
4632 png_byte *sp = row + row_info->rowbytes; /* source, last byte + 1 */
4633 png_byte *dp = sp + row_info->rowbytes; /* destination, end + 1 */
4634 while (dp > sp)
4635 {
4636 dp[-2] = dp[-1] = *--sp; dp -= 2;
4637 }
4638
4639 row_info->rowbytes *= 2;
4640 row_info->bit_depth = 16;
4641 row_info->pixel_depth = (png_byte)(row_info->channels * 16);
4642 }
4643 }
4644 #endif
4645
4646 #ifdef PNG_READ_QUANTIZE_SUPPORTED
4647 static void
4648 png_do_quantize(png_row_infop row_info, png_bytep row,
4649 png_const_bytep palette_lookup, png_const_bytep quantize_lookup)
4650 {
4651 png_bytep sp, dp;
4652 png_uint_32 i;
4653 png_uint_32 row_width=row_info->width;
4654
4655 png_debug(1, "in png_do_quantize");
4656
4657 if (row_info->bit_depth == 8)
|