1/*
2%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3%                                                                             %
4%                                                                             %
5%                                                                             %
6%            CCCC   OOO   L       OOO   RRRR   M   M   AAA   PPPP             %
7%           C      O   O  L      O   O  R   R  MM MM  A   A  P   P            %
8%           C      O   O  L      O   O  RRRR   M M M  AAAAA  PPPP             %
9%           C      O   O  L      O   O  R R    M   M  A   A  P                %
10%            CCCC   OOO   LLLLL   OOO   R  R   M   M  A   A  P                %
11%                                                                             %
12%                                                                             %
13%                        MagickCore Colormap Methods                          %
14%                                                                             %
15%                              Software Design                                %
16%                                   Cristy                                    %
17%                                 July 1992                                   %
18%                                                                             %
19%                                                                             %
20%  Copyright 1999-2016 ImageMagick Studio LLC, a non-profit organization      %
21%  dedicated to making software imaging solutions freely available.           %
22%                                                                             %
23%  You may not use this file except in compliance with the License.  You may  %
24%  obtain a copy of the License at                                            %
25%                                                                             %
26%    http://www.imagemagick.org/script/license.php                            %
27%                                                                             %
28%  Unless required by applicable law or agreed to in writing, software        %
29%  distributed under the License is distributed on an "AS IS" BASIS,          %
30%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
31%  See the License for the specific language governing permissions and        %
32%  limitations under the License.                                             %
33%                                                                             %
34%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35%
36%  We use linked-lists because splay-trees do not currently support duplicate
37%  key / value pairs (.e.g X11 green compliance and SVG green compliance).
38%
39*/
40
41/*
42  Include declarations.
43*/
44#include "MagickCore/studio.h"
45#include "MagickCore/attribute.h"
46#include "MagickCore/blob.h"
47#include "MagickCore/cache-view.h"
48#include "MagickCore/cache.h"
49#include "MagickCore/color.h"
50#include "MagickCore/color-private.h"
51#include "MagickCore/colormap.h"
52#include "MagickCore/client.h"
53#include "MagickCore/configure.h"
54#include "MagickCore/exception.h"
55#include "MagickCore/exception-private.h"
56#include "MagickCore/gem.h"
57#include "MagickCore/geometry.h"
58#include "MagickCore/image-private.h"
59#include "MagickCore/memory_.h"
60#include "MagickCore/monitor.h"
61#include "MagickCore/monitor-private.h"
62#include "MagickCore/option.h"
63#include "MagickCore/pixel-accessor.h"
64#include "MagickCore/quantize.h"
65#include "MagickCore/quantum.h"
66#include "MagickCore/resource_.h"
67#include "MagickCore/semaphore.h"
68#include "MagickCore/string_.h"
69#include "MagickCore/thread-private.h"
70#include "MagickCore/token.h"
71#include "MagickCore/utility.h"
72#include "MagickCore/xml-tree.h"
73
74/*
75%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
76%                                                                             %
77%                                                                             %
78%                                                                             %
79%   A c q u i r e I m a g e C o l o r m a p                                   %
80%                                                                             %
81%                                                                             %
82%                                                                             %
83%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84%
85%  AcquireImageColormap() allocates an image colormap and initializes
86%  it to a linear gray colorspace.  If the image already has a colormap,
87%  it is replaced.  AcquireImageColormap() returns MagickTrue if successful,
88%  otherwise MagickFalse if there is not enough memory.
89%
90%  The format of the AcquireImageColormap method is:
91%
92%      MagickBooleanType AcquireImageColormap(Image *image,const size_t colors,
93%        ExceptionInfo *exception)
94%
95%  A description of each parameter follows:
96%
97%    o image: the image.
98%
99%    o colors: the number of colors in the image colormap.
100%
101%    o exception: return any errors or warnings in this structure.
102%
103*/
104MagickExport MagickBooleanType AcquireImageColormap(Image *image,
105  const size_t colors,ExceptionInfo *exception)
106{
107  register ssize_t
108    i;
109
110  /*
111    Allocate image colormap.
112  */
113  assert(image != (Image *) NULL);
114  assert(image->signature == MagickCoreSignature);
115  if (image->debug != MagickFalse)
116    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
117  image->colors=MagickMax(colors,1);
118  if (image->colormap == (PixelInfo *) NULL)
119    image->colormap=(PixelInfo *) AcquireQuantumMemory(image->colors,
120      sizeof(*image->colormap));
121  else
122    image->colormap=(PixelInfo *) ResizeQuantumMemory(image->colormap,
123      image->colors,sizeof(*image->colormap));
124  if (image->colormap == (PixelInfo *) NULL)
125    {
126      image->colors=0;
127      image->storage_class=DirectClass;
128      ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
129        image->filename);
130    }
131  for (i=0; i < (ssize_t) image->colors; i++)
132  {
133    double
134      pixel;
135
136    pixel=(double) (i*(QuantumRange/MagickMax(colors-1,1)));
137    GetPixelInfo(image,image->colormap+i);
138    image->colormap[i].alpha_trait=BlendPixelTrait;
139    image->colormap[i].red=pixel;
140    image->colormap[i].green=pixel;
141    image->colormap[i].blue=pixel;
142    image->colormap[i].alpha=OpaqueAlpha;
143  }
144  return(SetImageStorageClass(image,PseudoClass,exception));
145}
146
147/*
148%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
149%                                                                             %
150%                                                                             %
151%                                                                             %
152%     C y c l e C o l o r m a p I m a g e                                     %
153%                                                                             %
154%                                                                             %
155%                                                                             %
156%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
157%
158%  CycleColormap() displaces an image's colormap by a given number of
159%  positions.  If you cycle the colormap a number of times you can produce
160%  a psychodelic effect.
161%
162%  WARNING: this assumes an images colormap is in a well know and defined
163%  order. Currently Imagemagick has no way of setting that order.
164%
165%  The format of the CycleColormapImage method is:
166%
167%      MagickBooleanType CycleColormapImage(Image *image,const ssize_t displace,
168%        ExceptionInfo *exception)
169%
170%  A description of each parameter follows:
171%
172%    o image: the image.
173%
174%    o displace:  displace the colormap this amount.
175%
176%    o exception: return any errors or warnings in this structure.
177%
178*/
179MagickExport MagickBooleanType CycleColormapImage(Image *image,
180  const ssize_t displace,ExceptionInfo *exception)
181{
182  CacheView
183    *image_view;
184
185  MagickBooleanType
186    status;
187
188  ssize_t
189    y;
190
191  assert(image != (Image *) NULL);
192  assert(image->signature == MagickCoreSignature);
193  if (image->debug != MagickFalse)
194    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
195  if (image->storage_class == DirectClass)
196    (void) SetImageType(image,PaletteType,exception);
197  status=MagickTrue;
198  image_view=AcquireAuthenticCacheView(image,exception);
199#if defined(MAGICKCORE_OPENMP_SUPPORT)
200  #pragma omp parallel for schedule(static,4) \
201    magick_threads(image,image,1,1)
202#endif
203  for (y=0; y < (ssize_t) image->rows; y++)
204  {
205    register ssize_t
206      x;
207
208    register Quantum
209      *magick_restrict q;
210
211    ssize_t
212      index;
213
214    if (status == MagickFalse)
215      continue;
216    q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
217    if (q == (Quantum *) NULL)
218      {
219        status=MagickFalse;
220        continue;
221      }
222    for (x=0; x < (ssize_t) image->columns; x++)
223    {
224      index=(ssize_t) (GetPixelIndex(image,q)+displace) % image->colors;
225      if (index < 0)
226        index+=(ssize_t) image->colors;
227      SetPixelIndex(image,(Quantum) index,q);
228      SetPixelViaPixelInfo(image,image->colormap+(ssize_t) index,q);
229      q+=GetPixelChannels(image);
230    }
231    if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
232      status=MagickFalse;
233  }
234  image_view=DestroyCacheView(image_view);
235  return(status);
236}
237
238/*
239%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
240%                                                                             %
241%                                                                             %
242%                                                                             %
243+   S o r t C o l o r m a p B y I n t e n s i t y                             %
244%                                                                             %
245%                                                                             %
246%                                                                             %
247%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
248%
249%  SortColormapByIntensity() sorts the colormap of a PseudoClass image by
250%  decreasing color intensity.
251%
252%  The format of the SortColormapByIntensity method is:
253%
254%      MagickBooleanType SortColormapByIntensity(Image *image,
255%        ExceptionInfo *exception)
256%
257%  A description of each parameter follows:
258%
259%    o image: A pointer to an Image structure.
260%
261%    o exception: return any errors or warnings in this structure.
262%
263*/
264
265#if defined(__cplusplus) || defined(c_plusplus)
266extern "C" {
267#endif
268
269static int IntensityCompare(const void *x,const void *y)
270{
271  const PixelInfo
272    *color_1,
273    *color_2;
274
275  int
276    intensity;
277
278  color_1=(const PixelInfo *) x;
279  color_2=(const PixelInfo *) y;
280  intensity=(int) GetPixelInfoIntensity((const Image *) NULL,color_2)-(int)
281    GetPixelInfoIntensity((const Image *) NULL,color_1);
282  return(intensity);
283}
284
285#if defined(__cplusplus) || defined(c_plusplus)
286}
287#endif
288
289MagickExport MagickBooleanType SortColormapByIntensity(Image *image,
290  ExceptionInfo *exception)
291{
292  CacheView
293    *image_view;
294
295  MagickBooleanType
296    status;
297
298  register ssize_t
299    i;
300
301  ssize_t
302    y;
303
304  unsigned short
305    *pixels;
306
307  assert(image != (Image *) NULL);
308  if (image->debug != MagickFalse)
309    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
310  assert(image->signature == MagickCoreSignature);
311  if (image->storage_class != PseudoClass)
312    return(MagickTrue);
313  /*
314    Allocate memory for pixel indexes.
315  */
316  pixels=(unsigned short *) AcquireQuantumMemory((size_t) image->colors,
317    sizeof(*pixels));
318  if (pixels == (unsigned short *) NULL)
319    ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
320      image->filename);
321  /*
322    Assign index values to colormap entries.
323  */
324#if defined(MAGICKCORE_OPENMP_SUPPORT)
325  #pragma omp parallel for schedule(static,4) shared(status) \
326    magick_threads(image,image,1,1)
327#endif
328  for (i=0; i < (ssize_t) image->colors; i++)
329    image->colormap[i].alpha=(double) i;
330  /*
331    Sort image colormap by decreasing color popularity.
332  */
333  qsort((void *) image->colormap,(size_t) image->colors,
334    sizeof(*image->colormap),IntensityCompare);
335  /*
336    Update image colormap indexes to sorted colormap order.
337  */
338#if defined(MAGICKCORE_OPENMP_SUPPORT)
339  #pragma omp parallel for schedule(static,4) shared(status)
340#endif
341  for (i=0; i < (ssize_t) image->colors; i++)
342    pixels[(ssize_t) image->colormap[i].alpha]=(unsigned short) i;
343  status=MagickTrue;
344  image_view=AcquireAuthenticCacheView(image,exception);
345  for (y=0; y < (ssize_t) image->rows; y++)
346  {
347    Quantum
348      index;
349
350    register ssize_t
351      x;
352
353    register Quantum
354      *magick_restrict q;
355
356    q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
357    if (q == (Quantum *) NULL)
358      {
359        status=MagickFalse;
360        break;
361      }
362    for (x=0; x < (ssize_t) image->columns; x++)
363    {
364      index=(Quantum) pixels[(ssize_t) GetPixelIndex(image,q)];
365      SetPixelIndex(image,index,q);
366      SetPixelViaPixelInfo(image,image->colormap+(ssize_t) index,q);
367      q+=GetPixelChannels(image);
368    }
369    if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
370      status=MagickFalse;
371    if (status == MagickFalse)
372      break;
373  }
374  image_view=DestroyCacheView(image_view);
375  pixels=(unsigned short *) RelinquishMagickMemory(pixels);
376  return(status);
377}
378