1 //C- -*- C++ -*-
2 //C- -------------------------------------------------------------------
3 //C- DjVuLibre-3.5
4 //C- Copyright (c) 2002 Leon Bottou and Yann Le Cun.
5 //C- Copyright (c) 2001 AT&T
6 //C-
7 //C- This software is subject to, and may be distributed under, the
8 //C- GNU General Public License, either Version 2 of the license,
9 //C- or (at your option) any later version. The license should have
10 //C- accompanied the software or you may obtain a copy of the license
11 //C- from the Free Software Foundation at http://www.fsf.org .
12 //C-
13 //C- This program is distributed in the hope that it will be useful,
14 //C- but WITHOUT ANY WARRANTY; without even the implied warranty of
15 //C- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 //C- GNU General Public License for more details.
17 //C-
18 //C- DjVuLibre-3.5 is derived from the DjVu(r) Reference Library from
19 //C- Lizardtech Software. Lizardtech Software has authorized us to
20 //C- replace the original DjVu(r) Reference Library notice by the following
21 //C- text (see doc/lizard2002.djvu and doc/lizardtech2007.djvu):
22 //C-
23 //C- ------------------------------------------------------------------
24 //C- | DjVu (r) Reference Library (v. 3.5)
25 //C- | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.
26 //C- | The DjVu Reference Library is protected by U.S. Pat. No.
27 //C- | 6,058,214 and patents pending.
28 //C- |
29 //C- | This software is subject to, and may be distributed under, the
30 //C- | GNU General Public License, either Version 2 of the license,
31 //C- | or (at your option) any later version. The license should have
32 //C- | accompanied the software or you may obtain a copy of the license
33 //C- | from the Free Software Foundation at http://www.fsf.org .
34 //C- |
35 //C- | The computer code originally released by LizardTech under this
36 //C- | license and unmodified by other parties is deemed "the LIZARDTECH
37 //C- | ORIGINAL CODE." Subject to any third party intellectual property
38 //C- | claims, LizardTech grants recipient a worldwide, royalty-free,
39 //C- | non-exclusive license to make, use, sell, or otherwise dispose of
40 //C- | the LIZARDTECH ORIGINAL CODE or of programs derived from the
41 //C- | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU
42 //C- | General Public License. This grant only confers the right to
43 //C- | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to
44 //C- | the extent such infringement is reasonably necessary to enable
45 //C- | recipient to make, have made, practice, sell, or otherwise dispose
46 //C- | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to
47 //C- | any greater extent that may be necessary to utilize further
48 //C- | modifications or combinations.
49 //C- |
50 //C- | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY
51 //C- | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
52 //C- | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF
53 //C- | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
54 //C- +------------------------------------------------------------------
55
56 #ifdef HAVE_CONFIG_H
57 # include "config.h"
58 #endif
59 #if NEED_GNUG_PRAGMAS
60 # pragma implementation
61 #endif
62
63 // Rescale images with fast bilinear interpolation
64 // From: Leon Bottou, 1/31/2002
65 // Almost equal to my initial code.
66
67 #include "GScaler.h"
68
69
70 #ifdef HAVE_NAMESPACES
71 namespace DJVU {
72 # ifdef NOT_DEFINED // Just to fool emacs c++ mode
73 }
74 #endif
75 #endif
76
77
78 ////////////////////////////////////////
79 // CONSTANTS
80
81
82 #define FRACBITS 4
83 #define FRACSIZE (1<<FRACBITS)
84 #define FRACSIZE2 (FRACSIZE>>1)
85 #define FRACMASK (FRACSIZE-1)
86
87
88
89
90
91
92 ////////////////////////////////////////
93 // UTILITIES
94
95
96 static int interp_ok = 0;
97 static short interp[FRACSIZE][512];
98
99 static void
prepare_interp()100 prepare_interp()
101 {
102 if (! interp_ok)
103 {
104 interp_ok = 1;
105 for (int i=0; i<FRACSIZE; i++)
106 {
107 short *deltas = & interp[i][256];
108 for (int j = -255; j <= 255; j++)
109 deltas[j] = ( j*i + FRACSIZE2 ) >> FRACBITS;
110 }
111 }
112 }
113
114
115 static inline int
mini(int x,int y)116 mini(int x, int y)
117 {
118 return (x < y ? x : y);
119 }
120
121
122 static inline int
maxi(int x,int y)123 maxi(int x, int y)
124 {
125 return (x > y ? x : y);
126 }
127
128
129
130
131
132
133 ////////////////////////////////////////
134 // GSCALER
135
136
GScaler()137 GScaler::GScaler()
138 : inw(0), inh(0),
139 xshift(0), yshift(0), redw(0), redh(0),
140 outw(0), outh(0),
141 gvcoord(vcoord,0), ghcoord(hcoord,0)
142 {
143 }
144
145
~GScaler()146 GScaler::~GScaler()
147 {
148 }
149
150
151 void
set_input_size(int w,int h)152 GScaler::set_input_size(int w, int h)
153 {
154 inw = w;
155 inh = h;
156 if (vcoord)
157 {
158 gvcoord.resize(0);
159 }
160 if (hcoord)
161 {
162 ghcoord.resize(0);
163 }
164 }
165
166
167 void
set_output_size(int w,int h)168 GScaler::set_output_size(int w, int h)
169 {
170 outw = w;
171 outh = h;
172 if (vcoord)
173 {
174 gvcoord.resize(0);
175 }
176 if (hcoord)
177 {
178 ghcoord.resize(0);
179 }
180 }
181
182
183 static void
prepare_coord(int * coord,int inmax,int outmax,int in,int out)184 prepare_coord(int *coord, int inmax, int outmax, int in, int out)
185 {
186 int len = (in*FRACSIZE);
187 int beg = (len+out)/(2*out) - FRACSIZE2;
188 // Bresenham algorithm
189 int y = beg;
190 int z = out/2;
191 int inmaxlim = (inmax-1)*FRACSIZE;
192 for (int x=0; x<outmax; x++)
193 {
194 coord[x] = mini(y,inmaxlim);
195 z = z + len;
196 y = y + z / out;
197 z = z % out;
198 }
199 // Result must fit exactly
200 if (out==outmax && y!=beg+len)
201 G_THROW( ERR_MSG("GScaler.assertion") );
202 }
203
204
205 void
set_horz_ratio(int numer,int denom)206 GScaler::set_horz_ratio(int numer, int denom)
207 {
208 if (! (inw>0 && inh>0 && outw>0 && outh>0))
209 G_THROW( ERR_MSG("GScaler.undef_size") );
210 // Implicit ratio (determined by the input/output sizes)
211 if (numer==0 && denom==0) {
212 numer = outw;
213 denom = inw;
214 } else if (numer<=0 || denom<=0)
215 G_THROW( ERR_MSG("GScaler.ratios") );
216 // Compute horz reduction
217 xshift = 0;
218 redw = inw;
219 while (numer+numer < denom) {
220 xshift += 1;
221 redw = (redw + 1) >> 1;
222 numer = numer << 1;
223 }
224 // Compute coordinate table
225 if (! hcoord)
226 ghcoord.resize(outw);
227 prepare_coord(hcoord, redw, outw, denom, numer);
228 }
229
230
231 void
set_vert_ratio(int numer,int denom)232 GScaler::set_vert_ratio(int numer, int denom)
233 {
234 if (! (inw>0 && inh>0 && outw>0 && outh>0))
235 G_THROW( ERR_MSG("GScaler.undef_size") );
236 // Implicit ratio (determined by the input/output sizes)
237 if (numer==0 && denom==0) {
238 numer = outh;
239 denom = inh;
240 } else if (numer<=0 || denom<=0)
241 G_THROW( ERR_MSG("GScaler.ratios") );
242 // Compute horz reduction
243 yshift = 0;
244 redh = inh;
245 while (numer+numer < denom) {
246 yshift += 1;
247 redh = (redh + 1) >> 1;
248 numer = numer << 1;
249 }
250 // Compute coordinate table
251 if (! vcoord)
252 {
253 gvcoord.resize(outh);
254 }
255 prepare_coord(vcoord, redh, outh, denom, numer);
256 }
257
258
259 void
make_rectangles(const GRect & desired,GRect & red,GRect & inp)260 GScaler::make_rectangles(const GRect &desired, GRect &red, GRect &inp)
261 {
262 // Parameter validation
263 if (desired.xmin<0 || desired.ymin<0 ||
264 desired.xmax>outw || desired.ymax>outh )
265 G_THROW( ERR_MSG("GScaler.too_big") );
266 // Compute ratio (if not done yet)
267 if (!vcoord)
268 set_vert_ratio(0,0);
269 if (!hcoord)
270 set_horz_ratio(0,0);
271 // Compute reduced bounds
272 red.xmin = (hcoord[desired.xmin]) >> FRACBITS;
273 red.ymin = (vcoord[desired.ymin]) >> FRACBITS;
274 red.xmax = (hcoord[desired.xmax-1]+FRACSIZE-1) >> FRACBITS;
275 red.ymax = (vcoord[desired.ymax-1]+FRACSIZE-1) >> FRACBITS;
276 // Borders
277 red.xmin = maxi(red.xmin, 0);
278 red.xmax = mini(red.xmax+1, redw);
279 red.ymin = maxi(red.ymin, 0);
280 red.ymax = mini(red.ymax+1, redh);
281 // Input
282 inp.xmin = maxi(red.xmin<<xshift, 0);
283 inp.xmax = mini(red.xmax<<xshift, inw);
284 inp.ymin = maxi(red.ymin<<yshift, 0);
285 inp.ymax = mini(red.ymax<<yshift, inh);
286 }
287
288
289 void
get_input_rect(const GRect & desired_output,GRect & required_input)290 GScaler::get_input_rect( const GRect &desired_output, GRect &required_input )
291 {
292 GRect red;
293 make_rectangles(desired_output, red, required_input);
294 }
295
296
297
298
299
300
301 ////////////////////////////////////////
302 // GBITMAPSCALER
303
304
GBitmapScaler()305 GBitmapScaler::GBitmapScaler()
306 : glbuffer(lbuffer,0), gconv(conv,0), gp1(p1,0), gp2(p2,0)
307 {
308 }
309
310
GBitmapScaler(int inw,int inh,int outw,int outh)311 GBitmapScaler::GBitmapScaler(int inw, int inh, int outw, int outh)
312 : glbuffer(lbuffer,0), gconv(conv,0), gp1(p1,0), gp2(p2,0)
313 {
314 set_input_size(inw, inh);
315 set_output_size(outw, outh);
316 }
317
318
~GBitmapScaler()319 GBitmapScaler::~GBitmapScaler()
320 {
321 }
322
323
324 unsigned char *
get_line(int fy,const GRect & required_red,const GRect & provided_input,const GBitmap & input)325 GBitmapScaler::get_line(int fy,
326 const GRect &required_red,
327 const GRect &provided_input,
328 const GBitmap &input )
329 {
330 if (fy < required_red.ymin)
331 fy = required_red.ymin;
332 else if (fy >= required_red.ymax)
333 fy = required_red.ymax - 1;
334 // Cached line
335 if (fy == l2)
336 return p2;
337 if (fy == l1)
338 return p1;
339 // Shift
340 unsigned char *p = p1;
341 p1 = p2;
342 l1 = l2;
343 p2 = p;
344 l2 = fy;
345 if (xshift==0 && yshift==0)
346 {
347 // Fast mode
348 int dx = required_red.xmin-provided_input.xmin;
349 int dx1 = required_red.xmax-provided_input.xmin;
350 const unsigned char *inp1 = input[fy-provided_input.ymin] + dx;
351 while (dx++ < dx1)
352 *p++ = conv[*inp1++];
353 return p2;
354 }
355 else
356 {
357 // Compute location of line
358 GRect line;
359 line.xmin = required_red.xmin << xshift;
360 line.xmax = required_red.xmax << xshift;
361 line.ymin = fy << yshift;
362 line.ymax = (fy+1) << yshift;
363 line.intersect(line, provided_input);
364 line.translate(-provided_input.xmin, -provided_input.ymin);
365 // Prepare variables
366 const unsigned char *botline = input[line.ymin];
367 int rowsize = input.rowsize();
368 int sw = 1<<xshift;
369 int div = xshift+yshift;
370 int rnd = 1<<(div-1);
371 // Compute averages
372 for (int x=line.xmin; x<line.xmax; x+=sw,p++)
373 {
374 int g=0, s=0;
375 const unsigned char *inp0 = botline + x;
376 int sy1 = mini(line.height(), (1<<yshift));
377 for (int sy=0; sy<sy1; sy++,inp0+=rowsize)
378 {
379 const unsigned char *inp1;
380 const unsigned char *inp2 = inp0 + mini(x+sw, line.xmax) - x;
381 for (inp1=inp0; inp1<inp2; inp1++)
382 {
383 g += conv[*inp1];
384 s += 1;
385 }
386 }
387 if (s == rnd+rnd)
388 *p = (g+rnd)>>div;
389 else
390 *p = (g+s/2)/s;
391 }
392 // Return
393 return p2;
394 }
395 }
396
397
398 void
scale(const GRect & provided_input,const GBitmap & input,const GRect & desired_output,GBitmap & output)399 GBitmapScaler::scale( const GRect &provided_input, const GBitmap &input,
400 const GRect &desired_output, GBitmap &output )
401 {
402 // Compute rectangles
403 GRect required_input;
404 GRect required_red;
405 make_rectangles(desired_output, required_red, required_input);
406 // Parameter validation
407 if (provided_input.width() != (int)input.columns() ||
408 provided_input.height() != (int)input.rows() )
409 G_THROW( ERR_MSG("GScaler.no_match") );
410 if (provided_input.xmin > required_input.xmin ||
411 provided_input.ymin > required_input.ymin ||
412 provided_input.xmax < required_input.xmax ||
413 provided_input.ymax < required_input.ymax )
414 G_THROW( ERR_MSG("GScaler.too_small") );
415 // Adjust output pixmap
416 if (desired_output.width() != (int)output.columns() ||
417 desired_output.height() != (int)output.rows() )
418 output.init(desired_output.height(), desired_output.width());
419 output.set_grays(256);
420 // Prepare temp stuff
421 gp1.resize(0);
422 gp2.resize(0);
423 glbuffer.resize(0);
424 prepare_interp();
425 const int bufw = required_red.width();
426 glbuffer.resize(bufw+2);
427 gp1.resize(bufw);
428 gp2.resize(bufw);
429 l1 = l2 = -1;
430 // Prepare gray conversion array (conv)
431 gconv.resize(0);
432 gconv.resize(256);
433 int maxgray = input.get_grays()-1;
434 for (int i=0; i<256; i++)
435 {
436 conv[i]=(i<= maxgray)
437 ?(((i*255) + (maxgray>>1)) / maxgray)
438 :255;
439 }
440 // Loop on output lines
441 for (int y=desired_output.ymin; y<desired_output.ymax; y++)
442 {
443 // Perform vertical interpolation
444 {
445 int fy = vcoord[y];
446 int fy1 = fy>>FRACBITS;
447 int fy2 = fy1+1;
448 const unsigned char *lower, *upper;
449 // Obtain upper and lower line in reduced image
450 lower = get_line(fy1, required_red, provided_input, input);
451 upper = get_line(fy2, required_red, provided_input, input);
452 // Compute line
453 unsigned char *dest = lbuffer+1;
454 const short *deltas = & interp[fy&FRACMASK][256];
455 for(unsigned char const * const edest=(unsigned char const *)dest+bufw;
456 dest<edest;upper++,lower++,dest++)
457 {
458 const int l = *lower;
459 const int u = *upper;
460 *dest = l + deltas[u-l];
461 }
462 }
463 // Perform horizontal interpolation
464 {
465 // Prepare for side effects
466 lbuffer[0] = lbuffer[1];
467 lbuffer[bufw+1] = lbuffer[bufw];
468 unsigned char *line = lbuffer+1-required_red.xmin;
469 unsigned char *dest = output[y-desired_output.ymin];
470 // Loop horizontally
471 for (int x=desired_output.xmin; x<desired_output.xmax; x++)
472 {
473 int n = hcoord[x];
474 const unsigned char *lower = line + (n>>FRACBITS);
475 const short *deltas = &interp[n&FRACMASK][256];
476 int l = lower[0];
477 int u = lower[1];
478 *dest = l + deltas[u-l];
479 dest++;
480 }
481 }
482 }
483 // Free temporaries
484 gp1.resize(0);
485 gp2.resize(0);
486 glbuffer.resize(0);
487 gconv.resize(0);
488 }
489
490
491
492
493
494
495 ////////////////////////////////////////
496 // GPIXMAPSCALER
497
498
GPixmapScaler()499 GPixmapScaler::GPixmapScaler()
500 : glbuffer(lbuffer,0),
501 gp1(p1,0),
502 gp2(p2,0)
503 {
504 }
505
506
GPixmapScaler(int inw,int inh,int outw,int outh)507 GPixmapScaler::GPixmapScaler(int inw, int inh, int outw, int outh)
508 : glbuffer(lbuffer,0),
509 gp1(p1,0),
510 gp2(p2,0)
511 {
512 set_input_size(inw, inh);
513 set_output_size(outw, outh);
514 }
515
516
~GPixmapScaler()517 GPixmapScaler::~GPixmapScaler()
518 {
519 }
520
521
522 GPixel *
get_line(int fy,const GRect & required_red,const GRect & provided_input,const GPixmap & input)523 GPixmapScaler::get_line(int fy,
524 const GRect &required_red,
525 const GRect &provided_input,
526 const GPixmap &input )
527 {
528 if (fy < required_red.ymin)
529 fy = required_red.ymin;
530 else if (fy >= required_red.ymax)
531 fy = required_red.ymax - 1;
532 // Cached line
533 if (fy == l2)
534 return p2;
535 if (fy == l1)
536 return p1;
537 // Shift
538 GPixel *p=p1;
539 p1 = p2;
540 l1 = l2;
541 p2 = p;
542 l2 = fy;
543 // Compute location of line
544 GRect line;
545 line.xmin = required_red.xmin << xshift;
546 line.xmax = required_red.xmax << xshift;
547 line.ymin = fy << yshift;
548 line.ymax = (fy+1) << yshift;
549 line.intersect(line, provided_input);
550 line.translate(-provided_input.xmin, -provided_input.ymin);
551 // Prepare variables
552 const GPixel *botline = input[line.ymin];
553 int rowsize = input.rowsize();
554 int sw = 1<<xshift;
555 int div = xshift+yshift;
556 int rnd = 1<<(div-1);
557 // Compute averages
558 for (int x=line.xmin; x<line.xmax; x+=sw,p++)
559 {
560 int r=0, g=0, b=0, s=0;
561 const GPixel *inp0 = botline + x;
562 int sy1 = mini(line.height(), (1<<yshift));
563 for (int sy=0; sy<sy1; sy++,inp0+=rowsize)
564 {
565 const GPixel *inp1;
566 const GPixel *inp2 = inp0 + mini(x+sw, line.xmax) - x;
567 for (inp1 = inp0; inp1<inp2; inp1++)
568 {
569 r += inp1->r;
570 g += inp1->g;
571 b += inp1->b;
572 s += 1;
573 }
574 }
575 if (s == rnd+rnd)
576 {
577 p->r = (r+rnd) >> div;
578 p->g = (g+rnd) >> div;
579 p->b = (b+rnd) >> div;
580 }
581 else
582 {
583 p->r = (r+s/2)/s;
584 p->g = (g+s/2)/s;
585 p->b = (b+s/2)/s;
586 }
587 }
588 // Return
589 return (GPixel *)p2;
590 }
591
592
593 void
scale(const GRect & provided_input,const GPixmap & input,const GRect & desired_output,GPixmap & output)594 GPixmapScaler::scale( const GRect &provided_input, const GPixmap &input,
595 const GRect &desired_output, GPixmap &output )
596 {
597 // Compute rectangles
598 GRect required_input;
599 GRect required_red;
600 make_rectangles(desired_output, required_red, required_input);
601 // Parameter validation
602 if (provided_input.width() != (int)input.columns() ||
603 provided_input.height() != (int)input.rows() )
604 G_THROW( ERR_MSG("GScaler.no_match") );
605 if (provided_input.xmin > required_input.xmin ||
606 provided_input.ymin > required_input.ymin ||
607 provided_input.xmax < required_input.xmax ||
608 provided_input.ymax < required_input.ymax )
609 G_THROW( ERR_MSG("GScaler.too_small") );
610 // Adjust output pixmap
611 if (desired_output.width() != (int)output.columns() ||
612 desired_output.height() != (int)output.rows() )
613 output.init(desired_output.height(), desired_output.width());
614 // Prepare temp stuff
615 gp1.resize(0);
616 gp2.resize(0);
617 glbuffer.resize(0);
618 prepare_interp();
619 const int bufw = required_red.width();
620 glbuffer.resize(bufw+2);
621 if (xshift>0 || yshift>0)
622 {
623 gp1.resize(bufw);
624 gp2.resize(bufw);
625 l1 = l2 = -1;
626 }
627 // Loop on output lines
628 for (int y=desired_output.ymin; y<desired_output.ymax; y++)
629 {
630 // Perform vertical interpolation
631 {
632 int fy = vcoord[y];
633 int fy1 = fy>>FRACBITS;
634 int fy2 = fy1+1;
635 const GPixel *lower, *upper;
636 // Obtain upper and lower line in reduced image
637 if (xshift>0 || yshift>0)
638 {
639 lower = get_line(fy1, required_red, provided_input, input);
640 upper = get_line(fy2, required_red, provided_input, input);
641 }
642 else
643 {
644 int dx = required_red.xmin-provided_input.xmin;
645 fy1 = maxi(fy1, required_red.ymin);
646 fy2 = mini(fy2, required_red.ymax-1);
647 lower = input[fy1-provided_input.ymin] + dx;
648 upper = input[fy2-provided_input.ymin] + dx;
649 }
650 // Compute line
651 GPixel *dest = lbuffer+1;
652 const short *deltas = & interp[fy&FRACMASK][256];
653 for(GPixel const * const edest = (GPixel const *)dest+bufw;
654 dest<edest;upper++,lower++,dest++)
655 {
656 const int lower_r = lower->r;
657 const int delta_r = deltas[(int)upper->r - lower_r];
658 dest->r = lower_r + delta_r;
659 const int lower_g = lower->g;
660 const int delta_g = deltas[(int)upper->g - lower_g];
661 dest->g = lower_g + delta_g;
662 const int lower_b = lower->b;
663 const int delta_b = deltas[(int)upper->b - lower_b];
664 dest->b = lower_b + delta_b;
665 }
666 }
667 // Perform horizontal interpolation
668 {
669 // Prepare for side effects
670 lbuffer[0] = lbuffer[1];
671 lbuffer[bufw+1] = lbuffer[bufw];
672 GPixel *line = lbuffer+1-required_red.xmin;
673 GPixel *dest = output[y-desired_output.ymin];
674 // Loop horizontally
675 for (int x=desired_output.xmin; x<desired_output.xmax; x++,dest++)
676 {
677 const int n = hcoord[x];
678 const GPixel *lower = line + (n>>FRACBITS);
679 const short *deltas = &interp[n&FRACMASK][256];
680 const int lower_r = lower[0].r;
681 const int delta_r = deltas[(int)lower[1].r - lower_r];
682 dest->r = lower_r + delta_r;
683 const int lower_g = lower[0].g;
684 const int delta_g = deltas[(int)lower[1].g - lower_g];
685 dest->g = lower_g + delta_g;
686 const int lower_b = lower[0].b;
687 const int delta_b = deltas[(int)lower[1].b - lower_b];
688 dest->b = lower_b + delta_b;
689 }
690 }
691 }
692 // Free temporaries
693 gp1.resize(0);
694 gp2.resize(0);
695 glbuffer.resize(0);
696 }
697
698
699
700 #ifdef HAVE_NAMESPACES
701 }
702 # ifndef NOT_USING_DJVU_NAMESPACE
703 using namespace DJVU;
704 # endif
705 #endif
706
707