Based on median cut implementation created by Sebastian Lackner.
Signed-off-by: Dmitry Timoshkov dmitry@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);