Lz77 Compression Technique: I Now Know What I'm Doing Wrong!

Discussion in 'Software' started by HarryPotter, Jan 26, 2025.

  1. HarryPotter

    HarryPotter MajorGeek

    Hi! I've been suspecting that my problem with my compression techniques' poor performance was that I was writing way too much information during compression. This information was to tell me what the program was doing at every point in the process. Yesterday evening, I disabled all this information, and now, the techniques are much faster. :) I still want to do faster than how I'm doing faster right now. What else can I do to speed up LZ77 more? I'm using partial Assembler and hash tables and plan to post my LZ77 code later today.
     
  2. HarryPotter

    HarryPotter MajorGeek

    Following is the code for detecting LZ77 blocks:
    Code:
    unsigned GetLZW (int d)
    {
    //LowPos is the earliest address to compare, even though the compare 
    //starts at InPos-1.
    //CurIn is the current pos. in InBuffer during scan.
    //CurIn also temporarily holds maxlen during initialization.
            /*register*/ int LowPos, CurIn;
            int c;
    //d and f store current input in and len. file to compress,
    //respectively for quick access.
    //f then holds the current input word to speed scan by comparing
    //the input to test and skipping misses.
    //e is the tmp. size of test block during find operation.
            //register unsigned d=vz.InPos;
            register unsigned e;
            register unsigned short f;//=TokDo?(d&~0x7FF)-2:vz.InEnd;
        unsigned i, j, k;
        if (!d) return 0;
    //if (!Cl && d>vz.InPos+3) //{putchar ('\a'); Cl=1;}
    //{printf ("\n\aBad input in BR.c: %X, InPos: %X\n", d, vz.InPos); getchar(); }//Cl=1;}
    //Calculate max. compressible block as the lesser of 67 bytes and
    //the rest of the file.
            c=(vz.InEnd>=32*1024?200:35); minlen=2;
            //CurIn=vz.InEnd-d; CurIn=CurIn>c?c:CurIn;
        CurIn=vz.InEnd-d; if (c>CurIn) c=CurIn;
            if (d<1 || c<3) return 0;   //Can't compress if at
                                            //beginning of file or <3
                                            //bytes left.
            maxlen=c;
    //printf ("maxlen=%d\n", maxlen);
    //Calculate lowest test pos. as in a 32k sliding dictionary.
            LowPos=(d<=60000?0:d-60000); //c=vz.InEnd-d; if (maxlen>c) maxlen=c;
    //LowPos=0;
    //if (d==1) printf ("LZW At 0x1, c = %d!\n", c);
    //Set curaddr as address of current input for block scan function
    //ChkBlock().
            //if (c<3) return 0;
            curaddr=&InBuffer[d]; //f=*(unsigned short*)&InBuffer[d];
    //Clear found max. size for best find.
            techLZW.size=0;
    //Read curent word for quick skip of non-matches.
            f=*(unsigned short*)curaddr;
        i=InBuffer[d]+InBuffer[d+1]+InBuffer[d+2]&255;
        if (hash[i][0]==0) return 0;
        for (j=techLZW.size=0; j<126 && hash[i][j]<&InBuffer[d] && hash[i][j]!=0; j++) {
            if (InBuffer[d]!=hash[i][j][0] || InBuffer[d+1]!=hash[i][j][1] || InBuffer[d+2]!=hash[i][j][2]) continue;
            if ((k=ChkBlock(hash[i][j]))>techLZW.size) {
                techLZW.size=k;  techLZW.pos=&InBuffer[d]-hash[i][j]-1;
                if (k>=maxlen) return techLZW.size=maxlen;
            }
        } 
        if (techLZW.size<3) {
            //lz77AddHash (curaddr);
            return 0;
        }
        return techLZW.size;
    }
    and the compare function:
    Code:
    unsigned ChkBlock (unsigned char* pos)
    {
            unsigned i;
            //unsigned maxlen=67;
            //if (maxlen>vz.InEnd-vz.InPos) maxlen=vz.InEnd-vz.InPos;
            //if (vz.InPos==0 /*|| maxlen<3*/) return 0;
        //for (i=0; i<maxlen; i++) if (InBuffer[vz.InPos+i]!=InBuffer[pos+i]) break;
        //for (i=0; i<maxlen; i++) if (curaddr[i]!=InBuffer[pos+i]) break;
            //if (i<3) return 0;
            //return i;
            asm {
    //Init. compare current input [edi] to test [esi].
                    mov     esi,[pos]
                   // add     esi,[pos]
                    //mov     edi,[curaddr]
                    mov    edi,curaddr
    //Clear count ecx to find size of block.
                    xor     ecx,ecx
    //Load max. size of readable block maxlen in edx.
                    mov     edx,maxlen
    lp1:
    //Prepare to compare dwords.
    //>=4 bytes left?
                    cmp     edx,4
    //Skip to bytes compare.
                    jb      lp2
    //Compare dwords.
                    mov     eax,[esi+ecx]
                    cmp     eax,[edi+ecx]
    //If !=, go to compare bytes.
                    jne     lp2
    //Advance and loop.
                    add     ecx,4
                    sub     edx,4
                    ja      lp1
    lp2:
    //Compare bytes.
                    mov     al,[esi+ecx]
    //If !=, len. found.  Exit.
                    cmp     al,[edi+ecx]
                    jne     lp3
    //Advance until end of max. len.
                    inc     ecx
                    dec     edx
                    jnz     lp2
    lp3:
    //Make sure block size >=3.  If not, return 0 for uncompressible.
                    //dec   ecx
                    //mov   edx,2
                    //movzx eax,TokDo
                    //sub   edx,eax
                    cmp     ecx,minlen
                    jae     lp3x
                    xor     ecx,ecx
    lp3x:
                    mov     i,ecx
            } return i;
    }
    
    It's doing very well right now, but I like optimizing. :)
     

MajorGeeks.Com Menu

Downloads All In One Tweaks \ Android \ Anti-Malware \ Anti-Virus \ Appearance \ Backup \ Browsers \ CD\DVD\Blu-Ray \ Covert Ops \ Drive Utilities \ Drivers \ Graphics \ Internet Tools \ Multimedia \ Networking \ Office Tools \ PC Games \ System Tools \ Mac/Apple/Ipad Downloads

Other News: Top Downloads \ News (Tech) \ Off Base (Other Websites News) \ Way Off Base (Offbeat Stories and Pics)

Social: Facebook \ YouTube \ Twitter \ Tumblr \ Pintrest \ RSS Feeds