/*	
 *	cliptlz.c
 *
 *	簡易LZ圧縮
 *
 *	CLiP - Common Library for P/ECE
 *	Copyright (C) 2001-2013 Naoyuki Sawa
 *
 *	* Sun Feb 17 22:17:30 JST 2008 Naoyuki Sawa
 *	- 1st リリース。
 *	* Mon Mar 02 21:48:23 JST 2009 Naoyuki Sawa
 *	- TinyLZc構造体、TinyLZc_init()関数、TinyLZc_put()関数を追加しました。
 *	- TinyLZ_compress()関数を再実装し、P/ECEコンパイル時も有効にしました。
 *	* Thu Apr 29 16:10:02 JST 2010 Naoyuki Sawa
 *	- TinyLZ_uncompress()をASM化しました。
 *	* Sun Sep 15 18:50:08 JST 2013 Naoyuki Sawa
 *	- TinyLZ_uncompress()のASM版を修正しました。
 *	  これまで、バッファサイズ終端の1バイトが格納されないという、バグがありました。
 *	  ＜例＞
 *		TinyLZ_uncompress(dst, 256, src, src_len);
 *		//⇒展開データが256バイト以上有っても、dst[255]が格納されていなかった。
 *	  今回修正し、バッファサイズ終端の1バイトも、正しく格納されるようになりました。
 */
#include "clip.h"

/****************************************************************************
 *	展開
 ****************************************************************************/

#ifndef PIECE
void
TinyLZ_init(TinyLZ* tlz, const void* p)
{
	tlz->p = p;
	memset(&tlz->len_pos, 0, sizeof(TinyLZ) - sizeof tlz->p);
}
#else /*PIECE*/
void TinyLZ_init(TinyLZ* tlz, const void* p);
asm("
	.code
	.align	1
	.global	TinyLZ_init
TinyLZ_init:
	;// %r12 := tlz
	;// %r13 := p
	ld.w	[%r12]+, %r13		; tlz->p = p
	ld.w	%r13, 0			; memset(&tlz->len_pos, 0, sizeof(TinyLZ) - sizeof tlz->p)
	xjp.d	memset
	ld.w	%r14, 16		;						*delay*
");
#endif /*PIECE*/

#ifndef PIECE
int
TinyLZ_get(TinyLZ* tlz)
{
	const unsigned char* p = tlz->p;
	int len_pos = tlz->len_pos;
	//
	int c;

	if((len_pos -= 16) < 0) {
		len_pos = *p++;
	}
	if(len_pos & 15) {
		c = tlz->dic[15 - (len_pos & 15)];
	} else {
		c = *p++;
	}
	tlz->p = p;
	tlz->len_pos = len_pos;
	memcpy(&tlz->dic[0], &tlz->dic[1], 14); /* 前方コピーなので、memmove()でなくて大丈夫 */
	tlz->dic[14] = c;

	return c;
}
#else /*PIECE*/
int TinyLZ_get(TinyLZ* tlz);
asm("
	.code
	.align	1
	.global	TinyLZ_get
TinyLZ_get:
	pushn	%r0
	ld.w	%r4, [%r12]+		; %r4  := p = tlz->p
	ld.ub	%r5, [%r12]+		; %r5  := len_pos = tlz->len_pos
	;// %r4  := p
	;// %r5  := len_pos
	;// %r12 := &tlz->dic[0]
	sub	%r5, 16			; if((len_pos -= 16) < 0)
	jrge.d	3
	 ld.w	%r13, 1			; %r13 := 1					*delay*
	 ld.ub	%r5, [%r4]+		;   %r5  := len_pos = *p++
	;// %r4  := p
	;// %r5  := len_pos
	;// %r12 := &tlz->dic[0]
	;// %r13 := 1
	xand	%r9, %r5, 15		; %r9  := len_pos & 15
	jreq.d	6			; if(len_pos & 15) ---------------------------+
	 ld.w	%r14, 14		; %r14 := 14                                  |	*delay*
	 xor	%r9, 15			;   %r9  := 15 - (len_pos & 15)               |
	 add	%r9, %r12		;   %r9  := &tlz->dic[15 - (len_pos & 15)]    |
	 ld.ub	%r0, [%r9]		;   %r0  := c = tlz->dic[15 - (len_pos & 15)] |
	 jp.d	3			; else                                        |
	  sub	%r12, 5			; %r12 := tlz <-------------------------------+	*delay*
	  ld.ub	%r0, [%r4]+		;   %r0  := c = *p++
	;// %r0  := c
	;// %r4  := p
	;// %r5  := len_pos
	;// %r12 := tlz
	;// %r13 := 1
	;// %r14 := 14
	ld.w	[%r12]+, %r4		; tlz->p = p
	ld.b	[%r12]+, %r5		; tlz->len = len_pos
	;// %r0  := c
	;// %r12 := &tlz->dic[0]
	;// %r13 := 1
	;// %r14 := 14
	xcall.d	memcpy			; memcpy(&tlz->dic[0], &tlz->dic[1], 14)
	add	%r13, %r12		; %r13 := &tlz->dic[1]				*delay*
	;// %r0  := c
	;// %r10 := &tlz->dic[0]
	xld.b	[%r10+14], %r0		; tlz->dic[14] = c
	ld.w	%r10, %r0		; return c
	popn	%r0
	ret
");
#endif /*PIECE*/

#ifndef PIECE
int
TinyLZ_uncompress(void* _dst, int dst_max, const void* _src, int src_len)
{
	const unsigned char* src = _src;
	      unsigned char* dst = _dst;
	int dst_len = 0;
	//
	TinyLZ tlz;
	int c;

	TinyLZ_init(&tlz, src);
	src += src_len;
	while((tlz.p < src) || (tlz.len_pos > 15)) {
		c = TinyLZ_get(&tlz);
		if(dst_len++ < dst_max) {
			*dst++ = c;
		}
	}

	return dst_len;
}
#else /*PIECE*/
int TinyLZ_uncompress(void* _dst, int dst_max, const void* _src, int src_len);
asm("
		.code
		.align		1
		.global		TinyLZ_uncompress
TinyLZ_uncompress:
		;// %r12 = dst
		;// %r13 = dst_max
		;// %r14 = src
		;// %r15 = src_len
		pushn		%r3
		ld.w		%r0, %r12			;// %r0  := dst
		ld.w		%r1, %r13			;// %r1  := dst_max
		ld.w		%r2, %r14			;// %r2  :=           src
		add		%r2, %r15			;// %r2  := src_end = src + src_len
		xsub		%sp, %sp, 20			;// %sp  := tlz
		;//
		ld.w		%r12, %sp			;// %r12 :=     tlz
		xcall.d		TinyLZ_init			;// TinyLZ_init(tlz, src)
		ld.w		%r13, %r14			;// %r13 :=          src		*delay*
		;//
		jp.d		TinyLZ_uncompress_NEXT
		ld.w		%r3, 0				;// %r3  := dst_len = 0			*delay*
		;//---------------------------------------------;//
		;// %r0  := dst
		;// %r1  := dst_max
		;// %r2  := src_end
		;// %r3  := dst_len
		;// %sp  := tlz
TinyLZ_uncompress_LOOP:
		ld.w		%r12, %sp			;// %r12 :=                tlz
		xcall.d		TinyLZ_get			;// %r10 := c = TinyLZ_get(tlz)
		add		%r3, 1				;// %r13 := dst_len++			*delay*
		;//
		cmp		%r3, %r1			;// if(dst_len++ < dst_max)
	;//{{2013/09/15修正:C言語の後置演算子と違って、dst_lenは既に+1している。従って、(dst_len==dst_max)の場合も、まだバッファ内である。
	;//	jrge		TinyLZ_uncompress_NEXT
	;//↓2013/09/15修正:C言語の後置演算子と違って、dst_lenは既に+1している。従って、(dst_len==dst_max)の場合も、まだバッファ内である。
		jrgt		TinyLZ_uncompress_NEXT
	;//}}2013/09/15修正:C言語の後置演算子と違って、dst_lenは既に+1している。従って、(dst_len==dst_max)の場合も、まだバッファ内である。
		ld.b		[%r0]+, %r10			;//   *dst++ = c
TinyLZ_uncompress_NEXT:
		xld.w		%r4, [%sp+0]			;// %r4  := tlz->p
		cmp		%r4, %r2			;// if(tlz->p < src)			!INTERLOCK!
		jrult		TinyLZ_uncompress_LOOP		;//   goto LOOP
		;//
		xld.ub		%r4, [%sp+4]			;// %r4  := tlz->len_pos
		cmp		%r4, 15				;// if(tlz->len_pos > 15)		!INTERLOCK!
		jrugt		TinyLZ_uncompress_LOOP		;//   goto LOOP
		;//---------------------------------------------;//
		ld.w		%r10, %r3			;// %r10 := dst_len
		xadd		%sp, %sp, 20
		popn		%r3
		ret
");
#endif /*PIECE*/

/****************************************************************************
 *	圧縮
 ****************************************************************************/

//{{2009/03/02削除
// * Mon Mar 02 21:48:23 JST 2009 Naoyuki Sawa
// - TinyLZc構造体、TinyLZc_init関数、TinyLZc_put関数の圧縮ストリーム実装に伴い、
//   TinyLZ_compress()もこれらを利用して再実装したため、古いコードを削除しました。
//   しかし、これまで安定して動いていたコードなので、参考のために残しておきます。
//   この古いコードの方が、単独の関数なので、新しいコードよりも理解し易いです。
//   新しいコードも、アルゴリズムはこの古いコードと同じです。
//---------------------------------------------------------------------------
//	int
//	TinyLZ_compress(void* _dst, int dst_max, const void* _src, int src_len)
//	{
//		      unsigned char* tmp = calloc(src_len + 15, 1);
//		const unsigned char* src = memcpy(&tmp[15], _src, src_len);
//		const unsigned char* end = src + src_len;
//		      unsigned char* dst = _dst;
//		int dst_len = 0;
//		int imm_len = 0;
//		//
//		int c;
//		int len;
//		int pos;
//		int dic_len;
//		int dic_pos;
//	
//		while(src < end) {
//			dic_len = 0;
//			dic_pos = 0; /* 警告抑制 */
//			for(pos = 1; pos <= 15; pos++) {
//				for(len = 0; (src < end) && (len < 16); src++, len++) {
//					if(*src != *(src - pos)) {
//						break;
//					}
//				}
//				src -= len;
//				if(len > dic_len) {
//					dic_len = len;
//					dic_pos = pos;
//				}
//			}
//			//if(dic_len >= 1) {
//			//↓ひんぱんにimm/dicが切り替わって圧縮率が低下するのを防ぐため
//			if((imm_len == 0 && dic_len >= 1) ||
//			   (imm_len != 0 && dic_len >= 2)) {
//				/*{{imm*/
//				if(imm_len) {
//					if(dst_len++ < dst_max) {
//						*dst++ = (imm_len - 1) << 4;
//					}
//					src -= imm_len;
//					do {
//						c = *src++;
//						if(dst_len++ < dst_max) {
//							*dst++ = c;
//						}
//					} while(--imm_len);
//				}
//				/*}}imm*/
//				/*{{dic*/
//				if(dst_len++ < dst_max) {
//					*dst++ = (dic_len - 1) << 4 | dic_pos;
//				}
//				/*}}dic*/
//				src += dic_len;
//			} else {
//				src++;
//				/*{{imm*/
//				if(++imm_len == 16) {
//					if(dst_len++ < dst_max) {
//						*dst++ = (imm_len - 1) << 4;
//					}
//					src -= imm_len;
//					do {
//						c = *src++;
//						if(dst_len++ < dst_max) {
//							*dst++ = c;
//						}
//					} while(--imm_len);
//				}
//				/*}}imm*/
//			}
//		}
//		/*{{imm*/
//		if(imm_len) {
//			if(dst_len++ < dst_max) {
//				*dst++ = (imm_len - 1) << 4;
//			}
//			src -= imm_len;
//			do {
//				c = *src++;
//				if(dst_len++ < dst_max) {
//					*dst++ = c;
//				}
//			} while(--imm_len);
//		}
//		/*}}imm*/
//	
//		free(tmp);
//		return dst_len;
//	}
//---------------------------------------------------------------------------
//}}2009/03/02削除

void
TinyLZc_init(TinyLZc* self, void* dst, int dst_max)
{
	memset(self, 0, sizeof(TinyLZc));
	self->dst = dst;
	self->end = self->dst + dst_max;
}

void
TinyLZc_put(TinyLZc* self, int c)
{
	unsigned char buf[15/*dic*/ + (15 + 1)/*src*/];
	unsigned char* src = buf + 15/*dic*/;
	//
	unsigned char* dst;
	unsigned char* end;
	int src_len;
	int imm_len;
	//
	int len;
	int pos;
	int dic_len;
	int dic_pos;

	dst = self->dst;
	end = self->end;
	src_len = self->src_len;
	imm_len = self->imm_len;
	memcpy(src - 15/*dic*/, self->buf, 15/*dic*/ + src_len/*src*/);

	if(c != -1/*EOF*/) {
		src[src_len++] = c;
	}
	while((c != -1/*EOF*/ && src_len == 16) ||
	      (c == -1/*EOF*/ && src_len !=  0)) {
		dic_len = 0;
		dic_pos = 0; /* 警告抑制 */
		for(pos = 1; pos <= 15; pos++) {
			for(len = 0; len < src_len; src++, len++) {
				if(*src != *(src - pos)) {
					break;
				}
			}
			src -= len;
			if(len > dic_len) {
				dic_len = len;
				dic_pos = pos;
			}
		}
		if((imm_len == 0 && dic_len >= 1) ||
		   (imm_len != 0 && dic_len >= 2)) {
			/*{{imm*/
			if(imm_len != 0) {
				if(dst < end) {
					*dst = (imm_len - 1) << 4;
				}
				dst++;
				src -= imm_len;
				do {
					if(dst < end) {
						*dst = *src;
					}
					dst++;
					src++;
				} while(--imm_len);
			}
			/*}}imm*/
			/*{{dic*/
			if(dst < end) {
				*dst = (dic_len - 1) << 4 | dic_pos;
			}
			dst++;
			/*}}dic*/
			src += dic_len;
			src_len -= dic_len;
		} else {
			src++;
			src_len--;
			/*{{imm*/
			if(++imm_len == 16) {
				if(dst < end) {
					*dst = (imm_len - 1) << 4;
				}
				dst++;
				src -= imm_len;
				do {
					if(dst < end) {
						*dst = *src;
					}
					dst++;
					src++;
				} while(--imm_len);
			}
			/*}}imm*/
		}
	}
	if(c == -1/*EOF*/ && imm_len != 0) {
		/*{{imm*/
		if(dst < end) {
			*dst = (imm_len - 1) << 4;
		}
		dst++;
		src -= imm_len;
		do {
			if(dst < end) {
				*dst = *src;
			}
			dst++;
			src++;
		} while(--imm_len);
		/*}}imm*/
	}

	self->dst = dst;
	//self->end = end;
	self->src_len = src_len;
	self->imm_len = imm_len;
	memcpy(self->buf, src - 15/*dic*/, 15/*dic*/ + src_len/*src*/);
}

int
TinyLZ_compress(void* _dst, int dst_max, const void* _src, int src_len)
{
	const unsigned char* src = _src;
	      unsigned char* dst = _dst;
	//
	TinyLZc lzc;

	TinyLZc_init(&lzc, dst, dst_max);
	while(src_len--) {
		TinyLZc_put(&lzc, *src++);
	}
	TinyLZc_put(&lzc, -1/*EOF*/);

	return lzc.dst - dst;
}

