granicus.if.org Git - imagemagick/blob - coders/dds.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                                                                             %
   6 %                            DDDD   DDDD   SSSSS                              %
   7 %                            D   D  D   D  SS                                 %
   8 %                            D   D  D   D   SSS                               %
   9 %                            D   D  D   D     SS                              %
  10 %                            DDDD   DDDD   SSSSS                              %
  11 %                                                                             %
  12 %                                                                             %
  13 %           Read/Write Microsoft Direct Draw Surface Image Format             %
  14 %                                                                             %
  15 %                              Software Design                                %
  16 %                             Bianca van Schaik                               %
  17 %                                March 2008                                   %
  18 %                               Dirk Lemstra                                  %
  19 %                              September 2013                                 %
  20 %                                                                             %
  21 %                                                                             %
  22 %  Copyright 1999-2018 ImageMagick Studio LLC, a non-profit organization      %
  23 %  dedicated to making software imaging solutions freely available.           %
  24 %                                                                             %
  25 %  You may not use this file except in compliance with the License.  You may  %
  26 %  obtain a copy of the License at                                            %
  27 %                                                                             %
  28 %    https://imagemagick.org/script/license.php                               %
  29 %                                                                             %
  30 %  Unless required by applicable law or agreed to in writing, software        %
  31 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  32 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  33 %  See the License for the specific language governing permissions and        %
  34 %  limitations under the License.                                             %
  35 %                                                                             %
  36 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  37 %
  38 %
  39 */
  40 \f
  41 /*
  42   Include declarations.
  43 */
  44 #include "MagickCore/studio.h"
  45 #include "MagickCore/attribute.h"
  46 #include "MagickCore/blob.h"
  47 #include "MagickCore/blob-private.h"
  48 #include "MagickCore/cache.h"
  49 #include "MagickCore/colorspace.h"
  50 #include "MagickCore/colorspace-private.h"
  51 #include "MagickCore/exception.h"
  52 #include "MagickCore/exception-private.h"
  53 #include "MagickCore/image.h"
  54 #include "MagickCore/image-private.h"
  55 #include "MagickCore/list.h"
  56 #include "MagickCore/log.h"
  57 #include "MagickCore/magick.h"
  58 #include "MagickCore/memory_.h"
  59 #include "MagickCore/monitor.h"
  60 #include "MagickCore/monitor-private.h"
  61 #include "MagickCore/option.h"
  62 #include "MagickCore/pixel-accessor.h"
  63 #include "MagickCore/profile.h"
  64 #include "MagickCore/quantum.h"
  65 #include "MagickCore/quantum-private.h"
  66 #include "MagickCore/resource_.h"
  67 #include "MagickCore/static.h"
  68 #include "MagickCore/string_.h"
  69 #include "MagickCore/string-private.h"
  70 #include "MagickCore/module.h"
  71 #include "MagickCore/transform.h"
  72 \f
  73 /*
  74   Definitions
  75 */
  76 #define DDSD_CAPS         0x00000001
  77 #define DDSD_HEIGHT       0x00000002
  78 #define DDSD_WIDTH        0x00000004
  79 #define DDSD_PITCH        0x00000008
  80 #define DDSD_PIXELFORMAT  0x00001000
  81 #define DDSD_MIPMAPCOUNT  0x00020000
  82 #define DDSD_LINEARSIZE   0x00080000
  83 #define DDSD_DEPTH        0x00800000
  84
  85 #define DDPF_ALPHAPIXELS  0x00000001
  86 #define DDPF_FOURCC       0x00000004
  87 #define DDPF_RGB          0x00000040
  88 #define DDPF_LUMINANCE    0x00020000
  89
  90 #define FOURCC_DXT1       0x31545844
  91 #define FOURCC_DXT3       0x33545844
  92 #define FOURCC_DXT5       0x35545844
  93
  94 #define DDSCAPS_COMPLEX   0x00000008
  95 #define DDSCAPS_TEXTURE   0x00001000
  96 #define DDSCAPS_MIPMAP    0x00400000
  97
  98 #define DDSCAPS2_CUBEMAP  0x00000200
  99 #define DDSCAPS2_CUBEMAP_POSITIVEX  0x00000400
 100 #define DDSCAPS2_CUBEMAP_NEGATIVEX  0x00000800
 101 #define DDSCAPS2_CUBEMAP_POSITIVEY  0x00001000
 102 #define DDSCAPS2_CUBEMAP_NEGATIVEY  0x00002000
 103 #define DDSCAPS2_CUBEMAP_POSITIVEZ  0x00004000
 104 #define DDSCAPS2_CUBEMAP_NEGATIVEZ  0x00008000
 105 #define DDSCAPS2_VOLUME   0x00200000
 106
 107 #ifndef SIZE_MAX
 108 #define SIZE_MAX ((size_t) -1)
 109 #endif
 110
 111 /*
 112   Structure declarations.
 113 */
 114 typedef struct _DDSPixelFormat
 115 {
 116   size_t
 117     flags,
 118     fourcc,
 119     rgb_bitcount,
 120     r_bitmask,
 121     g_bitmask,
 122     b_bitmask,
 123     alpha_bitmask;
 124 } DDSPixelFormat;
 125
 126 typedef struct _DDSInfo
 127 {
 128   size_t
 129     flags,
 130     height,
 131     width,
 132     pitchOrLinearSize,
 133     depth,
 134     mipmapcount,
 135     ddscaps1,
 136     ddscaps2;
 137
 138   DDSPixelFormat
 139     pixelformat;
 140 } DDSInfo;
 141
 142 typedef struct _DDSColors
 143 {
 144   unsigned char
 145     r[4],
 146     g[4],
 147     b[4],
 148     a[4];
 149 } DDSColors;
 150
 151 typedef struct _DDSVector4
 152 {
 153   float
 154     x,
 155     y,
 156     z,
 157     w;
 158 } DDSVector4;
 159
 160 typedef struct _DDSVector3
 161 {
 162   float
 163     x,
 164     y,
 165     z;
 166 } DDSVector3;
 167
 168 typedef struct _DDSSourceBlock
 169 {
 170   unsigned char
 171     start,
 172     end,
 173     error;
 174 } DDSSourceBlock;
 175
 176 typedef struct _DDSSingleColourLookup
 177 {
 178   DDSSourceBlock sources[2];
 179 } DDSSingleColourLookup;
 180
 181 typedef MagickBooleanType
 182   DDSDecoder(const ImageInfo *,Image *,DDSInfo *,const MagickBooleanType,
 183     ExceptionInfo *);
 184
 185 typedef MagickBooleanType
 186   DDSPixelDecoder(Image *,DDSInfo *,ExceptionInfo *);
 187
 188 static const DDSSingleColourLookup DDSLookup_5_4[] =
 189 {
 190   { { { 0, 0, 0 }, { 0, 0, 0 } } },
 191   { { { 0, 0, 1 }, { 0, 1, 1 } } },
 192   { { { 0, 0, 2 }, { 0, 1, 0 } } },
 193   { { { 0, 0, 3 }, { 0, 1, 1 } } },
 194   { { { 0, 0, 4 }, { 0, 2, 1 } } },
 195   { { { 1, 0, 3 }, { 0, 2, 0 } } },
 196   { { { 1, 0, 2 }, { 0, 2, 1 } } },
 197   { { { 1, 0, 1 }, { 0, 3, 1 } } },
 198   { { { 1, 0, 0 }, { 0, 3, 0 } } },
 199   { { { 1, 0, 1 }, { 1, 2, 1 } } },
 200   { { { 1, 0, 2 }, { 1, 2, 0 } } },
 201   { { { 1, 0, 3 }, { 0, 4, 0 } } },
 202   { { { 1, 0, 4 }, { 0, 5, 1 } } },
 203   { { { 2, 0, 3 }, { 0, 5, 0 } } },
 204   { { { 2, 0, 2 }, { 0, 5, 1 } } },
 205   { { { 2, 0, 1 }, { 0, 6, 1 } } },
 206   { { { 2, 0, 0 }, { 0, 6, 0 } } },
 207   { { { 2, 0, 1 }, { 2, 3, 1 } } },
 208   { { { 2, 0, 2 }, { 2, 3, 0 } } },
 209   { { { 2, 0, 3 }, { 0, 7, 0 } } },
 210   { { { 2, 0, 4 }, { 1, 6, 1 } } },
 211   { { { 3, 0, 3 }, { 1, 6, 0 } } },
 212   { { { 3, 0, 2 }, { 0, 8, 0 } } },
 213   { { { 3, 0, 1 }, { 0, 9, 1 } } },
 214   { { { 3, 0, 0 }, { 0, 9, 0 } } },
 215   { { { 3, 0, 1 }, { 0, 9, 1 } } },
 216   { { { 3, 0, 2 }, { 0, 10, 1 } } },
 217   { { { 3, 0, 3 }, { 0, 10, 0 } } },
 218   { { { 3, 0, 4 }, { 2, 7, 1 } } },
 219   { { { 4, 0, 4 }, { 2, 7, 0 } } },
 220   { { { 4, 0, 3 }, { 0, 11, 0 } } },
 221   { { { 4, 0, 2 }, { 1, 10, 1 } } },
 222   { { { 4, 0, 1 }, { 1, 10, 0 } } },
 223   { { { 4, 0, 0 }, { 0, 12, 0 } } },
 224   { { { 4, 0, 1 }, { 0, 13, 1 } } },
 225   { { { 4, 0, 2 }, { 0, 13, 0 } } },
 226   { { { 4, 0, 3 }, { 0, 13, 1 } } },
 227   { { { 4, 0, 4 }, { 0, 14, 1 } } },
 228   { { { 5, 0, 3 }, { 0, 14, 0 } } },
 229   { { { 5, 0, 2 }, { 2, 11, 1 } } },
 230   { { { 5, 0, 1 }, { 2, 11, 0 } } },
 231   { { { 5, 0, 0 }, { 0, 15, 0 } } },
 232   { { { 5, 0, 1 }, { 1, 14, 1 } } },
 233   { { { 5, 0, 2 }, { 1, 14, 0 } } },
 234   { { { 5, 0, 3 }, { 0, 16, 0 } } },
 235   { { { 5, 0, 4 }, { 0, 17, 1 } } },
 236   { { { 6, 0, 3 }, { 0, 17, 0 } } },
 237   { { { 6, 0, 2 }, { 0, 17, 1 } } },
 238   { { { 6, 0, 1 }, { 0, 18, 1 } } },
 239   { { { 6, 0, 0 }, { 0, 18, 0 } } },
 240   { { { 6, 0, 1 }, { 2, 15, 1 } } },
 241   { { { 6, 0, 2 }, { 2, 15, 0 } } },
 242   { { { 6, 0, 3 }, { 0, 19, 0 } } },
 243   { { { 6, 0, 4 }, { 1, 18, 1 } } },
 244   { { { 7, 0, 3 }, { 1, 18, 0 } } },
 245   { { { 7, 0, 2 }, { 0, 20, 0 } } },
 246   { { { 7, 0, 1 }, { 0, 21, 1 } } },
 247   { { { 7, 0, 0 }, { 0, 21, 0 } } },
 248   { { { 7, 0, 1 }, { 0, 21, 1 } } },
 249   { { { 7, 0, 2 }, { 0, 22, 1 } } },
 250   { { { 7, 0, 3 }, { 0, 22, 0 } } },
 251   { { { 7, 0, 4 }, { 2, 19, 1 } } },
 252   { { { 8, 0, 4 }, { 2, 19, 0 } } },
 253   { { { 8, 0, 3 }, { 0, 23, 0 } } },
 254   { { { 8, 0, 2 }, { 1, 22, 1 } } },
 255   { { { 8, 0, 1 }, { 1, 22, 0 } } },
 256   { { { 8, 0, 0 }, { 0, 24, 0 } } },
 257   { { { 8, 0, 1 }, { 0, 25, 1 } } },
 258   { { { 8, 0, 2 }, { 0, 25, 0 } } },
 259   { { { 8, 0, 3 }, { 0, 25, 1 } } },
 260   { { { 8, 0, 4 }, { 0, 26, 1 } } },
 261   { { { 9, 0, 3 }, { 0, 26, 0 } } },
 262   { { { 9, 0, 2 }, { 2, 23, 1 } } },
 263   { { { 9, 0, 1 }, { 2, 23, 0 } } },
 264   { { { 9, 0, 0 }, { 0, 27, 0 } } },
 265   { { { 9, 0, 1 }, { 1, 26, 1 } } },
 266   { { { 9, 0, 2 }, { 1, 26, 0 } } },
 267   { { { 9, 0, 3 }, { 0, 28, 0 } } },
 268   { { { 9, 0, 4 }, { 0, 29, 1 } } },
 269   { { { 10, 0, 3 }, { 0, 29, 0 } } },
 270   { { { 10, 0, 2 }, { 0, 29, 1 } } },
 271   { { { 10, 0, 1 }, { 0, 30, 1 } } },
 272   { { { 10, 0, 0 }, { 0, 30, 0 } } },
 273   { { { 10, 0, 1 }, { 2, 27, 1 } } },
 274   { { { 10, 0, 2 }, { 2, 27, 0 } } },
 275   { { { 10, 0, 3 }, { 0, 31, 0 } } },
 276   { { { 10, 0, 4 }, { 1, 30, 1 } } },
 277   { { { 11, 0, 3 }, { 1, 30, 0 } } },
 278   { { { 11, 0, 2 }, { 4, 24, 0 } } },
 279   { { { 11, 0, 1 }, { 1, 31, 1 } } },
 280   { { { 11, 0, 0 }, { 1, 31, 0 } } },
 281   { { { 11, 0, 1 }, { 1, 31, 1 } } },
 282   { { { 11, 0, 2 }, { 2, 30, 1 } } },
 283   { { { 11, 0, 3 }, { 2, 30, 0 } } },
 284   { { { 11, 0, 4 }, { 2, 31, 1 } } },
 285   { { { 12, 0, 4 }, { 2, 31, 0 } } },
 286   { { { 12, 0, 3 }, { 4, 27, 0 } } },
 287   { { { 12, 0, 2 }, { 3, 30, 1 } } },
 288   { { { 12, 0, 1 }, { 3, 30, 0 } } },
 289   { { { 12, 0, 0 }, { 4, 28, 0 } } },
 290   { { { 12, 0, 1 }, { 3, 31, 1 } } },
 291   { { { 12, 0, 2 }, { 3, 31, 0 } } },
 292   { { { 12, 0, 3 }, { 3, 31, 1 } } },
 293   { { { 12, 0, 4 }, { 4, 30, 1 } } },
 294   { { { 13, 0, 3 }, { 4, 30, 0 } } },
 295   { { { 13, 0, 2 }, { 6, 27, 1 } } },
 296   { { { 13, 0, 1 }, { 6, 27, 0 } } },
 297   { { { 13, 0, 0 }, { 4, 31, 0 } } },
 298   { { { 13, 0, 1 }, { 5, 30, 1 } } },
 299   { { { 13, 0, 2 }, { 5, 30, 0 } } },
 300   { { { 13, 0, 3 }, { 8, 24, 0 } } },
 301   { { { 13, 0, 4 }, { 5, 31, 1 } } },
 302   { { { 14, 0, 3 }, { 5, 31, 0 } } },
 303   { { { 14, 0, 2 }, { 5, 31, 1 } } },
 304   { { { 14, 0, 1 }, { 6, 30, 1 } } },
 305   { { { 14, 0, 0 }, { 6, 30, 0 } } },
 306   { { { 14, 0, 1 }, { 6, 31, 1 } } },
 307   { { { 14, 0, 2 }, { 6, 31, 0 } } },
 308   { { { 14, 0, 3 }, { 8, 27, 0 } } },
 309   { { { 14, 0, 4 }, { 7, 30, 1 } } },
 310   { { { 15, 0, 3 }, { 7, 30, 0 } } },
 311   { { { 15, 0, 2 }, { 8, 28, 0 } } },
 312   { { { 15, 0, 1 }, { 7, 31, 1 } } },
 313   { { { 15, 0, 0 }, { 7, 31, 0 } } },
 314   { { { 15, 0, 1 }, { 7, 31, 1 } } },
 315   { { { 15, 0, 2 }, { 8, 30, 1 } } },
 316   { { { 15, 0, 3 }, { 8, 30, 0 } } },
 317   { { { 15, 0, 4 }, { 10, 27, 1 } } },
 318   { { { 16, 0, 4 }, { 10, 27, 0 } } },
 319   { { { 16, 0, 3 }, { 8, 31, 0 } } },
 320   { { { 16, 0, 2 }, { 9, 30, 1 } } },
 321   { { { 16, 0, 1 }, { 9, 30, 0 } } },
 322   { { { 16, 0, 0 }, { 12, 24, 0 } } },
 323   { { { 16, 0, 1 }, { 9, 31, 1 } } },
 324   { { { 16, 0, 2 }, { 9, 31, 0 } } },
 325   { { { 16, 0, 3 }, { 9, 31, 1 } } },
 326   { { { 16, 0, 4 }, { 10, 30, 1 } } },
 327   { { { 17, 0, 3 }, { 10, 30, 0 } } },
 328   { { { 17, 0, 2 }, { 10, 31, 1 } } },
 329   { { { 17, 0, 1 }, { 10, 31, 0 } } },
 330   { { { 17, 0, 0 }, { 12, 27, 0 } } },
 331   { { { 17, 0, 1 }, { 11, 30, 1 } } },
 332   { { { 17, 0, 2 }, { 11, 30, 0 } } },
 333   { { { 17, 0, 3 }, { 12, 28, 0 } } },
 334   { { { 17, 0, 4 }, { 11, 31, 1 } } },
 335   { { { 18, 0, 3 }, { 11, 31, 0 } } },
 336   { { { 18, 0, 2 }, { 11, 31, 1 } } },
 337   { { { 18, 0, 1 }, { 12, 30, 1 } } },
 338   { { { 18, 0, 0 }, { 12, 30, 0 } } },
 339   { { { 18, 0, 1 }, { 14, 27, 1 } } },
 340   { { { 18, 0, 2 }, { 14, 27, 0 } } },
 341   { { { 18, 0, 3 }, { 12, 31, 0 } } },
 342   { { { 18, 0, 4 }, { 13, 30, 1 } } },
 343   { { { 19, 0, 3 }, { 13, 30, 0 } } },
 344   { { { 19, 0, 2 }, { 16, 24, 0 } } },
 345   { { { 19, 0, 1 }, { 13, 31, 1 } } },
 346   { { { 19, 0, 0 }, { 13, 31, 0 } } },
 347   { { { 19, 0, 1 }, { 13, 31, 1 } } },
 348   { { { 19, 0, 2 }, { 14, 30, 1 } } },
 349   { { { 19, 0, 3 }, { 14, 30, 0 } } },
 350   { { { 19, 0, 4 }, { 14, 31, 1 } } },
 351   { { { 20, 0, 4 }, { 14, 31, 0 } } },
 352   { { { 20, 0, 3 }, { 16, 27, 0 } } },
 353   { { { 20, 0, 2 }, { 15, 30, 1 } } },
 354   { { { 20, 0, 1 }, { 15, 30, 0 } } },
 355   { { { 20, 0, 0 }, { 16, 28, 0 } } },
 356   { { { 20, 0, 1 }, { 15, 31, 1 } } },
 357   { { { 20, 0, 2 }, { 15, 31, 0 } } },
 358   { { { 20, 0, 3 }, { 15, 31, 1 } } },
 359   { { { 20, 0, 4 }, { 16, 30, 1 } } },
 360   { { { 21, 0, 3 }, { 16, 30, 0 } } },
 361   { { { 21, 0, 2 }, { 18, 27, 1 } } },
 362   { { { 21, 0, 1 }, { 18, 27, 0 } } },
 363   { { { 21, 0, 0 }, { 16, 31, 0 } } },
 364   { { { 21, 0, 1 }, { 17, 30, 1 } } },
 365   { { { 21, 0, 2 }, { 17, 30, 0 } } },
 366   { { { 21, 0, 3 }, { 20, 24, 0 } } },
 367   { { { 21, 0, 4 }, { 17, 31, 1 } } },
 368   { { { 22, 0, 3 }, { 17, 31, 0 } } },
 369   { { { 22, 0, 2 }, { 17, 31, 1 } } },
 370   { { { 22, 0, 1 }, { 18, 30, 1 } } },
 371   { { { 22, 0, 0 }, { 18, 30, 0 } } },
 372   { { { 22, 0, 1 }, { 18, 31, 1 } } },
 373   { { { 22, 0, 2 }, { 18, 31, 0 } } },
 374   { { { 22, 0, 3 }, { 20, 27, 0 } } },
 375   { { { 22, 0, 4 }, { 19, 30, 1 } } },
 376   { { { 23, 0, 3 }, { 19, 30, 0 } } },
 377   { { { 23, 0, 2 }, { 20, 28, 0 } } },
 378   { { { 23, 0, 1 }, { 19, 31, 1 } } },
 379   { { { 23, 0, 0 }, { 19, 31, 0 } } },
 380   { { { 23, 0, 1 }, { 19, 31, 1 } } },
 381   { { { 23, 0, 2 }, { 20, 30, 1 } } },
 382   { { { 23, 0, 3 }, { 20, 30, 0 } } },
 383   { { { 23, 0, 4 }, { 22, 27, 1 } } },
 384   { { { 24, 0, 4 }, { 22, 27, 0 } } },
 385   { { { 24, 0, 3 }, { 20, 31, 0 } } },
 386   { { { 24, 0, 2 }, { 21, 30, 1 } } },
 387   { { { 24, 0, 1 }, { 21, 30, 0 } } },
 388   { { { 24, 0, 0 }, { 24, 24, 0 } } },
 389   { { { 24, 0, 1 }, { 21, 31, 1 } } },
 390   { { { 24, 0, 2 }, { 21, 31, 0 } } },
 391   { { { 24, 0, 3 }, { 21, 31, 1 } } },
 392   { { { 24, 0, 4 }, { 22, 30, 1 } } },
 393   { { { 25, 0, 3 }, { 22, 30, 0 } } },
 394   { { { 25, 0, 2 }, { 22, 31, 1 } } },
 395   { { { 25, 0, 1 }, { 22, 31, 0 } } },
 396   { { { 25, 0, 0 }, { 24, 27, 0 } } },
 397   { { { 25, 0, 1 }, { 23, 30, 1 } } },
 398   { { { 25, 0, 2 }, { 23, 30, 0 } } },
 399   { { { 25, 0, 3 }, { 24, 28, 0 } } },
 400   { { { 25, 0, 4 }, { 23, 31, 1 } } },
 401   { { { 26, 0, 3 }, { 23, 31, 0 } } },
 402   { { { 26, 0, 2 }, { 23, 31, 1 } } },
 403   { { { 26, 0, 1 }, { 24, 30, 1 } } },
 404   { { { 26, 0, 0 }, { 24, 30, 0 } } },
 405   { { { 26, 0, 1 }, { 26, 27, 1 } } },
 406   { { { 26, 0, 2 }, { 26, 27, 0 } } },
 407   { { { 26, 0, 3 }, { 24, 31, 0 } } },
 408   { { { 26, 0, 4 }, { 25, 30, 1 } } },
 409   { { { 27, 0, 3 }, { 25, 30, 0 } } },
 410   { { { 27, 0, 2 }, { 28, 24, 0 } } },
 411   { { { 27, 0, 1 }, { 25, 31, 1 } } },
 412   { { { 27, 0, 0 }, { 25, 31, 0 } } },
 413   { { { 27, 0, 1 }, { 25, 31, 1 } } },
 414   { { { 27, 0, 2 }, { 26, 30, 1 } } },
 415   { { { 27, 0, 3 }, { 26, 30, 0 } } },
 416   { { { 27, 0, 4 }, { 26, 31, 1 } } },
 417   { { { 28, 0, 4 }, { 26, 31, 0 } } },
 418   { { { 28, 0, 3 }, { 28, 27, 0 } } },
 419   { { { 28, 0, 2 }, { 27, 30, 1 } } },
 420   { { { 28, 0, 1 }, { 27, 30, 0 } } },
 421   { { { 28, 0, 0 }, { 28, 28, 0 } } },
 422   { { { 28, 0, 1 }, { 27, 31, 1 } } },
 423   { { { 28, 0, 2 }, { 27, 31, 0 } } },
 424   { { { 28, 0, 3 }, { 27, 31, 1 } } },
 425   { { { 28, 0, 4 }, { 28, 30, 1 } } },
 426   { { { 29, 0, 3 }, { 28, 30, 0 } } },
 427   { { { 29, 0, 2 }, { 30, 27, 1 } } },
 428   { { { 29, 0, 1 }, { 30, 27, 0 } } },
 429   { { { 29, 0, 0 }, { 28, 31, 0 } } },
 430   { { { 29, 0, 1 }, { 29, 30, 1 } } },
 431   { { { 29, 0, 2 }, { 29, 30, 0 } } },
 432   { { { 29, 0, 3 }, { 29, 30, 1 } } },
 433   { { { 29, 0, 4 }, { 29, 31, 1 } } },
 434   { { { 30, 0, 3 }, { 29, 31, 0 } } },
 435   { { { 30, 0, 2 }, { 29, 31, 1 } } },
 436   { { { 30, 0, 1 }, { 30, 30, 1 } } },
 437   { { { 30, 0, 0 }, { 30, 30, 0 } } },
 438   { { { 30, 0, 1 }, { 30, 31, 1 } } },
 439   { { { 30, 0, 2 }, { 30, 31, 0 } } },
 440   { { { 30, 0, 3 }, { 30, 31, 1 } } },
 441   { { { 30, 0, 4 }, { 31, 30, 1 } } },
 442   { { { 31, 0, 3 }, { 31, 30, 0 } } },
 443   { { { 31, 0, 2 }, { 31, 30, 1 } } },
 444   { { { 31, 0, 1 }, { 31, 31, 1 } } },
 445   { { { 31, 0, 0 }, { 31, 31, 0 } } }
 446 };
 447
 448 static const DDSSingleColourLookup DDSLookup_6_4[] =
 449 {
 450   { { { 0, 0, 0 }, { 0, 0, 0 } } },
 451   { { { 0, 0, 1 }, { 0, 1, 0 } } },
 452   { { { 0, 0, 2 }, { 0, 2, 0 } } },
 453   { { { 1, 0, 1 }, { 0, 3, 1 } } },
 454   { { { 1, 0, 0 }, { 0, 3, 0 } } },
 455   { { { 1, 0, 1 }, { 0, 4, 0 } } },
 456   { { { 1, 0, 2 }, { 0, 5, 0 } } },
 457   { { { 2, 0, 1 }, { 0, 6, 1 } } },
 458   { { { 2, 0, 0 }, { 0, 6, 0 } } },
 459   { { { 2, 0, 1 }, { 0, 7, 0 } } },
 460   { { { 2, 0, 2 }, { 0, 8, 0 } } },
 461   { { { 3, 0, 1 }, { 0, 9, 1 } } },
 462   { { { 3, 0, 0 }, { 0, 9, 0 } } },
 463   { { { 3, 0, 1 }, { 0, 10, 0 } } },
 464   { { { 3, 0, 2 }, { 0, 11, 0 } } },
 465   { { { 4, 0, 1 }, { 0, 12, 1 } } },
 466   { { { 4, 0, 0 }, { 0, 12, 0 } } },
 467   { { { 4, 0, 1 }, { 0, 13, 0 } } },
 468   { { { 4, 0, 2 }, { 0, 14, 0 } } },
 469   { { { 5, 0, 1 }, { 0, 15, 1 } } },
 470   { { { 5, 0, 0 }, { 0, 15, 0 } } },
 471   { { { 5, 0, 1 }, { 0, 16, 0 } } },
 472   { { { 5, 0, 2 }, { 1, 15, 0 } } },
 473   { { { 6, 0, 1 }, { 0, 17, 0 } } },
 474   { { { 6, 0, 0 }, { 0, 18, 0 } } },
 475   { { { 6, 0, 1 }, { 0, 19, 0 } } },
 476   { { { 6, 0, 2 }, { 3, 14, 0 } } },
 477   { { { 7, 0, 1 }, { 0, 20, 0 } } },
 478   { { { 7, 0, 0 }, { 0, 21, 0 } } },
 479   { { { 7, 0, 1 }, { 0, 22, 0 } } },
 480   { { { 7, 0, 2 }, { 4, 15, 0 } } },
 481   { { { 8, 0, 1 }, { 0, 23, 0 } } },
 482   { { { 8, 0, 0 }, { 0, 24, 0 } } },
 483   { { { 8, 0, 1 }, { 0, 25, 0 } } },
 484   { { { 8, 0, 2 }, { 6, 14, 0 } } },
 485   { { { 9, 0, 1 }, { 0, 26, 0 } } },
 486   { { { 9, 0, 0 }, { 0, 27, 0 } } },
 487   { { { 9, 0, 1 }, { 0, 28, 0 } } },
 488   { { { 9, 0, 2 }, { 7, 15, 0 } } },
 489   { { { 10, 0, 1 }, { 0, 29, 0 } } },
 490   { { { 10, 0, 0 }, { 0, 30, 0 } } },
 491   { { { 10, 0, 1 }, { 0, 31, 0 } } },
 492   { { { 10, 0, 2 }, { 9, 14, 0 } } },
 493   { { { 11, 0, 1 }, { 0, 32, 0 } } },
 494   { { { 11, 0, 0 }, { 0, 33, 0 } } },
 495   { { { 11, 0, 1 }, { 2, 30, 0 } } },
 496   { { { 11, 0, 2 }, { 0, 34, 0 } } },
 497   { { { 12, 0, 1 }, { 0, 35, 0 } } },
 498   { { { 12, 0, 0 }, { 0, 36, 0 } } },
 499   { { { 12, 0, 1 }, { 3, 31, 0 } } },
 500   { { { 12, 0, 2 }, { 0, 37, 0 } } },
 501   { { { 13, 0, 1 }, { 0, 38, 0 } } },
 502   { { { 13, 0, 0 }, { 0, 39, 0 } } },
 503   { { { 13, 0, 1 }, { 5, 30, 0 } } },
 504   { { { 13, 0, 2 }, { 0, 40, 0 } } },
 505   { { { 14, 0, 1 }, { 0, 41, 0 } } },
 506   { { { 14, 0, 0 }, { 0, 42, 0 } } },
 507   { { { 14, 0, 1 }, { 6, 31, 0 } } },
 508   { { { 14, 0, 2 }, { 0, 43, 0 } } },
 509   { { { 15, 0, 1 }, { 0, 44, 0 } } },
 510   { { { 15, 0, 0 }, { 0, 45, 0 } } },
 511   { { { 15, 0, 1 }, { 8, 30, 0 } } },
 512   { { { 15, 0, 2 }, { 0, 46, 0 } } },
 513   { { { 16, 0, 2 }, { 0, 47, 0 } } },
 514   { { { 16, 0, 1 }, { 1, 46, 0 } } },
 515   { { { 16, 0, 0 }, { 0, 48, 0 } } },
 516   { { { 16, 0, 1 }, { 0, 49, 0 } } },
 517   { { { 16, 0, 2 }, { 0, 50, 0 } } },
 518   { { { 17, 0, 1 }, { 2, 47, 0 } } },
 519   { { { 17, 0, 0 }, { 0, 51, 0 } } },
 520   { { { 17, 0, 1 }, { 0, 52, 0 } } },
 521   { { { 17, 0, 2 }, { 0, 53, 0 } } },
 522   { { { 18, 0, 1 }, { 4, 46, 0 } } },
 523   { { { 18, 0, 0 }, { 0, 54, 0 } } },
 524   { { { 18, 0, 1 }, { 0, 55, 0 } } },
 525   { { { 18, 0, 2 }, { 0, 56, 0 } } },
 526   { { { 19, 0, 1 }, { 5, 47, 0 } } },
 527   { { { 19, 0, 0 }, { 0, 57, 0 } } },
 528   { { { 19, 0, 1 }, { 0, 58, 0 } } },
 529   { { { 19, 0, 2 }, { 0, 59, 0 } } },
 530   { { { 20, 0, 1 }, { 7, 46, 0 } } },
 531   { { { 20, 0, 0 }, { 0, 60, 0 } } },
 532   { { { 20, 0, 1 }, { 0, 61, 0 } } },
 533   { { { 20, 0, 2 }, { 0, 62, 0 } } },
 534   { { { 21, 0, 1 }, { 8, 47, 0 } } },
 535   { { { 21, 0, 0 }, { 0, 63, 0 } } },
 536   { { { 21, 0, 1 }, { 1, 62, 0 } } },
 537   { { { 21, 0, 2 }, { 1, 63, 0 } } },
 538   { { { 22, 0, 1 }, { 10, 46, 0 } } },
 539   { { { 22, 0, 0 }, { 2, 62, 0 } } },
 540   { { { 22, 0, 1 }, { 2, 63, 0 } } },
 541   { { { 22, 0, 2 }, { 3, 62, 0 } } },
 542   { { { 23, 0, 1 }, { 11, 47, 0 } } },
 543   { { { 23, 0, 0 }, { 3, 63, 0 } } },
 544   { { { 23, 0, 1 }, { 4, 62, 0 } } },
 545   { { { 23, 0, 2 }, { 4, 63, 0 } } },
 546   { { { 24, 0, 1 }, { 13, 46, 0 } } },
 547   { { { 24, 0, 0 }, { 5, 62, 0 } } },
 548   { { { 24, 0, 1 }, { 5, 63, 0 } } },
 549   { { { 24, 0, 2 }, { 6, 62, 0 } } },
 550   { { { 25, 0, 1 }, { 14, 47, 0 } } },
 551   { { { 25, 0, 0 }, { 6, 63, 0 } } },
 552   { { { 25, 0, 1 }, { 7, 62, 0 } } },
 553   { { { 25, 0, 2 }, { 7, 63, 0 } } },
 554   { { { 26, 0, 1 }, { 16, 45, 0 } } },
 555   { { { 26, 0, 0 }, { 8, 62, 0 } } },
 556   { { { 26, 0, 1 }, { 8, 63, 0 } } },
 557   { { { 26, 0, 2 }, { 9, 62, 0 } } },
 558   { { { 27, 0, 1 }, { 16, 48, 0 } } },
 559   { { { 27, 0, 0 }, { 9, 63, 0 } } },
 560   { { { 27, 0, 1 }, { 10, 62, 0 } } },
 561   { { { 27, 0, 2 }, { 10, 63, 0 } } },
 562   { { { 28, 0, 1 }, { 16, 51, 0 } } },
 563   { { { 28, 0, 0 }, { 11, 62, 0 } } },
 564   { { { 28, 0, 1 }, { 11, 63, 0 } } },
 565   { { { 28, 0, 2 }, { 12, 62, 0 } } },
 566   { { { 29, 0, 1 }, { 16, 54, 0 } } },
 567   { { { 29, 0, 0 }, { 12, 63, 0 } } },
 568   { { { 29, 0, 1 }, { 13, 62, 0 } } },
 569   { { { 29, 0, 2 }, { 13, 63, 0 } } },
 570   { { { 30, 0, 1 }, { 16, 57, 0 } } },
 571   { { { 30, 0, 0 }, { 14, 62, 0 } } },
 572   { { { 30, 0, 1 }, { 14, 63, 0 } } },
 573   { { { 30, 0, 2 }, { 15, 62, 0 } } },
 574   { { { 31, 0, 1 }, { 16, 60, 0 } } },
 575   { { { 31, 0, 0 }, { 15, 63, 0 } } },
 576   { { { 31, 0, 1 }, { 24, 46, 0 } } },
 577   { { { 31, 0, 2 }, { 16, 62, 0 } } },
 578   { { { 32, 0, 2 }, { 16, 63, 0 } } },
 579   { { { 32, 0, 1 }, { 17, 62, 0 } } },
 580   { { { 32, 0, 0 }, { 25, 47, 0 } } },
 581   { { { 32, 0, 1 }, { 17, 63, 0 } } },
 582   { { { 32, 0, 2 }, { 18, 62, 0 } } },
 583   { { { 33, 0, 1 }, { 18, 63, 0 } } },
 584   { { { 33, 0, 0 }, { 27, 46, 0 } } },
 585   { { { 33, 0, 1 }, { 19, 62, 0 } } },
 586   { { { 33, 0, 2 }, { 19, 63, 0 } } },
 587   { { { 34, 0, 1 }, { 20, 62, 0 } } },
 588   { { { 34, 0, 0 }, { 28, 47, 0 } } },
 589   { { { 34, 0, 1 }, { 20, 63, 0 } } },
 590   { { { 34, 0, 2 }, { 21, 62, 0 } } },
 591   { { { 35, 0, 1 }, { 21, 63, 0 } } },
 592   { { { 35, 0, 0 }, { 30, 46, 0 } } },
 593   { { { 35, 0, 1 }, { 22, 62, 0 } } },
 594   { { { 35, 0, 2 }, { 22, 63, 0 } } },
 595   { { { 36, 0, 1 }, { 23, 62, 0 } } },
 596   { { { 36, 0, 0 }, { 31, 47, 0 } } },
 597   { { { 36, 0, 1 }, { 23, 63, 0 } } },
 598   { { { 36, 0, 2 }, { 24, 62, 0 } } },
 599   { { { 37, 0, 1 }, { 24, 63, 0 } } },
 600   { { { 37, 0, 0 }, { 32, 47, 0 } } },
 601   { { { 37, 0, 1 }, { 25, 62, 0 } } },
 602   { { { 37, 0, 2 }, { 25, 63, 0 } } },
 603   { { { 38, 0, 1 }, { 26, 62, 0 } } },
 604   { { { 38, 0, 0 }, { 32, 50, 0 } } },
 605   { { { 38, 0, 1 }, { 26, 63, 0 } } },
 606   { { { 38, 0, 2 }, { 27, 62, 0 } } },
 607   { { { 39, 0, 1 }, { 27, 63, 0 } } },
 608   { { { 39, 0, 0 }, { 32, 53, 0 } } },
 609   { { { 39, 0, 1 }, { 28, 62, 0 } } },
 610   { { { 39, 0, 2 }, { 28, 63, 0 } } },
 611   { { { 40, 0, 1 }, { 29, 62, 0 } } },
 612   { { { 40, 0, 0 }, { 32, 56, 0 } } },
 613   { { { 40, 0, 1 }, { 29, 63, 0 } } },
 614   { { { 40, 0, 2 }, { 30, 62, 0 } } },
 615   { { { 41, 0, 1 }, { 30, 63, 0 } } },
 616   { { { 41, 0, 0 }, { 32, 59, 0 } } },
 617   { { { 41, 0, 1 }, { 31, 62, 0 } } },
 618   { { { 41, 0, 2 }, { 31, 63, 0 } } },
 619   { { { 42, 0, 1 }, { 32, 61, 0 } } },
 620   { { { 42, 0, 0 }, { 32, 62, 0 } } },
 621   { { { 42, 0, 1 }, { 32, 63, 0 } } },
 622   { { { 42, 0, 2 }, { 41, 46, 0 } } },
 623   { { { 43, 0, 1 }, { 33, 62, 0 } } },
 624   { { { 43, 0, 0 }, { 33, 63, 0 } } },
 625   { { { 43, 0, 1 }, { 34, 62, 0 } } },
 626   { { { 43, 0, 2 }, { 42, 47, 0 } } },
 627   { { { 44, 0, 1 }, { 34, 63, 0 } } },
 628   { { { 44, 0, 0 }, { 35, 62, 0 } } },
 629   { { { 44, 0, 1 }, { 35, 63, 0 } } },
 630   { { { 44, 0, 2 }, { 44, 46, 0 } } },
 631   { { { 45, 0, 1 }, { 36, 62, 0 } } },
 632   { { { 45, 0, 0 }, { 36, 63, 0 } } },
 633   { { { 45, 0, 1 }, { 37, 62, 0 } } },
 634   { { { 45, 0, 2 }, { 45, 47, 0 } } },
 635   { { { 46, 0, 1 }, { 37, 63, 0 } } },
 636   { { { 46, 0, 0 }, { 38, 62, 0 } } },
 637   { { { 46, 0, 1 }, { 38, 63, 0 } } },
 638   { { { 46, 0, 2 }, { 47, 46, 0 } } },
 639   { { { 47, 0, 1 }, { 39, 62, 0 } } },
 640   { { { 47, 0, 0 }, { 39, 63, 0 } } },
 641   { { { 47, 0, 1 }, { 40, 62, 0 } } },
 642   { { { 47, 0, 2 }, { 48, 46, 0 } } },
 643   { { { 48, 0, 2 }, { 40, 63, 0 } } },
 644   { { { 48, 0, 1 }, { 41, 62, 0 } } },
 645   { { { 48, 0, 0 }, { 41, 63, 0 } } },
 646   { { { 48, 0, 1 }, { 48, 49, 0 } } },
 647   { { { 48, 0, 2 }, { 42, 62, 0 } } },
 648   { { { 49, 0, 1 }, { 42, 63, 0 } } },
 649   { { { 49, 0, 0 }, { 43, 62, 0 } } },
 650   { { { 49, 0, 1 }, { 48, 52, 0 } } },
 651   { { { 49, 0, 2 }, { 43, 63, 0 } } },
 652   { { { 50, 0, 1 }, { 44, 62, 0 } } },
 653   { { { 50, 0, 0 }, { 44, 63, 0 } } },
 654   { { { 50, 0, 1 }, { 48, 55, 0 } } },
 655   { { { 50, 0, 2 }, { 45, 62, 0 } } },
 656   { { { 51, 0, 1 }, { 45, 63, 0 } } },
 657   { { { 51, 0, 0 }, { 46, 62, 0 } } },
 658   { { { 51, 0, 1 }, { 48, 58, 0 } } },
 659   { { { 51, 0, 2 }, { 46, 63, 0 } } },
 660   { { { 52, 0, 1 }, { 47, 62, 0 } } },
 661   { { { 52, 0, 0 }, { 47, 63, 0 } } },
 662   { { { 52, 0, 1 }, { 48, 61, 0 } } },
 663   { { { 52, 0, 2 }, { 48, 62, 0 } } },
 664   { { { 53, 0, 1 }, { 56, 47, 0 } } },
 665   { { { 53, 0, 0 }, { 48, 63, 0 } } },
 666   { { { 53, 0, 1 }, { 49, 62, 0 } } },
 667   { { { 53, 0, 2 }, { 49, 63, 0 } } },
 668   { { { 54, 0, 1 }, { 58, 46, 0 } } },
 669   { { { 54, 0, 0 }, { 50, 62, 0 } } },
 670   { { { 54, 0, 1 }, { 50, 63, 0 } } },
 671   { { { 54, 0, 2 }, { 51, 62, 0 } } },
 672   { { { 55, 0, 1 }, { 59, 47, 0 } } },
 673   { { { 55, 0, 0 }, { 51, 63, 0 } } },
 674   { { { 55, 0, 1 }, { 52, 62, 0 } } },
 675   { { { 55, 0, 2 }, { 52, 63, 0 } } },
 676   { { { 56, 0, 1 }, { 61, 46, 0 } } },
 677   { { { 56, 0, 0 }, { 53, 62, 0 } } },
 678   { { { 56, 0, 1 }, { 53, 63, 0 } } },
 679   { { { 56, 0, 2 }, { 54, 62, 0 } } },
 680   { { { 57, 0, 1 }, { 62, 47, 0 } } },
 681   { { { 57, 0, 0 }, { 54, 63, 0 } } },
 682   { { { 57, 0, 1 }, { 55, 62, 0 } } },
 683   { { { 57, 0, 2 }, { 55, 63, 0 } } },
 684   { { { 58, 0, 1 }, { 56, 62, 1 } } },
 685   { { { 58, 0, 0 }, { 56, 62, 0 } } },
 686   { { { 58, 0, 1 }, { 56, 63, 0 } } },
 687   { { { 58, 0, 2 }, { 57, 62, 0 } } },
 688   { { { 59, 0, 1 }, { 57, 63, 1 } } },
 689   { { { 59, 0, 0 }, { 57, 63, 0 } } },
 690   { { { 59, 0, 1 }, { 58, 62, 0 } } },
 691   { { { 59, 0, 2 }, { 58, 63, 0 } } },
 692   { { { 60, 0, 1 }, { 59, 62, 1 } } },
 693   { { { 60, 0, 0 }, { 59, 62, 0 } } },
 694   { { { 60, 0, 1 }, { 59, 63, 0 } } },
 695   { { { 60, 0, 2 }, { 60, 62, 0 } } },
 696   { { { 61, 0, 1 }, { 60, 63, 1 } } },
 697   { { { 61, 0, 0 }, { 60, 63, 0 } } },
 698   { { { 61, 0, 1 }, { 61, 62, 0 } } },
 699   { { { 61, 0, 2 }, { 61, 63, 0 } } },
 700   { { { 62, 0, 1 }, { 62, 62, 1 } } },
 701   { { { 62, 0, 0 }, { 62, 62, 0 } } },
 702   { { { 62, 0, 1 }, { 62, 63, 0 } } },
 703   { { { 62, 0, 2 }, { 63, 62, 0 } } },
 704   { { { 63, 0, 1 }, { 63, 63, 1 } } },
 705   { { { 63, 0, 0 }, { 63, 63, 0 } } }
 706 };
 707
 708 static const DDSSingleColourLookup*
 709   DDS_LOOKUP[] =
 710 {
 711   DDSLookup_5_4,
 712   DDSLookup_6_4,
 713   DDSLookup_5_4
 714 };
 715
 716 /*
 717   Macros
 718 */
 719 #define C565_r(x) (((x) & 0xF800) >> 11)
 720 #define C565_g(x) (((x) & 0x07E0) >> 5)
 721 #define C565_b(x)  ((x) & 0x001F)
 722
 723 #define C565_red(x)   ( (C565_r(x) << 3 | C565_r(x) >> 2))
 724 #define C565_green(x) ( (C565_g(x) << 2 | C565_g(x) >> 4))
 725 #define C565_blue(x)  ( (C565_b(x) << 3 | C565_b(x) >> 2))
 726
 727 #define DIV2(x)  ((x) > 1 ? ((x) >> 1) : 1)
 728
 729 #define FixRange(min, max, steps) \
 730 if (min > max) \
 731   min = max; \
 732 if ((ssize_t) max - min < steps) \
 733   max = MagickMin(min + steps, 255); \
 734 if ((ssize_t) max - min < steps) \
 735   min = MagickMax(0, (ssize_t) max - steps)
 736
 737 #define Dot(left, right) (left.x*right.x) + (left.y*right.y) + (left.z*right.z)
 738
 739 #define VectorInit(vector, value) vector.x = vector.y = vector.z = vector.w \
 740   = value
 741 #define VectorInit3(vector, value) vector.x = vector.y = vector.z = value
 742
 743 #define IsBitMask(mask, r, g, b, a) (mask.r_bitmask == r && mask.g_bitmask == \
 744   g && mask.b_bitmask == b && mask.alpha_bitmask == a)
 745
 746 /*
 747   Forward declarations
 748 */
 749 /*
 750   Forward declarations
 751 */
 752 static MagickBooleanType
 753   ConstructOrdering(const size_t,const DDSVector4 *,const DDSVector3,
 754     DDSVector4 *, DDSVector4 *, unsigned char *, size_t),
 755   ReadDDSInfo(Image *,DDSInfo *),
 756   ReadDXT1(const ImageInfo *,Image *,DDSInfo *,const MagickBooleanType,
 757     ExceptionInfo *),
 758   ReadDXT3(const ImageInfo *,Image *,DDSInfo *,const MagickBooleanType,
 759     ExceptionInfo *),
 760   ReadDXT5(const ImageInfo *,Image *,DDSInfo *,const MagickBooleanType,
 761     ExceptionInfo *),
 762   ReadUncompressedRGB(const ImageInfo *,Image *,DDSInfo *,
 763     const MagickBooleanType,ExceptionInfo *),
 764   ReadUncompressedRGBA(const ImageInfo *,Image *,DDSInfo *,
 765     const MagickBooleanType,ExceptionInfo *),
 766   SkipDXTMipmaps(Image *,DDSInfo *,int,ExceptionInfo *),
 767   SkipRGBMipmaps(Image *,DDSInfo *,int,ExceptionInfo *),
 768   WriteDDSImage(const ImageInfo *,Image *,ExceptionInfo *),
 769   WriteMipmaps(Image *,const ImageInfo*,const size_t,const size_t,const size_t,
 770     const MagickBooleanType,const MagickBooleanType,const MagickBooleanType,
 771     ExceptionInfo *);
 772
 773 static void
 774   RemapIndices(const ssize_t *,const unsigned char *,unsigned char *),
 775   WriteDDSInfo(Image *,const size_t,const size_t,const size_t),
 776   WriteFourCC(Image *,const size_t,const MagickBooleanType,
 777     const MagickBooleanType,ExceptionInfo *),
 778   WriteImageData(Image *,const size_t,const size_t,const MagickBooleanType,
 779     const MagickBooleanType,ExceptionInfo *),
 780   WriteIndices(Image *,const DDSVector3,const DDSVector3,unsigned char *),
 781   WriteSingleColorFit(Image *,const DDSVector4 *,const ssize_t *),
 782   WriteUncompressed(Image *,ExceptionInfo *);
 783
 784 static inline void VectorAdd(const DDSVector4 left, const DDSVector4 right,
 785   DDSVector4 *destination)
 786 {
 787   destination->x = left.x + right.x;
 788   destination->y = left.y + right.y;
 789   destination->z = left.z + right.z;
 790   destination->w = left.w + right.w;
 791 }
 792
 793 static inline void VectorClamp(DDSVector4 *value)
 794 {
 795   value->x = MagickMin(1.0f,MagickMax(0.0f,value->x));
 796   value->y = MagickMin(1.0f,MagickMax(0.0f,value->y));
 797   value->z = MagickMin(1.0f,MagickMax(0.0f,value->z));
 798   value->w = MagickMin(1.0f,MagickMax(0.0f,value->w));
 799 }
 800
 801 static inline void VectorClamp3(DDSVector3 *value)
 802 {
 803   value->x = MagickMin(1.0f,MagickMax(0.0f,value->x));
 804   value->y = MagickMin(1.0f,MagickMax(0.0f,value->y));
 805   value->z = MagickMin(1.0f,MagickMax(0.0f,value->z));
 806 }
 807
 808 static inline void VectorCopy43(const DDSVector4 source,
 809   DDSVector3 *destination)
 810 {
 811   destination->x = source.x;
 812   destination->y = source.y;
 813   destination->z = source.z;
 814 }
 815
 816 static inline void VectorCopy44(const DDSVector4 source,
 817   DDSVector4 *destination)
 818 {
 819   destination->x = source.x;
 820   destination->y = source.y;
 821   destination->z = source.z;
 822   destination->w = source.w;
 823 }
 824
 825 static inline void VectorNegativeMultiplySubtract(const DDSVector4 a,
 826   const DDSVector4 b, const DDSVector4 c, DDSVector4 *destination)
 827 {
 828   destination->x = c.x - (a.x * b.x);
 829   destination->y = c.y - (a.y * b.y);
 830   destination->z = c.z - (a.z * b.z);
 831   destination->w = c.w - (a.w * b.w);
 832 }
 833
 834 static inline void VectorMultiply(const DDSVector4 left,
 835   const DDSVector4 right, DDSVector4 *destination)
 836 {
 837   destination->x = left.x * right.x;
 838   destination->y = left.y * right.y;
 839   destination->z = left.z * right.z;
 840   destination->w = left.w * right.w;
 841 }
 842
 843 static inline void VectorMultiply3(const DDSVector3 left,
 844   const DDSVector3 right, DDSVector3 *destination)
 845 {
 846   destination->x = left.x * right.x;
 847   destination->y = left.y * right.y;
 848   destination->z = left.z * right.z;
 849 }
 850
 851 static inline void VectorMultiplyAdd(const DDSVector4 a, const DDSVector4 b,
 852   const DDSVector4 c, DDSVector4 *destination)
 853 {
 854   destination->x = (a.x * b.x) + c.x;
 855   destination->y = (a.y * b.y) + c.y;
 856   destination->z = (a.z * b.z) + c.z;
 857   destination->w = (a.w * b.w) + c.w;
 858 }
 859
 860 static inline void VectorMultiplyAdd3(const DDSVector3 a, const DDSVector3 b,
 861   const DDSVector3 c, DDSVector3 *destination)
 862 {
 863   destination->x = (a.x * b.x) + c.x;
 864   destination->y = (a.y * b.y) + c.y;
 865   destination->z = (a.z * b.z) + c.z;
 866 }
 867
 868 static inline void VectorReciprocal(const DDSVector4 value,
 869   DDSVector4 *destination)
 870 {
 871   destination->x = 1.0f / value.x;
 872   destination->y = 1.0f / value.y;
 873   destination->z = 1.0f / value.z;
 874   destination->w = 1.0f / value.w;
 875 }
 876
 877 static inline void VectorSubtract(const DDSVector4 left,
 878   const DDSVector4 right, DDSVector4 *destination)
 879 {
 880   destination->x = left.x - right.x;
 881   destination->y = left.y - right.y;
 882   destination->z = left.z - right.z;
 883   destination->w = left.w - right.w;
 884 }
 885
 886 static inline void VectorSubtract3(const DDSVector3 left,
 887   const DDSVector3 right, DDSVector3 *destination)
 888 {
 889   destination->x = left.x - right.x;
 890   destination->y = left.y - right.y;
 891   destination->z = left.z - right.z;
 892 }
 893
 894 static inline void VectorTruncate(DDSVector4 *value)
 895 {
 896   value->x = value->x > 0.0f ? floor(value->x) : ceil(value->x);
 897   value->y = value->y > 0.0f ? floor(value->y) : ceil(value->y);
 898   value->z = value->z > 0.0f ? floor(value->z) : ceil(value->z);
 899   value->w = value->w > 0.0f ? floor(value->w) : ceil(value->w);
 900 }
 901
 902 static inline void VectorTruncate3(DDSVector3 *value)
 903 {
 904   value->x = value->x > 0.0f ? floor(value->x) : ceil(value->x);
 905   value->y = value->y > 0.0f ? floor(value->y) : ceil(value->y);
 906   value->z = value->z > 0.0f ? floor(value->z) : ceil(value->z);
 907 }
 908
 909 static void CalculateColors(unsigned short c0, unsigned short c1,
 910   DDSColors *c, MagickBooleanType ignoreAlpha)
 911 {
 912   c->a[0] = c->a[1] = c->a[2] = c->a[3] = 0;
 913
 914   c->r[0] = (unsigned char) C565_red(c0);
 915   c->g[0] = (unsigned char) C565_green(c0);
 916   c->b[0] = (unsigned char) C565_blue(c0);
 917
 918   c->r[1] = (unsigned char) C565_red(c1);
 919   c->g[1] = (unsigned char) C565_green(c1);
 920   c->b[1] = (unsigned char) C565_blue(c1);
 921
 922   if (ignoreAlpha != MagickFalse || c0 > c1)
 923     {
 924       c->r[2] = (unsigned char) ((2 * c->r[0] + c->r[1]) / 3);
 925       c->g[2] = (unsigned char) ((2 * c->g[0] + c->g[1]) / 3);
 926       c->b[2] = (unsigned char) ((2 * c->b[0] + c->b[1]) / 3);
 927
 928       c->r[3] = (unsigned char) ((c->r[0] + 2 * c->r[1]) / 3);
 929       c->g[3] = (unsigned char) ((c->g[0] + 2 * c->g[1]) / 3);
 930       c->b[3] = (unsigned char) ((c->b[0] + 2 * c->b[1]) / 3);
 931     }
 932   else
 933     {
 934       c->r[2] = (unsigned char) ((c->r[0] + c->r[1]) / 2);
 935       c->g[2] = (unsigned char) ((c->g[0] + c->g[1]) / 2);
 936       c->b[2] = (unsigned char) ((c->b[0] + c->b[1]) / 2);
 937
 938       c->r[3] = c->g[3] = c->b[3] = 0;
 939       c->a[3] = 255;
 940     }
 941 }
 942
 943 static size_t CompressAlpha(const size_t min, const size_t max,
 944   const size_t steps, const ssize_t *alphas, unsigned char* indices)
 945 {
 946   unsigned char
 947     codes[8];
 948
 949   register ssize_t
 950     i;
 951
 952   size_t
 953     error,
 954     index,
 955     j,
 956     least,
 957     value;
 958
 959   codes[0] = (unsigned char) min;
 960   codes[1] = (unsigned char) max;
 961   codes[6] = 0;
 962   codes[7] = 255;
 963
 964   for (i=1; i <  (ssize_t) steps; i++)
 965     codes[i+1] = (unsigned char) (((steps-i)*min + i*max) / steps);
 966
 967   error = 0;
 968   for (i=0; i<16; i++)
 969   {
 970     if (alphas[i] == -1)
 971       {
 972         indices[i] = 0;
 973         continue;
 974       }
 975
 976     value = alphas[i];
 977     least = SIZE_MAX;
 978     index = 0;
 979     for (j=0; j<8; j++)
 980     {
 981       size_t
 982         dist;
 983
 984       dist = value - (size_t)codes[j];
 985       dist *= dist;
 986
 987       if (dist < least)
 988         {
 989           least = dist;
 990           index = j;
 991         }
 992     }
 993
 994     indices[i] = (unsigned char)index;
 995     error += least;
 996   }
 997
 998   return error;
 999 }
1000
1001 static void CompressClusterFit(const size_t count,
1002   const DDSVector4 *points, const ssize_t *map, const DDSVector3 principle,
1003   const DDSVector4 metric, DDSVector3 *start, DDSVector3* end,
1004   unsigned char *indices)
1005 {
1006   DDSVector3
1007     axis;
1008
1009   DDSVector4
1010     grid,
1011     gridrcp,
1012     half,
1013     onethird_onethird2,
1014     pointsWeights[16],
1015     two,
1016     twonineths,
1017     twothirds_twothirds2,
1018     xSumwSum;
1019
1020   float
1021     bestError = 1e+37f;
1022
1023   size_t
1024     bestIteration = 0,
1025     besti = 0,
1026     bestj = 0,
1027     bestk = 0,
1028     iterationIndex;
1029
1030   ssize_t
1031     i;
1032
1033   unsigned char
1034     *o,
1035     order[128],
1036     unordered[16];
1037
1038   VectorInit(half,0.5f);
1039   VectorInit(two,2.0f);
1040
1041   VectorInit(onethird_onethird2,1.0f/3.0f);
1042   onethird_onethird2.w = 1.0f/9.0f;
1043   VectorInit(twothirds_twothirds2,2.0f/3.0f);
1044   twothirds_twothirds2.w = 4.0f/9.0f;
1045   VectorInit(twonineths,2.0f/9.0f);
1046
1047   grid.x = 31.0f;
1048   grid.y = 63.0f;
1049   grid.z = 31.0f;
1050   grid.w = 0.0f;
1051
1052   gridrcp.x = 1.0f/31.0f;
1053   gridrcp.y = 1.0f/63.0f;
1054   gridrcp.z = 1.0f/31.0f;
1055   gridrcp.w = 0.0f;
1056
1057   xSumwSum.x = 0.0f;
1058   xSumwSum.y = 0.0f;
1059   xSumwSum.z = 0.0f;
1060   xSumwSum.w = 0.0f;
1061
1062   ConstructOrdering(count,points,principle,pointsWeights,&xSumwSum,order,0);
1063
1064   for (iterationIndex = 0;;)
1065   {
1066 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1067   #pragma omp parallel for schedule(dynamic,1) \
1068     num_threads(GetMagickResourceLimit(ThreadResource))
1069 #endif
1070     for (i=0; i < (ssize_t) count; i++)
1071     {
1072       DDSVector4
1073         part0,
1074         part1,
1075         part2;
1076
1077       size_t
1078         ii,
1079         j,
1080         k,
1081         kmin;
1082
1083       VectorInit(part0,0.0f);
1084       for(ii=0; ii < (size_t) i; ii++)
1085         VectorAdd(pointsWeights[ii],part0,&part0);
1086
1087       VectorInit(part1,0.0f);
1088       for (j=(size_t) i;;)
1089       {
1090         if (j == 0)
1091           {
1092             VectorCopy44(pointsWeights[0],&part2);
1093             kmin = 1;
1094           }
1095           else
1096           {
1097             VectorInit(part2,0.0f);
1098             kmin = j;
1099           }
1100
1101         for (k=kmin;;)
1102         {
1103           DDSVector4
1104             a,
1105             alpha2_sum,
1106             alphax_sum,
1107             alphabeta_sum,
1108             b,
1109             beta2_sum,
1110             betax_sum,
1111             e1,
1112             e2,
1113             factor,
1114             part3;
1115
1116           float
1117             error;
1118
1119           VectorSubtract(xSumwSum,part2,&part3);
1120           VectorSubtract(part3,part1,&part3);
1121           VectorSubtract(part3,part0,&part3);
1122
1123           VectorMultiplyAdd(part1,twothirds_twothirds2,part0,&alphax_sum);
1124           VectorMultiplyAdd(part2,onethird_onethird2,alphax_sum,&alphax_sum);
1125           VectorInit(alpha2_sum,alphax_sum.w);
1126
1127           VectorMultiplyAdd(part2,twothirds_twothirds2,part3,&betax_sum);
1128           VectorMultiplyAdd(part1,onethird_onethird2,betax_sum,&betax_sum);
1129           VectorInit(beta2_sum,betax_sum.w);
1130
1131           VectorAdd(part1,part2,&alphabeta_sum);
1132           VectorInit(alphabeta_sum,alphabeta_sum.w);
1133           VectorMultiply(twonineths,alphabeta_sum,&alphabeta_sum);
1134
1135           VectorMultiply(alpha2_sum,beta2_sum,&factor);
1136           VectorNegativeMultiplySubtract(alphabeta_sum,alphabeta_sum,factor,
1137             &factor);
1138           VectorReciprocal(factor,&factor);
1139
1140           VectorMultiply(alphax_sum,beta2_sum,&a);
1141           VectorNegativeMultiplySubtract(betax_sum,alphabeta_sum,a,&a);
1142           VectorMultiply(a,factor,&a);
1143
1144           VectorMultiply(betax_sum,alpha2_sum,&b);
1145           VectorNegativeMultiplySubtract(alphax_sum,alphabeta_sum,b,&b);
1146           VectorMultiply(b,factor,&b);
1147
1148           VectorClamp(&a);
1149           VectorMultiplyAdd(grid,a,half,&a);
1150           VectorTruncate(&a);
1151           VectorMultiply(a,gridrcp,&a);
1152
1153           VectorClamp(&b);
1154           VectorMultiplyAdd(grid,b,half,&b);
1155           VectorTruncate(&b);
1156           VectorMultiply(b,gridrcp,&b);
1157
1158           VectorMultiply(b,b,&e1);
1159           VectorMultiply(e1,beta2_sum,&e1);
1160           VectorMultiply(a,a,&e2);
1161           VectorMultiplyAdd(e2,alpha2_sum,e1,&e1);
1162
1163           VectorMultiply(a,b,&e2);
1164           VectorMultiply(e2,alphabeta_sum,&e2);
1165           VectorNegativeMultiplySubtract(a,alphax_sum,e2,&e2);
1166           VectorNegativeMultiplySubtract(b,betax_sum,e2,&e2);
1167           VectorMultiplyAdd(two,e2,e1,&e2);
1168           VectorMultiply(e2,metric,&e2);
1169
1170           error = e2.x + e2.y + e2.z;
1171
1172           if (error < bestError)
1173             {
1174 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1175               #pragma omp critical (DDS_CompressClusterFit)
1176 #endif
1177               {
1178                 if (error < bestError)
1179                   {
1180                     VectorCopy43(a,start);
1181                     VectorCopy43(b,end);
1182                     bestError = error;
1183                     besti = i;
1184                     bestj = j;
1185                     bestk = k;
1186                     bestIteration = iterationIndex;
1187                   }
1188               }
1189             }
1190
1191           if (k == count)
1192             break;
1193
1194           VectorAdd(pointsWeights[k],part2,&part2);
1195           k++;
1196         }
1197
1198         if (j == count)
1199           break;
1200
1201         VectorAdd(pointsWeights[j],part1,&part1);
1202         j++;
1203       }
1204     }
1205
1206     if (bestIteration != iterationIndex)
1207       break;
1208
1209     iterationIndex++;
1210     if (iterationIndex == 8)
1211       break;
1212
1213     VectorSubtract3(*end,*start,&axis);
1214     if (ConstructOrdering(count,points,axis,pointsWeights,&xSumwSum,order,
1215       iterationIndex) == MagickFalse)
1216       break;
1217   }
1218
1219   o = order + (16*bestIteration);
1220
1221   for (i=0; i < (ssize_t) besti; i++)
1222     unordered[o[i]] = 0;
1223   for (i=besti; i < (ssize_t) bestj; i++)
1224     unordered[o[i]] = 2;
1225   for (i=bestj; i < (ssize_t) bestk; i++)
1226     unordered[o[i]] = 3;
1227   for (i=bestk; i < (ssize_t) count; i++)
1228     unordered[o[i]] = 1;
1229
1230   RemapIndices(map,unordered,indices);
1231 }
1232
1233 static void CompressRangeFit(const size_t count,
1234   const DDSVector4* points, const ssize_t *map, const DDSVector3 principle,
1235   const DDSVector4 metric, DDSVector3 *start, DDSVector3 *end,
1236   unsigned char *indices)
1237 {
1238   float
1239     d,
1240     bestDist,
1241     max,
1242     min,
1243     val;
1244
1245   DDSVector3
1246     codes[4],
1247     grid,
1248     gridrcp,
1249     half,
1250     dist;
1251
1252   register ssize_t
1253     i;
1254
1255   size_t
1256     bestj,
1257     j;
1258
1259   unsigned char
1260     closest[16];
1261
1262   VectorInit3(half,0.5f);
1263
1264   grid.x = 31.0f;
1265   grid.y = 63.0f;
1266   grid.z = 31.0f;
1267
1268   gridrcp.x = 1.0f/31.0f;
1269   gridrcp.y = 1.0f/63.0f;
1270   gridrcp.z = 1.0f/31.0f;
1271
1272   if (count > 0)
1273     {
1274       VectorCopy43(points[0],start);
1275       VectorCopy43(points[0],end);
1276
1277       min = max = Dot(points[0],principle);
1278       for (i=1; i < (ssize_t) count; i++)
1279       {
1280         val = Dot(points[i],principle);
1281         if (val < min)
1282         {
1283           VectorCopy43(points[i],start);
1284           min = val;
1285         }
1286         else if (val > max)
1287         {
1288           VectorCopy43(points[i],end);
1289           max = val;
1290         }
1291       }
1292     }
1293
1294   VectorClamp3(start);
1295   VectorMultiplyAdd3(grid,*start,half,start);
1296   VectorTruncate3(start);
1297   VectorMultiply3(*start,gridrcp,start);
1298
1299   VectorClamp3(end);
1300   VectorMultiplyAdd3(grid,*end,half,end);
1301   VectorTruncate3(end);
1302   VectorMultiply3(*end,gridrcp,end);
1303
1304   codes[0] = *start;
1305   codes[1] = *end;
1306   codes[2].x = (start->x * (2.0f/3.0f)) + (end->x * (1.0f/3.0f));
1307   codes[2].y = (start->y * (2.0f/3.0f)) + (end->y * (1.0f/3.0f));
1308   codes[2].z = (start->z * (2.0f/3.0f)) + (end->z * (1.0f/3.0f));
1309   codes[3].x = (start->x * (1.0f/3.0f)) + (end->x * (2.0f/3.0f));
1310   codes[3].y = (start->y * (1.0f/3.0f)) + (end->y * (2.0f/3.0f));
1311   codes[3].z = (start->z * (1.0f/3.0f)) + (end->z * (2.0f/3.0f));
1312
1313   for (i=0; i < (ssize_t) count; i++)
1314   {
1315     bestDist = 1e+37f;
1316     bestj = 0;
1317     for (j=0; j < 4; j++)
1318     {
1319       dist.x = (points[i].x - codes[j].x) * metric.x;
1320       dist.y = (points[i].y - codes[j].y) * metric.y;
1321       dist.z = (points[i].z - codes[j].z) * metric.z;
1322
1323       d = Dot(dist,dist);
1324       if (d < bestDist)
1325         {
1326           bestDist = d;
1327           bestj = j;
1328         }
1329     }
1330
1331     closest[i] = (unsigned char) bestj;
1332   }
1333
1334   RemapIndices(map, closest, indices);
1335 }
1336
1337 static void ComputeEndPoints(const DDSSingleColourLookup *lookup[],
1338   const unsigned char *color, DDSVector3 *start, DDSVector3 *end,
1339   unsigned char *index)
1340 {
1341   register ssize_t
1342     i;
1343
1344   size_t
1345     c,
1346     maxError = SIZE_MAX;
1347
1348   for (i=0; i < 2; i++)
1349   {
1350     const DDSSourceBlock*
1351       sources[3];
1352
1353       size_t
1354         error = 0;
1355
1356     for (c=0; c < 3; c++)
1357     {
1358       sources[c] = &lookup[c][color[c]].sources[i];
1359       error += ((size_t) sources[c]->error) * ((size_t) sources[c]->error);
1360     }
1361
1362     if (error > maxError)
1363       continue;
1364
1365     start->x = (float) sources[0]->start / 31.0f;
1366     start->y = (float) sources[1]->start / 63.0f;
1367     start->z = (float) sources[2]->start / 31.0f;
1368
1369     end->x = (float) sources[0]->end / 31.0f;
1370     end->y = (float) sources[1]->end / 63.0f;
1371     end->z = (float) sources[2]->end / 31.0f;
1372
1373     *index = (unsigned char) (2*i);
1374     maxError = error;
1375   }
1376 }
1377
1378 static void ComputePrincipleComponent(const float *covariance,
1379   DDSVector3 *principle)
1380 {
1381   DDSVector4
1382     row0,
1383     row1,
1384     row2,
1385     v;
1386
1387   register ssize_t
1388     i;
1389
1390   row0.x = covariance[0];
1391   row0.y = covariance[1];
1392   row0.z = covariance[2];
1393   row0.w = 0.0f;
1394
1395   row1.x = covariance[1];
1396   row1.y = covariance[3];
1397   row1.z = covariance[4];
1398   row1.w = 0.0f;
1399
1400   row2.x = covariance[2];
1401   row2.y = covariance[4];
1402   row2.z = covariance[5];
1403   row2.w = 0.0f;
1404
1405   VectorInit(v,1.0f);
1406
1407   for (i=0; i < 8; i++)
1408   {
1409     DDSVector4
1410       w;
1411
1412     float
1413       a;
1414
1415     w.x = row0.x * v.x;
1416     w.y = row0.y * v.x;
1417     w.z = row0.z * v.x;
1418     w.w = row0.w * v.x;
1419
1420     w.x = (row1.x * v.y) + w.x;
1421     w.y = (row1.y * v.y) + w.y;
1422     w.z = (row1.z * v.y) + w.z;
1423     w.w = (row1.w * v.y) + w.w;
1424
1425     w.x = (row2.x * v.z) + w.x;
1426     w.y = (row2.y * v.z) + w.y;
1427     w.z = (row2.z * v.z) + w.z;
1428     w.w = (row2.w * v.z) + w.w;
1429
1430     a = (float) PerceptibleReciprocal(MagickMax(w.x,MagickMax(w.y,w.z)));
1431
1432     v.x = w.x * a;
1433     v.y = w.y * a;
1434     v.z = w.z * a;
1435     v.w = w.w * a;
1436   }
1437
1438   VectorCopy43(v,principle);
1439 }
1440
1441 static void ComputeWeightedCovariance(const size_t count,
1442   const DDSVector4 *points, float *covariance)
1443 {
1444   DDSVector3
1445     centroid;
1446
1447   float
1448     total;
1449
1450   size_t
1451     i;
1452
1453   total = 0.0f;
1454   VectorInit3(centroid,0.0f);
1455
1456   for (i=0; i < count; i++)
1457   {
1458     total += points[i].w;
1459     centroid.x += (points[i].x * points[i].w);
1460     centroid.y += (points[i].y * points[i].w);
1461     centroid.z += (points[i].z * points[i].w);
1462   }
1463
1464   if( total > 1.192092896e-07F)
1465     {
1466       centroid.x /= total;
1467       centroid.y /= total;
1468       centroid.z /= total;
1469     }
1470
1471   for (i=0; i < 6; i++)
1472     covariance[i] = 0.0f;
1473
1474   for (i = 0; i < count; i++)
1475   {
1476     DDSVector3
1477       a,
1478       b;
1479
1480     a.x = points[i].x - centroid.x;
1481     a.y = points[i].y - centroid.y;
1482     a.z = points[i].z - centroid.z;
1483
1484     b.x = points[i].w * a.x;
1485     b.y = points[i].w * a.y;
1486     b.z = points[i].w * a.z;
1487
1488     covariance[0] += a.x*b.x;
1489     covariance[1] += a.x*b.y;
1490     covariance[2] += a.x*b.z;
1491     covariance[3] += a.y*b.y;
1492     covariance[4] += a.y*b.z;
1493     covariance[5] += a.z*b.z;
1494   }
1495 }
1496
1497 static MagickBooleanType ConstructOrdering(const size_t count,
1498   const DDSVector4 *points, const DDSVector3 axis, DDSVector4 *pointsWeights,
1499   DDSVector4 *xSumwSum, unsigned char *order, size_t iteration)
1500 {
1501   float
1502      dps[16],
1503      f;
1504
1505   register ssize_t
1506     i;
1507
1508   size_t
1509     j;
1510
1511   unsigned char
1512     c,
1513     *o,
1514     *p;
1515
1516   o = order + (16*iteration);
1517
1518   for (i=0; i < (ssize_t) count; i++)
1519   {
1520     dps[i] = Dot(points[i],axis);
1521     o[i] = (unsigned char)i;
1522   }
1523
1524   for (i=0; i < (ssize_t) count; i++)
1525   {
1526     for (j=i; j > 0 && dps[j] < dps[j - 1]; j--)
1527     {
1528       f = dps[j];
1529       dps[j] = dps[j - 1];
1530       dps[j - 1] = f;
1531
1532       c = o[j];
1533       o[j] = o[j - 1];
1534       o[j - 1] = c;
1535     }
1536   }
1537
1538   for (i=0; i < (ssize_t) iteration; i++)
1539   {
1540     MagickBooleanType
1541       same;
1542
1543     p = order + (16*i);
1544     same = MagickTrue;
1545
1546     for (j=0; j < count; j++)
1547     {
1548       if (o[j] != p[j])
1549         {
1550           same = MagickFalse;
1551           break;
1552         }
1553     }
1554
1555     if (same != MagickFalse)
1556       return MagickFalse;
1557   }
1558
1559   xSumwSum->x = 0;
1560   xSumwSum->y = 0;
1561   xSumwSum->z = 0;
1562   xSumwSum->w = 0;
1563
1564   for (i=0; i < (ssize_t) count; i++)
1565   {
1566     DDSVector4
1567       v;
1568
1569     j = (size_t) o[i];
1570
1571     v.x = points[j].w * points[j].x;
1572     v.y = points[j].w * points[j].y;
1573     v.z = points[j].w * points[j].z;
1574     v.w = points[j].w * 1.0f;
1575
1576     VectorCopy44(v,&pointsWeights[i]);
1577     VectorAdd(*xSumwSum,v,xSumwSum);
1578   }
1579
1580   return MagickTrue;
1581 }
1582
1583 /*
1584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1585 %                                                                             %
1586 %                                                                             %
1587 %                                                                             %
1588 %   I s D D S                                                                 %
1589 %                                                                             %
1590 %                                                                             %
1591 %                                                                             %
1592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1593 %
1594 %  IsDDS() returns MagickTrue if the image format type, identified by the
1595 %  magick string, is DDS.
1596 %
1597 %  The format of the IsDDS method is:
1598 %
1599 %      MagickBooleanType IsDDS(const unsigned char *magick,const size_t length)
1600 %
1601 %  A description of each parameter follows:
1602 %
1603 %    o magick: compare image format pattern against these bytes.
1604 %
1605 %    o length: Specifies the length of the magick string.
1606 %
1607 */
1608 static MagickBooleanType IsDDS(const unsigned char *magick, const size_t length)
1609 {
1610   if (length < 4)
1611     return(MagickFalse);
1612   if (LocaleNCompare((char *) magick,"DDS ", 4) == 0)
1613     return(MagickTrue);
1614   return(MagickFalse);
1615 }
1616 /*
1617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1618 %                                                                             %
1619 %                                                                             %
1620 %                                                                             %
1621 %   R e a d D D S I m a g e                                                   %
1622 %                                                                             %
1623 %                                                                             %
1624 %                                                                             %
1625 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1626 %
1627 %  ReadDDSImage() reads a DirectDraw Surface image file and returns it.  It
1628 %  allocates the memory necessary for the new Image structure and returns a
1629 %  pointer to the new image.
1630 %
1631 %  The format of the ReadDDSImage method is:
1632 %
1633 %      Image *ReadDDSImage(const ImageInfo *image_info,ExceptionInfo *exception)
1634 %
1635 %  A description of each parameter follows:
1636 %
1637 %    o image_info: The image info.
1638 %
1639 %    o exception: return any errors or warnings in this structure.
1640 %
1641 */
1642
1643 static Image *ReadDDSImage(const ImageInfo *image_info,ExceptionInfo *exception)
1644 {
1645   const char
1646     *option;
1647
1648   CompressionType
1649     compression;
1650
1651   DDSInfo
1652     dds_info;
1653
1654   DDSDecoder
1655     *decoder;
1656
1657   Image
1658     *image;
1659
1660   MagickBooleanType
1661     status,
1662     cubemap,
1663     volume,
1664     read_mipmaps;
1665
1666   PixelTrait
1667     alpha_trait;
1668
1669   size_t
1670     n,
1671     num_images;
1672
1673   /*
1674     Open image file.
1675   */
1676   assert(image_info != (const ImageInfo *) NULL);
1677   assert(image_info->signature == MagickCoreSignature);
1678   if (image_info->debug != MagickFalse)
1679     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",
1680       image_info->filename);
1681   assert(exception != (ExceptionInfo *) NULL);
1682   assert(exception->signature == MagickCoreSignature);
1683   cubemap=MagickFalse,
1684   volume=MagickFalse,
1685   read_mipmaps=MagickFalse;
1686   image=AcquireImage(image_info,exception);
1687   status=OpenBlob(image_info,image,ReadBinaryBlobMode,exception);
1688   if (status == MagickFalse)
1689     {
1690       image=DestroyImageList(image);
1691       return((Image *) NULL);
1692     }
1693
1694   /*
1695     Initialize image structure.
1696   */
1697   if (ReadDDSInfo(image, &dds_info) != MagickTrue)
1698     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1699
1700   if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP)
1701     cubemap = MagickTrue;
1702
1703   if (dds_info.ddscaps2 & DDSCAPS2_VOLUME && dds_info.depth > 0)
1704     volume = MagickTrue;
1705
1706   (void) SeekBlob(image, 128, SEEK_SET);
1707
1708   /*
1709     Determine pixel format
1710   */
1711   if (dds_info.pixelformat.flags & DDPF_RGB)
1712     {
1713       compression = NoCompression;
1714       if (dds_info.pixelformat.flags & DDPF_ALPHAPIXELS)
1715         {
1716           alpha_trait = BlendPixelTrait;
1717           decoder = ReadUncompressedRGBA;
1718         }
1719       else
1720         {
1721           alpha_trait = UndefinedPixelTrait;
1722           decoder = ReadUncompressedRGB;
1723         }
1724     }
1725   else if (dds_info.pixelformat.flags & DDPF_LUMINANCE)
1726    {
1727       compression = NoCompression;
1728       if (dds_info.pixelformat.flags & DDPF_ALPHAPIXELS)
1729         {
1730           /* Not sure how to handle this */
1731           ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1732         }
1733       else
1734         {
1735           alpha_trait = UndefinedPixelTrait;
1736           decoder = ReadUncompressedRGB;
1737         }
1738     }
1739   else if (dds_info.pixelformat.flags & DDPF_FOURCC)
1740     {
1741       switch (dds_info.pixelformat.fourcc)
1742       {
1743         case FOURCC_DXT1:
1744         {
1745           alpha_trait = UndefinedPixelTrait;
1746           compression = DXT1Compression;
1747           decoder = ReadDXT1;
1748           break;
1749         }
1750         case FOURCC_DXT3:
1751         {
1752           alpha_trait = BlendPixelTrait;
1753           compression = DXT3Compression;
1754           decoder = ReadDXT3;
1755           break;
1756         }
1757         case FOURCC_DXT5:
1758         {
1759           alpha_trait = BlendPixelTrait;
1760           compression = DXT5Compression;
1761           decoder = ReadDXT5;
1762           break;
1763         }
1764         default:
1765         {
1766           /* Unknown FOURCC */
1767           ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1768         }
1769       }
1770     }
1771   else
1772     {
1773       /* Neither compressed nor uncompressed... thus unsupported */
1774       ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1775     }
1776
1777   num_images = 1;
1778   if (cubemap)
1779     {
1780       /*
1781         Determine number of faces defined in the cubemap
1782       */
1783       num_images = 0;
1784       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEX) num_images++;
1785       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEX) num_images++;
1786       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEY) num_images++;
1787       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEY) num_images++;
1788       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEZ) num_images++;
1789       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEZ) num_images++;
1790     }
1791
1792   if (volume)
1793     num_images = dds_info.depth;
1794
1795   if ((num_images == 0) || (num_images > GetBlobSize(image)))
1796     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1797
1798   if (AcquireMagickResource(ListLengthResource,num_images) == MagickFalse)
1799     ThrowReaderException(ResourceLimitError,"ListLengthExceedsLimit");
1800
1801   option=GetImageOption(image_info,"dds:skip-mipmaps");
1802   if (IsStringFalse(option) != MagickFalse)
1803     read_mipmaps=MagickTrue;
1804
1805   for (n = 0; n < num_images; n++)
1806   {
1807     if (n != 0)
1808       {
1809         /* Start a new image */
1810         if (EOFBlob(image) != MagickFalse)
1811           ThrowReaderException(CorruptImageError,"UnexpectedEndOfFile");
1812         AcquireNextImage(image_info,image,exception);
1813         if (GetNextImageInList(image) == (Image *) NULL)
1814           return(DestroyImageList(image));
1815         image=SyncNextImageInList(image);
1816       }
1817
1818     image->alpha_trait=alpha_trait;
1819     image->compression=compression;
1820     image->columns=dds_info.width;
1821     image->rows=dds_info.height;
1822     image->storage_class=DirectClass;
1823     image->endian=LSBEndian;
1824     image->depth=8;
1825     if (image_info->ping != MagickFalse)
1826       {
1827         (void) CloseBlob(image);
1828         return(GetFirstImageInList(image));
1829       }
1830     status=SetImageExtent(image,image->columns,image->rows,exception);
1831     if (status == MagickFalse)
1832       return(DestroyImageList(image));
1833     (void) SetImageBackgroundColor(image,exception);
1834     status=(decoder)(image_info,image,&dds_info,read_mipmaps,exception);
1835     if (status == MagickFalse)
1836       {
1837         (void) CloseBlob(image);
1838         return(GetFirstImageInList(image));
1839       }
1840   }
1841   (void) CloseBlob(image);
1842   return(GetFirstImageInList(image));
1843 }
1844
1845 static MagickBooleanType ReadDDSInfo(Image *image, DDSInfo *dds_info)
1846 {
1847   size_t
1848     hdr_size,
1849     required;
1850
1851   /* Seek to start of header */
1852   (void) SeekBlob(image, 4, SEEK_SET);
1853
1854   /* Check header field */
1855   hdr_size = ReadBlobLSBLong(image);
1856   if (hdr_size != 124)
1857     return MagickFalse;
1858
1859   /* Fill in DDS info struct */
1860   dds_info->flags = ReadBlobLSBLong(image);
1861
1862   /* Check required flags */
1863   required=(size_t) (DDSD_WIDTH | DDSD_HEIGHT | DDSD_PIXELFORMAT);
1864   if ((dds_info->flags & required) != required)
1865     return MagickFalse;
1866
1867   dds_info->height = ReadBlobLSBLong(image);
1868   dds_info->width = ReadBlobLSBLong(image);
1869   dds_info->pitchOrLinearSize = ReadBlobLSBLong(image);
1870   dds_info->depth = ReadBlobLSBLong(image);
1871   dds_info->mipmapcount = ReadBlobLSBLong(image);
1872
1873   (void) SeekBlob(image, 44, SEEK_CUR);   /* reserved region of 11 DWORDs */
1874
1875   /* Read pixel format structure */
1876   hdr_size = ReadBlobLSBLong(image);
1877   if (hdr_size != 32)
1878     return MagickFalse;
1879
1880   dds_info->pixelformat.flags = ReadBlobLSBLong(image);
1881   dds_info->pixelformat.fourcc = ReadBlobLSBLong(image);
1882   dds_info->pixelformat.rgb_bitcount = ReadBlobLSBLong(image);
1883   dds_info->pixelformat.r_bitmask = ReadBlobLSBLong(image);
1884   dds_info->pixelformat.g_bitmask = ReadBlobLSBLong(image);
1885   dds_info->pixelformat.b_bitmask = ReadBlobLSBLong(image);
1886   dds_info->pixelformat.alpha_bitmask = ReadBlobLSBLong(image);
1887
1888   dds_info->ddscaps1 = ReadBlobLSBLong(image);
1889   dds_info->ddscaps2 = ReadBlobLSBLong(image);
1890   (void) SeekBlob(image, 12, SEEK_CUR); /* 3 reserved DWORDs */
1891
1892   return MagickTrue;
1893 }
1894
1895 static MagickBooleanType SetDXT1Pixels(Image *image,ssize_t x,ssize_t y,
1896   DDSColors colors,size_t bits,Quantum *q)
1897 {
1898   register ssize_t
1899     i;
1900
1901   ssize_t
1902     j;
1903
1904   unsigned char
1905     code;
1906
1907   for (j = 0; j < 4; j++)
1908   {
1909     for (i = 0; i < 4; i++)
1910     {
1911       if ((x + i) < (ssize_t) image->columns &&
1912           (y + j) < (ssize_t) image->rows)
1913         {
1914           code=(unsigned char) ((bits >> ((j*4+i)*2)) & 0x3);
1915           SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
1916           SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
1917           SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
1918           SetPixelOpacity(image,ScaleCharToQuantum(colors.a[code]),q);
1919           if ((colors.a[code] != 0) &&
1920               (image->alpha_trait == UndefinedPixelTrait))
1921             return(MagickFalse);
1922           q+=GetPixelChannels(image);
1923         }
1924     }
1925   }
1926   return(MagickTrue);
1927 }
1928
1929 static MagickBooleanType ReadMipmaps(const ImageInfo *image_info,Image *image,
1930   DDSInfo *dds_info,DDSPixelDecoder decoder,ExceptionInfo *exception)
1931 {
1932   MagickBooleanType
1933     status;
1934
1935   /*
1936     Only skip mipmaps for textures and cube maps
1937   */
1938   if (EOFBlob(image) != MagickFalse)
1939     {
1940       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
1941         image->filename);
1942       return(MagickFalse);
1943     }
1944   status=MagickTrue;
1945   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
1946       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
1947           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
1948     {
1949       register ssize_t
1950         i;
1951
1952       size_t
1953         h,
1954         w;
1955
1956       w=DIV2(dds_info->width);
1957       h=DIV2(dds_info->height);
1958
1959       /*
1960         Mipmapcount includes the main image, so start from one
1961       */
1962       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
1963       {
1964         AcquireNextImage(image_info,image,exception);
1965         if (GetNextImageInList(image) == (Image *) NULL)
1966           return(MagickFalse);
1967         image=SyncNextImageInList(image);
1968         status=SetImageExtent(image,w,h,exception);
1969         if (status == MagickFalse)
1970           break;
1971         status=decoder(image,dds_info,exception);
1972         if (status == MagickFalse)
1973           break;
1974         if ((w == 1) && (h == 1))
1975           break;
1976
1977         w=DIV2(w);
1978         h=DIV2(h);
1979       }
1980     }
1981   return(status);
1982 }
1983
1984 static MagickBooleanType ReadDXT1Pixels(Image *image,
1985   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
1986 {
1987   DDSColors
1988     colors;
1989
1990   register Quantum
1991     *q;
1992
1993   register ssize_t
1994     x;
1995
1996   size_t
1997     bits;
1998
1999   ssize_t
2000     y;
2001
2002   unsigned short
2003     c0,
2004     c1;
2005
2006   magick_unreferenced(dds_info);
2007   for (y = 0; y < (ssize_t) image->rows; y += 4)
2008   {
2009     for (x = 0; x < (ssize_t) image->columns; x += 4)
2010     {
2011       /* Get 4x4 patch of pixels to write on */
2012       q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2013         MagickMin(4,image->rows-y),exception);
2014
2015       if (q == (Quantum *) NULL)
2016         return(MagickFalse);
2017
2018       /* Read 8 bytes of data from the image */
2019       c0=ReadBlobLSBShort(image);
2020       c1=ReadBlobLSBShort(image);
2021       bits=ReadBlobLSBLong(image);
2022
2023       CalculateColors(c0,c1,&colors,MagickFalse);
2024       if (EOFBlob(image) != MagickFalse)
2025         return(MagickFalse);
2026
2027       /* Write the pixels */
2028       if (SetDXT1Pixels(image,x,y,colors,bits,q) == MagickFalse)
2029         {
2030           /* Correct alpha */
2031           SetImageAlpha(image,QuantumRange,exception);
2032           q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2033             MagickMin(4,image->rows-y),exception);
2034           if (q != (Quantum *) NULL)
2035             SetDXT1Pixels(image,x,y,colors,bits,q);
2036         }
2037       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2038         return(MagickFalse);
2039     }
2040     if (EOFBlob(image) != MagickFalse)
2041       return(MagickFalse);
2042   }
2043   return(MagickTrue);
2044 }
2045
2046 static MagickBooleanType ReadDXT1(const ImageInfo *image_info,Image *image,
2047   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2048   ExceptionInfo *exception)
2049 {
2050   if (ReadDXT1Pixels(image,dds_info,exception) == MagickFalse)
2051     return(MagickFalse);
2052
2053   if (read_mipmaps != MagickFalse)
2054     return(ReadMipmaps(image_info,image,dds_info,ReadDXT1Pixels,exception));
2055   else
2056     return(SkipDXTMipmaps(image,dds_info,8,exception));
2057 }
2058
2059 static MagickBooleanType ReadDXT3Pixels(Image *image,
2060   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2061 {
2062   DDSColors
2063     colors;
2064
2065   register Quantum
2066     *q;
2067
2068   register ssize_t
2069     i,
2070     x;
2071
2072   unsigned char
2073     alpha;
2074
2075   size_t
2076     a0,
2077     a1,
2078     bits,
2079     code;
2080
2081   ssize_t
2082     j,
2083     y;
2084
2085   unsigned short
2086     c0,
2087     c1;
2088
2089   magick_unreferenced(dds_info);
2090   for (y = 0; y < (ssize_t) image->rows; y += 4)
2091   {
2092     for (x = 0; x < (ssize_t) image->columns; x += 4)
2093     {
2094       /* Get 4x4 patch of pixels to write on */
2095       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2096                          MagickMin(4, image->rows - y),exception);
2097
2098       if (q == (Quantum *) NULL)
2099         return(MagickFalse);
2100
2101       /* Read alpha values (8 bytes) */
2102       a0 = ReadBlobLSBLong(image);
2103       a1 = ReadBlobLSBLong(image);
2104
2105       /* Read 8 bytes of data from the image */
2106       c0 = ReadBlobLSBShort(image);
2107       c1 = ReadBlobLSBShort(image);
2108       bits = ReadBlobLSBLong(image);
2109
2110       CalculateColors(c0, c1, &colors, MagickTrue);
2111
2112       if (EOFBlob(image) != MagickFalse)
2113         return(MagickFalse);
2114
2115       /* Write the pixels */
2116       for (j = 0; j < 4; j++)
2117       {
2118         for (i = 0; i < 4; i++)
2119         {
2120           if ((x + i) < (ssize_t) image->columns && (y + j) < (ssize_t) image->rows)
2121             {
2122               code = (bits >> ((4*j+i)*2)) & 0x3;
2123               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2124               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2125               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2126               /*
2127                 Extract alpha value: multiply 0..15 by 17 to get range 0..255
2128               */
2129               if (j < 2)
2130                 alpha = 17U * (unsigned char) ((a0 >> (4*(4*j+i))) & 0xf);
2131               else
2132                 alpha = 17U * (unsigned char) ((a1 >> (4*(4*(j-2)+i))) & 0xf);
2133               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2134               q+=GetPixelChannels(image);
2135             }
2136         }
2137       }
2138       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2139         return(MagickFalse);
2140     }
2141     if (EOFBlob(image) != MagickFalse)
2142       return(MagickFalse);
2143   }
2144   return(MagickTrue);
2145 }
2146
2147 static MagickBooleanType ReadDXT3(const ImageInfo *image_info,Image *image,
2148   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2149   ExceptionInfo *exception)
2150 {
2151   if (ReadDXT3Pixels(image,dds_info,exception) == MagickFalse)
2152     return(MagickFalse);
2153
2154   if (read_mipmaps != MagickFalse)
2155     return(ReadMipmaps(image_info,image,dds_info,ReadDXT3Pixels,exception));
2156   else
2157     return(SkipDXTMipmaps(image,dds_info,16,exception));
2158 }
2159
2160 static MagickBooleanType ReadDXT5Pixels(Image *image,
2161   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2162 {
2163   DDSColors
2164     colors;
2165
2166   MagickSizeType
2167     alpha_bits;
2168
2169   register Quantum
2170     *q;
2171
2172   register ssize_t
2173     i,
2174     x;
2175
2176   unsigned char
2177     a0,
2178     a1;
2179
2180   size_t
2181     alpha,
2182     bits,
2183     code,
2184     alpha_code;
2185
2186   ssize_t
2187     j,
2188     y;
2189
2190   unsigned short
2191     c0,
2192     c1;
2193
2194   magick_unreferenced(dds_info);
2195   for (y = 0; y < (ssize_t) image->rows; y += 4)
2196   {
2197     for (x = 0; x < (ssize_t) image->columns; x += 4)
2198     {
2199       /* Get 4x4 patch of pixels to write on */
2200       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2201                          MagickMin(4, image->rows - y),exception);
2202
2203       if (q == (Quantum *) NULL)
2204         return(MagickFalse);
2205
2206       /* Read alpha values (8 bytes) */
2207       a0 = (unsigned char) ReadBlobByte(image);
2208       a1 = (unsigned char) ReadBlobByte(image);
2209
2210       alpha_bits = (MagickSizeType)ReadBlobLSBLong(image);
2211       alpha_bits = alpha_bits | ((MagickSizeType)ReadBlobLSBShort(image) << 32);
2212
2213       /* Read 8 bytes of data from the image */
2214       c0 = ReadBlobLSBShort(image);
2215       c1 = ReadBlobLSBShort(image);
2216       bits = ReadBlobLSBLong(image);
2217
2218       CalculateColors(c0, c1, &colors, MagickTrue);
2219       if (EOFBlob(image) != MagickFalse)
2220         return(MagickFalse);
2221
2222       /* Write the pixels */
2223       for (j = 0; j < 4; j++)
2224       {
2225         for (i = 0; i < 4; i++)
2226         {
2227           if ((x + i) < (ssize_t) image->columns &&
2228               (y + j) < (ssize_t) image->rows)
2229             {
2230               code = (bits >> ((4*j+i)*2)) & 0x3;
2231               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2232               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2233               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2234               /* Extract alpha value */
2235               alpha_code = (size_t) (alpha_bits >> (3*(4*j+i))) & 0x7;
2236               if (alpha_code == 0)
2237                 alpha = a0;
2238               else if (alpha_code == 1)
2239                 alpha = a1;
2240               else if (a0 > a1)
2241                 alpha = ((8-alpha_code) * a0 + (alpha_code-1) * a1) / 7;
2242               else if (alpha_code == 6)
2243                 alpha = 0;
2244               else if (alpha_code == 7)
2245                 alpha = 255;
2246               else
2247                 alpha = (((6-alpha_code) * a0 + (alpha_code-1) * a1) / 5);
2248               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2249               q+=GetPixelChannels(image);
2250             }
2251         }
2252       }
2253       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2254         return(MagickFalse);
2255     }
2256     if (EOFBlob(image) != MagickFalse)
2257       return(MagickFalse);
2258   }
2259   return(MagickTrue);
2260 }
2261
2262 static MagickBooleanType ReadDXT5(const ImageInfo *image_info,Image *image,
2263   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2264   ExceptionInfo *exception)
2265 {
2266   if (ReadDXT5Pixels(image,dds_info,exception) == MagickFalse)
2267     return(MagickFalse);
2268
2269   if (read_mipmaps != MagickFalse)
2270     return(ReadMipmaps(image_info,image,dds_info,ReadDXT5Pixels,exception));
2271   else
2272     return(SkipDXTMipmaps(image,dds_info,16,exception));
2273 }
2274
2275 static MagickBooleanType ReadUncompressedRGBPixels(Image *image,
2276   DDSInfo *dds_info,ExceptionInfo *exception)
2277 {
2278   register Quantum
2279     *q;
2280
2281   ssize_t
2282     x, y;
2283
2284   unsigned short
2285     color;
2286
2287   for (y = 0; y < (ssize_t) image->rows; y++)
2288   {
2289     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2290
2291     if (q == (Quantum *) NULL)
2292       return(MagickFalse);
2293
2294     for (x = 0; x < (ssize_t) image->columns; x++)
2295     {
2296       if (dds_info->pixelformat.rgb_bitcount == 8)
2297         SetPixelGray(image,ScaleCharToQuantum(ReadBlobByte(image)),q);
2298       else if (dds_info->pixelformat.rgb_bitcount == 16)
2299         {
2300            color=ReadBlobShort(image);
2301            SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2302              (((color >> 11)/31.0)*255)),q);
2303            SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2304              ((((unsigned short)(color << 5) >> 10)/63.0)*255)),q);
2305            SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2306              ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2307         }
2308       else
2309         {
2310           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2311             ReadBlobByte(image)),q);
2312           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2313             ReadBlobByte(image)),q);
2314           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2315             ReadBlobByte(image)),q);
2316           if (dds_info->pixelformat.rgb_bitcount == 32)
2317             (void) ReadBlobByte(image);
2318         }
2319       q+=GetPixelChannels(image);
2320     }
2321     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2322       return(MagickFalse);
2323     if (EOFBlob(image) != MagickFalse)
2324       return(MagickFalse);
2325   }
2326   return(MagickTrue);
2327 }
2328
2329 static MagickBooleanType ReadUncompressedRGB(const ImageInfo *image_info,
2330   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2331   ExceptionInfo *exception)
2332 {
2333   if (dds_info->pixelformat.rgb_bitcount == 8)
2334     (void) SetImageType(image,GrayscaleType,exception);
2335   else if (dds_info->pixelformat.rgb_bitcount == 16 && !IsBitMask(
2336     dds_info->pixelformat,0xf800,0x07e0,0x001f,0x0000))
2337     ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2338       image->filename);
2339
2340   if (ReadUncompressedRGBPixels(image,dds_info,exception) == MagickFalse)
2341     return(MagickFalse);
2342
2343   if (read_mipmaps != MagickFalse)
2344     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBPixels,
2345       exception));
2346   else
2347     return(SkipRGBMipmaps(image,dds_info,3,exception));
2348 }
2349
2350 static MagickBooleanType ReadUncompressedRGBAPixels(Image *image,
2351   DDSInfo *dds_info,ExceptionInfo *exception)
2352 {
2353   register Quantum
2354     *q;
2355
2356   ssize_t
2357     alphaBits,
2358     x,
2359     y;
2360
2361   unsigned short
2362     color;
2363
2364   alphaBits=0;
2365   if (dds_info->pixelformat.rgb_bitcount == 16)
2366     {
2367       if (IsBitMask(dds_info->pixelformat,0x7c00,0x03e0,0x001f,0x8000))
2368         alphaBits=1;
2369       else if (IsBitMask(dds_info->pixelformat,0x00ff,0x00ff,0x00ff,0xff00))
2370         {
2371           alphaBits=2;
2372           (void) SetImageType(image,GrayscaleAlphaType,exception);
2373         }
2374       else if (IsBitMask(dds_info->pixelformat,0x0f00,0x00f0,0x000f,0xf000))
2375         alphaBits=4;
2376       else
2377         ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2378           image->filename);
2379     }
2380
2381   for (y = 0; y < (ssize_t) image->rows; y++)
2382   {
2383     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2384
2385     if (q == (Quantum *) NULL)
2386       return(MagickFalse);
2387
2388     for (x = 0; x < (ssize_t) image->columns; x++)
2389     {
2390       if (dds_info->pixelformat.rgb_bitcount == 16)
2391         {
2392            color=ReadBlobShort(image);
2393            if (alphaBits == 1)
2394              {
2395                SetPixelAlpha(image,(color & (1 << 15)) ? QuantumRange : 0,q);
2396                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2397                  ((((unsigned short)(color << 1) >> 11)/31.0)*255)),q);
2398                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2399                  ((((unsigned short)(color << 6) >> 11)/31.0)*255)),q);
2400                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2401                  ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2402              }
2403           else if (alphaBits == 2)
2404             {
2405                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2406                  (color >> 8)),q);
2407                SetPixelGray(image,ScaleCharToQuantum((unsigned char)color),q);
2408             }
2409           else
2410             {
2411                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2412                  (((color >> 12)/15.0)*255)),q);
2413                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2414                  ((((unsigned short)(color << 4) >> 12)/15.0)*255)),q);
2415                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2416                  ((((unsigned short)(color << 8) >> 12)/15.0)*255)),q);
2417                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2418                  ((((unsigned short)(color << 12) >> 12)/15.0)*255)),q);
2419             }
2420         }
2421       else
2422         {
2423           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2424             ReadBlobByte(image)),q);
2425           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2426             ReadBlobByte(image)),q);
2427           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2428             ReadBlobByte(image)),q);
2429           SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2430             ReadBlobByte(image)),q);
2431         }
2432       q+=GetPixelChannels(image);
2433     }
2434     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2435       return(MagickFalse);
2436     if (EOFBlob(image) != MagickFalse)
2437       return(MagickFalse);
2438   }
2439   return(MagickTrue);
2440 }
2441
2442 static MagickBooleanType ReadUncompressedRGBA(const ImageInfo *image_info,
2443   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2444   ExceptionInfo *exception)
2445 {
2446   if (ReadUncompressedRGBAPixels(image,dds_info,exception) == MagickFalse)
2447     return(MagickFalse);
2448
2449   if (read_mipmaps != MagickFalse)
2450     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBAPixels,
2451       exception));
2452   else
2453     return(SkipRGBMipmaps(image,dds_info,4,exception));
2454 }
2455 \f
2456 /*
2457 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2458 %                                                                             %
2459 %                                                                             %
2460 %                                                                             %
2461 %   R e g i s t e r D D S I m a g e                                           %
2462 %                                                                             %
2463 %                                                                             %
2464 %                                                                             %
2465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2466 %
2467 %  RegisterDDSImage() adds attributes for the DDS image format to
2468 %  the list of supported formats.  The attributes include the image format
2469 %  tag, a method to read and/or write the format, whether the format
2470 %  supports the saving of more than one frame to the same file or blob,
2471 %  whether the format supports native in-memory I/O, and a brief
2472 %  description of the format.
2473 %
2474 %  The format of the RegisterDDSImage method is:
2475 %
2476 %      RegisterDDSImage(void)
2477 %
2478 */
2479 ModuleExport size_t RegisterDDSImage(void)
2480 {
2481   MagickInfo
2482     *entry;
2483
2484   entry = AcquireMagickInfo("DDS","DDS","Microsoft DirectDraw Surface");
2485   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2486   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2487   entry->magick = (IsImageFormatHandler *) IsDDS;
2488   entry->flags|=CoderDecoderSeekableStreamFlag;
2489   (void) RegisterMagickInfo(entry);
2490   entry = AcquireMagickInfo("DDS","DXT1","Microsoft DirectDraw Surface");
2491   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2492   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2493   entry->magick = (IsImageFormatHandler *) IsDDS;
2494   entry->flags|=CoderDecoderSeekableStreamFlag;
2495   (void) RegisterMagickInfo(entry);
2496   entry = AcquireMagickInfo("DDS","DXT5","Microsoft DirectDraw Surface");
2497   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2498   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2499   entry->magick = (IsImageFormatHandler *) IsDDS;
2500   entry->flags|=CoderDecoderSeekableStreamFlag;
2501   (void) RegisterMagickInfo(entry);
2502   return(MagickImageCoderSignature);
2503 }
2504
2505 static void RemapIndices(const ssize_t *map, const unsigned char *source,
2506   unsigned char *target)
2507 {
2508   register ssize_t
2509     i;
2510
2511   for (i = 0; i < 16; i++)
2512   {
2513     if (map[i] == -1)
2514       target[i] = 3;
2515     else
2516       target[i] = source[map[i]];
2517   }
2518 }
2519
2520 /*
2521   Skip the mipmap images for compressed (DXTn) dds files
2522 */
2523 static MagickBooleanType SkipDXTMipmaps(Image *image,DDSInfo *dds_info,
2524   int texel_size,ExceptionInfo *exception)
2525 {
2526   /*
2527     Only skip mipmaps for textures and cube maps
2528   */
2529   if (EOFBlob(image) != MagickFalse)
2530     {
2531       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
2532         image->filename);
2533       return(MagickFalse);
2534     }
2535   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2536       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2537           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2538     {
2539       MagickOffsetType
2540         offset;
2541
2542       register ssize_t
2543         i;
2544
2545       size_t
2546         h,
2547         w;
2548
2549       w=DIV2(dds_info->width);
2550       h=DIV2(dds_info->height);
2551
2552       /*
2553         Mipmapcount includes the main image, so start from one
2554       */
2555       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2556       {
2557         offset=(MagickOffsetType)((w+3)/4)*((h+3)/4)*texel_size;
2558         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2559           break;
2560         w=DIV2(w);
2561         h=DIV2(h);
2562         if ((w == 1) && (h == 1))
2563           break;
2564       }
2565     }
2566   return(MagickTrue);
2567 }
2568
2569 /*
2570   Skip the mipmap images for uncompressed (RGB or RGBA) dds files
2571 */
2572 static MagickBooleanType SkipRGBMipmaps(Image *image,DDSInfo *dds_info,
2573   int pixel_size,ExceptionInfo *exception)
2574 {
2575   /*
2576     Only skip mipmaps for textures and cube maps
2577   */
2578   if (EOFBlob(image) != MagickFalse)
2579     {
2580       ThrowFileException(exception,CorruptImageError,"UnexpectedEndOfFile",
2581         image->filename);
2582       return(MagickFalse);
2583     }
2584   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2585       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2586           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2587     {
2588       MagickOffsetType
2589         offset;
2590
2591       register ssize_t
2592         i;
2593
2594       size_t
2595         h,
2596         w;
2597
2598       w=DIV2(dds_info->width);
2599       h=DIV2(dds_info->height);
2600
2601       /*
2602         Mipmapcount includes the main image, so start from one
2603       */
2604       for (i=1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2605       {
2606         offset=(MagickOffsetType)w*h*pixel_size;
2607         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2608           break;
2609         w=DIV2(w);
2610         h=DIV2(h);
2611         if ((w == 1) && (h == 1))
2612           break;
2613       }
2614     }
2615   return(MagickTrue);
2616 }
2617 \f
2618 /*
2619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2620 %                                                                             %
2621 %                                                                             %
2622 %                                                                             %
2623 %   U n r e g i s t e r D D S I m a g e                                       %
2624 %                                                                             %
2625 %                                                                             %
2626 %                                                                             %
2627 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2628 %
2629 %  UnregisterDDSImage() removes format registrations made by the
2630 %  DDS module from the list of supported formats.
2631 %
2632 %  The format of the UnregisterDDSImage method is:
2633 %
2634 %      UnregisterDDSImage(void)
2635 %
2636 */
2637 ModuleExport void UnregisterDDSImage(void)
2638 {
2639   (void) UnregisterMagickInfo("DDS");
2640   (void) UnregisterMagickInfo("DXT1");
2641   (void) UnregisterMagickInfo("DXT5");
2642 }
2643
2644 static void WriteAlphas(Image *image, const ssize_t *alphas, size_t min5,
2645   size_t max5, size_t min7, size_t max7)
2646 {
2647   register ssize_t
2648     i;
2649
2650   size_t
2651     err5,
2652     err7,
2653     j;
2654
2655   unsigned char
2656     indices5[16],
2657     indices7[16];
2658
2659   FixRange(min5,max5,5);
2660   err5 = CompressAlpha(min5,max5,5,alphas,indices5);
2661
2662   FixRange(min7,max7,7);
2663   err7 = CompressAlpha(min7,max7,7,alphas,indices7);
2664
2665   if (err7 < err5)
2666   {
2667     for (i=0; i < 16; i++)
2668     {
2669       unsigned char
2670         index;
2671
2672       index = indices7[i];
2673       if( index == 0 )
2674         indices5[i] = 1;
2675       else if (index == 1)
2676         indices5[i] = 0;
2677       else
2678         indices5[i] = 9 - index;
2679     }
2680
2681     min5 = max7;
2682     max5 = min7;
2683   }
2684
2685   (void) WriteBlobByte(image,(unsigned char) min5);
2686   (void) WriteBlobByte(image,(unsigned char) max5);
2687
2688   for(i=0; i < 2; i++)
2689   {
2690     size_t
2691       value = 0;
2692
2693     for (j=0; j < 8; j++)
2694     {
2695       size_t index = (size_t) indices5[j + i*8];
2696       value |= ( index << 3*j );
2697     }
2698
2699     for (j=0; j < 3; j++)
2700     {
2701       size_t byte = (value >> 8*j) & 0xff;
2702       (void) WriteBlobByte(image,(unsigned char) byte);
2703     }
2704   }
2705 }
2706
2707 static void WriteCompressed(Image *image, const size_t count,
2708   DDSVector4 *points, const ssize_t *map, const MagickBooleanType clusterFit)
2709 {
2710   float
2711     covariance[16];
2712
2713   DDSVector3
2714     end,
2715     principle,
2716     start;
2717
2718   DDSVector4
2719     metric;
2720
2721   unsigned char
2722     indices[16];
2723
2724   VectorInit(metric,1.0f);
2725   VectorInit3(start,0.0f);
2726   VectorInit3(end,0.0f);
2727
2728   ComputeWeightedCovariance(count,points,covariance);
2729   ComputePrincipleComponent(covariance,&principle);
2730
2731   if ((clusterFit == MagickFalse) || (count == 0))
2732     CompressRangeFit(count,points,map,principle,metric,&start,&end,indices);
2733   else
2734     CompressClusterFit(count,points,map,principle,metric,&start,&end,indices);
2735
2736   WriteIndices(image,start,end,indices);
2737 }
2738
2739 /*
2740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2741 %                                                                             %
2742 %                                                                             %
2743 %                                                                             %
2744 %   W r i t e D D S I m a g e                                                 %
2745 %                                                                             %
2746 %                                                                             %
2747 %                                                                             %
2748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2749 %
2750 %  WriteDDSImage() writes a DirectDraw Surface image file in the DXT5 format.
2751 %
2752 %  The format of the WriteBMPImage method is:
2753 %
2754 %     MagickBooleanType WriteDDSImage(const ImageInfo *image_info,Image *image)
2755 %
2756 %  A description of each parameter follows.
2757 %
2758 %    o image_info: the image info.
2759 %
2760 %    o image:  The image.
2761 %
2762 */
2763 static MagickBooleanType WriteDDSImage(const ImageInfo *image_info,
2764   Image *image, ExceptionInfo *exception)
2765 {
2766   const char
2767     *option;
2768
2769   size_t
2770     compression,
2771     columns,
2772     maxMipmaps,
2773     mipmaps,
2774     pixelFormat,
2775     rows;
2776
2777   MagickBooleanType
2778     clusterFit,
2779     fromlist,
2780     status,
2781     weightByAlpha;
2782
2783   assert(image_info != (const ImageInfo *) NULL);
2784   assert(image_info->signature == MagickCoreSignature);
2785   assert(image != (Image *) NULL);
2786   assert(image->signature == MagickCoreSignature);
2787   if (image->debug != MagickFalse)
2788     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2789   status=OpenBlob(image_info,image,WriteBinaryBlobMode,exception);
2790   if (status == MagickFalse)
2791     return(status);
2792   (void) TransformImageColorspace(image,sRGBColorspace,exception);
2793   pixelFormat=DDPF_FOURCC;
2794   compression=FOURCC_DXT5;
2795
2796   if (image->alpha_trait == UndefinedPixelTrait)
2797     compression=FOURCC_DXT1;
2798
2799   if (LocaleCompare(image_info->magick,"dxt1") == 0)
2800     compression=FOURCC_DXT1;
2801
2802   option=GetImageOption(image_info,"dds:compression");
2803   if (option != (char *) NULL)
2804     {
2805        if (LocaleCompare(option,"dxt1") == 0)
2806          compression=FOURCC_DXT1;
2807        if (LocaleCompare(option,"none") == 0)
2808          pixelFormat=DDPF_RGB;
2809     }
2810
2811   clusterFit=MagickFalse;
2812   weightByAlpha=MagickFalse;
2813
2814   if (pixelFormat == DDPF_FOURCC)
2815     {
2816       option=GetImageOption(image_info,"dds:cluster-fit");
2817       if (IsStringTrue(option) != MagickFalse)
2818         {
2819           clusterFit=MagickTrue;
2820           if (compression != FOURCC_DXT1)
2821             {
2822               option=GetImageOption(image_info,"dds:weight-by-alpha");
2823               if (IsStringTrue(option) != MagickFalse)
2824                 weightByAlpha=MagickTrue;
2825             }
2826         }
2827     }
2828
2829   mipmaps=0;
2830   fromlist=MagickFalse;
2831   option=GetImageOption(image_info,"dds:mipmaps");
2832   if (option != (char *) NULL)
2833     {
2834       if (LocaleNCompare(option,"fromlist",8) == 0)
2835         {
2836           Image
2837             *next;
2838
2839           fromlist=MagickTrue;
2840           next=image->next;
2841           while(next != (Image *) NULL)
2842           {
2843             mipmaps++;
2844             next=next->next;
2845           }
2846         }
2847     }
2848
2849   if ((mipmaps == 0) &&
2850       ((image->columns & (image->columns - 1)) == 0) &&
2851       ((image->rows & (image->rows - 1)) == 0))
2852     {
2853       maxMipmaps=SIZE_MAX;
2854       if (option != (char *) NULL)
2855         maxMipmaps=StringToUnsignedLong(option);
2856
2857       if (maxMipmaps != 0)
2858         {
2859           columns=image->columns;
2860           rows=image->rows;
2861           while ((columns != 1 || rows != 1) && mipmaps != maxMipmaps)
2862           {
2863             columns=DIV2(columns);
2864             rows=DIV2(rows);
2865             mipmaps++;
2866           }
2867         }
2868     }
2869
2870   WriteDDSInfo(image,pixelFormat,compression,mipmaps);
2871
2872   WriteImageData(image,pixelFormat,compression,clusterFit,weightByAlpha,
2873     exception);
2874
2875   if ((mipmaps > 0) && (WriteMipmaps(image,image_info,pixelFormat,compression,
2876        mipmaps,fromlist,clusterFit,weightByAlpha,exception) == MagickFalse))
2877     return(MagickFalse);
2878
2879   (void) CloseBlob(image);
2880   return(MagickTrue);
2881 }
2882
2883 static void WriteDDSInfo(Image *image, const size_t pixelFormat,
2884   const size_t compression, const size_t mipmaps)
2885 {
2886   char
2887     software[MagickPathExtent];
2888
2889   register ssize_t
2890     i;
2891
2892   unsigned int
2893     format,
2894     caps,
2895     flags;
2896
2897   flags=(unsigned int) (DDSD_CAPS | DDSD_WIDTH | DDSD_HEIGHT |
2898     DDSD_PIXELFORMAT);
2899   caps=(unsigned int) DDSCAPS_TEXTURE;
2900   format=(unsigned int) pixelFormat;
2901
2902   if (format == DDPF_FOURCC)
2903       flags=flags | DDSD_LINEARSIZE;
2904   else
2905       flags=flags | DDSD_PITCH;
2906
2907   if (mipmaps > 0)
2908     {
2909       flags=flags | (unsigned int) DDSD_MIPMAPCOUNT;
2910       caps=caps | (unsigned int) (DDSCAPS_MIPMAP | DDSCAPS_COMPLEX);
2911     }
2912
2913   if (format != DDPF_FOURCC && image->alpha_trait != UndefinedPixelTrait)
2914     format=format | DDPF_ALPHAPIXELS;
2915
2916   (void) WriteBlob(image,4,(unsigned char *) "DDS ");
2917   (void) WriteBlobLSBLong(image,124);
2918   (void) WriteBlobLSBLong(image,flags);
2919   (void) WriteBlobLSBLong(image,(unsigned int) image->rows);
2920   (void) WriteBlobLSBLong(image,(unsigned int) image->columns);
2921
2922   if (pixelFormat == DDPF_FOURCC)
2923     {
2924       /* Compressed DDS requires linear compressed size of first image */
2925       if (compression == FOURCC_DXT1)
2926         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2927           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*8));
2928       else /* DXT5 */
2929         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2930           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*16));
2931     }
2932   else
2933     {
2934       /* Uncompressed DDS requires byte pitch of first image */
2935       if (image->alpha_trait != UndefinedPixelTrait)
2936         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 4));
2937       else
2938         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 3));
2939     }
2940
2941   (void) WriteBlobLSBLong(image,0x00);
2942   (void) WriteBlobLSBLong(image,(unsigned int) mipmaps+1);
2943   (void) memset(software,0,sizeof(software));
2944   (void) CopyMagickString(software,"IMAGEMAGICK",MagickPathExtent);
2945   (void) WriteBlob(image,44,(unsigned char *) software);
2946
2947   (void) WriteBlobLSBLong(image,32);
2948   (void) WriteBlobLSBLong(image,format);
2949
2950   if (pixelFormat == DDPF_FOURCC)
2951     {
2952       (void) WriteBlobLSBLong(image,(unsigned int) compression);
2953       for(i=0;i < 5;i++)  /* bitcount / masks */
2954         (void) WriteBlobLSBLong(image,0x00);
2955     }
2956   else
2957     {
2958       (void) WriteBlobLSBLong(image,0x00);
2959       if (image->alpha_trait != UndefinedPixelTrait)
2960         {
2961           (void) WriteBlobLSBLong(image,32);
2962           (void) WriteBlobLSBLong(image,0xff0000);
2963           (void) WriteBlobLSBLong(image,0xff00);
2964           (void) WriteBlobLSBLong(image,0xff);
2965           (void) WriteBlobLSBLong(image,0xff000000);
2966         }
2967       else
2968         {
2969           (void) WriteBlobLSBLong(image,24);
2970           (void) WriteBlobLSBLong(image,0xff0000);
2971           (void) WriteBlobLSBLong(image,0xff00);
2972           (void) WriteBlobLSBLong(image,0xff);
2973           (void) WriteBlobLSBLong(image,0x00);
2974         }
2975     }
2976
2977   (void) WriteBlobLSBLong(image,caps);
2978   for(i=0;i < 4;i++)   /* ddscaps2 + reserved region */
2979     (void) WriteBlobLSBLong(image,0x00);
2980 }
2981
2982 static void WriteFourCC(Image *image, const size_t compression,
2983   const MagickBooleanType clusterFit, const MagickBooleanType weightByAlpha,
2984   ExceptionInfo *exception)
2985 {
2986   register ssize_t
2987     x;
2988
2989   ssize_t
2990     i,
2991     y,
2992     bx,
2993     by;
2994
2995   register const Quantum
2996     *p;
2997
2998   for (y=0; y < (ssize_t) image->rows; y+=4)
2999   {
3000     for (x=0; x < (ssize_t) image->columns; x+=4)
3001     {
3002       MagickBooleanType
3003         match;
3004
3005       DDSVector4
3006         point,
3007         points[16];
3008
3009       size_t
3010         count = 0,
3011         max5 = 0,
3012         max7 = 0,
3013         min5 = 255,
3014         min7 = 255,
3015         columns = 4,
3016         rows = 4;
3017
3018       ssize_t
3019         alphas[16],
3020         map[16];
3021
3022       unsigned char
3023         alpha;
3024
3025       if (x + columns >= image->columns)
3026         columns = image->columns - x;
3027
3028       if (y + rows >= image->rows)
3029         rows = image->rows - y;
3030
3031       p=GetVirtualPixels(image,x,y,columns,rows,exception);
3032       if (p == (const Quantum *) NULL)
3033         break;
3034
3035       for (i=0; i<16; i++)
3036       {
3037         map[i] = -1;
3038         alphas[i] = -1;
3039       }
3040
3041       for (by=0; by < (ssize_t) rows; by++)
3042       {
3043         for (bx=0; bx < (ssize_t) columns; bx++)
3044         {
3045           if (compression == FOURCC_DXT5)
3046             alpha = ScaleQuantumToChar(GetPixelAlpha(image,p));
3047           else
3048             alpha = 255;
3049
3050           if (compression == FOURCC_DXT5)
3051             {
3052               if (alpha < min7)
3053                 min7 = alpha;
3054               if (alpha > max7)
3055                 max7 = alpha;
3056               if (alpha != 0 && alpha < min5)
3057                 min5 = alpha;
3058               if (alpha != 255 && alpha > max5)
3059                 max5 = alpha;
3060             }
3061
3062           alphas[4*by + bx] = (size_t)alpha;
3063
3064           point.x = (float)ScaleQuantumToChar(GetPixelRed(image,p)) / 255.0f;
3065           point.y = (float)ScaleQuantumToChar(GetPixelGreen(image,p)) / 255.0f;
3066           point.z = (float)ScaleQuantumToChar(GetPixelBlue(image,p)) / 255.0f;
3067           point.w = weightByAlpha ? (float)(alpha + 1) / 256.0f : 1.0f;
3068           p+=GetPixelChannels(image);
3069
3070           match = MagickFalse;
3071           for (i=0; i < (ssize_t) count; i++)
3072           {
3073             if ((points[i].x == point.x) &&
3074                 (points[i].y == point.y) &&
3075                 (points[i].z == point.z) &&
3076                 (alpha       >= 128 || compression == FOURCC_DXT5))
3077               {
3078                 points[i].w += point.w;
3079                 map[4*by + bx] = i;
3080                 match = MagickTrue;
3081                 break;
3082               }
3083           }
3084
3085           if (match != MagickFalse)
3086             continue;
3087
3088           points[count].x = point.x;
3089           points[count].y = point.y;
3090           points[count].z = point.z;
3091           points[count].w = point.w;
3092           map[4*by + bx] = count;
3093           count++;
3094         }
3095       }
3096
3097       for (i=0; i < (ssize_t) count; i++)
3098         points[i].w = sqrt(points[i].w);
3099
3100       if (compression == FOURCC_DXT5)
3101         WriteAlphas(image,alphas,min5,max5,min7,max7);
3102
3103       if (count == 1)
3104         WriteSingleColorFit(image,points,map);
3105       else
3106         WriteCompressed(image,count,points,map,clusterFit);
3107     }
3108   }
3109 }
3110
3111 static void WriteImageData(Image *image, const size_t pixelFormat,
3112   const size_t compression,const MagickBooleanType clusterFit,
3113   const MagickBooleanType weightByAlpha, ExceptionInfo *exception)
3114 {
3115   if (pixelFormat == DDPF_FOURCC)
3116     WriteFourCC(image,compression,clusterFit,weightByAlpha,exception);
3117   else
3118     WriteUncompressed(image,exception);
3119 }
3120
3121 static inline size_t ClampToLimit(const float value, const size_t limit)
3122 {
3123   size_t
3124     result = (int) (value + 0.5f);
3125
3126   if (result < 0.0f)
3127     return(0);
3128   if (result > limit)
3129     return(limit);
3130   return result;
3131 }
3132
3133 static inline size_t ColorTo565(const DDSVector3 point)
3134 {
3135   size_t r = ClampToLimit(31.0f*point.x,31);
3136   size_t g = ClampToLimit(63.0f*point.y,63);
3137   size_t b = ClampToLimit(31.0f*point.z,31);
3138
3139   return (r << 11) | (g << 5) | b;
3140 }
3141
3142 static void WriteIndices(Image *image, const DDSVector3 start,
3143   const DDSVector3 end, unsigned char *indices)
3144 {
3145   register ssize_t
3146     i;
3147
3148   size_t
3149     a,
3150     b;
3151
3152   unsigned char
3153     remapped[16];
3154
3155   const unsigned char
3156     *ind;
3157
3158   a = ColorTo565(start);
3159   b = ColorTo565(end);
3160
3161   for (i=0; i<16; i++)
3162   {
3163     if( a < b )
3164       remapped[i] = (indices[i] ^ 0x1) & 0x3;
3165     else if( a == b )
3166       remapped[i] = 0;
3167     else
3168       remapped[i] = indices[i];
3169   }
3170
3171   if( a < b )
3172     Swap(a,b);
3173
3174   (void) WriteBlobByte(image,(unsigned char) (a & 0xff));
3175   (void) WriteBlobByte(image,(unsigned char) (a >> 8));
3176   (void) WriteBlobByte(image,(unsigned char) (b & 0xff));
3177   (void) WriteBlobByte(image,(unsigned char) (b >> 8));
3178
3179   for (i=0; i<4; i++)
3180   {
3181      ind = remapped + 4*i;
3182      (void) WriteBlobByte(image,ind[0] | (ind[1] << 2) | (ind[2] << 4) |
3183        (ind[3] << 6));
3184   }
3185 }
3186
3187 static MagickBooleanType WriteMipmaps(Image *image,const ImageInfo *image_info,
3188   const size_t pixelFormat,const size_t compression,const size_t mipmaps,
3189   const MagickBooleanType fromlist,const MagickBooleanType clusterFit,
3190   const MagickBooleanType weightByAlpha,ExceptionInfo *exception)
3191 {
3192   const char
3193     *option;
3194
3195   Image
3196     *mipmap_image,
3197     *resize_image;
3198
3199   MagickBooleanType
3200     fast_mipmaps,
3201     status;
3202
3203   register ssize_t
3204     i;
3205
3206   size_t
3207     columns,
3208     rows;
3209
3210   columns=DIV2(image->columns);
3211   rows=DIV2(image->rows);
3212
3213   option=GetImageOption(image_info,"dds:fast-mipmaps");
3214   fast_mipmaps=IsStringTrue(option);
3215   mipmap_image=image;
3216   resize_image=image;
3217   status=MagickTrue;
3218   for (i=0; i < (ssize_t) mipmaps; i++)
3219   {
3220     if (fromlist == MagickFalse)
3221       {
3222         mipmap_image=ResizeImage(resize_image,columns,rows,TriangleFilter,
3223           exception);
3224
3225         if (mipmap_image == (Image *) NULL)
3226           {
3227             status=MagickFalse;
3228             break;
3229           }
3230       }
3231     else
3232       {
3233         mipmap_image=mipmap_image->next;
3234         if ((mipmap_image->columns != columns) || (mipmap_image->rows != rows))
3235           ThrowBinaryException(CoderError,"ImageColumnOrRowSizeIsNotSupported",
3236             image->filename);
3237       }
3238
3239     DestroyBlob(mipmap_image);
3240     mipmap_image->blob=ReferenceBlob(image->blob);
3241
3242     WriteImageData(mipmap_image,pixelFormat,compression,weightByAlpha,
3243       clusterFit,exception);
3244
3245     if (fromlist == MagickFalse)
3246       {
3247         if (fast_mipmaps == MagickFalse)
3248           mipmap_image=DestroyImage(mipmap_image);
3249         else
3250           {
3251             if (resize_image != image)
3252               resize_image=DestroyImage(resize_image);
3253             resize_image=mipmap_image;
3254           }
3255       }
3256
3257     columns=DIV2(columns);
3258     rows=DIV2(rows);
3259   }
3260
3261   if (resize_image != image)
3262     resize_image=DestroyImage(resize_image);
3263
3264   return(status);
3265 }
3266
3267 static void WriteSingleColorFit(Image *image, const DDSVector4 *points,
3268   const ssize_t *map)
3269 {
3270   DDSVector3
3271     start,
3272     end;
3273
3274   register ssize_t
3275     i;
3276
3277   unsigned char
3278     color[3],
3279     index,
3280     indexes[16],
3281     indices[16];
3282
3283   color[0] = (unsigned char) ClampToLimit(255.0f*points->x,255);
3284   color[1] = (unsigned char) ClampToLimit(255.0f*points->y,255);
3285   color[2] = (unsigned char) ClampToLimit(255.0f*points->z,255);
3286
3287   index=0;
3288   ComputeEndPoints(DDS_LOOKUP,color,&start,&end,&index);
3289
3290   for (i=0; i< 16; i++)
3291     indexes[i]=index;
3292   RemapIndices(map,indexes,indices);
3293   WriteIndices(image,start,end,indices);
3294 }
3295
3296 static void WriteUncompressed(Image *image, ExceptionInfo *exception)
3297 {
3298   register const Quantum
3299     *p;
3300
3301   register ssize_t
3302     x;
3303
3304   ssize_t
3305     y;
3306
3307   for (y=0; y < (ssize_t) image->rows; y++)
3308   {
3309     p=GetVirtualPixels(image,0,y,image->columns,1,exception);
3310     if (p == (const Quantum *) NULL)
3311       break;
3312
3313     for (x=0; x < (ssize_t) image->columns; x++)
3314     {
3315       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelBlue(image,p)));
3316       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelGreen(image,p)));
3317       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelRed(image,p)));
3318       if (image->alpha_trait != UndefinedPixelTrait)
3319         (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelAlpha(image,p)));
3320       p+=GetPixelChannels(image);
3321     }
3322   }
3323 }