Commit 6af9c204f for imagemagick.org

commit 6af9c204f68acab4789493b20ef98a2af52e19cc
Author: Cristy <urban-warrior@imagemagick.org>
Date:   Thu Nov 19 19:50:27 2026 -0500

    an out-of-memory error during tree building put pixel data into the wrong tree node

diff --git a/MagickCore/quantize.c b/MagickCore/quantize.c
index cf033d1e1..5bbbd4ead 100644
--- a/MagickCore/quantize.c
+++ b/MagickCore/quantize.c
@@ -75,14 +75,14 @@
 %  tree for the image.  Reduction collapses the tree until the number it
 %  represents, at most, the number of colors desired in the output image.
 %  Assignment defines the output image's color map and sets each pixel's
-%  color by restorage_class in the reduced tree.  Our goal is to minimize
+%  color by reclassification in the reduced tree.  Our goal is to minimize
 %  the numerical discrepancies between the original colors and quantized
 %  colors (quantization error).
 %
 %  Classification begins by initializing a color description tree of
 %  sufficient depth to represent each possible input color in a leaf.
 %  However, it is impractical to generate a fully-formed color description
-%  tree in the storage_class phase for realistic values of Cmax.  If
+%  tree in the classification phase for realistic values of Cmax.  If
 %  colors components in the input image are quantized to k-bit precision,
 %  so that Cmax= 2k-1, the tree would need k levels below the root node to
 %  allow representing each possible input color in a leaf.  This becomes
@@ -95,7 +95,7 @@
 %  Chooses a maximum depth for the tree as a function of the desired
 %  number of colors in the output image (currently log2(colormap size)).
 %
-%  For each pixel in the input image, storage_class scans downward from
+%  For each pixel in the input image, classification scans downward from
 %  the root of the color description tree.  At each level of the tree it
 %  identifies the single node which represents a cube in RGB space
 %  containing the pixel's color.  It updates the following data for each
@@ -690,7 +690,7 @@ static MagickBooleanType AssignImageColors(Image *image,QCubeInfo *cube_info,
 %  ClassifyImageColors() begins by initializing a color description tree
 %  of sufficient depth to represent each possible input color in a leaf.
 %  However, it is impractical to generate a fully-formed color
-%  description tree in the storage_class phase for realistic values of
+%  description tree in the classification phase for realistic values of
 %  Cmax.  If colors components in the input image are quantized to k-bit
 %  precision, so that Cmax= 2k-1, the tree would need k levels below the
 %  root node to allow representing each possible input color in a leaf.
@@ -703,7 +703,7 @@ static MagickBooleanType AssignImageColors(Image *image,QCubeInfo *cube_info,
 %  Chooses a maximum depth for the tree as a function of the desired
 %  number of colors in the output image (currently log2(colormap size)).
 %
-%  For each pixel in the input image, storage_class scans downward from
+%  For each pixel in the input image, classification scans downward from
 %  the root of the color description tree.  At each level of the tree it
 %  identifies the single node which represents a cube in RGB space
 %  containing It updates the following data for each such node:
@@ -769,7 +769,8 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
     pixel;

   MagickBooleanType
-    proceed;
+    proceed,
+    status;

   QNodeInfo
     *node_info;
@@ -803,6 +804,7 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
   midpoint.blue=(double) QuantumRange/2.0;
   midpoint.alpha=(double) QuantumRange/2.0;
   error.alpha=0.0;
+  status=MagickTrue;
   image_view=AcquireVirtualCacheView(image,exception);
   for (y=0; y < (ssize_t) image->rows; y++)
   {
@@ -814,7 +816,10 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,

     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
     if (p == (const Quantum *) NULL)
-      break;
+      {
+        status=MagickFalse;
+        break;
+      }
     if (cube_info->nodes > MaxQNodes)
       {
         /*
@@ -865,7 +870,8 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
                 (void) ThrowMagickException(exception,GetMagickModule(),
                   ResourceLimitError,"MemoryAllocationFailed","`%s'",
                   image->filename);
-                continue;
+                status=MagickFalse;
+                break;
               }
             if (level == MaxTreeDepth)
               cube_info->colors++;
@@ -887,6 +893,8 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
         cube_info->root->quantize_error+=node_info->quantize_error;
         index--;
       }
+      if (status == MagickFalse)
+        break;
       /*
         Sum RGB for this leaf for later derivation of the mean cube color.
       */
@@ -906,6 +914,8 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
           ClampPixel((double) OpaqueAlpha);
       p+=(ptrdiff_t) count*(ssize_t) GetPixelChannels(image);
     }
+    if (status == MagickFalse)
+      break;
     if (cube_info->colors > cube_info->maximum_colors)
       {
         PruneToCubeDepth(cube_info,cube_info->root);
@@ -914,8 +924,12 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
     proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
       image->rows);
     if (proceed == MagickFalse)
-      break;
+      {
+        status=MagickFalse;
+        break;
+      }
   }
+  if (status != MagickFalse)
   for (y++; y < (ssize_t) image->rows; y++)
   {
     const Quantum
@@ -926,7 +940,10 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,

     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
     if (p == (const Quantum *) NULL)
-      break;
+      {
+        status=MagickFalse;
+        break;
+      }
     if (cube_info->nodes > MaxQNodes)
       {
         /*
@@ -975,9 +992,10 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
             if (node_info->child[id] == (QNodeInfo *) NULL)
               {
                 (void) ThrowMagickException(exception,GetMagickModule(),
-                  ResourceLimitError,"MemoryAllocationFailed","%s",
+                  ResourceLimitError,"MemoryAllocationFailed","`%s'",
                   image->filename);
-                continue;
+                status=MagickFalse;
+                break;
               }
             if (level == cube_info->depth)
               cube_info->colors++;
@@ -999,6 +1017,8 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
         cube_info->root->quantize_error+=node_info->quantize_error;
         index--;
       }
+      if (status == MagickFalse)
+        break;
       /*
         Sum RGB for this leaf for later derivation of the mean cube color.
       */
@@ -1018,17 +1038,22 @@ static MagickBooleanType ClassifyImageColors(QCubeInfo *cube_info,
           ClampPixel((MagickRealType) OpaqueAlpha);
       p+=(ptrdiff_t) count*(ssize_t) GetPixelChannels(image);
     }
+    if (status == MagickFalse)
+      break;
     proceed=SetImageProgress(image,ClassifyImageTag,(MagickOffsetType) y,
       image->rows);
     if (proceed == MagickFalse)
-      break;
+      {
+        status=MagickFalse;
+        break;
+      }
   }
   image_view=DestroyCacheView(image_view);
   if (cube_info->quantize_info->colorspace != image->colorspace)
     if ((cube_info->quantize_info->colorspace != UndefinedColorspace) &&
         (cube_info->quantize_info->colorspace != CMYKColorspace))
       (void) TransformImageColorspace((Image *) image,sRGBColorspace,exception);
-  return(y < (ssize_t) image->rows ? MagickFalse : MagickTrue);
+  return(status);
 }

 /*
@@ -1230,7 +1255,7 @@ MagickExport MagickBooleanType CompressImageColormap(Image *image,
 %
 %  DefineImageColormap() traverses the color cube tree and notes each colormap
 %  entry.  A colormap entry is any node in the color cube tree where the
-%  of unique colors is not zero.
+%  number of unique colors is not zero.
 %
 %  The format of the DefineImageColormap method is:
 %
@@ -1689,8 +1714,6 @@ static MagickBooleanType FloydSteinbergDither(Image *image,QCubeInfo *cube_info,
             SetPixelAlpha(image,ClampToQuantum(image->colormap[index].alpha),
               q+u*(ssize_t) GetPixelChannels(image));
         }
-      if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
-        status=MagickFalse;
       /*
         Store the error.
       */
@@ -1711,10 +1734,12 @@ static MagickBooleanType FloydSteinbergDither(Image *image,QCubeInfo *cube_info,
             status=MagickFalse;
         }
     }
+    if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
+      status=MagickFalse;
   }
   image_view=DestroyCacheView(image_view);
   pixels=DestroyPixelTLS(pixels);
-  return(MagickTrue);
+  return(status);
 }

 static MagickBooleanType RiemersmaDither(Image *image,CacheView *image_view,
@@ -2116,7 +2141,10 @@ static QCubeInfo *GetQCubeInfo(const QuantizeInfo *quantize_info,
   */
   cube_info->root=GetQNodeInfo(cube_info,0,0,(QNodeInfo *) NULL);
   if (cube_info->root == (QNodeInfo *) NULL)
-    return((QCubeInfo *) NULL);
+    {
+      cube_info=(QCubeInfo *) RelinquishMagickMemory(cube_info);
+      return((QCubeInfo *) NULL);
+    }
   cube_info->root->parent=cube_info->root;
   cube_info->quantize_info=CloneQuantizeInfo(quantize_info);
   if (cube_info->quantize_info->dither_method == NoDitherMethod)
@@ -2127,7 +2155,10 @@ static QCubeInfo *GetQCubeInfo(const QuantizeInfo *quantize_info,
   cube_info->cache=(ssize_t **) AcquireQuantumMemory(CacheBlocks,
     sizeof(*cube_info->cache));
   if (cube_info->cache == (ssize_t **) NULL)
-    return((QCubeInfo *) NULL);
+    {
+      DestroyQCubeInfo(cube_info);
+      return((QCubeInfo *) NULL);
+    }
   (void) memset(cube_info->cache,0,CacheBlocks*sizeof(*cube_info->cache));
   /*
     Distribute weights along a curve of exponential decay.
@@ -2167,7 +2198,7 @@ static QCubeInfo *GetQCubeInfo(const QuantizeInfo *quantize_info,
 %
 %    o id: Specifies the child number of the node.
 %
-%    o level: Specifies the level in the storage_class the node resides.
+%    o level: Specifies the level in the tree the node resides.
 %
 */
 static QNodeInfo *GetQNodeInfo(QCubeInfo *cube_info,const size_t id,
@@ -2190,7 +2221,10 @@ static QNodeInfo *GetQNodeInfo(QCubeInfo *cube_info,const size_t id,
       nodes->nodes=(QNodeInfo *) AcquireQuantumMemory(QNodesInAList,
         sizeof(*nodes->nodes));
       if (nodes->nodes == (QNodeInfo *) NULL)
-        return((QNodeInfo *) NULL);
+        {
+          nodes=(QNodes *) RelinquishMagickMemory(nodes);
+          return((QNodeInfo *) NULL);
+        }
       nodes->next=cube_info->node_queue;
       cube_info->node_queue=nodes;
       cube_info->next_node=nodes->nodes;
@@ -2263,6 +2297,9 @@ MagickExport MagickBooleanType GetImageQuantizeError(Image *image,
     mean_error,
     mean_error_per_pixel;

+  MagickBooleanType
+    status;
+
   ssize_t
     index,
     y;
@@ -2281,6 +2318,7 @@ MagickExport MagickBooleanType GetImageQuantizeError(Image *image,
   maximum_error=0.0;
   mean_error_per_pixel=0.0;
   mean_error=0.0;
+  status=MagickTrue;
   image_view=AcquireVirtualCacheView(image,exception);
   for (y=0; y < (ssize_t) image->rows; y++)
   {
@@ -2292,7 +2330,10 @@ MagickExport MagickBooleanType GetImageQuantizeError(Image *image,

     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
     if (p == (const Quantum *) NULL)
-      break;
+      {
+        status=MagickFalse;
+        break;
+      }
     for (x=0; x < (ssize_t) image->columns; x++)
     {
       index=(ssize_t) GetPixelIndex(image,p);
@@ -2323,6 +2364,8 @@ MagickExport MagickBooleanType GetImageQuantizeError(Image *image,
     }
   }
   image_view=DestroyCacheView(image_view);
+  if (status == MagickFalse)
+    return(MagickFalse);
   image->error.mean_error_per_pixel=(double) mean_error_per_pixel/area;
   image->error.normalized_mean_error=(double) QuantumScale*QuantumScale*
     mean_error/area;
@@ -2432,7 +2475,11 @@ static int DominantColorCompare(const void *x,const void *y)

   pixel_1=(PixelInfo *) x;
   pixel_2=(PixelInfo *) y;
-  return((int) pixel_2->count-(int) pixel_1->count);
+  if (pixel_2->count > pixel_1->count)
+    return(1);
+  if (pixel_2->count < pixel_1->count)
+    return(-1);
+  return(0);
 }

 static KmeansInfo **AcquireKmeansTLS(const size_t number_colors)
@@ -2549,7 +2596,7 @@ MagickExport MagickBooleanType KmeansImage(Image *image,
   assert(exception->signature == MagickCoreSignature);
   if (IsEventLogging() != MagickFalse)
     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
-  if (max_iterations == 0)
+  if ((number_colors == 0) || (max_iterations == 0))
     return(MagickFalse);
   colors=GetImageArtifact(image,"kmeans:seed-colors");
   if (colors == (const char *) NULL)
@@ -2652,7 +2699,7 @@ MagickExport MagickBooleanType KmeansImage(Image *image,
   /*
     Iterative refinement.
   */
-  kmeans_pixels=AcquireKmeansTLS(number_colors);
+  kmeans_pixels=AcquireKmeansTLS(MagickMax(number_colors,image->colors));
   if (kmeans_pixels == (KmeansInfo **) NULL)
     ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
       image->filename);
@@ -2937,6 +2984,7 @@ MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
         }
       if (SetImageStorageClass(map_image,DirectClass,exception) == MagickFalse)
         {
+          map_image=DestroyImage(map_image);
           status=MagickFalse;
           break;
         }
@@ -2960,9 +3008,10 @@ MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
         map_image_view=AcquireAuthenticCacheView (map_image,exception);
         q=GetCacheViewAuthenticPixels(map_image_view,0,0,number_columns,1,
           exception);
-        if (q == (const Quantum *) NULL)
+        if (q == (Quantum *) NULL)
           {
             map_image_view=DestroyCacheView(map_image_view);
+            map_image=DestroyImage(map_image);
             status=MagickFalse;
             break;
           }
@@ -2985,6 +3034,7 @@ MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
         if (SyncCacheViewAuthenticPixels(map_image_view,exception) == MagickFalse)
           {
             map_image_view=DestroyCacheView(map_image_view);
+            map_image=DestroyImage(map_image);
             status=MagickFalse;
             break;
           }
@@ -2997,7 +3047,7 @@ MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
           */
           QuantizeInfo *quantize_info = AcquireQuantizeInfo((ImageInfo *) NULL);
           quantize_info->dither_method=dither_method;
-          (void) RemapImage(quantize_info,image,map_image,exception);
+          status=RemapImage(quantize_info,image,map_image,exception);
           quantize_info=DestroyQuantizeInfo(quantize_info);
       }
       map_image=DestroyImage(map_image);
@@ -3096,10 +3146,11 @@ MagickExport MagickBooleanType PosterizeImage(Image *image,const size_t levels,
       image_view=DestroyCacheView(image_view);
       {
         QuantizeInfo *quantize_info=AcquireQuantizeInfo((ImageInfo *) NULL);
-        quantize_info->number_colors=(size_t) MagickMin(levels*levels*levels,
-          MaxColormapSize);
+        quantize_info->number_colors=(levels > 40) ? (size_t) MaxColormapSize :
+          (size_t) MagickMin(levels*levels*levels,MaxColormapSize);
         quantize_info->dither_method=dither_method;
-        status=QuantizeImage(quantize_info,image,exception);
+        if (status != MagickFalse)
+          status=QuantizeImage(quantize_info,image,exception);
         quantize_info=DestroyQuantizeInfo(quantize_info);
       }
     }
@@ -3464,9 +3515,9 @@ MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
     progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor) NULL,
       image->client_data);
     status=ClassifyImageColors(cube_info,image,exception);
+    (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
     if (status == MagickFalse)
       break;
-    (void) SetImageProgressMonitor(image,progress_monitor,image->client_data);
     proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
       number_images);
     if (proceed == MagickFalse)
@@ -3485,10 +3536,10 @@ MagickExport MagickBooleanType QuantizeImages(const QuantizeInfo *quantize_info,
         progress_monitor=SetImageProgressMonitor(image,(MagickProgressMonitor)
           NULL,image->client_data);
         status=AssignImageColors(image,cube_info,exception);
-        if (status == MagickFalse)
-          break;
         (void) SetImageProgressMonitor(image,progress_monitor,
           image->client_data);
+        if (status == MagickFalse)
+          break;
         proceed=SetImageProgress(image,AssignImageTag,(MagickOffsetType) i,
           number_images);
         if (proceed == MagickFalse)
@@ -3926,11 +3977,11 @@ static int IntensityCompare(const void *x,const void *y)
   color_2=(PixelInfo *) y;
   intensity=GetPixelInfoIntensity((const Image *) NULL,color_1)-
     GetPixelInfoIntensity((const Image *) NULL,color_2);
-  if (intensity < (double) INT_MIN)
-    intensity=(double) INT_MIN;
-  if (intensity > (double) INT_MAX)
-    intensity=(double) INT_MAX;
-  return((int) intensity);
+  if (intensity < 0.0)
+    return(-1);
+  if (intensity > 0.0)
+    return(1);
+  return(0);
 }

 #if defined(__cplusplus) || defined(c_plusplus)
@@ -4031,6 +4082,11 @@ static MagickBooleanType SetGrayscaleImage(Image *image,
           status=MagickFalse;
       }
       image_view=DestroyCacheView(image_view);
+      if (status == MagickFalse)
+        {
+          colormap_index=(ssize_t *) RelinquishMagickMemory(colormap_index);
+          return(MagickFalse);
+        }
     }
   (void) memset(colormap_index,0,extent*sizeof(*colormap_index));
   for (i=0; i < (ssize_t) image->colors; i++)
@@ -4082,8 +4138,8 @@ static MagickBooleanType SetGrayscaleImage(Image *image,
       }
     for (x=0; x < (ssize_t) image->columns; x++)
     {
-      SetPixelIndex(image,(Quantum) colormap_index[ScaleQuantumToMap(
-        GetPixelIndex(image,q))],q);
+      SetPixelIndex(image,(Quantum) colormap_index[(size_t) ((double)
+        GetPixelIndex(image,q)+0.5)],q);
       q+=(ptrdiff_t) GetPixelChannels(image);
     }
     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
@@ -4110,12 +4166,12 @@ static MagickBooleanType SetGrayscaleImage(Image *image,
 %
 %  SetImageColormap() traverses the color cube tree and sets the colormap of
 %  the image.  A colormap entry is any node in the color cube tree where the
-%  of unique colors is not zero.
+%  number of unique colors is not zero.
 %
 %  The format of the SetImageColormap method is:
 %
 %      MagickBooleanType SetImageColormap(Image *image,QCubeInfo *cube_info,
-%        ExceptionInfo *node_info)
+%        ExceptionInfo *exception)
 %
 %  A description of each parameter follows.
 %