source/libs/poppler/poppler-0.36.0/poppler/CairoRescaleBox.cc

   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 Adrian Johnson <ajohnson@redneon.com>
  35 //
  36 // To see a description of the changes please see the Changelog file that
  37 // came with your tarball or type make ChangeLog if you are building from git
  38 //
  39 //========================================================================
  40
  41
  42 /* This implements a box filter that supports non-integer box sizes */
  43
  44 #ifdef HAVE_CONFIG_H
  45 #include <config.h>
  46 #endif
  47
  48 #include <stdint.h>
  49 #include <stdio.h>
  50 #include <assert.h>
  51 #include <stdlib.h>
  52 #include <math.h>
  53 #include "goo/gmem.h"
  54 #include "goo/gtypes_p.h"
  55 #include "CairoRescaleBox.h"
  56
  57
  58 /* we work in fixed point where 1. == 1 << 24 */
  59 #define FIXED_SHIFT 24
  60
  61
  62 static void downsample_row_box_filter (
  63         int start, int width,
  64         uint32_t *src, uint32_t *dest,
  65         int coverage[], int pixel_coverage)
  66 {
  67     /* we need an array of the pixel contribution of each destination pixel on the boundaries.
  68      * we invert the value to get the value on the other size of the box */
  69     /*
  70
  71        value  = a * contribution * 1/box_size
  72        value += a * 1/box_size
  73        value += a * 1/box_size
  74        value += a * 1/box_size
  75        value += a * (1 - contribution) * 1/box_size
  76                 a * (1/box_size - contribution * 1/box_size)
  77
  78         box size is constant
  79
  80
  81        value = a * contribtion_a * 1/box_size + b * contribution_b * 1/box_size
  82                contribution_b = (1 - contribution_a)
  83                               = (1 - contribution_a_next)
  84     */
  85
  86     /* box size = ceil(src_width/dest_width) */
  87     int x = 0;
  88
  89     /* skip to start */
  90     /* XXX: it might be possible to do this directly instead of iteratively, however
  91      * the iterative solution is simple */
  92     while (x < start)
  93     {
  94         int box = 1 << FIXED_SHIFT;
  95         int start_coverage = coverage[x];
  96         box -= start_coverage;
  97         src++;
  98         while (box >= pixel_coverage)
  99         {
 100             src++;
 101             box -= pixel_coverage;
 102         }
 103         x++;
 104     }
 105
 106     while (x < start + width)
 107     {
 108         uint32_t a = 0;
 109         uint32_t r = 0;
 110         uint32_t g = 0;
 111         uint32_t b = 0;
 112         int box = 1 << FIXED_SHIFT;
 113         int start_coverage = coverage[x];
 114
 115         a = ((*src >> 24) & 0xff) * start_coverage;
 116         r = ((*src >> 16) & 0xff) * start_coverage;
 117         g = ((*src >>  8) & 0xff) * start_coverage;
 118         b = ((*src >>  0) & 0xff) * start_coverage;
 119         src++;
 120         x++;
 121         box -= start_coverage;
 122
 123         while (box >= pixel_coverage)
 124         {
 125             a += ((*src >> 24) & 0xff) * pixel_coverage;
 126             r += ((*src >> 16) & 0xff) * pixel_coverage;
 127             g += ((*src >>  8) & 0xff) * pixel_coverage;
 128             b += ((*src >>  0) & 0xff) * pixel_coverage;
 129             src++;
 130
 131             box -= pixel_coverage;
 132         }
 133
 134         /* multiply by whatever is leftover
 135          * this ensures that we don't bias down.
 136          * i.e. start_coverage + n*pixel_coverage + box == 1 << 24 */
 137         if (box > 0)
 138         {
 139             a += ((*src >> 24) & 0xff) * box;
 140             r += ((*src >> 16) & 0xff) * box;
 141             g += ((*src >>  8) & 0xff) * box;
 142             b += ((*src >>  0) & 0xff) * box;
 143         }
 144
 145         a >>= FIXED_SHIFT;
 146         r >>= FIXED_SHIFT;
 147         g >>= FIXED_SHIFT;
 148         b >>= FIXED_SHIFT;
 149
 150         *dest = (a << 24) | (r << 16) | (g << 8) | b;
 151         dest++;
 152     }
 153 }
 154
 155 static void downsample_columns_box_filter (
 156         int n,
 157         int start_coverage,
 158         int pixel_coverage,
 159         uint32_t *src, uint32_t *dest)
 160 {
 161     int stride = n;
 162     while (n--) {
 163         uint32_t a = 0;
 164         uint32_t r = 0;
 165         uint32_t g = 0;
 166         uint32_t b = 0;
 167         uint32_t *column_src = src;
 168         int box = 1 << FIXED_SHIFT;
 169
 170         a = ((*column_src >> 24) & 0xff) * start_coverage;
 171         r = ((*column_src >> 16) & 0xff) * start_coverage;
 172         g = ((*column_src >>  8) & 0xff) * start_coverage;
 173         b = ((*column_src >>  0) & 0xff) * start_coverage;
 174         column_src += stride;
 175         box -= start_coverage;
 176
 177         while (box >= pixel_coverage)
 178         {
 179             a += ((*column_src >> 24) & 0xff) * pixel_coverage;
 180             r += ((*column_src >> 16) & 0xff) * pixel_coverage;
 181             g += ((*column_src >>  8) & 0xff) * pixel_coverage;
 182             b += ((*column_src >>  0) & 0xff) * pixel_coverage;
 183             column_src += stride;
 184             box -= pixel_coverage;
 185         }
 186
 187         if (box > 0) {
 188             a += ((*column_src >> 24) & 0xff) * box;
 189             r += ((*column_src >> 16) & 0xff) * box;
 190             g += ((*column_src >>  8) & 0xff) * box;
 191             b += ((*column_src >>  0) & 0xff) * box;
 192         }
 193
 194         a >>= FIXED_SHIFT;
 195         r >>= FIXED_SHIFT;
 196         g >>= FIXED_SHIFT;
 197         b >>= FIXED_SHIFT;
 198
 199         *dest = (a << 24) | (r << 16) | (g << 8) | b;
 200         dest++;
 201         src++;
 202     }
 203 }
 204
 205 static int compute_coverage (int coverage[], int src_length, int dest_length)
 206 {
 207     int i;
 208     /* num = src_length/dest_length
 209        total = sum(pixel) / num
 210
 211        pixel * 1/num == pixel * dest_length / src_length
 212     */
 213     /* the average contribution of each source pixel */
 214     int ratio = ((1 << 24)*(long long int)dest_length)/src_length;
 215     /* because ((1 << 24)*(long long int)dest_length) won't always be divisible by src_length
 216      * we'll need someplace to put the other bits.
 217      *
 218      * We want to ensure a + n*ratio < 1<<24
 219      *
 220      * 1<<24
 221      * */
 222
 223     double scale = (double)src_length/dest_length;
 224
 225     /* for each destination pixel compute the coverage of the left most pixel included in the box */
 226     /* I have a proof of this, which this margin is too narrow to contain */
 227     for (i=0; i<dest_length; i++)
 228     {
 229         float left_side = i*scale;
 230         float right_side = (i+1)*scale;
 231         float right_fract = right_side - floor (right_side);
 232         float left_fract = ceil (left_side) - left_side;
 233         int overage;
 234         /* find out how many source pixels will be used to fill the box */
 235         int count = floor (right_side) - ceil (left_side);
 236         /* what's the maximum value this expression can become?
 237            floor((i+1)*scale) - ceil(i*scale)
 238
 239            (i+1)*scale - i*scale == scale
 240
 241            since floor((i+1)*scale) <= (i+1)*scale
 242            and   ceil(i*scale)      >= i*scale
 243
 244            floor((i+1)*scale) - ceil(i*scale) <= scale
 245
 246            further since: floor((i+1)*scale) - ceil(i*scale) is an integer
 247
 248            therefore:
 249            floor((i+1)*scale) - ceil(i*scale) <= floor(scale)
 250         */
 251
 252         if (left_fract == 0.)
 253             count--;
 254
 255         /* compute how much the right-most pixel contributes */
 256         overage = ratio*(right_fract);
 257
 258         /* the remainder is the the amount that the left-most pixel
 259          * contributes */
 260         coverage[i] = (1<<24) - (count * ratio + overage);
 261     }
 262
 263     return ratio;
 264 }
 265
 266
 267 GBool CairoRescaleBox::downScaleImage(unsigned orig_width, unsigned orig_height,
 268                                       signed scaled_width, signed scaled_height,
 269                                       unsigned short int start_column, unsigned short int start_row,
 270                                       unsigned short int width, unsigned short int height,
 271                                       cairo_surface_t *dest_surface) {
 272   int pixel_coverage_x, pixel_coverage_y;
 273   int dest_y;
 274   int src_y = 0;
 275   uint32_t *scanline;
 276   int *x_coverage = NULL;
 277   int *y_coverage = NULL;
 278   uint32_t *temp_buf = NULL;
 279   GBool retval = gFalse;
 280   unsigned int *dest;
 281   int dst_stride;
 282
 283   dest = (unsigned int *)cairo_image_surface_get_data (dest_surface);
 284   dst_stride = cairo_image_surface_get_stride (dest_surface);
 285
 286   scanline = (uint32_t*)gmallocn3 (orig_width, 1, sizeof(int));
 287
 288   x_coverage = (int *)gmallocn3 (orig_width, 1, sizeof(int));
 289   y_coverage = (int *)gmallocn3 (orig_height, 1, sizeof(int));
 290
 291   /* we need to allocate enough room for ceil(src_height/dest_height)+1
 292      Example:
 293      src_height = 140
 294      dest_height = 50
 295      src_height/dest_height = 2.8
 296
 297      |-------------|       2.8 pixels
 298      |----|----|----|----| 4 pixels
 299      need to sample 3 pixels
 300
 301      |-------------|       2.8 pixels
 302      |----|----|----|----| 4 pixels
 303      need to sample 4 pixels
 304   */
 305
 306   temp_buf = (uint32_t *)gmallocn3 ((orig_height + scaled_height-1)/scaled_height+1, scaled_width, sizeof(uint32_t));
 307
 308   if (!x_coverage || !y_coverage || !scanline || !temp_buf)
 309     goto cleanup;
 310
 311   pixel_coverage_x = compute_coverage (x_coverage, orig_width, scaled_width);
 312   pixel_coverage_y = compute_coverage (y_coverage, orig_height, scaled_height);
 313
 314   assert (width + start_column <= scaled_width);
 315
 316
 317
 318   /* skip the rows at the beginning */
 319   for (dest_y = 0; dest_y < start_row; dest_y++)
 320   {
 321     int box = 1 << FIXED_SHIFT;
 322     int start_coverage_y = y_coverage[dest_y];
 323     box -= start_coverage_y;
 324     src_y++;
 325     while (box >= pixel_coverage_y)
 326     {
 327       box -= pixel_coverage_y;
 328       src_y++;
 329     }
 330   }
 331
 332   for (; dest_y < start_row + height; dest_y++)
 333   {
 334     int columns = 0;
 335     int box = 1 << FIXED_SHIFT;
 336     int start_coverage_y = y_coverage[dest_y];
 337
 338     getRow(src_y, scanline);
 339     downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
 340     columns++;
 341     src_y++;
 342     box -= start_coverage_y;
 343
 344     while (box >= pixel_coverage_y)
 345     {
 346       getRow(src_y, scanline);
 347       downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
 348       columns++;
 349       src_y++;
 350       box -= pixel_coverage_y;
 351     }
 352
 353     /* downsample any leftovers */
 354     if (box > 0)
 355     {
 356       getRow(src_y, scanline);
 357       downsample_row_box_filter (start_column, width, scanline, temp_buf + width * columns, x_coverage, pixel_coverage_x);
 358       columns++;
 359     }
 360
 361     /* now scale the rows we just downsampled in the y direction */
 362     downsample_columns_box_filter (width, start_coverage_y, pixel_coverage_y, temp_buf, dest);
 363     dest += dst_stride / 4;
 364
 365 //        assert(width*columns <= ((orig_height + scaled_height-1)/scaled_height+1) * width);
 366   }
 367 //    assert (src_y<=orig_height);
 368
 369   retval = gTrue;
 370
 371 cleanup:
 372   free (x_coverage);
 373   free (y_coverage);
 374   free (temp_buf);
 375   free (scanline);
 376
 377   return retval;
 378 }