#! /usr/bin/perl -w

# This program is free software. It comes without any warranty, to the
# extent permitted by applicable law. You can redistribute it and/or
# modify it under the terms of the Do What The Fuck You Want To Public
# License, Version 2, as published by Sam Hocevar.
# See http://sam.zoy.org/wtfpl/COPYING for more details.


$VERSION = "0.5.2, 21 January 2012";

use Getopt::Long qw /:config posix_default no_ignore_case gnu_compat
                             bundling auto_version auto_help/;
use Pod::Usage;
use IPC::Open3;
use File::Spec::Functions qw /tmpdir catfile/;
use POSIX qw /floor/;
use Error qw /:try/;
use strict;


=head1 NAME

pdftool.pl - a swiss army knife for PDF documents

=head1 SYNOPSIS

B<pdftool.pl> [B<-w> I<width> ] [B<-h> I<height>] [B<-p> I<paper>]
[B<-W> I<width>] [B<-H> I<height>] [B<-P> I<paper>] [B<-s> I<pages>]
[B<-m> I<margin>] [B<-b> I<border>] [B<-c>] [B<--book>] [B<--column>]
[B<-n> I<num>] [B<--auto-rotate>] [B<--ps>] [B<-q>] [I<infile> [I<outfile>]]

B<pdftool.pl> [I<OPTIONS>] I<infile1> ... [I<OPTIONS>] I<infilen> [I<OPTIONS>] I<outfile>

=head1 DESCRIPTION

B<PDFTool> combines the tools in the PSUtils bundle in a nice way. The
inputs should be either Portable Document Format (PDF) files, or
PostScript files.

If no input file is given, or if a single hyphen-minus (I<->) is given as
file name, B<PDFTool> reads the PDF or PostScript data from the standard
input. If a PDF is sent to the standard input, an auxiliary file is
created (because reading a PDF requires random access to the data), and removed
afterwards. Also, if the option B<-c> (cropping) is set while the input is
not a regular seekable file, an auxiliary file is created, and removed
afterwards.

The input page size is by default guessed from the input document. However,
the options B<-P>, B<-W> and B<-H> let you choose a specific input page
size, while B<-c> makes B<PDFTool> ignore the input page size and
calculate the minimal bouding box instead. The default output page size
is I<a4>.

If no output file is given, or if a single hyphen-minus (I<->) is given as
file name, B<PDFTool> sends the data to the standard output. By
default, B<PDFTool> outputs a PDF document; Use B<--ps> to
get a PostScript instead.

If more than n>2 files are passed to B<PDFTool>, the n-1 first will be
processed (using the set of options given immediately before each
argument) and then merged. A global set of options can be passed after the
last input file: they will be applied to all the inputs, (but the local
options take precedence).
NOTE: The options B<-p>, B<-w>, B<-h>, B<--auto-rotate> and B<--ps>
refer to the output file only, and should only be set once.


B<PDFTool> does the following passes on the input documents:

=over 4

=item *

Convert from PDF to PostScript if necessary (if possible,
that is if all page numbers are relative to the begining of the
document, convert only the smallest interval that contains all the selected
pages),

=item *

Select the page range if necessary (option B<-s>),

=item *

Calculate the minimal bounding box (option B<-c>),

=item *

Rearrange pages for printing books or booklets if necessary
(option B<--book>),

=item *

Put multiple pages per sheets (option B<-n>), and

=item *

"Flatten" the output, and convert it to PDF (if the flag B<--ps> is not set).

=back

=head1 OPTIONS

=over 8

=item B<-s> I<pages>, B<--select=>I<pages>

Specify the pages which are to be selected.
I<Pages> is a comma separated list of page ranges, each of which
may be a page number, or a page range of the form
I<first>-I<last>. If I<first> is omitted, the first page is assumed,
and if I<last> is omitted, the last page is assumed.

The prefix character `_' indicates that the page number is relative
to the end of the document, counting backwards. If just this
character with no page number is used, a blank page will be inserted.

=item B<-w> I<length>, B<--width=>I<length>

Specify the width of the output file. If the height is not specified as
well, it will be ignored. The known units are I<pt>, I<in>, I<cm> and
I<mm>. The default unit is I<pt>.

=item B<-h> I<length>, B<--height=>I<length>

Specify the height of the output file. If the width is not specified as
well, it will be ignored. The known units are I<pt>, I<in>, I<cm> and
I<mm>. The default unit is I<pt>.

=item B<-p> I<paper>, B<--paper=>I<paper>

Specify the paper size of the output file, as an alternative to B<-w>
and B<-h>. Can be set to I<a0>, I<a1>, I<a2>, I<a3>, I<a4>, I<a5>, I<b5>,
I<letter>, I<legal>, I<ledger>, I<tabloid>, I<statement>, I<executive>,
I<folio>, I<quarto>, or I<10x14>. The default output paper size is I<a4>.

=item B<-W> I<length>, B<--Width=>I<length>

Same as the option B<-w>, but for the input file. This option is ignored if
the option B<-c> (cropping) is set.

=item B<-H> I<length>, B<--Height=>I<length>

Same as the option B<-h>, but for the input file. This option is ignored if
the option B<-c> (cropping) is set.

=item B<-P> I<paper>, B<--Paper=>I<paper>

Same as the option B<-p>, but for the input file. By default,
B<PDFTool> will try to guess this value from the header of the file,
and will fail if the information is missing. This option is ignored if the
option B<-c> (cropping) is set.

=item B<-b> I<length>, B<--border=>I<length>

Add a margin around each logical page on a sheet. Possible units are I<pt>,
I<in>, I<cm> and I<mm>. The default unit is I<pt>. The default border is
I<1cm> if the option B<-c> (cropping) is set, and I<0> otherwise.

=item B<-m> I<length>, B<--margin=>I<length>

Add a margin around the whole page. Possible units are I<pt>, I<in>, I<cm>
and I<mm>. The default unit is I<pt>. The default margin is I<0>.

=item B<-c>, B<--crop>

If this option is set, the PostScript code will interpreted to calculate the
maximal effective bounding box. This operation may take time and be quite
demanding for the CPU. See the note for the option B<-b> above.

=item B<--book>

Rearrange pages for printing books or booklets.

=item B<-n> I<num>, B<--nup=>I<num>

Put multiple logical pages onto each physical sheet of paper.
If I<num> is less than 10, the option B<->I<num> may be used as an
alternative.

=item B<--auto-rotate>

Auto-rotate the pages in order to ensure that your document will be
printable using your favorite duplex mode for portrait documents (e.g.,
C<Tumble> if you prefer to turn the pages like those of a book -
"vertical folding"; regardless of the orientation of the document).
It has no effect if the input is a portrait document.
This flag might not be suitable if you plan to read the output document
on your screen.
NOTE: Using this flag with multiple input files might lead to weird
outputs!

=item B<--ps>

By default, B<PDFTool> outputs a PDF document; use this flag if
you want a PostScript instead.

=item B<--column>

Change the order to "column-major", where successive pages are placed in
columns down the paper.

=item B<-q>, B<--quiet>

B<PDFTool> normally prints the page numbers of the pages output; this
option suppresses this.

=item B<--help>

Display a brief help.

=item B<--version>

Display the version number of the B<PDFTool> program.

=item B<--man>

Display the manual page.

=back

=head1 EXAMPLES

The following comand can be used to remotely crop a PDF file, convert it
to A4 paper, and rearrange the pages to locally print a (PostScript)
booklet with custom margins:

C<< ssh remote pdftool.pl -cpA4 --book -2 -b2cm -m-1cm --auto-rotate < in.pdf | 
    lpr -o Duplex=DumplexTumble >>

=head1 REQUIREMENTS

=over 4

=item *

Requires C<pdftops> available via the command line (only if the input is
a PDF). Depending on your own version of this program, you might need to
hack the source yourself to remove the C<-origpagesizes> option :-/. 

=item *

Requires L<PSUtils|http://www.tardis.ed.ac.uk/~ajcd/psutils/> installed
and available via the command line.

=item *

Requires L<GhostScript|http://ghostscript.com/> installed and available
via the command C<gs>.

=back

=head1 AUTHOR

Copyright 2010-2012 Guilhem Moulin. See the source for copying
conditions.

=cut



#
# Options & arguments
#

my @inputs;
my %out;    # Global option, for the output file

my $index = 1;
while (@ARGV) {
    my %config;
    GetOptions( "select|s=s" => sub { $config{select} = $_[1] },
                "w|width=s"  => sub { $out{width} = $_[1] },
                "h|height=s" => sub { $out{height} = $_[1] },
                "p|paper=s"  => sub { my ($w,$h) = &papersize ($_[1]);
                                      $out{width} = $w;
                                      $out{height} = $h; },
                "W|Width=s"  => sub { $config{inwidth} = $_[1] },
                "H|Height=s" => sub { $config{inheight} = $_[1] },
                "P|Paper=s"  => sub { my ($w,$h) = &papersize ($_[1]);
                                      $config{inwidth} = $w;
                                      $config{inheight} = $h; },
                "margin|m=s" => sub { $config{margin} = $_[1] },
                "border|b=s" => sub { $config{border} = $_[1] },
                "crop|c"     => sub { $config{crop} = 1 },
                "book"       => sub { $config{book} = 1 },
                "ps"         => sub { $out{ps} = 1 },
                "nup|n=i"    => sub { $config{nup} = $_[1] },
                "auto-rotate"=> sub { $out{autorotate} = 1 },
                "1"          => sub { $config{nup} = 1 },
                "2"          => sub { $config{nup} = 2 },
                "3"          => sub { $config{nup} = 3 },
                "4"          => sub { $config{nup} = 4 },
                "5"          => sub { $config{nup} = 5 },
                "6"          => sub { $config{nup} = 6 },
                "7"          => sub { $config{nup} = 7 },
                "8"          => sub { $config{nup} = 8 },
                "9"          => sub { $config{nup} = 9 },
                "column"     => sub { $config{column} = 1 },
                "q|quiet"    => sub { $config{quiet} = 1},
                "man"        => sub { pod2usage(-exitstatus => 0,
                                                -verbose => 2) }
    ) or pod2usage(2);
    if (@ARGV) {
        $config{infile} = $ARGV[0];
        $config{index} = $index;
        $index++;
        shift;
    }
    push @inputs, \%config;
}


*LOG = *STDERR;
my @gs = ('gs', '-dSAFER');

# Global variables
my @auxfiles;   # Auxiliary files, to remove
my @fds;        # File handles, to close
my @pids;       # Pids, to waid for
my $return = 0; # Return value


my $FOUT;
if ($#inputs > 0) {
    # The last file with the expected result, and the last set of
    # options was the global one
    my $global = pop @inputs;

    pod2usage(2) unless defined $global->{infile};
    if ($global->{infile} ne "-") {
        open $FOUT, '>', $global->{infile}
            or die "Error: Cannot create `" .$global->{infile}. "': $!\n";
        push @fds, $FOUT;
        delete $global->{infile};
    }

    foreach my $config (@inputs) {
        foreach (keys %$global) {
            $config->{$_} = $global->{$_} unless exists $config->{$_};
        }
    }
}
elsif ($#inputs < 0) {
    @inputs = ({ infile => '-' });
}
$FOUT = *STDOUT  unless  defined $FOUT;


try {
    my @ins;
    my ($landscape, $rotate);
    foreach my $config (@inputs) {
        #
        # Default values
        #
        
        $config->{nup} = 1 unless exists $config->{nup};
        
        # Default margin & border
        $config->{margin} = 0 unless exists $config->{margin};
        unless (exists $config->{border}) {
            if (exists $config->{crop}) {
                $config->{border} = '1cm';
            } else {
                $config->{border} = 0;
            }
        }
        
        # Default output papersize
        unless  (exists $out{width} and exists $out{height}) {
            my ($w,$h) = &papersize ("a4");
            $out{width} = $w;
            $out{height} = $h;
        }
        
        # Default unit: PostScript point
        map { $config->{$_} = &topoints($config->{$_}) if exists $config->{$_} }
            qw /inwidth inheight margin border/;
        map { $out{$_} = &topoints($out{$_}) if exists $out{$_} }
            qw /width height/;
        die "Error: Margins are too big.\n"
            if $out{width} <= 2*$config->{margin}
                or $out{height} <= $config->{margin};
        
        
        
        #
        # Check options
        #
        die "Error: Bad page range: `" .$config->{select}. "'.\n" if
            defined $config->{select} &&
            not $config->{select} =~ /^(_?\d*-?_?\d*,)*_?\d*-?_?\d*$/;
        
        die "Error: Bad nup: `" .$config->{nup}. "'.\n" if
            defined $config->{nup} &&
            not ($config->{nup} =~ /^\d+$/ && $config->{nup} > 0);
        
        #
        # Open input file
        #
        my $FIN;
        if (defined $config->{infile} && $config->{infile} ne "-") {
            open $FIN, '<', $config->{infile}
                or die "Error: Cannot read `" .$config->{infile}. "': $!\n";
            push @fds, $FIN;
        } else {
            $FIN = *STDIN;
        }
    

        #
        # Process the file
        #
        my $FD = &pdftops($FIN, $config);
    
        $FD = &psselect($FD, $config) if exists $config->{select};
    
        my ($FD2, $bbox) = &psbbox($FD, $config);
    
        $FD2 = &psbook($FD2, $config) if exists $config->{book};
    
        my $FD3;
        ($FD3, $landscape, $rotate) = &psnup ($FD2, $bbox, $config);
        push @ins, $FD3;
    }
    &write ($landscape, $rotate, @ins);
}
    
catch Error with {

    # Print the error message
    print LOG shift;

    # Kill all the running childrens
    kill 15, map {$$_[0]} @pids;

    $return = 1;
}

finally {

    # Avoid zombies
    map { my ($pid, @cmd) = @$_;
          my ($r,$v) = (waitpid ($pid, 0), $?);
          warn "Warning: Cannot run `" .&printcmd (@cmd). "'.\n"
            if  ($r != -1 and $v >> 8);
        } @pids;

    # Close opened file handles
    map { close $_  or  die "Cannot close: $!" } @fds;

    # Delete auxiliary files
    unlink @auxfiles;

    exit $return;
};
    
# Useless, but Perl doesn't see that this filehandle is used more than
# once
close IN; # automatically closed by `open3'
close OUT;


# =========================================================



#
# Conversion from PDF to PS, if necessary
#
sub pdftops {

    my ($IN, $config) = @_;
    my $OUT;

    #
    # Detect filetype, using input file's magic number
    #
    # To avoid to seek into IN, it gonna be copied from WRITE to READ in
    # the background, once the filetype has been read

    my $filetype;
    my ($READ, $WRITE);
    pipe $READ, $WRITE  or  die "Cannot pipe: $!";

    $_ = <$IN>;
    print $WRITE ($_)  or  die "Cannot print: $!";
    if (defined $_ && $_ =~ /^%!/) {
        $filetype = "PS";
    } elsif (defined $_ && $_ =~ /^%PDF/) {
        $filetype = "PDF";
    } else {
        die "Error: Input file `" .$config->{infile}.
            "' has an unknown magic number.\n";
    }

    unless (my $pid = fork) {
        # Child: cat $IN > $WRITE in background
        die "Cannot fork: $!" unless defined $pid;
        close $READ  or  die "Cannot close: $!";

        while (<$IN>) {
            print $WRITE ($_)  or  die "Cannot print: $!";
        }
        exit;
    }

    # Parent
    close $WRITE  or  die "Cannot close: $!";


    return $READ if $filetype eq "PS";


    #
    # Conversion from PDF to PS
    #
    my $infile;
    if (defined $config->{infile} && $config->{infile} ne '-') {
        $infile = $config->{infile};
    }
    else {
        # Need to copy the whole input to an auxiliary file, since
        # conversion from PDF to PS requires random access to the data

        $infile = &mktemp( "pdftool-stdin-$$.". lc $filetype );

        open my $AUX, '>', $infile
            or die "Error: Cannot write into `" .$infile. "': $!\n";

        # cat > $infile
        while (<$READ>) {
            print $AUX ($_)  or  die "Cannot print: $!";
        }
        close $AUX;
    }

    my ($first, $last);
    # pdftops doesn't provide any way to have page numbers relative to
    # the end of the document, hence there is no detection of the
    # smallest interval if $config->{select} contains `_'
    if (defined $config->{select} && not $config->{select} =~ /_/) {
        # Convert to PS only the pages we are interested in
        ($first, $last) = (1<<16,-(1<<16));
        for (split /,/, $config->{select}) {
            $_ =~ /^(\d*)(-?)(\d*)$/;
            my ($rmin,$sep,$rmax) = ($1,$2,$3);
            undef $first if $sep && not $rmin;
            undef $last if $sep && not $rmax;
            if ($rmin) {
                $first = $rmin if defined $first && $rmin < $first;
                $last = $rmin if defined $last && $rmin > $last;
            }
            if ($rmax) {
                $first = $rmax if defined $first && $rmax < $first;
                $last = $rmax if defined $last && $rmax > $last;
            }
        }

        # Calculate the new page range
        my @newselect;
        for (split /,/, $config->{select}) {
            $_ =~ /^(\d*)(-?)(\d*)$/;
            my ($rmin,$sep,$rmax) = ($1,$2,$3);
            if (defined $first) {
                $rmin -= $first-1 if $rmin;
                $rmax -= $first-1 if $rmax;
            }
            push @newselect, "$rmin$sep$rmax";
        }

        $config->{select} = join ',', @newselect;
    }

    # Convert to PS
    # TODO: use gs & ps2write, more portable
    my @cmd = ('pdftops', '-origpagesizes', $infile, '-');
    push @cmd, '-f', $first  if  defined $first;
    push @cmd, '-l', $last  if  defined $last;
    push @cmd, '-q'  if  exists $config->{quiet};

    my $pid = open $OUT, '-|', @cmd;
    push @pids, [$pid, @cmd];

    return $OUT;
}



#
# Select some pages in the document
#
sub psselect {
    my ($IN, $config) = @_;
    my $OUT;

    my @cmd = ('psselect', '-p'. $config->{select});
    push @cmd, '-q'  if  exists $config->{quiet};

    *IN = $IN;
    my $pid = open3 '<&IN', $OUT, '>&LOG', @cmd;
    push @pids, [$pid, @cmd];

    return $OUT;
}



#
# Detect / calculate the bounding box
#
sub psbbox {
    my ($IN, $config) = @_;
    my ($OUT, @bbox);

    if (exists $config->{crop}) {
        # Calculate the maximal bounding box

        unless (seek $IN, 0, 1) {
            # The input is not seekable: have to create a seekable auxiliary
            # file

            my $auxfile = &mktemp( "pdftool-in$config->{index}-$$.ps" );

            open my $AUX, '>', $auxfile
                or die "Cannot write into `" .$auxfile. "': $!\n";

            # cat > $auxfile
            while (<$IN>) {
                print $AUX ($_) or  die "Cannot print: $!";
            }
            close $AUX  or  die "Cannot close: $!";
            close $IN  or  die "Cannot close: $!";

            open $IN, '<', $auxfile  or  die "Cannot read `" .$auxfile.  "': $!\n";
        }

        # Need to duplicate IN, since it will be closed in the parent process
        open *IN, '<&=', $IN  or die "Cannot fdopen: $!";

        my @cmd = (@gs, '-sDEVICE=bbox', '-dQUIET', '-dBATCH', '-dNOPAUSE',
                        '-f', '-');
        my $pid = open3 '<&IN', '>&OUT', *OUT, @cmd;

        my ($p,$c) = (0,0); # Page & character counter
        my ($x0, $y0, $x1, $y1) = (1<<16, 1<<16, -(1<<16), -(1<<16));
        while (<OUT>) {
            if ($_ =~ m/^\%\%BoundingBox: (\d+) (\d+) (\d+) (\d+)/) {
                $x0 = $1 if $1 < $x0;
                $y0 = $2 if $2 < $y0;
                $x1 = $3 if $3 > $x1;
                $y1 = $4 if $4 > $y1;
                unless (exists $config->{quiet}) {
                    my $s = "[" . ++$p . "] ";
                    $c += length $s;
                    if ($c >= 80) {
                        print LOG "\n"  or  die "Cannot print: $!";
                        $c = length $s;
                    }
                    print LOG $s  or  die "Cannot print: $!";
                }
            }
        }
        close OUT  or  die "Cannot close: $!";
        print LOG "\n"  or  die "Cannot print: $!" unless exists $config->{quiet};

        # No zombie processes
        waitpid $pid, 0;
        die "Cannot run `" .&printcmd (@cmd). "'.\n"  if  $? >> 8;

        die "Error while calculating bounding box.\n"
            if ($x0 >= $x1 || $y0 >= $y1);
        @bbox = ($x0, $y0, $x1, $y1);

        # Let's go back to the beginning of the input
        seek $IN, 0, 0  or  die "Cannot seek: $!";
        $OUT = $IN;
    }
    elsif (exists $config->{inwidth} and exists $config->{inheight}) {
        @bbox = (0, 0, $config->{inwidth}, $config->{inheight});
        $OUT = $IN;
    }
    else {
        # Guess page size from the input file

        # To avoid to seek into IN, it gonna be copied from WRITE to READ
        # in background, once the Bounding Box has been read
        my ($READ, $WRITE);
        pipe $READ, $WRITE  or  die "Cannot pipe: $!";

        # TODO: consider PageBoundingBox (and take the biggest)
        while (not (@bbox) && defined (my $l = <$IN>)) {
            print $WRITE ($l)  or  die "Cannot print: $!";
            @bbox = ($1, $2, $3, $4)
                if ($l =~ m/^\%\%BoundingBox: (\d+) (\d+) (\d+) (\d+)/);
        }

        die "Cannot guess input page size.\n"  unless  @bbox;

        unless (my $pid = fork) {
            # Child: cat IN > WRITE in background
            die "Cannot fork: $!" unless defined $pid;
            close $READ  or  die "Cannot close: $!";;

            while (<$IN>) {
                print $WRITE ($_)  or  die "Cannot print: $!";
            }
            exit;
        }
        # Parent

        close $WRITE  or  die "Cannot close: $!";

        $OUT = $READ;
    }

    return ($OUT, \@bbox);
}



#
# PSBook
#
sub psbook {
    my ($IN, $config) = @_;
    my $OUT;

    my @cmd = ('psbook');
    push @cmd, '-q'  if  exists $config->{quiet};

    *IN = $IN;
    my $pid = open3 '<&IN', $OUT, '>&LOG', @cmd;
    push @pids, [$pid, @cmd];

    return $OUT;
}



#
# PSNup (inlined here, to keep track of the possible rotation)
#
sub psnup {
    my ($IN, $bbox, $config) = @_;

    my ($OUT, $landscape, $rotate);

    if ((($bbox->[2]-$bbox->[0] > $bbox->[3]-$bbox->[1])
            and not ($out{width}-2*$config->{margin} >
                     $out{height}-2*$config->{margin}))
         or
         (not (exists $out{autorotate})
            and not ($bbox->[2]-$bbox->[0] > $bbox->[3]-$bbox->[1])
            and ($out{width}-2*$config->{margin} >
                 $out{height}-2*$config->{margin}))) {
        ($out{height}, $out{width}) = ($out{width}, $out{height});
        $landscape = 1;
    }


    #
    # Find the best layout is an optimisation problem. We try all of the
    # combinations of width*height in both normal and rotated form, and
    # minimise the wasted space.
    #
    my ($ow,$oh) = ($out{width}-2*$config->{margin},
                    $out{height}-2*$config->{margin});

    my ($iw, $ih) = ($bbox->[2]-$bbox->[0], $bbox->[3]-$bbox->[1]);
    my ($horiz, $vert, $scale, $hshift, $vshift);

    my $tolerance = 100000; # layout tolerance
    my $best = $tolerance;

    for (my $hor = 1; $hor; $hor = &nextdiv($hor, $config->{nup})) {
        my $ver = $config->{nup} / $hor;
        # try normal orientation first
        my $scl = &min ($oh/($ih*$ver), $ow/($iw*$hor));

        my $optim = ($ow-$scl*$iw*$hor) * ($ow-$scl*$iw*$hor)
                  + ($oh-$scl*$ih*$ver) * ($oh-$scl*$ih*$ver);
        if ($optim < $best) {
           $best = $optim;
           # recalculate scale to allow for internal borders
           $scale = &min (($oh-2*$config->{border}*$ver)/($ih*$ver),
                          ($ow-2*$config->{border}*$hor)/($iw*$hor));
           $hshift = ($ow/$hor - ($bbox->[2]+$bbox->[0])*$scale)/2;
           $vshift = ($oh/$ver - ($bbox->[3]+$bbox->[1])*$scale)/2;
           ($horiz, $vert) = ($hor, $ver);
           $rotate = 0;
        }
        # try rotated orientation
        $scl = &min ($oh/($iw*$hor), $ow/($ih*$ver));
        $optim = ($oh-$scl*$iw*$hor) * ($oh-$scl*$iw*$hor)
               + ($ow-$scl*$ih*$ver) * ($ow-$scl*$ih*$ver);
        if ($optim < $best) {
           $best = $optim;
           # recalculate scale to allow for internal borders
           $scale = &min (($oh-2*$config->{border}*$hor)/($iw*$hor),
                          ($ow-2*$config->{border}*$ver)/($ih*$ver));
           $hshift = ($ow/$ver - ($bbox->[3]+$bbox->[1])*$scale)/2;
           $vshift = ($oh/$hor - ($bbox->[2]+$bbox->[0])*$scale)/2;
           ($horiz, $vert) = ($ver, $hor);
           $rotate = 3;
        }
    }

    # Fail if nothing better than worst tolerance was found
    die "Error: Cannot find acceptable layout for $config->{nup}-up.\n"
        if $best == $tolerance;


    #
    # Construct pstops specification list
    #
    my $n = $horiz * $vert;
    my (@ospecs, @especs); # specs for odd and even pages

    for (my $pageno = 0; $pageno < $n; $pageno++) {
        my ($up, $across);   # pageno index
        my ($orot,$erot) = ('','U');
        my ($xoff, $yoff);


        if ($rotate) {
            if (exists $config->{column}) {
                # column=0; leftright=1; topbottom=0;
                $across = $pageno % $horiz;
                $up = floor ($pageno / $horiz);
            } else {
                # column=1; leftright=1; topbottom=0;
                $across = floor($pageno / $vert);
                $up = $pageno % $vert;
            }
            ($orot,$erot) = ('L','R');
            $xoff = ($across+1)*$ow/$horiz - $hshift;
        } else {
            if (exists $config->{column}) {
                # column=1; leftright=1; topbottom=1;
                $across = floor($pageno / $vert);
                $up = $vert-1 - floor($pageno % $vert);
            } else {
                # column=0; leftright=1; topbottom=1;
                $across = $pageno % $horiz;
                $up = $vert-1 - floor($pageno / $horiz);
            }
            $xoff = $across*$ow/$horiz + $hshift;
        }
        $yoff = $up*$oh/$vert + $vshift;

        push @ospecs, sprintf ("%d%s@%.3f(%.3f,%.3f)",
                               $pageno, $orot, $scale,
                               $xoff+$config->{margin},
                               $yoff+$config->{margin});
        push @especs, sprintf ("%d%s@%.3f(%.3f,%.3f)",
                               $n + $pageno, $erot, $scale,
                               $ow-$xoff+$config->{margin},
                               $oh-$yoff+$config->{margin});
    }

    ($ow,$oh) = ($oh,$ow) if $rotate%2;

    my $pagespecs;
    if (not (exists $out{autorotate}) || $ow < $oh) {
      $pagespecs = $config->{nup} . ':' . join ('+', @ospecs);
    } else {
      $pagespecs = 2*$config->{nup} . ':' . join ('+', @ospecs)
                                    . ',' . join ('+', @especs);
    }

    my @cmd = ('pstops', '-w'. $bbox->[2], '-h'. $bbox->[3], $pagespecs);
    push @cmd, '-q'  if  exists $config->{quiet};

    *IN = $IN;
    my $pid = open3 '<&IN', $OUT, '>&LOG', @cmd;
    push @pids, [$pid, @cmd];

    return ($OUT, $landscape, $rotate);
}



#
# Final file: setup the correct orientation/page size
#
sub write {
    my ($landscape, $rotate, @FINS) = @_;

    my @args = ('-f', '-');
    my $IN = $FINS[0];

    for (my $index=2; $index<=1+$#FINS; $index++) {
      # We have to create temporary files for every PostScript file
      my $auxfile = &mktemp( "pdftool-gsin$index-$$.ps" );
      push @args, '-f', $auxfile;
    
      open my $AUX, '>', $auxfile
          or die "Error: Cannot write into `" .$auxfile. "': $!\n";
      my $FIN = $FINS[$index-1];   # Bug: can't <$FINS[$index-1]>
      while (<$FIN>) {
          print $AUX ($_)  or  die "Cannot print: $!";
      }
      close $FIN or die "Cannot close: $!";
    }

    my ($ow, $oh) = ($out{width}, $out{height});
    ($ow,$oh) = ($oh,$ow) if $rotate%2;

    my $pagedevice;
    if (not (exists $out{autorotate}) || $oh < $oh || $landscape) {
        $rotate = ($rotate+1)%4 if (exists $out{autorotate}) and $oh < $ow;
        $pagedevice = "/Orientation $rotate /PageSize [$out{width} $out{height}]";
    } else {
        $pagedevice = "/PageSize [$out{width} $out{height}]";
    }

    my $device = '-sDEVICE=pdfwrite';
    $device = '-sDEVICE=ps2write' if exists $out{ps};
    my @cmd = (@gs, '-dQUIET', '-dBATCH', '-dNOPAUSE', $device, 
                    '-dAutoRotatePages=/None',
                    '-dDetectDuplicateImages=false',
                    # Preserve image quality
                    '-dAutoFilterColorImages=false',
                    '-dAutoFilterGrayImages=false',
                    '-dColorImageFilter=/FlateEncode',
                    '-dGrayImageFilter=/FlateEncode',
                    '-dMonoImageFilter=/FlateEncode',
                    '-sOutputFile=%stdout%', 
                    '-c', "<< $pagedevice >> setpagedevice",
                    @args);

    (*IN,*OUT) = ($IN,$FOUT);
    my $pid = open3 '<&IN', '>&OUT', '>&LOG', @cmd;
    push @pids, [$pid, @cmd];
}



#
# In-place convert the given length to PostScript points
#
sub topoints {
    my $l = $_[0];
    return unless defined $l;

    $l =~ /^([+-]?\d*\.?\d+)(\w*)$/  or  die "Unable to parse `" .$l. "'.\n";

    my $r = $1;
    if ($2 eq "" or $2 eq "pt") {
        # nothing
    } elsif ($2 eq "in") {
        $r *= 72;
    } elsif ($2 eq "cm") {
        $r *= 72/2.54;
    } elsif ($2 eq "mm") {
        $r *= 72/25.4;
    } else {
        die "Unknown unit: `$2'.\n";
    }
    return floor ($r + .5);
}



#
# In-place set the given width and height to the predefined papersize
#
sub papersize {
    my $p = lc $_[0];

    if ($p eq "a0") {
        return (2384, 3370);   # 84.1cm * 118.9cm
    } elsif ($p eq "a1") {
        return (1684, 2384);   # 59.4cm * 84.1cm
    } elsif ($p eq "a2") {
        return (1191, 1684);   # 42cm *  59.4cm
    } elsif ($p eq "a3") {
        return (842, 1191);    # 29.7cm * 42cm
    } elsif ($p eq "a4") {
        return (595, 842);     # 21cm * 29.7cm
    } elsif ($p eq "a5") {
        return (421, 595);     # 14.85cm * 21cm
    } elsif ($p eq "b5") {
        return (516, 729);     # 18.2cm * 25.72cm
    } elsif ($p eq "letter") {
        return (612, 792);     # 8.5in * 11in
    } elsif ($p eq "legal") {
        return (612, 1008);    # 8.5in * 14in
    } elsif ($p eq "ledger") {
        return (1224, 792);    # 17in * 11in
    } elsif ($p eq "tabloid") {
        return (792, 1224);    # 11in * 17in
    } elsif ($p eq "statement") {
        return (396, 612);     # 5.5in * 8.5in
    } elsif ($p eq "executive") {
        return (540, 720);     # 7.6in * 10in
    } elsif ($p eq "folio") {
        return (612, 936);     # 8.5in * 13in
    } elsif ($p eq "quarto") {
        return (610, 780);     # 8.5in * 10.83in
    } elsif ($p eq "10x14") {
        return ("10in", "14in");
    } else {
        die "Error: Unknown paper size: `" .$p. "'.\n";
    }
}



#
# Print a command just like you'd do in a shell
#
sub printcmd {
    my @cmd;

    for (@_) {
        my $s = $_;
        $s =~ s/"/\\"/;
        $s = "\"$s\""  if  $s =~ /[ ()';#{}*?~&|`!]/;
        push @cmd, $s;
    }

    join ' ', @cmd;
}

sub nextdiv {
    my ($n, $m) = @_;
    while (++$n <= $m) {
        return $n if ($m % $n == 0)
    }
    return 0;
}

sub min {
    my ($n, $m) = @_;
    return $n if $n < $m;
    return $m;
}


#
# Make a temporary file, and remove it afterwards
#
sub mktemp {
    my $auxfile = catfile( tmpdir(), $_[0] );
    push @auxfiles, $auxfile;
    return $auxfile;
}