/* pngrtran.c - transforms the data in a row for PNG readers

 *

 * Last changed in libpng 1.6.19 [November 12, 2015]

 * Copyright (c) 1998-2002,2004,2006-2015 Glenn Randers-Pehrson

 * (Version 0.96 Copyright (c) 1996, 1997 Andreas Dilger)

 * (Version 0.88 Copyright (c) 1995, 1996 Guy Eric Schalnat, Group 42, Inc.)

 *

 * This code is released under the libpng license.

 * For conditions of distribution and use, see the disclaimer

 * and license in png.h

 *

 * This file contains functions optionally called by an application

 * in order to tell libpng how to handle data when reading a PNG.

 * Transformations that are used in both reading and writing are

 * in pngtrans.c.

 */

#include "pngpriv.h"

#ifdef PNG_READ_SUPPORTED

/* Set the action on getting a CRC error for an ancillary or critical chunk. */

void PNGAPI

png_set_crc_action(png_structrp png_ptr, int crit_action, int ancil_action)

{

   png_debug(1, "in png_set_crc_action");

   if (png_ptr == NULL)

      return;

   /* Tell libpng how we react to CRC errors in critical chunks */

   switch (crit_action)

   {

      case PNG_CRC_NO_CHANGE:                        /* Leave setting as is */

         break;

      case PNG_CRC_WARN_USE:                               /* Warn/use data */

         png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;

         png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE;

         break;

      case PNG_CRC_QUIET_USE:                             /* Quiet/use data */

         png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;

         png_ptr->flags |= PNG_FLAG_CRC_CRITICAL_USE |

                           PNG_FLAG_CRC_CRITICAL_IGNORE;

         break;

      case PNG_CRC_WARN_DISCARD:    /* Not a valid action for critical data */

         png_warning(png_ptr,

            "Can't discard critical data on CRC error");

      case PNG_CRC_ERROR_QUIT:                                /* Error/quit */

      case PNG_CRC_DEFAULT:

      default:

         png_ptr->flags &= ~PNG_FLAG_CRC_CRITICAL_MASK;

         break;

   }

   /* Tell libpng how we react to CRC errors in ancillary chunks */

   switch (ancil_action)

   {

      case PNG_CRC_NO_CHANGE:                       /* Leave setting as is */

         break;

      case PNG_CRC_WARN_USE:                              /* Warn/use data */

         png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;

         png_ptr->flags |= PNG_FLAG_CRC_ANCILLARY_USE;

         break;

      case PNG_CRC_QUIET_USE:                            /* Quiet/use data */

         png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;

         png_ptr->flags |= PNG_FLAG_CRC_ANCILLARY_USE |

                           PNG_FLAG_CRC_ANCILLARY_NOWARN;

         break;

      case PNG_CRC_ERROR_QUIT:                               /* Error/quit */

         png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;

         png_ptr->flags |= PNG_FLAG_CRC_ANCILLARY_NOWARN;

         break;

      case PNG_CRC_WARN_DISCARD:                      /* Warn/discard data */

      case PNG_CRC_DEFAULT:

      default:

         png_ptr->flags &= ~PNG_FLAG_CRC_ANCILLARY_MASK;

         break;

   }

}

#ifdef PNG_READ_TRANSFORMS_SUPPORTED

/* Is it OK to set a transformation now?  Only if png_start_read_image or

 * png_read_update_info have not been called.  It is not necessary for the IHDR

 * to have been read in all cases; the need_IHDR parameter allows for this

 * check too.

 */

static int

png_rtran_ok(png_structrp png_ptr, int need_IHDR)

{

   if (png_ptr != NULL)

   {

      if ((png_ptr->flags & PNG_FLAG_ROW_INIT) != 0)

         png_app_error(png_ptr,

            "invalid after png_start_read_image or png_read_update_info");

      else if (need_IHDR && (png_ptr->mode & PNG_HAVE_IHDR) == 0)

         png_app_error(png_ptr, "invalid before the PNG header has been read");

      else

      {

         /* Turn on failure to initialize correctly for all transforms. */

         png_ptr->flags |= PNG_FLAG_DETECT_UNINITIALIZED;

         return 1; /* Ok */

      }

   }

   return 0; /* no png_error possible! */

}

#endif

#ifdef PNG_READ_BACKGROUND_SUPPORTED

/* Handle alpha and tRNS via a background color */

void PNGFAPI

png_set_background_fixed(png_structrp png_ptr,

    png_const_color_16p background_color, int background_gamma_code,

    int need_expand, png_fixed_point background_gamma)

{

   png_debug(1, "in png_set_background_fixed");

   if (png_rtran_ok(png_ptr, 0) == 0 || background_color == NULL)

      return;

   if (background_gamma_code == PNG_BACKGROUND_GAMMA_UNKNOWN)

   {

      png_warning(png_ptr, "Application must supply a known background gamma");

      return;

   }

   png_ptr->transformations |= PNG_COMPOSE | PNG_STRIP_ALPHA;

   png_ptr->transformations &= ~PNG_ENCODE_ALPHA;

   png_ptr->flags &= ~PNG_FLAG_OPTIMIZE_ALPHA;

   png_ptr->background = *background_color;

   png_ptr->background_gamma = background_gamma;

   png_ptr->background_gamma_type = (png_byte)(background_gamma_code);

   if (need_expand != 0)

      png_ptr->transformations |= PNG_BACKGROUND_EXPAND;

   else

      png_ptr->transformations &= ~PNG_BACKGROUND_EXPAND;

}

#  ifdef PNG_FLOATING_POINT_SUPPORTED

void PNGAPI

png_set_background(png_structrp png_ptr,

    png_const_color_16p background_color, int background_gamma_code,

    int need_expand, double background_gamma)

{

   png_set_background_fixed(png_ptr, background_color, background_gamma_code,

      need_expand, png_fixed(png_ptr, background_gamma, "png_set_background"));

}

#  endif  /* FLOATING_POINT */

#endif /* READ_BACKGROUND */

/* Scale 16-bit depth files to 8-bit depth.  If both of these are set then the

 * one that pngrtran does first (scale) happens.  This is necessary to allow the

 * TRANSFORM and API behavior to be somewhat consistent, and it's simpler.

 */

#ifdef PNG_READ_SCALE_16_TO_8_SUPPORTED

void PNGAPI

png_set_scale_16(png_structrp png_ptr)

{

   png_debug(1, "in png_set_scale_16");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   png_ptr->transformations |= PNG_SCALE_16_TO_8;

}

#endif

#ifdef PNG_READ_STRIP_16_TO_8_SUPPORTED

/* Chop 16-bit depth files to 8-bit depth */

void PNGAPI

png_set_strip_16(png_structrp png_ptr)

{

   png_debug(1, "in png_set_strip_16");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   png_ptr->transformations |= PNG_16_TO_8;

}

#endif

#ifdef PNG_READ_STRIP_ALPHA_SUPPORTED

void PNGAPI

png_set_strip_alpha(png_structrp png_ptr)

{

   png_debug(1, "in png_set_strip_alpha");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   png_ptr->transformations |= PNG_STRIP_ALPHA;

}

#endif

#if defined(PNG_READ_ALPHA_MODE_SUPPORTED) || defined(PNG_READ_GAMMA_SUPPORTED)

static png_fixed_point

translate_gamma_flags(png_structrp png_ptr, png_fixed_point output_gamma,

   int is_screen)

{

   /* Check for flag values.  The main reason for having the old Mac value as a

    * flag is that it is pretty near impossible to work out what the correct

    * value is from Apple documentation - a working Mac system is needed to

    * discover the value!

    */

   if (output_gamma == PNG_DEFAULT_sRGB ||

      output_gamma == PNG_FP_1 / PNG_DEFAULT_sRGB)

   {

      /* If there is no sRGB support this just sets the gamma to the standard

       * sRGB value.  (This is a side effect of using this function!)

       */

#     ifdef PNG_READ_sRGB_SUPPORTED

         png_ptr->flags |= PNG_FLAG_ASSUME_sRGB;

#     else

         PNG_UNUSED(png_ptr)

#     endif

      if (is_screen != 0)

         output_gamma = PNG_GAMMA_sRGB;

      else

         output_gamma = PNG_GAMMA_sRGB_INVERSE;

   }

   else if (output_gamma == PNG_GAMMA_MAC_18 ||

      output_gamma == PNG_FP_1 / PNG_GAMMA_MAC_18)

   {

      if (is_screen != 0)

         output_gamma = PNG_GAMMA_MAC_OLD;

      else

         output_gamma = PNG_GAMMA_MAC_INVERSE;

   }

   return output_gamma;

}

#  ifdef PNG_FLOATING_POINT_SUPPORTED

static png_fixed_point

convert_gamma_value(png_structrp png_ptr, double output_gamma)

{

   /* The following silently ignores cases where fixed point (times 100,000)

    * gamma values are passed to the floating point API.  This is safe and it

    * means the fixed point constants work just fine with the floating point

    * API.  The alternative would just lead to undetected errors and spurious

    * bug reports.  Negative values fail inside the _fixed API unless they

    * correspond to the flag values.

    */

   if (output_gamma > 0 && output_gamma < 128)

      output_gamma *= PNG_FP_1;

   /* This preserves -1 and -2 exactly: */

   output_gamma = floor(output_gamma + .5);

   if (output_gamma > PNG_FP_MAX || output_gamma < PNG_FP_MIN)

      png_fixed_error(png_ptr, "gamma value");

   return (png_fixed_point)output_gamma;

}

#  endif

#endif /* READ_ALPHA_MODE || READ_GAMMA */

#ifdef PNG_READ_ALPHA_MODE_SUPPORTED

void PNGFAPI

png_set_alpha_mode_fixed(png_structrp png_ptr, int mode,

   png_fixed_point output_gamma)

{

   int compose = 0;

   png_fixed_point file_gamma;

   png_debug(1, "in png_set_alpha_mode");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   output_gamma = translate_gamma_flags(png_ptr, output_gamma, 1/*screen*/);

   /* Validate the value to ensure it is in a reasonable range. The value

    * is expected to be 1 or greater, but this range test allows for some

    * viewing correction values.  The intent is to weed out users of this API

    * who use the inverse of the gamma value accidentally!  Since some of these

    * values are reasonable this may have to be changed.

    */

   if (output_gamma < 70000 || output_gamma > 300000)

      png_error(png_ptr, "output gamma out of expected range");

   /* The default file gamma is the inverse of the output gamma; the output

    * gamma may be changed below so get the file value first:

    */

   file_gamma = png_reciprocal(output_gamma);

   /* There are really 8 possibilities here, composed of any combination

    * of:

    *

    *    premultiply the color channels

    *    do not encode non-opaque pixels

    *    encode the alpha as well as the color channels

    *

    * The differences disappear if the input/output ('screen') gamma is 1.0,

    * because then the encoding is a no-op and there is only the choice of

    * premultiplying the color channels or not.

    *

    * png_set_alpha_mode and png_set_background interact because both use

    * png_compose to do the work.  Calling both is only useful when

    * png_set_alpha_mode is used to set the default mode - PNG_ALPHA_PNG - along

    * with a default gamma value.  Otherwise PNG_COMPOSE must not be set.

    */

   switch (mode)

   {

      case PNG_ALPHA_PNG:        /* default: png standard */

         /* No compose, but it may be set by png_set_background! */

         png_ptr->transformations &= ~PNG_ENCODE_ALPHA;

         png_ptr->flags &= ~PNG_FLAG_OPTIMIZE_ALPHA;

         break;

      case PNG_ALPHA_ASSOCIATED: /* color channels premultiplied */

         compose = 1;

         png_ptr->transformations &= ~PNG_ENCODE_ALPHA;

         png_ptr->flags &= ~PNG_FLAG_OPTIMIZE_ALPHA;

         /* The output is linear: */

         output_gamma = PNG_FP_1;

         break;

      case PNG_ALPHA_OPTIMIZED:  /* associated, non-opaque pixels linear */

         compose = 1;

         png_ptr->transformations &= ~PNG_ENCODE_ALPHA;

         png_ptr->flags |= PNG_FLAG_OPTIMIZE_ALPHA;

         /* output_gamma records the encoding of opaque pixels! */

         break;

      case PNG_ALPHA_BROKEN:     /* associated, non-linear, alpha encoded */

         compose = 1;

         png_ptr->transformations |= PNG_ENCODE_ALPHA;

         png_ptr->flags &= ~PNG_FLAG_OPTIMIZE_ALPHA;

         break;

      default:

         png_error(png_ptr, "invalid alpha mode");

   }

   /* Only set the default gamma if the file gamma has not been set (this has

    * the side effect that the gamma in a second call to png_set_alpha_mode will

    * be ignored.)

    */

   if (png_ptr->colorspace.gamma == 0)

   {

      png_ptr->colorspace.gamma = file_gamma;

      png_ptr->colorspace.flags |= PNG_COLORSPACE_HAVE_GAMMA;

   }

   /* But always set the output gamma: */

   png_ptr->screen_gamma = output_gamma;

   /* Finally, if pre-multiplying, set the background fields to achieve the

    * desired result.

    */

   if (compose != 0)

   {

      /* And obtain alpha pre-multiplication by composing on black: */

      memset(&png_ptr->background, 0, (sizeof png_ptr->background));

      png_ptr->background_gamma = png_ptr->colorspace.gamma; /* just in case */

      png_ptr->background_gamma_type = PNG_BACKGROUND_GAMMA_FILE;

      png_ptr->transformations &= ~PNG_BACKGROUND_EXPAND;

      if ((png_ptr->transformations & PNG_COMPOSE) != 0)

         png_error(png_ptr,

            "conflicting calls to set alpha mode and background");

      png_ptr->transformations |= PNG_COMPOSE;

   }

}

#  ifdef PNG_FLOATING_POINT_SUPPORTED

void PNGAPI

png_set_alpha_mode(png_structrp png_ptr, int mode, double output_gamma)

{

   png_set_alpha_mode_fixed(png_ptr, mode, convert_gamma_value(png_ptr,

      output_gamma));

}

#  endif

#endif

#ifdef PNG_READ_QUANTIZE_SUPPORTED

/* Dither file to 8-bit.  Supply a palette, the current number

 * of elements in the palette, the maximum number of elements

 * allowed, and a histogram if possible.  If the current number

 * of colors is greater than the maximum number, the palette will be

 * modified to fit in the maximum number.  "full_quantize" indicates

 * whether we need a quantizing cube set up for RGB images, or if we

 * simply are reducing the number of colors in a paletted image.

 */

typedef struct png_dsort_struct

{

   struct png_dsort_struct * next;

   png_byte left;

   png_byte right;

} png_dsort;

typedef png_dsort *   png_dsortp;

typedef png_dsort * * png_dsortpp;

void PNGAPI

png_set_quantize(png_structrp png_ptr, png_colorp palette,

    int num_palette, int maximum_colors, png_const_uint_16p histogram,

    int full_quantize)

{

   png_debug(1, "in png_set_quantize");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   png_ptr->transformations |= PNG_QUANTIZE;

   if (full_quantize == 0)

   {

      int i;

      png_ptr->quantize_index = (png_bytep)png_malloc(png_ptr,

          (png_uint_32)(num_palette * (sizeof (png_byte))));

      for (i = 0; i < num_palette; i++)

         png_ptr->quantize_index[i] = (png_byte)i;

   }

   if (num_palette > maximum_colors)

   {

      if (histogram != NULL)

      {

         /* This is easy enough, just throw out the least used colors.

          * Perhaps not the best solution, but good enough.

          */

         int i;

         /* Initialize an array to sort colors */

         png_ptr->quantize_sort = (png_bytep)png_malloc(png_ptr,

             (png_uint_32)(num_palette * (sizeof (png_byte))));

         /* Initialize the quantize_sort array */

         for (i = 0; i < num_palette; i++)

            png_ptr->quantize_sort[i] = (png_byte)i;

         /* Find the least used palette entries by starting a

          * bubble sort, and running it until we have sorted

          * out enough colors.  Note that we don't care about

          * sorting all the colors, just finding which are

          * least used.

          */

         for (i = num_palette - 1; i >= maximum_colors; i--)

         {

            int done; /* To stop early if the list is pre-sorted */

            int j;

            done = 1;

            for (j = 0; j < i; j++)

            {

               if (histogram[png_ptr->quantize_sort[j]]

                   < histogram[png_ptr->quantize_sort[j + 1]])

               {

                  png_byte t;

                  t = png_ptr->quantize_sort[j];

                  png_ptr->quantize_sort[j] = png_ptr->quantize_sort[j + 1];

                  png_ptr->quantize_sort[j + 1] = t;

                  done = 0;

               }

            }

            if (done != 0)

               break;

         }

         /* Swap the palette around, and set up a table, if necessary */

         if (full_quantize != 0)

         {

            int j = num_palette;

            /* Put all the useful colors within the max, but don't

             * move the others.

             */

            for (i = 0; i < maximum_colors; i++)

            {

               if ((int)png_ptr->quantize_sort[i] >= maximum_colors)

               {

                  do

                     j--;

                  while ((int)png_ptr->quantize_sort[j] >= maximum_colors);

                  palette[i] = palette[j];

               }

            }

         }

         else

         {

            int j = num_palette;

            /* Move all the used colors inside the max limit, and

             * develop a translation table.

             */

            for (i = 0; i < maximum_colors; i++)

            {

               /* Only move the colors we need to */

               if ((int)png_ptr->quantize_sort[i] >= maximum_colors)

               {

                  png_color tmp_color;

                  do

                     j--;

                  while ((int)png_ptr->quantize_sort[j] >= maximum_colors);

                  tmp_color = palette[j];

                  palette[j] = palette[i];

                  palette[i] = tmp_color;

                  /* Indicate where the color went */

                  png_ptr->quantize_index[j] = (png_byte)i;

                  png_ptr->quantize_index[i] = (png_byte)j;

               }

            }

            /* Find closest color for those colors we are not using */

            for (i = 0; i < num_palette; i++)

            {

               if ((int)png_ptr->quantize_index[i] >= maximum_colors)

               {

                  int min_d, k, min_k, d_index;

                  /* Find the closest color to one we threw out */

                  d_index = png_ptr->quantize_index[i];

                  min_d = PNG_COLOR_DIST(palette[d_index], palette[0]);

                  for (k = 1, min_k = 0; k < maximum_colors; k++)

                  {

                     int d;

                     d = PNG_COLOR_DIST(palette[d_index], palette[k]);

                     if (d < min_d)

                     {

                        min_d = d;

                        min_k = k;

                     }

                  }

                  /* Point to closest color */

                  png_ptr->quantize_index[i] = (png_byte)min_k;

               }

            }

         }

         png_free(png_ptr, png_ptr->quantize_sort);

         png_ptr->quantize_sort = NULL;

      }

      else

      {

         /* This is much harder to do simply (and quickly).  Perhaps

          * we need to go through a median cut routine, but those

          * don't always behave themselves with only a few colors

          * as input.  So we will just find the closest two colors,

          * and throw out one of them (chosen somewhat randomly).

          * [We don't understand this at all, so if someone wants to

          *  work on improving it, be our guest - AED, GRP]

          */

         int i;

         int max_d;

         int num_new_palette;

         png_dsortp t;

         png_dsortpp hash;

         t = NULL;

         /* Initialize palette index arrays */

         png_ptr->index_to_palette = (png_bytep)png_malloc(png_ptr,

             (png_uint_32)(num_palette * (sizeof (png_byte))));

         png_ptr->palette_to_index = (png_bytep)png_malloc(png_ptr,

             (png_uint_32)(num_palette * (sizeof (png_byte))));

         /* Initialize the sort array */

         for (i = 0; i < num_palette; i++)

         {

            png_ptr->index_to_palette[i] = (png_byte)i;

            png_ptr->palette_to_index[i] = (png_byte)i;

         }

         hash = (png_dsortpp)png_calloc(png_ptr, (png_uint_32)(769 *

             (sizeof (png_dsortp))));

         num_new_palette = num_palette;

         /* Initial wild guess at how far apart the farthest pixel

          * pair we will be eliminating will be.  Larger

          * numbers mean more areas will be allocated, Smaller

          * numbers run the risk of not saving enough data, and

          * having to do this all over again.

          *

          * I have not done extensive checking on this number.

          */

         max_d = 96;

         while (num_new_palette > maximum_colors)

         {

            for (i = 0; i < num_new_palette - 1; i++)

            {

               int j;

               for (j = i + 1; j < num_new_palette; j++)

               {

                  int d;

                  d = PNG_COLOR_DIST(palette[i], palette[j]);

                  if (d <= max_d)

                  {

                     t = (png_dsortp)png_malloc_warn(png_ptr,

                         (png_uint_32)(sizeof (png_dsort)));

                     if (t == NULL)

                         break;

                     t->next = hash[d];

                     t->left = (png_byte)i;

                     t->right = (png_byte)j;

                     hash[d] = t;

                  }

               }

               if (t == NULL)

                  break;

            }

            if (t != NULL)

            for (i = 0; i <= max_d; i++)

            {

               if (hash[i] != NULL)

               {

                  png_dsortp p;

                  for (p = hash[i]; p; p = p->next)

                  {

                     if ((int)png_ptr->index_to_palette[p->left]

                         < num_new_palette &&

                         (int)png_ptr->index_to_palette[p->right]

                         < num_new_palette)

                     {

                        int j, next_j;

                        if (num_new_palette & 0x01)

                        {

                           j = p->left;

                           next_j = p->right;

                        }

                        else

                        {

                           j = p->right;

                           next_j = p->left;

                        }

                        num_new_palette--;

                        palette[png_ptr->index_to_palette[j]]

                            = palette[num_new_palette];

                        if (full_quantize == 0)

                        {

                           int k;

                           for (k = 0; k < num_palette; k++)

                           {

                              if (png_ptr->quantize_index[k] ==

                                  png_ptr->index_to_palette[j])

                                 png_ptr->quantize_index[k] =

                                     png_ptr->index_to_palette[next_j];

                              if ((int)png_ptr->quantize_index[k] ==

                                  num_new_palette)

                                 png_ptr->quantize_index[k] =

                                     png_ptr->index_to_palette[j];

                           }

                        }

                        png_ptr->index_to_palette[png_ptr->palette_to_index

                            [num_new_palette]] = png_ptr->index_to_palette[j];

                        png_ptr->palette_to_index[png_ptr->index_to_palette[j]]

                            = png_ptr->palette_to_index[num_new_palette];

                        png_ptr->index_to_palette[j] =

                            (png_byte)num_new_palette;

                        png_ptr->palette_to_index[num_new_palette] =

                            (png_byte)j;

                     }

                     if (num_new_palette <= maximum_colors)

                        break;

                  }

                  if (num_new_palette <= maximum_colors)

                     break;

               }

            }

            for (i = 0; i < 769; i++)

            {

               if (hash[i] != NULL)

               {

                  png_dsortp p = hash[i];

                  while (p)

                  {

                     t = p->next;

                     png_free(png_ptr, p);

                     p = t;

                  }

               }

               hash[i] = 0;

            }

            max_d += 96;

         }

         png_free(png_ptr, hash);

         png_free(png_ptr, png_ptr->palette_to_index);

         png_free(png_ptr, png_ptr->index_to_palette);

         png_ptr->palette_to_index = NULL;

         png_ptr->index_to_palette = NULL;

      }

      num_palette = maximum_colors;

   }

   if (png_ptr->palette == NULL)

   {

      png_ptr->palette = palette;

   }

   png_ptr->num_palette = (png_uint_16)num_palette;

   if (full_quantize != 0)

   {

      int i;

      png_bytep distance;

      int total_bits = PNG_QUANTIZE_RED_BITS + PNG_QUANTIZE_GREEN_BITS +

          PNG_QUANTIZE_BLUE_BITS;

      int num_red = (1 << PNG_QUANTIZE_RED_BITS);

      int num_green = (1 << PNG_QUANTIZE_GREEN_BITS);

      int num_blue = (1 << PNG_QUANTIZE_BLUE_BITS);

      png_size_t num_entries = ((png_size_t)1 << total_bits);

      png_ptr->palette_lookup = (png_bytep)png_calloc(png_ptr,

          (png_uint_32)(num_entries * (sizeof (png_byte))));

      distance = (png_bytep)png_malloc(png_ptr, (png_uint_32)(num_entries *

          (sizeof (png_byte))));

      memset(distance, 0xff, num_entries * (sizeof (png_byte)));

      for (i = 0; i < num_palette; i++)

      {

         int ir, ig, ib;

         int r = (palette[i].red >> (8 - PNG_QUANTIZE_RED_BITS));

         int g = (palette[i].green >> (8 - PNG_QUANTIZE_GREEN_BITS));

         int b = (palette[i].blue >> (8 - PNG_QUANTIZE_BLUE_BITS));

         for (ir = 0; ir < num_red; ir++)

         {

            /* int dr = abs(ir - r); */

            int dr = ((ir > r) ? ir - r : r - ir);

            int index_r = (ir << (PNG_QUANTIZE_BLUE_BITS +

                PNG_QUANTIZE_GREEN_BITS));

            for (ig = 0; ig < num_green; ig++)

            {

               /* int dg = abs(ig - g); */

               int dg = ((ig > g) ? ig - g : g - ig);

               int dt = dr + dg;

               int dm = ((dr > dg) ? dr : dg);

               int index_g = index_r | (ig << PNG_QUANTIZE_BLUE_BITS);

               for (ib = 0; ib < num_blue; ib++)

               {

                  int d_index = index_g | ib;

                  /* int db = abs(ib - b); */

                  int db = ((ib > b) ? ib - b : b - ib);

                  int dmax = ((dm > db) ? dm : db);

                  int d = dmax + dt + db;

                  if (d < (int)distance[d_index])

                  {

                     distance[d_index] = (png_byte)d;

                     png_ptr->palette_lookup[d_index] = (png_byte)i;

                  }

               }

            }

         }

      }

      png_free(png_ptr, distance);

   }

}

#endif /* READ_QUANTIZE */

#ifdef PNG_READ_GAMMA_SUPPORTED

void PNGFAPI

png_set_gamma_fixed(png_structrp png_ptr, png_fixed_point scrn_gamma,

   png_fixed_point file_gamma)

{

   png_debug(1, "in png_set_gamma_fixed");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   /* New in libpng-1.5.4 - reserve particular negative values as flags. */

   scrn_gamma = translate_gamma_flags(png_ptr, scrn_gamma, 1/*screen*/);

   file_gamma = translate_gamma_flags(png_ptr, file_gamma, 0/*file*/);

   /* Checking the gamma values for being >0 was added in 1.5.4 along with the

    * premultiplied alpha support; this actually hides an undocumented feature

    * of the previous implementation which allowed gamma processing to be

    * disabled in background handling.  There is no evidence (so far) that this

    * was being used; however, png_set_background itself accepted and must still

    * accept '0' for the gamma value it takes, because it isn't always used.

    *

    * Since this is an API change (albeit a very minor one that removes an

    * undocumented API feature) the following checks were only enabled in

    * libpng-1.6.0.

    */

   if (file_gamma <= 0)

      png_error(png_ptr, "invalid file gamma in png_set_gamma");

   if (scrn_gamma <= 0)

      png_error(png_ptr, "invalid screen gamma in png_set_gamma");

   /* Set the gamma values unconditionally - this overrides the value in the PNG

    * file if a gAMA chunk was present.  png_set_alpha_mode provides a

    * different, easier, way to default the file gamma.

    */

   png_ptr->colorspace.gamma = file_gamma;

   png_ptr->colorspace.flags |= PNG_COLORSPACE_HAVE_GAMMA;

   png_ptr->screen_gamma = scrn_gamma;

}

#  ifdef PNG_FLOATING_POINT_SUPPORTED

void PNGAPI

png_set_gamma(png_structrp png_ptr, double scrn_gamma, double file_gamma)

{

   png_set_gamma_fixed(png_ptr, convert_gamma_value(png_ptr, scrn_gamma),

      convert_gamma_value(png_ptr, file_gamma));

}

#  endif /* FLOATING_POINT */

#endif /* READ_GAMMA */

#ifdef PNG_READ_EXPAND_SUPPORTED

/* Expand paletted images to RGB, expand grayscale images of

 * less than 8-bit depth to 8-bit depth, and expand tRNS chunks

 * to alpha channels.

 */

void PNGAPI

png_set_expand(png_structrp png_ptr)

{

   png_debug(1, "in png_set_expand");

   if (png_rtran_ok(png_ptr, 0) == 0)

      return;

   png_ptr->transformations |= (PNG_EXPAND | PNG_EXPAND_tRNS);

}

/* GRR 19990627:  the following three functions currently are identical

 *  to png_set_expand().  However, it is entirely reasonable that someone

 *  might wish to expand an indexed image to RGB but *not* expand a single,

 *  fully transparent palette entry to a full alpha channel--perhaps instead

 *  convert tRNS to the grayscale/RGB format (16-bit RGB value), or replace

 *  the transparent color with a particular RGB value, or drop tRNS entirely.

 *  IOW, a future version of the library may make the transformations flag

 *  a bit more fine-grained, with separate bits for each of these three

 *  functions.

 *

 *  More to the point, these functions make it obvious what libpng will be

 *  doing, whereas "expand" can (and does) mean any number of things.

 *

 *  GRP 20060307: In libpng-1.2.9, png_set_gray_1_2_4_to_8() was modified