/***********************************************************************
 Copyright 2002 Ben Rudiak-Gould.

 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA,
 or visit <http://www.gnu.org/copyleft/gpl.html>.
***********************************************************************/


#include "DVDSubber-encode.h"

#include <string.h>


template<class T> static inline T Min(T a, T b) { return a<b?a:b; }
template<class T> static inline T Max(T a, T b) { return a<b?b:a; }


void PutBigEndian(unsigned char* p, int bytes, unsigned value) {
   for (int i=bytes-1; i>=0; --i) {
      p[i] = value;
      value >>= 8;
   }
}


class Palette {
   signed char map[256];
   unsigned char pal[4];
   int pos;
public:
   Palette() {
      memset(map, (char)-1, 256);
      pos = 4;
   }
   int ColorLookup(int pixel) {
      int entry = map[pixel];
      if (entry < 0) {
         if (pos == 0 || (pos == 1 && map[0] == 0)) {
            throw "no more than four colors at once (including the transparent background)";
         }
         map[pixel] = entry = (pixel==0 ? 0 : --pos);
         pal[entry] = pixel;
      }
      return entry;
   }
   const unsigned char* GetPalette() const { return pal; }
};


// returns length of encoding or 0 if overflow
int EncodeLine(unsigned char* line, int linelen, unsigned char* buffer, int buflen, Palette* palette) {
   bool midbyte = false;
   int old_nibble = 0;
   int bufpos = 0;

   int first_alloc_color=0;
   signed char colormap[256];
   memset(colormap, 0xFF, 256);

   int x = 0;
   while (x < linelen) {
      int pixel = line[x];
      int run = 1;
      while (x+run < linelen && line[x+run] == pixel) {
         ++run;
      }
      if (x+run >= linelen) {
         run = 16384;
      } else if (run > 255) {
         run = 255;
      }
      int nibbles = 1 + (run >= 4) + (run >= 16) + (run >= 64);
      int data = run*4 + palette->ColorLookup(pixel);
      for (int i=nibbles-1; i>=0; --i) {
         int new_nibble = (data>>(i*4)) & 15;
         if (midbyte) {
            if (bufpos >= buflen) return 0;
            buffer[bufpos++] = old_nibble*16 + new_nibble;
         } else {
            old_nibble = new_nibble;
         }
         midbyte = !midbyte;
      }
      x += run;
   }

   if (midbyte) {
      if (bufpos >= buflen) return 0;
      buffer[bufpos++] = old_nibble*16;
   }

   return bufpos;
}


int GetLeftMargin(unsigned char* p, int width) {
	int x;
	for (x = 0; x < width; ++x) {
		if (p[x]) break;
	}
	return x;
}

int GetRightMargin(unsigned char* p, int width) {
	int x;
	for (x = 0; x < width; ++x) {
		if (p[-x]) break;
	}
	return x;
}

int ConvertTime(int t, bool ntsc) {
   return (t * (ntsc ? 3003 : 2500) + 2047) / 2048;
}


void ChoosePageColors(unsigned char* buf, int width, int height, int stride, unsigned char* colors) {
	int num_colors=0;
	unsigned char colormap[256];
	memset(colormap, 0xFF, 256);
	for (int y=0; y<height; ++y) {
		for (int x=0; x<width; ++x) {
			unsigned char c = buf[y*stride+x];
			unsigned char d = colormap[c];
			if (d == 0xFF) {
				if (num_colors == 4) {
					throw "no more than four colors at once (including the transparent background)";
				}
				colors[num_colors] = c;
				d = colormap[c] = num_colors;
				++num_colors;
			}
			buf[y*stride+x] = d;
		}
	}
}


/********************************************************************
********************************************************************/


SubpictureBuf::SubpictureBuf() {
	pos =  4;
	last_dcsqt = 0;
}


const unsigned char* SubpictureBuf::GetPtr() {
	PutBigEndian(buf, 2, pos+1);
	buf[pos] = 255;
	PutBigEndian(buf + last_dcsqt + 2, 2, last_dcsqt);
	return buf;
}


void SubpictureBuf::SubpictureOn(int on_time, unsigned char* screen, int left, int right, int top, int bottom, bool ntsc) {
   --right;
   --bottom;

   while (top <= bottom && GetLeftMargin(screen + top*720 + left, right - left + 1) == right - left + 1) {
      ++top;
   }
   if (top > bottom) return;
   while (GetLeftMargin(screen + bottom*720 + left, right - left + 1) == right - left + 1) {
      --bottom;
   }
   int extra_left = right - left + 1, extra_right = right - left + 1;
   for (int y = top; y <= bottom; ++y) {
      extra_left = Min(extra_left, GetLeftMargin(screen + y*720 + left, right - left + 1));
      extra_right = Min(extra_right, GetRightMargin(screen + y*720 + right, right - left + 1));
   }
   left += extra_left;
   right -= extra_right;

   top &= ~1;
   bottom |= 1;

//   ChoosePageColors(screen + top*720 + left, right-left+1, bottom-top+1, 720, colr);

   Palette palette;
   int field_pointer[2];
   for (int parity=0; parity<=1; ++parity) {
      field_pointer[parity] = pos;
      for (int y=top; y<=bottom+2; ++y) {
         if ((y&1)==parity) {
            // reserve 25 bytes for control information
            int length = EncodeLine(&screen[720*y]+left, right-left+1, buf + pos, subpicture_buf_size - 25 - pos, &palette);
            memset(&screen[720*y]+left, 0, right-left+1);
            if (length==0) {
               throw "overflow!";
            }
            pos += length;
         }
      }
   }

   const unsigned char* colr = palette.GetPalette();

   // Subpicture control information (24 bytes long + extra 0xFF)
   PutBigEndian(buf + last_dcsqt + 2, 2, pos);
   last_dcsqt = pos;
   unsigned char* p = buf + pos;

   // start time
   PutBigEndian(p, 2, ConvertTime(on_time, ntsc));
   // turn on subtitle
   p[4] = 1;
   // colors
   p[5] = 3;
   p[6] = (colr[3]*16)+(colr[2]&15);
   p[7] = (colr[1]*16)+(colr[0]&15);
   // transparencies
   p[8] = 4;
   p[9] = (colr[3]&240)+(colr[2]>>4);
   p[10]= (colr[1]&240)+(colr[0]>>4);
   // screen area
   p[11]= 5;
   PutBigEndian(&p[12], 3, left*4096+right);
   PutBigEndian(&p[15], 3, top*4096+bottom);
   // data pointers
   p[18]= 6;
   PutBigEndian(&p[19], 2, field_pointer[0]);
   PutBigEndian(&p[21], 2, field_pointer[1]);
   // end control sequence
   p[23]= 255;
   pos += 24;
}


void SubpictureBuf::SubpictureOff(int off_time, bool ntsc) {
   if (pos > subpicture_buf_size-7)
      throw "overflow!";

   PutBigEndian(buf + last_dcsqt + 2, 2, pos);
   last_dcsqt = pos;
   unsigned char* p = buf + pos;

   // start time
   PutBigEndian(p, 2, ConvertTime(off_time, ntsc));
   // turn off subtitle
   p[4] = 2;
   // end control sequence
   p[5] = 255;
   pos += 6;
}