From dae2250691184ef6d638fc9d3c45b3c24299148b Mon Sep 17 00:00:00 2001
From: kramm <kramm>
Date: Mon, 7 Jan 2002 15:24:09 +0000
Subject: [PATCH] implemented picture cache. still pictures are now much
 smaller. ;)

---
 lib/example/avi2swf.cc |  557 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 412 insertions(+), 145 deletions(-)

diff --git a/lib/example/avi2swf.cc b/lib/example/avi2swf.cc
index a4912f6..d287944 100644
--- a/lib/example/avi2swf.cc
+++ b/lib/example/avi2swf.cc
@@ -18,17 +18,39 @@ extern "C" {
 #include "avifile.h"
 #include "aviplay.h"
 
+/*
+   37   bytes per shape (rectangle)
+   8-12 bytes per placeobject
+   4    bytes per removeobject2
+   696+ bytes per definejpeg2 (576 jpegtables)
+   576  bytes per jpegtables
+   122+ bytes per definejpeg
+
+   blocks*140 = minimal bytes per frames
+   5000/140   = maximal blocks with framerate 5000
+
+   2    bytes per showframe
+*/
+
+int cache_size=38; //in frames
+
 char * filename = 0;
 char * outputfilename = "output.swf";
-unsigned int lastframe = 0xffffffff;
+unsigned int firstframe = 0;
+unsigned int lastframe = 0x7fffffff;
 
-int jpeg_quality = 40;
+int jpeg_quality = 20;
+
+#ifndef ST_DEFINEBITSJPEG
+#define ST_DEFINEBITSJPEG       6 
+#endif
 
 struct options_t options[] =
 {
  {"v","verbose"},
  {"o","output"},
- {"e","end"},
+ {"n","num"},
+ {"s","start"},
  {"V","version"},
  {0,0}
 };
@@ -43,10 +65,14 @@ int args_callback_option(char*name,char*val)
 	outputfilename = val;
 	return 1;
     }
-    else if(!strcmp(name, "e")) {
+    else if(!strcmp(name, "n")) {
 	lastframe = atoi(val);
 	return 1;
     }
+    else if(!strcmp(name, "s")) {
+	firstframe = atoi(val);
+	return 1;
+    }
 }
 int args_callback_longoption(char*name,char*val)
 {
@@ -57,7 +83,8 @@ void args_callback_usage(char*name)
     printf("\nUsage: %s file.swf\n", name);
     printf("\t-h , --help\t\t Print help and exit\n");
     printf("\t-o , --output=filename\t Specify output filename\n"); 
-    printf("\t-e , --end=frame\t\t Last frame to encode\n");
+    printf("\t-n , --num=frames\t\t Number of frames to encode\n");
+    printf("\t-s , --start=frame\t\t First frame to encode\n");
     printf("\t-V , --version\t\t Print program version and exit\n");
     exit(0);
 }
@@ -71,11 +98,345 @@ int args_callback_command(char*name,char*val)
     return 0;
 }
 
+/* id allocation/deallocation */
+char idtab[65536];
+unsigned int idtab_pos=1;
+int get_free_id()
+{
+    while(idtab[idtab_pos] || !idtab_pos)
+	idtab_pos++;
+    idtab[idtab_pos]=1;
+    return idtab_pos;
+}
+void free_id(int id)
+{
+    idtab[id] = 0;
+}
+
+void makeshape(int file, int id, int gfxid, int width, int height)
+{
+    TAG*tag;
+    RGBA rgb;
+    MATRIX m;
+    SHAPE*s;
+    SRECT r;
+    int lines = 0;
+    int ls,fs;
+    tag = swf_InsertTag(NULL, ST_DEFINESHAPE);
+    swf_ShapeNew(&s);
+    rgb.b = rgb.g = rgb.r = 0xff;
+    if(lines)
+	ls = swf_ShapeAddLineStyle(s,20,&rgb);  
+    swf_GetMatrix(NULL,&m);
+    m.sx = 20*65536;
+    m.sy = 20*65536;
+
+    fs = swf_ShapeAddBitmapFillStyle(s,&m,gfxid,0);
+    swf_SetU16(tag,id);   // ID   
+    r.xmin = 0;
+    r.ymin = 0;
+    r.xmax = width*20;
+    r.ymax = height*20;
+    swf_SetRect(tag,&r);
+
+    swf_SetShapeStyles(tag,s);
+    swf_ShapeCountBits(s,NULL,NULL);
+    swf_SetShapeBits(tag,s);
+
+    swf_ShapeSetAll(tag,s,0,0,lines?ls:0,fs,0);
+
+    swf_ShapeSetLine(tag,s,width*20,0);
+    swf_ShapeSetLine(tag,s,0,height*20);
+    swf_ShapeSetLine(tag,s,-width*20,0);
+    swf_ShapeSetLine(tag,s,0,-height*20);
+    swf_ShapeSetEnd(tag);
+    swf_WriteTag(file, tag);
+    swf_DeleteTag(tag);
+    swf_ShapeFree(s);
+}
+
+void setshape(int file,int id,int depth,int x,int y,CXFORM*cx)
+{
+    TAG*tag;
+    MATRIX m;
+    m.sx = 0x10000; m.sy = 0x10000;
+    m.r0 = 0; m.r1 = 0;
+    m.tx = x*20; 
+    m.ty = y*20;
+    if(cx && !((cx->a0!=256)||(cx->r0!=256)||(cx->g0!=256)||(cx->b0!=256)
+		||(cx->a1|cx->r1|cx->g1|cx->b1))) cx = 0;
+    tag = swf_InsertTag(NULL,ST_PLACEOBJECT2);
+      swf_ObjectPlace(tag,id,depth,&m,cx,0);
+    swf_WriteTag(file, tag);
+    swf_DeleteTag(tag);
+}
+
+
+int xblocksize;
+int yblocksize;
+struct GfxBlock {
+//    static int xblocksize;
+//    static int yblocksize;
+    U8*data;
+    int len;
+};
+
+int width=0;
+int height=0;
+
+int xblocks;
+int yblocks;
+
+U8* blockbuffer = 0;
+   
+class GfxBlockCache {
+
+    GfxBlock*list;
+    char*expire; //0=block's free
+    int*ids;
+    int size;
+    int pos;
+    int hits;
+    int misses;
+
+    public:
+
+    GfxBlockCache(int file) 
+    {
+	list=0;
+	size = xblocks*yblocks*cache_size;
+	printf("initializing cache (%d entries)\n", size);
+	list = new GfxBlock[size];
+	expire = new char[size];
+	ids = new int[size];
+	memset(expire,0,size);
+	memset(list,0,sizeof(GfxBlock)*size);
+	memset(ids,0,sizeof(int)*size);
+	pos = 0;
+	hits =0;
+	misses =0;
+    }
+    void insert(GfxBlock*block, int gfxid)
+    {
+	int oldpos = pos;
+	while(++pos!=oldpos)
+	{
+	    if(pos==size) pos=0;
+	    if(!expire[pos])
+		break;
+	}
+	if(pos==oldpos) {
+	    // cache full- don't insert item
+	    return;
+	}
+	if(list[pos].data) {
+	    free(list[pos].data);
+	    list[pos].data = 0;
+	    //TODO: free this in the SWF, also
+	}
+	list[pos].data=(U8*)malloc(block->len);
+	memcpy(list[pos].data,block->data,block->len);
+	list[pos].len = block->len;
+	expire[pos] = cache_size;
+	ids[pos] = gfxid;
+    }
+    int find(GfxBlock*block, CXFORM*cxform)
+    {
+	//TODO: do least square regression here to derive cxform
+	int s;
+	int bestsum=-1;
+	int bestid;
+	float best;
+	for(s=0;s<size;s++)
+	if(expire[s])
+	{
+	    int t = (block->len);
+	    U8*ptr1 = block->data;
+	    U8*ptr2 = list[s].data;
+	    int sum2 = 0;
+	    // notice: we treat r,g,b as equal here.
+	    do {
+		int a = (*ptr1++)-(*ptr2++);
+		sum2 += a*a;
+	    } while(--t);
+	    if(bestsum < 0 || bestsum > sum2) {
+		bestid = s;
+		bestsum = sum2;
+	    }
+	}
+	if(bestsum<0) {
+	    misses++;
+	    return -1;
+	}
+	best = bestsum/block->len;
+
+	if(best > 96.0) {
+	    misses++;
+	    return -1;
+	} 
+	expire[bestid]= cache_size;
+	hits++;
+	cxform->a0 = 256;
+	cxform->r0 = 256;
+	cxform->g0 = 256;
+	cxform->b0 = 256;
+	cxform->a1 = 0;
+	cxform->r1 = 0;
+	cxform->g1 = 0;
+	cxform->b1 = 0;
+	return ids[bestid];
+    }
+    void newframe()
+    {
+	int t;
+	for(t=0;t<size;t++)
+	    if(expire[t])
+		expire[t]--;
+
+    }
+    ~GfxBlockCache()
+    {
+	int t;
+	printf("destroying cache...\n");
+	printf("hits:%d (%02d%%)\n", hits, hits*100/(hits+misses));
+	printf("misses:%d (%02d%%)\n", misses, misses*100/(hits+misses));
+	for(t=0;t<size;t++)
+	    if(expire[t] && list[t].data)
+		free(list[t].data);
+	free(list);
+	free(expire);
+	free(ids);
+    }
+} * cache = 0;
+
+class GfxBlockEncoder {
+    int sizex;
+    int sizey;
+    int posx;
+    int posy;
+    int basedepth;
+    int depth[3];
+    public:
+    void init(int depth, int posx,int posy, int sizex, int sizey) 
+    {
+	this->basedepth = depth;
+	this->posx = posx;
+	this->posy = posy;
+	this->sizex = sizex;
+	this->sizey = sizey;
+	this->depth[0] = this->depth[1] = this->depth[2] = -1;
+    }
+    void clear(int file)
+    {
+	/* clear everything in the block */
+	int t;
+	for(t=0;t<3;t++)
+	if(depth[t]>=0)
+	{
+	    TAG*tag;
+	    tag = swf_InsertTag(NULL, ST_REMOVEOBJECT2);
+	    swf_SetU16(tag, basedepth+t); //depth
+	    swf_WriteTag(file, tag);
+	    swf_DeleteTag(tag);
+	    depth[t] = -1;
+	}
+    }
+    void writeiframe(int file, GfxBlock*block)
+    {
+	clear(file);
+
+	int gfxid = get_free_id();
+	int shapeid = get_free_id();
+
+	//memset(data,0,sizex*sizey*3);
+	TAG*tag = swf_InsertTag(NULL, ST_DEFINEBITS);
+	JPEGBITS * jb = swf_SetJPEGBitsStart(tag,sizex,sizey,jpeg_quality);
+	tag->len = 0; //bad hack
+	swf_SetU16(tag, gfxid);
+	int y;
+	for(y=0;y<sizey;y++)
+	    swf_SetJPEGBitsLine(jb,&block->data[y*sizex*3]);
+	swf_SetJPEGBitsFinish(jb);
+	swf_WriteTag(file, tag);
+	swf_DeleteTag(tag);
+
+	cache->insert(block, shapeid);
+
+	makeshape(file, shapeid, gfxid, sizex, sizey);
+	setshape(file, shapeid, basedepth+1, posx, posy, 0);
+	depth[1] = shapeid;
+    }
+    void writereference(int file, int shapeid, CXFORM*form)
+    {
+	if(depth[1]!=shapeid)
+	{
+	    clear(file);
+	    setshape(file, shapeid, basedepth+1, posx, posy, form);
+	    depth[1] = shapeid;
+	}
+    }
+    void compress(int file, GfxBlock*block)
+    {	
+	CXFORM form;
+	int id = cache->find(block, &form);
+	if(id<0)
+	    writeiframe(file, block);
+	else {
+	    writereference(file, id, &form);
+	}
+    }
+} *blocks = 0;
+
+void initdisplay(int file)
+{
+    if(blockbuffer)
+	free(blockbuffer);
+    if(blocks) {
+	int t;
+	for(t=0;t<xblocks;t++)
+	    blocks[t].clear(file);
+	free(blocks);
+    }
+    if(cache)
+	delete cache;
+    xblocksize = (width/3)&~7;
+    yblocksize = (height/2)&~7;
+    xblocks = width/xblocksize;
+    yblocks = height/yblocksize;
+    printf("%dx%d blocks of size %dx%d\n", xblocks,yblocks, xblocksize, yblocksize);
+    printf("cutting lower %d lines, right %d columns\n", 
+	    height-yblocks*yblocksize, width-xblocks*xblocksize);
+    blocks = new GfxBlockEncoder[xblocks*yblocks];
+    blockbuffer = new U8[xblocksize*yblocksize*4]; //should be 3
+    cache = new GfxBlockCache(file);
+    int t;
+    for(t=0;t<xblocks*yblocks;t++) {
+	blocks[t].init(t*64,
+		       (t%xblocks)*xblocksize,
+		       (t/xblocks)*yblocksize,
+		       xblocksize, yblocksize);
+    }
+
+    TAG*tag = swf_InsertTag(NULL, ST_JPEGTABLES);
+    JPEGBITS * jpeg = swf_SetJPEGBitsStart(tag, xblocksize, yblocksize, jpeg_quality);
+    swf_WriteTag(file, tag);
+    swf_DeleteTag(tag);
+    free(jpeg);
+}
+
+void destroydisplay(int file)
+{
+    delete cache;
+    free(blocks);
+    free(blockbuffer);
+}
+
 SWF swf;
 TAG*tag;
 
 int main (int argc,char ** argv)
-{ int file;
+{ 
+  int file;
   IAviReadFile* player;
   IAviReadStream* astream;
   IAviReadStream* vstream;
@@ -83,9 +444,12 @@ int main (int argc,char ** argv)
   SRECT r;
 
   processargs(argc, argv);
+  lastframe += firstframe;
   if(!filename)
       exit(0);
 
+  memset(idtab, 0, sizeof(idtab));
+
   player = CreateIAviReadFile(filename);    
   player->GetFileHeader(&head);
   printf("fps: %d\n", 1000000/head.dwMicroSecPerFrame);
@@ -99,6 +463,9 @@ int main (int argc,char ** argv)
   vstream = player->GetStream(0, AviStream::Video);
 
   vstream -> StartStreaming();
+
+  width = head.dwWidth;
+  height = head.dwHeight;
   
   file = open(outputfilename,O_WRONLY|O_CREAT|O_TRUNC, 0644);
   
@@ -108,8 +475,8 @@ int main (int argc,char ** argv)
   swf.fileSize = 0x0fffffff;
   r.xmin = 0;
   r.ymin = 0;
-  r.xmax = head.dwWidth*20;
-  r.ymax = head.dwHeight*20;
+  r.xmax = width*20;
+  r.ymax = height*20;
   swf.movieSize = r;
 
   swf_WriteHeader(file, &swf);
@@ -121,15 +488,18 @@ int main (int argc,char ** argv)
   swf_WriteTag(file, tag);
   swf_DeleteTag(tag);
 
-  U8*newdata = (U8*)malloc((head.dwWidth+3) * head.dwHeight * 4);
-
   int frame = 0;
+  initdisplay(file);
 
-  int lastsize = (head.dwWidth+3) * head.dwHeight * 4;
-  U8* lastdata = (U8*)malloc(lastsize);
-  U8* data;
-  memset(lastdata,0, lastsize);
-
+  while(frame<firstframe) {
+    if(vstream->ReadFrame()<0)
+	break;
+    printf("\rskipping frame %d",frame);
+    frame++;
+  }
+  if(firstframe)
+  printf("\n");
+  
   while(1) {
     if(vstream->ReadFrame()<0) {
 	printf("\n");
@@ -139,165 +509,62 @@ int main (int argc,char ** argv)
     fflush(stdout);
     CImage*img = vstream->GetFrame();
     img->ToRGB();
-    data = img->data();
-    int width = img->width();
+    U8*data = img->data();
     int bpp = img->bpp();
-    int width4 = width*4;
-    int height = img->height();
     int x,y;
+    int xx,yy;
     int fs,ls;
     SHAPE*s;
     MATRIX m;
     SRECT r;
     RGBA rgb;
 
-    if(frame!=0) {
-	tag = swf_InsertTag(NULL, ST_REMOVEOBJECT2);
-	swf_SetU16(tag, 1); //depth
-	swf_WriteTag(file, tag);
-	swf_DeleteTag(tag);
+    /* some movies have changing dimensions */
+    if(img->width() != width ||
+       img->height() != height) {
+	printf("\n");
+	width = img->width();
+	height = img->height();
+	initdisplay(file);
     }
 
-    /* todo: dynamically decide whether to generate jpeg/lossless
-       bitmaps, (using transparency to modify the previous 
-       picture), and which jpeg compression depth to use.
-       (btw: Are there video frame transitions which can
-        reasonably be approximated by shapes?)
-     */
-
-    int type = 1;
-    int rel = 0;
-    if(type == 0) {
-	tag = swf_InsertTag(NULL, ST_DEFINEBITSLOSSLESS);
-	swf_SetU16(tag, frame*2);
-	U8*mylastdata = lastdata;
-	for(y=0;y<height;y++) {
-	    U8*nd = &newdata[width4*y];
-	    U8*mydata = img->at(y);
-	    if(!rel)
-	    for(x=0;x<width;x++) {
-		nd[3]=mydata[0];
-		nd[2]=mydata[1];
-		nd[1]=mydata[2];
-		mylastdata[2] = mydata[2];
-		mylastdata[1] = mydata[1];
-		mylastdata[0] = mydata[0];
-		nd+=4;
-		mydata+=3;
-		mylastdata+=3;
-	    }
-	    else
-	    for(x=0;x<width;x++) {
-		int a = mylastdata[3]-data[3];
-		int b = mylastdata[2]-data[2];
-		int c = mylastdata[1]-data[1];
-		if((a*a+b*b+c*c)>64)
-		{
-		    nd[3]=mydata[0];
-		    nd[2]=mydata[1];
-		    nd[1]=mydata[2];
-		    nd[0]=255;
-		} else {
-		    nd[3]=0;
-		    nd[2]=0;
-		    nd[1]=0;
-		    nd[0]=0;
-		}
-		mylastdata[2] = mydata[2];
-		mylastdata[1] = mydata[1];
-		mylastdata[0] = mydata[0];
-		nd+=4;
-		mydata+=3;
-		mylastdata+=3;
+    for(yy=0;yy<yblocks;yy++)
+    for(xx=0;xx<xblocks;xx++) 
+    {
+	int x,y;
+	for(y=0;y<yblocksize;y++) {
+	    U8*mydata = img->at(yy*yblocksize+y);
+	    for(x=0;x<xblocksize;x++) {
+		blockbuffer[(y*xblocksize+x)*3+2] = mydata[(xx*xblocksize+x)*3+0];
+		blockbuffer[(y*xblocksize+x)*3+1] = mydata[(xx*xblocksize+x)*3+1];
+		blockbuffer[(y*xblocksize+x)*3+0] = mydata[(xx*xblocksize+x)*3+2];
 	    }
 	}
-	swf_SetLosslessBits(tag,width,height,newdata,BMF_32BIT);
-	swf_WriteTag(file, tag);
-	swf_DeleteTag(tag);
-    } else 
-    if(type == 1) {
-	tag = swf_InsertTag(NULL, ST_DEFINEBITSJPEG2);
-	swf_SetU16(tag, frame*2);
-	JPEGBITS * jb = swf_SetJPEGBitsStart(tag,width,height,jpeg_quality);
-	U8*mylastdata = lastdata;
-	for(y=0;y<height;y++) {
-	    U8*nd = newdata;
-	    U8*mydata = img->at(y);
-	    for(x=0;x<width;x++) {
-		nd[0] = mydata[2];
-		nd[1] = mydata[1];
-		nd[2] = mydata[0];
-		if(rel) {
-		    nd[0] = (mydata[2]-mylastdata[2])/2+0x80;
-		    nd[1] = (mydata[1]-mylastdata[1])/2+0x80;
-		    nd[2] = (mydata[0]-mylastdata[0])/2+0x80;
-		}
-		mylastdata[2] = mydata[2];
-		mylastdata[1] = mydata[1];
-		mylastdata[0] = mydata[0];
-		nd+=3;
-		mydata+=3;
-		mylastdata+=3;
-	    }
-	    swf_SetJPEGBitsLine(jb,newdata);
-	}
-	swf_SetJPEGBitsFinish(jb);
-	swf_WriteTag(file, tag);
-	swf_DeleteTag(tag);
+	GfxBlock b;
+	b.data = blockbuffer;
+	b.len = xblocksize*yblocksize*3;
+	blocks[yy*xblocks+xx].compress(file, &b);
     }
 
-    tag = swf_InsertTag(NULL, ST_DEFINESHAPE);
-      swf_ShapeNew(&s);
-      rgb.b = rgb.g = rgb.r = 0xff;
-      ls = swf_ShapeAddLineStyle(s,20,&rgb);  
-      swf_GetMatrix(NULL,&m);
-      m.sx = 20*65536;
-      m.sy = 20*65536;
-
-      fs = swf_ShapeAddBitmapFillStyle(s,&m,frame*2,0);
-      swf_SetU16(tag ,frame*2+1);   // ID   
-      r.xmin = 0;
-      r.ymin = 0;
-      r.xmax = width*20;
-      r.ymax = height*20;
-      swf_SetRect(tag,&r);
-
-      swf_SetShapeStyles(tag,s);
-      swf_ShapeCountBits(s,NULL,NULL);
-      swf_SetShapeBits(tag,s);
-
-      swf_ShapeSetAll(tag,s,0,0,ls,fs,0);
-
-      swf_ShapeSetLine(tag,s,width*20,0);
-      swf_ShapeSetLine(tag,s,0,height*20);
-      swf_ShapeSetLine(tag,s,-width*20,0);
-      swf_ShapeSetLine(tag,s,0,-height*20);
-      swf_ShapeSetEnd(tag);
-    swf_WriteTag(file, tag);
-    swf_DeleteTag(tag);
-
-    tag = swf_InsertTag(NULL,ST_PLACEOBJECT2);
-      swf_ObjectPlace(tag,frame*2+1,1,0,0,0);
-    swf_WriteTag(file, tag);
-    swf_DeleteTag(tag);
-
     tag = swf_InsertTag(NULL, ST_SHOWFRAME);
     swf_WriteTag(file, tag);
     swf_DeleteTag(tag);
 
+    cache->newframe();
+
     frame++;
     if(frame == lastframe)
 	break;
   }
-  free(newdata);
   printf("\n");
+  destroydisplay(file);
   
   tag = swf_InsertTag(NULL, ST_END);
   swf_WriteTag(file, tag);
   swf_DeleteTag(tag);
 
   close(file);
-
+  
   return 0;
 }
 
-- 
1.7.10.4