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