View source for Beam Software Compression Algorithm

'''Beam Software Compression Algorithm''' is the algo, developed by the [[Beam Software]] company. It uses [[LZ77]]-like system. List of games for the [[Sega Mega Drive]] is:
* ''[[George Foreman's KO Boxing]]'' (1992)
* ''[[NBA All-Star Challenge]]'' (1992)
* ''[[Blades of Vengeance]]'' (1993)
* ''[[Radical Rex]]'' (1994)
* ''[[Tom and Jerry: Frantic Antics]]'' (1994)
* ''[[True Lies]]'' (1994)

There is two variants of the decompressor (DWORD- and BYTE-length for the command token). But every variant can be unpacked by BYTE-length one. this is its algo (taken from the [[Radical Rex]] game, DWORD-length):
<pre>; =============== S U B	R O U T	I N E =======================================


bsct_decompress:
		movem.l	d2/d4-d5/a3-a5,-(sp)
		movea.l	a1,a2
		move.w	(a0)+,d3
		move.w	(a0)+,d0
		lea	-2(a0,d0.w),a3
		andi.w	#1,d0
		bne.s	lbl_ReadFromNonOddOffset
		moveq	#32,d4
		move.l	(a3)+,d5
		bra.s	lbl_StartDecompress
; ---------------------------------------------------------------------------

lbl_ReadFromNonOddOffset:
		subq.w	#1,a3
		moveq	#24,d4
		move.l	(a3)+,d5
		asl.l	#8,d5

lbl_StartDecompress:
		lea	(data_BSCT_COUNTS).l,a5
		moveq	#0,d0
		bra.s	lbl_Start
; ---------------------------------------------------------------------------

lbl_MainLoop:
		dbf	d4,lbl_DecCmdBitsCount1
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount1:
		roxl.l	#1,d5
		bcs.s	lbl_CopyDestToDest_Start

lbl_Start:	
		moveq	#1,d1
		dbf	d4,lbl_DecCmdBitsCount2
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount2:
		roxl.l	#1,d5
		bcs.s	lbl_DoCopySrcToDest

lbl_ReadCopyCount:
		dbf	d4,lbl_DecCmdBitsCount3
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount3:
		roxl.l	#1,d5
		roxl.w	#1,d1
		dbf	d4,lbl_DecCmdBitsCount4
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount4:
		roxl.l	#1,d5
		bcc.s	lbl_ReadCopyCount

lbl_DoCopySrcToDest:
		add.w	d1,d0
		subq.w	#1,d1

lbl_CopySrcToDest:
		move.b	(a0)+,(a1)+
		dbf	d1,lbl_CopySrcToDest
		cmp.w	d0,d3
		bhi.s	lbl_CopyDestToDest_Start
		bra.s	lblExit
; ---------------------------------------------------------------------------

lbl_CopyDestToDest_Start:
		move.w	d0,d2
		move.w	d0,d1
		andi.w	#$FF00,d1
		beq.s	lbl_HiWordIsZero
		moveq	#8,d1
		lsr.w	#8,d2

lbl_HiWordIsZero:	
		andi.w	#$FF,d2
		add.b	(a5,d2.w),d1
		subq.w	#1,d1
		clr.w	d2

lbl_ReadOffsetInWindow:
		dbf	d4,lbl_DecCmdBitsCount5
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount5:
		roxl.l	#1,d5
		roxl.w	#1,d2
		dbf	d1,lbl_ReadOffsetInWindow
		lea	(a2,d2.w),a4
		moveq	#1,d1
		dbf	d4,lbl_DecCmdBitsCount6
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount6:
		roxl.l	#1,d5
		bcs.s	lbl_DoCopyDestToDest

lbl_ReadLengthForWindow:
		dbf	d4,lbl_DecCmdBitsCount7
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount7:
		roxl.l	#1,d5
		roxl.w	#1,d1
		dbf	d4,lbl_DecCmdBitsCount8
		moveq	#31,d4
		move.l	(a3)+,d5

lbl_DecCmdBitsCount8:
		roxl.l	#1,d5
		bcc.s	lbl_ReadLengthForWindow

lbl_DoCopyDestToDest:
		addq.w	#2,d1
		add.w	d1,d0
		subq.w	#1,d1

lbl_CopyDestToDest:
		move.b	(a4)+,(a1)+
		dbf	d1,lbl_CopyDestToDest
		cmp.w	d0,d3
		bhi.w	lbl_MainLoop

lblExit:
		movem.l	(sp)+,d2/d4-d5/a3-a5
		rts
; End of function bsct_decompress

; ---------------------------------------------------------------------------</pre>

==Remarks==
There is one interest thing in this algo. It uses bits-count table for the offsets when unpacking from LZ77-window. So, other algos use statical bit-length for the offset (dword or word, for ex.). And '''BSCT''' uses dynamic length. It can be explained by nonsense of using of 32 bits for the offset if its value is just 5, for ex.

==Unpackers==
[http://www.romhacking.net/utilities/1084/ BSCT (Beam Software Compression Tool)]

[[Category:Data compression]]