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-2017 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://www.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 = 1.0f / 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 < 1)
1796     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1797
1798   option=GetImageOption(image_info,"dds:skip-mipmaps");
1799   if (IsStringFalse(option) != MagickFalse)
1800     read_mipmaps=MagickTrue;
1801
1802   for (n = 0; n < num_images; n++)
1803   {
1804     if (n != 0)
1805       {
1806         /* Start a new image */
1807         if (EOFBlob(image) != MagickFalse)
1808           ThrowReaderException(CorruptImageError,"UnexpectedEndOfFile");
1809         AcquireNextImage(image_info,image,exception);
1810         if (GetNextImageInList(image) == (Image *) NULL)
1811           return(DestroyImageList(image));
1812         image=SyncNextImageInList(image);
1813       }
1814
1815     image->alpha_trait=alpha_trait;
1816     image->compression=compression;
1817     image->columns=dds_info.width;
1818     image->rows=dds_info.height;
1819     image->storage_class=DirectClass;
1820     image->endian=LSBEndian;
1821     image->depth=8;
1822     if (image_info->ping != MagickFalse)
1823       {
1824         (void) CloseBlob(image);
1825         return(GetFirstImageInList(image));
1826       }
1827     status=SetImageExtent(image,image->columns,image->rows,exception);
1828     if (status == MagickFalse)
1829       return(DestroyImageList(image));
1830     status=(decoder)(image_info,image,&dds_info,read_mipmaps,exception);
1831     if (status == MagickFalse)
1832       {
1833         (void) CloseBlob(image);
1834         return(GetFirstImageInList(image));
1835       }
1836   }
1837   (void) CloseBlob(image);
1838   return(GetFirstImageInList(image));
1839 }
1840
1841 static MagickBooleanType ReadDDSInfo(Image *image, DDSInfo *dds_info)
1842 {
1843   size_t
1844     hdr_size,
1845     required;
1846
1847   /* Seek to start of header */
1848   (void) SeekBlob(image, 4, SEEK_SET);
1849
1850   /* Check header field */
1851   hdr_size = ReadBlobLSBLong(image);
1852   if (hdr_size != 124)
1853     return MagickFalse;
1854
1855   /* Fill in DDS info struct */
1856   dds_info->flags = ReadBlobLSBLong(image);
1857
1858   /* Check required flags */
1859   required=(size_t) (DDSD_WIDTH | DDSD_HEIGHT | DDSD_PIXELFORMAT);
1860   if ((dds_info->flags & required) != required)
1861     return MagickFalse;
1862
1863   dds_info->height = ReadBlobLSBLong(image);
1864   dds_info->width = ReadBlobLSBLong(image);
1865   dds_info->pitchOrLinearSize = ReadBlobLSBLong(image);
1866   dds_info->depth = ReadBlobLSBLong(image);
1867   dds_info->mipmapcount = ReadBlobLSBLong(image);
1868
1869   (void) SeekBlob(image, 44, SEEK_CUR);   /* reserved region of 11 DWORDs */
1870
1871   /* Read pixel format structure */
1872   hdr_size = ReadBlobLSBLong(image);
1873   if (hdr_size != 32)
1874     return MagickFalse;
1875
1876   dds_info->pixelformat.flags = ReadBlobLSBLong(image);
1877   dds_info->pixelformat.fourcc = ReadBlobLSBLong(image);
1878   dds_info->pixelformat.rgb_bitcount = ReadBlobLSBLong(image);
1879   dds_info->pixelformat.r_bitmask = ReadBlobLSBLong(image);
1880   dds_info->pixelformat.g_bitmask = ReadBlobLSBLong(image);
1881   dds_info->pixelformat.b_bitmask = ReadBlobLSBLong(image);
1882   dds_info->pixelformat.alpha_bitmask = ReadBlobLSBLong(image);
1883
1884   dds_info->ddscaps1 = ReadBlobLSBLong(image);
1885   dds_info->ddscaps2 = ReadBlobLSBLong(image);
1886   (void) SeekBlob(image, 12, SEEK_CUR); /* 3 reserved DWORDs */
1887
1888   return MagickTrue;
1889 }
1890
1891 static MagickBooleanType SetDXT1Pixels(Image *image,ssize_t x,ssize_t y,
1892   DDSColors colors,size_t bits,Quantum *q)
1893 {
1894   register ssize_t
1895     i;
1896
1897   ssize_t
1898     j;
1899
1900   unsigned char
1901     code;
1902
1903   for (j = 0; j < 4; j++)
1904   {
1905     for (i = 0; i < 4; i++)
1906     {
1907       if ((x + i) < (ssize_t) image->columns &&
1908           (y + j) < (ssize_t) image->rows)
1909         {
1910           code=(unsigned char) ((bits >> ((j*4+i)*2)) & 0x3);
1911           SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
1912           SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
1913           SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
1914           SetPixelOpacity(image,ScaleCharToQuantum(colors.a[code]),q);
1915           if ((colors.a[code] != 0) &&
1916               (image->alpha_trait == UndefinedPixelTrait))
1917             return(MagickFalse);
1918           q+=GetPixelChannels(image);
1919         }
1920     }
1921   }
1922   return(MagickTrue);
1923 }
1924
1925 static MagickBooleanType ReadMipmaps(const ImageInfo *image_info,Image *image,
1926   DDSInfo *dds_info,DDSPixelDecoder decoder,ExceptionInfo *exception)
1927 {
1928   MagickBooleanType
1929     status;
1930
1931   /*
1932     Only skip mipmaps for textures and cube maps
1933   */
1934   if (EOFBlob(image) != MagickFalse)
1935     {
1936       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
1937         image->filename);
1938       return(MagickFalse);
1939     }
1940   status=MagickTrue;
1941   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
1942       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
1943           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
1944     {
1945       register ssize_t
1946         i;
1947
1948       size_t
1949         h,
1950         w;
1951
1952       w=DIV2(dds_info->width);
1953       h=DIV2(dds_info->height);
1954
1955       /*
1956         Mipmapcount includes the main image, so start from one
1957       */
1958       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
1959       {
1960         AcquireNextImage(image_info,image,exception);
1961         if (GetNextImageInList(image) == (Image *) NULL)
1962           return(MagickFalse);
1963         image=SyncNextImageInList(image);
1964         status=SetImageExtent(image,w,h,exception);
1965         if (status == MagickFalse)
1966           break;
1967         status=decoder(image,dds_info,exception);
1968         if (status == MagickFalse)
1969           break;
1970
1971         w=DIV2(w);
1972         h=DIV2(h);
1973       }
1974     }
1975   return(status);
1976 }
1977
1978 static MagickBooleanType ReadDXT1Pixels(Image *image,
1979   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
1980 {
1981   DDSColors
1982     colors;
1983
1984   register Quantum
1985     *q;
1986
1987   register ssize_t
1988     x;
1989
1990   size_t
1991     bits;
1992
1993   ssize_t
1994     y;
1995
1996   unsigned short
1997     c0,
1998     c1;
1999
2000   magick_unreferenced(dds_info);
2001   for (y = 0; y < (ssize_t) image->rows; y += 4)
2002   {
2003     for (x = 0; x < (ssize_t) image->columns; x += 4)
2004     {
2005       /* Get 4x4 patch of pixels to write on */
2006       q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2007         MagickMin(4,image->rows-y),exception);
2008
2009       if (q == (Quantum *) NULL)
2010         return(MagickFalse);
2011
2012       /* Read 8 bytes of data from the image */
2013       c0=ReadBlobLSBShort(image);
2014       c1=ReadBlobLSBShort(image);
2015       bits=ReadBlobLSBLong(image);
2016
2017       CalculateColors(c0,c1,&colors,MagickFalse);
2018       if (EOFBlob(image) != MagickFalse)
2019         return(MagickFalse);
2020
2021       /* Write the pixels */
2022       if (SetDXT1Pixels(image,x,y,colors,bits,q) == MagickFalse)
2023         {
2024           /* Correct alpha */
2025           SetImageAlpha(image,QuantumRange,exception);
2026           q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2027             MagickMin(4,image->rows-y),exception);
2028           if (q != (Quantum *) NULL)
2029             SetDXT1Pixels(image,x,y,colors,bits,q);
2030         }
2031       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2032         return(MagickFalse);
2033     }
2034     if (EOFBlob(image) != MagickFalse)
2035       return(MagickFalse);
2036   }
2037   return(MagickTrue);
2038 }
2039
2040 static MagickBooleanType ReadDXT1(const ImageInfo *image_info,Image *image,
2041   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2042   ExceptionInfo *exception)
2043 {
2044   if (ReadDXT1Pixels(image,dds_info,exception) == MagickFalse)
2045     return(MagickFalse);
2046
2047   if (read_mipmaps != MagickFalse)
2048     return(ReadMipmaps(image_info,image,dds_info,ReadDXT1Pixels,exception));
2049   else
2050     return(SkipDXTMipmaps(image,dds_info,8,exception));
2051 }
2052
2053 static MagickBooleanType ReadDXT3Pixels(Image *image,
2054   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2055 {
2056   DDSColors
2057     colors;
2058
2059   register Quantum
2060     *q;
2061
2062   register ssize_t
2063     i,
2064     x;
2065
2066   unsigned char
2067     alpha;
2068
2069   size_t
2070     a0,
2071     a1,
2072     bits,
2073     code;
2074
2075   ssize_t
2076     j,
2077     y;
2078
2079   unsigned short
2080     c0,
2081     c1;
2082
2083   magick_unreferenced(dds_info);
2084   for (y = 0; y < (ssize_t) image->rows; y += 4)
2085   {
2086     for (x = 0; x < (ssize_t) image->columns; x += 4)
2087     {
2088       /* Get 4x4 patch of pixels to write on */
2089       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2090                          MagickMin(4, image->rows - y),exception);
2091
2092       if (q == (Quantum *) NULL)
2093         return(MagickFalse);
2094
2095       /* Read alpha values (8 bytes) */
2096       a0 = ReadBlobLSBLong(image);
2097       a1 = ReadBlobLSBLong(image);
2098
2099       /* Read 8 bytes of data from the image */
2100       c0 = ReadBlobLSBShort(image);
2101       c1 = ReadBlobLSBShort(image);
2102       bits = ReadBlobLSBLong(image);
2103
2104       CalculateColors(c0, c1, &colors, MagickTrue);
2105
2106       if (EOFBlob(image) != MagickFalse)
2107         return(MagickFalse);
2108
2109       /* Write the pixels */
2110       for (j = 0; j < 4; j++)
2111       {
2112         for (i = 0; i < 4; i++)
2113         {
2114           if ((x + i) < (ssize_t) image->rows && (y + j) < (ssize_t) image->columns)
2115             {
2116               code = (bits >> ((4*j+i)*2)) & 0x3;
2117               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2118               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2119               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2120               /*
2121                 Extract alpha value: multiply 0..15 by 17 to get range 0..255
2122               */
2123               if (j < 2)
2124                 alpha = 17U * (unsigned char) ((a0 >> (4*(4*j+i))) & 0xf);
2125               else
2126                 alpha = 17U * (unsigned char) ((a1 >> (4*(4*(j-2)+i))) & 0xf);
2127               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2128               q+=GetPixelChannels(image);
2129             }
2130         }
2131       }
2132       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2133         return(MagickFalse);
2134     }
2135     if (EOFBlob(image) != MagickFalse)
2136       return(MagickFalse);
2137   }
2138   return(MagickTrue);
2139 }
2140
2141 static MagickBooleanType ReadDXT3(const ImageInfo *image_info,Image *image,
2142   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2143   ExceptionInfo *exception)
2144 {
2145   if (ReadDXT3Pixels(image,dds_info,exception) == MagickFalse)
2146     return(MagickFalse);
2147
2148   if (read_mipmaps != MagickFalse)
2149     return(ReadMipmaps(image_info,image,dds_info,ReadDXT3Pixels,exception));
2150   else
2151     return(SkipDXTMipmaps(image,dds_info,16,exception));
2152 }
2153
2154 static MagickBooleanType ReadDXT5Pixels(Image *image,
2155   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2156 {
2157   DDSColors
2158     colors;
2159
2160   MagickSizeType
2161     alpha_bits;
2162
2163   register Quantum
2164     *q;
2165
2166   register ssize_t
2167     i,
2168     x;
2169
2170   unsigned char
2171     a0,
2172     a1;
2173
2174   size_t
2175     alpha,
2176     bits,
2177     code,
2178     alpha_code;
2179
2180   ssize_t
2181     j,
2182     y;
2183
2184   unsigned short
2185     c0,
2186     c1;
2187
2188   magick_unreferenced(dds_info);
2189   for (y = 0; y < (ssize_t) image->rows; y += 4)
2190   {
2191     for (x = 0; x < (ssize_t) image->columns; x += 4)
2192     {
2193       /* Get 4x4 patch of pixels to write on */
2194       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2195                          MagickMin(4, image->rows - y),exception);
2196
2197       if (q == (Quantum *) NULL)
2198         return(MagickFalse);
2199
2200       /* Read alpha values (8 bytes) */
2201       a0 = (unsigned char) ReadBlobByte(image);
2202       a1 = (unsigned char) ReadBlobByte(image);
2203
2204       alpha_bits = (MagickSizeType)ReadBlobLSBLong(image);
2205       alpha_bits = alpha_bits | ((MagickSizeType)ReadBlobLSBShort(image) << 32);
2206
2207       /* Read 8 bytes of data from the image */
2208       c0 = ReadBlobLSBShort(image);
2209       c1 = ReadBlobLSBShort(image);
2210       bits = ReadBlobLSBLong(image);
2211
2212       CalculateColors(c0, c1, &colors, MagickTrue);
2213       if (EOFBlob(image) != MagickFalse)
2214         return(MagickFalse);
2215
2216       /* Write the pixels */
2217       for (j = 0; j < 4; j++)
2218       {
2219         for (i = 0; i < 4; i++)
2220         {
2221           if ((x + i) < (ssize_t) image->columns &&
2222               (y + j) < (ssize_t) image->rows)
2223             {
2224               code = (bits >> ((4*j+i)*2)) & 0x3;
2225               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2226               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2227               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2228               /* Extract alpha value */
2229               alpha_code = (size_t) (alpha_bits >> (3*(4*j+i))) & 0x7;
2230               if (alpha_code == 0)
2231                 alpha = a0;
2232               else if (alpha_code == 1)
2233                 alpha = a1;
2234               else if (a0 > a1)
2235                 alpha = ((8-alpha_code) * a0 + (alpha_code-1) * a1) / 7;
2236               else if (alpha_code == 6)
2237                 alpha = 0;
2238               else if (alpha_code == 7)
2239                 alpha = 255;
2240               else
2241                 alpha = (((6-alpha_code) * a0 + (alpha_code-1) * a1) / 5);
2242               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2243               q+=GetPixelChannels(image);
2244             }
2245         }
2246       }
2247       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2248         return(MagickFalse);
2249     }
2250     if (EOFBlob(image) != MagickFalse)
2251       return(MagickFalse);
2252   }
2253   return(MagickTrue);
2254 }
2255
2256 static MagickBooleanType ReadDXT5(const ImageInfo *image_info,Image *image,
2257   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2258   ExceptionInfo *exception)
2259 {
2260   if (ReadDXT5Pixels(image,dds_info,exception) == MagickFalse)
2261     return(MagickFalse);
2262
2263   if (read_mipmaps != MagickFalse)
2264     return(ReadMipmaps(image_info,image,dds_info,ReadDXT5Pixels,exception));
2265   else
2266     return(SkipDXTMipmaps(image,dds_info,16,exception));
2267 }
2268
2269 static MagickBooleanType ReadUncompressedRGBPixels(Image *image,
2270   DDSInfo *dds_info,ExceptionInfo *exception)
2271 {
2272   register Quantum
2273     *q;
2274
2275   ssize_t
2276     x, y;
2277
2278   unsigned short
2279     color;
2280
2281   for (y = 0; y < (ssize_t) image->rows; y++)
2282   {
2283     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2284
2285     if (q == (Quantum *) NULL)
2286       return(MagickFalse);
2287
2288     for (x = 0; x < (ssize_t) image->columns; x++)
2289     {
2290       if (dds_info->pixelformat.rgb_bitcount == 8)
2291         SetPixelGray(image,ScaleCharToQuantum(ReadBlobByte(image)),q);
2292       else if (dds_info->pixelformat.rgb_bitcount == 16)
2293         {
2294            color=ReadBlobShort(image);
2295            SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2296              (((color >> 11)/31.0)*255)),q);
2297            SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2298              ((((unsigned short)(color << 5) >> 10)/63.0)*255)),q);
2299            SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2300              ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2301         }
2302       else
2303         {
2304           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2305             ReadBlobByte(image)),q);
2306           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2307             ReadBlobByte(image)),q);
2308           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2309             ReadBlobByte(image)),q);
2310           if (dds_info->pixelformat.rgb_bitcount == 32)
2311             (void) ReadBlobByte(image);
2312         }
2313       q+=GetPixelChannels(image);
2314     }
2315     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2316       return(MagickFalse);
2317     if (EOFBlob(image) != MagickFalse)
2318       return(MagickFalse);
2319   }
2320   return(MagickTrue);
2321 }
2322
2323 static MagickBooleanType ReadUncompressedRGB(const ImageInfo *image_info,
2324   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2325   ExceptionInfo *exception)
2326 {
2327   if (dds_info->pixelformat.rgb_bitcount == 8)
2328     (void) SetImageType(image,GrayscaleType,exception);
2329   else if (dds_info->pixelformat.rgb_bitcount == 16 && !IsBitMask(
2330     dds_info->pixelformat,0xf800,0x07e0,0x001f,0x0000))
2331     ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2332       image->filename);
2333
2334   if (ReadUncompressedRGBPixels(image,dds_info,exception) == MagickFalse)
2335     return(MagickFalse);
2336
2337   if (read_mipmaps != MagickFalse)
2338     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBPixels,
2339       exception));
2340   else
2341     return(SkipRGBMipmaps(image,dds_info,3,exception));
2342 }
2343
2344 static MagickBooleanType ReadUncompressedRGBAPixels(Image *image,
2345   DDSInfo *dds_info,ExceptionInfo *exception)
2346 {
2347   register Quantum
2348     *q;
2349
2350   ssize_t
2351     alphaBits,
2352     x,
2353     y;
2354
2355   unsigned short
2356     color;
2357
2358   alphaBits=0;
2359   if (dds_info->pixelformat.rgb_bitcount == 16)
2360     {
2361       if (IsBitMask(dds_info->pixelformat,0x7c00,0x03e0,0x001f,0x8000))
2362         alphaBits=1;
2363       else if (IsBitMask(dds_info->pixelformat,0x00ff,0x00ff,0x00ff,0xff00))
2364         {
2365           alphaBits=2;
2366           (void) SetImageType(image,GrayscaleAlphaType,exception);
2367         }
2368       else if (IsBitMask(dds_info->pixelformat,0x0f00,0x00f0,0x000f,0xf000))
2369         alphaBits=4;
2370       else
2371         ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2372           image->filename);
2373     }
2374
2375   for (y = 0; y < (ssize_t) image->rows; y++)
2376   {
2377     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2378
2379     if (q == (Quantum *) NULL)
2380       return(MagickFalse);
2381
2382     for (x = 0; x < (ssize_t) image->columns; x++)
2383     {
2384       if (dds_info->pixelformat.rgb_bitcount == 16)
2385         {
2386            color=ReadBlobShort(image);
2387            if (alphaBits == 1)
2388              {
2389                SetPixelAlpha(image,(color & (1 << 15)) ? QuantumRange : 0,q);
2390                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2391                  ((((unsigned short)(color << 1) >> 11)/31.0)*255)),q);
2392                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2393                  ((((unsigned short)(color << 6) >> 11)/31.0)*255)),q);
2394                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2395                  ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2396              }
2397           else if (alphaBits == 2)
2398             {
2399                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2400                  (color >> 8)),q);
2401                SetPixelGray(image,ScaleCharToQuantum((unsigned char)color),q);
2402             }
2403           else
2404             {
2405                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2406                  (((color >> 12)/15.0)*255)),q);
2407                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2408                  ((((unsigned short)(color << 4) >> 12)/15.0)*255)),q);
2409                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2410                  ((((unsigned short)(color << 8) >> 12)/15.0)*255)),q);
2411                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2412                  ((((unsigned short)(color << 12) >> 12)/15.0)*255)),q);
2413             }
2414         }
2415       else
2416         {
2417           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2418             ReadBlobByte(image)),q);
2419           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2420             ReadBlobByte(image)),q);
2421           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2422             ReadBlobByte(image)),q);
2423           SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2424             ReadBlobByte(image)),q);
2425         }
2426       q+=GetPixelChannels(image);
2427     }
2428     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2429       return(MagickFalse);
2430     if (EOFBlob(image) != MagickFalse)
2431       return(MagickFalse);
2432   }
2433   return(MagickTrue);
2434 }
2435
2436 static MagickBooleanType ReadUncompressedRGBA(const ImageInfo *image_info,
2437   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2438   ExceptionInfo *exception)
2439 {
2440   if (ReadUncompressedRGBAPixels(image,dds_info,exception) == MagickFalse)
2441     return(MagickFalse);
2442
2443   if (read_mipmaps != MagickFalse)
2444     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBAPixels,
2445       exception));
2446   else
2447     return(SkipRGBMipmaps(image,dds_info,4,exception));
2448 }
2449 \f
2450 /*
2451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2452 %                                                                             %
2453 %                                                                             %
2454 %                                                                             %
2455 %   R e g i s t e r D D S I m a g e                                           %
2456 %                                                                             %
2457 %                                                                             %
2458 %                                                                             %
2459 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2460 %
2461 %  RegisterDDSImage() adds attributes for the DDS image format to
2462 %  the list of supported formats.  The attributes include the image format
2463 %  tag, a method to read and/or write the format, whether the format
2464 %  supports the saving of more than one frame to the same file or blob,
2465 %  whether the format supports native in-memory I/O, and a brief
2466 %  description of the format.
2467 %
2468 %  The format of the RegisterDDSImage method is:
2469 %
2470 %      RegisterDDSImage(void)
2471 %
2472 */
2473 ModuleExport size_t RegisterDDSImage(void)
2474 {
2475   MagickInfo
2476     *entry;
2477
2478   entry = AcquireMagickInfo("DDS","DDS","Microsoft DirectDraw Surface");
2479   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2480   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2481   entry->magick = (IsImageFormatHandler *) IsDDS;
2482   entry->flags|=CoderDecoderSeekableStreamFlag;
2483   (void) RegisterMagickInfo(entry);
2484   entry = AcquireMagickInfo("DDS","DXT1","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","DXT5","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   return(MagickImageCoderSignature);
2497 }
2498
2499 static void RemapIndices(const ssize_t *map, const unsigned char *source,
2500   unsigned char *target)
2501 {
2502   register ssize_t
2503     i;
2504
2505   for (i = 0; i < 16; i++)
2506   {
2507     if (map[i] == -1)
2508       target[i] = 3;
2509     else
2510       target[i] = source[map[i]];
2511   }
2512 }
2513
2514 /*
2515   Skip the mipmap images for compressed (DXTn) dds files
2516 */
2517 static MagickBooleanType SkipDXTMipmaps(Image *image,DDSInfo *dds_info,
2518   int texel_size,ExceptionInfo *exception)
2519 {
2520   /*
2521     Only skip mipmaps for textures and cube maps
2522   */
2523   if (EOFBlob(image) != MagickFalse)
2524     {
2525       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
2526         image->filename);
2527       return(MagickFalse);
2528     }
2529   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2530       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2531           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2532     {
2533       MagickOffsetType
2534         offset;
2535
2536       register ssize_t
2537         i;
2538
2539       size_t
2540         h,
2541         w;
2542
2543       w=DIV2(dds_info->width);
2544       h=DIV2(dds_info->height);
2545
2546       /*
2547         Mipmapcount includes the main image, so start from one
2548       */
2549       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2550       {
2551         offset=(MagickOffsetType)((w+3)/4)*((h+3)/4)*texel_size;
2552         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2553           break;
2554         w=DIV2(w);
2555         h=DIV2(h);
2556       }
2557     }
2558   return(MagickTrue);
2559 }
2560
2561 /*
2562   Skip the mipmap images for uncompressed (RGB or RGBA) dds files
2563 */
2564 static MagickBooleanType SkipRGBMipmaps(Image *image,DDSInfo *dds_info,
2565   int pixel_size,ExceptionInfo *exception)
2566 {
2567   /*
2568     Only skip mipmaps for textures and cube maps
2569   */
2570   if (EOFBlob(image) != MagickFalse)
2571     {
2572       ThrowFileException(exception,CorruptImageError,"UnexpectedEndOfFile",
2573         image->filename);
2574       return(MagickFalse);
2575     }
2576   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2577       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2578           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2579     {
2580       MagickOffsetType
2581         offset;
2582
2583       register ssize_t
2584         i;
2585
2586       size_t
2587         h,
2588         w;
2589
2590       w=DIV2(dds_info->width);
2591       h=DIV2(dds_info->height);
2592
2593       /*
2594         Mipmapcount includes the main image, so start from one
2595       */
2596       for (i=1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2597       {
2598         offset=(MagickOffsetType)w*h*pixel_size;
2599         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2600           break;
2601         w=DIV2(w);
2602         h=DIV2(h);
2603       }
2604     }
2605   return(MagickTrue);
2606 }
2607 \f
2608 /*
2609 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2610 %                                                                             %
2611 %                                                                             %
2612 %                                                                             %
2613 %   U n r e g i s t e r D D S I m a g e                                       %
2614 %                                                                             %
2615 %                                                                             %
2616 %                                                                             %
2617 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2618 %
2619 %  UnregisterDDSImage() removes format registrations made by the
2620 %  DDS module from the list of supported formats.
2621 %
2622 %  The format of the UnregisterDDSImage method is:
2623 %
2624 %      UnregisterDDSImage(void)
2625 %
2626 */
2627 ModuleExport void UnregisterDDSImage(void)
2628 {
2629   (void) UnregisterMagickInfo("DDS");
2630   (void) UnregisterMagickInfo("DXT1");
2631   (void) UnregisterMagickInfo("DXT5");
2632 }
2633
2634 static void WriteAlphas(Image *image, const ssize_t *alphas, size_t min5,
2635   size_t max5, size_t min7, size_t max7)
2636 {
2637   register ssize_t
2638     i;
2639
2640   size_t
2641     err5,
2642     err7,
2643     j;
2644
2645   unsigned char
2646     indices5[16],
2647     indices7[16];
2648
2649   FixRange(min5,max5,5);
2650   err5 = CompressAlpha(min5,max5,5,alphas,indices5);
2651
2652   FixRange(min7,max7,7);
2653   err7 = CompressAlpha(min7,max7,7,alphas,indices7);
2654
2655   if (err7 < err5)
2656   {
2657     for (i=0; i < 16; i++)
2658     {
2659       unsigned char
2660         index;
2661
2662       index = indices7[i];
2663       if( index == 0 )
2664         indices5[i] = 1;
2665       else if (index == 1)
2666         indices5[i] = 0;
2667       else
2668         indices5[i] = 9 - index;
2669     }
2670
2671     min5 = max7;
2672     max5 = min7;
2673   }
2674
2675   (void) WriteBlobByte(image,(unsigned char) min5);
2676   (void) WriteBlobByte(image,(unsigned char) max5);
2677
2678   for(i=0; i < 2; i++)
2679   {
2680     size_t
2681       value = 0;
2682
2683     for (j=0; j < 8; j++)
2684     {
2685       size_t index = (size_t) indices5[j + i*8];
2686       value |= ( index << 3*j );
2687     }
2688
2689     for (j=0; j < 3; j++)
2690     {
2691       size_t byte = (value >> 8*j) & 0xff;
2692       (void) WriteBlobByte(image,(unsigned char) byte);
2693     }
2694   }
2695 }
2696
2697 static void WriteCompressed(Image *image, const size_t count,
2698   DDSVector4 *points, const ssize_t *map, const MagickBooleanType clusterFit)
2699 {
2700   float
2701     covariance[16];
2702
2703   DDSVector3
2704     end,
2705     principle,
2706     start;
2707
2708   DDSVector4
2709     metric;
2710
2711   unsigned char
2712     indices[16];
2713
2714   VectorInit(metric,1.0f);
2715   VectorInit3(start,0.0f);
2716   VectorInit3(end,0.0f);
2717
2718   ComputeWeightedCovariance(count,points,covariance);
2719   ComputePrincipleComponent(covariance,&principle);
2720
2721   if ((clusterFit == MagickFalse) || (count == 0))
2722     CompressRangeFit(count,points,map,principle,metric,&start,&end,indices);
2723   else
2724     CompressClusterFit(count,points,map,principle,metric,&start,&end,indices);
2725
2726   WriteIndices(image,start,end,indices);
2727 }
2728
2729 /*
2730 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2731 %                                                                             %
2732 %                                                                             %
2733 %                                                                             %
2734 %   W r i t e D D S I m a g e                                                 %
2735 %                                                                             %
2736 %                                                                             %
2737 %                                                                             %
2738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2739 %
2740 %  WriteDDSImage() writes a DirectDraw Surface image file in the DXT5 format.
2741 %
2742 %  The format of the WriteBMPImage method is:
2743 %
2744 %     MagickBooleanType WriteDDSImage(const ImageInfo *image_info,Image *image)
2745 %
2746 %  A description of each parameter follows.
2747 %
2748 %    o image_info: the image info.
2749 %
2750 %    o image:  The image.
2751 %
2752 */
2753 static MagickBooleanType WriteDDSImage(const ImageInfo *image_info,
2754   Image *image, ExceptionInfo *exception)
2755 {
2756   const char
2757     *option;
2758
2759   size_t
2760     compression,
2761     columns,
2762     maxMipmaps,
2763     mipmaps,
2764     pixelFormat,
2765     rows;
2766
2767   MagickBooleanType
2768     clusterFit,
2769     fromlist,
2770     status,
2771     weightByAlpha;
2772
2773   assert(image_info != (const ImageInfo *) NULL);
2774   assert(image_info->signature == MagickCoreSignature);
2775   assert(image != (Image *) NULL);
2776   assert(image->signature == MagickCoreSignature);
2777   if (image->debug != MagickFalse)
2778     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2779   status=OpenBlob(image_info,image,WriteBinaryBlobMode,exception);
2780   if (status == MagickFalse)
2781     return(status);
2782   (void) TransformImageColorspace(image,sRGBColorspace,exception);
2783   pixelFormat=DDPF_FOURCC;
2784   compression=FOURCC_DXT5;
2785
2786   if (image->alpha_trait == UndefinedPixelTrait)
2787     compression=FOURCC_DXT1;
2788
2789   if (LocaleCompare(image_info->magick,"dxt1") == 0)
2790     compression=FOURCC_DXT1;
2791
2792   option=GetImageOption(image_info,"dds:compression");
2793   if (option != (char *) NULL)
2794     {
2795        if (LocaleCompare(option,"dxt1") == 0)
2796          compression=FOURCC_DXT1;
2797        if (LocaleCompare(option,"none") == 0)
2798          pixelFormat=DDPF_RGB;
2799     }
2800
2801   clusterFit=MagickFalse;
2802   weightByAlpha=MagickFalse;
2803
2804   if (pixelFormat == DDPF_FOURCC)
2805     {
2806       option=GetImageOption(image_info,"dds:cluster-fit");
2807       if (IsStringTrue(option) != MagickFalse)
2808         {
2809           clusterFit=MagickTrue;
2810           if (compression != FOURCC_DXT1)
2811             {
2812               option=GetImageOption(image_info,"dds:weight-by-alpha");
2813               if (IsStringTrue(option) != MagickFalse)
2814                 weightByAlpha=MagickTrue;
2815             }
2816         }
2817     }
2818
2819   mipmaps=0;
2820   fromlist=MagickFalse;
2821   option=GetImageOption(image_info,"dds:mipmaps");
2822   if (option != (char *) NULL)
2823     {
2824       if (LocaleNCompare(option,"fromlist",8) == 0)
2825         {
2826           Image
2827             *next;
2828
2829           fromlist=MagickTrue;
2830           next=image->next;
2831           while(next != (Image *) NULL)
2832           {
2833             mipmaps++;
2834             next=next->next;
2835           }
2836         }
2837     }
2838
2839   if ((mipmaps == 0) &&
2840       ((image->columns & (image->columns - 1)) == 0) &&
2841       ((image->rows & (image->rows - 1)) == 0))
2842     {
2843       maxMipmaps=SIZE_MAX;
2844       if (option != (char *) NULL)
2845         maxMipmaps=StringToUnsignedLong(option);
2846
2847       if (maxMipmaps != 0)
2848         {
2849           columns=image->columns;
2850           rows=image->rows;
2851           while ((columns != 1 || rows != 1) && mipmaps != maxMipmaps)
2852           {
2853             columns=DIV2(columns);
2854             rows=DIV2(rows);
2855             mipmaps++;
2856           }
2857         }
2858     }
2859
2860   WriteDDSInfo(image,pixelFormat,compression,mipmaps);
2861
2862   WriteImageData(image,pixelFormat,compression,clusterFit,weightByAlpha,
2863     exception);
2864
2865   if ((mipmaps > 0) && (WriteMipmaps(image,image_info,pixelFormat,compression,
2866        mipmaps,fromlist,clusterFit,weightByAlpha,exception) == MagickFalse))
2867     return(MagickFalse);
2868
2869   (void) CloseBlob(image);
2870   return(MagickTrue);
2871 }
2872
2873 static void WriteDDSInfo(Image *image, const size_t pixelFormat,
2874   const size_t compression, const size_t mipmaps)
2875 {
2876   char
2877     software[MagickPathExtent];
2878
2879   register ssize_t
2880     i;
2881
2882   unsigned int
2883     format,
2884     caps,
2885     flags;
2886
2887   flags=(unsigned int) (DDSD_CAPS | DDSD_WIDTH | DDSD_HEIGHT |
2888     DDSD_PIXELFORMAT);
2889   caps=(unsigned int) DDSCAPS_TEXTURE;
2890   format=(unsigned int) pixelFormat;
2891
2892   if (format == DDPF_FOURCC)
2893       flags=flags | DDSD_LINEARSIZE;
2894   else
2895       flags=flags | DDSD_PITCH;
2896
2897   if (mipmaps > 0)
2898     {
2899       flags=flags | (unsigned int) DDSD_MIPMAPCOUNT;
2900       caps=caps | (unsigned int) (DDSCAPS_MIPMAP | DDSCAPS_COMPLEX);
2901     }
2902
2903   if (format != DDPF_FOURCC && image->alpha_trait != UndefinedPixelTrait)
2904     format=format | DDPF_ALPHAPIXELS;
2905
2906   (void) WriteBlob(image,4,(unsigned char *) "DDS ");
2907   (void) WriteBlobLSBLong(image,124);
2908   (void) WriteBlobLSBLong(image,flags);
2909   (void) WriteBlobLSBLong(image,(unsigned int) image->rows);
2910   (void) WriteBlobLSBLong(image,(unsigned int) image->columns);
2911
2912   if (pixelFormat == DDPF_FOURCC)
2913     {
2914       /* Compressed DDS requires linear compressed size of first image */
2915       if (compression == FOURCC_DXT1)
2916         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2917           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*8));
2918       else /* DXT5 */
2919         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2920           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*16));
2921     }
2922   else
2923     {
2924       /* Uncompressed DDS requires byte pitch of first image */
2925       if (image->alpha_trait != UndefinedPixelTrait)
2926         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 4));
2927       else
2928         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 3));
2929     }
2930
2931   (void) WriteBlobLSBLong(image,0x00);
2932   (void) WriteBlobLSBLong(image,(unsigned int) mipmaps+1);
2933   (void) ResetMagickMemory(software,0,sizeof(software));
2934   (void) CopyMagickString(software,"IMAGEMAGICK",MagickPathExtent);
2935   (void) WriteBlob(image,44,(unsigned char *) software);
2936
2937   (void) WriteBlobLSBLong(image,32);
2938   (void) WriteBlobLSBLong(image,format);
2939
2940   if (pixelFormat == DDPF_FOURCC)
2941     {
2942       (void) WriteBlobLSBLong(image,(unsigned int) compression);
2943       for(i=0;i < 5;i++) // bitcount / masks
2944         (void) WriteBlobLSBLong(image,0x00);
2945     }
2946   else
2947     {
2948       (void) WriteBlobLSBLong(image,0x00);
2949       if (image->alpha_trait != UndefinedPixelTrait)
2950         {
2951           (void) WriteBlobLSBLong(image,32);
2952           (void) WriteBlobLSBLong(image,0xff0000);
2953           (void) WriteBlobLSBLong(image,0xff00);
2954           (void) WriteBlobLSBLong(image,0xff);
2955           (void) WriteBlobLSBLong(image,0xff000000);
2956         }
2957       else
2958         {
2959           (void) WriteBlobLSBLong(image,24);
2960           (void) WriteBlobLSBLong(image,0xff0000);
2961           (void) WriteBlobLSBLong(image,0xff00);
2962           (void) WriteBlobLSBLong(image,0xff);
2963           (void) WriteBlobLSBLong(image,0x00);
2964         }
2965     }
2966
2967   (void) WriteBlobLSBLong(image,caps);
2968   for(i=0;i < 4;i++) // ddscaps2 + reserved region
2969     (void) WriteBlobLSBLong(image,0x00);
2970 }
2971
2972 static void WriteFourCC(Image *image, const size_t compression,
2973   const MagickBooleanType clusterFit, const MagickBooleanType weightByAlpha,
2974   ExceptionInfo *exception)
2975 {
2976   register ssize_t
2977     x;
2978
2979   ssize_t
2980     i,
2981     y,
2982     bx,
2983     by;
2984
2985   register const Quantum
2986     *p;
2987
2988   for (y=0; y < (ssize_t) image->rows; y+=4)
2989   {
2990     for (x=0; x < (ssize_t) image->columns; x+=4)
2991     {
2992       MagickBooleanType
2993         match;
2994
2995       DDSVector4
2996         point,
2997         points[16];
2998
2999       size_t
3000         count = 0,
3001         max5 = 0,
3002         max7 = 0,
3003         min5 = 255,
3004         min7 = 255,
3005         columns = 4,
3006         rows = 4;
3007
3008       ssize_t
3009         alphas[16],
3010         map[16];
3011
3012       unsigned char
3013         alpha;
3014
3015       if (x + columns >= image->columns)
3016         columns = image->columns - x;
3017
3018       if (y + rows >= image->rows)
3019         rows = image->rows - y;
3020
3021       p=GetVirtualPixels(image,x,y,columns,rows,exception);
3022       if (p == (const Quantum *) NULL)
3023         break;
3024
3025       for (i=0; i<16; i++)
3026       {
3027         map[i] = -1;
3028         alphas[i] = -1;
3029       }
3030
3031       for (by=0; by < (ssize_t) rows; by++)
3032       {
3033         for (bx=0; bx < (ssize_t) columns; bx++)
3034         {
3035           if (compression == FOURCC_DXT5)
3036             alpha = ScaleQuantumToChar(GetPixelAlpha(image,p));
3037           else
3038             alpha = 255;
3039
3040           if (compression == FOURCC_DXT5)
3041             {
3042               if (alpha < min7)
3043                 min7 = alpha;
3044               if (alpha > max7)
3045                 max7 = alpha;
3046               if (alpha != 0 && alpha < min5)
3047                 min5 = alpha;
3048               if (alpha != 255 && alpha > max5)
3049                 max5 = alpha;
3050             }
3051
3052           alphas[4*by + bx] = (size_t)alpha;
3053
3054           point.x = (float)ScaleQuantumToChar(GetPixelRed(image,p)) / 255.0f;
3055           point.y = (float)ScaleQuantumToChar(GetPixelGreen(image,p)) / 255.0f;
3056           point.z = (float)ScaleQuantumToChar(GetPixelBlue(image,p)) / 255.0f;
3057           point.w = weightByAlpha ? (float)(alpha + 1) / 256.0f : 1.0f;
3058           p+=GetPixelChannels(image);
3059
3060           match = MagickFalse;
3061           for (i=0; i < (ssize_t) count; i++)
3062           {
3063             if ((points[i].x == point.x) &&
3064                 (points[i].y == point.y) &&
3065                 (points[i].z == point.z) &&
3066                 (alpha       >= 128 || compression == FOURCC_DXT5))
3067               {
3068                 points[i].w += point.w;
3069                 map[4*by + bx] = i;
3070                 match = MagickTrue;
3071                 break;
3072               }
3073           }
3074
3075           if (match != MagickFalse)
3076             continue;
3077
3078           points[count].x = point.x;
3079           points[count].y = point.y;
3080           points[count].z = point.z;
3081           points[count].w = point.w;
3082           map[4*by + bx] = count;
3083           count++;
3084         }
3085       }
3086
3087       for (i=0; i < (ssize_t) count; i++)
3088         points[i].w = sqrt(points[i].w);
3089
3090       if (compression == FOURCC_DXT5)
3091         WriteAlphas(image,alphas,min5,max5,min7,max7);
3092
3093       if (count == 1)
3094         WriteSingleColorFit(image,points,map);
3095       else
3096         WriteCompressed(image,count,points,map,clusterFit);
3097     }
3098   }
3099 }
3100
3101 static void WriteImageData(Image *image, const size_t pixelFormat,
3102   const size_t compression,const MagickBooleanType clusterFit,
3103   const MagickBooleanType weightByAlpha, ExceptionInfo *exception)
3104 {
3105   if (pixelFormat == DDPF_FOURCC)
3106     WriteFourCC(image,compression,clusterFit,weightByAlpha,exception);
3107   else
3108     WriteUncompressed(image,exception);
3109 }
3110
3111 static inline size_t ClampToLimit(const float value, const size_t limit)
3112 {
3113   size_t
3114     result = (int) (value + 0.5f);
3115
3116   if (result < 0.0f)
3117     return(0);
3118   if (result > limit)
3119     return(limit);
3120   return result;
3121 }
3122
3123 static inline size_t ColorTo565(const DDSVector3 point)
3124 {
3125   size_t r = ClampToLimit(31.0f*point.x,31);
3126   size_t g = ClampToLimit(63.0f*point.y,63);
3127   size_t b = ClampToLimit(31.0f*point.z,31);
3128
3129   return (r << 11) | (g << 5) | b;
3130 }
3131
3132 static void WriteIndices(Image *image, const DDSVector3 start,
3133   const DDSVector3 end, unsigned char *indices)
3134 {
3135   register ssize_t
3136     i;
3137
3138   size_t
3139     a,
3140     b;
3141
3142   unsigned char
3143     remapped[16];
3144
3145   const unsigned char
3146     *ind;
3147
3148   a = ColorTo565(start);
3149   b = ColorTo565(end);
3150
3151   for (i=0; i<16; i++)
3152   {
3153     if( a < b )
3154       remapped[i] = (indices[i] ^ 0x1) & 0x3;
3155     else if( a == b )
3156       remapped[i] = 0;
3157     else
3158       remapped[i] = indices[i];
3159   }
3160
3161   if( a < b )
3162     Swap(a,b);
3163
3164   (void) WriteBlobByte(image,(unsigned char) (a & 0xff));
3165   (void) WriteBlobByte(image,(unsigned char) (a >> 8));
3166   (void) WriteBlobByte(image,(unsigned char) (b & 0xff));
3167   (void) WriteBlobByte(image,(unsigned char) (b >> 8));
3168
3169   for (i=0; i<4; i++)
3170   {
3171      ind = remapped + 4*i;
3172      (void) WriteBlobByte(image,ind[0] | (ind[1] << 2) | (ind[2] << 4) |
3173        (ind[3] << 6));
3174   }
3175 }
3176
3177 static MagickBooleanType WriteMipmaps(Image *image,const ImageInfo *image_info,
3178   const size_t pixelFormat,const size_t compression,const size_t mipmaps,
3179   const MagickBooleanType fromlist,const MagickBooleanType clusterFit,
3180   const MagickBooleanType weightByAlpha,ExceptionInfo *exception)
3181 {
3182   const char
3183     *option;
3184
3185   Image
3186     *mipmap_image,
3187     *resize_image;
3188
3189   MagickBooleanType
3190     fast_mipmaps,
3191     status;
3192
3193   register ssize_t
3194     i;
3195
3196   size_t
3197     columns,
3198     rows;
3199
3200   columns=DIV2(image->columns);
3201   rows=DIV2(image->rows);
3202
3203   option=GetImageOption(image_info,"dds:fast-mipmaps");
3204   fast_mipmaps=IsStringTrue(option);
3205   mipmap_image=image;
3206   resize_image=image;
3207   status=MagickTrue;
3208   for (i=0; i < (ssize_t) mipmaps; i++)
3209   {
3210     if (fromlist == MagickFalse)
3211       {
3212         mipmap_image=ResizeImage(resize_image,columns,rows,TriangleFilter,
3213           exception);
3214
3215         if (mipmap_image == (Image *) NULL)
3216           {
3217             status=MagickFalse;
3218             break;
3219           }
3220       }
3221     else
3222       {
3223         mipmap_image=mipmap_image->next;
3224         if ((mipmap_image->columns != columns) || (mipmap_image->rows != rows))
3225           ThrowBinaryException(CoderError,"ImageColumnOrRowSizeIsNotSupported",
3226             image->filename);
3227       }
3228
3229     DestroyBlob(mipmap_image);
3230     mipmap_image->blob=ReferenceBlob(image->blob);
3231
3232     WriteImageData(mipmap_image,pixelFormat,compression,weightByAlpha,
3233       clusterFit,exception);
3234
3235     if (fromlist == MagickFalse)
3236       {
3237         if (fast_mipmaps == MagickFalse)
3238           mipmap_image=DestroyImage(mipmap_image);
3239         else
3240           {
3241             if (resize_image != image)
3242               resize_image=DestroyImage(resize_image);
3243             resize_image=mipmap_image;
3244           }
3245       }
3246
3247     columns=DIV2(columns);
3248     rows=DIV2(rows);
3249   }
3250
3251   if (resize_image != image)
3252     resize_image=DestroyImage(resize_image);
3253
3254   return(status);
3255 }
3256
3257 static void WriteSingleColorFit(Image *image, const DDSVector4 *points,
3258   const ssize_t *map)
3259 {
3260   DDSVector3
3261     start,
3262     end;
3263
3264   register ssize_t
3265     i;
3266
3267   unsigned char
3268     color[3],
3269     index,
3270     indexes[16],
3271     indices[16];
3272
3273   color[0] = (unsigned char) ClampToLimit(255.0f*points->x,255);
3274   color[1] = (unsigned char) ClampToLimit(255.0f*points->y,255);
3275   color[2] = (unsigned char) ClampToLimit(255.0f*points->z,255);
3276
3277   index=0;
3278   ComputeEndPoints(DDS_LOOKUP,color,&start,&end,&index);
3279
3280   for (i=0; i< 16; i++)
3281     indexes[i]=index;
3282   RemapIndices(map,indexes,indices);
3283   WriteIndices(image,start,end,indices);
3284 }
3285
3286 static void WriteUncompressed(Image *image, ExceptionInfo *exception)
3287 {
3288   register const Quantum
3289     *p;
3290
3291   register ssize_t
3292     x;
3293
3294   ssize_t
3295     y;
3296
3297   for (y=0; y < (ssize_t) image->rows; y++)
3298   {
3299     p=GetVirtualPixels(image,0,y,image->columns,1,exception);
3300     if (p == (const Quantum *) NULL)
3301       break;
3302
3303     for (x=0; x < (ssize_t) image->columns; x++)
3304     {
3305       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelBlue(image,p)));
3306       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelGreen(image,p)));
3307       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelRed(image,p)));
3308       if (image->alpha_trait != UndefinedPixelTrait)
3309         (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelAlpha(image,p)));
3310       p+=GetPixelChannels(image);
3311     }
3312   }
3313 }