lz4ブロック解凍(arm向け)

unlz4.s

/* 
	unlz4
	LZ4ブロック圧縮の解凍。展開速度が早く単純でコードサイズも抑えられるので組み込み向け
	LZ4は単純なRLEではなく辞書方式なので、展開用RAMが多ければ多いほど高圧縮が見込めるが
	妥当な圧縮率を得る場合はメモリは最低64Kほど必要かもしれない。
	https://lz4.github.io/lz4/

	以下の実装を参考にCM4-7向けに変更と書き出しサイズを返すように改良
	また、末端で必ず+4バイトほどオーバ書き込みしていたのでそれも治した
	Jens Bauer
	https://community.arm.com/processors/b/blog/posts/lz4-decompression-routine-for-cortex-m0-and-later
  yza
  https://www.yza.jp/tblog/2018/11/12/lz4-decompress-assembler-code-for-cortex-m3-or-later/
 
	License: Public Domain - I cannot be held responsible for what it does or does not do if you use it, whether it's modified or not.

	Entry point = unlz4：
	  r0 = 圧縮データブロックのポインタ。
	       このときの最初の4Byte(Dword)は、圧縮ブロックのデータ長(Byte)を指定する必要がある
	  r1 = 解凍結果を入れるポインタ
	  return 
	  r0 = 書き出したサイズを返す

	Entry point = unlz4_len：
	  r0 = 圧縮データブロックのポインタ。
	       ここでのデータはunlz4の時とは違い、いきなり圧縮データが始まっている必要がある
	  r1 = 解凍結果を入れるポインタ
	  r2 = 圧縮データブロックの長さ(Byte単位)
	  return 
	  r0 = 書き出したサイズを返す


	C, C++ での呼び出し：

	extern uint32_t unlz4(const void *src, void *dest);
	    srcに入っている圧縮ブロックの解凍結果をdestに入れる
		destは十分な容量を確保しておく必要があるが、圧縮時に指定したブロックサイズ以上にはならないはず

		src : 圧縮ブロックデータのポインタを指定
	          このときの最初の4Byte(Dword)は、圧縮ブロックのデータ長(Byte)を指定する必要がある
	    dest： 解凍結果を入れるポインタ

		ret: 書き出したサイズを返す

	extern uint32_t unlz4_len(const void *src, void *dest, uint32_t length);
	    srcに入っている圧縮ブロックの解凍結果をdestに入れる
		destは十分な容量を確保しておく必要があるが、圧縮時に指定したブロックサイズ以上にはならないはず

		src : 圧縮ブロックデータのポインタを指定
	         ここでのデータはunlz4の時とは違い、いきなり圧縮データが始まっている必要がある
	    dest：解凍結果を入れるポインタ
	    len： 圧縮データブロックの長さ(Byte単位)

		ret: 書き出したサイズを返す

	[注意]
		dest(書き出し先)のメモリ確保サイズは事前に決めておく必要がある。
		これはファイルフォーマット自体に圧縮時のブロックサイズを決めておくなどしておく必要がある。
 */
 
#include "asm/unified.h"
#include "asm/linkage.h"
#include "asm/assembler.h"

	.text
    .cpu			cortex-m7
	.align	5
	.thumb
	.thumb_func

/* unlz4_copydata
	srcポインタr2 から dstポインタr1 に r4 バイトをコピーするマクロ
	r2,r1 は r4 ぶん進む (r4は0になる)
	パラメータ
		r1: コピー先ポインタ(最終的にr1+r4となる)
		r2: コピー元ポインタ(最終的にr2+r4となる)
		r4: コピーするバイト数(0になる)

	r3はワークとして破壊されるので注意
*/
.macro  unlz4_copydate
1:
	ldrb			r3, [r2],#1			// read byte from source, with post increment
	strb			r3, [r1],#1			// store byte to destination, with post increment
	subs			r4, r4,#1			// decrement counter
	bne				1b					// 0になるまでloop
.endm

/*
	unlz4_getlen
	Lz4ブロックのタグから長さを取得する
	パラメータ
		r0: 圧縮ブロックデータへのポインタ
		r4: リテラル長(1～15)		※15の場合、ソースにさらにlengthが続いているのでそれを取り出す
	戻り値
		r4 リテラル長
		r0 はさらにlengthを取り出した場合、進む

	r3はワークとして破壊されるので注意
 */
.macro  unlz4_getlen
	cmp				r4, #15				// if (r4 != 15) goto 2
	bne				2f
1:										// while(1) {
	ldrb			r3, [r0],#1			//   r3 = *r0++;		   ; read another byte
	add				r4, r4,r3			//   r4 += r3;		       ; add byte to length
	cmp				r3, #0xFF			//   if(r3 != 0xFF) break; ; check if end reached
	beq				1b					// }
2:
.endm



/*	r0 : 圧縮データ ソースポインタ
	r1 : 伸長データ書き出しポインタ
	r2 : 圧縮データlength (エンドポインタの計算後はワークとする)
	r5 : 圧縮データのエンドポインタ

	r3 : ワーク
	r4 : ワーク
	r6 : ワーク
	r7 : ワーク (伸長サイズ計算用)
*/

// extern uint32_t unlz4(const void *src, void *dest);
ENTRY(unlz4)
	ldr			    r2, [r0],#4			// r2 = *r0++; get length of compressed data
ENDPROC(unlz4)
	.thumb_func

// unlz4_len() の場合 r2に 圧縮データ長が入ってくるので
// unlz4() からはそのまま流せばよい
// extern uint32_t unlz4_len(const void *src, void *dest, uint32_t length);
ENTRY(unlz4_len)
	push			{r4-r7,lr}			// save r4, r5, r6 r7 and return-address (r4,r5,r6,r7 をワークに使用する)
	adds			r5, r2,r0			// point r5 to end of compressed data
	movs			r7, #0				// r7 = 0 clear decompress counter

getToken:
	ldrb			r6, [r0],#1			// r6 = *r0++; get token
	lsrs			r4, r6,#4			// r4: トークンの下位4bit == literal length,  r6: keep token 
	beq				getOffset			// jump forward if there are no literals

	// get length of literals
	unlz4_getlen

	movs			r2, r0				// point r2 to literals
	adds			r7, r7, r4			// r7 += r4;  r4 = copy length
	// copy literals (r2=src, r1=dst, r4=len)
	unlz4_copydate

	movs			r0, r2				// update source pointer

getOffset:
	cmp				r0, r5				// fix: check end of data
	bge				unlz4_quit			// fix: oops unlz exit
	ldrb			r3, [r0],#1			// r3 = *r0++;					get match offset's low byte
	sub				r2, r1,r3			// r2 = r1 - r3;				subtract from destination; this will become the match position
	ldrb			r3, [r0],#1			// r3 = *r0++;					get match offset's high byte
	lsl				r3, r3,#8			// r3 <<= 8;					shift to high byte
	sub				r2, r2,r3			// r2 -= r3;					subtract from match position

	//lsl				r4, r6,#28			// r4 = r6 << 28;				get rid of token's high 28 bits
	//lsr				r4, r4,#28			// r4 >>= 28;					move the 4 low bits back where they were
	// 上記2命令は、r6の下位4bitをr4に入れればよい(Cortex-M0では使えないそうだ)
	and				r4, r6,#0xF			// r4 = r6 & 0x0F;				r4 にトークンの下位4bitを取り出す

	// get length of match data
	unlz4_getlen

	adds			r4, r4,#4			// r4 += 4;  minimum match length is 4 bytes
	adds			r7, r7, r4			// r7 += r4; r4 = copy length

	// copy match data (r2=src, r1=dst, r4=len)
	unlz4_copydate

	cmp				r0, r5				// check if we've reached the end of the compressed data
	blt				getToken			// if not, go get the next token

unlz4_quit:
	movs			r0, r7				// r0 = r7; return uncompressed length
	pop				{r4-r7,pc}			// restore r4, r5 ,r6, r7 then return
ENDPROC(unlz4_len)