#!perl -w
$|=1;
package PageReader;
use strict;

sub findpattern {
    my ($ref, $pattern)= @_;
    my @ofs;
    my $pos;
    while ($$ref =~ /$pattern/g) {
        push @ofs, pos($$ref)-length($&);
    }
    return @ofs;
}
sub new {
    my ($class, $savedir)=@_;

    my $self= bless {data=>\$_[0]}, $class;
    my @ofs=findpattern($self->{data}, qr/\x00\x00\x00\x53....EFSSuper/);
    my @diff;
    push @diff, $ofs[$_]-$ofs[$_-1] for (1..$#ofs);
    my %diff;
    $diff{$_}++ for @diff;

    print map { sprintf("%08x:%2d\n", $_, $diff{$_}) } keys %diff;
    my @diffmost= sort { $diff{$a}<=>$diff{$b} } keys %diff;

    $self->{bytesPerBlock}= $diffmost[-1];
    $self->{nSuperBlocks}= $diff{$diffmost[-1]}+1;
    $self->{totalBlocks}= length(${$self->{data}})/$self->{bytesPerBlock};

    printf("b/blk=%08lx nsuper=%d nblks=%d\n", $self->{bytesPerBlock}, $self->{nSuperBlocks}, $self->{totalBlocks});

    my $super;
    for (my $i=0 ; $i<$self->{nSuperBlocks} ; $i++)
    {
        my $superdata= $self->read_block($self->{totalBlocks}-$i-1, 2048);
        my $s= parse_super($superdata);
        $super= $s if (!$super || compareage($s->{age}, $super->{age})>0)
    }
    printf("age=%04x\n", $super->{age});
    $self->{$_} = $super->{$_} for keys %$super;

    $self->{totalPages}= $self->{totalBlocks}*$self->{pagesPerBlock};

    $self->{tablesize}= scalar @{$super->{ptable}};

    $self->{info}= parse_inodeinfo($self->read_cluster($self->{info_clus}));
    $self->{db}= $self->parse_dbpage($self->read_cluster($self->{db_clus}));
    for my $c (@{$self->{db}{subdbpages}}) {
        my $n= $self->parse_dbpage($self->read_cluster($c));
    }

    for my $in (keys %{$self->{files}}) {
        my $f= $self->{files}{$in};
        next if $f->{name} eq "..";
        next if $f->{name} eq ".";
        next if !exists $f->{data};
        printf("i_%04x: %s\n", $in, $self->findpath($in));
        if ($savedir) {
            my $ofh= IO::File->new("$savedir/efs".$self->findpath($in), "w") or die "efs-save: $!\n";
            binmode $ofh;
            $ofh->print($f->{data});
            $ofh->close();
        }
        else {
            printf("   %s\n", unpack("H*", $f->{data}));
        }
    }

    return $self;
}
sub isdir { return ($_[0]&0170000)==0040000; }
sub isreg { return ($_[0]&0170000)==0100000; }

sub findpath {
        my ($self, $inr)= @_;
        my $in= $self->{files}{$inr};
        return "" if $inr == $in->{parent};
        return $self->findpath($in->{parent})."/".$in->{name}
}

sub compareage {
    my ($a,$b)= @_;
    #  |...|...|...|...|
    #    a           b    : b younger
    #    b           a    : a younger
    #        a   b        : a younger
    #        b   a        : b younger
    #    a       b        : ?
    #    b       a        : ?
    return 1 if ($a<0x4000 && $b>0xc000);
    return -1 if ($b<0x4000 && $a>0xc000);
    return 1 if ($a>$b);
    return -1 if ($a<$b);
    return 0;
}
sub read_block {
    my ($self, $blocknr, $size)= @_;
    #printf("block %d  %08lx\n", $blocknr, $size);
    return substr(${$self->{data}}, $self->{bytesPerBlock}*$blocknr, $size);
}

sub read_page {
    my ($self, $pagenr)=@_;
    #printf("page %04x\n", $pagenr);
    return substr(${$self->{data}}, $self->{bytesPerPage}*$pagenr, $self->{bytesPerPage});
}

sub parse_super {
    my %super;
    my ($ptable, $rtable, $crc);
    (
    $super{magic0},           # V   +0000: 
    $super{version},          # v   +0004: 
    $super{age},              # v   +0006: 
    $super{magic},            # a8  +0008: 
    $super{pagesPerBlock},    # V   +0010:
    $super{bytesPerPage},     # V   +0014:
    $super{totalBlocks},      # V   +0018:
    $super{pagenr1},          # V   +001c:
    undef,                    # a40 +0020:
    $super{db_clus},          # V   +0048
    $super{info_clus},        # V   +004c
    undef,                    # a112+0050
    $super{w0},               # v   +00c0:
    $super{w1},               # v   +00c2:
    $super{w2},               # v   +00c4:
    $super{w3},               # v   +00c6:
    $super{pageTablesStart},  # V   +00c8:
    $super{superStart0},      # V   +00cc:
    $super{superStart},       # V   +00d0:
    $super{superEnd},         # V   +00d4:
    undef,                    # V   +00d8:
    undef,                    # V   +00dc:
    $ptable,                  # a904+00e0:
    $rtable,                  # a904+0468:
    undef,                    # V   +07f0:
    undef,                    # V   +07f4:
    undef,                    # V   +07f8:
    $crc,                     # V   +07fc:
)= unpack("Vvva8VVVVa40VVa112vvvvVVVVVVa904a904VVVV", $_[0]);

#print map { sprintf("%-20s: %8x\n", $_, $super{$_}) } keys %super;
    $super{rtable}= [ unpack("V*", $rtable) ];
    $super{ptable}= [ unpack("V*", $ptable) ];

    return \%super;
}
use constant {
    P_DATA => 0,
    P_PAGETABLE => 1,
    P_SUPER => 2,
    P_UNDEF1 => 3,
    P_TABLINFO => 4,
    P_UNDEF2 => 5,
    PT_UNKNOWN => -1,
    PT_2 => -2,
    PT_3 => -3,
    PT_4 => -4,
    PT_5 => -5,
    PT_6 => -6,
    PT_RESERVED => -7,
    PT_LOG => -8,
    PT_SUPER => -9,
    PT_10 => -10,
    PT_11 => -11,
    PT_GARBAGE => -12,
    PT_13 => -13,
    PT_BAD => -14,
    PT_ERASED => -15,
    PT_16 => -16
};
sub pagenrtype {
    my ($self, $pagenr)= @_;
    die unless defined $pagenr;
    die "ERROR: negative pagenr $pagenr\n" if ($pagenr<0);
    # data page
    return 0 if ($pagenr<$self->{pageTablesStart}*$self->{pagesPerBlock});
    # pagetable page
    return 1 if ($pagenr<$self->{superStart}*$self->{pagesPerBlock});
    # superblock page
    return 2 if ($pagenr<$self->{totalBlocks}*$self->{pagesPerBlock});
    # undefined page
    return 3 if ($pagenr<0x80000000);
    # pagetable
    return 4 if ($pagenr<0xc0000000);
    # undefined page
    return 5 if ($pagenr<0xfffffff0);
    # special
    #  -1 : unknown
    #  -2.. -6 : ?
    #  -7 : reserved
    #  -8 : log
    #  -9 : super
    #  -10 .. -11 : ?
    #  -12 : garbage
    #  -13 : ?
    #  -14 : bad
    #  -15 : erased
    return ($pagenr&0xf)-0x10;
}

sub cluster2page {
    my ($self, $clusternr)= @_;
    return 0xFFFFFFFF if $clusternr == 0xFFFFFFFF;;
    my $ptpage= $self->{ptable}[$clusternr>>9];
    if ($self->pagenrtype($ptpage)==P_PAGETABLE) {
        my $data= $self->read_page($ptpage);
        return unpack("V", substr($data, ($clusternr&511)*4, 4));
    }
    else {
        warn sprintf("ptab %04x -> page %08lx\n", $clusternr, $ptpage);
    }
    return 0xFFFFFFFF;
}
sub page2cluster {
    my ($self, $pagenr)= @_;
    my $ptpage= $self->{rtable}[$pagenr>>9];
    if ($self->pagenrtype($ptpage)==P_PAGETABLE) {
        my $data= $self->read_page($ptpage);
        return unpack("V", substr($data, ($pagenr&511)*4, 4));
    }
    else {
        warn sprintf("rtab %04x -> page %08lx\n", $pagenr, $ptpage);
    }
    return 0xFFFFFFFF;
}
sub read_cluster {
    my ($self, $clusternr)= @_;
    my $pagenr= $self->cluster2page($clusternr);
    if ($self->pagenrtype($pagenr)==P_DATA) {
        return $self->read_page($pagenr);
    }
    else {
        warn sprintf("cluster %04x -> page %08lx\n", $clusternr, $pagenr);
    }
}
sub read_inode {
    my ($self, $inodenr)= @_;
    my $clusternr= $inodenr>>4;
    my $clusterofs= ($inodenr&0xF)<<7;
    my $data= $self->read_cluster($clusternr);
    return substr($data, $clusterofs, 0x80);
}
sub parseinode {
    my %inode;
    my $ptrdata;
    # note:
    #   attr is either 0 or 0x4564
    #   uid==gid==0  always
    #   mode is one of:
    # 040555  dr-xr-xr-x
    # 040700  drwx------
    # 040755  drwxr-xr-x
    # 040777  drwxrwxrwx
    # 100600  -rw-------
    # 100666  -rw-rw-rw-
    # 100755  -rwxr-xr-x
    # 104544  -r-xr-Sr--

    # dates are one of the following: (all in UTC)
    #   1980-01-06 00:00:00  ( 0x12d53d80 )
    #   2007-08-11 17:50:04  ( 0x46bdf6cc )
    #   .. and later

    return if ($_[0] =~ /^\xff+$/);
    (
        $inode{mode},        #+00:   fs_mode_t     mode;
        $inode{nlink},       #+02:   uint16        nlink;          /* Number of hard links. */
        $inode{attr},        #+04:   uint32        attr;           /* Extended attributes. */
        $inode{size},        #+08:   uint32        size;           /* Size of file, in bytes. */
        $inode{uid},         #+0c:   uint16        uid;
        $inode{gid},         #+0e:   uint16        gid;
        $inode{generation},  #+10:   uint32        generation;     /* Inode generation.  Incremented on file creation. */
        $inode{clusters},    #+14:   uint32        blocks;         /* Blocks (clusters) used by file. */
        $inode{mtime},       #+18:   uint32        mtime;          /* Last mod time of file. */
        $inode{ctime},       #+1c:   uint32        ctime;          /* Posix ctime. */
        $inode{reserved},    #+20:   uint32        reserved[8];    /* Future use. */
        $ptrdata,            #+40:   cluster_id data[FS_DIRECT_CLUSTER_COUNT + FS_DIRECTION_LEVELS - 1];
    )= unpack("vvVVvvVVVVa32a64", $_[0]);
    my @dataclusters= unpack 'V*', $ptrdata;
    $inode{dataptrs}= [@dataclusters];
    if ($inode{reserved} !~ /^\x00+$/) {
        printf("NOTE:RES: %s\n", unpack 'H*', $inode{reserved});
    }
    printf("NOTE:gid=%d uid=%d\n", $inode{gid}, $inode{uid}) if ($inode{gid} || $inode{uid});

    return \%inode;
}
sub read_inode_data {
    my ($self, $inode)= @_;
    my $data= "";
    my $i=0;
    while (length($data)<$inode->{size} && $i<13) {
        if ($inode->{dataptrs}[$i]==0xFFFFFFFF) {
            warn "invalid cluster in block list\n";
            return $data;
        }
        $data .= $self->read_cluster($inode->{dataptrs}[$i++]);
    }
    while (length($data)<$inode->{size} && $i<16) {
        if ($inode->{dataptrs}[$i]==0xFFFFFFFF) {
            warn "invalid cluster in block list\n";
            return $data;
        }
        my $clusblock= $self->read_cluster($inode->{dataptrs}[$i++]);
        my @clusters= unpack("V*", $clusblock);
        my $j=0;
        while (length($data)<$inode->{size} && $j<@clusters) {
            if ($clusters[$j]==0xFFFFFFFF) {
                warn "invalid cluster in block list\n";
                return $data;
            }
            $data .= $self->read_cluster($clusters[$j++]);
        }
    }
    warn "not enough clusters\n" if (length($data)<$inode->{size});
    $data= substr($data, 0, $inode->{size});

    return $data;
}
sub lookslikeinode {
    return 1 if ($_[0] =~ /^\xff+$/);
    return 0 if ($_[0] =~ /^\x00+$/);

    #                 mmllaaaaaaaaaassssuuuuuuuuggggggggGGGGGGGGGGBBBBBBBBBBmmmmccccRRRRRRRRDDDDDDDDDDDDDDDDDDDDD
    return $_[0] =~ /^......\x00\x00....\x00\x00\x00\x00..\x00\x00..\x00\x00........\x00{32}.{60}\xff\xff\xff\xff$/s;
}
sub lookslikeinodepage {
    return 0 if ($_[0] =~ /^\xff+$/);
    my @nodes= map { substr($_[0], $_*0x80, 0x80) } 0..15;
    my @lookalikes= grep { lookslikeinode($nodes[$_]) } 0..15;
    #printf("look=%s\n", join "", map { lookslikeinode($nodes[$_]) || 0 } 0..15);
    return @lookalikes==16;
}
sub parse_inodeinfo {
    my %info;
    (
        $info{magic},
        $info{version},
        $info{top},
        $info{next},
        $info{free},
        $info{root},
    )= unpack("VVVVVVV", $_[0]);
    printf("INFO: %08lx %08lx %08lx %08lx %08lx %08lx\n", map { $info{$_} } qw(magic version top next free root));
    return \%info;
}
sub parse_dbpage {
    my ($self, $dbdata)= @_;
    my %dbpage;
    my $data;
    (
        $dbpage{prev},
        $dbpage{next},
        $dbpage{bytesused},
        undef, 
        $dbpage{type},
        $data,
    )= unpack("VVva7Ca*", $dbdata);
    printf("NODE: %08lx %08lx  %04x %02x\n", map { $dbpage{$_} } qw(prev next bytesused type));
    $data= substr($data, 0, $dbpage{bytesused});
    if ($dbpage{type}==1) {
        # root
        my @dbpages;
        push @dbpages, unpack("V", $data);
        printf("   firstclus=c_%04x\n", $dbpages[-1]);
        my $ofs=4;
        while ($ofs<length($data))
        {
            my %ix;
            (
                $ix{len},
                $ix{rectype},   # 'd'=dir
                $ix{inode},
            )= unpack("CaV", substr($data, $ofs, 6));
            $ix{name}= substr($data, $ofs+6,$ix{len}-5);
            $ix{clus}= unpack("V", substr($data, $ofs+$ix{len}+1, 4));
            push @dbpages, $ix{clus};
            printf("%02x %s i_%04x c_%04x '%s'\n", $ix{len}, $ix{rectype}, $ix{inode}, $ix{clus}, $ix{name});

            push @{$dbpage{ix}}, \%ix;

            $ofs += $ix{len}+5;
        }
        $dbpage{subdbpages}= \@dbpages;
    }
    else {
        my @dbpages;
        my $ofs= 0;
        while ($ofs<length($data))
        {
            my %ix;
            (
                $ix{len1},
                $ix{len2},
                $ix{rectype},
                $ix{parentinode},
            )= unpack("CCaV", substr($data, $ofs, 7));
            $ix{name}= substr($data, $ofs+7, $ix{len1}-5);
            # d = dir
            # i = file
            # s = symlink
            # n = item?
            $ix{type2}= substr($data, $ofs+2+$ix{len1},1);
            $ix{data}= substr($data, $ofs+3+$ix{len1}, $ix{len2}-1);

            $ix{name}= "."  if ($ix{name} eq "");
            $ix{name}= ".." if ($ix{name} eq "\x00");

            if ($ix{type2} eq 'i') {
                $ix{inode2}= unpack("V", $ix{data});
                if ($ix{name} ne "..") {
                    $self->{files}{$ix{inode2}}= {
                        name=>$ix{name},
                        parent=>$ix{parentinode},
                    };
                }

                printf("%02x %02x %s i_%04x %s i_%04x %-35s\n",
                    $ix{len1}, $ix{len2}, $ix{rectype}, $ix{parentinode}, $ix{type2}, $ix{inode2}, "'$ix{name}'");

                my $inodedat = $self->read_inode($ix{inode2});
                my $inode= parseinode($inodedat);
                if ($inode) {
                    printf("i_%04x: %06o %2d %04x %8d %2d %3d %08lx %08lx %08lx,%08lx,...\n",
                        $ix{inode2}, map({ $inode->{$_} } qw(mode nlink attr size generation clusters mtime ctime)),
                        @{$inode->{dataptrs}}[0,1]);

                    if (isreg($inode->{mode})) {
                        my $filedata= $self->read_inode_data($inode);
                        printf("filesize=%8d\n", length($filedata));
                        $self->{files}{$ix{inode2}}{data}= $filedata;
                    }
                }
            }
            else {
                printf("%02x %02x %s i_%04x %s        %-35s %s\n",
                    $ix{len1}, $ix{len2}, $ix{rectype}, $ix{parentinode}, $ix{type2}, "'$ix{name}'", unpack("H*",$ix{data}));
                $self->{files}{0x10000+scalar keys %{$self->{files}}}= {
                    name=>$ix{name},
                    parent=>$ix{parentinode},
                    data=>$ix{data},
                };

            }

            $ofs += $ix{len1}+$ix{len2}+2;
        }
    }

    # key layout:
    #   'd' + inode_num + name
    return \%dbpage;
}
package main;
use strict;
use IO::File;

my $fn= shift || die "Usage: dumpefs <filename> [savedir]\n";
my $savedir= shift;
my @blocks;
my $fh= IO::File->new($fn, "r") or die "$!\n";
binmode $fh;
my $efsdata;
$fh->read($efsdata, -s $fh);
$fh->close();
my $pr= PageReader->new($efsdata, $savedir);

# todo: dump $pr->{files}
sub page_scan {
    for (my $i=0 ; $i<$pr->{tablesize} ; $i++) {
        pagetree($pr->{ptable}[$i], sprintf("p.%03d", $i));
    }
    for (my $i=0 ; $i<$pr->{tablesize} ; $i++) {
        pagetree($pr->{rtable}[$i], sprintf("r.%03d", $i));
    }
}
sub pagetree {
    my ($pagenr, $desc)= @_;
    if ($pr->pagenrtype($pagenr)==PageReader::P_PAGETABLE) {
        printf("%s  %04x\n", $desc, $pagenr);
    }
    else {
        my $data= $pr->read_page($pagenr);
        my @pages= unpack("V*", $data);
        for (my $i=0 ; $i<@pages ; $i++) {
            pagetree($pages[$i], sprintf("%s.%03d", $desc, $i));
        }
    }
}
sub inode_scan {
    for (my $pagenr=0 ; $pagenr<$pr->{pageTablesStart}*$pr->{pagesPerBlock} ; $pagenr++)
    {
        my $data= $pr->read_page($pagenr);
        if (PageReader::lookslikeinodepage($data)) {
            my $clusnr= $pr->page2cluster($pagenr);
            printf("p_%04x,  c_%04x\n", $pagenr, $clusnr);
            my @inodes= map { substr($data, $_*0x80, 0x80) } 0..15;
            for my $i (0..15) {
                next if $inodes[$i] =~ /^\xff+$/;
                my $inode= PageReader::parseinode($inodes[$i]);
                printf("i_%04x: %06o %2d %04x %8d %2d %3d %08lx %08lx %08lx,%08lx,...\n",
                    $i+16*$clusnr, map({ $inode->{$_} } qw(mode nlink attr size generation clusters mtime ctime)),
                    $inode->{dataptrs}[0], $inode->{dataptrs}[1]);
            }
        }
    }
}