#!/usr/bin/perl -w
# (C) 2003-2007 Willem Jan Hengeveld <itsme@xs4all.nl>
# Web: http://www.xs4all.nl/~itsme/
#      http://wiki.xda-developers.com/
#
# $Id: makefiles.pl 1502 2007-04-15 07:54:20Z itsme $
#
use strict;
use File::stat;
use List::Util qw(sum);

# tries to optimally create file sections, based on this 
# estimate of size: 28*nfiles+84+0x1000+sum(filesize)+sum(filenamesize)

if (@ARGV<3) { die Usage(); }

sub Usage {
    return <<__EOF__;
Usage: makefiles <sourcedir> <targetdir> <maxsize> [ <targetdir> <maxsize>  ...]
__EOF__
}

my $sourcedir= shift;

my $filelist= GetFileList($sourcedir);
my @targets;
while (@ARGV) {
    my $dir= shift;
    my $maxsize= eval(shift);

    my $files= GetFileList($dir);

    push @targets, {
        dir=>$dir,
        maxsize=>$maxsize,
        spaceused=>0x1000+84+(@$files?sum(map { $_->{spaceneeded} } @$files):0),
        files=>$files,
    };
}

# loop over files, in order of descending size
for my $file (sort { $b->{spaceneeded} <=> $a->{spaceneeded} } @$filelist)
{
    my $area= FindSuitableArea(\@targets, $file) || die "Cannot fit files in given sections\n";

    push @{$area->{newfiles}}, $file;
    $file->{moveto}= $area->{dir};

    $area->{spaceused} += $file->{spaceneeded};
}

for (@targets) {
    if ($_->{spaceused} > $_->{maxsize}) {
        die "Area $_->{dir} is too large\n";
    }
}
for(@$filelist) {
    rename($_->{path}, "$_->{moveto}/$_->{name}") || die "error moving $_->{path} to $_->{moveto}: $!\n";
}

exit(0);

sub FindSuitableArea {
    my ($targets, $file)= @_;
    # loop over target regions, in order of ascending leftover space
    for my $area (sort { $a->{maxsize}-$a->{spaceused} <=> $b->{maxsize}-$b->{spaceused} } @$targets)
    {
        if ($area->{maxsize}-$area->{spaceused} >= $file->{spaceneeded}) {
            return $area;
        }
    }
}

sub GetFileList {
    my ($filedir)= @_;

    return [] unless ($filedir);

    opendir(DIR, $filedir) or warn "$!: reading $filedir\n";
    my @files= readdir DIR;
    closedir DIR;

    my @fileinfo;
    for (@files) {
        my $path= "$filedir/$_";
        next unless -f $path;
        my $stat= stat($path);
        push @fileinfo, {
            name=>$_,
            path=>$path,
            size=>$stat->size,
            spaceneeded=>roundup($stat->size)+roundup(length($_)+1)+28,
        };
    }

    return \@fileinfo;
}
sub roundup {
    my ($n)= @_;
    return ($n|3)+1;
}