dlls/windowscodecs/palette.c

   1 /*
   2  * Copyright 2009 Vincent Povirk for CodeWeavers
   3  * Copyright 2012,2016 Dmitry Timoshkov
   4  * Copyright 2016 Sebastian Lackner
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20
  21 #include <stdarg.h>
  22
  23 #define COBJMACROS
  24
  25 #include "windef.h"
  26 #include "winbase.h"
  27 #include "winreg.h"
  28 #include "objbase.h"
  29
  30 #include "wincodecs_private.h"
  31
  32 #include "wine/debug.h"
  33
  34 WINE_DEFAULT_DEBUG_CHANNEL(wincodecs);
  35
  36 typedef struct {
  37     IWICPalette IWICPalette_iface;
  38     LONG ref;
  39     UINT count;
  40     WICColor *colors;
  41     WICBitmapPaletteType type;
  42     CRITICAL_SECTION lock; /* must be held when count, colors, or type is accessed */
  43 } PaletteImpl;
  44
  45 static inline PaletteImpl *impl_from_IWICPalette(IWICPalette *iface)
  46 {
  47     return CONTAINING_RECORD(iface, PaletteImpl, IWICPalette_iface);
  48 }
  49
  50 static HRESULT WINAPI PaletteImpl_QueryInterface(IWICPalette *iface, REFIID iid,
  51     void **ppv)
  52 {
  53     PaletteImpl *This = impl_from_IWICPalette(iface);
  54     TRACE("(%p,%s,%p)\n", iface, debugstr_guid(iid), ppv);
  55
  56     if (!ppv) return E_INVALIDARG;
  57
  58     if (IsEqualIID(&IID_IUnknown, iid) || IsEqualIID(&IID_IWICPalette, iid))
  59     {
  60         *ppv = &This->IWICPalette_iface;
  61     }
  62     else
  63     {
  64         *ppv = NULL;
  65         return E_NOINTERFACE;
  66     }
  67
  68     IUnknown_AddRef((IUnknown*)*ppv);
  69     return S_OK;
  70 }
  71
  72 static ULONG WINAPI PaletteImpl_AddRef(IWICPalette *iface)
  73 {
  74     PaletteImpl *This = impl_from_IWICPalette(iface);
  75     ULONG ref = InterlockedIncrement(&This->ref);
  76
  77     TRACE("(%p) refcount=%lu\n", iface, ref);
  78
  79     return ref;
  80 }
  81
  82 static ULONG WINAPI PaletteImpl_Release(IWICPalette *iface)
  83 {
  84     PaletteImpl *This = impl_from_IWICPalette(iface);
  85     ULONG ref = InterlockedDecrement(&This->ref);
  86
  87     TRACE("(%p) refcount=%lu\n", iface, ref);
  88
  89     if (ref == 0)
  90     {
  91         This->lock.DebugInfo->Spare[0] = 0;
  92         DeleteCriticalSection(&This->lock);
  93         HeapFree(GetProcessHeap(), 0, This->colors);
  94         HeapFree(GetProcessHeap(), 0, This);
  95     }
  96
  97     return ref;
  98 }
  99
 100 static WICColor *generate_gray16_palette(UINT *count)
 101 {
 102     WICColor *entries;
 103     UINT i;
 104
 105     *count = 16;
 106     entries = HeapAlloc(GetProcessHeap(), 0, 16 * sizeof(WICColor));
 107     if (!entries) return NULL;
 108
 109     for (i = 0; i < 16; i++)
 110     {
 111         entries[i] = 0xff000000;
 112         entries[i] |= (i<<20) | (i<<16) | (i<<12) | (i<<8) | (i<<4) | i;
 113     }
 114     return entries;
 115 }
 116
 117 static WICColor *generate_gray256_palette(UINT *count)
 118 {
 119     WICColor *entries;
 120     UINT i;
 121
 122     *count = 256;
 123     entries = HeapAlloc(GetProcessHeap(), 0, 256 * sizeof(WICColor));
 124     if (!entries) return NULL;
 125
 126     for (i = 0; i < 256; i++)
 127     {
 128         entries[i] = 0xff000000;
 129         entries[i] |= (i<<16) | (i<<8) | i;
 130     }
 131     return entries;
 132 }
 133
 134 static WICColor *generate_halftone8_palette(UINT *count, BOOL add_transparent)
 135 {
 136     WICColor *entries;
 137     UINT i;
 138
 139     *count = add_transparent ? 17 : 16;
 140     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 141     if (!entries) return NULL;
 142
 143     for (i = 0; i < 8; i++)
 144     {
 145         entries[i] = 0xff000000;
 146         if (i & 1) entries[i] |= 0xff;
 147         if (i & 2) entries[i] |= 0xff00;
 148         if (i & 4) entries[i] |= 0xff0000;
 149     }
 150
 151     for (i = 8; i < 16; i++)
 152     {
 153         static const DWORD halftone[8] = { 0xc0c0c0, 0x808080, 0x800000, 0x008000,
 154                                            0x000080, 0x808000, 0x800080, 0x008080 };
 155         entries[i] = 0xff000000;
 156         entries[i] |= halftone[i-8];
 157     }
 158
 159     if (add_transparent)
 160         entries[i] = 0;
 161
 162     return entries;
 163 }
 164
 165 static WICColor *generate_halftone27_palette(UINT *count, BOOL add_transparent)
 166 {
 167     WICColor *entries;
 168     UINT i;
 169
 170     *count = add_transparent ? 29 : 28;
 171     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 172     if (!entries) return NULL;
 173
 174     for (i = 0; i < 27; i++)
 175     {
 176         static const BYTE halftone_values[4] = { 0x00,0x80,0xff };
 177         entries[i] = 0xff000000;
 178         entries[i] |= halftone_values[i%3];
 179         entries[i] |= halftone_values[(i/3)%3] << 8;
 180         entries[i] |= halftone_values[(i/9)%3] << 16;
 181     }
 182
 183     entries[i++] = 0xffc0c0c0;
 184     if (add_transparent)
 185         entries[i] = 0;
 186
 187     return entries;
 188 }
 189
 190 static WICColor *generate_halftone64_palette(UINT *count, BOOL add_transparent)
 191 {
 192     WICColor *entries;
 193     UINT i;
 194
 195     *count = add_transparent ? 73 : 72;
 196     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 197     if (!entries) return NULL;
 198
 199     for (i = 0; i < 64; i++)
 200     {
 201         static const BYTE halftone_values[4] = { 0x00,0x55,0xaa,0xff };
 202         entries[i] = 0xff000000;
 203         entries[i] |= halftone_values[i%4];
 204         entries[i] |= halftone_values[(i/4)%4] << 8;
 205         entries[i] |= halftone_values[(i/16)%4] << 16;
 206     }
 207
 208     for (i = 64; i < 72; i++)
 209     {
 210         static const DWORD halftone[8] = { 0xc0c0c0, 0x808080, 0x800000, 0x008000,
 211                                            0x000080, 0x808000, 0x800080, 0x008080 };
 212         entries[i] = 0xff000000;
 213         entries[i] |= halftone[i-64];
 214     }
 215
 216     if (add_transparent)
 217         entries[i] = 0;
 218
 219     return entries;
 220 }
 221
 222 static WICColor *generate_halftone125_palette(UINT *count, BOOL add_transparent)
 223 {
 224     WICColor *entries;
 225     UINT i;
 226
 227     *count = add_transparent ? 127 : 126;
 228     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 229     if (!entries) return NULL;
 230
 231     for (i = 0; i < 125; i++)
 232     {
 233         static const BYTE halftone_values[5] = { 0x00,0x40,0x80,0xbf,0xff };
 234         entries[i] = 0xff000000;
 235         entries[i] |= halftone_values[i%5];
 236         entries[i] |= halftone_values[(i/5)%5] << 8;
 237         entries[i] |= halftone_values[(i/25)%5] << 16;
 238     }
 239
 240     entries[i++] = 0xffc0c0c0;
 241     if (add_transparent)
 242         entries[i] = 0;
 243
 244     return entries;
 245 }
 246
 247 static WICColor *generate_halftone216_palette(UINT *count, BOOL add_transparent)
 248 {
 249     WICColor *entries;
 250     UINT i;
 251
 252     *count = add_transparent ? 225 : 224;
 253     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 254     if (!entries) return NULL;
 255
 256     for (i = 0; i < 216; i++)
 257     {
 258         static const BYTE halftone_values[6] = { 0x00,0x33,0x66,0x99,0xcc,0xff };
 259         entries[i] = 0xff000000;
 260         entries[i] |= halftone_values[i%6];
 261         entries[i] |= halftone_values[(i/6)%6] << 8;
 262         entries[i] |= halftone_values[(i/36)%6] << 16;
 263     }
 264
 265     for (i = 216; i < 224; i++)
 266     {
 267         static const DWORD halftone[8] = { 0xc0c0c0, 0x808080, 0x800000, 0x008000,
 268                                            0x000080, 0x808000, 0x800080, 0x008080 };
 269         entries[i] = 0xff000000;
 270         entries[i] |= halftone[i-216];
 271     }
 272
 273     if (add_transparent)
 274         entries[i] = 0;
 275
 276     return entries;
 277 }
 278
 279 static WICColor *generate_halftone252_palette(UINT *count, BOOL add_transparent)
 280 {
 281     WICColor *entries;
 282     UINT i;
 283
 284     *count = add_transparent ? 253 : 252;
 285     entries = HeapAlloc(GetProcessHeap(), 0, *count * sizeof(WICColor));
 286     if (!entries) return NULL;
 287
 288     for (i = 0; i < 252; i++)
 289     {
 290         static const BYTE halftone_values_rb[6] = { 0x00,0x33,0x66,0x99,0xcc,0xff };
 291         static const BYTE halftone_values_g[7] = { 0x00,0x2b,0x55,0x80,0xaa,0xd5,0xff };
 292         entries[i] = 0xff000000;
 293         entries[i] |= halftone_values_rb[i%6];
 294         entries[i] |= halftone_values_g[(i/6)%7] << 8;
 295         entries[i] |= halftone_values_rb[(i/42)%6] << 16;
 296     }
 297
 298     if (add_transparent)
 299         entries[i] = 0;
 300
 301     return entries;
 302 }
 303
 304 static WICColor *generate_halftone256_palette(UINT *count, BOOL add_transparent)
 305 {
 306     WICColor *entries;
 307     UINT i;
 308
 309     *count = 256;
 310     entries = HeapAlloc(GetProcessHeap(), 0, 256 * sizeof(WICColor));
 311     if (!entries) return NULL;
 312
 313     for (i = 0; i < 256; i++)
 314     {
 315         static const BYTE halftone_values_b[4] = { 0x00,0x55,0xaa,0xff };
 316         static const BYTE halftone_values_gr[8] = { 0x00,0x24,0x49,0x6d,0x92,0xb6,0xdb,0xff };
 317         entries[i] = 0xff000000;
 318         entries[i] |= halftone_values_b[i%4];
 319         entries[i] |= halftone_values_gr[(i/4)%8] << 8;
 320         entries[i] |= halftone_values_gr[(i/32)%8] << 16;
 321     }
 322
 323     if (add_transparent)
 324         entries[255] = 0;
 325
 326     return entries;
 327 }
 328
 329 static HRESULT WINAPI PaletteImpl_InitializePredefined(IWICPalette *iface,
 330     WICBitmapPaletteType type, BOOL add_transparent)
 331 {
 332     PaletteImpl *This = impl_from_IWICPalette(iface);
 333     WICColor *colors;
 334     UINT count;
 335
 336     TRACE("(%p,%u,%d)\n", iface, type, add_transparent);
 337
 338     switch (type)
 339     {
 340     case WICBitmapPaletteTypeFixedBW:
 341         count = 2;
 342         colors = HeapAlloc(GetProcessHeap(), 0, count * sizeof(WICColor));
 343         if (!colors) return E_OUTOFMEMORY;
 344         colors[0] = 0xff000000;
 345         colors[1] = 0xffffffff;
 346         break;
 347
 348     case WICBitmapPaletteTypeFixedGray4:
 349         count = 4;
 350         colors = HeapAlloc(GetProcessHeap(), 0, count * sizeof(WICColor));
 351         if (!colors) return E_OUTOFMEMORY;
 352         colors[0] = 0xff000000;
 353         colors[1] = 0xff555555;
 354         colors[2] = 0xffaaaaaa;
 355         colors[3] = 0xffffffff;
 356         break;
 357
 358     case WICBitmapPaletteTypeFixedGray16:
 359         colors = generate_gray16_palette(&count);
 360         if (!colors) return E_OUTOFMEMORY;
 361         break;
 362
 363     case WICBitmapPaletteTypeFixedGray256:
 364         colors = generate_gray256_palette(&count);
 365         if (!colors) return E_OUTOFMEMORY;
 366         break;
 367
 368     case WICBitmapPaletteTypeFixedHalftone8:
 369         colors = generate_halftone8_palette(&count, add_transparent);
 370         if (!colors) return E_OUTOFMEMORY;
 371         break;
 372
 373     case WICBitmapPaletteTypeFixedHalftone27:
 374         colors = generate_halftone27_palette(&count, add_transparent);
 375         if (!colors) return E_OUTOFMEMORY;
 376         break;
 377
 378     case WICBitmapPaletteTypeFixedHalftone64:
 379         colors = generate_halftone64_palette(&count, add_transparent);
 380         if (!colors) return E_OUTOFMEMORY;
 381         break;
 382
 383     case WICBitmapPaletteTypeFixedHalftone125:
 384         colors = generate_halftone125_palette(&count, add_transparent);
 385         if (!colors) return E_OUTOFMEMORY;
 386         break;
 387
 388     case WICBitmapPaletteTypeFixedHalftone216:
 389         colors = generate_halftone216_palette(&count, add_transparent);
 390         if (!colors) return E_OUTOFMEMORY;
 391         break;
 392
 393     case WICBitmapPaletteTypeFixedHalftone252:
 394         colors = generate_halftone252_palette(&count, add_transparent);
 395         if (!colors) return E_OUTOFMEMORY;
 396         break;
 397
 398     case WICBitmapPaletteTypeFixedHalftone256:
 399         colors = generate_halftone256_palette(&count, add_transparent);
 400         if (!colors) return E_OUTOFMEMORY;
 401         break;
 402
 403     default:
 404         WARN("invalid palette type %u\n", type);
 405         return E_INVALIDARG;
 406     }
 407
 408     EnterCriticalSection(&This->lock);
 409     HeapFree(GetProcessHeap(), 0, This->colors);
 410     This->colors = colors;
 411     This->count = count;
 412     This->type = type;
 413     LeaveCriticalSection(&This->lock);
 414
 415     return S_OK;
 416 }
 417
 418 static HRESULT WINAPI PaletteImpl_InitializeCustom(IWICPalette *iface,
 419     WICColor *pColors, UINT colorCount)
 420 {
 421     PaletteImpl *This = impl_from_IWICPalette(iface);
 422     WICColor *new_colors;
 423
 424     TRACE("(%p,%p,%u)\n", iface, pColors, colorCount);
 425
 426     if (colorCount == 0)
 427     {
 428         new_colors = NULL;
 429     }
 430     else
 431     {
 432         if (!pColors) return E_INVALIDARG;
 433         new_colors = HeapAlloc(GetProcessHeap(), 0, sizeof(WICColor) * colorCount);
 434         if (!new_colors) return E_OUTOFMEMORY;
 435         memcpy(new_colors, pColors, sizeof(WICColor) * colorCount);
 436     }
 437
 438     EnterCriticalSection(&This->lock);
 439     HeapFree(GetProcessHeap(), 0, This->colors);
 440     This->colors = new_colors;
 441     This->count = colorCount;
 442     This->type = WICBitmapPaletteTypeCustom;
 443     LeaveCriticalSection(&This->lock);
 444
 445     return S_OK;
 446 }
 447
 448 #define R_COUNT (1 << 5)
 449 #define R_SHIFT (8 - 5)
 450 #define R_SCALE 2
 451
 452 #define G_COUNT (1 << 6)
 453 #define G_SHIFT (8 - 6)
 454 #define G_SCALE 3
 455
 456 #define B_COUNT (1 << 5)
 457 #define B_SHIFT (8 - 5)
 458 #define B_SCALE 1
 459
 460 struct histogram
 461 {
 462     unsigned int data[R_COUNT][G_COUNT][B_COUNT];
 463 };
 464
 465 struct box
 466 {
 467     int r_min, r_max;
 468     int g_min, g_max;
 469     int b_min, b_max;
 470     unsigned int count;
 471     unsigned int score;
 472 };
 473
 474 /* count nonzero elements in the histogram range [r_min, r_max] x [g_min, g_max] x [b_min, b_max] */
 475 static inline unsigned int histogram_count(struct histogram *h, int r_min, int r_max,
 476                                            int g_min, int g_max, int b_min, int b_max)
 477 {
 478     unsigned int count = 0;
 479     int r, g, b;
 480     for (r = r_min; r <= r_max; r++)
 481     for (g = g_min; g <= g_max; g++)
 482     for (b = b_min; b <= b_max; b++)
 483         if (h->data[r][g][b] != 0) count++;
 484     return count;
 485 }
 486
 487 /* compute weighted average color in the range [r_min, r_max] x [g_min, g_max] x [b_min, b_max] */
 488 static unsigned int histogram_color(struct histogram *h, int r_min, int r_max,
 489                                     int g_min, int g_max, int b_min, int b_max)
 490 {
 491     unsigned long long r_sum = 0, g_sum = 0, b_sum = 0;
 492     unsigned int tmp, count = 0;
 493     int r, g, b;
 494
 495     for (r = r_min; r <= r_max; r++)
 496     for (g = g_min; g <= g_max; g++)
 497     for (b = b_min; b <= b_max; b++)
 498     {
 499         if (!(tmp = h->data[r][g][b])) continue;
 500         r_sum += ((r << R_SHIFT) + ((1 << R_SHIFT) / 2)) * tmp;
 501         g_sum += ((g << G_SHIFT) + ((1 << G_SHIFT) / 2)) * tmp;
 502         b_sum += ((b << B_SHIFT) + ((1 << B_SHIFT) / 2)) * tmp;
 503         count += tmp;
 504     }
 505
 506     return ((b_sum + (count / 2)) / count) |
 507            ((g_sum + (count / 2)) / count) << 8 |
 508            ((r_sum + (count / 2)) / count) << 16 | 0xff000000;
 509 }
 510
 511 /* same as histogram_count */
 512 static inline unsigned int box_count(struct histogram *h, struct box *b)
 513 {
 514     return histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, b->b_min, b->b_max);
 515 }
 516
 517 /* same as histogram_color */
 518 static inline unsigned int box_color(struct histogram *h, struct box *b)
 519 {
 520     return histogram_color(h, b->r_min, b->r_max, b->g_min, b->g_max, b->b_min, b->b_max);
 521 }
 522
 523 /* compute score used to determine best split (also called "volume") */
 524 static inline unsigned int box_score(struct box *b)
 525 {
 526     unsigned int tmp, sum = 0;
 527     tmp = ((b->r_max - b->r_min) << R_SHIFT) * R_SCALE; sum += tmp * tmp;
 528     tmp = ((b->g_max - b->g_min) << G_SHIFT) * G_SCALE; sum += tmp * tmp;
 529     tmp = ((b->b_max - b->b_min) << B_SHIFT) * B_SCALE; sum += tmp * tmp;
 530     return sum;
 531 }
 532
 533 /* attempt to shrink a box */
 534 static void shrink_box(struct histogram *h, struct box *b)
 535 {
 536     int i;
 537     for (i = b->r_min; i <= b->r_max; i++)
 538         if (histogram_count(h, i, i, b->g_min, b->g_max, b->b_min, b->b_max)) { b->r_min = i; break; }
 539     for (i = b->r_max; i >= b->r_min; i--)
 540         if (histogram_count(h, i, i, b->g_min, b->g_max, b->b_min, b->b_max)) { b->r_max = i; break; }
 541     for (i = b->g_min; i <= b->g_max; i++)
 542         if (histogram_count(h, b->r_min, b->r_max, i, i, b->b_min, b->b_max)) { b->g_min = i; break; }
 543     for (i = b->g_max; i >= b->g_min; i--)
 544         if (histogram_count(h, b->r_min, b->r_max, i, i, b->b_min, b->b_max)) { b->g_max = i; break; }
 545     for (i = b->b_min; i <= b->b_max; i++)
 546         if (histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, i, i)) { b->b_min = i; break; }
 547     for (i = b->b_max; i >= b->b_min; i--)
 548         if (histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, i, i)) { b->b_max = i; break; }
 549     b->count = box_count(h, b);
 550     b->score = box_score(b);
 551 }
 552
 553 /* helper for split_box */
 554 static inline void set_avg(int *min, int *max)
 555 {
 556     int avg = (*min + *max) / 2;
 557     *min = avg + 1;
 558     *max = avg;
 559 }
 560
 561 /* split a box based on the best axis */
 562 static void split_box(struct histogram *h, struct box *b1, struct box *b2)
 563 {
 564     int r = ((b1->r_max - b1->r_min) << R_SHIFT) * R_SCALE;
 565     int g = ((b1->g_max - b1->g_min) << G_SHIFT) * G_SCALE;
 566     int b = ((b1->b_max - b1->b_min) << B_SHIFT) * B_SCALE;
 567
 568     *b2 = *b1;
 569
 570     if (r > g)
 571     {
 572         if (b > r) set_avg(&b1->b_min, &b2->b_max);
 573         else set_avg(&b1->r_min, &b2->r_max);
 574     }
 575     else
 576     {
 577         if (b > g) set_avg(&b1->b_min, &b2->b_max);
 578         else set_avg(&b1->g_min, &b2->g_max);
 579     }
 580
 581     shrink_box(h, b1);
 582     shrink_box(h, b2);
 583 }
 584
 585 /* find box suitable for split based on count */
 586 static struct box *find_box_max_count(struct box *b, int count)
 587 {
 588     struct box *best = NULL;
 589     for (; count--; b++)
 590         if (b->score && (!best || b->count > best->count)) best = b;
 591     return best;
 592 }
 593
 594 /* find box suitable for split based on score */
 595 static struct box *find_box_max_score(struct box *b, int count)
 596 {
 597     struct box *best = NULL;
 598     for (; count--; b++)
 599         if (b->score && (!best || b->score > best->score)) best = b;
 600     return best;
 601 }
 602
 603 /* compute color map with at most 'desired' colors
 604  * image must be in 24bpp BGR format and colors are returned in 0xAARRGGBB format */
 605 static int median_cut(unsigned char *image, unsigned int width, unsigned int height,
 606                       unsigned int stride, int desired, unsigned int *colors)
 607 {
 608     struct box boxes[256];
 609     struct histogram *h;
 610     unsigned int x, y;
 611     unsigned char *p;
 612     struct box *b1, *b2;
 613     int numboxes, i;
 614
 615     if (!(h = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*h))))
 616         return 0;
 617
 618     for (y = 0; y < height; y++)
 619         for (x = 0, p = image + y * stride; x < width; x++, p += 3)
 620             h->data[p[2] >> R_SHIFT][p[1] >> G_SHIFT][p[0] >> B_SHIFT]++;
 621
 622     numboxes = 1;
 623     boxes[0].r_min = 0; boxes[0].r_max = R_COUNT - 1;
 624     boxes[0].g_min = 0; boxes[0].g_max = G_COUNT - 1;
 625     boxes[0].b_min = 0; boxes[0].b_max = B_COUNT - 1;
 626     shrink_box(h, &boxes[0]);
 627
 628     while (numboxes <= desired / 2)
 629     {
 630         if (!(b1 = find_box_max_count(boxes, numboxes))) break;
 631         b2 = &boxes[numboxes++];
 632         split_box(h, b1, b2);
 633     }
 634     while (numboxes < desired)
 635     {
 636         if (!(b1 = find_box_max_score(boxes, numboxes))) break;
 637         b2 = &boxes[numboxes++];
 638         split_box(h, b1, b2);
 639     }
 640
 641     for (i = 0; i < numboxes; i++)
 642         colors[i] = box_color(h, &boxes[i]);
 643
 644     HeapFree(GetProcessHeap(), 0, h);
 645     return numboxes;
 646 }
 647
 648
 649 static HRESULT WINAPI PaletteImpl_InitializeFromBitmap(IWICPalette *palette,
 650     IWICBitmapSource *source, UINT desired, BOOL add_transparent)
 651 {
 652     IWICImagingFactory *factory = NULL;
 653     IWICBitmap *rgb24_bitmap = NULL;
 654     IWICBitmapSource *rgb24_source;
 655     IWICBitmapLock *lock = NULL;
 656     WICPixelFormatGUID format;
 657     HRESULT hr;
 658     UINT width, height, stride, size, actual_number_of_colors;
 659     BYTE *src;
 660     WICColor colors[256];
 661
 662     TRACE("(%p,%p,%u,%d)\n", palette, source, desired, add_transparent);
 663
 664     if (!source || desired < 2 || desired > 256)
 665         return E_INVALIDARG;
 666
 667     hr = IWICBitmapSource_GetPixelFormat(source, &format);
 668     if (hr != S_OK) return hr;
 669
 670     /* For interoperability with gdiplus where PixelFormat24bppRGB is actually stored
 671      * as BGR (and there is no corresponding RGB format), we have to use 24bppBGR
 672      * to avoid format conversions.
 673      */
 674     if (!IsEqualGUID(&format, &GUID_WICPixelFormat24bppBGR))
 675     {
 676         hr = WICConvertBitmapSource(&GUID_WICPixelFormat24bppBGR, source, &rgb24_source);
 677         if (hr != S_OK) return hr;
 678     }
 679     else
 680         rgb24_source = source;
 681
 682     hr = create_instance(&CLSID_WICImagingFactory, &IID_IWICImagingFactory, (void **)&factory);
 683     if (hr != S_OK) goto fail;
 684
 685     hr = IWICImagingFactory_CreateBitmapFromSource(factory, rgb24_source, WICBitmapCacheOnLoad, &rgb24_bitmap);
 686     if (hr != S_OK) goto fail;
 687
 688     hr = IWICBitmap_Lock(rgb24_bitmap, NULL, WICBitmapLockRead, &lock);
 689     if (hr != S_OK) goto fail;
 690
 691     IWICBitmapLock_GetSize(lock, &width, &height);
 692     IWICBitmapLock_GetStride(lock, &stride);
 693     IWICBitmapLock_GetDataPointer(lock, &size, &src);
 694
 695     actual_number_of_colors = median_cut(src, width, height, stride, add_transparent ? desired - 1 : desired, colors);
 696     TRACE("actual number of colors: %u\n", actual_number_of_colors);
 697
 698     if (actual_number_of_colors)
 699     {
 700         if (add_transparent) colors[actual_number_of_colors++] = 0;
 701
 702         hr = IWICPalette_InitializeCustom(palette, colors, actual_number_of_colors);
 703     }
 704     else
 705         hr = E_OUTOFMEMORY;
 706
 707 fail:
 708     if (lock)
 709         IWICBitmapLock_Release(lock);
 710
 711     if (rgb24_bitmap)
 712         IWICBitmap_Release(rgb24_bitmap);
 713
 714     if (factory)
 715         IWICImagingFactory_Release(factory);
 716
 717     if (rgb24_source != source)
 718         IWICBitmapSource_Release(rgb24_source);
 719
 720     return hr;
 721 }
 722
 723 static HRESULT WINAPI PaletteImpl_InitializeFromPalette(IWICPalette *iface,
 724     IWICPalette *source)
 725 {
 726     PaletteImpl *This = impl_from_IWICPalette(iface);
 727     UINT count;
 728     WICColor *colors = NULL;
 729     WICBitmapPaletteType type;
 730     HRESULT hr;
 731
 732     TRACE("(%p,%p)\n", iface, source);
 733
 734     if (!source) return E_INVALIDARG;
 735
 736     hr = IWICPalette_GetType(source, &type);
 737     if (hr != S_OK) return hr;
 738     hr = IWICPalette_GetColorCount(source, &count);
 739     if (hr != S_OK) return hr;
 740     if (count)
 741     {
 742         colors = HeapAlloc(GetProcessHeap(), 0, sizeof(WICColor) * count);
 743         if (!colors) return E_OUTOFMEMORY;
 744         hr = IWICPalette_GetColors(source, count, colors, &count);
 745         if (hr != S_OK)
 746         {
 747             HeapFree(GetProcessHeap(), 0, colors);
 748             return hr;
 749         }
 750     }
 751
 752     EnterCriticalSection(&This->lock);
 753     HeapFree(GetProcessHeap(), 0, This->colors);
 754     This->colors = colors;
 755     This->count = count;
 756     This->type = type;
 757     LeaveCriticalSection(&This->lock);
 758
 759     return S_OK;
 760 }
 761
 762 static HRESULT WINAPI PaletteImpl_GetType(IWICPalette *iface,
 763     WICBitmapPaletteType *pePaletteType)
 764 {
 765     PaletteImpl *This = impl_from_IWICPalette(iface);
 766
 767     TRACE("(%p,%p)\n", iface, pePaletteType);
 768
 769     if (!pePaletteType) return E_INVALIDARG;
 770
 771     EnterCriticalSection(&This->lock);
 772     *pePaletteType = This->type;
 773     LeaveCriticalSection(&This->lock);
 774
 775     return S_OK;
 776 }
 777
 778 static HRESULT WINAPI PaletteImpl_GetColorCount(IWICPalette *iface, UINT *pcCount)
 779 {
 780     PaletteImpl *This = impl_from_IWICPalette(iface);
 781
 782     TRACE("(%p,%p)\n", iface, pcCount);
 783
 784     if (!pcCount) return E_INVALIDARG;
 785
 786     EnterCriticalSection(&This->lock);
 787     *pcCount = This->count;
 788     LeaveCriticalSection(&This->lock);
 789
 790     return S_OK;
 791 }
 792
 793 static HRESULT WINAPI PaletteImpl_GetColors(IWICPalette *iface, UINT colorCount,
 794     WICColor *pColors, UINT *pcActualColors)
 795 {
 796     PaletteImpl *This = impl_from_IWICPalette(iface);
 797
 798     TRACE("(%p,%i,%p,%p)\n", iface, colorCount, pColors, pcActualColors);
 799
 800     if (!pColors || !pcActualColors) return E_INVALIDARG;
 801
 802     EnterCriticalSection(&This->lock);
 803
 804     if (This->count < colorCount) colorCount = This->count;
 805
 806     memcpy(pColors, This->colors, sizeof(WICColor) * colorCount);
 807
 808     *pcActualColors = colorCount;
 809
 810     LeaveCriticalSection(&This->lock);
 811
 812     return S_OK;
 813 }
 814
 815 static HRESULT WINAPI PaletteImpl_IsBlackWhite(IWICPalette *iface, BOOL *pfIsBlackWhite)
 816 {
 817     PaletteImpl *This = impl_from_IWICPalette(iface);
 818
 819     TRACE("(%p,%p)\n", iface, pfIsBlackWhite);
 820
 821     if (!pfIsBlackWhite) return E_INVALIDARG;
 822
 823     EnterCriticalSection(&This->lock);
 824     if (This->type == WICBitmapPaletteTypeFixedBW)
 825         *pfIsBlackWhite = TRUE;
 826     else
 827         *pfIsBlackWhite = FALSE;
 828     LeaveCriticalSection(&This->lock);
 829
 830     return S_OK;
 831 }
 832
 833 static HRESULT WINAPI PaletteImpl_IsGrayscale(IWICPalette *iface, BOOL *pfIsGrayscale)
 834 {
 835     PaletteImpl *This = impl_from_IWICPalette(iface);
 836
 837     TRACE("(%p,%p)\n", iface, pfIsGrayscale);
 838
 839     if (!pfIsGrayscale) return E_INVALIDARG;
 840
 841     EnterCriticalSection(&This->lock);
 842     switch(This->type)
 843     {
 844         case WICBitmapPaletteTypeFixedBW:
 845         case WICBitmapPaletteTypeFixedGray4:
 846         case WICBitmapPaletteTypeFixedGray16:
 847         case WICBitmapPaletteTypeFixedGray256:
 848             *pfIsGrayscale = TRUE;
 849             break;
 850         default:
 851             *pfIsGrayscale = FALSE;
 852     }
 853     LeaveCriticalSection(&This->lock);
 854
 855     return S_OK;
 856 }
 857
 858 static HRESULT WINAPI PaletteImpl_HasAlpha(IWICPalette *iface, BOOL *pfHasAlpha)
 859 {
 860     PaletteImpl *This = impl_from_IWICPalette(iface);
 861     UINT i;
 862
 863     TRACE("(%p,%p)\n", iface, pfHasAlpha);
 864
 865     if (!pfHasAlpha) return E_INVALIDARG;
 866
 867     *pfHasAlpha = FALSE;
 868
 869     EnterCriticalSection(&This->lock);
 870     for (i=0; i<This->count; i++)
 871         if ((This->colors[i]&0xff000000) != 0xff000000)
 872         {
 873             *pfHasAlpha = TRUE;
 874             break;
 875         }
 876     LeaveCriticalSection(&This->lock);
 877
 878     return S_OK;
 879 }
 880
 881 static const IWICPaletteVtbl PaletteImpl_Vtbl = {
 882     PaletteImpl_QueryInterface,
 883     PaletteImpl_AddRef,
 884     PaletteImpl_Release,
 885     PaletteImpl_InitializePredefined,
 886     PaletteImpl_InitializeCustom,
 887     PaletteImpl_InitializeFromBitmap,
 888     PaletteImpl_InitializeFromPalette,
 889     PaletteImpl_GetType,
 890     PaletteImpl_GetColorCount,
 891     PaletteImpl_GetColors,
 892     PaletteImpl_IsBlackWhite,
 893     PaletteImpl_IsGrayscale,
 894     PaletteImpl_HasAlpha
 895 };
 896
 897 HRESULT PaletteImpl_Create(IWICPalette **palette)
 898 {
 899     PaletteImpl *This;
 900
 901     This = HeapAlloc(GetProcessHeap(), 0, sizeof(PaletteImpl));
 902     if (!This) return E_OUTOFMEMORY;
 903
 904     This->IWICPalette_iface.lpVtbl = &PaletteImpl_Vtbl;
 905     This->ref = 1;
 906     This->count = 0;
 907     This->colors = NULL;
 908     This->type = WICBitmapPaletteTypeCustom;
 909     InitializeCriticalSection(&This->lock);
 910     This->lock.DebugInfo->Spare[0] = (DWORD_PTR)(__FILE__ ": PaletteImpl.lock");
 911
 912     *palette = &This->IWICPalette_iface;
 913
 914     return S_OK;
 915 }