Table extractor tool

[Benjamin Larsson]

Hi, I have meant to release this tool for some time now but I've been
lazy. Anyway it's called elftractor and can extract tables from elf
executables with the info from the symbol tables. To use it just run it
with ./elftractor.pl --analyse "file". A default database file is then
created. This file is a regular textfile that can be edited. After the
database has been edited, just run ./elftractor.pl --generate-tables
"file" to extract the tables from the file. Currently only 1 and 2
dimensional tables can be generated correctly. I've attached one example
db for the indeo4 decoder elf. This file can be found in the all codec
package from mplayerhq.

MvH
Benjamin Larsson

--
"incorrect information" is an oxymoron. Information is, by definition, factual, correct.


#!/usr/bin/perl

#Argument parser

if (@ARGV){
    if ($ARGV[0] eq "--analyse"){
        $demange=0;
        analyse();
    }
    if ($ARGV[0] eq "--analyse-demangle"){
        $demangle=1;
        analyse();
    }
    if ($ARGV[0] eq "--generate-skeleton"){
        generate_skeleton();
    }
    if ($ARGV[0] eq "--generate-tables"){
        generate_tables();
    }
    if ($ARGV[0] eq "--generate-all"){
        generate_tables();
        generate_skeleton();
    }

} else{
    print "Usage:\n";
    print "./elftractor.pl [command] binary\n";
    print "--analyse - analyses and creates a database\n";
    print "--analyse-demangle - analyse and demangle of function names\n";
    print "--generate-skeleton - generates code skeleton from database\n";
    print "--generate-tables - generates datatables from database\n";
    print "--generate-all - generates tables and function skeleton\n";
    exit;
}
exit;

sub generate_skeleton
{
    #parse the input file
    $FILE1 = $ARGV[1];
    $ts = 0;
    $tn = 0;
    open(DATAFILE, "<$FILE1.db") or die "File doesn't exist\n";
    while ($rad = <DATAFILE>)
    {
        if ($rad eq "[functions end]\n") {$ts = 0;}
        if ($ts == 1) {
            chomp($rad);
            @tmpsplit=split /;/,$rad;
            $functions_name[$tn] = $tmpsplit[0];
            $functions_address[$tn] = $tmpsplit[1];
            $functions_size[$tn] = $tmpsplit[2];
            $functions_argument[$tn] = $tmpsplit[3];
            $tn++;
        }
        if ($rad eq "[functions begin]\n") {$ts = 1;}
    }
    #open outputfile
    open(OUTFILE, ">$FILE1.c") or die "can't open $FILE1.c: $!";

    print OUTFILE "#include \"$FILE1.h\"\n\n\n\n";
    for ($i=0 ; $i<$tn; $i++){
        print OUTFILE "static void $functions_name[$i]$functions_argument[$i]\n{\n}\n\n";
    }
    close(OUTFILE);
    print "$tn functions written to $FILE1.c\n";
}

sub generate_tables
{
    #parse the input file
    $FILE1 = $ARGV[1];
    $ts = 0;
    $tn = 0;
    open(DATAFILE, "<$FILE1.db") or die "File doesn't exist\n";
    while ($rad = <DATAFILE>)
    {
        if ($rad eq "[tables end]\n") {$ts = 0;}
        if ($ts == 1) {
            chomp($rad);
            @tmpsplit=split /;/,$rad;
            $tabler_name[$tn] = $tmpsplit[0];
            $tabler_address[$tn] = $tmpsplit[1];
            $tabler_size[$tn] = $tmpsplit[2];
            $tabler_type[$tn] = $tmpsplit[3];
            $tabler_cols[$tn] = $tmpsplit[4];
            $tabler_readonly[$tn] = $tmpsplit[5];
            $tabler_dimensions[$tn] = $tmpsplit[6];
            for ($i=0 ; $i<$tabler_dimensions[$tn] ; $i++){
                $tabler_dsize[$tn][$i] = $tmpsplit[7+$i];
            }
            $tn++;
            #print "$tmpsplit[0] - $tmpsplit[5]\n";
        }
        if ($rad eq "[tables begin]\n") {$ts = 1;}
    }
    close(DATAFILE);

    #get .data and .rodata offsets
    open(DATAFILE, "<$FILE1.db") or die "File doesn't exist\n";
    $ts = 0;
    while ($rad = <DATAFILE>)
    {
        if ($rad eq "[offset end]\n") {$ts = 0;}
        if ($ts == 2) {
            @tmpsplit=split /;/,$rad;
            $doffset = $tmpsplit[1];
            $ts = 3;
        }
        if ($ts == 1) {
            @tmpsplit=split /;/,$rad;
            $drooffset = $tmpsplit[1];
            $ts = 2;
        }
        if ($rad eq "[offset begin]\n") {$ts = 1;}
    }
    close(DATAFILE);

    #open outputfile
    open(OUTFILE, ">$FILE1.h") or die "can't open $FILE1.h: $!";

    #print "$drooffset $doffset\n";
    for ($i=0 ; $i<$tn; $i++){
        #type to unpacktype
        $unpacktype="";
        $delim=0;
        $floatfix=0;
        if ($tabler_type[$i] eq "int8_t") {$unpacktype="c";}
        if ($tabler_type[$i] eq "uint8_t") {$unpacktype="C";}
        if ($tabler_type[$i] eq "int16_t") {$unpacktype="s";}
        if ($tabler_type[$i] eq "uint16_t") {$unpacktype="S";}
        if ($tabler_type[$i] eq "int32_t") {$unpacktype="i";}
        if ($tabler_type[$i] eq "uint32_t") {$unpacktype="I";}
        if ($tabler_type[$i] eq "int64_t") {$unpacktype="l";}
        if ($tabler_type[$i] eq "uint64_t") {$unpacktype="L";}
        if ($tabler_type[$i] eq "float") {$unpacktype="f";$floatfix = 1;}
        if ($tabler_type[$i] eq "double") {$unpacktype="d";$floatfix = 1;}
        if ($tabler_type[$i] eq "hex8_t") {$unpacktype="h";$delim=2;}
        if ($tabler_type[$i] eq "hex16_t") {$unpacktype="h";$delim=4;}
        if ($tabler_type[$i] eq "hex32_t") {$unpacktype="h";$delim=8;}
        if ($tabler_type[$i] eq "hex64_t") {$unpacktype="h";$delim=16;}

        #get right offset
        if ($tabler_readonly[$i]==1){
            $ofs = $drooffset;
        } else {
            $ofs = $doffset;
        }

        #calculate the seek address
        $seekaddress = hex($tabler_address[$i]) - $ofs;

        #access the file for data
        open(BINFILE, $FILE1) or die "can't open $FILE1: $!";
        seek(BINFILE, $seekaddress, 0) or die "seek:$!";
        read(BINFILE, $BUFFER, $tabler_size[$i]);
        close(BINFILE);

        @fields = unpack("$unpacktype*",$BUFFER);

        #divide the hex numbers
        if ($delim > 0) {
            $hexdata = $fields[0];
            $fptr = 0;
            for ($nptr=0;$nptr < (length($hexdata));$nptr = $nptr + $delim) {
                $fields[$fptr] = "\"0x".substr("$hexdata", $nptr, $delim)."\"";
                $fptr++;
            }
            #rename the type hex to uint
            $tabler_type[$i] =~ s/hex/uint/;
        }



        #numbers of elements
        $numelements = $#fields+1;

        #const or not
        $const = "";
        if ($tabler_readonly[$i]==1){
            $const = "const ";
        }

        $tsize = 1;
        $dimstring = "";
        #evaluate the dimensions
        for ($j=0; $j<$tabler_dimensions[$i]-1; $j++){
            $tsize = $tsize*$tabler_dsize[$i][$j];
            $dimstring = $dimstring."\[$tabler_dsize[$i][$j]\]";
        }
        $numelements_last = $numelements/$tsize;
        $dimstring = $dimstring."\[$numelements_last\]";

        print OUTFILE "static $const$tabler_type[$i] $tabler_name[$i]$dimstring = {\n    ";
        if ($tabler_dimensions[$tn]>1) {
            print OUTFILE "{ ";
        }

        $colcounter = 0;
        $elcounter = 0;
        foreach $rad (@fields) {
            for ($j=0; $j<$tabler_dimensions[$i]-1; $j++){
                if (($elcounter%$numelements_last == 0)) {
                    $colcounter = 0;
                    if ($elcounter == 0){
                        print OUTFILE "{";
                    } else {
                        print OUTFILE "    {";
                    }
                }
            }
            $elcounter++;
            if ($colcounter == $tabler_cols[$i]) {
                print OUTFILE "\n    ";
                $colcounter = 0;
            }
            #fix missing .0 for floats
            if ($floatfix==1) {
                if ($rad=~ m/\./) {
                } else {
                    $rad = "$rad.0";
                }
            }
            print OUTFILE "$rad,";
            $colcounter ++;
            for ($j=0; $j<$tabler_dimensions[$i]-1; $j++){
                if ($elcounter%$numelements_last == 0){
                    $colcounter = 0;
                    print OUTFILE "},\n";
                }
            }
        }
        if ($tabler_dimensions[$i]>1) {
            print OUTFILE "};\n\n";
        } else {
            print OUTFILE "\n};\n\n";
        }
        #print "$tabler_name[$i] $tabler_address[$i] $tabler_size[$i] $seekaddress\n @fields\n";
    }
    print "$tn tables written to $FILE1.h.\n";
    close(OUTFILE);
}


sub analyse
{
    my $k;
    $tn = 0;
    $tron = 0;
    $fnum = 0;
    $FILE1 = $ARGV[1];
    print "$FILE1\n";
    # get SYMBOL TABLE
    if ($demangle == 1) {
        @symtable = `objdump -C -tT $FILE1`;
    } else {
        @symtable = `objdump -tT $FILE1`;
    }
    foreach $rad (@symtable) {
        #parse readwrite tables
        if ($rad =~ m/\.data/) {
            #print $rad;
            $address = (substr $`,0,8);
            $rad = $';
            while (($rad =~ s/  / /g) || ($rad =~ s/\t//g)){}
            #print $rad;
            $size = (substr $rad,0,8);
            $name = (substr $rad,9);
            chomp($name);
            $size = hex($size);
            if ($size > 0) {
                #print "$name $size $address\n";
                $tabler_name[$tn] = $name;
                $tabler_size[$tn] = $size;
                $tabler_address[$tn] = $address;
                $tn++;
            }
        }
        #parse readonly tables
        if ($rad =~ m/\.rodata/) {
            #print $rad;
            $address = (substr $`,0,8);
            $rad = $';
            while (($rad =~ s/  / /g) || ($rad =~ s/\t//g)){}
            #print $rad;
            $size = (substr $rad,0,8);
            $name = (substr $rad,9);
            chomp($name);
            $size = hex($size);
            #print "$name $size $address\n";
            if ($size > 0) {
                #print "$name $size $address\n";
                $tablero_name[$tron] = $name;
                $tablero_size[$tron] = $size;
                $tablero_address[$tron] = $address;
                $tron++;
            }
        }
        #parse functions
        if ($rad =~ m/\.text/) {
        $address = (substr $`,0,8);
        #print $rad;
        $rad = $';
        while (($rad =~ s/  / /g) || ($rad =~ s/\t//g)){}
            $argument="(n/a)";
            $size = (substr $rad,0,8);
            $name = (substr $rad,9);
            chomp($name);
            if ($demangle == 1) {
                if($name =~ m/\(/) {
                    $argument = "(".$';
                    $name = $`;
                }
            }
            $size = hex($size);
            #print "$name $argument $size\n";
            if ($size > 0) {
                #print "$name $argument $size\n";
                $functions_name[$fnum] = $name;
                $functions_address[$fnum] = $address;
                $functions_size[$fnum] = $size;
                $functions_argument[$fnum] = $argument;
                $fnum++;
            }
        }
    }

    #get .data and .rodata offsets
    @offsets = `readelf -S $FILE1`;
    foreach $rad (@offsets) {
        if ($rad=~ m/ \.data/) {
            $dataaddress = (substr $rad,41,8);
            $dataoffset = (substr $rad,50,6);
            $doffset = hex($dataaddress) - hex($dataoffset);
        }
        if ($rad=~ m/ \.rodata/) {
            $rodataaddress = (substr $rad,41,8);
            $rodataoffset = (substr $rad,50,6);
            $drooffset = hex($rodataaddress) - hex($rodataoffset);
        }
    }

    #write the database
    open(DB, ">".$FILE1.".db") or die "File doesn't exist\n";
    print DB "# offsets for data tables in non hex format(decimal), the order is fixed\n";
    print DB "[offset begin]\n";
    print DB "ro_offset;$drooffset;\n";
    print DB "rw_offset;$doffset;\n";
    print DB "[offset end]\n";

    print DB "# name(string), address(hex), size(int), type(string), cols(int), readonly(bolean), dimensions(int), dim 1 to n-1 size...(int)\n";
    print DB "[tables begin]\n";
    #write read/write tables
    for ($i=0 ; $i<$tn; $i++){
        print DB "$tabler_name[$i];$tabler_address[$i];$tabler_size[$i];hex8_t;8;0;1;\n";
    }
    #write readonly tables
    for ($i=0 ; $i<$tron; $i++){
        print DB "$tablero_name[$i];$tablero_address[$i];$tablero_size[$i];hex8_t;8;1;1;\n";
    }
    print DB "[tables end]\n";
    #write functions
    print DB "# name(string); address(hex); size(int); arguments(string)\n";
    print DB "[functions begin]\n";
    for ($i=0 ; $i<$fnum; $i++){
        print DB "$functions_name[$i];$functions_address[$i];$functions_size[$i];$functions_argument[$i];\n";
    }
    print DB "[functions end]\n";
    close DB;
    print "Found $tn rw tables, $tron readonly tables and $fnum functions.\n";
    print "Database $FILE1.db written.\n";
}

# offsets for data tables in non hex format(decimal), the order is fixed
[offset begin]
ro_offset;0;
rw_offset;4096;
[offset end]
# name(string), address(hex), size(int), type(string), cols(int), readonly(bolean), dimensions(int), dim 1 to n-1 size...(int)
[tables begin]
ubScan;0002e4c0;1024;uint8_t;8;0;2;16;
MapTbl3;000283e0;1424;uint8_t;8;1;1;
xform_to_scan;0002a860;18;hex8_t;8;1;1;
ClampDitherY_0e;0001d800;256;uint8_t;8;1;1;
MapTbl4;00028980;1424;hex8_t;8;1;1;
CP_ClampDitherY_06;00022740;256;hex8_t;8;1;1;
au16ScaleTables;0002be80;5632;uint16_t;8;1;1;
MapTbl7;00029a60;1424;hex8_t;8;1;1;
ComPicSizes;0002a7e8;56;uint32_t;8;1;1;
au16BaseTables;0002a880;5632;hex16_t;8;1;1;
MapTbl0;00027300;1424;hex8_t;8;1;1;
NullFrmHeader;0002a724;12;uint8_t;8;1;1;
ClampDitherY_02;0001d500;256;hex8_t;8;1;1;
MapTbl2;00027e40;1424;hex8_t;8;1;1;
DitherTable;0001e100;16384;hex32_t;8;1;1;
MapTbl6;000294c0;1424;hex8_t;8;1;1;
MapTbl1;000278a0;1424;hex8_t;8;1;1;
MapTbl5;00028f20;1424;hex8_t;8;1;1;
TruncateV;0001d900;1024;uint32_t;8;1;1;
CP_PalTable;00022280;944;uint8_t;8;1;2;16;
CP_ClampDitherY_0e;00022940;256;hex8_t;8;1;1;
FP_PalTable;0001d140;944;uint8_t;8;1;1;
ClampDitherY_0a;0001d700;256;hex8_t;8;1;1;
CP_ClampDitherY_0a;00022840;256;hex8_t;8;1;1;
CP_ClampDitherY_02;00022640;256;hex8_t;8;1;1;
TileSizeTable;0002a7bc;32;uint16_t;8;1;1;
MapTbl8;0002a000;1424;hex8_t;8;1;1;
TruncateU;0001dd00;1024;uint32_t;8;1;1;
ClampDitherY_06;0001d600;256;hex8_t;8;1;1;
CP_DitherTable;00022a40;16384;hex32_t;8;1;1;
[tables end]
# name(string); address(hex); size(int); arguments(string)
[functions begin]
inv_bits;0001ca60;67;(n/a);
PB2Huff;0001c310;319;(n/a);
transform;00011d50;2560;(n/a);
HiveCreateMutex;00005fd0;12;(n/a);
DecMcRectInterp;0001a9c0;890;(n/a);
BitBuff2Mem;0001c180;174;(n/a);
BitBuffOverWrite;0001bec0;225;(n/a);
DecodeDebugGet;00006d50;12;(n/a);
DecodeResetBrightness;00008670;97;(n/a);
DecodeChangeSaturation;00008580;229;(n/a);
DecodeStartup;00006a40;267;(n/a);
DecodeGetCompressedSize;000067b0;90;(n/a);
DecodeResetContrast;000086e0;97;(n/a);
DecodeUseFixedPalette;00006fb0;232;(n/a);
HiveLocalPtrCheck;00005f00;25;(n/a);
CDecompressBegin;00008100;109;(n/a);
DecodeConstantInit;00006070;327;(n/a);
HiveDecTimer;00006020;39;(n/a);
CDecompress;000070a0;1648;(n/a);
HiveGlobalFreePtr;00005f20;41;(n/a);
DecodeGetDefaultPersData;00006d70;12;(n/a);
make_quant;0000f440;193;(n/a);
GetRVMapTbl;0001c830;131;(n/a);
HiveGlobalPtrCheck;00005f50;25;(n/a);
HiveClosestPaletteIndex;00006060;12;(n/a);
DecodeGetSupportedAlgorithms;00006e40;40;(n/a);
BlockPut;00012870;162;(n/a);
C_YVU9toConfigurablePalette;00016e40;13150;(n/a);
What_The;00005bf0;132;(n/a);
MatCopyFast;0000a540;41;(n/a);
bDecodeThisTile;0001a780;87;(n/a);
BitBuffFlush;0001bfb0;52;(n/a);
BitBuffAlloc;0001bd50;72;(n/a);
HiveGlobalUnlockHandle;00005f80;25;(n/a);
DecodeGetPersData;00006e30;12;(n/a);
tounsigned;0001c2c0;27;(n/a);
readTransTileData;0000ad60;704;(n/a);
dec_transform;00010d30;2459;(n/a);
MatSet;00009fd0;88;(n/a);
HiveEndCriticalSection;00006010;12;(n/a);
HiveGlobalAllocHandle;00005e80;66;(n/a);
DecodeFreePrivateData;000066c0;229;(n/a);
GetHuffmanTbls;0001c5a0;76;(n/a);
MatConvU8;0000a0e0;422;(n/a);
DecodeQuery;00006810;310;(n/a);
HiveLocalFreePtr;00005ed0;41;(n/a);
C_YVU9toActivePalette;00015d60;4308;(n/a);
HiveBeginCriticalSection;00005ff0;25;(n/a);
DecPlaneOpen;00008bb0;182;(n/a);
DecodeImageDimInit;00006e70;66;(n/a);
YVU9_to_RGB24;0000f6c0;4996;(n/a);
BitBuffRead;0001bff0;223;(n/a);
SysFreeFunc;0001cb00;45;(n/a);
HiveFreeMutex;00005fe0;12;(n/a);
readTransBandHdr;0000a810;1350;(n/a);
MatAllocFunc;0000a290;94;(n/a);
DecodeSequenceEnd;00006ee0;12;(n/a);
InitYVU2RGBContribs;0000f550;361;(n/a);
BitBuffByteRead;0001c0d0;171;(n/a);
BitBuffWrite;0001b010;295;(n/a);
MatAdd;0000a3c0;100;(n/a);
BitBuffSize;0001c260;64;(n/a);
ModifyContrastOrSaturation;00008830;114;(n/a);
DecBandOpen;0001a630;228;(n/a);
C_YVU9toCLUT8;00012a00;13150;(n/a);
readPicHdrSt;0000d380;3141;(n/a);
DecodeResetSaturation;00008750;59;(n/a);
DecodeChangeContrast;000083e0;259;(n/a);
DecodeUpdateChroma;000087e0;73;(n/a);
HiveGlobalAllocPtr;00005e30;66;(n/a);
HiveGlobalLockHandle;00005f70;16;(n/a);
DecodeSetPersData;00006f00;12;(n/a);
BlockGetDiff;00012750;286;(n/a);
MatCopyFull;0000a490;172;(n/a);
DecodeIsKeyFrame;00006ec0;32;(n/a);
InitRVMapTbl;0001c950;264;(n/a);
MatAddFull;0000a030;167;(n/a);
MatFreeFunc;0000a2f0;26;(n/a);
make_scan;0000f510;57;(n/a);
DecodeShutdown;00006f10;148;(n/a);
NpMBitBuffWrite;0001be70;72;(n/a);
HuffEncBitBuff;0001b600;1126;(n/a);
BitBuffHist;0001b250;937;(n/a);
MatCksum;0000a360;94;(n/a);
BitBuffFree;0001be20;68;(n/a);
DecodeUpdateLuma;00008790;73;(n/a);
DecodeDebugSet;00006d60;12;(n/a);
InitStaticEncodeTables;0001c450;99;(n/a);
GetRVMapTbls;0001c5f0;208;(n/a);
MatCopy;0000a430;86;(n/a);
DecodeSequenceSetup;00006950;234;(n/a);
DecodeFrame;000061c0;1273;(n/a);
SkipPad2DWord;0001ba70;357;(n/a);
DecBand;0001a1a0;1156;(n/a);
CDecompressEnd;00007710;299;(n/a);
ColorConvert;000088b0;756;(n/a);
tosigned;0001c2a0;23;(n/a);
HuffRead;0001bbe0;360;(n/a);
ComputeDynamicClut;00008ec0;3471;(n/a);
InitQuantTables;0001cb30;410;(n/a);
DecodeSetPaletteConfiguration;00006ef0;12;(n/a);
MatSetFast;00009fa0;44;(n/a);
DecPlaneClose;00008c70;95;(n/a);
DecodeChangeBrightness;000084f0;129;(n/a);
DecodeGetPalette;00006d80;162;(n/a);
DecBandClose;0001a720;88;(n/a);
HiveEncodeProgressFunc;00006050;12;(n/a);
MatSetFull;0000a310;72;(n/a);
PicInfoStAllocPlanes;0000f320;277;(n/a);
HiveLocalAllocPtr;00005de0;66;(n/a);
SysMallocFunc;0001cab0;71;(n/a);
HiveGlobalFreeHandle;00005fa0;41;(n/a);
InitStaticDecodeTables;0001c4c0;223;(n/a);
DecMcRectInterpAvg;0001ad40;706;(n/a);
PicInfoStClose;0000a5a0;624;(n/a);
HaarBands;00009e40;344;(n/a);
GetDecHuffmanTable;0001c6c0;360;(n/a);
HaarInv;00009c50;489;(n/a);
PicInfoStOpen;0000dfd0;4942;(n/a);
DecodeUseThisPalette;00006b50;502;(n/a);
BitBuffSkip2ByteAlign;0001b140;266;(n/a);
BitBuffInit;0001bda0;116;(n/a);
DecPlane;00008cd0;258;(n/a);
SetMatrixRect;0000a570;47;(n/a);
BitBuffByteAlign;0001c230;42;(n/a);
CreateHuffDecTable;0001c8c0;139;(n/a);
BlockGet;00012920;216;(n/a);
[functions end]

[Michael Niedermayer]

Hi

On Tue, Dec 20, 2005 at 07:55:44PM +0000, Benjamin Larsson wrote:
> Hi, I have meant to release this tool for some time now but I've been
> lazy. Anyway it's called elftractor and can extract tables from elf
> executables with the info from the symbol tables. To use it just run it

hmm, that remainds me of my vlc-leech tool which will search for vlc and
scantables bruteforce style, it will find plenty of false positives and is
slow but maybe its usefull for someone

[...]

--
Michael

/*
    Copyright (C) 2004 Michael Niedermayer <michaelni@...>

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

#define CODE_SPACE (1<<31)
#define MIN(a,b) ((a) < (b) ? (a) : (b))

const uint8_t ff_log2_tab[256]={
        0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
        5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
        6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
        6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
        7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

static inline int log2(unsigned int v)
{
    int n;

    n = 0;
    if (v & 0xffff0000) {
        v >>= 16;
        n += 16;
    }
    if (v & 0xff00) {
        v >>= 8;
        n += 8;
    }
    n += ff_log2_tab[v];

    return n;
}

static int read_symbol(uint8_t *b, int size){
    if(size==1)
        return *b;
    else if(size==2)
        return *(uint16_t*)b;
    else
        return *(uint32_t*)b;
}

int main(int argc, char **argv){
    FILE *f;
    int filesize, size, start, step, index, temp, i;
    int size2, start2, step2, index2, table_index;
    int last_start, last_table_size, last_size;
    uint8_t *buffer;
    uint8_t len_table[100000];
    int bits_table[100000];
    int tables_found=0;
   
    int min_code_count=8;
    int max_code_len=31;
   
    f= fopen(argv[1], "r");
    if(f==NULL){
        fprintf(stderr, "cant open\n");
        return -1;
    }
    fseek(f, 0, SEEK_END);
    filesize= ftell(f);
    fseek(f, 0, SEEK_SET);
    buffer= malloc(filesize);
   
    if(1 != fread(buffer, filesize, 1, f)){
        fprintf(stderr, "cant read\n");
        return -1;
    }
   
    // scantables
    for(start=0; start<filesize; start++){
        for(size= 1; size <=4; size+=size){
            for(size2=16; size2<=64; size2+=size2){
                int row_size= size2 <= 16 ? 4 : 8;
                uint8_t tab[64];
                int trivial=1;
                step= size;
                memset(tab, 0, sizeof(tab));
               
                if(filesize - start < size2*step)
                    continue;
                   
                for(table_index= 0; table_index<size2; table_index++){
                    unsigned int x= read_symbol(buffer+start+table_index*step, size);
                    if(x>=size2)
                        break;
                    if(x==0 && table_index!=0 && table_index!=8 && size2 == 16)
                        break;
                    if(x != table_index)
                        trivial=0;
                    tab[x]++;
                    if(tab[x] > 1)
                        break;
                }
                if(table_index<size2 || trivial)
                    continue;
                   
                printf("found possible %dx%d scantable at %X with %2dbit entries\n",
                    row_size, size2 / row_size,
                    start,
                    8*size
                );

                for(table_index= 0; table_index<size2; table_index++){
                    int x= read_symbol(buffer+start+table_index*step, size);

                    printf("%2d ", x);
                    if(table_index % row_size == row_size-1 || table_index+1 == size2)
                        printf("\n");
                }
            }
        }
    }
   
    last_start= last_table_size= last_size=0;
    for(start=0; start<filesize; start++){
        for(size= 1; size <=4; size+=size){
            step= size;
//            for(step=size; step<=2*size; step+=size){ remove and add bit reversed indexing
                int table_size;
                for(table_size=16384; table_size>=16; table_size>>=1){
                    int last_x, run, count;
                    int min_len= 31;
                    int max_len= 1;

                    if(filesize - start < table_size*step)
                        continue;

                    count= 0;
                    run=1;
                    last_x= read_symbol(buffer+start, size);
                    for(table_index= 1; table_index<=table_size; table_index++){
                        int x= table_index<table_size ? read_symbol(buffer+start+table_index*step, size)
                                                      : last_x+1;
                       
                        if(x == last_x){
                            run++;
                        }else{
                            int len;
                            if(run&(run-1))
                                break;
                            if(table_index % run)
                                break;
                               
                            len= (int)log2(table_size/run);
                            len_table[count++]= len;
                            if(len < min_len) min_len= len;
                            if(len > max_len) max_len= len;
                            run=1;
                            last_x= x;
                        }
                    }
                    if(table_index<=table_size)
                        continue;
                       
                    if(count<min_code_count)
                        continue;
                   
                    if(count > table_size/2)
                        continue;
                       
                    if(min_len == max_len) //flc
                        continue;
                   
                    if(1<<max_len < table_size) //table could be 50% smaller
                        continue;
                       
                    last_x= read_symbol(buffer+start, size);
                    for(table_index= 1; table_index<table_size; table_index++){
                        int x= read_symbol(buffer+start+table_index*step, size);
                       
                        if(x != last_x){
                            for(i=0; i<table_index; i++){
                                int y= read_symbol(buffer+start+i*step, size);
                                if(y == x)
                                    break;
                            }
                            if(i<table_index)
                                break;
                        }
                        last_x= x;
                    }
                    if(table_index<table_size)
                        continue;

                    if(last_start == start && last_table_size*last_size >= table_size*size) // same or smaller block with larger element size
                        continue;
               
                printf("found possible vlc table at %X with %4d %2dbit entries (%3d unique), len=%d/%d id=%d\n",
                    start,
                    table_size,
                    8*size,
                    count,
                    min_len, max_len,
                    tables_found
                );

                            for(table_index=0; table_index< count; table_index++){
                                int len= len_table[table_index];
                                printf("%3d ", len);
                                if(table_index % 8 == 7 || table_index+1 == count)
                                    printf("\n");
                            }
                            for(table_index=0; table_index< table_size; table_index++){
                                int x= read_symbol(buffer+start+table_index*step, size);
                                printf("%8X ", x);
                                if(table_index % 8 == 7 || table_index+1 == table_size)
                                    printf("\n");
                            }
                    last_start=start;
                    last_table_size= table_size;
                    last_size= size;
                    break;
                   
                }
        }
    }
   
           
    //vlc
    for(start=0; start<filesize; start++){
        for(size= 1; size <=4; size+=size){
            for(step=size; step<=2*size; step+=size){
                int optimal_count=0;
                int optimal_space, optimal_min_len, optimal_max_len, optimal_table_size, optimal_high_zero[2], optimal_skip_zero, table_index;
                unsigned int code_space=0;
                int count=0;
                int max_len= 1;
                int min_len= max_code_len;
                int high_zero[2]= {1,1};
                int skip_zero=1;
                int stats[32];

                for(index= start; index+size <= filesize; index+= step){
                    unsigned int len= read_symbol(buffer+index, size);
                    table_index= (index-start)/step;
                   
                    len_table[table_index]= len;
                   
                    if(step > size || read_symbol(buffer+index+size, size))
                        skip_zero=0;
                   
                    if(len){
                        if(len > (unsigned)max_code_len)
                            break;

                        code_space += 1<<(31-len);
                        if(code_space > (unsigned)CODE_SPACE)
                            break;

                        if(len > max_len) max_len= len;
                        if(len < min_len) min_len= len;
                       
                        high_zero[ table_index & 1 ]= 0;
                           
                        temp= CODE_SPACE - code_space;
                        count++;
                        if(!(temp & (temp-1))){
                            optimal_count= count;
                            optimal_table_size= table_index+1;
                            optimal_space= temp;
                            optimal_min_len= min_len;
                            optimal_max_len= max_len;
                            optimal_high_zero[0]= high_zero[0];
                            optimal_high_zero[1]= high_zero[1];
                            optimal_skip_zero= skip_zero;
                        }
                    }else if(index == start)
                        break;
                }
                if(optimal_count < min_code_count)
                    continue;
                if((unsigned)optimal_space > ((unsigned)CODE_SPACE)/(unsigned)optimal_count)
                    continue;
//                if((unsigned)optimal_space > 1U<<(31-optimal_max_len)) //only single zero word
//                    continue;
//                if(optimal_space)
//                    continue;
                if(optimal_min_len == optimal_max_len) //constant style 2222
                    continue;
                if(optimal_min_len+1 == optimal_max_len) //split constant style 333322
                    continue;
                if(optimal_high_zero[0] || optimal_high_zero[1] || optimal_skip_zero)
                    continue;
                   
                memset(stats, 0, sizeof(stats));
                for(i=0; i<optimal_table_size; i++){
                    int len= len_table[i];
                    stats[len]++;
                    if(stats[len] > 1 && len > 0 && len < optimal_max_len)
                        break;
                    if(stats[len] > 2 && len==optimal_max_len)
                        break;
                }
                if(i == optimal_table_size && optimal_min_len==1 && optimal_max_len==optimal_count) //monotone style 1234
                    continue;
//                if(i == optimal_table_size && optimal_min_len==1 && optimal_max_len+1==optimal_count) //monotone style 12344
//                    continue;
                   
                tables_found++;
               
                for(start2=0; start2<filesize; start2++){
                    for(size2= 1; size2 <=4; size2+=size2){
                        for(step2=size2; step2<=2*size2; step2+=size2){
                            if(size2*step != size*step2) // same interleave
                                continue;
                            if(step != size && step != step2) //if interleaved then step must be the same
                                continue;

                            if(filesize - start2 < optimal_table_size*step2)
                                continue;

                            for(table_index=0; table_index< optimal_table_size; table_index++){
                                unsigned int bits= read_symbol(buffer+start2+step2*table_index, size2);
                                int len= len_table[table_index];
                   
                                bits_table[table_index]= bits;

                                if(bits >> len)
                                    break;
                                if(optimal_space && bits == 0) //zero code in zeroless table
                                    break;
                            }
                            if(table_index < optimal_table_size)
                                continue;

                            for(table_index=0; table_index< optimal_table_size; table_index++){
                                unsigned int bits= read_symbol(buffer+start2+step2*table_index, size2);
                                int len= len_table[table_index];

                                for(i=0; i< table_index; i++){
                                    unsigned int bits2= read_symbol(buffer+start2+step2*i, size2);
                                    int min_len= MIN(len_table[table_index], len_table[i]);
                                   
                                    if(min_len && bits>>(len - min_len) == bits2>>(len_table[i] - min_len))
                                        break;
                                }
                                if(i<table_index)
                                    break;
                            }
                            if(table_index < optimal_table_size)
                                continue;

                printf("found possible %s vlc table at %X/%X with %3d %2d/%2dbit entries %f%% waste %d-%d len, id=%d\n",
                    optimal_space ? "zeroless" : "optimal",
                    start, start2,
                    optimal_count,
                    8*size, 8*size2,
                    optimal_space*100.0 / (float)((unsigned)CODE_SPACE),
                    optimal_min_len, optimal_max_len,
                    tables_found
                );

                            for(table_index=0; table_index< optimal_table_size; table_index++){
                                int bits= bits_table[table_index];
                                int len= len_table[table_index];
                                printf("%3d ", len);
                                if(table_index % 8 == 7 || table_index+1 == optimal_table_size)
                                    printf("\n");
                            }
                            for(table_index=0; table_index< optimal_table_size; table_index++){
                                int bits= bits_table[table_index];
                                int len= len_table[table_index];
                                printf("%8X ", bits);
                                if(table_index % 8 == 7 || table_index+1 == optimal_table_size)
                                    printf("\n");
                            }
                            printf("\n");
                        }
                    }
                }

            }
        }
    }
}

[Mike Melanson]

Michael Niedermayer wrote:

> Hi
>
> On Tue, Dec 20, 2005 at 07:55:44PM +0000, Benjamin Larsson wrote:
>
>>Hi, I have meant to release this tool for some time now but I've been
>>lazy. Anyway it's called elftractor and can extract tables from elf
>>executables with the info from the symbol tables. To use it just run it
>
>
> hmm, that remainds me of my vlc-leech tool which will search for vlc and
> scantables bruteforce style, it will find plenty of false positives and is
> slow but maybe its usefull for someone

        Sounds like a good topic for a blog post...
--
        -Mike Melanson


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
_______________________________________________
xine-codec-devel mailing list
xine-codec-devel@...
https://lists.sourceforge.net/lists/listinfo/xine-codec-devel