shc.c

最新的spcaview linux视频采集 包含spcaserve和spcacat

/*
 *  shcodec ;) version 1.0.1
 *  Copyright (C) 1998-2002 Alexander Simakov
 *  April 2002
 *
 *  This software may be used freely for any purpose. However, when
 *  distributed, the original source must be clearly stated, and,
 *  when the source code is distributed, the copyright notice must
 *  be retained and any alterations in the code must be clearly marked.
 *  No warranty is given regarding the quality of this software.
 *
 *  internet: http://www.webcenter.ru/~xander
 *  e-mail: [e-mail]
 */

#include "shc.h"


#define KEY(a)       (freq[symb[a]])
#define SWP(a, b)    (t=symb[a], symb[a]=symb[b], symb[b]=t)
#define CMP(a,b,c,d) (a<b ? 0 : (a>b ? 1 : (c<d ? 1 : 0)))

void sh_GetFreq(int *freq, uchar *block, int size)
{
    int i;

    for (i=0; i<SH_MAX_ALPHA; i++) freq[i]=0;
    for (i=0; i<size; i++) freq[block[i]]++;
}

int sh_SortFreq(int *freq, uchar *symb)
{
    int ls[8], hs[8];
    int l, h, m, p, i, j, s, n;
    uchar t;

    /* Mark & count actual symbols */
    for (i=n=0; i<SH_MAX_ALPHA; i++)
    if (freq[i]) symb[n++]=(uchar)i;

    ls[0]=0; hs[0]=n-1;

    for (s=0; s>=0; s--) {

        /* Pop next one */
        l=ls[s]; h=hs[s];

        while (l<h) {

            /* Choose pivot frequency */
            m=(l+h)>>1; p=KEY(m);
            SWP(l, m); i=l+1; j=h;

            /* Partition loop */
            while (1) {
                while (i<=j && KEY(i)<=p) i++;
                while (p<KEY(j)) j--;
                if (i>=j) break;
                SWP(i, j); i++; j--;
            }

            SWP(l, j);

            /* Push largest one */
            if (j-l<=h-j) {
                if (j+1<h) { ls[s]=j+1; hs[s++]=h; }
                h=j-1;
            } else {
                if (j-1>l) { ls[s]=l; hs[s++]=j-1; }
                l=j+1;
            }
        }
    }

    return n;
}

void sh_CalcLen(int *freq, uchar *symb, uchar *len, int n, int maxLen)
{
    int root, leaf, next, avbl, dpth;
    int removed, inserted, dpthins, first, last;

    /* Check for pathological cases */
    if (n==1) {
       for (next=0; next<SH_MAX_ALPHA; next++) len[next]=0;

        len[symb[0]]=1; return;
    }

    if (n==2) {
       for (next=0; next<SH_MAX_ALPHA; next++) len[next]=0;

        len[symb[0]]=len[symb[1]]=1; return;
    }

    freq[symb[0]]+=freq[symb[1]]; root=0; leaf=2;

    /* First pass, left to right, setting parent pointers */
    for (next=1; next<n-1; next++) {

        if (leaf>=n || freq[symb[root]]<freq[symb[leaf]]) {
            freq[symb[next]]=freq[symb[root]];
            freq[symb[root++]]=next;
        } else 
            freq[symb[next]]=freq[symb[leaf++]];

        if (leaf>=n || (root<next && freq[symb[root]]<freq[symb[leaf]])) {
            freq[symb[next]]+=freq[symb[root]];
            freq[symb[root++]]=next+n;
        } else
            freq[symb[next]]+=freq[symb[leaf++]];
    }

    /* Second pass, right to left, count internal nodes to be removed */
    if (maxLen==-1) { removed=0; dpthins=n+2; }
    else {
        first=last=n-3; dpth=1;

        while (dpth<maxLen-1) {

            while ((freq[symb[first]]%n)>last) {
                root=first; first-=last-first+1;
                if (first<0) { first=-1; break; }
            }

            while (root-first>1) {
                if ((freq[symb[(first+root)>>1]]%n)>last)
                root=(first+root)>>1;
                else first=(first+root)>>1;
            }

            last=first; dpth++;
            if (last<0) break;
        }
 
        removed=last+1;

        if ((freq[symb[0]]%n)>=removed) {
            removed=0;
            dpthins=n+2;
        } else {
            for (dpthins=0; (1<<dpthins)<removed; dpthins++);
            dpthins=maxLen-dpthins;
        }
    }

    /* Third pass, right to left, setting leaf depths */
    avbl=2; dpth=1; first=last=n-3;
    next=n-1; inserted=0;

    if (dpthins==1) {
        avbl=4; dpth=2;
        inserted=2;
    }

    while (avbl>0) {
        if (last<removed) first=last+1;
        else {

            while ((freq[symb[first]]%n)>last) {
                root=first; first-=last-first+1;
                if (first<removed) { first=removed-1; break; }
            }

            while (root-first>1) {
                if ((freq[symb[(first+root)>>1]]%n)>last)
                root=(first+root)>>1;
                else first=(first+root)>>1;
            }
   
            first=root;
        }

        avbl-=last-first+1; root=0;

        if (dpth>=dpthins) {
            root=1<<(dpth-dpthins);
            if ((inserted+root)>removed)
            root=removed-inserted;
            inserted+=root; avbl-=root;
        }

        else if (dpth==(dpthins-1)) {
            if (freq[symb[first]]==(last+1)) first++;
            else avbl--; root=1; inserted++;
        }

        while (avbl>0) {
            freq[symb[next--]]=dpth;
            avbl--;
        }

        avbl=(last-first+1+root)<<1;
        dpth++; last=(--first);
    }

    for (next=0; next<SH_MAX_ALPHA; next++)
    len[next]=(uchar)freq[next];

}

void sh_SortLen(uchar *len, uchar *symb, int n)
{
    int ls[8], hs[8];
    int l, h, m, lm, sm, i, j, s;
    uchar t;

    ls[0]=0; hs[0]=n-1;

    for (s=0; s>=0; s--) {

        /* Pop next one */
        l=ls[s]; h=hs[s];

        while (l<h) {

            /* Choose pivot length & symbol */
            m=(l+h)>>1; lm=len[sm=symb[m]];
            SWP(l, m); i=l+1; j=h;

            /* Partition loop */
            while (1) {
                while (i<=j && CMP(len[symb[i]],lm,symb[i],sm)) i++;
                while (CMP(lm,len[symb[j]],sm,symb[j])) j--;
                if (i>=j) break; SWP(i, j); i++; j--;
            }

            SWP(l, j);

            /* Push largest one */
            if (j-l<=h-j) {
                if (j+1<h) { ls[s]=j+1; hs[s++]=h; }
                h=j-1;
            } else {
                if (j-1>l) { ls[s]=l; hs[s++]=j-1; }
                l=j+1;
            }
        }
    }
}

void sh_CalcCode(uchar *len, uchar *symb, uchar *code, int n)
{
    int i, codeval, next, prev;

    for (prev=len[symb[0]], i=codeval=0; i<n; i++, codeval++) {
       next=len[symb[i]]; codeval>>=(prev-next);
       prev=next; code[symb[i]]=codeval;
    }
}

int sh_PackTree(uchar *len, uchar *symb, uchar *aux, uint *buf, int n)
{
    int runlen, maxrun, maxlen, runbits, lenbits, flag, i, j, t;
    int treesize, bufpos, curval, curbits, bits;
    uint bitbuf;

    /* log(maxlen) base 2 */
    t=maxlen=len[symb[0]];
    for (lenbits=0; t>0; t>>=1, lenbits++);

    maxrun=runbits=flag=0;

    /* Max 0-run length */
    if (n<SH_MAX_ALPHA) {
        for (i=t=0; i<SH_MAX_ALPHA; i++)

        /* 0-run detected */
        if (!len[i]) {
            for (j=i; (i<SH_MAX_ALPHA) && (!len[i]); i++);
            maxrun=((i-j)>maxrun ? (i-j) : maxrun);
            aux[t++]=i-j;
        }

        /* log(maxrun) base 2 */
        for (runbits=0, t=maxrun; t>0; t>>=1, runbits++);

        /* 0-run flag, increase lenbits if necessary */
        flag=maxlen+1; if (!(maxlen&(maxlen+1))) lenbits++;
    }

    /* Pack RLE parameters */
    bitbuf=(uint)((((lenbits<<4)|runbits)<<8)|flag);
    bits=16;

    /* Pack tree itself */
    for (treesize=bufpos=i=j=0; i<SH_MAX_ALPHA; i++) {

        curval=len[i];
        curbits=lenbits;

        /* 0-run detected */
        if (!curval) {
            runlen=aux[j++]; i+=runlen-1;
            if (runbits<(runlen-1)*lenbits) {
                curval=((flag<<runbits)|runlen);
                curbits+=runbits;
            } else
                curbits+=(runlen-1)*lenbits;
        }

        /* Pack bits */
        if (curbits<=bits) {
            bitbuf<<=curbits;
            bitbuf|=curval;
            bits-=curbits;
        } else {
            bitbuf<<=bits;
            bitbuf|=(curval>>(curbits-bits));
            buf[bufpos++]=bitbuf;
            bitbuf=curval; 
            bits+=(32-curbits);
            treesize++;
        }
    }

    /* Flush remaining data */
    buf[bufpos]=(bitbuf<<bits);
    return (treesize+1)<<2;
}

int sh_ExpandTree(uchar *len, uchar *symb, uint *buf)
{
    int curval, currun, lenbits, runbits, flag, bits, i, j, n;
    uint bitbuf, lenmask, runmask;

    /* Extract RLE parameters */
    bitbuf=buf[0];
    lenbits=(int)((bitbuf>>28) & 0xf);
    runbits=(int)((bitbuf>>24) & 0xf);
    flag=(int)((bitbuf>>16) & 0xff);

    for (i=0; i<SH_MAX_ALPHA; i++) len[i]=0;
	
    lenmask=(1<<lenbits)-1;
    runmask=(1<<runbits)-1;

    /* Expand tree */
    for (bits=16, i=n=0, j=1; i<SH_MAX_ALPHA; i++) {

        /* Extract value */
        if (lenbits<=bits) {
            curval=(int)((bitbuf>>(bits-lenbits))&lenmask);
            bits-=lenbits;
        } else {
            curval=(int)bitbuf;
            bitbuf=buf[j++];
            curval<<=(lenbits-bits);
            curval|=bitbuf>>(32-lenbits+bits);
            curval&=lenmask;
            bits+=(32-lenbits);
        }

        /* Extract run */
        if (curval!=flag) {
            len[i]=(uchar)curval;
            if (curval) symb[n++]=i; /* curval may be zero */
        } else {
            if (runbits<=bits) {
                currun=(int)((bitbuf>>(bits-runbits))&runmask);
                bits-=runbits;
            } else {
                currun=(int)bitbuf;
                bitbuf=buf[j++];
                currun<<=(runbits-bits);
                currun|=bitbuf>>(32-runbits+bits);
                currun&=runmask;
                bits+=(32-runbits);
            }

            i+=(currun-1);
        }
    }

    return n;
}

void sh_CalcDecode(uchar *len, uchar *symb, uchar *base, uchar *offs, uchar *cache, int n)
{
    int root, leaf, i, j;

    for (root=j=0, i=len[symb[0]]; i>=0; i--) {
        leaf=0;
        while ((len[symb[j]]==i) && (j<n)) { leaf++; j++; }
        base[i]=root; if (leaf) offs[i]=j-leaf;
        root=(root+leaf)>>1;
    }

    for (i=0; i<SH_CACHESIZE; i++) {
        for (j=1; (j<=SH_CACHEBITS) && (i>>(SH_CACHEBITS-j)<base[j]); j++);
        cache[i]=j;
    }
}