shobiz - Viewing Profile - Sonic and Sega Retro Message Board

Find My Content

Group:: Tech Member: Tech Members
Active Posts:: 895 (0.24 per day)
Most Active In:: Engineering & Reverse Engineering (377 posts)
Joined:: 27-March 05
Profile Views:: 3222
Last Active:: Private
Currently:: Offline

My Information

Age:: 23 years old
Birthday:: October 22, 1991
Gender:: Male
Location:: Karachi, Pakistan
Interests:: Mathematics, sciences, programming, reading, (association) football

Contact Information

E-mail:: Click here to e-mail me
MSN:: [email protected]
Website:: http://

Previous Fields

National Flag:: pk
Wiki edits:: 4,411

Latest Visitors

Billy
20 Dec 2014 - 14:38
nineko
07 Oct 2014 - 23:37
Hitaxas
22 Oct 2013 - 01:40
Toasty
02 Jun 2013 - 14:29
redhotsonic
22 Oct 2012 - 07:47

Topics I've Started

Nemesis compression

20 June 2010 - 08:14 AM

I started looking at the Nemesis decompression subroutine in Sonic & Knuckles a few days back, and the results can be seen at http://segaretro.org/Nemesis_compression under the Format Description and Decompression code headings. (I don't know if the decompression code is appropriate for that article actually - it seems useful for reference purposes but the lack of asm tags on Sega Retro spoils it somewhat).

Anyway, I had a couple of questions which I was hoping somebody here could answer. Bear in mind that I've never formally studied information theory or compression theory in my life, so they might be quite dumb.

QUOTE

The original compression program used by Sega to compress data into Nemesis archives most likely used the Shannon-Fano coding technique to build the binary tree. As a result, most Nemesis archives found within Mega Drive ROMs are not optimal

Any idea why Sega would use Shannon-Fano? Huffman coding's been around since 1952 according to Wikipedia, so it must've been known to them. Additionally, the archives produced by the Nemesis compressor in TSDC don't seem to be optimal either - for a simple uncompressed file I was able to produce a hand-compressed file which was 4 bytes smaller than TSDC's output. I know 4 bytes is a trivial difference, but it might be larger for more complex files, although then again no one would hand-compress a more complex file anyway.

QUOTE

The source data is analysed, and a table is built of the most commonly occurring 16-bit sequences in that data.

As far as I can tell the compressor operates on runs of nybbles rather than runs of words. I haven't touched the Compression Theory part, however, because it was written by Nemesis himself, and so I wanted someone with more knowledge of this to confirm before modifying it.

Also, in case anyone's interested, here's an annotated version of the Nemesis decompression code in Sonic & Knuckles in all its syntax-highlighted glory:

Syntax Highlighted Code: ASM

; ---------------------------------------------------------------------------
; Nemesis decompression subroutine, decompresses art directly to VRAM
; Inputs:
; a0 = art address
; a VDP command to write to the destination VRAM address must be issued
; before calling this routine
; ---------------------------------------------------------------------------
 
; =============== S U B R O U T I N E =======================================
 
 
Nem_Decomp:
		movem.l	d0-a1/a3-a5,-(sp)
		lea	(Nem_PCD_WriteRowToVDP).l,a3
		lea	(VDP_data_port).l,a4	; write all rows to the VDP data port
		bra.s	Nem_Decomp_Main
; End of function Nem_Decomp
 
; ---------------------------------------------------------------------------
; Nemesis decompression subroutine, decompresses art to RAM
; Inputs:
; a0 = art address
; a4 = destination RAM address
; ---------------------------------------------------------------------------
 
; =============== S U B R O U T I N E =======================================
 
 
Nem_Decomp_To_RAM:
		movem.l	d0-a1/a3-a5,-(sp)
		lea	(Nem_PCD_WriteRowToRAM).l,a3
; End of function Nem_Decomp_To_RAM
 
; ---------------------------------------------------------------------------
; Main Nemesis decompression subroutine
; ---------------------------------------------------------------------------
 
; =============== S U B R O U T I N E =======================================
 
 
Nem_Decomp_Main:
		lea	(Nem_code_table).w,a1
		move.w	(a0)+,d2	; get number of patterns
		lsl.w	#1,d2
		bcc.s	+	; branch if the sign bit isn't set
		adda.w	#Nem_PCD_WriteRowToVDP_XOR-Nem_PCD_WriteRowToVDP,a3	; otherwise the file uses XOR mode
+
		lsl.w	#2,d2	; get number of 8-pixel rows in the uncompressed data
		movea.w	d2,a5	; and store it in a5 because there aren't any spare data registers
		moveq	#8,d3	; 8 pixels in a pattern row
		moveq	#0,d2
		moveq	#0,d4
		bsr.w	Nem_Build_Code_Table
		move.b	(a0)+,d5	; get first byte of compressed data
		asl.w	#8,d5	; shift up by a byte
		move.b	(a0)+,d5	; get second byte of compressed data
		move.w	#$10,d6	; set initial shift value
		bsr.s	Nem_Process_Compressed_Data
		movem.l	(sp)+,d0-a1/a3-a5
		rts
; End of function Nem_Decomp_Main
 
; ---------------------------------------------------------------------------
; Part of the Nemesis decompressor, processes the actual compressed data
; ---------------------------------------------------------------------------
 
; =============== S U B R O U T I N E =======================================
 
; PCD is used throughout this subroutine as an initialism for Process_Compressed_Data
Nem_Process_Compressed_Data:
		move.w	d6,d7
		subq.w	#8,d7	; get shift value
		move.w	d5,d1
		lsr.w	d7,d1	; shift so that high bit of the code is in bit position 7
		cmpi.b	#%11111100,d1	; are the high 6 bits set?
		bcc.s	Nem_PCD_InlineData	; if they are, it signifies inline data
		andi.w	#$FF,d1
		add.w	d1,d1
		move.b	(a1,d1.w),d0	; get the length of the code in bits
		ext.w	d0
		sub.w	d0,d6	; subtract from shift value so that the next code is read next time around
		cmpi.w	#9,d6	; does a new byte need to be read?
		bcc.s	+	; if not, branch
		addq.w	#8,d6
		asl.w	#8,d5
		move.b	(a0)+,d5	; read next byte
+
		move.b	1(a1,d1.w),d1
		move.w	d1,d0
		andi.w	#$F,d1	; get palette index for pixel
		andi.w	#$F0,d0
 
Nem_PCD_GetRepeatCount:
		lsr.w	#4,d0	; get repeat count
 
Nem_PCD_WritePixel:
		lsl.l	#4,d4	; shift up by a nybble
		or.b	d1,d4	; write pixel
		subq.w	#1,d3	; has an entire 8-pixel row been written?
		bne.s	Nem_PCD_WritePixel_Loop	; if not, loop
		jmp	(a3)	; otherwise, write the row to its destination
; ---------------------------------------------------------------------------
 
Nem_PCD_NewRow:
		moveq	#0,d4	; reset row
		moveq	#8,d3	; reset nybble counter
 
Nem_PCD_WritePixel_Loop:
		dbf	d0,Nem_PCD_WritePixel
		bra.s	Nem_Process_Compressed_Data
; ---------------------------------------------------------------------------
 
Nem_PCD_InlineData:
		subq.w	#6,d6	; 6 bits needed to signal inline data
		cmpi.w	#9,d6
		bcc.s	+
		addq.w	#8,d6
		asl.w	#8,d5
		move.b	(a0)+,d5
+
		subq.w	#7,d6	; and 7 bits needed for the inline data itself
		move.w	d5,d1
		lsr.w	d6,d1	; shift so that low bit of the code is in bit position 0
		move.w	d1,d0
		andi.w	#$F,d1	; get palette index for pixel
		andi.w	#$70,d0	; high nybble is repeat count for pixel
		cmpi.w	#9,d6
		bcc.s	Nem_PCD_GetRepeatCount
		addq.w	#8,d6
		asl.w	#8,d5
		move.b	(a0)+,d5
		bra.s	Nem_PCD_GetRepeatCount
; ---------------------------------------------------------------------------
 
Nem_PCD_WriteRowToVDP:
		move.l	d4,(a4)	; write 8-pixel row
		subq.w	#1,a5
		move.w	a5,d4	; have all the 8-pixel rows been written?
		bne.s	Nem_PCD_NewRow	; if not, branch
		rts	; otherwise the decompression is finished
; ---------------------------------------------------------------------------
 
Nem_PCD_WriteRowToVDP_XOR:
		eor.l	d4,d2	; XOR the previous row by the current row
		move.l	d2,(a4)	; and write the result
		subq.w	#1,a5
		move.w	a5,d4
		bne.s	Nem_PCD_NewRow
		rts
; ---------------------------------------------------------------------------
 
Nem_PCD_WriteRowToRAM:
		move.l	d4,(a4)+
		subq.w	#1,a5
		move.w	a5,d4
		bne.s	Nem_PCD_NewRow
		rts
; ---------------------------------------------------------------------------
 
Nem_PCD_WriteRowToRAM_XOR:
		eor.l	d4,d2
		move.l	d2,(a4)+
		subq.w	#1,a5
		move.w	a5,d4
		bne.s	Nem_PCD_NewRow
		rts
; End of function Nem_Process_Compressed_Data
 
; ---------------------------------------------------------------------------
; Part of the Nemesis decompressor, builds the code table (in RAM)
; ---------------------------------------------------------------------------
 
; =============== S U B R O U T I N E =======================================
 
; BCT is used throughout this subroutine as an initialism for Build_Code_Table
Nem_Build_Code_Table:
		move.b	(a0)+,d0	; read first byte
 
Nem_BCT_ChkEnd:
		cmpi.b	#$FF,d0	; has the end of the code table description been reached?
		bne.s	Nem_BCT_NewPalIndex	; if not, branch
		rts	; otherwise, this subroutine's work is done
; ---------------------------------------------------------------------------
 
Nem_BCT_NewPalIndex:
		move.w	d0,d7
 
Nem_BCT_Loop:
		move.b	(a0)+,d0	; read next byte
		cmpi.b	#$80,d0	; sign bit being set signifies a new palette index
		bcc.s	Nem_BCT_ChkEnd	; a bmi could have been used instead of a compare and bcc
		move.b	d0,d1
		andi.w	#$F,d7	; get palette index
		andi.w	#$70,d1	; get repeat count for palette index
		or.w	d1,d7	; combine the two
		andi.w	#$F,d0	; get the length of the code in bits
		move.b	d0,d1
		lsl.w	#8,d1
		or.w	d1,d7	; combine with palette index and repeat count to form code table entry
		moveq	#8,d1
		sub.w	d0,d1	; is the code 8 bits long?
		bne.s	Nem_BCT_ShortCode	; if not, a bit of extra processing is needed
		move.b	(a0)+,d0	; get code
		add.w	d0,d0	; each code gets a word-sized entry in the table
		move.w	d7,(a1,d0.w)	; store the entry for the code
		bra.s	Nem_BCT_Loop	; repeat
; ---------------------------------------------------------------------------
 
; the Nemesis decompressor uses prefix-free codes (no valid code is a prefix of a longer code)
; e.g. if 10 is a valid 2-bit code, 110 is a valid 3-bit code but 100 isn't
; also, when the actual compressed data is processed the high bit of each code is in bit position 7
; so the code needs to be bit-shifted appropriately over here before being used as a code table index
; additionally, the code needs multiple entries in the table because no masking is done during compressed data processing
; so if 11000 is a valid code then all indices of the form 11000XXX need to have the same entry
Nem_BCT_ShortCode:
		move.b	(a0)+,d0	; get code
		lsl.w	d1,d0	; shift so that high bit is in bit position 7
		add.w	d0,d0	; get index into code table
		moveq	#1,d5
		lsl.w	d1,d5
		subq.w	#1,d5	; d5 = 2^d1 - 1
 
Nem_BCT_ShortCode_Loop:
		move.w	d7,(a1,d0.w)	; store entry
		addq.w	#2,d0	; increment index
		dbf	d5,Nem_BCT_ShortCode_Loop	; repeat for required number of entries
		bra.s	Nem_BCT_Loop
; End of function Nem_Build_Code_Table

A few Quackshot things

13 May 2010 - 01:15 PM

Use the PAR code 00AB4C:6002 (for REV00) or 00AC80:6002 (for REV01), go to the Sound Test, set the sound to Transylvania and start playing for a nice surprise.

For the curious, the game's story screen clears the RAM till $FFFD00 when it loads, which is why this effect normally doesn't occur. The PAR codes I posted make the game skip the RAM clearing and allow the effect to be seen.
Unused objects in Sonic 3k

18 May 2008 - 10:44 AM
(The first part of this post is a copypasta from my earlier post in The Supreme Topic of 'Other' Knowledge, that can be deleted if needed)

Anyone have any idea what this is supposed to be?

It's object ID $12 in the first object pointer list in Sonic 3k. It's not placed in any level, but the graphics fit perfectly in both acts of LBZ. All it does is moves down to a target position (or up, depending on a flag) when it senses a flag has been set, and then moves up to its original position (or down, depending on the same flag) when it senses the flag has been cleared. The use of the flag leads me to think this was supposed to be triggered by a button or some other external event.

If anyone wants to play around with it, use the PAR code 1EFC52:1200, which replaces the first monitor in LBZ with this. To make it move down, use the (Kega specific) PAR code FFF7E0:00FF, and once it's moved fully down use the (again Kega specific) PAR code FFF7E0:0000 to make it move up again. While moving down, it'll get overlapped by level tiles, so I recommend also using 025B00:C3C3 to give the object high priority and make it visible over the level tiles. Alternatively, if you want one which starts off downwards and moves up, along with the first PAR code use 1EFC50:25F0. This is the exact opposite - it starts off down and moves up when the flag is set. The code for this is at $25AF6, it's marked as Obj_12_1 in Stealth's disasm.

Another unused sprite, at object id $1A:

Unfortunately the graphics for this one don't seem to be present in any level, so it's hard to tell what it's supposed to be. You can control it using controller 2 - pressing A rotates it anti-clockwise, C rotates it clockwise and B resets it to horizontal. Normally, without any modifications, when you reach the centre you get sorta stuck there, just gaining speed until you jump off. However, in what I believe to be a coding error, the code for this object contains these two lines:

Syntax Highlighted Code: ASM
```
[color= #00bfff;]lea[/color]     (Vectors+[color= #ff0000;]$[/color][color= #ff0000;][color= #ff0000;]30[/color][/color]).[color= #00bfff;]w[/color],a2
```
and

Syntax Highlighted Code: ASM
```
[color= #00bfff;]lea[/color]     (Vectors+[color= #ff0000;]$[/color][color= #ff0000;][color= #ff0000;]34[/color][/color]).[color= #00bfff;]w[/color],a2
```
Loading part of the vector table is strange in itself, but later on an attempt is made to write to these addresses, which makes no sense at all and should apparently cause real hardware to crash. If you replace these two lines with

Syntax Highlighted Code: ASM
```
[color= #00bfff;]lea[/color]     [color= #ff0000;]$[/color][color= #ff0000;][color= #ff0000;]30[/color][/color](a0),a2
```
and

Syntax Highlighted Code: ASM
```
[color= #00bfff;]lea[/color]     [color= #ff0000;]$[/color][color= #ff0000;][color= #ff0000;]34[/color][/color](a0),a2
```
the cool running effect disappears and Sonic can just slide down these without hinderance, so I have no idea whether the effect was intended or just a coding error.

Although the graphics appear garbled, the code for this exists in the middle of other LBZ objects, so I think it's safe to assume it was intended for LBZ. If anyone wants to play around with these, you can use the PAR codes 094EA6:0002 and 094EA8:7106 to replace all in-level monitors with this object. Additionally, if you want to fix what I believe to be a coding error, also use the PAR codes 027270:45E8 and 027284:45E8. Anyone have more info about this?
Sonic 3k rings management system in Sonic 2

11 April 2008 - 02:42 PM
Sonic 3k's ring management system differs drastically from Sonic 2's in one major way: Levels in Sonic 3k don't use groups of rings, they only have individual rings, and as a result Sonic 3k can read ring placement data directly from ROM instead of having to expand it inside RAM, allowing more rings in less RAM space. Setting up a similar system in Sonic 2 also allows more rings in levels and frees up RAM space which can be used for other purposes.

The first step is downloading this zip file, which contains the rings conversion program (compiled with MinGW GCC), the program source code (written in C), and a text file containing the names of all the rings files. Extract this zip inside yourdisassemblypath/level/rings. The purpose of the rings conversion program is to take a Sonic 2-style rings data file, expand all ring groups and sort the file according to X position. rings.txt contains the names of all files to be converted - you can add more files to this list if you need to. The source code for the program is included so that it can be compiled for other platforms. Also, I suck pretty badly at C, so any suggestions to improve the program would be appreciated.

After you've done this, open up your disassembly. The first step is adding some equates. At the very top of the RAM equates section, add this:

Syntax Highlighted Code: ASM
```
Max_Rings = [color= #ff0000;]511[/color] [color= #adadad; font-style: italic;]; default. maximum number possible is 759[/color]

    [color= #00CC66;]if[/color] Max_Rings > [color= #ff0000;]759[/color]

    fatal [color= #CC33CC;]"Maximum number of rings possible is 759"[/color]

    [color= #00CC66;]endif[/color]

 

Rings_Space = (Max_Rings[color= #ff0000;]+1[/color])*[color= #ff0000;]2[/color]
```
Then, after the Ring_Positions equate, add

Syntax Highlighted Code: ASM
```
Ring_start_addr_ROM =        ramaddr( Ring_Positions+Rings_Space )

Ring_end_addr_ROM =        ramaddr( Ring_Positions+Rings_Space[color= #ff0000;]+4[/color] )

Ring_start_addr_ROM_P2 =    ramaddr( Ring_Positions+Rings_Space[color= #ff0000;]+8[/color] )

Ring_end_addr_ROM_P2 =        ramaddr( Ring_Positions+Rings_Space[color= #ff0000;]+12[/color] )

Ring_free_RAM_start =        ramaddr( Ring_Positions+Rings_Space[color= #ff0000;]+16[/color] )
```
Finally, after the Level_started_flag equate, add

Syntax Highlighted Code: ASM
```
Ring_start_addr_RAM =        ramaddr( [color= #ff0000;]$[/color][color= #ff0000;]FFFFF712[/color] )

Ring_start_addr_RAM_P2 =    ramaddr( [color= #ff0000;]$[/color][color= #ff0000;]FFFFF714[/color] )
```
The next step is to go to all the ring incbins (right after Off_Rings). Change all these incbins from something like "level/rings/EHZ_1.bin" to "level/rings/EHZ_1_INDIVIDUAL.bin". If your editor supports regular expression search and replace, this is as simple as searching for "level/rings/(.+)\.bin" (including the quotes) and replacing it with "level/rings/\1_INDIVIDUAL.bin" (once again including the quotes). If it doesn't, get a better text editor :P

After you've done this, the rings manager needs to be changed completely to read ring positions from ROM and ring statuses from RAM. The basic idea behind all the changes is to use two separate pointers, one for RAM and one for ROM. There are too many changes to explain individually though, so just replace everything from RingsManager to off_1736A (inclusive) with the contents of this file. By default, the rings manager includes S3K-type ring attraction, but for it to work properly you're going to have to either port the attracted ring yourself or use this ported object.

Finally, open up build.bat in the main disassembly folder, and after these lines:
```
REM // clear the output window
cls
```
add
```
REM // run the rings conversion program
cd level/rings
rings.exe
cd ../..
```
Whenever the rings conversion program runs, it outputs the name of each file it's going to convert, what errors (if any) were encountered during conversion, and at the end, the total number of successful and unsuccessful conversions. I've tested this out pretty thoroughly and it seems to work perfectly, but if you encounter any problems please post them in this topic. The only thing I've noticed so far is that 2P mode randomly lags sometimes, probably because it's slower to read ring data from ROM than from RAM.

The main advantage of doing this is that quite a bit of RAM is freed up ($1F0 bytes under default settings). If you want more free RAM or more rings, you can change the Max_Rings equate, and everything else will be adjusted automatically. The first byte of the free RAM space obtained this way is at Ring_free_RAM_start, and it continues all the way up to $EDFF. The free RAM can obviously be used for whatever you like - the most obvious uses I can think of right now are changing a ported Sonic 1 sound driver to use this RAM area to avoid having to mess around with underwater palette stuff, or setting up an object collision response list like in S3K to save some cycles in TouchResponse.
Weird routine in Sonic and Knuckles

22 February 2008 - 08:02 AM

I was going through Stealth's Sonic and Knuckles disassembly today when I noticed a weird routine located at $522 (right after JumpToSegaScreen). It starts off similar to the checksum error routine, but the main body does something completely different, which produces a weird multi-colour flickering effect. (To see the routine in action, enter the PAR code 0004C8:0522 in either S&K or S3K and restart the game)

Apologies if this is well known, but I searched and couldn't find any reference to it. The routine isn't referenced anywhere by the game code, but judging by its placement it seems to be an alternate checksum error screen. Pretty minor, but kinda cool all the same.