module yamalib.util.clzss;

private import std.math;

/**	
	LZSSによる圧縮ルーチン
	☆　参考文献
	 奥村晴彦著『C言語による最新アルゴリズム事典』／技術評論社
*/
class CLZSS {
	
	bool decode(ubyte* lpSrc, ubyte* lpDst, uint dwSize, bool bDst=true) {

		if (dwSize==0) return false;	//	なんじゃこりゃ:p
	
		ubyte* lpDs;
		if (bDst) {	//	こちらで確保するのか？そうでなければ初期化されていると仮定するぞ
			lpDst = cast(ubyte*) new ubyte[dwSize];	//	展開先を確保する。
		}
		lpDs  = lpDst;
	
		int i, j, k, r, c;
		r = LZSS_RING_BUFFER - LZSS_LONGEST_MATCH;
	
		uint dwFlags = 0;
	
		for(int ii; ii < m_szText.length; ++ii) {
			m_szText[ii] = 0;
		}

		for ( ; ; ) {
			if (((dwFlags >>= 1) & 256) == 0) {
				c = *(lpSrc++);
				dwFlags = c | 0xff00;
			}
			if (dwFlags & 1) {
				c = *(lpSrc++);
				*(lpDs++) = cast(ubyte) c;
				if (--dwSize == 0) return 0;
				m_szText[r++] = cast(ubyte) c;	r &= (LZSS_RING_BUFFER - 1);
			} else {
				i = *(lpSrc++); j = *(lpSrc++);
				i |= ((j & 0xf0) << 4);	 j = (j & 0x0f) + 2;
				for (k = 0; k <= j; k++) {
					c = m_szText[(i + k) & (LZSS_RING_BUFFER - 1)];
					*(lpDs++) = cast(ubyte) c;
					if (--dwSize == 0) return 0;
					m_szText[r++] = cast(ubyte) c;	r &= (LZSS_RING_BUFFER - 1);
				}
			}
		}
		
		return true;
	}
	
	bool encode(byte* lpSrc, byte* lpDst, uint dwSize, inout uint dwDstSize, bool bDst=true) {
		int i, c, len, r, s, lastmatchlen, codeptr;
		byte[17] code;
		byte mask;
	
		if (dwSize <= 16) {
		//	サイズが小さいなら、圧縮できんぞよ＾＾；
			return 1;
		}
	
		uint dwSize2 = dwSize - 8; // これを上回るならば圧縮する価値が無い
	
	     /* 木を初期化 */
		init_tree(); 

		code[0] = 0;  
		codeptr = mask = 1;
		s = 0;	
		r = LZSS_RING_BUFFER - LZSS_LONGEST_MATCH;

		for (i = s; i < r; i++) { 
			m_szText[i] = 0;  /* バッファを初期化 */
		}

		for (len = 0; len < LZSS_LONGEST_MATCH ; len++) {
			c = *(lpSrc++);

			if (--dwSize <= 0) 
				break;

			m_szText[r + len] = cast(ubyte) c;
		}

		if (len == 0) 
			return false;

		for (i = 1; i <= LZSS_LONGEST_MATCH; i++) {
			insert_node(r - i);
		}
		insert_node(r);

		dwDstSize = 0;

		byte* lpDs;
		if (bDst) {
			lpDst = cast(byte*) new byte[dwSize2];	//	とりあえず、これだけ確保して足りんかったらやめ:p
			lpDs = lpDst;
		}
		
		do {
			if (m_matchlen > len) 
				m_matchlen = len;
				
			if (m_matchlen < 3) {
				m_matchlen = 1;	 
				code[0] |= mask;	 
				code[codeptr++] = cast(byte) m_szText[r];
			} else {
				code[codeptr++] = cast(byte) m_matchpos;
				code[codeptr++] = cast(byte) (((m_matchpos >> 4) & 0xf0) | (m_matchlen - 3));
			}
			
			if ( (mask <<= 1) == 0 ) {
				dwDstSize += codeptr;
				if (dwSize2 <= dwDstSize) goto ErrorEnd;	//	展開先バッファ溢れ:p

				for (i = 0; i < codeptr; i++) {
					if (bDst) 
						*(lpDs++) = code[i];
				}
				code[0] = 0;  
				codeptr = mask = 1;
			}
			
			lastmatchlen = m_matchlen;
			for (i = 0; i < lastmatchlen; i++) {
				if (dwSize == 0) break;
				dwSize--;
				c = *(lpSrc++);
				delete_node(s);	 
				m_szText[s] = cast(ubyte) c;
				if (s < LZSS_LONGEST_MATCH - 1) 
					m_szText[s + LZSS_RING_BUFFER] = cast(ubyte) c;
				s = (s + 1) & (LZSS_RING_BUFFER - 1);	
				r = (r + 1) & (LZSS_RING_BUFFER - 1);
				insert_node(r);
			}
			
			while (i++ < lastmatchlen) {
				delete_node(s);
				s = (s + 1) & (LZSS_RING_BUFFER - 1);	
				r = (r + 1) & (LZSS_RING_BUFFER - 1);
				if (--len) 
					insert_node(r);
			}
		} while (len > 0);
		
		if (codeptr > 1) {
			dwDstSize += codeptr;
			//	展開先バッファ溢れ:p
			if (!(dwSize2 <= dwDstSize)) {
				for (i = 0; i < codeptr; i++) {
					if (bDst) 
						*(lpDs++) = code[i];
				}
			}
		}
	
	ErrorEnd:;
		//	圧縮比が悪ければ圧縮を放棄
		if (dwSize2 <= dwDstSize){
			if (bDst) 
				lpDst = null;
			return false;
		}

		return true;
	}
	
private:

	///	木の初期化
	void init_tree() {
		int i;
	
		for (i = LZSS_RING_BUFFER + 1; i <= LZSS_RING_BUFFER + 256; i++) m_rson[i] = NIL;
		for (i = 0; i < LZSS_RING_BUFFER; i++) m_dad[i] = NIL;
	}

	///	節 r を木に挿入	
	void insert_node(int r) {
		int i, p, cmp;
		ubyte* key;
	
		cmp = 1;  key = &m_szText[r];  p = LZSS_RING_BUFFER + 1 + key[0];
		m_rson[r] = m_lson[r] = NIL;  m_matchlen = 0;
		for ( ; ; ) {
			if (cmp >= 0) {
				if (m_rson[p] != NIL) p = m_rson[p];
				else {	m_rson[p] = r;	m_dad[r] = p;  return;	}
			} else {
				if (m_lson[p] != NIL) p = m_lson[p];
				else {	m_lson[p] = r;	m_dad[r] = p;  return;	}
			}
			for (i = 1; i < LZSS_LONGEST_MATCH; i++)
				if ((cmp = key[i] - m_szText[p + i]) != 0)	break;
			if (i > m_matchlen) {
				m_matchpos = p;
				if ((m_matchlen = i) >= LZSS_LONGEST_MATCH)	 break;
			}
		}
		m_dad[r] = m_dad[p];   m_lson[r] = m_lson[p];  m_rson[r] = m_rson[p];
		m_dad[m_lson[p]] = r;  m_dad[m_rson[p]] = r;
		if (m_rson[m_dad[p]] == p) m_rson[m_dad[p]] = r;
		else					   m_lson[m_dad[p]] = r;
		m_dad[p] = NIL;	 /* p を外す */
	}

	///	節 p を木から消す
	void delete_node(int p) {
		int	 q;
	
		if (m_dad[p]  == NIL) return;  /* 見つからない */
		if (m_rson[p] == NIL) q = m_lson[p];
		else if (m_lson[p] == NIL) q = m_rson[p];
		else {
			q = m_lson[p];
			if (m_rson[q] != NIL) {
				do {  q = m_rson[q];  } while (m_rson[q] != NIL);
				m_rson[m_dad[q]] = m_lson[q];  m_dad[m_lson[q]] = m_dad[q];
				m_lson[q] = m_lson[p];	m_dad[m_lson[p]] = q;
			}
			m_rson[q] = m_rson[p];	m_dad[m_rson[p]] = q;
		}
		m_dad[q] = m_dad[p];
		if (m_rson[m_dad[p]] == p)	m_rson[m_dad[p]] = q;
		else						m_lson[m_dad[p]] = q;
		m_dad[p] = NIL;
	}	
	
	
private:
	static const uint LZSS_RING_BUFFER = 4096;	// 環状バッファサイズ
	static const uint LZSS_LONGEST_MATCH = 18;	// 最長一致帳
	static const uint NIL = LZSS_RING_BUFFER;	// 木の末端
	
	//	出力バイト数カウンタ
	uint	m_dwOutCount;

	// テキスト用バッファ
	ubyte	m_szText[LZSS_RING_BUFFER+LZSS_LONGEST_MATCH-1];

	//	木
	int		m_dad[LZSS_RING_BUFFER+1];
	int		m_lson[LZSS_RING_BUFFER+1];
	int		m_rson[LZSS_RING_BUFFER+257];

	int		m_matchpos; 
	int		m_matchlen;	 /* 最長一致位置, 一致長 */	
}