Сжатие данных без потерь
Author
#include "pure_deflate.h"
#include <string.h>
static const uint16_t lb[29]={3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,51,59,67,83,99,115,131,163,195,227,258};
static const uint8_t le[29]={0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
static const uint16_t db[30]={1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577};
static const uint8_t de[30]={0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
typedef struct { uint8_t *p; size_t n,pos; uint32_t bits; unsigned used; pd_status error; } writer;
static void put(writer *w,unsigned x,unsigned n) {
w->bits|=(uint32_t)x<<w->used; w->used+=n;
while(w->used>=8) {
if(w->pos==w->n) { w->error=PD_OUTPUT_FULL; return; }
w->p[w->pos++]=(uint8_t)w->bits; w->bits>>=8; w->used-=8;
}
}
static unsigned reverse(unsigned x,unsigned n) {
unsigned r=0; while(n--) { r=(r<<1)|(x&1u); x>>=1; } return r;
}
static void symbol(writer *w,unsigned s) {
unsigned code,bits;
if(s<144) { code=48+s; bits=8; }
else if(s<256) { code=400+s-144; bits=9; }
else if(s<280) { code=s-256; bits=7; }
else { code=192+s-280; bits=8; }
put(w,reverse(code,bits),bits);
}
static unsigned hash3(const uint8_t *x,size_t i) {
return (((unsigned)x[i]*251u+x[i+1])*251u+x[i+2])&4095u;
}
static void insert(pd_deflate_workspace *w,const uint8_t *x,size_t n,size_t p) {
if(n-p>=3) { unsigned h=hash3(x,p); w->prev[p&(PD_WINDOW-1)]=w->head[h]; w->head[h]=(uint32_t)p; }
}
size_t pd_deflate_bound(size_t n) {
size_t extra=n/8+(n%8!=0)+2;
return n>SIZE_MAX-extra ? 0 : n+extra;
}
pd_status pd_deflate(const uint8_t *x,size_t n,uint8_t *dst,size_t cap,size_t *written,pd_deflate_workspace *work) {
size_t i=0;
writer w={dst,cap,0,0,0,PD_OK};
if(!written) return PD_ARGUMENT;
*written=0;
if((!x&&n)||(!dst&&cap)||!work||n>=UINT32_MAX) return PD_ARGUMENT;
memset(work,255,sizeof(*work));
put(&w,1,1); put(&w,1,2);
while(i<n && w.error==PD_OK) {
size_t best=0,distance=0;
if(n-i>=3) {
uint32_t p=work->head[hash3(x,i)]; unsigned attempts=0;
size_t limit=n-i<258 ? n-i : 258;
while(p!=UINT32_MAX && p<i && i-p<PD_WINDOW && attempts<32) {
size_t k=0; uint32_t q;
while(k<limit && x[p+k]==x[i+k]) ++k;
if(k>best) { best=k; distance=i-p; }
if(best==limit) break;
q=work->prev[p&(PD_WINDOW-1)];
if(q>=p) break;
p=q; ++attempts;
}
}
if(best>=3) {
unsigned l=0,d=0; size_t j;
while(l<28 && lb[l+1]<=best) ++l;
symbol(&w,257+l); if(w.error) break;
put(&w,(unsigned)(best-lb[l]),le[l]); if(w.error) break;
while(d<29 && db[d+1]<=distance) ++d;
put(&w,reverse(d,5),5); if(w.error) break;
put(&w,(unsigned)(distance-db[d]),de[d]); if(w.error) break;
for(j=0;j<best;++j) insert(work,x,n,i+j);
i+=best;
} else { symbol(&w,x[i]); insert(work,x,n,i); ++i; }
}
if(w.error) return w.error;
symbol(&w,256); if(w.error) return w.error;
if(w.used) { if(w.pos==cap) return PD_OUTPUT_FULL; dst[w.pos++]=(uint8_t)w.bits; }
*written=w.pos; return PD_OK;
}
typedef struct { const uint8_t *p; size_t n,pos; uint32_t bits; unsigned used; pd_status error; } reader;
static unsigned get(reader *r,unsigned n) {
unsigned x;
while(r->used<n) {
if(r->pos==r->n) { r->error=PD_TRUNCATED; return 0; }
r->bits|=(uint32_t)r->p[r->pos++]<<r->used; r->used+=8;
}
x=(unsigned)(r->bits&((UINT32_C(1)<<n)-1)); r->bits>>=n; r->used-=n; return x;
}
static int build(pd_huffman *h,const uint8_t *lengths,unsigned n,int empty,int single) {
unsigned i,offset[16],nonzero=0; int32_t left=1;
memset(h->count,0,sizeof(h->count));
for(i=0;i<n;++i) { if(lengths[i]>15) return 0; ++h->count[lengths[i]]; }
for(i=1;i<=15;++i) { nonzero+=h->count[i]; left=2*left-h->count[i]; if(left<0) return 0; }
if(!nonzero) return empty;
if(left && !(single && nonzero==1 && h->count[1]==1)) return 0;
offset[1]=0;
for(i=1;i<15;++i) offset[i+1]=offset[i]+h->count[i];
for(i=0;i<n;++i) if(lengths[i]) h->symbol[offset[lengths[i]]++]=(uint16_t)i;
return 1;
}
static int decode(reader *r,const pd_huffman *h) {
unsigned len,code=0,first=0,index=0;
for(len=1;len<=15;++len) {
unsigned count=h->count[len];
code=(code<<1)|get(r,1); if(r->error) return -1;
if(code>=first && code-first<count) return h->symbol[index+code-first];
index+=count; first=(first+count)<<1;
}
r->error=PD_DATA; return -1;
}
static int trees(reader *r,pd_inflate_workspace *w,unsigned kind) {
uint8_t *lens=w->lengths; unsigned i,nl,nd,nc,total;
static const uint8_t order[19]={16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
if(kind==1) {
for(i=0;i<288;++i) lens[i]=(uint8_t)(i<144?8:i<256?9:i<280?7:8);
if(!build(&w->lit,lens,288,0,0)) return 0;
memset(lens,5,32); return build(&w->dist,lens,32,0,0);
}
nl=get(r,5)+257; nd=get(r,5)+1; nc=get(r,4)+4;
if(r->error || nl>286) return 0;
memset(lens,0,19);
for(i=0;i<nc;++i) lens[order[i]]=(uint8_t)get(r,3);
if(r->error || !build(&w->code,lens,19,0,0)) return 0;
total=nl+nd; i=0;
while(i<total) {
int s=decode(r,&w->code); unsigned count,value;
if(s<0) return 0;
if(s<16) { lens[i++]=(uint8_t)s; continue; }
if(s==16) { if(!i) return 0; value=lens[i-1]; count=get(r,2)+3; }
else { value=0; count=s==17?get(r,3)+3:get(r,7)+11; }
if(r->error || count>total-i) return 0;
while(count--) lens[i++]=(uint8_t)value;
}
return lens[256] && build(&w->lit,lens,nl,0,1) && build(&w->dist,lens+nl,nd,1,1);
}
pd_status pd_inflate(const uint8_t *src,size_t n,uint8_t *dst,size_t cap,size_t *written,pd_inflate_workspace *work) {
reader r={src,n,0,0,0,PD_OK}; size_t out=0; unsigned final=0;
if(!written) return PD_ARGUMENT;
*written=0;
if((!src&&n)||(!dst&&cap)||!work) return PD_ARGUMENT;
while(!final) {
unsigned kind;
final=get(&r,1); kind=get(&r,2); if(r.error) return r.error;
if(kind==0) {
unsigned len,inv,i;
r.bits=0; r.used=0; len=get(&r,16); inv=get(&r,16);
if(r.error) return r.error;
if((len^inv)!=65535u) return PD_DATA;
if(len>cap-out) return PD_OUTPUT_FULL;
for(i=0;i<len;++i) { unsigned v=get(&r,8); if(r.error) return r.error; dst[out++]=(uint8_t)v; }
} else if(kind==1 || kind==2) {
if(!trees(&r,work,kind)) return r.error?r.error:PD_DATA;
for(;;) {
int s=decode(&r,&work->lit);
if(s<0) return r.error;
if(s==256) break;
if(s<256) { if(out==cap) return PD_OUTPUT_FULL; dst[out++]=(uint8_t)s; }
else {
unsigned len,dist,i,l; int d;
if(s>285) return PD_DATA;
l=(unsigned)s-257; len=lb[l]+get(&r,le[l]);
d=decode(&r,&work->dist); if(d<0) return r.error;
if(d>29) return PD_DATA;
dist=db[d]+get(&r,de[d]); if(r.error) return r.error;
if(dist>out) return PD_DATA;
if(len>cap-out) return PD_OUTPUT_FULL;
for(i=0;i<len;++i) { dst[out]=dst[out-dist]; ++out; }
}
}
} else return PD_DATA;
}
if(r.pos!=n) return PD_DATA;
*written=out; return PD_OK;
}
pd_status pd_shuffle8(const uint8_t *src,uint8_t *dst,size_t n) {
size_t k,j,count=n/8;
if(n%8 || ((!src||!dst)&&n) || (n&&src==dst)) return PD_ARGUMENT;
for(k=0;k<8;++k) for(j=0;j<count;++j) dst[k*count+j]=src[8*j+k];
return PD_OK;
}
pd_status pd_unshuffle8(const uint8_t *src,uint8_t *dst,size_t n) {
size_t k,j,count=n/8;
if(n%8 || ((!src||!dst)&&n) || (n&&src==dst)) return PD_ARGUMENT;
for(k=0;k<8;++k) for(j=0;j<count;++j) dst[8*j+k]=src[k*count+j];
return PD_OK;
}