1/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
2/*
3 * Copyright © 2009 Mozilla Corporation
4 *
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Mozilla Corporation not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission. Mozilla Corporation makes no
12 * representations about the suitability of this software for any purpose. It
13 * is provided "as is" without express or implied warranty.
14 *
15 * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
17 * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
21 * OF THIS SOFTWARE.
22 *
23 * Author: Jeff Muizelaar, Mozilla Corp.
24 */
25
26//========================================================================
27//
28// Modified under the Poppler project - http://poppler.freedesktop.org
29//
30// All changes made under the Poppler project to this file are licensed
31// under GPL version 2 or later
32//
33// Copyright (C) 2012 Hib Eris <hib@hiberis.nl>
34// Copyright (C) 2012, 2017 Adrian Johnson <ajohnson@redneon.com>
35// Copyright (C) 2018 Adam Reichold <adam.reichold@t-online.de>
36// Copyright (C) 2019 Albert Astals Cid <aacid@kde.org>
37// Copyright (C) 2019 Marek Kasik <mkasik@redhat.com>
38//
39// To see a description of the changes please see the Changelog file that
40// came with your tarball or type make ChangeLog if you are building from git
41//
42//========================================================================
43
44/* This implements a box filter that supports non-integer box sizes */
45
46#include <config.h>
47
48#include <cstdint>
49#include <cstdint>
50#include <cstdio>
51#include <cassert>
52#include <cstdlib>
53#include <cmath>
54#include "goo/gmem.h"
55#include "CairoRescaleBox.h"
56
57/* we work in fixed point where 1. == 1 << 24 */
58#define FIXED_SHIFT 24
59
60static void downsample_row_box_filter(int start, int width, uint32_t *src, const uint32_t *src_limit, uint32_t *dest, const int coverage[], int pixel_coverage)
61{
62 /* we need an array of the pixel contribution of each destination pixel on the boundaries.
63 * we invert the value to get the value on the other size of the box */
64 /*
65
66 value = a * contribution * 1/box_size
67 value += a * 1/box_size
68 value += a * 1/box_size
69 value += a * 1/box_size
70 value += a * (1 - contribution) * 1/box_size
71 a * (1/box_size - contribution * 1/box_size)
72
73 box size is constant
74
75
76 value = a * contribution_a * 1/box_size + b * contribution_b * 1/box_size
77 contribution_b = (1 - contribution_a)
78 = (1 - contribution_a_next)
79 */
80
81 /* box size = ceil(src_width/dest_width) */
82 int x = 0;
83
84 /* skip to start */
85 /* XXX: it might be possible to do this directly instead of iteratively, however
86 * the iterative solution is simple */
87 while (x < start && src < src_limit) {
88 int box = 1 << FIXED_SHIFT;
89 int start_coverage = coverage[x];
90 box -= start_coverage;
91 src++;
92 while (box >= pixel_coverage && src < src_limit) {
93 src++;
94 box -= pixel_coverage;
95 }
96 x++;
97 }
98
99 while (x < start + width && src < src_limit) {
100 uint32_t a = 0;
101 uint32_t r = 0;
102 uint32_t g = 0;
103 uint32_t b = 0;
104 int box = 1 << FIXED_SHIFT;
105 int start_coverage = coverage[x];
106
107 a = ((*src >> 24) & 0xff) * start_coverage;
108 r = ((*src >> 16) & 0xff) * start_coverage;
109 g = ((*src >> 8) & 0xff) * start_coverage;
110 b = ((*src >> 0) & 0xff) * start_coverage;
111 src++;
112 x++;
113 box -= start_coverage;
114
115 while (box >= pixel_coverage && src < src_limit) {
116 a += ((*src >> 24) & 0xff) * pixel_coverage;
117 r += ((*src >> 16) & 0xff) * pixel_coverage;
118 g += ((*src >> 8) & 0xff) * pixel_coverage;
119 b += ((*src >> 0) & 0xff) * pixel_coverage;
120 src++;
121
122 box -= pixel_coverage;
123 }
124
125 /* multiply by whatever is leftover
126 * this ensures that we don't bias down.
127 * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
128 if (box > 0 && src < src_limit) {
129 a += ((*src >> 24) & 0xff) * box;
130 r += ((*src >> 16) & 0xff) * box;
131 g += ((*src >> 8) & 0xff) * box;
132 b += ((*src >> 0) & 0xff) * box;
133 }
134
135 a >>= FIXED_SHIFT;
136 r >>= FIXED_SHIFT;
137 g >>= FIXED_SHIFT;
138 b >>= FIXED_SHIFT;
139
140 *dest = (a << 24) | (r << 16) | (g << 8) | b;
141 dest++;
142 }
143}
144
145static void downsample_columns_box_filter(int n, int start_coverage, int pixel_coverage, uint32_t *src, uint32_t *dest)
146{
147 int stride = n;
148 while (n--) {
149 uint32_t a = 0;
150 uint32_t r = 0;
151 uint32_t g = 0;
152 uint32_t b = 0;
153 uint32_t *column_src = src;
154 int box = 1 << FIXED_SHIFT;
155
156 a = ((*column_src >> 24) & 0xff) * start_coverage;
157 r = ((*column_src >> 16) & 0xff) * start_coverage;
158 g = ((*column_src >> 8) & 0xff) * start_coverage;
159 b = ((*column_src >> 0) & 0xff) * start_coverage;
160 column_src += stride;
161 box -= start_coverage;
162
163 while (box >= pixel_coverage) {
164 a += ((*column_src >> 24) & 0xff) * pixel_coverage;
165 r += ((*column_src >> 16) & 0xff) * pixel_coverage;
166 g += ((*column_src >> 8) & 0xff) * pixel_coverage;
167 b += ((*column_src >> 0) & 0xff) * pixel_coverage;
168 column_src += stride;
169 box -= pixel_coverage;
170 }
171
172 if (box > 0) {
173 a += ((*column_src >> 24) & 0xff) * box;
174 r += ((*column_src >> 16) & 0xff) * box;
175 g += ((*column_src >> 8) & 0xff) * box;
176 b += ((*column_src >> 0) & 0xff) * box;
177 }
178
179 a >>= FIXED_SHIFT;
180 r >>= FIXED_SHIFT;
181 g >>= FIXED_SHIFT;
182 b >>= FIXED_SHIFT;
183
184 *dest = (a << 24) | (r << 16) | (g << 8) | b;
185 dest++;
186 src++;
187 }
188}
189
190static int compute_coverage(int coverage[], int src_length, int dest_length)
191{
192 int i;
193 /* num = src_length/dest_length
194 total = sum(pixel) / num
195
196 pixel * 1/num == pixel * dest_length / src_length
197 */
198 /* the average contribution of each source pixel */
199 int ratio = ((1 << 24) * (long long int)dest_length) / src_length;
200 /* because ((1 << 24)*(long long int)dest_length) won't always be divisible by src_length
201 * we'll need someplace to put the other bits.
202 *
203 * We want to ensure a + n*ratio < 1<<24
204 *
205 * 1<<24
206 * */
207
208 double scale = (double)src_length / dest_length;
209
210 /* for each destination pixel compute the coverage of the left most pixel included in the box */
211 /* I have a proof of this, which this margin is too narrow to contain */
212 for (i = 0; i < dest_length; i++) {
213 double left_side = i * scale;
214 double right_side = (i + 1) * scale;
215 double right_fract = right_side - floor(x: right_side);
216 double left_fract = ceil(x: left_side) - left_side;
217 int overage;
218 /* find out how many source pixels will be used to fill the box */
219 int count = floor(x: right_side) - ceil(x: left_side);
220 /* what's the maximum value this expression can become?
221 floor((i+1)*scale) - ceil(i*scale)
222
223 (i+1)*scale - i*scale == scale
224
225 since floor((i+1)*scale) <= (i+1)*scale
226 and ceil(i*scale) >= i*scale
227
228 floor((i+1)*scale) - ceil(i*scale) <= scale
229
230 further since: floor((i+1)*scale) - ceil(i*scale) is an integer
231
232 therefore:
233 floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
234 */
235
236 if (left_fract == 0.) {
237 count--;
238 }
239
240 /* compute how much the right-most pixel contributes */
241 overage = ratio * (right_fract);
242
243 /* the remainder is the amount that the left-most pixel
244 * contributes */
245 coverage[i] = (1 << 24) - (count * ratio + overage);
246 }
247
248 return ratio;
249}
250
251bool CairoRescaleBox::downScaleImage(unsigned orig_width, unsigned orig_height, signed scaled_width, signed scaled_height, unsigned short int start_column, unsigned short int start_row, unsigned short int width, unsigned short int height,
252 cairo_surface_t *dest_surface)
253{
254 int pixel_coverage_x, pixel_coverage_y;
255 int dest_y;
256 int src_y = 0;
257 uint32_t *scanline;
258 int *x_coverage = nullptr;
259 int *y_coverage = nullptr;
260 uint32_t *temp_buf = nullptr;
261 bool retval = false;
262 unsigned int *dest;
263 int dst_stride;
264
265 dest = reinterpret_cast<unsigned int *>(cairo_image_surface_get_data(surface: dest_surface));
266 dst_stride = cairo_image_surface_get_stride(surface: dest_surface);
267
268 scanline = (uint32_t *)gmallocn(count: orig_width, size: sizeof(int));
269
270 x_coverage = (int *)gmallocn(count: orig_width, size: sizeof(int));
271 y_coverage = (int *)gmallocn(count: orig_height, size: sizeof(int));
272
273 /* we need to allocate enough room for ceil(src_height/dest_height)+1
274 Example:
275 src_height = 140
276 dest_height = 50
277 src_height/dest_height = 2.8
278
279 |-------------| 2.8 pixels
280 |----|----|----|----| 4 pixels
281 need to sample 3 pixels
282
283 |-------------| 2.8 pixels
284 |----|----|----|----| 4 pixels
285 need to sample 4 pixels
286 */
287
288 temp_buf = (uint32_t *)gmallocn3(width: (orig_height + scaled_height - 1) / scaled_height + 1, height: scaled_width, size: sizeof(uint32_t));
289
290 if (!x_coverage || !y_coverage || !scanline || !temp_buf) {
291 goto cleanup;
292 }
293
294 pixel_coverage_x = compute_coverage(coverage: x_coverage, src_length: orig_width, dest_length: scaled_width);
295 pixel_coverage_y = compute_coverage(coverage: y_coverage, src_length: orig_height, dest_length: scaled_height);
296
297 assert(width + start_column <= scaled_width);
298
299 /* skip the rows at the beginning */
300 for (dest_y = 0; dest_y < start_row; dest_y++) {
301 int box = 1 << FIXED_SHIFT;
302 int start_coverage_y = y_coverage[dest_y];
303 box -= start_coverage_y;
304 src_y++;
305 while (box >= pixel_coverage_y) {
306 box -= pixel_coverage_y;
307 src_y++;
308 }
309 }
310
311 for (; dest_y < start_row + height; dest_y++) {
312 int columns = 0;
313 int box = 1 << FIXED_SHIFT;
314 int start_coverage_y = y_coverage[dest_y];
315
316 getRow(row_num: src_y, row_data: scanline);
317 downsample_row_box_filter(start: start_column, width, src: scanline, src_limit: scanline + orig_width, dest: temp_buf + width * columns, coverage: x_coverage, pixel_coverage: pixel_coverage_x);
318 columns++;
319 src_y++;
320 box -= start_coverage_y;
321
322 while (box >= pixel_coverage_y) {
323 getRow(row_num: src_y, row_data: scanline);
324 downsample_row_box_filter(start: start_column, width, src: scanline, src_limit: scanline + orig_width, dest: temp_buf + width * columns, coverage: x_coverage, pixel_coverage: pixel_coverage_x);
325 columns++;
326 src_y++;
327 box -= pixel_coverage_y;
328 }
329
330 /* downsample any leftovers */
331 if (box > 0) {
332 getRow(row_num: src_y, row_data: scanline);
333 downsample_row_box_filter(start: start_column, width, src: scanline, src_limit: scanline + orig_width, dest: temp_buf + width * columns, coverage: x_coverage, pixel_coverage: pixel_coverage_x);
334 columns++;
335 }
336
337 /* now scale the rows we just downsampled in the y direction */
338 downsample_columns_box_filter(n: width, start_coverage: start_coverage_y, pixel_coverage: pixel_coverage_y, src: temp_buf, dest);
339 dest += dst_stride / 4;
340
341 // assert(width*columns <= ((orig_height + scaled_height-1)/scaled_height+1) * width);
342 }
343 // assert (src_y<=orig_height);
344
345 retval = true;
346
347cleanup:
348 free(ptr: x_coverage);
349 free(ptr: y_coverage);
350 free(ptr: temp_buf);
351 free(ptr: scanline);
352
353 return retval;
354}
355

source code of poppler/poppler/CairoRescaleBox.cc