FeLZ32 Tool 0

/*
FELZ32: LZ in terms of 32-bit DWORDs

tag:
  bits  0..15: md, match distance (DWORDs)
  bits 16..22: ml, match length (DWORDs)
  bits 23..29: rl, raw length (DWORDs)
  bits 30..31: al, tag/align

ml!=0:
  md=distance
  ml=length
  mr=raw
  al=align (0=DWORD aligned, others: byte offset)

ml==0, rl==0, al==0:
    md==0: EOB
    md!=0: long run of raw DWORDs
 */

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

#include <time.h>

#ifdef __linux
#include <unistd.h>
#include <fcntl.h>
#include <termios.h>
#endif

#ifdef __EMSCRIPTEN__
#include <emscripten.h>
#include <SDL/SDL.h>
#include <SDL/SDL_mouse.h>
#include <SDL/SDL_keyboard.h>
#endif

#if defined(__linux) || defined(__EMSCRIPTEN__)
#include <sys/time.h>
#endif


#if defined(__x86_64__) || defined(_M_X64)
#ifndef X86_64
#define X86_64
#endif

#ifndef ARCH_64BIT
#define ARCH_64BIT
#endif
#endif

#if defined(__i386__) || defined(_M_IX86)
#ifndef X86
#define X86
#endif
#endif

#if defined(__arm__) || defined(_M_ARM)
#ifndef ARM
#define ARM
#endif
#endif

#ifdef __BIG_ENDIAN__
#define BIGENDIAN
#endif

#ifdef __LITTLE_ENDIAN__
#define LTLENDIAN
#endif

#if defined(X86) || defined(X86_64)
#ifndef LTLENDIAN
#define LTLENDIAN
#endif
#endif


typedef unsigned char byte;
typedef signed char sbyte;
typedef unsigned short u16;
typedef signed short s16;
typedef unsigned int u32;
typedef signed int s32;
#if defined(__linux) && defined(__x86_64__)
typedef unsigned long u64;
typedef signed long s64;
#else
typedef unsigned long long u64;
typedef signed long long s64;
#endif

typedef struct BGBDT_FeLzContext_s BGBDT_FeLzContext;

struct BGBDT_FeLzContext_s {
u32 mark1;

byte use_lvm;       //use multi-level matching (log2)
byte use_lvb;       //enable byte matching

u32 *css;
u32 *cse;
//u32 lzhash[16384];
u32 lzhash[65536];
byte lzhrov[4096];
};

#if defined(X86) || defined(X86_64)

#define felz_getu32(ptr)            (*(u32 *)(ptr))
#define felz_getu32le(ptr)          (*(u32 *)(ptr))
#define felz_setu32le(ptr, val)     (*(u32 *)(ptr)=(val))

#define felz_getu32lea(ptr)         (*(u32 *)(ptr))
#define felz_setu32lea(ptr, val)    (*(u32 *)(ptr)=(val))

#else

u32 bgbdt_felz_getu32(byte *ptr)
{
    u32 v;
#if defined(BIGENDIAN)
    v=ptr[3]|(ptr[2]<<8)|(ptr[1]<<16)|(ptr[0]<<24);
#elif defined(LTLENDIAN)
    v=ptr[0]|(ptr[1]<<8)|(ptr[2]<<16)|(ptr[3]<<24);
#else
    static int tv=1;
    if(*(byte *)(&tv)==1)
        { v=ptr[0]|(ptr[1]<<8)|(ptr[2]<<16)|(ptr[3]<<24); }
    else
        { v=ptr[3]|(ptr[2]<<8)|(ptr[1]<<16)|(ptr[0]<<24); }
#endif
    return(v);
}

u32 bgbdt_felz_getu32le(byte *ptr)
{
    u32 v;
    v=ptr[0]|(ptr[1]<<8)|(ptr[2]<<16)|(ptr[3]<<24);
    return(v);
}

void bgbdt_felz_setu32le(byte *ptr, u32 val)
{   ptr[0]=val;     ptr[1]=val>>8;
    ptr[2]=val>>16; ptr[3]=val>>24;     }

#define felz_getu32(ptr)            bgbdt_felz_getu32((byte *)(ptr))
#define felz_getu32le(ptr)          bgbdt_felz_getu32le((byte *)(ptr))
#define felz_setu32le(ptr, val)     bgbdt_felz_setu32le((byte *)(ptr), (val))

#if defined(LTLENDIAN)
#define felz_getu32lea(ptr)         (*(u32 *)(ptr))
#define felz_setu32lea(ptr, val)    (*(u32 *)(ptr)=(val))
#else
#define felz_getu32lea(ptr)         bgbdt_felz_getu32le((byte *)(ptr))
#define felz_setu32lea(ptr, val)    bgbdt_felz_setu32le((byte *)(ptr), (val))
#endif

#endif

int FRGL_TimeMS()
{
#ifdef _WIN32
    static unsigned int init;
    unsigned int t;

    t=timeGetTime();
    if(!init)init=t;

    return((unsigned int)(t-init));
#else

#ifdef __EMSCRIPTEN__
    struct timeval  tp;
    static int      secbase;

    gettimeofday(&tp, NULL);
    if(!secbase)secbase=tp.tv_sec;
    return(((tp.tv_sec-secbase)*1000)+tp.tv_usec/1000);
#endif

#ifndef linux
    static int init;
    int t;

    t=clock();
    t*=CLOCKS_PER_SEC/1000.0;
//  t=FRGL_TimeMS();

    if(!init)init=t;

    return((unsigned int)(t-init));
#endif
#ifdef linux
    struct timeval  tp;
    static int      secbase;

    gettimeofday(&tp, NULL);
    if(!secbase)secbase=tp.tv_sec;
    return(((tp.tv_sec-secbase)*1000)+tp.tv_usec/1000);
#endif
#endif
}


int BGBDT_FeLz32_LookupMatch(BGBDT_FeLzContext *ctx,
    u32 *cs, u32 *cse, int *rml, int *rmd)
{
    u32 *s, *se, *t, *te, *ct;
    byte *ctb, *tb;
    u32 v0, v, h, h1, o;
    int hr, hm, sd;
    int l, d, al, bl, bd, bal;
    int i, j, k;

    if(ctx->use_lvb)
    {
        v0=*cs;
        h=((v0*65521)>>16)&4095;
        hr=ctx->lzhrov[h];
        h1=h<<ctx->use_lvm;
        sd=1<<ctx->use_lvm;
        hm=sd-1;

        bl=0; bd=0;

#if 1
        for(i=0; i<sd; i++)
        {
            o=ctx->lzhash[h1|((hr+i)&hm)]^v0;
            ct=ctx->css+(o>>2);
            ctb=(byte *)ct;
            al=0;
            if((ct>=cs) || (ct<ctx->css))
                continue;

            s=cs; se=s+126;
            if(cse<se)se=cse;
            tb=ctb;

            while(s<se)
            {
                v=felz_getu32(tb);
                if(*s!=v)
                    break;
                s++; tb+=4;
            }

            l=s-cs;
            d=cs-ct;

            if((l>bl) && (d<65536))
                { bl=l; bd=d; bal=al; }
        }
#endif

//      bl=0; bd=0;
        for(i=0; i<sd; i++)
        {
            o=ctx->lzhash[h1|((hr+i)&hm)]^v0;
            ct=ctx->css+(o>>2);
            ctb=((byte *)ctx->css)+o;
            al=o&3;
            if((ct>=cs) || (ct<ctx->css))
                continue;

            s=cs; se=s+126;
            if(cse<se)se=cse;
            tb=ctb;

            while(s<se)
            {
                v=felz_getu32(tb);
                if(*s!=v)
                    break;
                s++; tb+=4;
            }

            l=s-cs;
            d=cs-ct;

            if((l>bl) && (d<65536))
                { bl=l; bd=d; bal=al; }
        }

        *rml=bl|(bal<<14);
        *rmd=bd;
        return((bl>1) && (bd<65536));
    }

    if(ctx->use_lvm)
    {
        v0=*cs;
        h=((v0*65521)>>16)&4095;
        hr=ctx->lzhrov[h];
        h1=h<<ctx->use_lvm;
        sd=1<<ctx->use_lvm;
        hm=sd-1;

        bl=0; bd=0;
        for(i=0; i<sd; i++)
        {
            o=ctx->lzhash[h1|((hr+i)&hm)]^v0;
            ct=ctx->css+o;
            if((ct>=cs) || (ct<ctx->css))
                continue;

            s=cs; se=s+126;
            if(cse<se)se=cse;
            t=ct;

            while(s<se)
            {
                if(*s!=*t)
                    break;
                s++; t++;
            }

            l=s-cs;
            d=cs-ct;

            if((l>bl) && (d<65536))
                { bl=l; bd=d; }
        }

        *rml=bl;
        *rmd=bd;
        return((bl>1) && (bd<65536));
    }else
    {
        v0=*cs;
        h=((v0*65521)>>16)&4095;

        o=ctx->lzhash[h]^v0;
        ct=ctx->css+o;

        if((ct>=cs) || (ct<ctx->css))
        {
            *rml=0; *rmd=0;
            return(0);
        }

        s=cs; se=s+126;
        if(cse<se)se=cse;
        t=ct;

        while(s<se)
        {
            if(*s!=*t)
                break;
            s++; t++;
        }

        l=s-cs;
        d=cs-ct;
        *rml=l;
        *rmd=d;
        return((l>1) && (d<65536));
    }
}

int BGBDT_FeLz32_UpdateString(BGBDT_FeLzContext *ctx,
    u32 *cs, u32 *cse, int len)
{
    byte *csb;
    u32 v;
    int i, h, h1, hr, hm;

    if(ctx->use_lvb)
    {
        hm=(1<<ctx->use_lvm)-1;

        csb=(byte *)cs;
        i=len*4;
        while(i--)
        {
            v=felz_getu32(csb);
            h=((v*65521)>>16)&4095;
            h1=h<<ctx->use_lvm;

            hr=ctx->lzhrov[h];
            hr=(hr-1)&hm;
            ctx->lzhrov[h]=hr;
            ctx->lzhash[h1|hr]=(csb-((byte *)ctx->css))^v;
            csb++;
        }

        return(0);
    }

    if(ctx->use_lvm)
    {
        hm=(1<<ctx->use_lvm)-1;

        i=len;
        while(i--)
        {
            v=*cs;
            h=((v*65521)>>16)&4095;
            h1=h<<ctx->use_lvm;

            hr=ctx->lzhrov[h];
            hr=(hr-1)&hm;
            ctx->lzhrov[h]=hr;
            ctx->lzhash[h1|hr]=(cs-ctx->css)^v;
            cs++;
        }
    }else
    {
        i=len;
        while(i--)
        {
            v=*cs;
            h=((v*65521)>>16)&4095;
            ctx->lzhash[h]=(cs-ctx->css)^v;
            cs++;
        }
    }
    return(0);
}

int BGBDT_FeLz32_EncodeBufferCtx(BGBDT_FeLzContext *ctx,
    u32 *ibuf, int ibsz, u32 *obuf, int obsz, int lvl)
{
    u32 *cs, *cse, *csrb;
    u32 *ct, *cte;
    u32 tg;
    int ml, md, rl, al;
    int i, j, k;

    switch(lvl)
    {
    case 0:
    case 1:
        ctx->use_lvb=0;
        ctx->use_lvm=0;
        break;
    case 2:
        ctx->use_lvb=0;
        ctx->use_lvm=1;
        break;
    case 3:
        ctx->use_lvb=0;
        ctx->use_lvm=2;
        break;
    case 4:
        ctx->use_lvb=0;
        ctx->use_lvm=3;
        break;
    case 5:
        ctx->use_lvb=0;
        ctx->use_lvm=4;
        break;

    case 6:
        ctx->use_lvb=1;
        ctx->use_lvm=2;
        break;
    case 7:
        ctx->use_lvb=1;
        ctx->use_lvm=3;
        break;
    case 8:
    case 9:
        ctx->use_lvb=1;
        ctx->use_lvm=4;
        break;
    }

//  ctx->use_lvb=0;
//  ctx->use_lvm=0;

//  ctx->use_lvm=4;
//  ctx->use_lvm=2;
//  ctx->use_lvb=1;
//  ctx->use_lvm=0;

    ml=4096<<ctx->use_lvm;

//  for(i=0; i<4096; i++)
//  for(i=0; i<16384; i++)
    for(i=0; i<ml; i++)
    {
//      ctx->lzhash[i]=NULL;
        ctx->lzhash[i]=0;
    }

    for(i=0; i<4096; i++)
        ctx->lzhrov[i]=0;

    ctx->css=ibuf;
    ctx->cse=ibuf+ibsz;

    cs=ibuf; cse=cs+ibsz;
    ct=obuf; cte=ct+obsz;
    csrb=cs;

    while(cs<cse)
    {
        if(BGBDT_FeLz32_LookupMatch(ctx, cs, cse, &ml, &md))
        {
            rl=cs-csrb;
            while(rl>=127)
            {
                if(rl>=65536)
                    rl=65535;
                *ct++=rl;
//              felz_setu32lea(ct, rl);
//              ct++;
                i=rl;
                while(i--)
                    { *ct++=*csrb++; }
                rl=cs-csrb;
            }

//          al=ml>>14;
//          ml&=65535;

            tg=md|(ml<<16)|(rl<<23);
            ml&=16383;
            *ct++=tg;
//          felz_setu32le(ct, tg);
//          ct++;
            i=rl;
            while(i--)
                { *ct++=*csrb++; }
            BGBDT_FeLz32_UpdateString(ctx, cs, cse, ml);
            cs+=ml;
            csrb=cs;
        }else
        {
            BGBDT_FeLz32_UpdateString(ctx, cs, cse, 1);
            cs++;
        }
    }

    rl=cs-csrb;
    while(rl>0)
    {
        if(rl>=65536)
            rl=65535;
        *ct++=rl;
//      felz_setu32lea(ct, rl);
//      ct++;
        i=rl;
        while(i--)
            { *ct++=*csrb++; }
        rl=cs-csrb;
    }

    *ct++=0;

    return(ct-obuf);
}

int BGBDT_FeLz32_EncodeBuffer(
    u32 *ibuf, int ibsz, u32 *obuf, int obsz, int lvl)
{
    BGBDT_FeLzContext tctx;
    return(BGBDT_FeLz32_EncodeBufferCtx(&tctx, ibuf, ibsz, obuf, obsz, lvl));
}

int BGBDT_FeLz32_DecodeBuffer(
    u32 *ibuf, int ibsz, u32 *obuf, int obsz)
{
    u32 *cs, *cse, *cs1;
    u32 *ct, *ct1, *cte;
    byte *cs1b;
    u64 lv;
    u32 tg, v, v0, v1, v2;
    int ml, md, rl, al;
    int i, j, k;

    cs=ibuf; cse=cs+ibsz;
    ct=obuf; cte=ct+obsz;

    while(cs<cse)
    {
        tg=*cs++;
//      tg=felz_getu32lea(cs);
//      cs++;

        ml=(tg>>16)&127;
        md=tg&65535;

        if(ml)
        {
            rl=(tg>>23)&127;
            al=(tg>>30)&3;

            i=rl;

#if defined(X86) || defined(X86_64)
            if(rl)
            {
                cs1=cs;     ct1=ct;
                ct+=rl;     cs+=rl;
                while(ct1<ct)
                {
                    *ct1++=*cs1++; *ct1++=*cs1++;
                }
            }
#else
            while(i--)
                { *ct++=*cs++; }
#endif

            if(al)
            {
                cs1b=((byte *)(ct-md))+al;
                i=ml;
                if(md<2)
                {
#if defined(X86) || defined(X86_64)
                    switch(al)
                    {
                    case 3:
                        v=cs1b[0];
                        v=v|(v<<8);
                        v=v|(v<<16);
                        ct1=ct; ct+=ml;
                        while(ct1<ct)
                            { *ct1++=v; *ct1++=v; }
                        break;
                    case 2:
                        v=cs1b[0]|(cs1b[1]<<8);
                        v=v|(v<<16);
                        while(i--)
                            { *ct++=v; }
                        break;
#if 1
                    case 1:
                        v=cs1b[0]|(cs1b[1]<<8)|(cs1b[2]<<8);
                        v0=v|(v<<24);
                        v1=(v>>8)|(v<<16);
                        v2=(v>>16)|(v<<8);
                        ct1=ct; ct+=ml;
                        while(ct1<ct)
                        {
                            *ct1++=v0;
                            *ct1++=v1;
                            *ct1++=v2;
                        }
                        break;
#endif
                    default:
                        while(i--)
                        {
                            ((byte *)ct)[0]=cs1b[0];
                            ((byte *)ct)[1]=cs1b[1];
                            ((byte *)ct)[2]=cs1b[2];
                            ((byte *)ct)[3]=cs1b[3];
                            cs1b+=4;
                            ct++;
                        }
                        break;
                    }
#else
                    while(i--)
                    {
                        ((byte *)ct)[0]=cs1b[0];
                        ((byte *)ct)[1]=cs1b[1];
                        ((byte *)ct)[2]=cs1b[2];
                        ((byte *)ct)[3]=cs1b[3];
                        cs1b+=4;
                        ct++;
                    }
#endif
                }else
                {
                    while(i--)
                    {
                        j=felz_getu32(cs1b);
                        cs1b+=4;
                        *ct++=j;
                    }
                }
            }else
            {
                cs1=ct-md;
                i=ml;

#if defined(X86) || defined(X86_64)
                if(md>1)
                {
                    ct1=ct;     ct+=ml;
                    while(ct1<ct)
                        { *ct1++=*cs1++; *ct1++=*cs1++; }
                }else
                {
                    v=*cs1;
                    ct1=ct; ct+=ml;
                    while(ct1<ct)
                        { *ct1++=v; *ct1++=v; }
                }
#else
                while(i--)
                    { *ct++=*cs1++; }
#endif
            }
            continue;
        }

        if(!tg)
            break;

        if(!(tg&0xFFFF0000U))
        {
#if defined(X86) || defined(X86_64)
            cs1=cs;     ct1=ct;
            ct+=md;     cs+=md;
            while(ct1<ct)
                { *ct1++=*cs1++; *ct1++=*cs1++; }
#else
            i=md;
            while(i--)
                { *ct++=*cs++; }
#endif
            continue;
        }

//      FRGL_DBGBREAK_SOFT
    }

    return(ct-obuf);
}

byte *loadfile(char *path, int *rsz)
{
    byte *buf;
    FILE *fd;
    int sz, i;

    fd=fopen(path, "rb");
    if(!fd)
        return(NULL);

    fseek(fd, 0, 2);
    sz=ftell(fd);
    fseek(fd, 0, 0);
    buf=malloc(sz);
    i=fread(buf, 1, sz, fd);
    fclose(fd);

    *rsz=sz;
    return(buf);
}

int storefile(char *name, byte *ibuf, int isz)
{
    byte *tbuf;
    FILE *fd;
    int sz;

    fd=fopen(name, "wb");
    if(!fd)
    {
        printf("Fail Open Write %s\n", name);
        return(-1);
    }

    fwrite(ibuf, 1, isz, fd);
    fclose(fd);
    return(0);
}


int help(char *prg)
{
    printf("usage: %s opts* infile outfile\n", prg);
    printf("\t-d Decode\n");
    printf("\t-1 .. -9 Compression Level\n");
    return(0);
}

int main(int argc, char *argv[])
{
    byte *ibuf, *obuf, *tbuf;
    byte *cs, *cse;
    char *ifn, *ofn;
    byte dec, lvl;
    s64 li0;
    double f, g;
    int t0, t1, t2, t3;
    int bd0, bl0, bd1, bl1;
    int bl, bd;
    int sz, csz, dsz, h, rb;
    int i, j, k;

    ifn=NULL; ofn=NULL; dec=0; lvl=1;
    for(i=1; i<argc; i++)
    {
        if(argv[i][0]=='-')
        {
            if(!strcmp(argv[i], "-d"))
                { dec=1; continue; }
            if(!strcmp(argv[i], "-t"))
                { dec=2; continue; }

            if(!strcmp(argv[i], "-1"))
                { lvl=1; continue; }
            if(!strcmp(argv[i], "-2"))
                { lvl=2; continue; }
            if(!strcmp(argv[i], "-3"))
                { lvl=3; continue; }
            if(!strcmp(argv[i], "-4"))
                { lvl=4; continue; }
            if(!strcmp(argv[i], "-5"))
                { lvl=5; continue; }
            if(!strcmp(argv[i], "-6"))
                { lvl=6; continue; }
            if(!strcmp(argv[i], "-7"))
                { lvl=7; continue; }
            if(!strcmp(argv[i], "-8"))
                { lvl=8; continue; }
            if(!strcmp(argv[i], "-9"))
                { lvl=9; continue; }

            continue;
        }
        if(!ifn)
            { ifn=argv[i]; continue; }
        if(!ofn)
            { ofn=argv[i]; continue; }
    }

    if(!ifn || !ofn)
    {
        help(argv[0]);
        return(-1);
    }

    if(dec==0)
    {
        ibuf=loadfile(ifn, &sz);
        obuf=malloc(sz*2);

        i=BGBDT_FeLz32_EncodeBuffer(
            (u32 *)ibuf, (sz+3)/4,
            (u32 *)(obuf+16), (2*sz+3)/4, lvl);
        csz=i*4+16;
        obuf[0]='F';    obuf[1]='e';
        obuf[2]='L';    obuf[3]='Z';
        obuf[4]='3';    obuf[5]='2';
        obuf[6]=1;      obuf[7]=0;
        felz_setu32le(obuf+ 8, csz);
        felz_setu32le(obuf+12, sz);

        printf("Enc %d -> %d (%.2f%%)\n", sz, csz, (100.0*csz)/(sz+1));

        if(ofn)
        {
            storefile(ofn, obuf, csz);
        }

        return(0);
    }

    if(dec==1)
    {
        ibuf=loadfile(ifn, &csz);

        if(memcmp(ibuf, "FeLZ32", 6))
        {
            printf("FeLZ Magic Failed\n");
            return(-1);
        }

        csz=felz_getu32le(ibuf+ 8);
        dsz=felz_getu32le(ibuf+12);
        obuf=malloc(dsz+4096);

        BGBDT_FeLz32_DecodeBuffer(
            (u32 *)(ibuf+16), ((csz-16)+3)/4,
            (u32 *)(obuf), (dsz+3)/4);
        storefile(ofn, obuf, dsz);

        return(0);
    }

    if(dec==2)
    {
        ibuf=loadfile(ifn, &sz);
        obuf=malloc(sz*2);
        tbuf=malloc(sz*2);

        dsz=sz;

        i=BGBDT_FeLz32_EncodeBuffer(
            (u32 *)ibuf, (sz+3)/4,
            (u32 *)(obuf+16), (2*sz+3)/4, lvl);
        csz=i*4+16;
        obuf[0]='F';    obuf[1]='e';
        obuf[2]='L';    obuf[3]='Z';
        obuf[4]='3';    obuf[5]='2';
        obuf[6]=1;      obuf[7]=0;
        felz_setu32le(obuf+ 8, csz);
        felz_setu32le(obuf+12, sz);

        printf("Test %d -> %d (%.2f%%)\n", sz, csz, (100.0*csz)/(sz+1));

        if(ofn)
        {
            storefile(ofn, obuf, csz);
        }

//      printf("A0A\n");

        i=BGBDT_FeLz32_DecodeBuffer(
            (u32 *)(obuf+16), ((csz-16)+3)/4,
            (u32 *)(tbuf), (dsz+3)/4);

//      printf("A0B\n");

        if(i!=((dsz+3)/4))
        {
            printf("Size Mismatch %d -> %d\n", dsz, i*4);
        }

        if(memcmp(ibuf, tbuf, dsz))
        {
            printf("Data Mismatch\n");
            return(-1);
        }

        t0=FRGL_TimeMS();
        t2=t0+10000;
        t1=t0;

//      printf("A1\n");

        li0=0;
        while((t1<t2) && (t1>=t0))
        {
            i=BGBDT_FeLz32_DecodeBuffer(
                (u32 *)(obuf+16), ((csz-16)+3)/4,
                (u32 *)(tbuf), (dsz+3)/4);
            li0+=i;

            f=(t1-t0)/(1000.0);
            g=(4*li0)/(f*1000000.0);
            printf("%.2fs %.2fMB/s\r", f, g);
            t1=FRGL_TimeMS();
        }

//      printf("A2\n");

        printf("\n");

        return(0);
    }
}