CairoRescaleBox.cc 12 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* -*- Mode: c; c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t; -*- */
/*
 * Copyright © 2009 Mozilla Corporation
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Mozilla Corporation not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  Mozilla Corporation makes no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * MOZILLA CORPORATION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT
 * SHALL MOZILLA CORPORATION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
 * OF THIS SOFTWARE.
 *
 * Author: Jeff Muizelaar, Mozilla Corp.
 */

Albert Astals Cid's avatar
Albert Astals Cid committed
26
27
28
29
30
31
32
33
//========================================================================
//
// Modified under the Poppler project - http://poppler.freedesktop.org
//
// All changes made under the Poppler project to this file are licensed
// under GPL version 2 or later
//
// 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>
Albert Astals Cid's avatar
Albert Astals Cid committed
36
// Copyright (C) 2019 Albert Astals Cid <aacid@kde.org>
37
// Copyright (C) 2019 Marek Kasik <mkasik@redhat.com>
Albert Astals Cid's avatar
Albert Astals Cid committed
38
39
40
41
42
43
44
//
// To see a description of the changes please see the Changelog file that
// came with your tarball or type make ChangeLog if you are building from git
//
//========================================================================


45
46
47
48
/* This implements a box filter that supports non-integer box sizes */

#include <config.h>

49
#include <cstdint>
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <math.h>
#include "goo/gmem.h"
#include "CairoRescaleBox.h"


/* we work in fixed point where 1. == 1 << 24 */
#define FIXED_SHIFT 24

62

63
64
static void downsample_row_box_filter (
        int start, int width,
65
        uint32_t *src, uint32_t *src_limit, uint32_t *dest,
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
        int coverage[], int pixel_coverage)
{
    /* we need an array of the pixel contribution of each destination pixel on the boundaries.
     * we invert the value to get the value on the other size of the box */
    /*

       value  = a * contribution * 1/box_size
       value += a * 1/box_size
       value += a * 1/box_size
       value += a * 1/box_size
       value += a * (1 - contribution) * 1/box_size
                a * (1/box_size - contribution * 1/box_size)

        box size is constant


Yuri Chornoivan's avatar
Yuri Chornoivan committed
82
       value = a * contribution_a * 1/box_size + b * contribution_b * 1/box_size
83
84
85
86
87
88
89
90
91
92
               contribution_b = (1 - contribution_a)
                              = (1 - contribution_a_next)
    */

    /* box size = ceil(src_width/dest_width) */
    int x = 0;

    /* skip to start */
    /* XXX: it might be possible to do this directly instead of iteratively, however
     * the iterative solution is simple */
93
    while (x < start && src < src_limit)
94
95
96
97
98
    {
        int box = 1 << FIXED_SHIFT;
        int start_coverage = coverage[x];
        box -= start_coverage;
        src++;
99
        while (box >= pixel_coverage && src < src_limit)
100
101
102
103
104
105
106
        {
            src++;
            box -= pixel_coverage;
        }
        x++;
    }

107
    while (x < start + width && src < src_limit)
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
    {
        uint32_t a = 0;
        uint32_t r = 0;
        uint32_t g = 0;
        uint32_t b = 0;
        int box = 1 << FIXED_SHIFT;
        int start_coverage = coverage[x];

        a = ((*src >> 24) & 0xff) * start_coverage;
        r = ((*src >> 16) & 0xff) * start_coverage;
        g = ((*src >>  8) & 0xff) * start_coverage;
        b = ((*src >>  0) & 0xff) * start_coverage;
        src++;
        x++;
        box -= start_coverage;

124
        while (box >= pixel_coverage && src < src_limit)
125
126
127
128
129
130
131
132
133
134
135
136
137
        {
            a += ((*src >> 24) & 0xff) * pixel_coverage;
            r += ((*src >> 16) & 0xff) * pixel_coverage;
            g += ((*src >>  8) & 0xff) * pixel_coverage;
            b += ((*src >>  0) & 0xff) * pixel_coverage;
            src++;

            box -= pixel_coverage;
        }

        /* multiply by whatever is leftover
         * this ensures that we don't bias down.
         * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
138
        if (box > 0 && src < src_limit)
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
        {
            a += ((*src >> 24) & 0xff) * box;
            r += ((*src >> 16) & 0xff) * box;
            g += ((*src >>  8) & 0xff) * box;
            b += ((*src >>  0) & 0xff) * box;
        }

        a >>= FIXED_SHIFT;
        r >>= FIXED_SHIFT;
        g >>= FIXED_SHIFT;
        b >>= FIXED_SHIFT;

        *dest = (a << 24) | (r << 16) | (g << 8) | b;
        dest++;
    }
}

static void downsample_columns_box_filter (
        int n,
        int start_coverage,
        int pixel_coverage,
        uint32_t *src, uint32_t *dest)
{
    int stride = n;
    while (n--) {
        uint32_t a = 0;
        uint32_t r = 0;
        uint32_t g = 0;
        uint32_t b = 0;
        uint32_t *column_src = src;
        int box = 1 << FIXED_SHIFT;

        a = ((*column_src >> 24) & 0xff) * start_coverage;
        r = ((*column_src >> 16) & 0xff) * start_coverage;
        g = ((*column_src >>  8) & 0xff) * start_coverage;
        b = ((*column_src >>  0) & 0xff) * start_coverage;
        column_src += stride;
        box -= start_coverage;

        while (box >= pixel_coverage)
        {
            a += ((*column_src >> 24) & 0xff) * pixel_coverage;
            r += ((*column_src >> 16) & 0xff) * pixel_coverage;
            g += ((*column_src >>  8) & 0xff) * pixel_coverage;
            b += ((*column_src >>  0) & 0xff) * pixel_coverage;
            column_src += stride;
            box -= pixel_coverage;
        }

        if (box > 0) {
            a += ((*column_src >> 24) & 0xff) * box;
            r += ((*column_src >> 16) & 0xff) * box;
            g += ((*column_src >>  8) & 0xff) * box;
            b += ((*column_src >>  0) & 0xff) * box;
        }

        a >>= FIXED_SHIFT;
        r >>= FIXED_SHIFT;
        g >>= FIXED_SHIFT;
        b >>= FIXED_SHIFT;

        *dest = (a << 24) | (r << 16) | (g << 8) | b;
        dest++;
        src++;
    }
}

static int compute_coverage (int coverage[], int src_length, int dest_length)
{
    int i;
    /* num = src_length/dest_length
       total = sum(pixel) / num

       pixel * 1/num == pixel * dest_length / src_length
    */
    /* the average contribution of each source pixel */
    int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
    /* because ((1 << 24)*(long long int)dest_length) won't always be divisible by src_length
     * we'll need someplace to put the other bits.
     *
     * We want to ensure a + n*ratio < 1<<24
     *
     * 1<<24
     * */

    double scale = (double)src_length/dest_length;

    /* for each destination pixel compute the coverage of the left most pixel included in the box */
    /* I have a proof of this, which this margin is too narrow to contain */
    for (i=0; i<dest_length; i++)
    {
230
231
232
233
        double left_side = i*scale;
        double right_side = (i+1)*scale;
        double right_fract = right_side - floor (right_side);
        double left_fract = ceil (left_side) - left_side;
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
        int overage;
        /* find out how many source pixels will be used to fill the box */
        int count = floor (right_side) - ceil (left_side);
        /* what's the maximum value this expression can become?
           floor((i+1)*scale) - ceil(i*scale)

           (i+1)*scale - i*scale == scale

           since floor((i+1)*scale) <= (i+1)*scale
           and   ceil(i*scale)      >= i*scale

           floor((i+1)*scale) - ceil(i*scale) <= scale

           further since: floor((i+1)*scale) - ceil(i*scale) is an integer

           therefore:
           floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
        */

        if (left_fract == 0.)
            count--;

        /* compute how much the right-most pixel contributes */
        overage = ratio*(right_fract);

Yuri Chornoivan's avatar
Yuri Chornoivan committed
259
        /* the remainder is the amount that the left-most pixel
260
261
262
263
264
265
266
267
         * contributes */
        coverage[i] = (1<<24) - (count * ratio + overage);
    }

    return ratio;
}


268
bool CairoRescaleBox::downScaleImage(unsigned orig_width, unsigned orig_height,
269
270
271
272
273
274
275
276
                                      signed scaled_width, signed scaled_height,
                                      unsigned short int start_column, unsigned short int start_row,
                                      unsigned short int width, unsigned short int height,
                                      cairo_surface_t *dest_surface) {
  int pixel_coverage_x, pixel_coverage_y;
  int dest_y;
  int src_y = 0;
  uint32_t *scanline;
277
278
279
  int *x_coverage = nullptr;
  int *y_coverage = nullptr;
  uint32_t *temp_buf = nullptr;
280
  bool retval = false;
281
282
283
  unsigned int *dest;
  int dst_stride;

284
  dest = reinterpret_cast<unsigned int *>(cairo_image_surface_get_data (dest_surface));
285
286
  dst_stride = cairo_image_surface_get_stride (dest_surface);

287
  scanline = (uint32_t*)gmallocn (orig_width, sizeof(int));
288

289
290
  x_coverage = (int *)gmallocn (orig_width, sizeof(int));
  y_coverage = (int *)gmallocn (orig_height, sizeof(int));
291
292
293
294
295
296

  /* we need to allocate enough room for ceil(src_height/dest_height)+1
     Example:
     src_height = 140
     dest_height = 50
     src_height/dest_height = 2.8
297

298
299
300
     |-------------|       2.8 pixels
     |----|----|----|----| 4 pixels
     need to sample 3 pixels
301

302
303
304
305
     |-------------|       2.8 pixels
     |----|----|----|----| 4 pixels
     need to sample 4 pixels
  */
306

307
  temp_buf = (uint32_t *)gmallocn3 ((orig_height + scaled_height-1)/scaled_height+1, scaled_width, sizeof(uint32_t));
308

309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
  if (!x_coverage || !y_coverage || !scanline || !temp_buf)
    goto cleanup;

  pixel_coverage_x = compute_coverage (x_coverage, orig_width, scaled_width);
  pixel_coverage_y = compute_coverage (y_coverage, orig_height, scaled_height);

  assert (width + start_column <= scaled_width);



  /* skip the rows at the beginning */
  for (dest_y = 0; dest_y < start_row; dest_y++)
  {
    int box = 1 << FIXED_SHIFT;
    int start_coverage_y = y_coverage[dest_y];
    box -= start_coverage_y;
    src_y++;
    while (box >= pixel_coverage_y)
327
    {
328
329
      box -= pixel_coverage_y;
      src_y++;
330
    }
331
  }
332

333
334
335
336
337
  for (; dest_y < start_row + height; dest_y++)
  {
    int columns = 0;
    int box = 1 << FIXED_SHIFT;
    int start_coverage_y = y_coverage[dest_y];
338

339
    getRow(src_y, scanline);
340
    downsample_row_box_filter (start_column, width, scanline, scanline + orig_width, temp_buf + width * columns, x_coverage, pixel_coverage_x);
341
342
343
    columns++;
    src_y++;
    box -= start_coverage_y;
344

345
346
347
    while (box >= pixel_coverage_y)
    {
      getRow(src_y, scanline);
348
      downsample_row_box_filter (start_column, width, scanline, scanline + orig_width, temp_buf + width * columns, x_coverage, pixel_coverage_x);
349
350
351
352
      columns++;
      src_y++;
      box -= pixel_coverage_y;
    }
353

354
355
356
357
    /* downsample any leftovers */
    if (box > 0)
    {
      getRow(src_y, scanline);
358
      downsample_row_box_filter (start_column, width, scanline, scanline + orig_width, temp_buf + width * columns, x_coverage, pixel_coverage_x);
359
360
      columns++;
    }
361

362
363
364
    /* now scale the rows we just downsampled in the y direction */
    downsample_columns_box_filter (width, start_coverage_y, pixel_coverage_y, temp_buf, dest);
    dest += dst_stride / 4;
365
366

//        assert(width*columns <= ((orig_height + scaled_height-1)/scaled_height+1) * width);
367
  }
368
369
//    assert (src_y<=orig_height);

370
  retval = true;
371
372

cleanup:
373
374
375
376
  free (x_coverage);
  free (y_coverage);
  free (temp_buf);
  free (scanline);
377

378
  return retval;
379
}