[PATCH 6/9] windowscodecs: Implement IWICPalette::InitializeFromBitmap.

[Dmitry Timoshkov]

Based on median cut implementation created by Sebastian Lackner.

Signed-off-by: Dmitry Timoshkov <dmitry(a)baikal.ru>
---
 dlls/windowscodecs/palette.c       | 279 ++++++++++++++++++++++++++++-
 dlls/windowscodecs/tests/palette.c |  21 +--
 2 files changed, 275 insertions(+), 25 deletions(-)

diff --git a/dlls/windowscodecs/palette.c b/dlls/windowscodecs/palette.c
index 89ec9ead11..1c1e85834b 100644
--- a/dlls/windowscodecs/palette.c
+++ b/dlls/windowscodecs/palette.c
@@ -1,6 +1,7 @@
 /*
  * Copyright 2009 Vincent Povirk for CodeWeavers
- * Copyright 2012 Dmitry Timoshkov
+ * Copyright 2012,2016 Dmitry Timoshkov
+ * Copyright 2016 Sebastian Lackner
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
@@ -446,11 +447,279 @@ static HRESULT WINAPI PaletteImpl_InitializeCustom(IWICPalette *iface,
     return S_OK;
 }
 
-static HRESULT WINAPI PaletteImpl_InitializeFromBitmap(IWICPalette *iface,
-    IWICBitmapSource *pISurface, UINT colorCount, BOOL fAddTransparentColor)
+#define R_COUNT (1 << 5)
+#define R_SHIFT (8 - 5)
+#define R_SCALE 2
+
+#define G_COUNT (1 << 6)
+#define G_SHIFT (8 - 6)
+#define G_SCALE 3
+
+#define B_COUNT (1 << 5)
+#define B_SHIFT (8 - 5)
+#define B_SCALE 1
+
+struct histogram
+{
+    unsigned int data[R_COUNT][G_COUNT][B_COUNT];
+};
+
+struct box
+{
+    int r_min, r_max;
+    int g_min, g_max;
+    int b_min, b_max;
+    unsigned int count;
+    unsigned int score;
+};
+
+/* count nonzero elements in the histogram range [r_min, r_max] x [g_min, g_max] x [b_min, b_max] */
+static inline unsigned int histogram_count(struct histogram *h, int r_min, int r_max,
+                                           int g_min, int g_max, int b_min, int b_max)
+{
+    unsigned int count = 0;
+    int r, g, b;
+    for (r = r_min; r <= r_max; r++)
+    for (g = g_min; g <= g_max; g++)
+    for (b = b_min; b <= b_max; b++)
+        if (h->data[r][g][b] != 0) count++;
+    return count;
+}
+
+/* compute weighted average color in the range [r_min, r_max] x [g_min, g_max] x [b_min, b_max] */
+static unsigned int histogram_color(struct histogram *h, int r_min, int r_max,
+                                    int g_min, int g_max, int b_min, int b_max)
+{
+    unsigned long long r_sum = 0, g_sum = 0, b_sum = 0;
+    unsigned int tmp, count = 0;
+    int r, g, b;
+
+    for (r = r_min; r <= r_max; r++)
+    for (g = g_min; g <= g_max; g++)
+    for (b = b_min; b <= b_max; b++)
+    {
+        if (!(tmp = h->data[r][g][b])) continue;
+        r_sum += ((r << R_SHIFT) + ((1 << R_SHIFT) / 2)) * tmp;
+        g_sum += ((g << G_SHIFT) + ((1 << G_SHIFT) / 2)) * tmp;
+        b_sum += ((b << B_SHIFT) + ((1 << B_SHIFT) / 2)) * tmp;
+        count += tmp;
+    }
+
+    return ((b_sum + (count / 2)) / count) |
+           ((g_sum + (count / 2)) / count) << 8 |
+           ((r_sum + (count / 2)) / count) << 16 | 0xff000000;
+}
+
+/* same as histogram_count */
+static inline unsigned int box_count(struct histogram *h, struct box *b)
+{
+    return histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, b->b_min, b->b_max);
+}
+
+/* same as histogram_color */
+static inline unsigned int box_color(struct histogram *h, struct box *b)
+{
+    return histogram_color(h, b->r_min, b->r_max, b->g_min, b->g_max, b->b_min, b->b_max);
+}
+
+/* compute score used to determine best split (also called "volume") */
+static inline unsigned int box_score(struct box *b)
+{
+    unsigned int tmp, sum = 0;
+    tmp = ((b->r_max - b->r_min) << R_SHIFT) * R_SCALE; sum += tmp * tmp;
+    tmp = ((b->g_max - b->g_min) << G_SHIFT) * G_SCALE; sum += tmp * tmp;
+    tmp = ((b->b_max - b->b_min) << B_SHIFT) * B_SCALE; sum += tmp * tmp;
+    return sum;
+}
+
+/* attempt to shrink a box */
+static void shrink_box(struct histogram *h, struct box *b)
+{
+    int i;
+    for (i = b->r_min; i <= b->r_max; i++)
+        if (histogram_count(h, i, i, b->g_min, b->g_max, b->b_min, b->b_max)) { b->r_min = i; break; }
+    for (i = b->r_max; i >= b->r_min; i--)
+        if (histogram_count(h, i, i, b->g_min, b->g_max, b->b_min, b->b_max)) { b->r_max = i; break; }
+    for (i = b->g_min; i <= b->g_max; i++)
+        if (histogram_count(h, b->r_min, b->r_max, i, i, b->b_min, b->b_max)) { b->g_min = i; break; }
+    for (i = b->g_max; i >= b->g_min; i--)
+        if (histogram_count(h, b->r_min, b->r_max, i, i, b->b_min, b->b_max)) { b->g_max = i; break; }
+    for (i = b->b_min; i <= b->b_max; i++)
+        if (histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, i, i)) { b->b_min = i; break; }
+    for (i = b->b_max; i >= b->b_min; i--)
+        if (histogram_count(h, b->r_min, b->r_max, b->g_min, b->g_max, i, i)) { b->b_max = i; break; }
+    b->count = box_count(h, b);
+    b->score = box_score(b);
+}
+
+/* helper for split_box */
+static inline void set_avg(int *min, int *max)
+{
+    int avg = (*min + *max) / 2;
+    *min = avg + 1;
+    *max = avg;
+}
+
+/* split a box based on the best axis */
+static void split_box(struct histogram *h, struct box *b1, struct box *b2)
+{
+    int r = ((b1->r_max - b1->r_min) << R_SHIFT) * R_SCALE;
+    int g = ((b1->g_max - b1->g_min) << G_SHIFT) * G_SCALE;
+    int b = ((b1->b_max - b1->b_min) << B_SHIFT) * B_SCALE;
+
+    *b2 = *b1;
+
+    if (r > g)
+    {
+        if (b > r) set_avg(&b1->b_min, &b2->b_max);
+        else set_avg(&b1->r_min, &b2->r_max);
+    }
+    else
+    {
+        if (b > g) set_avg(&b1->b_min, &b2->b_max);
+        else set_avg(&b1->g_min, &b2->g_max);
+    }
+
+    shrink_box(h, b1);
+    shrink_box(h, b2);
+}
+
+/* find box suitable for split based on count */
+static struct box *find_box_max_count(struct box *b, int count)
+{
+    struct box *best = NULL;
+    for (; count--; b++)
+        if (b->score && (!best || b->count > best->count)) best = b;
+    return best;
+}
+
+/* find box suitable for split based on score */
+static struct box *find_box_max_score(struct box *b, int count)
+{
+    struct box *best = NULL;
+    for (; count--; b++)
+        if (b->score && (!best || b->score > best->score)) best = b;
+    return best;
+}
+
+/* compute color map with at most 'desired' colors
+ * image must be in 24bpp BGR format and colors are returned in 0xAARRGGBB format */
+static int median_cut(unsigned char *image, unsigned int width, unsigned int height,
+                      unsigned int stride, int desired, unsigned int *colors)
+{
+    struct box boxes[256];
+    struct histogram *h;
+    unsigned int x, y;
+    unsigned char *p;
+    struct box *b1, *b2;
+    int numboxes, i;
+
+    if (!(h = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sizeof(*h))))
+        return 0;
+
+    for (y = 0; y < height; y++)
+        for (x = 0, p = image + y * stride; x < width; x++, p += 3)
+            h->data[p[2] >> R_SHIFT][p[1] >> G_SHIFT][p[0] >> B_SHIFT]++;
+
+    numboxes = 1;
+    boxes[0].r_min = 0; boxes[0].r_max = R_COUNT - 1;
+    boxes[0].g_min = 0; boxes[0].g_max = G_COUNT - 1;
+    boxes[0].b_min = 0; boxes[0].b_max = B_COUNT - 1;
+    shrink_box(h, &boxes[0]);
+
+    while (numboxes <= desired / 2)
+    {
+        if (!(b1 = find_box_max_count(boxes, numboxes))) break;
+        b2 = &boxes[numboxes++];
+        split_box(h, b1, b2);
+    }
+    while (numboxes < desired)
+    {
+        if (!(b1 = find_box_max_score(boxes, numboxes))) break;
+        b2 = &boxes[numboxes++];
+        split_box(h, b1, b2);
+    }
+
+    for (i = 0; i < numboxes; i++)
+        colors[i] = box_color(h, &boxes[i]);
+
+    HeapFree(GetProcessHeap(), 0, h);
+    return numboxes;
+}
+
+
+static HRESULT WINAPI PaletteImpl_InitializeFromBitmap(IWICPalette *palette,
+    IWICBitmapSource *source, UINT desired, BOOL add_transparent)
 {
-    FIXME("(%p,%p,%u,%i): stub\n", iface, pISurface, colorCount, fAddTransparentColor);
-    return E_NOTIMPL;
+    IWICImagingFactory *factory = NULL;
+    IWICBitmap *rgb24_bitmap = NULL;
+    IWICBitmapSource *rgb24_source;
+    IWICBitmapLock *lock = NULL;
+    WICPixelFormatGUID format;
+    HRESULT hr;
+    UINT width, height, stride, size, actual_number_of_colors;
+    BYTE *src;
+    WICColor colors[256];
+
+    TRACE("(%p,%p,%u,%d)\n", palette, source, desired, add_transparent);
+
+    if (!source || desired < 2 || desired > 256)
+        return E_INVALIDARG;
+
+    hr = IWICBitmapSource_GetPixelFormat(source, &format);
+    if (hr != S_OK) return hr;
+
+    /* For interoperability with gdiplus where PixelFormat24bppRGB actully stored
+     * as BGR (and there is no a corresponding RGB format) we have to use 24bppBGR
+     * to avoid format conversions.
+     */
+    if (!IsEqualGUID(&format, &GUID_WICPixelFormat24bppBGR))
+    {
+        hr = WICConvertBitmapSource(&GUID_WICPixelFormat24bppBGR, source, &rgb24_source);
+        if (hr != S_OK) return hr;
+    }
+    else
+        rgb24_source = source;
+
+    hr = ImagingFactory_CreateInstance(&IID_IWICImagingFactory, (void **)&factory);
+    if (hr != S_OK) goto fail;
+
+    hr = IWICImagingFactory_CreateBitmapFromSource(factory, rgb24_source, WICBitmapCacheOnLoad, &rgb24_bitmap);
+    if (hr != S_OK) goto fail;
+
+    hr = IWICBitmap_Lock(rgb24_bitmap, NULL, WICBitmapLockRead, &lock);
+    if (hr != S_OK) goto fail;
+
+    IWICBitmapLock_GetSize(lock, &width, &height);
+    IWICBitmapLock_GetStride(lock, &stride);
+    IWICBitmapLock_GetDataPointer(lock, &size, &src);
+
+    actual_number_of_colors = median_cut(src, width, height, stride, add_transparent ? desired - 1 : desired, colors);
+    TRACE("actual number of colors: %u\n", actual_number_of_colors);
+
+    if (actual_number_of_colors)
+    {
+        if (add_transparent) colors[actual_number_of_colors++] = 0;
+
+        hr = IWICPalette_InitializeCustom(palette, colors, actual_number_of_colors);
+    }
+    else
+        hr = E_OUTOFMEMORY;
+
+fail:
+    if (lock)
+        IWICBitmapLock_Release(lock);
+
+    if (rgb24_bitmap)
+        IWICBitmap_Release(rgb24_bitmap);
+
+    if (factory)
+        IWICImagingFactory_Release(factory);
+
+    if (rgb24_source != source)
+        IWICBitmapSource_Release(rgb24_source);
+
+    return hr;
 }
 
 static HRESULT WINAPI PaletteImpl_InitializeFromPalette(IWICPalette *iface,
diff --git a/dlls/windowscodecs/tests/palette.c b/dlls/windowscodecs/tests/palette.c
index 3b9f68535b..5bb25fa427 100644
--- a/dlls/windowscodecs/tests/palette.c
+++ b/dlls/windowscodecs/tests/palette.c
@@ -577,48 +577,34 @@ static void test_palette_from_bitmap(void)
     ok(hr == S_OK, "CreatePalette error %#x\n", hr);
 
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 0, FALSE);
-todo_wine
     ok(hr == E_INVALIDARG, "expected E_INVALIDARG, got %#x\n", hr);
 
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 1, FALSE);
-todo_wine
     ok(hr == E_INVALIDARG, "expected E_INVALIDARG, got %#x\n", hr);
 
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 257, FALSE);
-todo_wine
     ok(hr == E_INVALIDARG, "expected E_INVALIDARG, got %#x\n", hr);
 
     hr = IWICPalette_InitializeFromBitmap(palette, NULL, 16, FALSE);
-todo_wine
     ok(hr == E_INVALIDARG, "expected E_INVALIDARG, got %#x\n", hr);
 
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 2, FALSE);
-todo_wine
     ok(hr == S_OK, "InitializeFromBitmap error %#x\n", hr);
-if (hr == S_OK)
-{
+    count = 0;
     hr = IWICPalette_GetColorCount(palette, &count);
     ok(hr == S_OK, "GetColorCount error %#x\n", hr);
     ok(count == 2, "expected 2, got %u\n", count);
-}
 
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 2, TRUE);
-todo_wine
     ok(hr == S_OK, "InitializeFromBitmap error %#x\n", hr);
-if (hr == S_OK)
-{
     count = 0;
     hr = IWICPalette_GetColorCount(palette, &count);
     ok(hr == S_OK, "GetColorCount error %#x\n", hr);
     ok(count == 2, "expected 2, got %u\n", count);
-}
 
     /* without trasparent color */
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 16, FALSE);
-todo_wine
     ok(hr == S_OK, "InitializeFromBitmap error %#x\n", hr);
-if (hr == S_OK)
-{
     type = -1;
     hr = IWICPalette_GetType(palette, &type);
     ok(hr == S_OK, "GetType error %#x\n", hr);
@@ -632,14 +618,10 @@ if (hr == S_OK)
     ok(hr == S_OK, "GetColors error %#x\n", hr);
     ok(ret == count, "expected %u, got %u\n", count, ret);
     ok(color[count - 1] != 0, "expected !0, got %08x\n", color[count - 1]);
-}
 
     /* with trasparent color */
     hr = IWICPalette_InitializeFromBitmap(palette, (IWICBitmapSource *)bitmap, 16, TRUE);
-todo_wine
     ok(hr == S_OK, "InitializeFromBitmap error %#x\n", hr);
-if (hr == S_OK)
-{
     type = -1;
     hr = IWICPalette_GetType(palette, &type);
     ok(hr == S_OK, "GetType error %#x\n", hr);
@@ -653,7 +635,6 @@ if (hr == S_OK)
     ok(hr == S_OK, "GetColors error %#x\n", hr);
     ok(ret == count, "expected %u, got %u\n", count, ret);
     ok(color[count - 1] == 0, "expected 0, got %08x\n", color[count - 1]);
-}
 
     IWICPalette_Release(palette);
     IWICBitmap_Release(bitmap);
-- 
2.19.2