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

    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");
                        }
                    }
                }

            }
        }
    }
}