Packed DXTn Encoder

/*
Copyright (C) 2013 by Brendan G Bohannon
Email: cr88192@gmail.com
Copying: http://pastebin.com/iJxtZHm6
 */

/*
DXTn packed images.

Each block tag will be encoded in the form (byte):
0 <block:QWORD>         Literal Block.
1-127                           Single byte block index.
128-191 X                       Two byte block index (16384 blocks).
192-223 XX                      Three byte block index (2097152 blocks).
224-238 I                       LZ/RLE Run (2-16 blocks, Index)
239             LI                      LZ/RLE Run (Length, Index)
240             XXX                     24-Bit Index
241             XXXX            32-Bit Index
242-246                         Literal Blocks (2-6 Blocks)
247             L                       Literal Blocks (L Blocks)
248-255                         Reserved

The block index will indicate how many blocks backwards to look for a matching block (1 will repeat the prior block).

Length/Index values will use the same organization as above, only limited to encoding numeric values.

0-127                           0-127.
128-191 X                       128-16383.
192-223 XX                      16384-2097151.
240             XXX                     24-Bit Index (0-16777215)
241             XXXX            32-Bit Index (0-4294967295)

Note that DXT5 images will be split into 2 block-planes, with the first encoding the alpha component, followed by the plane encoding the RGB components.
*/

byte *BGBBTJ_PackBCn_EmitValue(byte *ct, int val)
{
    if(val<128)
    {
        *ct++=val;
        return(ct);
    }
    if(val<16384)
    {
        *ct++=128+(val>>8);
        *ct++=val;
        return(ct);
    }
    if(val<2097152)
    {
        *ct++=128+(val>>16);
        *ct++=val>>8;
        *ct++=val;
        return(ct);
    }
    if(val<1677216)
    {
        *ct++=240;
        *ct++=val>>16;
        *ct++=val>>8;
        *ct++=val;
        return(ct);
    }
    *ct++=241;
    *ct++=val>>24;  *ct++=val>>16;
    *ct++=val>>8;   *ct++=val;
    return(ct);
}

byte *BGBBTJ_PackBCn_EmitRun(byte *ct, int idx, int len)
{
    if(idx==0)
    {
        if(len<2)
        {
            *ct++=0;
            return(ct);
        }
        if(len<7)
        {
            *ct++=242+(len-2);
            return(ct);
        }

        *ct++=247;
        ct=BGBBTJ_PackBCn_EmitValue(ct, len);
        return(ct);
    }

    if(len<2)
    {
        ct=BGBBTJ_PackBCn_EmitValue(ct, idx);
        return(ct);
    }

    if(len<=16)
    {
        *ct++=224+(len-2);
        ct=BGBBTJ_PackBCn_EmitValue(ct, idx);
        return(ct);
    }

    *ct++=239;
    ct=BGBBTJ_PackBCn_EmitValue(ct, len);
    ct=BGBBTJ_PackBCn_EmitValue(ct, idx);
    return(ct);
}

byte *BGBBTJ_PackBCn_EmitBlockValue(byte *ct, u64 block)
{
    *ct++=block;        *ct++=block>>8;
    *ct++=block>>16;    *ct++=block>>24;
    *ct++=block>>32;    *ct++=block>>40;
    *ct++=block>>48;    *ct++=block>>56;
    return(ct);
}

u64 BGBBTJ_PackBCn_GetBlockValue(byte *cs)
{
    u32 t1, t2;
    u64 tmp;
    t1=cs[0] | (cs[1]<<8) | (cs[2]<<16) | (cs[3]<<24);
    t2=cs[4] | (cs[5]<<8) | (cs[6]<<16) | (cs[7]<<24);
    tmp=t1+(((u64)t2)<<32);
    return(tmp);
}

int BGBBTJ_PackBCn_LookupBlockSpan(
    byte *css, byte *cs, byte *cse, int stride,
    int *ridx, int *rlen, int max)
{
    u64 li, lj, lk;
    int bi, bl, ci, cl;
    byte *csi, *csj, *csk;

    li=BGBBTJ_PackBCn_GetBlockValue(cs);
    csi=cs-stride; bi=0; bl=0;
    while(csi>=css)
    {
        lj=BGBBTJ_PackBCn_GetBlockValue(csi);
        if(li!=lj)
            { csi-=stride; continue; }
        csj=csi+stride;
        csk=cs+stride;
        while(csk<cse)
        {
            lj=BGBBTJ_PackBCn_GetBlockValue(csj);
            lk=BGBBTJ_PackBCn_GetBlockValue(csk);
            if(lj!=lk)break;
            csj+=stride; csk+=stride;
        }

        ci=(cs-csi)/stride;
        cl=(csk-cs)/stride;
        if(cl>bl) { bi=ci; bl=cl; }
        if(bl>=max)break;
        csi-=stride;
    }

    *ridx=bi;
    *rlen=bl;
    return(0);
}

byte *BGBBTJ_PackBCn_EncodeBlockArray(byte *obuf, byte *blks,
    int count, int stride)
{
    byte *cs, *cse, *ct, *cs1;
    u64 li;
    int i, bi, bl, bi1, bl1;

    ct=obuf;
    cs=blks; cse=blks+count*stride;
    while(cs<cse)
    {
        BGBBTJ_PackBCn_LookupBlockSpan(blks, cs, cse, stride,
            &bi, &bl, 65536);

#if 1
        if(bi==0)
        {
            bl=1; cs1=cs+stride;
            while(cs1<cse)
            {
                BGBBTJ_PackBCn_LookupBlockSpan(blks, cs1, cse,
                    stride, &bi1, &bl1, 1);
                if(bi1>0)break;
                bl++;
                cs1=cs+bl*stride;
            }
        }
#endif

        if(bi<1)
        {
            if(bl<2)
            {
                *ct++=0;
                li=BGBBTJ_PackBCn_GetBlockValue(cs);
                ct=BGBBTJ_PackBCn_EmitBlockValue(ct, li);
                cs+=stride;
                continue;
            }
            ct=BGBBTJ_PackBCn_EmitRun(ct, 0, bl);
            for(i=0; i<bl; i++)
            {
                li=BGBBTJ_PackBCn_GetBlockValue(cs);
                ct=BGBBTJ_PackBCn_EmitBlockValue(ct, li);
                cs+=stride;
            }
            continue;
        }
        ct=BGBBTJ_PackBCn_EmitRun(ct, bi, bl);
        cs+=bl*stride;
    }
    return(ct);
}

BGBBTJ_API int BGBBTJ_PackBCn_EncodeBlocksDXT5(
    byte *obuf, byte *blks, int count)
{
    byte *ct;
    ct=BGBBTJ_PackBCn_EncodeBlockArray(obuf, blks, count, 16);
    ct=BGBBTJ_PackBCn_EncodeBlockArray(ct, blks+8, count, 16);
    return(ct-obuf);
}