1#======================================================================= 2# ____ ____ _____ _ ____ ___ ____ 3# | _ \| _ \| ___| _ _ / \ | _ \_ _| |___ \ 4# | |_) | | | | |_ (_) (_) / _ \ | |_) | | __) | 5# | __/| |_| | _| _ _ / ___ \| __/| | / __/ 6# |_| |____/|_| (_) (_) /_/ \_\_| |___| |_____| 7# 8# A Perl Module Chain to faciliate the Creation and Modification 9# of High-Quality "Portable Document Format (PDF)" Files. 10# 11# Copyright 1999-2005 Alfred Reibenschuh <areibens@cpan.org>. 12# 13#======================================================================= 14# 15# This library is free software; you can redistribute it and/or 16# modify it under the terms of the GNU Lesser General Public 17# License as published by the Free Software Foundation; either 18# version 2 of the License, or (at your option) any later version. 19# 20# This library is distributed in the hope that it will be useful, 21# but WITHOUT ANY WARRANTY; without even the implied warranty of 22# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 23# Lesser General Public License for more details. 24# 25# You should have received a copy of the GNU Lesser General Public 26# License along with this library; if not, write to the 27# Free Software Foundation, Inc., 59 Temple Place - Suite 330, 28# Boston, MA 02111-1307, USA. 29# 30# $Id: PNG.pm,v 2.0 2005/11/16 02:18:23 areibens Exp $ 31# 32#======================================================================= 33package PDF::API3::Compat::API2::Resource::XObject::Image::PNG; 34 35BEGIN { 36 37 use PDF::API3::Compat::API2::Util; 38 use PDF::API3::Compat::API2::Basic::PDF::Utils; 39 use PDF::API3::Compat::API2::Resource::XObject::Image; 40 41 use POSIX; 42 use Compress::Zlib; 43 44 use vars qw(@ISA $VERSION); 45 @ISA = qw( PDF::API3::Compat::API2::Resource::XObject::Image ); 46 ( $VERSION ) = sprintf '%i.%03i', split(/\./,('$Revision: 2.0 $' =~ /Revision: (\S+)\s/)[0]); # $Date: 2005/11/16 02:18:23 $ 47} 48no warnings qw[ deprecated recursion uninitialized ]; 49 50=item $res = PDF::API3::Compat::API2::Resource::XObject::Image::PNG->new $pdf, $file [, $name] 51 52Returns a png-image object. 53 54=cut 55 56sub new { 57 my ($class,$pdf,$file,$name,%opts) = @_; 58 my $self; 59 60 $class = ref $class if ref $class; 61 62 $self=$class->SUPER::new($pdf,$name || 'Px'.pdfkey()); 63 $pdf->new_obj($self) unless($self->is_obj($pdf)); 64 65 $self->{' apipdf'}=$pdf; 66 67 my $fh = IO::File->new; 68 open($fh,$file); 69 binmode($fh,':raw'); 70 71 my ($buf,$l,$crc,$w,$h,$bpc,$cs,$cm,$fm,$im,$palete,$trns); 72 open($fh,$file); 73 binmode($fh); 74 seek($fh,8,0); 75 $self->{' stream'}=''; 76 $self->{' nofilt'}=1; 77 while(!eof($fh)) { 78 read($fh,$buf,4); 79 $l=unpack('N',$buf); 80 read($fh,$buf,4); 81 if($buf eq 'IHDR') { 82 read($fh,$buf,$l); 83 ($w,$h,$bpc,$cs,$cm,$fm,$im)=unpack('NNCCCCC',$buf); 84 die "Unsupported Compression($cm) Method" if($cm); 85 die "Unsupported Interlace($im) Method" if($im); 86 die "Unsupported Filter($fm) Method" if($fm); 87 } elsif($buf eq 'PLTE') { 88 read($fh,$buf,$l); 89 $palete=$buf; 90 } elsif($buf eq 'IDAT') { 91 read($fh,$buf,$l); 92 $self->{' stream'}.=$buf; 93 } elsif($buf eq 'tRNS') { 94 read($fh,$buf,$l); 95 $trns=$buf; 96 } elsif($buf eq 'IEND') { 97 last; 98 } else { 99 # skip ahead 100 seek($fh,$l,1); 101 } 102 read($fh,$buf,4); 103 $crc=$buf; 104 } 105 close($fh); 106 107 $self->width($w); 108 $self->height($h); 109 110 if($cs==0){ # greyscale 111 # scanline = ceil(bpc * comp / 8)+1 112 if($bpc>8) { 113 die "16-bits of greylevel in png not supported."; 114 } else { 115 $self->filters('FlateDecode'); 116 $self->colorspace('DeviceGray'); 117 $self->bpc($bpc); 118 my $dict=PDFDict(); 119 $self->{DecodeParms}=PDFArray($dict); 120 $dict->{Predictor}=PDFNum(15); 121 $dict->{BitsPerComponent}=PDFNum($bpc); 122 $dict->{Colors}=PDFNum(1); 123 $dict->{Columns}=PDFNum($w); 124 if(defined $trns && !$opts{-notrans}) { 125 my $m=mMax(unpack('n*',$trns)); 126 my $n=mMin(unpack('n*',$trns)); 127 $self->{Mask}=PDFArray(PDFNum($n),PDFNum($m)); 128 } 129 } 130 } elsif($cs==2){ # rgb 8/16 bits 131 if($bpc>8) { 132 die "16-bits of rgb in png not supported."; 133 } else { 134 $self->filters('FlateDecode'); 135 $self->colorspace('DeviceRGB'); 136 $self->bpc($bpc); 137 my $dict=PDFDict(); 138 $self->{DecodeParms}=PDFArray($dict); 139 $dict->{Predictor}=PDFNum(15); 140 $dict->{BitsPerComponent}=PDFNum($bpc); 141 $dict->{Colors}=PDFNum(3); 142 $dict->{Columns}=PDFNum($w); 143 if(defined $trns && !$opts{-notrans}) { 144 my @v=unpack('n*',$trns); 145 my (@cr,@cg,@cb,$m,$n); 146 while(scalar @v > 0) { 147 push(@cr,shift(@v)); 148 push(@cg,shift(@v)); 149 push(@cb,shift(@v)); 150 } 151 @v=(); 152 $m=mMax(@cr); 153 $n=mMin(@cr); 154 push @v,$n,$m; 155 $m=mMax(@cg); 156 $n=mMin(@cg); 157 push @v,$n,$m; 158 $m=mMax(@cb); 159 $n=mMin(@cb); 160 push @v,$n,$m; 161 $self->{Mask}=PDFArray(map { PDFNum($_) } @v); 162 } 163 } 164 } elsif($cs==3){ # palette 165 if($bpc>8) { 166 die "bits>8 of palette in png not supported."; 167 } else { 168 my $dict=PDFDict(); 169 $pdf->new_obj($dict); 170 $dict->{Filter}=PDFArray(PDFName('FlateDecode')); 171 $dict->{' stream'}=$palete; 172 $palete=""; 173 $self->filters('FlateDecode'); 174 $self->colorspace(PDFArray(PDFName('Indexed'),PDFName('DeviceRGB'),PDFNum(int(length($dict->{' stream'})/3)-1),$dict)); 175 $self->bpc($bpc); 176 $dict=PDFDict(); 177 $self->{DecodeParms}=PDFArray($dict); 178 $dict->{Predictor}=PDFNum(15); 179 $dict->{BitsPerComponent}=PDFNum($bpc); 180 $dict->{Colors}=PDFNum(1); 181 $dict->{Columns}=PDFNum($w); 182 if(defined $trns && !$opts{-notrans}) { 183 $trns.="\xFF" x 256; 184 $dict=PDFDict(); 185 $pdf->new_obj($dict); 186 $dict->{Type}=PDFName('XObject'); 187 $dict->{Subtype}=PDFName('Image'); 188 $dict->{Width}=PDFNum($w); 189 $dict->{Height}=PDFNum($h); 190 $dict->{ColorSpace}=PDFName('DeviceGray'); 191 $dict->{Filter}=PDFArray(PDFName('FlateDecode')); 192 # $dict->{Filter}=PDFArray(PDFName('ASCIIHexDecode')); 193 $dict->{BitsPerComponent}=PDFNum(8); 194 $self->{SMask}=$dict; 195 my $scanline=1+ceil($bpc*$w/8); 196 my $bpp=ceil($bpc/8); 197 my $clearstream=unprocess($bpc,$bpp,1,$w,$h,$scanline,\$self->{' stream'}); 198 foreach my $n (0..($h*$w)-1) { 199 vec($dict->{' stream'},$n,8)=vec($trns,vec($clearstream,$n,$bpc),8); 200 # print STDERR vec($trns,vec($clearstream,$n,$bpc),8)."=".vec($clearstream,$n,$bpc).","; 201 } 202 # print STDERR "\n"; 203 } 204 } 205 } elsif($cs==4){ # greyscale+alpha 206 # die "greylevel+alpha in png not supported."; 207 if($bpc>8) { 208 die "16-bits of greylevel+alpha in png not supported."; 209 } else { 210 $self->filters('FlateDecode'); 211 $self->colorspace('DeviceGray'); 212 $self->bpc($bpc); 213 my $dict=PDFDict(); 214 $self->{DecodeParms}=PDFArray($dict); 215 # $dict->{Predictor}=PDFNum(15); 216 $dict->{BitsPerComponent}=PDFNum($bpc); 217 $dict->{Colors}=PDFNum(1); 218 $dict->{Columns}=PDFNum($w); 219 220 $dict=PDFDict(); 221 unless($opts{-notrans}) { 222 $pdf->new_obj($dict); 223 $dict->{Type}=PDFName('XObject'); 224 $dict->{Subtype}=PDFName('Image'); 225 $dict->{Width}=PDFNum($w); 226 $dict->{Height}=PDFNum($h); 227 $dict->{ColorSpace}=PDFName('DeviceGray'); 228 $dict->{Filter}=PDFArray(PDFName('FlateDecode')); 229 $dict->{BitsPerComponent}=PDFNum($bpc); 230 $self->{SMask}=$dict; 231 } 232 my $scanline=1+ceil($bpc*2*$w/8); 233 my $bpp=ceil($bpc*2/8); 234 my $clearstream=unprocess($bpc,$bpp,2,$w,$h,$scanline,\$self->{' stream'}); 235 delete $self->{' nofilt'}; 236 delete $self->{' stream'}; 237 foreach my $n (0..($h*$w)-1) { 238 vec($dict->{' stream'},$n,$bpc)=vec($clearstream,($n*2)+1,$bpc); 239 vec($self->{' stream'},$n,$bpc)=vec($clearstream,$n*2,$bpc); 240 } 241 } 242 } elsif($cs==6){ # rgb+alpha 243 # die "rgb+alpha in png not supported."; 244 if($bpc>8) { 245 die "16-bits of rgb+alpha in png not supported."; 246 } else { 247 $self->filters('FlateDecode'); 248 $self->colorspace('DeviceRGB'); 249 $self->bpc($bpc); 250 my $dict=PDFDict(); 251 $self->{DecodeParms}=PDFArray($dict); 252 # $dict->{Predictor}=PDFNum(15); 253 $dict->{BitsPerComponent}=PDFNum($bpc); 254 $dict->{Colors}=PDFNum(3); 255 $dict->{Columns}=PDFNum($w); 256 257 $dict=PDFDict(); 258 unless($opts{-notrans}) { 259 $pdf->new_obj($dict); 260 $dict->{Type}=PDFName('XObject'); 261 $dict->{Subtype}=PDFName('Image'); 262 $dict->{Width}=PDFNum($w); 263 $dict->{Height}=PDFNum($h); 264 $dict->{ColorSpace}=PDFName('DeviceGray'); 265 $dict->{Filter}=PDFArray(PDFName('FlateDecode')); 266 $dict->{BitsPerComponent}=PDFNum($bpc); 267 $self->{SMask}=$dict; 268 } 269 my $scanline=1+ceil($bpc*4*$w/8); 270 my $bpp=ceil($bpc*4/8); 271 my $clearstream=unprocess($bpc,$bpp,4,$w,$h,$scanline,\$self->{' stream'}); 272 delete $self->{' nofilt'}; 273 delete $self->{' stream'}; 274 foreach my $n (0..($h*$w)-1) { 275 vec($dict->{' stream'},$n,$bpc)=vec($clearstream,($n*4)+3,$bpc); 276 vec($self->{' stream'},($n*3),$bpc)=vec($clearstream,($n*4),$bpc); 277 vec($self->{' stream'},($n*3)+1,$bpc)=vec($clearstream,($n*4)+1,$bpc); 278 vec($self->{' stream'},($n*3)+2,$bpc)=vec($clearstream,($n*4)+2,$bpc); 279 } 280 } 281 } else { 282 die "unsupported png-type ($cs)."; 283 } 284 285 return($self); 286} 287 288=item $res = PDF::API3::Compat::API2::Resource::XObject::Image::PNG->new_api $api, $file [, $name] 289 290Returns a png-image object. This method is different from 'new' that 291it needs an PDF::API3::Compat::API2-object rather than a Text::PDF::File-object. 292 293=cut 294 295sub new_api { 296 my ($class,$api,@opts)=@_; 297 298 my $obj=$class->new($api->{pdf},@opts); 299 $obj->{' api'}=$api; 300 301 return($obj); 302} 303 304sub PaethPredictor { 305 my ($a, $b, $c)=@_; 306 my $p = $a + $b - $c; 307 my $pa = abs($p - $a); 308 my $pb = abs($p - $b); 309 my $pc = abs($p - $c); 310 if(($pa <= $pb) && ($pa <= $pc)) { 311 return $a; 312 } elsif($pb <= $pc) { 313 return $b; 314 } else { 315 return $c; 316 } 317} 318 319sub unprocess { 320 my ($bpc,$bpp,$comp,$width,$height,$scanline,$sstream)=@_; 321 my $stream=uncompress($$sstream); 322 my $prev=''; 323 my $clearstream=''; 324 foreach my $n (0..$height-1) { 325 # print STDERR "line $n:"; 326 my $line=substr($stream,$n*$scanline,$scanline); 327 my $filter=vec($line,0,8); 328 my $clear=''; 329 $line=substr($line,1); 330 # print STDERR " filter=$filter"; 331 if($filter==0) { 332 $clear=$line; 333 } elsif($filter==1) { 334 foreach my $x (0..length($line)-1) { 335 vec($clear,$x,8)=(vec($line,$x,8)+vec($clear,$x-$bpp,8))%256; 336 } 337 } elsif($filter==2) { 338 foreach my $x (0..length($line)-1) { 339 vec($clear,$x,8)=(vec($line,$x,8)+vec($prev,$x,8))%256; 340 } 341 } elsif($filter==3) { 342 foreach my $x (0..length($line)-1) { 343 vec($clear,$x,8)=(vec($line,$x,8)+floor((vec($clear,$x-$bpp,8)+vec($prev,$x,8))/2))%256; 344 } 345 } elsif($filter==4) { 346 # die "paeth/png filter not supported."; 347 foreach my $x (0..length($line)-1) { 348 vec($clear,$x,8)=(vec($line,$x,8)+PaethPredictor(vec($clear,$x-$bpp,8),vec($prev,$x,8),vec($prev,$x-$bpp,8)))%256; 349 } 350 } 351 $prev=$clear; 352 foreach my $x (0..($width*$comp)-1) { 353 vec($clearstream,($n*$width*$comp)+$x,$bpc)=vec($clear,$x,$bpc); 354 # print STDERR "".vec($clear,$x,$bpc).","; 355 } 356 # print STDERR "\n"; 357 } 358 return($clearstream); 359} 360 3611; 362 363__END__ 364 365=head1 AUTHOR 366 367alfred reibenschuh 368 369=head1 HISTORY 370 371 $Log: PNG.pm,v $ 372 Revision 2.0 2005/11/16 02:18:23 areibens 373 revision workaround for SF cvs import not to screw up CPAN 374 375 Revision 1.2 2005/11/16 01:27:50 areibens 376 genesis2 377 378 Revision 1.1 2005/11/16 01:19:27 areibens 379 genesis 380 381 Revision 1.10 2005/06/17 19:44:04 fredo 382 fixed CPAN modulefile versioning (again) 383 384 Revision 1.9 2005/06/17 18:53:35 fredo 385 fixed CPAN modulefile versioning (dislikes cvs) 386 387 Revision 1.8 2005/03/14 22:01:31 fredo 388 upd 2005 389 390 Revision 1.7 2004/12/16 00:30:55 fredo 391 added no warn for recursion 392 393 Revision 1.6 2004/06/15 09:14:54 fredo 394 removed cr+lf 395 396 Revision 1.5 2004/06/07 19:44:44 fredo 397 cleaned out cr+lf for lf 398 399 Revision 1.4 2004/02/12 14:48:01 fredo 400 removed duplicate definition of $fh 401 402 Revision 1.3 2003/12/08 13:06:11 Administrator 403 corrected to proper licencing statement 404 405 Revision 1.2 2003/11/30 17:37:16 Administrator 406 merged into default 407 408 Revision 1.1.1.1.2.2 2003/11/30 16:57:10 Administrator 409 merged into default 410 411 Revision 1.1.1.1.2.1 2003/11/30 16:00:42 Administrator 412 added CVS id/log 413 414 415=cut 416 417RFC 2083 418PNG: Portable Network Graphics 419January 1997 420 421 4224.1.3. IDAT Image data 423 424 The IDAT chunk contains the actual image data. To create this 425 data: 426 427 * Begin with image scanlines represented as described in 428 Image layout (Section 2.3); the layout and total size of 429 this raw data are determined by the fields of IHDR. 430 * Filter the image data according to the filtering method 431 specified by the IHDR chunk. (Note that with filter 432 method 0, the only one currently defined, this implies 433 prepending a filter type byte to each scanline.) 434 * Compress the filtered data using the compression method 435 specified by the IHDR chunk. 436 437 The IDAT chunk contains the output datastream of the compression 438 algorithm. 439 440 To read the image data, reverse this process. 441 442 There can be multiple IDAT chunks; if so, they must appear 443 consecutively with no other intervening chunks. The compressed 444 datastream is then the concatenation of the contents of all the 445 IDAT chunks. The encoder can divide the compressed datastream 446 into IDAT chunks however it wishes. (Multiple IDAT chunks are 447 allowed so that encoders can work in a fixed amount of memory; 448 typically the chunk size will correspond to the encoder's buffer 449 size.) It is important to emphasize that IDAT chunk boundaries 450 have no semantic significance and can occur at any point in the 451 compressed datastream. A PNG file in which each IDAT chunk 452 contains only one data byte is legal, though remarkably wasteful 453 of space. (For that matter, zero-length IDAT chunks are legal, 454 though even more wasteful.) 455 456 4574.2.9. tRNS Transparency 458 459 The tRNS chunk specifies that the image uses simple 460 transparency: either alpha values associated with palette 461 entries (for indexed-color images) or a single transparent 462 color (for grayscale and truecolor images). Although simple 463 transparency is not as elegant as the full alpha channel, it 464 requires less storage space and is sufficient for many common 465 cases. 466 467 For color type 3 (indexed color), the tRNS chunk contains a 468 series of one-byte alpha values, corresponding to entries in 469 the PLTE chunk: 470 471 Alpha for palette index 0: 1 byte 472 Alpha for palette index 1: 1 byte 473 ... etc ... 474 475 Each entry indicates that pixels of the corresponding palette 476 index must be treated as having the specified alpha value. 477 Alpha values have the same interpretation as in an 8-bit full 478 alpha channel: 0 is fully transparent, 255 is fully opaque, 479 regardless of image bit depth. The tRNS chunk must not contain 480 more alpha values than there are palette entries, but tRNS can 481 contain fewer values than there are palette entries. In this 482 case, the alpha value for all remaining palette entries is 483 assumed to be 255. In the common case in which only palette 484 index 0 need be made transparent, only a one-byte tRNS chunk is 485 needed. 486 487 For color type 0 (grayscale), the tRNS chunk contains a single 488 gray level value, stored in the format: 489 490 Gray: 2 bytes, range 0 .. (2^bitdepth)-1 491 492 (For consistency, 2 bytes are used regardless of the image bit 493 depth.) Pixels of the specified gray level are to be treated as 494 transparent (equivalent to alpha value 0); all other pixels are 495 to be treated as fully opaque (alpha value (2^bitdepth)-1). 496 497 For color type 2 (truecolor), the tRNS chunk contains a single 498 RGB color value, stored in the format: 499 500 Red: 2 bytes, range 0 .. (2^bitdepth)-1 501 Green: 2 bytes, range 0 .. (2^bitdepth)-1 502 Blue: 2 bytes, range 0 .. (2^bitdepth)-1 503 504 (For consistency, 2 bytes per sample are used regardless of the 505 image bit depth.) Pixels of the specified color value are to be 506 treated as transparent (equivalent to alpha value 0); all other 507 pixels are to be treated as fully opaque (alpha value 508 2^bitdepth)-1). 509 510 tRNS is prohibited for color types 4 and 6, since a full alpha 511 channel is already present in those cases. 512 513 Note: when dealing with 16-bit grayscale or truecolor data, it 514 is important to compare both bytes of the sample values to 515 determine whether a pixel is transparent. Although decoders 516 may drop the low-order byte of the samples for display, this 517 must not occur until after the data has been tested for 518 transparency. For example, if the grayscale level 0x0001 is 519 specified to be transparent, it would be incorrect to compare 520 only the high-order byte and decide that 0x0002 is also 521 transparent. 522 523 When present, the tRNS chunk must precede the first IDAT chunk, 524 and must follow the PLTE chunk, if any. 525 526 5276. Filter Algorithms 528 529 This chapter describes the filter algorithms that can be applied 530 before compression. The purpose of these filters is to prepare the 531 image data for optimum compression. 532 533 5346.1. Filter types 535 536 PNG filter method 0 defines five basic filter types: 537 538 Type Name 539 540 0 None 541 1 Sub 542 2 Up 543 3 Average 544 4 Paeth 545 546 (Note that filter method 0 in IHDR specifies exactly this set of 547 five filter types. If the set of filter types is ever extended, a 548 different filter method number will be assigned to the extended 549 set, so that decoders need not decompress the data to discover 550 that it contains unsupported filter types.) 551 552 The encoder can choose which of these filter algorithms to apply 553 on a scanline-by-scanline basis. In the image data sent to the 554 compression step, each scanline is preceded by a filter type byte 555 that specifies the filter algorithm used for that scanline. 556 557 Filtering algorithms are applied to bytes, not to pixels, 558 regardless of the bit depth or color type of the image. The 559 filtering algorithms work on the byte sequence formed by a 560 scanline that has been represented as described in Image layout 561 (Section 2.3). If the image includes an alpha channel, the alpha 562 data is filtered in the same way as the image data. 563 564 When the image is interlaced, each pass of the interlace pattern 565 is treated as an independent image for filtering purposes. The 566 filters work on the byte sequences formed by the pixels actually 567 transmitted during a pass, and the "previous scanline" is the one 568 previously transmitted in the same pass, not the one adjacent in 569 the complete image. Note that the subimage transmitted in any one 570 pass is always rectangular, but is of smaller width and/or height 571 than the complete image. Filtering is not applied when this 572 subimage is empty. 573 574 For all filters, the bytes "to the left of" the first pixel in a 575 scanline must be treated as being zero. For filters that refer to 576 the prior scanline, the entire prior scanline must be treated as 577 being zeroes for the first scanline of an image (or of a pass of 578 an interlaced image). 579 580 To reverse the effect of a filter, the decoder must use the 581 decoded values of the prior pixel on the same line, the pixel 582 immediately above the current pixel on the prior line, and the 583 pixel just to the left of the pixel above. This implies that at 584 least one scanline's worth of image data will have to be stored by 585 the decoder at all times. Even though some filter types do not 586 refer to the prior scanline, the decoder will always need to store 587 each scanline as it is decoded, since the next scanline might use 588 a filter that refers to it. 589 590 PNG imposes no restriction on which filter types can be applied to 591 an image. However, the filters are not equally effective on all 592 types of data. See Recommendations for Encoders: Filter selection 593 (Section 9.6). 594 595 See also Rationale: Filtering (Section 12.9). 596 597 598 5996.2. Filter type 0: None 600 601 With the None filter, the scanline is transmitted unmodified; it 602 is only necessary to insert a filter type byte before the data. 603 604 6056.3. Filter type 1: Sub 606 607 The Sub filter transmits the difference between each byte and the 608 value of the corresponding byte of the prior pixel. 609 610 To compute the Sub filter, apply the following formula to each 611 byte of the scanline: 612 613 Sub(x) = Raw(x) - Raw(x-bpp) 614 615 where x ranges from zero to the number of bytes representing the 616 scanline minus one, Raw(x) refers to the raw data byte at that 617 byte position in the scanline, and bpp is defined as the number of 618 bytes per complete pixel, rounding up to one. For example, for 619 color type 2 with a bit depth of 16, bpp is equal to 6 (three 620 samples, two bytes per sample); for color type 0 with a bit depth 621 of 2, bpp is equal to 1 (rounding up); for color type 4 with a bit 622 depth of 16, bpp is equal to 4 (two-byte grayscale sample, plus 623 two-byte alpha sample). 624 625 Note this computation is done for each byte, regardless of bit 626 depth. In a 16-bit image, each MSB is predicted from the 627 preceding MSB and each LSB from the preceding LSB, because of the 628 way that bpp is defined. 629 630 Unsigned arithmetic modulo 256 is used, so that both the inputs 631 and outputs fit into bytes. The sequence of Sub values is 632 transmitted as the filtered scanline. 633 634 For all x < 0, assume Raw(x) = 0. 635 636 To reverse the effect of the Sub filter after decompression, 637 output the following value: 638 639 Sub(x) + Raw(x-bpp) 640 641 (computed mod 256), where Raw refers to the bytes already decoded. 642 643 6446.4. Filter type 2: Up 645 646 The Up filter is just like the Sub filter except that the pixel 647 immediately above the current pixel, rather than just to its left, 648 is used as the predictor. 649 650 To compute the Up filter, apply the following formula to each byte 651 of the scanline: 652 653 Up(x) = Raw(x) - Prior(x) 654 655 where x ranges from zero to the number of bytes representing the 656 scanline minus one, Raw(x) refers to the raw data byte at that 657 byte position in the scanline, and Prior(x) refers to the 658 unfiltered bytes of the prior scanline. 659 660 Note this is done for each byte, regardless of bit depth. 661 Unsigned arithmetic modulo 256 is used, so that both the inputs 662 and outputs fit into bytes. The sequence of Up values is 663 transmitted as the filtered scanline. 664 665 On the first scanline of an image (or of a pass of an interlaced 666 image), assume Prior(x) = 0 for all x. 667 668 To reverse the effect of the Up filter after decompression, output 669 the following value: 670 671 Up(x) + Prior(x) 672 673 (computed mod 256), where Prior refers to the decoded bytes of the 674 prior scanline. 675 676 6776.5. Filter type 3: Average 678 679 The Average filter uses the average of the two neighboring pixels 680 (left and above) to predict the value of a pixel. 681 682 To compute the Average filter, apply the following formula to each 683 byte of the scanline: 684 685 Average(x) = Raw(x) - floor((Raw(x-bpp)+Prior(x))/2) 686 687 where x ranges from zero to the number of bytes representing the 688 scanline minus one, Raw(x) refers to the raw data byte at that 689 byte position in the scanline, Prior(x) refers to the unfiltered 690 bytes of the prior scanline, and bpp is defined as for the Sub 691 filter. 692 693 Note this is done for each byte, regardless of bit depth. The 694 sequence of Average values is transmitted as the filtered 695 scanline. 696 697 The subtraction of the predicted value from the raw byte must be 698 done modulo 256, so that both the inputs and outputs fit into 699 bytes. However, the sum Raw(x-bpp)+Prior(x) must be formed 700 without overflow (using at least nine-bit arithmetic). floor() 701 indicates that the result of the division is rounded to the next 702 lower integer if fractional; in other words, it is an integer 703 division or right shift operation. 704 705 For all x < 0, assume Raw(x) = 0. On the first scanline of an 706 image (or of a pass of an interlaced image), assume Prior(x) = 0 707 for all x. 708 709 To reverse the effect of the Average filter after decompression, 710 output the following value: 711 712 Average(x) + floor((Raw(x-bpp)+Prior(x))/2) 713 714 where the result is computed mod 256, but the prediction is 715 calculated in the same way as for encoding. Raw refers to the 716 bytes already decoded, and Prior refers to the decoded bytes of 717 the prior scanline. 718 719 7206.6. Filter type 4: Paeth 721 722 The Paeth filter computes a simple linear function of the three 723 neighboring pixels (left, above, upper left), then chooses as 724 predictor the neighboring pixel closest to the computed value. 725 This technique is due to Alan W. Paeth [PAETH]. 726 727 To compute the Paeth filter, apply the following formula to each 728 byte of the scanline: 729 730 Paeth(x) = Raw(x) - PaethPredictor(Raw(x-bpp), Prior(x), Prior(x-bpp)) 731 732 where x ranges from zero to the number of bytes representing the 733 scanline minus one, Raw(x) refers to the raw data byte at that 734 byte position in the scanline, Prior(x) refers to the unfiltered 735 bytes of the prior scanline, and bpp is defined as for the Sub 736 filter. 737 738 Note this is done for each byte, regardless of bit depth. 739 Unsigned arithmetic modulo 256 is used, so that both the inputs 740 and outputs fit into bytes. The sequence of Paeth values is 741 transmitted as the filtered scanline. 742 743 The PaethPredictor function is defined by the following 744 pseudocode: 745 746 function PaethPredictor (a, b, c) 747 begin 748 ; a = left, b = above, c = upper left 749 p := a + b - c ; initial estimate 750 pa := abs(p - a) ; distances to a, b, c 751 pb := abs(p - b) 752 pc := abs(p - c) 753 ; return nearest of a,b,c, 754 ; breaking ties in order a,b,c. 755 if pa <= pb AND pa <= pc then return a 756 else if pb <= pc then return b 757 else return c 758 end 759 760 The calculations within the PaethPredictor function must be 761 performed exactly, without overflow. Arithmetic modulo 256 is to 762 be used only for the final step of subtracting the function result 763 from the target byte value. 764 765 Note that the order in which ties are broken is critical and must 766 not be altered. The tie break order is: pixel to the left, pixel 767 above, pixel to the upper left. (This order differs from that 768 given in Paeth's article.) 769 770 For all x < 0, assume Raw(x) = 0 and Prior(x) = 0. On the first 771 scanline of an image (or of a pass of an interlaced image), assume 772 Prior(x) = 0 for all x. 773 774 To reverse the effect of the Paeth filter after decompression, 775 output the following value: 776 777 Paeth(x) + PaethPredictor(Raw(x-bpp), Prior(x), Prior(x-bpp)) 778 779 (computed mod 256), where Raw and Prior refer to bytes already 780 decoded. Exactly the same PaethPredictor function is used by both 781 encoder and decoder. 782