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.20.1
