Re: Table extractor tool
Michael Niedermayer <[email protected]> Wed, 21 Dec 2005 22:54:21 +0100
| Newsgroups | gmane.comp.video.xine.codec.devel |
|---|---|
| Message-ID | <20051221215421.GF5154@MichaelsNB> |
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
vlc-leech.c
(text/plain, 16 KB)
/*
Copyright (C) 2004 Michael Niedermayer <[email protected]>
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");
}
}
}
}
}
}
}