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 | |
60 | static 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 | |
145 | static 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 | |
190 | static 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 | |
251 | bool 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 | |
347 | cleanup: |
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 | |