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

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                                                                             %
   6 %                            DDDD   DDDD   SSSSS                              %
   7 %                            D   D  D   D  SS                                 %
   8 %                            D   D  D   D   SSS                               %
   9 %                            D   D  D   D     SS                              %
  10 %                            DDDD   DDDD   SSSSS                              %
  11 %                                                                             %
  12 %                                                                             %
  13 %           Read/Write Microsoft Direct Draw Surface Image Format             %
  14 %                                                                             %
  15 %                              Software Design                                %
  16 %                             Bianca van Schaik                               %
  17 %                                March 2008                                   %
  18 %                               Dirk Lemstra                                  %
  19 %                              September 2013                                 %
  20 %                                                                             %
  21 %                                                                             %
  22 %  Copyright 1999-2018 ImageMagick Studio LLC, a non-profit organization      %
  23 %  dedicated to making software imaging solutions freely available.           %
  24 %                                                                             %
  25 %  You may not use this file except in compliance with the License.  You may  %
  26 %  obtain a copy of the License at                                            %
  27 %                                                                             %
  28 %    https://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                 VectorCopy43(a,start);
1179                 VectorCopy43(b,end);
1180                 bestError = error;
1181                 besti = i;
1182                 bestj = j;
1183                 bestk = k;
1184                 bestIteration = iterationIndex;
1185               }
1186             }
1187
1188           if (k == count)
1189             break;
1190
1191           VectorAdd(pointsWeights[k],part2,&part2);
1192           k++;
1193         }
1194
1195         if (j == count)
1196           break;
1197
1198         VectorAdd(pointsWeights[j],part1,&part1);
1199         j++;
1200       }
1201     }
1202
1203     if (bestIteration != iterationIndex)
1204       break;
1205
1206     iterationIndex++;
1207     if (iterationIndex == 8)
1208       break;
1209
1210     VectorSubtract3(*end,*start,&axis);
1211     if (ConstructOrdering(count,points,axis,pointsWeights,&xSumwSum,order,
1212       iterationIndex) == MagickFalse)
1213       break;
1214   }
1215
1216   o = order + (16*bestIteration);
1217
1218   for (i=0; i < (ssize_t) besti; i++)
1219     unordered[o[i]] = 0;
1220   for (i=besti; i < (ssize_t) bestj; i++)
1221     unordered[o[i]] = 2;
1222   for (i=bestj; i < (ssize_t) bestk; i++)
1223     unordered[o[i]] = 3;
1224   for (i=bestk; i < (ssize_t) count; i++)
1225     unordered[o[i]] = 1;
1226
1227   RemapIndices(map,unordered,indices);
1228 }
1229
1230 static void CompressRangeFit(const size_t count,
1231   const DDSVector4* points, const ssize_t *map, const DDSVector3 principle,
1232   const DDSVector4 metric, DDSVector3 *start, DDSVector3 *end,
1233   unsigned char *indices)
1234 {
1235   float
1236     d,
1237     bestDist,
1238     max,
1239     min,
1240     val;
1241
1242   DDSVector3
1243     codes[4],
1244     grid,
1245     gridrcp,
1246     half,
1247     dist;
1248
1249   register ssize_t
1250     i;
1251
1252   size_t
1253     bestj,
1254     j;
1255
1256   unsigned char
1257     closest[16];
1258
1259   VectorInit3(half,0.5f);
1260
1261   grid.x = 31.0f;
1262   grid.y = 63.0f;
1263   grid.z = 31.0f;
1264
1265   gridrcp.x = 1.0f/31.0f;
1266   gridrcp.y = 1.0f/63.0f;
1267   gridrcp.z = 1.0f/31.0f;
1268
1269   if (count > 0)
1270     {
1271       VectorCopy43(points[0],start);
1272       VectorCopy43(points[0],end);
1273
1274       min = max = Dot(points[0],principle);
1275       for (i=1; i < (ssize_t) count; i++)
1276       {
1277         val = Dot(points[i],principle);
1278         if (val < min)
1279         {
1280           VectorCopy43(points[i],start);
1281           min = val;
1282         }
1283         else if (val > max)
1284         {
1285           VectorCopy43(points[i],end);
1286           max = val;
1287         }
1288       }
1289     }
1290
1291   VectorClamp3(start);
1292   VectorMultiplyAdd3(grid,*start,half,start);
1293   VectorTruncate3(start);
1294   VectorMultiply3(*start,gridrcp,start);
1295
1296   VectorClamp3(end);
1297   VectorMultiplyAdd3(grid,*end,half,end);
1298   VectorTruncate3(end);
1299   VectorMultiply3(*end,gridrcp,end);
1300
1301   codes[0] = *start;
1302   codes[1] = *end;
1303   codes[2].x = (start->x * (2.0f/3.0f)) + (end->x * (1.0f/3.0f));
1304   codes[2].y = (start->y * (2.0f/3.0f)) + (end->y * (1.0f/3.0f));
1305   codes[2].z = (start->z * (2.0f/3.0f)) + (end->z * (1.0f/3.0f));
1306   codes[3].x = (start->x * (1.0f/3.0f)) + (end->x * (2.0f/3.0f));
1307   codes[3].y = (start->y * (1.0f/3.0f)) + (end->y * (2.0f/3.0f));
1308   codes[3].z = (start->z * (1.0f/3.0f)) + (end->z * (2.0f/3.0f));
1309
1310   for (i=0; i < (ssize_t) count; i++)
1311   {
1312     bestDist = 1e+37f;
1313     bestj = 0;
1314     for (j=0; j < 4; j++)
1315     {
1316       dist.x = (points[i].x - codes[j].x) * metric.x;
1317       dist.y = (points[i].y - codes[j].y) * metric.y;
1318       dist.z = (points[i].z - codes[j].z) * metric.z;
1319
1320       d = Dot(dist,dist);
1321       if (d < bestDist)
1322         {
1323           bestDist = d;
1324           bestj = j;
1325         }
1326     }
1327
1328     closest[i] = (unsigned char) bestj;
1329   }
1330
1331   RemapIndices(map, closest, indices);
1332 }
1333
1334 static void ComputeEndPoints(const DDSSingleColourLookup *lookup[],
1335   const unsigned char *color, DDSVector3 *start, DDSVector3 *end,
1336   unsigned char *index)
1337 {
1338   register ssize_t
1339     i;
1340
1341   size_t
1342     c,
1343     maxError = SIZE_MAX;
1344
1345   for (i=0; i < 2; i++)
1346   {
1347     const DDSSourceBlock*
1348       sources[3];
1349
1350       size_t
1351         error = 0;
1352
1353     for (c=0; c < 3; c++)
1354     {
1355       sources[c] = &lookup[c][color[c]].sources[i];
1356       error += ((size_t) sources[c]->error) * ((size_t) sources[c]->error);
1357     }
1358
1359     if (error > maxError)
1360       continue;
1361
1362     start->x = (float) sources[0]->start / 31.0f;
1363     start->y = (float) sources[1]->start / 63.0f;
1364     start->z = (float) sources[2]->start / 31.0f;
1365
1366     end->x = (float) sources[0]->end / 31.0f;
1367     end->y = (float) sources[1]->end / 63.0f;
1368     end->z = (float) sources[2]->end / 31.0f;
1369
1370     *index = (unsigned char) (2*i);
1371     maxError = error;
1372   }
1373 }
1374
1375 static void ComputePrincipleComponent(const float *covariance,
1376   DDSVector3 *principle)
1377 {
1378   DDSVector4
1379     row0,
1380     row1,
1381     row2,
1382     v;
1383
1384   register ssize_t
1385     i;
1386
1387   row0.x = covariance[0];
1388   row0.y = covariance[1];
1389   row0.z = covariance[2];
1390   row0.w = 0.0f;
1391
1392   row1.x = covariance[1];
1393   row1.y = covariance[3];
1394   row1.z = covariance[4];
1395   row1.w = 0.0f;
1396
1397   row2.x = covariance[2];
1398   row2.y = covariance[4];
1399   row2.z = covariance[5];
1400   row2.w = 0.0f;
1401
1402   VectorInit(v,1.0f);
1403
1404   for (i=0; i < 8; i++)
1405   {
1406     DDSVector4
1407       w;
1408
1409     float
1410       a;
1411
1412     w.x = row0.x * v.x;
1413     w.y = row0.y * v.x;
1414     w.z = row0.z * v.x;
1415     w.w = row0.w * v.x;
1416
1417     w.x = (row1.x * v.y) + w.x;
1418     w.y = (row1.y * v.y) + w.y;
1419     w.z = (row1.z * v.y) + w.z;
1420     w.w = (row1.w * v.y) + w.w;
1421
1422     w.x = (row2.x * v.z) + w.x;
1423     w.y = (row2.y * v.z) + w.y;
1424     w.z = (row2.z * v.z) + w.z;
1425     w.w = (row2.w * v.z) + w.w;
1426
1427     a = (float) PerceptibleReciprocal(MagickMax(w.x,MagickMax(w.y,w.z)));
1428
1429     v.x = w.x * a;
1430     v.y = w.y * a;
1431     v.z = w.z * a;
1432     v.w = w.w * a;
1433   }
1434
1435   VectorCopy43(v,principle);
1436 }
1437
1438 static void ComputeWeightedCovariance(const size_t count,
1439   const DDSVector4 *points, float *covariance)
1440 {
1441   DDSVector3
1442     centroid;
1443
1444   float
1445     total;
1446
1447   size_t
1448     i;
1449
1450   total = 0.0f;
1451   VectorInit3(centroid,0.0f);
1452
1453   for (i=0; i < count; i++)
1454   {
1455     total += points[i].w;
1456     centroid.x += (points[i].x * points[i].w);
1457     centroid.y += (points[i].y * points[i].w);
1458     centroid.z += (points[i].z * points[i].w);
1459   }
1460
1461   if( total > 1.192092896e-07F)
1462     {
1463       centroid.x /= total;
1464       centroid.y /= total;
1465       centroid.z /= total;
1466     }
1467
1468   for (i=0; i < 6; i++)
1469     covariance[i] = 0.0f;
1470
1471   for (i = 0; i < count; i++)
1472   {
1473     DDSVector3
1474       a,
1475       b;
1476
1477     a.x = points[i].x - centroid.x;
1478     a.y = points[i].y - centroid.y;
1479     a.z = points[i].z - centroid.z;
1480
1481     b.x = points[i].w * a.x;
1482     b.y = points[i].w * a.y;
1483     b.z = points[i].w * a.z;
1484
1485     covariance[0] += a.x*b.x;
1486     covariance[1] += a.x*b.y;
1487     covariance[2] += a.x*b.z;
1488     covariance[3] += a.y*b.y;
1489     covariance[4] += a.y*b.z;
1490     covariance[5] += a.z*b.z;
1491   }
1492 }
1493
1494 static MagickBooleanType ConstructOrdering(const size_t count,
1495   const DDSVector4 *points, const DDSVector3 axis, DDSVector4 *pointsWeights,
1496   DDSVector4 *xSumwSum, unsigned char *order, size_t iteration)
1497 {
1498   float
1499      dps[16],
1500      f;
1501
1502   register ssize_t
1503     i;
1504
1505   size_t
1506     j;
1507
1508   unsigned char
1509     c,
1510     *o,
1511     *p;
1512
1513   o = order + (16*iteration);
1514
1515   for (i=0; i < (ssize_t) count; i++)
1516   {
1517     dps[i] = Dot(points[i],axis);
1518     o[i] = (unsigned char)i;
1519   }
1520
1521   for (i=0; i < (ssize_t) count; i++)
1522   {
1523     for (j=i; j > 0 && dps[j] < dps[j - 1]; j--)
1524     {
1525       f = dps[j];
1526       dps[j] = dps[j - 1];
1527       dps[j - 1] = f;
1528
1529       c = o[j];
1530       o[j] = o[j - 1];
1531       o[j - 1] = c;
1532     }
1533   }
1534
1535   for (i=0; i < (ssize_t) iteration; i++)
1536   {
1537     MagickBooleanType
1538       same;
1539
1540     p = order + (16*i);
1541     same = MagickTrue;
1542
1543     for (j=0; j < count; j++)
1544     {
1545       if (o[j] != p[j])
1546         {
1547           same = MagickFalse;
1548           break;
1549         }
1550     }
1551
1552     if (same != MagickFalse)
1553       return MagickFalse;
1554   }
1555
1556   xSumwSum->x = 0;
1557   xSumwSum->y = 0;
1558   xSumwSum->z = 0;
1559   xSumwSum->w = 0;
1560
1561   for (i=0; i < (ssize_t) count; i++)
1562   {
1563     DDSVector4
1564       v;
1565
1566     j = (size_t) o[i];
1567
1568     v.x = points[j].w * points[j].x;
1569     v.y = points[j].w * points[j].y;
1570     v.z = points[j].w * points[j].z;
1571     v.w = points[j].w * 1.0f;
1572
1573     VectorCopy44(v,&pointsWeights[i]);
1574     VectorAdd(*xSumwSum,v,xSumwSum);
1575   }
1576
1577   return MagickTrue;
1578 }
1579
1580 /*
1581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1582 %                                                                             %
1583 %                                                                             %
1584 %                                                                             %
1585 %   I s D D S                                                                 %
1586 %                                                                             %
1587 %                                                                             %
1588 %                                                                             %
1589 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1590 %
1591 %  IsDDS() returns MagickTrue if the image format type, identified by the
1592 %  magick string, is DDS.
1593 %
1594 %  The format of the IsDDS method is:
1595 %
1596 %      MagickBooleanType IsDDS(const unsigned char *magick,const size_t length)
1597 %
1598 %  A description of each parameter follows:
1599 %
1600 %    o magick: compare image format pattern against these bytes.
1601 %
1602 %    o length: Specifies the length of the magick string.
1603 %
1604 */
1605 static MagickBooleanType IsDDS(const unsigned char *magick, const size_t length)
1606 {
1607   if (length < 4)
1608     return(MagickFalse);
1609   if (LocaleNCompare((char *) magick,"DDS ", 4) == 0)
1610     return(MagickTrue);
1611   return(MagickFalse);
1612 }
1613 /*
1614 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1615 %                                                                             %
1616 %                                                                             %
1617 %                                                                             %
1618 %   R e a d D D S I m a g e                                                   %
1619 %                                                                             %
1620 %                                                                             %
1621 %                                                                             %
1622 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1623 %
1624 %  ReadDDSImage() reads a DirectDraw Surface image file and returns it.  It
1625 %  allocates the memory necessary for the new Image structure and returns a
1626 %  pointer to the new image.
1627 %
1628 %  The format of the ReadDDSImage method is:
1629 %
1630 %      Image *ReadDDSImage(const ImageInfo *image_info,ExceptionInfo *exception)
1631 %
1632 %  A description of each parameter follows:
1633 %
1634 %    o image_info: The image info.
1635 %
1636 %    o exception: return any errors or warnings in this structure.
1637 %
1638 */
1639
1640 static Image *ReadDDSImage(const ImageInfo *image_info,ExceptionInfo *exception)
1641 {
1642   const char
1643     *option;
1644
1645   CompressionType
1646     compression;
1647
1648   DDSInfo
1649     dds_info;
1650
1651   DDSDecoder
1652     *decoder;
1653
1654   Image
1655     *image;
1656
1657   MagickBooleanType
1658     status,
1659     cubemap,
1660     volume,
1661     read_mipmaps;
1662
1663   PixelTrait
1664     alpha_trait;
1665
1666   size_t
1667     n,
1668     num_images;
1669
1670   /*
1671     Open image file.
1672   */
1673   assert(image_info != (const ImageInfo *) NULL);
1674   assert(image_info->signature == MagickCoreSignature);
1675   if (image_info->debug != MagickFalse)
1676     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",
1677       image_info->filename);
1678   assert(exception != (ExceptionInfo *) NULL);
1679   assert(exception->signature == MagickCoreSignature);
1680   cubemap=MagickFalse,
1681   volume=MagickFalse,
1682   read_mipmaps=MagickFalse;
1683   image=AcquireImage(image_info,exception);
1684   status=OpenBlob(image_info,image,ReadBinaryBlobMode,exception);
1685   if (status == MagickFalse)
1686     {
1687       image=DestroyImageList(image);
1688       return((Image *) NULL);
1689     }
1690
1691   /*
1692     Initialize image structure.
1693   */
1694   if (ReadDDSInfo(image, &dds_info) != MagickTrue)
1695     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1696
1697   if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP)
1698     cubemap = MagickTrue;
1699
1700   if (dds_info.ddscaps2 & DDSCAPS2_VOLUME && dds_info.depth > 0)
1701     volume = MagickTrue;
1702
1703   (void) SeekBlob(image, 128, SEEK_SET);
1704
1705   /*
1706     Determine pixel format
1707   */
1708   if (dds_info.pixelformat.flags & DDPF_RGB)
1709     {
1710       compression = NoCompression;
1711       if (dds_info.pixelformat.flags & DDPF_ALPHAPIXELS)
1712         {
1713           alpha_trait = BlendPixelTrait;
1714           decoder = ReadUncompressedRGBA;
1715         }
1716       else
1717         {
1718           alpha_trait = UndefinedPixelTrait;
1719           decoder = ReadUncompressedRGB;
1720         }
1721     }
1722   else if (dds_info.pixelformat.flags & DDPF_LUMINANCE)
1723    {
1724       compression = NoCompression;
1725       if (dds_info.pixelformat.flags & DDPF_ALPHAPIXELS)
1726         {
1727           /* Not sure how to handle this */
1728           ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1729         }
1730       else
1731         {
1732           alpha_trait = UndefinedPixelTrait;
1733           decoder = ReadUncompressedRGB;
1734         }
1735     }
1736   else if (dds_info.pixelformat.flags & DDPF_FOURCC)
1737     {
1738       switch (dds_info.pixelformat.fourcc)
1739       {
1740         case FOURCC_DXT1:
1741         {
1742           alpha_trait = UndefinedPixelTrait;
1743           compression = DXT1Compression;
1744           decoder = ReadDXT1;
1745           break;
1746         }
1747         case FOURCC_DXT3:
1748         {
1749           alpha_trait = BlendPixelTrait;
1750           compression = DXT3Compression;
1751           decoder = ReadDXT3;
1752           break;
1753         }
1754         case FOURCC_DXT5:
1755         {
1756           alpha_trait = BlendPixelTrait;
1757           compression = DXT5Compression;
1758           decoder = ReadDXT5;
1759           break;
1760         }
1761         default:
1762         {
1763           /* Unknown FOURCC */
1764           ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1765         }
1766       }
1767     }
1768   else
1769     {
1770       /* Neither compressed nor uncompressed... thus unsupported */
1771       ThrowReaderException(CorruptImageError, "ImageTypeNotSupported");
1772     }
1773
1774   num_images = 1;
1775   if (cubemap)
1776     {
1777       /*
1778         Determine number of faces defined in the cubemap
1779       */
1780       num_images = 0;
1781       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEX) num_images++;
1782       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEX) num_images++;
1783       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEY) num_images++;
1784       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEY) num_images++;
1785       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_POSITIVEZ) num_images++;
1786       if (dds_info.ddscaps2 & DDSCAPS2_CUBEMAP_NEGATIVEZ) num_images++;
1787     }
1788
1789   if (volume)
1790     num_images = dds_info.depth;
1791
1792   if ((num_images == 0) || (num_images > GetBlobSize(image)))
1793     ThrowReaderException(CorruptImageError,"ImproperImageHeader");
1794
1795   if (AcquireMagickResource(ListLengthResource,num_images) == MagickFalse)
1796     ThrowReaderException(ResourceLimitError,"ListLengthExceedsLimit");
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     (void) SetImageBackgroundColor(image,exception);
1831     status=(decoder)(image_info,image,&dds_info,read_mipmaps,exception);
1832     if (status == MagickFalse)
1833       {
1834         (void) CloseBlob(image);
1835         return(GetFirstImageInList(image));
1836       }
1837   }
1838   (void) CloseBlob(image);
1839   return(GetFirstImageInList(image));
1840 }
1841
1842 static MagickBooleanType ReadDDSInfo(Image *image, DDSInfo *dds_info)
1843 {
1844   size_t
1845     hdr_size,
1846     required;
1847
1848   /* Seek to start of header */
1849   (void) SeekBlob(image, 4, SEEK_SET);
1850
1851   /* Check header field */
1852   hdr_size = ReadBlobLSBLong(image);
1853   if (hdr_size != 124)
1854     return MagickFalse;
1855
1856   /* Fill in DDS info struct */
1857   dds_info->flags = ReadBlobLSBLong(image);
1858
1859   /* Check required flags */
1860   required=(size_t) (DDSD_WIDTH | DDSD_HEIGHT | DDSD_PIXELFORMAT);
1861   if ((dds_info->flags & required) != required)
1862     return MagickFalse;
1863
1864   dds_info->height = ReadBlobLSBLong(image);
1865   dds_info->width = ReadBlobLSBLong(image);
1866   dds_info->pitchOrLinearSize = ReadBlobLSBLong(image);
1867   dds_info->depth = ReadBlobLSBLong(image);
1868   dds_info->mipmapcount = ReadBlobLSBLong(image);
1869
1870   (void) SeekBlob(image, 44, SEEK_CUR);   /* reserved region of 11 DWORDs */
1871
1872   /* Read pixel format structure */
1873   hdr_size = ReadBlobLSBLong(image);
1874   if (hdr_size != 32)
1875     return MagickFalse;
1876
1877   dds_info->pixelformat.flags = ReadBlobLSBLong(image);
1878   dds_info->pixelformat.fourcc = ReadBlobLSBLong(image);
1879   dds_info->pixelformat.rgb_bitcount = ReadBlobLSBLong(image);
1880   dds_info->pixelformat.r_bitmask = ReadBlobLSBLong(image);
1881   dds_info->pixelformat.g_bitmask = ReadBlobLSBLong(image);
1882   dds_info->pixelformat.b_bitmask = ReadBlobLSBLong(image);
1883   dds_info->pixelformat.alpha_bitmask = ReadBlobLSBLong(image);
1884
1885   dds_info->ddscaps1 = ReadBlobLSBLong(image);
1886   dds_info->ddscaps2 = ReadBlobLSBLong(image);
1887   (void) SeekBlob(image, 12, SEEK_CUR); /* 3 reserved DWORDs */
1888
1889   return MagickTrue;
1890 }
1891
1892 static MagickBooleanType SetDXT1Pixels(Image *image,ssize_t x,ssize_t y,
1893   DDSColors colors,size_t bits,Quantum *q)
1894 {
1895   register ssize_t
1896     i;
1897
1898   ssize_t
1899     j;
1900
1901   unsigned char
1902     code;
1903
1904   for (j = 0; j < 4; j++)
1905   {
1906     for (i = 0; i < 4; i++)
1907     {
1908       if ((x + i) < (ssize_t) image->columns &&
1909           (y + j) < (ssize_t) image->rows)
1910         {
1911           code=(unsigned char) ((bits >> ((j*4+i)*2)) & 0x3);
1912           SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
1913           SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
1914           SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
1915           SetPixelOpacity(image,ScaleCharToQuantum(colors.a[code]),q);
1916           if ((colors.a[code] != 0) &&
1917               (image->alpha_trait == UndefinedPixelTrait))
1918             return(MagickFalse);
1919           q+=GetPixelChannels(image);
1920         }
1921     }
1922   }
1923   return(MagickTrue);
1924 }
1925
1926 static MagickBooleanType ReadMipmaps(const ImageInfo *image_info,Image *image,
1927   DDSInfo *dds_info,DDSPixelDecoder decoder,ExceptionInfo *exception)
1928 {
1929   MagickBooleanType
1930     status;
1931
1932   /*
1933     Only skip mipmaps for textures and cube maps
1934   */
1935   if (EOFBlob(image) != MagickFalse)
1936     {
1937       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
1938         image->filename);
1939       return(MagickFalse);
1940     }
1941   status=MagickTrue;
1942   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
1943       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
1944           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
1945     {
1946       register ssize_t
1947         i;
1948
1949       size_t
1950         h,
1951         w;
1952
1953       w=DIV2(dds_info->width);
1954       h=DIV2(dds_info->height);
1955
1956       /*
1957         Mipmapcount includes the main image, so start from one
1958       */
1959       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
1960       {
1961         AcquireNextImage(image_info,image,exception);
1962         if (GetNextImageInList(image) == (Image *) NULL)
1963           return(MagickFalse);
1964         image=SyncNextImageInList(image);
1965         status=SetImageExtent(image,w,h,exception);
1966         if (status == MagickFalse)
1967           break;
1968         status=decoder(image,dds_info,exception);
1969         if (status == MagickFalse)
1970           break;
1971         if ((w == 1) && (h == 1))
1972           break;
1973
1974         w=DIV2(w);
1975         h=DIV2(h);
1976       }
1977     }
1978   return(status);
1979 }
1980
1981 static MagickBooleanType ReadDXT1Pixels(Image *image,
1982   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
1983 {
1984   DDSColors
1985     colors;
1986
1987   register Quantum
1988     *q;
1989
1990   register ssize_t
1991     x;
1992
1993   size_t
1994     bits;
1995
1996   ssize_t
1997     y;
1998
1999   unsigned short
2000     c0,
2001     c1;
2002
2003   magick_unreferenced(dds_info);
2004   for (y = 0; y < (ssize_t) image->rows; y += 4)
2005   {
2006     for (x = 0; x < (ssize_t) image->columns; x += 4)
2007     {
2008       /* Get 4x4 patch of pixels to write on */
2009       q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2010         MagickMin(4,image->rows-y),exception);
2011
2012       if (q == (Quantum *) NULL)
2013         return(MagickFalse);
2014
2015       /* Read 8 bytes of data from the image */
2016       c0=ReadBlobLSBShort(image);
2017       c1=ReadBlobLSBShort(image);
2018       bits=ReadBlobLSBLong(image);
2019
2020       CalculateColors(c0,c1,&colors,MagickFalse);
2021       if (EOFBlob(image) != MagickFalse)
2022         return(MagickFalse);
2023
2024       /* Write the pixels */
2025       if (SetDXT1Pixels(image,x,y,colors,bits,q) == MagickFalse)
2026         {
2027           /* Correct alpha */
2028           SetImageAlpha(image,QuantumRange,exception);
2029           q=QueueAuthenticPixels(image,x,y,MagickMin(4,image->columns-x),
2030             MagickMin(4,image->rows-y),exception);
2031           if (q != (Quantum *) NULL)
2032             SetDXT1Pixels(image,x,y,colors,bits,q);
2033         }
2034       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2035         return(MagickFalse);
2036     }
2037     if (EOFBlob(image) != MagickFalse)
2038       return(MagickFalse);
2039   }
2040   return(MagickTrue);
2041 }
2042
2043 static MagickBooleanType ReadDXT1(const ImageInfo *image_info,Image *image,
2044   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2045   ExceptionInfo *exception)
2046 {
2047   if (ReadDXT1Pixels(image,dds_info,exception) == MagickFalse)
2048     return(MagickFalse);
2049
2050   if (read_mipmaps != MagickFalse)
2051     return(ReadMipmaps(image_info,image,dds_info,ReadDXT1Pixels,exception));
2052   else
2053     return(SkipDXTMipmaps(image,dds_info,8,exception));
2054 }
2055
2056 static MagickBooleanType ReadDXT3Pixels(Image *image,
2057   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2058 {
2059   DDSColors
2060     colors;
2061
2062   register Quantum
2063     *q;
2064
2065   register ssize_t
2066     i,
2067     x;
2068
2069   unsigned char
2070     alpha;
2071
2072   size_t
2073     a0,
2074     a1,
2075     bits,
2076     code;
2077
2078   ssize_t
2079     j,
2080     y;
2081
2082   unsigned short
2083     c0,
2084     c1;
2085
2086   magick_unreferenced(dds_info);
2087   for (y = 0; y < (ssize_t) image->rows; y += 4)
2088   {
2089     for (x = 0; x < (ssize_t) image->columns; x += 4)
2090     {
2091       /* Get 4x4 patch of pixels to write on */
2092       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2093                          MagickMin(4, image->rows - y),exception);
2094
2095       if (q == (Quantum *) NULL)
2096         return(MagickFalse);
2097
2098       /* Read alpha values (8 bytes) */
2099       a0 = ReadBlobLSBLong(image);
2100       a1 = ReadBlobLSBLong(image);
2101
2102       /* Read 8 bytes of data from the image */
2103       c0 = ReadBlobLSBShort(image);
2104       c1 = ReadBlobLSBShort(image);
2105       bits = ReadBlobLSBLong(image);
2106
2107       CalculateColors(c0, c1, &colors, MagickTrue);
2108
2109       if (EOFBlob(image) != MagickFalse)
2110         return(MagickFalse);
2111
2112       /* Write the pixels */
2113       for (j = 0; j < 4; j++)
2114       {
2115         for (i = 0; i < 4; i++)
2116         {
2117           if ((x + i) < (ssize_t) image->columns && (y + j) < (ssize_t) image->rows)
2118             {
2119               code = (bits >> ((4*j+i)*2)) & 0x3;
2120               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2121               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2122               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2123               /*
2124                 Extract alpha value: multiply 0..15 by 17 to get range 0..255
2125               */
2126               if (j < 2)
2127                 alpha = 17U * (unsigned char) ((a0 >> (4*(4*j+i))) & 0xf);
2128               else
2129                 alpha = 17U * (unsigned char) ((a1 >> (4*(4*(j-2)+i))) & 0xf);
2130               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2131               q+=GetPixelChannels(image);
2132             }
2133         }
2134       }
2135       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2136         return(MagickFalse);
2137     }
2138     if (EOFBlob(image) != MagickFalse)
2139       return(MagickFalse);
2140   }
2141   return(MagickTrue);
2142 }
2143
2144 static MagickBooleanType ReadDXT3(const ImageInfo *image_info,Image *image,
2145   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2146   ExceptionInfo *exception)
2147 {
2148   if (ReadDXT3Pixels(image,dds_info,exception) == MagickFalse)
2149     return(MagickFalse);
2150
2151   if (read_mipmaps != MagickFalse)
2152     return(ReadMipmaps(image_info,image,dds_info,ReadDXT3Pixels,exception));
2153   else
2154     return(SkipDXTMipmaps(image,dds_info,16,exception));
2155 }
2156
2157 static MagickBooleanType ReadDXT5Pixels(Image *image,
2158   DDSInfo *magick_unused(dds_info),ExceptionInfo *exception)
2159 {
2160   DDSColors
2161     colors;
2162
2163   MagickSizeType
2164     alpha_bits;
2165
2166   register Quantum
2167     *q;
2168
2169   register ssize_t
2170     i,
2171     x;
2172
2173   unsigned char
2174     a0,
2175     a1;
2176
2177   size_t
2178     alpha,
2179     bits,
2180     code,
2181     alpha_code;
2182
2183   ssize_t
2184     j,
2185     y;
2186
2187   unsigned short
2188     c0,
2189     c1;
2190
2191   magick_unreferenced(dds_info);
2192   for (y = 0; y < (ssize_t) image->rows; y += 4)
2193   {
2194     for (x = 0; x < (ssize_t) image->columns; x += 4)
2195     {
2196       /* Get 4x4 patch of pixels to write on */
2197       q = QueueAuthenticPixels(image, x, y, MagickMin(4, image->columns - x),
2198                          MagickMin(4, image->rows - y),exception);
2199
2200       if (q == (Quantum *) NULL)
2201         return(MagickFalse);
2202
2203       /* Read alpha values (8 bytes) */
2204       a0 = (unsigned char) ReadBlobByte(image);
2205       a1 = (unsigned char) ReadBlobByte(image);
2206
2207       alpha_bits = (MagickSizeType)ReadBlobLSBLong(image);
2208       alpha_bits = alpha_bits | ((MagickSizeType)ReadBlobLSBShort(image) << 32);
2209
2210       /* Read 8 bytes of data from the image */
2211       c0 = ReadBlobLSBShort(image);
2212       c1 = ReadBlobLSBShort(image);
2213       bits = ReadBlobLSBLong(image);
2214
2215       CalculateColors(c0, c1, &colors, MagickTrue);
2216       if (EOFBlob(image) != MagickFalse)
2217         return(MagickFalse);
2218
2219       /* Write the pixels */
2220       for (j = 0; j < 4; j++)
2221       {
2222         for (i = 0; i < 4; i++)
2223         {
2224           if ((x + i) < (ssize_t) image->columns &&
2225               (y + j) < (ssize_t) image->rows)
2226             {
2227               code = (bits >> ((4*j+i)*2)) & 0x3;
2228               SetPixelRed(image,ScaleCharToQuantum(colors.r[code]),q);
2229               SetPixelGreen(image,ScaleCharToQuantum(colors.g[code]),q);
2230               SetPixelBlue(image,ScaleCharToQuantum(colors.b[code]),q);
2231               /* Extract alpha value */
2232               alpha_code = (size_t) (alpha_bits >> (3*(4*j+i))) & 0x7;
2233               if (alpha_code == 0)
2234                 alpha = a0;
2235               else if (alpha_code == 1)
2236                 alpha = a1;
2237               else if (a0 > a1)
2238                 alpha = ((8-alpha_code) * a0 + (alpha_code-1) * a1) / 7;
2239               else if (alpha_code == 6)
2240                 alpha = 0;
2241               else if (alpha_code == 7)
2242                 alpha = 255;
2243               else
2244                 alpha = (((6-alpha_code) * a0 + (alpha_code-1) * a1) / 5);
2245               SetPixelAlpha(image,ScaleCharToQuantum((unsigned char) alpha),q);
2246               q+=GetPixelChannels(image);
2247             }
2248         }
2249       }
2250       if (SyncAuthenticPixels(image,exception) == MagickFalse)
2251         return(MagickFalse);
2252     }
2253     if (EOFBlob(image) != MagickFalse)
2254       return(MagickFalse);
2255   }
2256   return(MagickTrue);
2257 }
2258
2259 static MagickBooleanType ReadDXT5(const ImageInfo *image_info,Image *image,
2260   DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2261   ExceptionInfo *exception)
2262 {
2263   if (ReadDXT5Pixels(image,dds_info,exception) == MagickFalse)
2264     return(MagickFalse);
2265
2266   if (read_mipmaps != MagickFalse)
2267     return(ReadMipmaps(image_info,image,dds_info,ReadDXT5Pixels,exception));
2268   else
2269     return(SkipDXTMipmaps(image,dds_info,16,exception));
2270 }
2271
2272 static MagickBooleanType ReadUncompressedRGBPixels(Image *image,
2273   DDSInfo *dds_info,ExceptionInfo *exception)
2274 {
2275   register Quantum
2276     *q;
2277
2278   ssize_t
2279     x, y;
2280
2281   unsigned short
2282     color;
2283
2284   for (y = 0; y < (ssize_t) image->rows; y++)
2285   {
2286     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2287
2288     if (q == (Quantum *) NULL)
2289       return(MagickFalse);
2290
2291     for (x = 0; x < (ssize_t) image->columns; x++)
2292     {
2293       if (dds_info->pixelformat.rgb_bitcount == 8)
2294         SetPixelGray(image,ScaleCharToQuantum(ReadBlobByte(image)),q);
2295       else if (dds_info->pixelformat.rgb_bitcount == 16)
2296         {
2297            color=ReadBlobShort(image);
2298            SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2299              (((color >> 11)/31.0)*255)),q);
2300            SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2301              ((((unsigned short)(color << 5) >> 10)/63.0)*255)),q);
2302            SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2303              ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2304         }
2305       else
2306         {
2307           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2308             ReadBlobByte(image)),q);
2309           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2310             ReadBlobByte(image)),q);
2311           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2312             ReadBlobByte(image)),q);
2313           if (dds_info->pixelformat.rgb_bitcount == 32)
2314             (void) ReadBlobByte(image);
2315         }
2316       q+=GetPixelChannels(image);
2317     }
2318     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2319       return(MagickFalse);
2320     if (EOFBlob(image) != MagickFalse)
2321       return(MagickFalse);
2322   }
2323   return(MagickTrue);
2324 }
2325
2326 static MagickBooleanType ReadUncompressedRGB(const ImageInfo *image_info,
2327   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2328   ExceptionInfo *exception)
2329 {
2330   if (dds_info->pixelformat.rgb_bitcount == 8)
2331     (void) SetImageType(image,GrayscaleType,exception);
2332   else if (dds_info->pixelformat.rgb_bitcount == 16 && !IsBitMask(
2333     dds_info->pixelformat,0xf800,0x07e0,0x001f,0x0000))
2334     ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2335       image->filename);
2336
2337   if (ReadUncompressedRGBPixels(image,dds_info,exception) == MagickFalse)
2338     return(MagickFalse);
2339
2340   if (read_mipmaps != MagickFalse)
2341     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBPixels,
2342       exception));
2343   else
2344     return(SkipRGBMipmaps(image,dds_info,3,exception));
2345 }
2346
2347 static MagickBooleanType ReadUncompressedRGBAPixels(Image *image,
2348   DDSInfo *dds_info,ExceptionInfo *exception)
2349 {
2350   register Quantum
2351     *q;
2352
2353   ssize_t
2354     alphaBits,
2355     x,
2356     y;
2357
2358   unsigned short
2359     color;
2360
2361   alphaBits=0;
2362   if (dds_info->pixelformat.rgb_bitcount == 16)
2363     {
2364       if (IsBitMask(dds_info->pixelformat,0x7c00,0x03e0,0x001f,0x8000))
2365         alphaBits=1;
2366       else if (IsBitMask(dds_info->pixelformat,0x00ff,0x00ff,0x00ff,0xff00))
2367         {
2368           alphaBits=2;
2369           (void) SetImageType(image,GrayscaleAlphaType,exception);
2370         }
2371       else if (IsBitMask(dds_info->pixelformat,0x0f00,0x00f0,0x000f,0xf000))
2372         alphaBits=4;
2373       else
2374         ThrowBinaryException(CorruptImageError,"ImageTypeNotSupported",
2375           image->filename);
2376     }
2377
2378   for (y = 0; y < (ssize_t) image->rows; y++)
2379   {
2380     q = QueueAuthenticPixels(image, 0, y, image->columns, 1,exception);
2381
2382     if (q == (Quantum *) NULL)
2383       return(MagickFalse);
2384
2385     for (x = 0; x < (ssize_t) image->columns; x++)
2386     {
2387       if (dds_info->pixelformat.rgb_bitcount == 16)
2388         {
2389            color=ReadBlobShort(image);
2390            if (alphaBits == 1)
2391              {
2392                SetPixelAlpha(image,(color & (1 << 15)) ? QuantumRange : 0,q);
2393                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2394                  ((((unsigned short)(color << 1) >> 11)/31.0)*255)),q);
2395                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2396                  ((((unsigned short)(color << 6) >> 11)/31.0)*255)),q);
2397                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2398                  ((((unsigned short)(color << 11) >> 11)/31.0)*255)),q);
2399              }
2400           else if (alphaBits == 2)
2401             {
2402                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2403                  (color >> 8)),q);
2404                SetPixelGray(image,ScaleCharToQuantum((unsigned char)color),q);
2405             }
2406           else
2407             {
2408                SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2409                  (((color >> 12)/15.0)*255)),q);
2410                SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2411                  ((((unsigned short)(color << 4) >> 12)/15.0)*255)),q);
2412                SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2413                  ((((unsigned short)(color << 8) >> 12)/15.0)*255)),q);
2414                SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2415                  ((((unsigned short)(color << 12) >> 12)/15.0)*255)),q);
2416             }
2417         }
2418       else
2419         {
2420           SetPixelBlue(image,ScaleCharToQuantum((unsigned char)
2421             ReadBlobByte(image)),q);
2422           SetPixelGreen(image,ScaleCharToQuantum((unsigned char)
2423             ReadBlobByte(image)),q);
2424           SetPixelRed(image,ScaleCharToQuantum((unsigned char)
2425             ReadBlobByte(image)),q);
2426           SetPixelAlpha(image,ScaleCharToQuantum((unsigned char)
2427             ReadBlobByte(image)),q);
2428         }
2429       q+=GetPixelChannels(image);
2430     }
2431     if (SyncAuthenticPixels(image,exception) == MagickFalse)
2432       return(MagickFalse);
2433     if (EOFBlob(image) != MagickFalse)
2434       return(MagickFalse);
2435   }
2436   return(MagickTrue);
2437 }
2438
2439 static MagickBooleanType ReadUncompressedRGBA(const ImageInfo *image_info,
2440   Image *image,DDSInfo *dds_info,const MagickBooleanType read_mipmaps,
2441   ExceptionInfo *exception)
2442 {
2443   if (ReadUncompressedRGBAPixels(image,dds_info,exception) == MagickFalse)
2444     return(MagickFalse);
2445
2446   if (read_mipmaps != MagickFalse)
2447     return(ReadMipmaps(image_info,image,dds_info,ReadUncompressedRGBAPixels,
2448       exception));
2449   else
2450     return(SkipRGBMipmaps(image,dds_info,4,exception));
2451 }
2452 \f
2453 /*
2454 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2455 %                                                                             %
2456 %                                                                             %
2457 %                                                                             %
2458 %   R e g i s t e r D D S I m a g e                                           %
2459 %                                                                             %
2460 %                                                                             %
2461 %                                                                             %
2462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2463 %
2464 %  RegisterDDSImage() adds attributes for the DDS image format to
2465 %  the list of supported formats.  The attributes include the image format
2466 %  tag, a method to read and/or write the format, whether the format
2467 %  supports the saving of more than one frame to the same file or blob,
2468 %  whether the format supports native in-memory I/O, and a brief
2469 %  description of the format.
2470 %
2471 %  The format of the RegisterDDSImage method is:
2472 %
2473 %      RegisterDDSImage(void)
2474 %
2475 */
2476 ModuleExport size_t RegisterDDSImage(void)
2477 {
2478   MagickInfo
2479     *entry;
2480
2481   entry = AcquireMagickInfo("DDS","DDS","Microsoft DirectDraw Surface");
2482   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2483   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2484   entry->magick = (IsImageFormatHandler *) IsDDS;
2485   entry->flags|=CoderDecoderSeekableStreamFlag;
2486   (void) RegisterMagickInfo(entry);
2487   entry = AcquireMagickInfo("DDS","DXT1","Microsoft DirectDraw Surface");
2488   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2489   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2490   entry->magick = (IsImageFormatHandler *) IsDDS;
2491   entry->flags|=CoderDecoderSeekableStreamFlag;
2492   (void) RegisterMagickInfo(entry);
2493   entry = AcquireMagickInfo("DDS","DXT5","Microsoft DirectDraw Surface");
2494   entry->decoder = (DecodeImageHandler *) ReadDDSImage;
2495   entry->encoder = (EncodeImageHandler *) WriteDDSImage;
2496   entry->magick = (IsImageFormatHandler *) IsDDS;
2497   entry->flags|=CoderDecoderSeekableStreamFlag;
2498   (void) RegisterMagickInfo(entry);
2499   return(MagickImageCoderSignature);
2500 }
2501
2502 static void RemapIndices(const ssize_t *map, const unsigned char *source,
2503   unsigned char *target)
2504 {
2505   register ssize_t
2506     i;
2507
2508   for (i = 0; i < 16; i++)
2509   {
2510     if (map[i] == -1)
2511       target[i] = 3;
2512     else
2513       target[i] = source[map[i]];
2514   }
2515 }
2516
2517 /*
2518   Skip the mipmap images for compressed (DXTn) dds files
2519 */
2520 static MagickBooleanType SkipDXTMipmaps(Image *image,DDSInfo *dds_info,
2521   int texel_size,ExceptionInfo *exception)
2522 {
2523   /*
2524     Only skip mipmaps for textures and cube maps
2525   */
2526   if (EOFBlob(image) != MagickFalse)
2527     {
2528       ThrowFileException(exception,CorruptImageWarning,"UnexpectedEndOfFile",
2529         image->filename);
2530       return(MagickFalse);
2531     }
2532   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2533       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2534           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2535     {
2536       MagickOffsetType
2537         offset;
2538
2539       register ssize_t
2540         i;
2541
2542       size_t
2543         h,
2544         w;
2545
2546       w=DIV2(dds_info->width);
2547       h=DIV2(dds_info->height);
2548
2549       /*
2550         Mipmapcount includes the main image, so start from one
2551       */
2552       for (i = 1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2553       {
2554         offset=(MagickOffsetType)((w+3)/4)*((h+3)/4)*texel_size;
2555         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2556           break;
2557         w=DIV2(w);
2558         h=DIV2(h);
2559         if ((w == 1) && (h == 1))
2560           break;
2561       }
2562     }
2563   return(MagickTrue);
2564 }
2565
2566 /*
2567   Skip the mipmap images for uncompressed (RGB or RGBA) dds files
2568 */
2569 static MagickBooleanType SkipRGBMipmaps(Image *image,DDSInfo *dds_info,
2570   int pixel_size,ExceptionInfo *exception)
2571 {
2572   /*
2573     Only skip mipmaps for textures and cube maps
2574   */
2575   if (EOFBlob(image) != MagickFalse)
2576     {
2577       ThrowFileException(exception,CorruptImageError,"UnexpectedEndOfFile",
2578         image->filename);
2579       return(MagickFalse);
2580     }
2581   if (dds_info->ddscaps1 & DDSCAPS_MIPMAP
2582       && (dds_info->ddscaps1 & DDSCAPS_TEXTURE
2583           || dds_info->ddscaps2 & DDSCAPS2_CUBEMAP))
2584     {
2585       MagickOffsetType
2586         offset;
2587
2588       register ssize_t
2589         i;
2590
2591       size_t
2592         h,
2593         w;
2594
2595       w=DIV2(dds_info->width);
2596       h=DIV2(dds_info->height);
2597
2598       /*
2599         Mipmapcount includes the main image, so start from one
2600       */
2601       for (i=1; (i < (ssize_t) dds_info->mipmapcount) && w && h; i++)
2602       {
2603         offset=(MagickOffsetType)w*h*pixel_size;
2604         if (SeekBlob(image,offset,SEEK_CUR) < 0)
2605           break;
2606         w=DIV2(w);
2607         h=DIV2(h);
2608         if ((w == 1) && (h == 1))
2609           break;
2610       }
2611     }
2612   return(MagickTrue);
2613 }
2614 \f
2615 /*
2616 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2617 %                                                                             %
2618 %                                                                             %
2619 %                                                                             %
2620 %   U n r e g i s t e r D D S I m a g e                                       %
2621 %                                                                             %
2622 %                                                                             %
2623 %                                                                             %
2624 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2625 %
2626 %  UnregisterDDSImage() removes format registrations made by the
2627 %  DDS module from the list of supported formats.
2628 %
2629 %  The format of the UnregisterDDSImage method is:
2630 %
2631 %      UnregisterDDSImage(void)
2632 %
2633 */
2634 ModuleExport void UnregisterDDSImage(void)
2635 {
2636   (void) UnregisterMagickInfo("DDS");
2637   (void) UnregisterMagickInfo("DXT1");
2638   (void) UnregisterMagickInfo("DXT5");
2639 }
2640
2641 static void WriteAlphas(Image *image, const ssize_t *alphas, size_t min5,
2642   size_t max5, size_t min7, size_t max7)
2643 {
2644   register ssize_t
2645     i;
2646
2647   size_t
2648     err5,
2649     err7,
2650     j;
2651
2652   unsigned char
2653     indices5[16],
2654     indices7[16];
2655
2656   FixRange(min5,max5,5);
2657   err5 = CompressAlpha(min5,max5,5,alphas,indices5);
2658
2659   FixRange(min7,max7,7);
2660   err7 = CompressAlpha(min7,max7,7,alphas,indices7);
2661
2662   if (err7 < err5)
2663   {
2664     for (i=0; i < 16; i++)
2665     {
2666       unsigned char
2667         index;
2668
2669       index = indices7[i];
2670       if( index == 0 )
2671         indices5[i] = 1;
2672       else if (index == 1)
2673         indices5[i] = 0;
2674       else
2675         indices5[i] = 9 - index;
2676     }
2677
2678     min5 = max7;
2679     max5 = min7;
2680   }
2681
2682   (void) WriteBlobByte(image,(unsigned char) min5);
2683   (void) WriteBlobByte(image,(unsigned char) max5);
2684
2685   for(i=0; i < 2; i++)
2686   {
2687     size_t
2688       value = 0;
2689
2690     for (j=0; j < 8; j++)
2691     {
2692       size_t index = (size_t) indices5[j + i*8];
2693       value |= ( index << 3*j );
2694     }
2695
2696     for (j=0; j < 3; j++)
2697     {
2698       size_t byte = (value >> 8*j) & 0xff;
2699       (void) WriteBlobByte(image,(unsigned char) byte);
2700     }
2701   }
2702 }
2703
2704 static void WriteCompressed(Image *image, const size_t count,
2705   DDSVector4 *points, const ssize_t *map, const MagickBooleanType clusterFit)
2706 {
2707   float
2708     covariance[16];
2709
2710   DDSVector3
2711     end,
2712     principle,
2713     start;
2714
2715   DDSVector4
2716     metric;
2717
2718   unsigned char
2719     indices[16];
2720
2721   VectorInit(metric,1.0f);
2722   VectorInit3(start,0.0f);
2723   VectorInit3(end,0.0f);
2724
2725   ComputeWeightedCovariance(count,points,covariance);
2726   ComputePrincipleComponent(covariance,&principle);
2727
2728   if ((clusterFit == MagickFalse) || (count == 0))
2729     CompressRangeFit(count,points,map,principle,metric,&start,&end,indices);
2730   else
2731     CompressClusterFit(count,points,map,principle,metric,&start,&end,indices);
2732
2733   WriteIndices(image,start,end,indices);
2734 }
2735
2736 /*
2737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2738 %                                                                             %
2739 %                                                                             %
2740 %                                                                             %
2741 %   W r i t e D D S I m a g e                                                 %
2742 %                                                                             %
2743 %                                                                             %
2744 %                                                                             %
2745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2746 %
2747 %  WriteDDSImage() writes a DirectDraw Surface image file in the DXT5 format.
2748 %
2749 %  The format of the WriteBMPImage method is:
2750 %
2751 %     MagickBooleanType WriteDDSImage(const ImageInfo *image_info,Image *image)
2752 %
2753 %  A description of each parameter follows.
2754 %
2755 %    o image_info: the image info.
2756 %
2757 %    o image:  The image.
2758 %
2759 */
2760 static MagickBooleanType WriteDDSImage(const ImageInfo *image_info,
2761   Image *image, ExceptionInfo *exception)
2762 {
2763   const char
2764     *option;
2765
2766   size_t
2767     compression,
2768     columns,
2769     maxMipmaps,
2770     mipmaps,
2771     pixelFormat,
2772     rows;
2773
2774   MagickBooleanType
2775     clusterFit,
2776     fromlist,
2777     status,
2778     weightByAlpha;
2779
2780   assert(image_info != (const ImageInfo *) NULL);
2781   assert(image_info->signature == MagickCoreSignature);
2782   assert(image != (Image *) NULL);
2783   assert(image->signature == MagickCoreSignature);
2784   if (image->debug != MagickFalse)
2785     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2786   status=OpenBlob(image_info,image,WriteBinaryBlobMode,exception);
2787   if (status == MagickFalse)
2788     return(status);
2789   (void) TransformImageColorspace(image,sRGBColorspace,exception);
2790   pixelFormat=DDPF_FOURCC;
2791   compression=FOURCC_DXT5;
2792
2793   if (image->alpha_trait == UndefinedPixelTrait)
2794     compression=FOURCC_DXT1;
2795
2796   if (LocaleCompare(image_info->magick,"dxt1") == 0)
2797     compression=FOURCC_DXT1;
2798
2799   option=GetImageOption(image_info,"dds:compression");
2800   if (option != (char *) NULL)
2801     {
2802        if (LocaleCompare(option,"dxt1") == 0)
2803          compression=FOURCC_DXT1;
2804        if (LocaleCompare(option,"none") == 0)
2805          pixelFormat=DDPF_RGB;
2806     }
2807
2808   clusterFit=MagickFalse;
2809   weightByAlpha=MagickFalse;
2810
2811   if (pixelFormat == DDPF_FOURCC)
2812     {
2813       option=GetImageOption(image_info,"dds:cluster-fit");
2814       if (IsStringTrue(option) != MagickFalse)
2815         {
2816           clusterFit=MagickTrue;
2817           if (compression != FOURCC_DXT1)
2818             {
2819               option=GetImageOption(image_info,"dds:weight-by-alpha");
2820               if (IsStringTrue(option) != MagickFalse)
2821                 weightByAlpha=MagickTrue;
2822             }
2823         }
2824     }
2825
2826   mipmaps=0;
2827   fromlist=MagickFalse;
2828   option=GetImageOption(image_info,"dds:mipmaps");
2829   if (option != (char *) NULL)
2830     {
2831       if (LocaleNCompare(option,"fromlist",8) == 0)
2832         {
2833           Image
2834             *next;
2835
2836           fromlist=MagickTrue;
2837           next=image->next;
2838           while(next != (Image *) NULL)
2839           {
2840             mipmaps++;
2841             next=next->next;
2842           }
2843         }
2844     }
2845
2846   if ((mipmaps == 0) &&
2847       ((image->columns & (image->columns - 1)) == 0) &&
2848       ((image->rows & (image->rows - 1)) == 0))
2849     {
2850       maxMipmaps=SIZE_MAX;
2851       if (option != (char *) NULL)
2852         maxMipmaps=StringToUnsignedLong(option);
2853
2854       if (maxMipmaps != 0)
2855         {
2856           columns=image->columns;
2857           rows=image->rows;
2858           while ((columns != 1 || rows != 1) && mipmaps != maxMipmaps)
2859           {
2860             columns=DIV2(columns);
2861             rows=DIV2(rows);
2862             mipmaps++;
2863           }
2864         }
2865     }
2866
2867   WriteDDSInfo(image,pixelFormat,compression,mipmaps);
2868
2869   WriteImageData(image,pixelFormat,compression,clusterFit,weightByAlpha,
2870     exception);
2871
2872   if ((mipmaps > 0) && (WriteMipmaps(image,image_info,pixelFormat,compression,
2873        mipmaps,fromlist,clusterFit,weightByAlpha,exception) == MagickFalse))
2874     return(MagickFalse);
2875
2876   (void) CloseBlob(image);
2877   return(MagickTrue);
2878 }
2879
2880 static void WriteDDSInfo(Image *image, const size_t pixelFormat,
2881   const size_t compression, const size_t mipmaps)
2882 {
2883   char
2884     software[MagickPathExtent];
2885
2886   register ssize_t
2887     i;
2888
2889   unsigned int
2890     format,
2891     caps,
2892     flags;
2893
2894   flags=(unsigned int) (DDSD_CAPS | DDSD_WIDTH | DDSD_HEIGHT |
2895     DDSD_PIXELFORMAT);
2896   caps=(unsigned int) DDSCAPS_TEXTURE;
2897   format=(unsigned int) pixelFormat;
2898
2899   if (format == DDPF_FOURCC)
2900       flags=flags | DDSD_LINEARSIZE;
2901   else
2902       flags=flags | DDSD_PITCH;
2903
2904   if (mipmaps > 0)
2905     {
2906       flags=flags | (unsigned int) DDSD_MIPMAPCOUNT;
2907       caps=caps | (unsigned int) (DDSCAPS_MIPMAP | DDSCAPS_COMPLEX);
2908     }
2909
2910   if (format != DDPF_FOURCC && image->alpha_trait != UndefinedPixelTrait)
2911     format=format | DDPF_ALPHAPIXELS;
2912
2913   (void) WriteBlob(image,4,(unsigned char *) "DDS ");
2914   (void) WriteBlobLSBLong(image,124);
2915   (void) WriteBlobLSBLong(image,flags);
2916   (void) WriteBlobLSBLong(image,(unsigned int) image->rows);
2917   (void) WriteBlobLSBLong(image,(unsigned int) image->columns);
2918
2919   if (pixelFormat == DDPF_FOURCC)
2920     {
2921       /* Compressed DDS requires linear compressed size of first image */
2922       if (compression == FOURCC_DXT1)
2923         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2924           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*8));
2925       else /* DXT5 */
2926         (void) WriteBlobLSBLong(image,(unsigned int) (MagickMax(1,
2927           (image->columns+3)/4)*MagickMax(1,(image->rows+3)/4)*16));
2928     }
2929   else
2930     {
2931       /* Uncompressed DDS requires byte pitch of first image */
2932       if (image->alpha_trait != UndefinedPixelTrait)
2933         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 4));
2934       else
2935         (void) WriteBlobLSBLong(image,(unsigned int) (image->columns * 3));
2936     }
2937
2938   (void) WriteBlobLSBLong(image,0x00);
2939   (void) WriteBlobLSBLong(image,(unsigned int) mipmaps+1);
2940   (void) memset(software,0,sizeof(software));
2941   (void) CopyMagickString(software,"IMAGEMAGICK",MagickPathExtent);
2942   (void) WriteBlob(image,44,(unsigned char *) software);
2943
2944   (void) WriteBlobLSBLong(image,32);
2945   (void) WriteBlobLSBLong(image,format);
2946
2947   if (pixelFormat == DDPF_FOURCC)
2948     {
2949       (void) WriteBlobLSBLong(image,(unsigned int) compression);
2950       for(i=0;i < 5;i++)  /* bitcount / masks */
2951         (void) WriteBlobLSBLong(image,0x00);
2952     }
2953   else
2954     {
2955       (void) WriteBlobLSBLong(image,0x00);
2956       if (image->alpha_trait != UndefinedPixelTrait)
2957         {
2958           (void) WriteBlobLSBLong(image,32);
2959           (void) WriteBlobLSBLong(image,0xff0000);
2960           (void) WriteBlobLSBLong(image,0xff00);
2961           (void) WriteBlobLSBLong(image,0xff);
2962           (void) WriteBlobLSBLong(image,0xff000000);
2963         }
2964       else
2965         {
2966           (void) WriteBlobLSBLong(image,24);
2967           (void) WriteBlobLSBLong(image,0xff0000);
2968           (void) WriteBlobLSBLong(image,0xff00);
2969           (void) WriteBlobLSBLong(image,0xff);
2970           (void) WriteBlobLSBLong(image,0x00);
2971         }
2972     }
2973
2974   (void) WriteBlobLSBLong(image,caps);
2975   for(i=0;i < 4;i++)   /* ddscaps2 + reserved region */
2976     (void) WriteBlobLSBLong(image,0x00);
2977 }
2978
2979 static void WriteFourCC(Image *image, const size_t compression,
2980   const MagickBooleanType clusterFit, const MagickBooleanType weightByAlpha,
2981   ExceptionInfo *exception)
2982 {
2983   register ssize_t
2984     x;
2985
2986   ssize_t
2987     i,
2988     y,
2989     bx,
2990     by;
2991
2992   register const Quantum
2993     *p;
2994
2995   for (y=0; y < (ssize_t) image->rows; y+=4)
2996   {
2997     for (x=0; x < (ssize_t) image->columns; x+=4)
2998     {
2999       MagickBooleanType
3000         match;
3001
3002       DDSVector4
3003         point,
3004         points[16];
3005
3006       size_t
3007         count = 0,
3008         max5 = 0,
3009         max7 = 0,
3010         min5 = 255,
3011         min7 = 255,
3012         columns = 4,
3013         rows = 4;
3014
3015       ssize_t
3016         alphas[16],
3017         map[16];
3018
3019       unsigned char
3020         alpha;
3021
3022       if (x + columns >= image->columns)
3023         columns = image->columns - x;
3024
3025       if (y + rows >= image->rows)
3026         rows = image->rows - y;
3027
3028       p=GetVirtualPixels(image,x,y,columns,rows,exception);
3029       if (p == (const Quantum *) NULL)
3030         break;
3031
3032       for (i=0; i<16; i++)
3033       {
3034         map[i] = -1;
3035         alphas[i] = -1;
3036       }
3037
3038       for (by=0; by < (ssize_t) rows; by++)
3039       {
3040         for (bx=0; bx < (ssize_t) columns; bx++)
3041         {
3042           if (compression == FOURCC_DXT5)
3043             alpha = ScaleQuantumToChar(GetPixelAlpha(image,p));
3044           else
3045             alpha = 255;
3046
3047           if (compression == FOURCC_DXT5)
3048             {
3049               if (alpha < min7)
3050                 min7 = alpha;
3051               if (alpha > max7)
3052                 max7 = alpha;
3053               if (alpha != 0 && alpha < min5)
3054                 min5 = alpha;
3055               if (alpha != 255 && alpha > max5)
3056                 max5 = alpha;
3057             }
3058
3059           alphas[4*by + bx] = (size_t)alpha;
3060
3061           point.x = (float)ScaleQuantumToChar(GetPixelRed(image,p)) / 255.0f;
3062           point.y = (float)ScaleQuantumToChar(GetPixelGreen(image,p)) / 255.0f;
3063           point.z = (float)ScaleQuantumToChar(GetPixelBlue(image,p)) / 255.0f;
3064           point.w = weightByAlpha ? (float)(alpha + 1) / 256.0f : 1.0f;
3065           p+=GetPixelChannels(image);
3066
3067           match = MagickFalse;
3068           for (i=0; i < (ssize_t) count; i++)
3069           {
3070             if ((points[i].x == point.x) &&
3071                 (points[i].y == point.y) &&
3072                 (points[i].z == point.z) &&
3073                 (alpha       >= 128 || compression == FOURCC_DXT5))
3074               {
3075                 points[i].w += point.w;
3076                 map[4*by + bx] = i;
3077                 match = MagickTrue;
3078                 break;
3079               }
3080           }
3081
3082           if (match != MagickFalse)
3083             continue;
3084
3085           points[count].x = point.x;
3086           points[count].y = point.y;
3087           points[count].z = point.z;
3088           points[count].w = point.w;
3089           map[4*by + bx] = count;
3090           count++;
3091         }
3092       }
3093
3094       for (i=0; i < (ssize_t) count; i++)
3095         points[i].w = sqrt(points[i].w);
3096
3097       if (compression == FOURCC_DXT5)
3098         WriteAlphas(image,alphas,min5,max5,min7,max7);
3099
3100       if (count == 1)
3101         WriteSingleColorFit(image,points,map);
3102       else
3103         WriteCompressed(image,count,points,map,clusterFit);
3104     }
3105   }
3106 }
3107
3108 static void WriteImageData(Image *image, const size_t pixelFormat,
3109   const size_t compression,const MagickBooleanType clusterFit,
3110   const MagickBooleanType weightByAlpha, ExceptionInfo *exception)
3111 {
3112   if (pixelFormat == DDPF_FOURCC)
3113     WriteFourCC(image,compression,clusterFit,weightByAlpha,exception);
3114   else
3115     WriteUncompressed(image,exception);
3116 }
3117
3118 static inline size_t ClampToLimit(const float value, const size_t limit)
3119 {
3120   size_t
3121     result = (int) (value + 0.5f);
3122
3123   if (result < 0.0f)
3124     return(0);
3125   if (result > limit)
3126     return(limit);
3127   return result;
3128 }
3129
3130 static inline size_t ColorTo565(const DDSVector3 point)
3131 {
3132   size_t r = ClampToLimit(31.0f*point.x,31);
3133   size_t g = ClampToLimit(63.0f*point.y,63);
3134   size_t b = ClampToLimit(31.0f*point.z,31);
3135
3136   return (r << 11) | (g << 5) | b;
3137 }
3138
3139 static void WriteIndices(Image *image, const DDSVector3 start,
3140   const DDSVector3 end, unsigned char *indices)
3141 {
3142   register ssize_t
3143     i;
3144
3145   size_t
3146     a,
3147     b;
3148
3149   unsigned char
3150     remapped[16];
3151
3152   const unsigned char
3153     *ind;
3154
3155   a = ColorTo565(start);
3156   b = ColorTo565(end);
3157
3158   for (i=0; i<16; i++)
3159   {
3160     if( a < b )
3161       remapped[i] = (indices[i] ^ 0x1) & 0x3;
3162     else if( a == b )
3163       remapped[i] = 0;
3164     else
3165       remapped[i] = indices[i];
3166   }
3167
3168   if( a < b )
3169     Swap(a,b);
3170
3171   (void) WriteBlobByte(image,(unsigned char) (a & 0xff));
3172   (void) WriteBlobByte(image,(unsigned char) (a >> 8));
3173   (void) WriteBlobByte(image,(unsigned char) (b & 0xff));
3174   (void) WriteBlobByte(image,(unsigned char) (b >> 8));
3175
3176   for (i=0; i<4; i++)
3177   {
3178      ind = remapped + 4*i;
3179      (void) WriteBlobByte(image,ind[0] | (ind[1] << 2) | (ind[2] << 4) |
3180        (ind[3] << 6));
3181   }
3182 }
3183
3184 static MagickBooleanType WriteMipmaps(Image *image,const ImageInfo *image_info,
3185   const size_t pixelFormat,const size_t compression,const size_t mipmaps,
3186   const MagickBooleanType fromlist,const MagickBooleanType clusterFit,
3187   const MagickBooleanType weightByAlpha,ExceptionInfo *exception)
3188 {
3189   const char
3190     *option;
3191
3192   Image
3193     *mipmap_image,
3194     *resize_image;
3195
3196   MagickBooleanType
3197     fast_mipmaps,
3198     status;
3199
3200   register ssize_t
3201     i;
3202
3203   size_t
3204     columns,
3205     rows;
3206
3207   columns=DIV2(image->columns);
3208   rows=DIV2(image->rows);
3209
3210   option=GetImageOption(image_info,"dds:fast-mipmaps");
3211   fast_mipmaps=IsStringTrue(option);
3212   mipmap_image=image;
3213   resize_image=image;
3214   status=MagickTrue;
3215   for (i=0; i < (ssize_t) mipmaps; i++)
3216   {
3217     if (fromlist == MagickFalse)
3218       {
3219         mipmap_image=ResizeImage(resize_image,columns,rows,TriangleFilter,
3220           exception);
3221
3222         if (mipmap_image == (Image *) NULL)
3223           {
3224             status=MagickFalse;
3225             break;
3226           }
3227       }
3228     else
3229       {
3230         mipmap_image=mipmap_image->next;
3231         if ((mipmap_image->columns != columns) || (mipmap_image->rows != rows))
3232           ThrowBinaryException(CoderError,"ImageColumnOrRowSizeIsNotSupported",
3233             image->filename);
3234       }
3235
3236     DestroyBlob(mipmap_image);
3237     mipmap_image->blob=ReferenceBlob(image->blob);
3238
3239     WriteImageData(mipmap_image,pixelFormat,compression,weightByAlpha,
3240       clusterFit,exception);
3241
3242     if (fromlist == MagickFalse)
3243       {
3244         if (fast_mipmaps == MagickFalse)
3245           mipmap_image=DestroyImage(mipmap_image);
3246         else
3247           {
3248             if (resize_image != image)
3249               resize_image=DestroyImage(resize_image);
3250             resize_image=mipmap_image;
3251           }
3252       }
3253
3254     columns=DIV2(columns);
3255     rows=DIV2(rows);
3256   }
3257
3258   if (resize_image != image)
3259     resize_image=DestroyImage(resize_image);
3260
3261   return(status);
3262 }
3263
3264 static void WriteSingleColorFit(Image *image, const DDSVector4 *points,
3265   const ssize_t *map)
3266 {
3267   DDSVector3
3268     start,
3269     end;
3270
3271   register ssize_t
3272     i;
3273
3274   unsigned char
3275     color[3],
3276     index,
3277     indexes[16],
3278     indices[16];
3279
3280   color[0] = (unsigned char) ClampToLimit(255.0f*points->x,255);
3281   color[1] = (unsigned char) ClampToLimit(255.0f*points->y,255);
3282   color[2] = (unsigned char) ClampToLimit(255.0f*points->z,255);
3283
3284   index=0;
3285   ComputeEndPoints(DDS_LOOKUP,color,&start,&end,&index);
3286
3287   for (i=0; i< 16; i++)
3288     indexes[i]=index;
3289   RemapIndices(map,indexes,indices);
3290   WriteIndices(image,start,end,indices);
3291 }
3292
3293 static void WriteUncompressed(Image *image, ExceptionInfo *exception)
3294 {
3295   register const Quantum
3296     *p;
3297
3298   register ssize_t
3299     x;
3300
3301   ssize_t
3302     y;
3303
3304   for (y=0; y < (ssize_t) image->rows; y++)
3305   {
3306     p=GetVirtualPixels(image,0,y,image->columns,1,exception);
3307     if (p == (const Quantum *) NULL)
3308       break;
3309
3310     for (x=0; x < (ssize_t) image->columns; x++)
3311     {
3312       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelBlue(image,p)));
3313       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelGreen(image,p)));
3314       (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelRed(image,p)));
3315       if (image->alpha_trait != UndefinedPixelTrait)
3316         (void) WriteBlobByte(image,ScaleQuantumToChar(GetPixelAlpha(image,p)));
3317       p+=GetPixelChannels(image);
3318     }
3319   }
3320 }