Sonic and Sega Retro Message Board: vladikcomper - Viewing Profile - Sonic and Sega Retro Message Board

A much faster Kosinski decompressor for the 68k

Kosinski is a variant of LZSS compression algorithm, used in various Sega Genesis games. Being much faster than Nemesis algorithm in decompression, this format also provides a fairly better compression ratio on data with frequently repeated sequences of bytes. The decompression code for the 68k found in many Genesis games seems identical. Its decompression routine is known as 'KosDec' in most of Sonic diassemblies. Although written in quite a wise and accurate manner, it still suffers from some optimization errors, both on logic and instructions side of things.

I started looking into the ways of reducing decompression times after once I attempted decompressing big blocks of data on the fly. The process was time-critical and the original decompressor was doing pretty well, but not as well as I wanted it to be: it was kind of balancing on the edge -- I needed just a tiny bit faster processing to get rid of unwanted slowdown. I analyzed the whole decompressor's code back then in order to optimize it and get the best out of it. I figured few tricks which allowed me about 5% faster decompression which was enough back at the time.

Later I did realize that the decompression routine can be optimized even further, but more fundamental changes should be made to it. I then decided to create my own implementation of Kosinski decompressor by applying all the optimization tricks I planned and more. It was doing the same thing, but in a different way, using a different, more efficient code logic.

The result overcame all my expectations, the very first revision of my own Kosinski decompressor was overall 40% faster than the original one. Later on, MarkeyJester and flamewing have suggested a few more ideas, which helped to optimize it even further. Initially, I didn't plan to use some extreme optimization tricks like look-up tables (LUTs) in order to simplify calculations, but flamewing's test proved to give it a good performance increase that I didn't expect, which quite makes up for a larger decompression code.

Now, let me present you, an extremely fast Kosinski decompressor!

http://pastebin.com/EtYf1vz6

The performance increase compared to the original decompressor is unreal. Believe or not, it works more than 1.5 times faster. I've set several tests to measure new compressor's effectiveness. Here's a test involving decompressing the original EHZ art from Sonic 2:



Using the new decompressor will not only greatly reduce loading times on any Kosinski-compressed art, but also provide you more freedom with "on the fly" decompression, since you will be able to decompress nearly twice as much data within one TV-frame.

An optimized Nemesis decompressor for the 68k

Unlike Kosinski, Nemesis is an entropy-based compression method. Due to this method's nature, characters in the compressed stream have variable size in bits, making decompression process way more time-consuming: it is required to read compressed stream bit by bit and analyze it to decode characters. Although compression was rather high, it took about 10 times slower than Kosinski to decompress. The latter also provided quite a close compression ratio, which was even higher for many files with frequently repeated byte sequences. That was the reason Sonic Team started slowly migrating from this compression format starting from Sonic 2. Most of the compressed art in Sonic 3K was in Kosinski format already.

I attempted to optimize the Nemesis decompression routine, known as 'NemDec' shortly after my success with the Kosinski decoder. However, even given the fact that Nemesis decompression was terribly slow, their original code was surprisingly well-designed. The algorithm was quite complex and used nearly all the registers processor provided, leaving me almost no gaps for usual optimization tricks.

I've managed to pull just a few optimization tricks, but this didn't make a considerable improvement though. Anyways, a little optimization over the original version was reached, which, considering how long the decompression takes, helps it to save up to 4 frames on decompressing a single level art file in Sonic 1.

http://pastebin.com/cAJSJ0np

The performance increase is about 5% as seen below. This test program decompressed the original GHZ art from Sonic 1. The optimized version works 3 frames faster:



* * *

Also, stay tuned! More on the Kosinski and Nemesis compression shall come soon.

THE FIRST PUBLIC RELEASE

The day has finally come: the day I am finally releasing a full-fledged, full on hack that I have been working on for quite a long time. I can't believe it's finally happening! What an exciting moment for myself!

I must say, a lot, and I mean a lot of work is still needed until I feel this hack is complete. To my regret, SWA still doesn't boast a wide variety of levels, so don't expect too much from the hack. In any case, I was able to make this release as a playable and enjoyable as possible, so I'm extremely happy about this release.

So, proceed!

---

The release trailer. Totally necessary to watch. I can't describe how thankful am I to mr. MB for creating this amazing sight!

---

So, what's new about this hack?

• Blast Processing. Who says Sega can't do what Super Nintendo does?
  
• Russian and English languages. Sonic Winter Adventures also has two language settings, English and Russian. The two languages ​​are represented in one menu. You can change the language in the Options menu.
  
• High-speed gameplay! Like the best features of its predecessor, Sonic Quick Winter Adventures, SWA brings new tricks to the table that add even more speed and drive to the game play. Some of the moves include the Homing Attack, Jump Dash, Super Peel Out, and of course, the good old Spin Dash.
  
• New bosses. Making bosses is usually a very complex process that requires a lot of effort. Not to mention, it can be difficult sometimes to come up with the idea of a good boss, but as you can see from my past projects, I have a special fondness for bosses! Therefore, one of the key elements of Sonic Winter Adventures is the bosses. In this hack, I paid particular attention to the development of bosses, which means lots of time and effort had been poured in.
  
• Unlockables. Even after you finished all the levels, the game is far from over! As you go, you will open some previously hidden features and modes, so be on the lookout.

---

Of course, Sonic Winter Adventures would not be possible without the help and support of many wonderful people!

• Jet - a great musician and a good friend. He has made many invaluable contributions to the project. He not only created the music for the hack in zingy quality, made ​​technically sophisticated ports, but also gave valuable tips and expressed interesting ideas. Not to mention the fact that he strongly encouraged me to develop. It is unlikely that this project would have been further developed without his support.
  
• S_T_D - another first-class musician who has recently expressed a desire to make some music ports for hacking. The quality of his work took my fancy, I took his songs, no questions asked.
  
• Deoxys Kyogre - offered some amazing ideas for the act of the first zone, which gave me a second wind in the improvement of the levels. He created a few chunks, but they later helped me realize a lot of interesting solutions and new ways in the first zone.
  
• PsychoRFG - has an incredible ability to push every button combination that will cause the game to behave in unexpected ways. Also has X-ray vision and can see the bug, even if it occurs in one case in a million.
  
• SonicVaan - another beta tester, who, like PsychoRFG, revealed a lot of bugs and flaws. Thanks to him the game was fixed many small and medium-sized bugs and flaws in the placement of objects in the levels.
  
• MarkeyJester - special thanks for the testing of some components of the hack on real hardware.
  
• MainMemory - advised me on the English localization.
  
• Sienduk - tested one of the pre-final prototypes the on March 30th on real hardware. Watching his passing has helped me to bring out the many weaknesses in the structure of the levels and some shortcomings.
  
• mr. MB - provided the flash cartridge, making and testing took place Sonic Winter Adventures in Tula on March 30 He also created a stunning Launch Trailer for the hack, for which I am eternally grateful to him.

Also express my gratitude to the Sonic Retro Tech Members and Sonic SCANF!

---

DOWNLOAD

hai guyz lemme present u my new projec!!! its called sonic 1 megahack ultra edition!!!

there r new levelz!!! new pallets!!! and it haev homming atack!!!

screenhots!!!



donwload!!!

05-Aug-2012 - Version 1.1 is out! Check out this post for the info (clickie). Links in this post are also up to date.
28-Oct-2012 - New guide: "How to increase playback quality with Mega PCM".
03-Mar-2013 - Added "Fixing SEGA PCM playback" section into the "How to increase playback quality with Mega PCM" guide.


* * *

"Mega PCM" is my new DAC driver for Sonic 1, coded from the ground up. We already have JMan's and S1HL's custom drivers, which provided us with a lot of good possibilities over the native Sonic 1's DAC driver. I personally used JMan's driver all the time, finding it the best for my purposes. However, like most Z80 drivers, it had some limits and quirks, which were impossible to overpass. All these 'quirks' are actually caused by the hardware design: the Z80 is very limited in accessing ROM sections (this is done via a small 32 KB window) and the processor has to do all DAC timing itself, which adds many difficulties into programming it.

In my driver, I attempted to get rid of some unpleasant limits most of Z80 drivers usually have. I also aimed to code it in the most optimized way to keep playback rates high, while the code is overloaded with a lot of logic I have to program to make overpassing limits possible. To my surprise, I succeded, Mega PCM currently plays sound faster than YM's maximum output frequency (~27 kHz), so there is some room remains for future additions

The features

• Automatic bank-switching
  Forget about the banks, put your samples where you like, how you like. You no longer have to align samples on 32 KB boundary and care if they cross the boundary.
  
  
• Unlimited sample size
  Samples are no more limited to 32 KB. "Mega PCM" is capable of playing samples of absolutely any size, as long as it can fit your ROM space.
  
  
• Two sound formats supported
  These are 4-bit DPCM and 8-bit PCM.
  The first format was widely used by Sonic 1 to Sonic 3K for DAC samples as it takes only half of the space a normal PCM sound would. 8-bit PCM, however, is the 'native' format for Sega's YM2612 chip, it takes more space but provides a better sound quality.
  
  
• Extended playback controls: Stop, Pause, Loop, Priority
  "Mega PCM" can pause and continue sample playback, so if you play a long sample it won't be cut off after you pause the game.
  You can also loop samples (good for DAC-songs) and can tell "Mega PCM" not to overwrite some samples (good for in-game voice clips).
  
  
• DAC panning
  You can store your sample to play in Left or Right headphone only.
  
  
• Up to $5F DAC samples allowed
  For instance, JMan's driver allowed $1F DAC sample due to its usage of 8-bit pointers in the code. However, in reality DAC table size is only limited by the RAM size, but the SMPS only allows up $5F different DAC samples (slots $81-$CF).

How-to Install "Mega PCM"

If you got interested in trying it out, here we go!
In this guide, I'll tell you how to put Mega PCM driver into your hack, how to improve SMPS slightly to suit new driver's needs and go wild with including new DACs!
This guide also includes bonus: "How-to play voices in-game" (see below)

First off, download this: https://dl.dropbox.c...aPCM_v11_Bin.7z
This is almost ready to use "Mega PCM" setup with Sonic 3 samples set (except for timpani, S3's doesn't fit well here). Copy all files from my archive into your hack's folder and we'll start.

The guide is for Hivebrain's Disassembly.

1. Replacing old driver and driver loading routine

Open Sonic1.asm and find 'Kos_Z80' label, you'll see the following code:

Kos_Z80:	incbin	sound\z80_1.bin
		dc.w ((SegaPCM&$FF)<<8)+((SegaPCM&$FF00)>>8)
		dc.b $21
		dc.w (((EndOfRom-SegaPCM)&$FF)<<8)+(((EndOfRom-SegaPCM)&$FF00)>>8)
		incbin	sound\z80_2.bin
		even

Delete everything, and put this instead:

	include	'MegaPCM.asm'

Now, goto 'SoundDriverLoad' routine and replace all the code with this:

SoundDriverLoad:			; XREF: GameClrRAM; TitleScreen
		nop
		move.w	#$100,d0
		move.w	d0,($A11100).l
		move.w	d0,($A11200).l
		lea	(MegaPCM).l,a0
		lea	($A00000).l,a1
		move.w	#(MegaPCM_End-MegaPCM)-1,d1

	@Load:	move.b	(a0)+,(a1)+
		dbf	d1,@Load
		moveq	#0,d1
		move.w	d1,($A11200).l
		nop
		nop
		nop
		nop
		move.w	d0,($A11200).l
		move.w	d1,($A11100).l
		rts
; End of function SoundDriverLoad

2. Editing SMPS to work with the driver

Find 'sub_71B4C' label and scroll down until you see this part:

		btst	#7,($A01FFD).l
		beq.s	loc_71B82
		move.w	#0,($A11100).l	; start	the Z80
		nop	
		nop	
		nop	
		nop	
		nop	
		bra.s	sub_71B4C
; ===========================================================================

loc_71B82:

Delete or comment out this code.



Then, goto 'loc_71C88' label, find and delete these lines:

		btst	#3,d0
		bne.s	loc_71CAC

Next, find 'loc_71C44' label and in the very beginning add this code:

		move.b	($A04000).l,d2
		btst	#7,d2
		bne.s	loc_71C44
		move.b	#$2A,($A04000).l

The following changes will make "Mega PCM" pause playback when the game pauses and continue it when the game unpauses.

Find 'loc_71E7C' and at the very end, just before BRA, add this line:

		move.b	#$7F,($A01FFF).l; pause DAC

Next, find 'loc_71EDC' and replace all the code until label 'loc_71EFE' with this:

loc_71EDC:
		adda.w	d3,a5
		dbf	d4,loc_71EC4

		lea	$340(a6),a5
		btst	#7,(a5)
		beq.s	@UnpauseDAC
		btst	#2,(a5)
		bne.s	@UnpauseDAC
		move.b	#-$4C,d0
		move.b	$A(a5),d1
		jsr	sub_72722(pc)

@UnpauseDAC:
		move.b	#0,($A01FFF).l	; unpause DAC

And the last touch, let's make playback stop properly (not only mute) when SMPS stops the sound.
Goto 'loc_725B6' (a part of 'Sound_E4' code) and before the 'bra.w sub_729B6' add this line:

		move.b	#$80,($A01FFF).l ; stop DAC playback

That's it!

How-to use "Mega PCM"

Open MegaPCM.asm. This file includes compiled "Mega PCM" Z80-code and stores table of samples to play. To make working with driver easier, I added some constants and macros to setup table and include samples.

Scroll down in the file until you see this:

; ---------------------------------------------------------------
; DAC Samples Table
; ---------------------------------------------------------------

	DAC_Entry	$08, Kick, dpcm			; $81	- Kick
	DAC_Entry	$08, Snare, dpcm		; $82	- Snare
	DAC_Entry	$1B, Timpani, dpcm		; $83	- Timpani
	dc.l	0,0					; $84	- <Free>
	dc.l	0,0					; $85	- <Free>
	dc.l	0,0					; $86	- <Free>
	dc.l	0,0					; $87	- <Free>
	DAC_Entry	$12, Timpani, dpcm		; $88	- Hi-Timpani
	DAC_Entry	$15, Timpani, dpcm		; $89	- Mid-Timpani
	DAC_Entry	$1B, Timpani, dpcm		; $8A	- Mid-Low-Timpani
	DAC_Entry	$1D, Timpani, dpcm		; $8B	- Low-Timpani

MegaPCM_End:

; ---------------------------------------------------------------
; DAC Samples Files
; ---------------------------------------------------------------

	IncludeDAC	Kick, bin
	IncludeDAC	Snare, bin
	IncludeDAC	Timpani, bin
	even

First block is a DAC samples table, storing what sample to play and how to play it. It will be loaded to Z80 memory along with "Mega PCM" code.

Second block includes sound files into your ROM. 'IncludeDAC' macro searches for file with given name and extension in 'dac' folder, which you've added to your hack among with other files.

For example,

	IncludeDAC	Kick, bin

will include 'dac\kick.bin' file.

The macro includes all the files 'as is', except for files with 'wav' extension. For WAV-files, the macro cuts off the header, or you will hear a short noise when play them.

BIN-files usually used for DPCM format. The fact "Mega PCM" plays this format means you may rip DACs from any Sonic game and play it without conversion to PCM, which makes file two times heavier, but doesn't help with the quality. If you wish to convert PCM sound to DPCM, you can use JMan's compressor: http://selbi.se.funp...e/s1sndcomp.exe

WAV-files should use "8-bit unsigned PCM" format. PCM sound can be also presented with 'RAW' extension (raw sound without header), some trackers support it.

Sound frequency can be up to ~30 kHz for PCM and ~32 for DPCM (Yeah, suddenly the more complex format got a higher playback rate, seems my optimized code is way fast. Actually, the fact it processes 2 DAC writes per loop helps a lot.)
But actually, YM2612 can't play DAC faster than ~27 kHz (it will lead to missed writes). However, emulators don't emulate this and if you don't care about playback quality on real hardware, go wild.

DAC samples table uses 'DAC_Entry' macros to store sample, which has the following format:

DAC_Entry <pitch>, <sample name>, <flags>

The real 8-byte format used by "Mega PCM" you can see in the macro's definition.

Pitch sets how fast the sample sound should play. The lower pitch is, the faster it will play.

Sample Name refers to sample name as defined by 'IncludeDAC' macro.

Flags field accepts the following flags:
* pcm - selects PCM format
* dpcm - selects DPCM format
* loop - makes sample loop itself
* pri - priority flag, playback won't be interrupted if new sample requested. Playback will respond only to stop/pause commands in this mode.
* panL - play in Left headphone only
* panR - play in Right headphone only
* panLR - play in both headphones

You can combine flags like this: dpcm+panL+loop+pri

Note: if no pan flags were set, "Mega PCM" won't change DAC panning, it will leave setting by SMPS.

Bonus: How-to play voices in game

Here is a small example of using "Mega PCM" to play voice clips during the game.

Download this clip: https://dl.dropbox.c...7401/V_Hurt.wav
Move it to 'dac' folder in you disassembly.

In the very end of MegaPCM.asm file, just before the 'even', add:

	IncludeDAC	V_Hurt,wav

Now we should add it in one of DAC table's slot, take slot $84 for example, it's free. We'll need "Mega PCM" to play this as PCM sound with high priority (or else it can be interrupted by another DACs in BGM).
Modify the table so it will look like this:

	DAC_Entry	$08, Kick, dpcm			; $81	- Kick
	DAC_Entry	$08, Snare, dpcm		; $82	- Snare
	DAC_Entry	$1B, Timpani, dpcm		; $83	- Timpani
	DAC_Entry	$07, V_Hurt, pcm+pri		; $84	- 'Hurt' voice
	dc.l	0,0					; $85	- <Free>
	dc.l	0,0					; $86	- <Free>
	dc.l	0,0					; $87	- <Free>
	DAC_Entry	$12, Timpani, dpcm		; $88	- Hi-Timpani
	DAC_Entry	$15, Timpani, dpcm		; $89	- Mid-Timpani
	DAC_Entry	$1B, Timpani, dpcm		; $8A	- Mid-Low-Timpani
	DAC_Entry	$1D, Timpani, dpcm		; $8B	- Low-Timpani

Done! Sample is now playable. However, we must program the game to play it. In order to do this, find 'PlaySound' routine and add a new routine above:

; ---------------------------------------------------------------------------
; Subroutine to	play a DAC sample
; ---------------------------------------------------------------------------

PlaySample:
	move.w	#$100,($A11100).l	; stop the Z80
@0	btst	#0,($A11100).l
	bne.s	@0
	move.b	d0,$A01FFF
	move.w	#0,($A11100).l
	rts

This routine will allow you to play DAC samples in game. Our new sample is $84, let's play it when Sonic's hurt.

Goto 'Hurt_Sound' and replace

	jsr	(PlaySound_Special).l

with

		moveq	#$FFFFFF84,d0
		jsr	PlaySample

That's it. Enjoy!

"Mega PCM" source code

"Mega PCM" has an open source code, enjoy!

Version 1.1 Source Code: https://dl.dropbox.c...1_SourceCode.7z
Version 1.0 Source Code: https://dl.dropbox.c...0_SourceCode.7z

I accept any ideas on improving driver's core, bug reports etc. You are free to modify driver for your purposes or create something new of it.

Pattern Load Cues, or simply PLC, is a system for loading Nemesis-compressed art during game execution. PLC is used to load art at the beginning of the level, as well as at certain points of the game (like loading singpost or boss art at the end of level). This system is rather complicated, in Sonic 1 and 2 it has few bugs, one of the was described in "How to fix PLC race condition" guide.

Recently I have figured out another bug regarding PLC queue shifting mechanism, which I considered to be simple queue overflow earlier.

Introduction

PLC system has a buffer, better to be called 'queue', taking $60 bytes in memory space. Queue is filled by the art load cues, each takes 6 bytes, first 4 being source ROM offset, and last two being destination VRAM offset. The cues are executed one by one until all the queue gets empty. To see what these cues are, check out _inc\Pattern Load Cues.asm file in Sonic 1's disassembly.

PLC queue can hold up to $10 (16) cues. Cues execution starts from the beginning of the queue storage. When the cue is done, all the cues are getting moved: the first cues is replaced by the second, the second - by the third and so on. In other words, the whole queue gets shifted. However, due to program error, when the buffer is filled up with all $10 cues, the last one doesn't clear on shifting, which leads to overcopying it, so all the queue eventually overfills with the same cue, so the game gets stuck decompressing the same art over and over again.

This bug is easy to meet in Sonic 1: once you have added two more cues into PLC_GHZ, the queue will take $10 cues, and the game will stuck at the Title Cards, though $10 cues is an is acceptable number.

Explanation of the bug

Let's look at queue shifting code to understand the reason of the bug. As an example, I will show you the code from Sonic 2 Xenowhirl's Disassembly, as it's more annotated in this place than Sonic 1's. Remember, the this code is the same in both Sonic 1 and Sonic 2.

; ===========================================================================
; pop one request off the buffer so that the next one can be filled

; loc_177A:
ProcessDPLC_Pop:
	lea	(Plc_Buffer).w,a0
	moveq	#$15,d0

-	move.l	6(a0),(a0)+
	dbf	d0,-
	rts

Firstly, this code transfers $16*4 = $58 bytes, which doesn't even match an integral number of cues. It should've done $5A bytes, which is $F cues. Transferring $58 bytes means it won't transfer last 2 bytes of the last ($10-th) cue which are VRAM offset. So the VRAM offset will remain from the previous cue.

Secondly, the last cue in the queue is not cleared, which will cause overcopying it. Eventually, all the queue will be filled with the last cue stored and the game will stuck endlessly processing the same cue.

Fixing the bug

Sonic 1 (Hivebrain's Disassembly)

Go to 'loc_16DC' and replace the whole code with this:

loc_16DC:			; XREF: sub_165E
		lea	($FFFFF680).w,a0
		lea	6(a0),a1
		moveq	#$E,d0		; do $F cues

loc_16E2:				; XREF: sub_165E
		move.l	(a1)+,(a0)+
		move.w	(a1)+,(a0)+
		dbf	d0,loc_16E2
		
		moveq	#0,d0
		move.l	d0,(a0)+	; clear the last cue to avoid overcopying it
		move.w	d0,(a0)+	;
		rts
; End of function sub_165E

Sonic 2 (Xenowhirl's Disassembly)

Go to 'ProcessDPLC_Pop' and replace the whole code with this:

ProcessDPLC_Pop:
	lea	(Plc_Buffer).w,a0
	lea	6(a0),a1
	moveq	#$E,d0		; do $F cues

-	move.l	(a1)+,(a0)+
	move.w	(a1)+,(a0)+
	dbf	d0,-

	moveq	#0,d0
	move.l	d0,(a0)+	; clear the last cue to avoid overcopying it
	move.w	d0,(a0)+	;
	rts

This new version of code will shift the queue correctly and protect the last cue from overcopying. The bug is gone! But don't forget about queue overflow, this will fix bug when queue is filled with $10 cues, but $11 and more cues are out of queue size!

EDIT: GRAMMAR