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