Bad Apple demo for SNES

Discussion of hardware and software development for Super NES and Super Famicom.

Moderator: Moderators

Forum rules
  • For making cartridges of your Super NES games, see Reproduction.
Post Reply
psycopathicteen
Posts: 2901
Joined: Wed May 19, 2010 6:12 pm

Bad Apple demo for SNES

Post by psycopathicteen » Sat Nov 16, 2013 1:28 pm

I think it is a good idea to make a Bad Apple demo for the SNES, to compete with the Genesis demo.

If the SNES demo video runs at 30fps fullscreen 2bpp, then it would take 7kB of DMA per frame. Since we do not need to use the OAM for this demo, we can DMA up to 6kB of data per frame. In order to fit 7kB of graphical patterns into 6kB, we can take advantage of solid colored tiles that are all black or all white.

I could program the dma loading scheme and pack-to-planar conversion, but I don't know how to do the video encoding part.

Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: Bad Apple demo for SNES

Post by Shiru » Sat Nov 16, 2013 1:43 pm

Why not.

I don't think a runtime packed-to-planar conversion is needed, though. Pretty much everything could be done in preprocessing.

A thing that may work on the SNES is interleaved bitplane updates. Like, one frame (1/60) we update bit 0, other frame bit 1. Will create some kind of motion blur, but may be acceptable. This will cut VRAM bandwidth, and the whole (bitplane of) the frame buffer could be DMAed, without breaking it into sequence of DMAs; tile update could be done in a RAM buffer.

tepples
Posts: 21707
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Bad Apple demo for SNES

Post by tepples » Sat Nov 16, 2013 2:15 pm

I reverse engineered how the 15fps version of Bad Apple for NES encodes video. The screen is divided into a grid of 16x30 blocks of 4x2 texels (2 tiles, 16x8 pixels). There are a handful of frames, mostly before the lyrics begin, that use a special code for "all blocks modified" (I-frame, also called keyframe) or "no blocks modified" (D-frame), but the vast majority of frames in Bad Apple are P-frames. Each P-frame has 4 bytes for which rows of tiles have at least one modified row, then 2 bytes for which blocks are modified, then 1 byte for each modified block.

What you're talking about doing is making all frames I-frames and using a bitwise encoding to store which tiles in a frame are black, which are white, and which have a pattern. Then you'd send the nametable and unique patterns for each frame. I could write prototype code in Python and 6502 for that; you could optimize it for native mode.

Would it be acceptable to use mosaic mode for 128x112 texels? That'd let you use H-flipped tiles, V-flipped tiles, and VH-flipped tiles to fit the entire display into 3.5 KiB per frame, at the cost of some chunkiness.

Or would it be acceptable to use 1bpp, with even tile columns using black, white, black, white, and odd tile columns using black, black, white, white? That'd cut it down to 7 KiB per frame, which fits in 6+1.

One thing I'd like to see where it freezes on the apple as Marisa is grabbing it is this:
Image
Then I wonder if the dropping cup that shatters could be changed into a dropping iPhone that shatters.

psycopathicteen
Posts: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Bad Apple demo for SNES

Post by psycopathicteen » Sat Nov 16, 2013 11:06 pm

I want it to be the same quality as the Genesis version, and using a smaller resolution would look bad in comparison.

A possible compression technique can be to do RLE on 8x1 slivers, with the tiles arranged vertically.

Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: Bad Apple demo for SNES

Post by Shiru » Sun Nov 17, 2013 12:05 am

RLE is certainly not something well suitable for video, even a silhouette one.

It needs interframe compression, i.e. storing only difference between frames, with a fixed dictionary of often used elements (solid black and solid white at the least), maybe with loss of details (replacing tiles with similar entries of the dictionary set), maybe with Huffman or LZ on top of all this.

tepples
Posts: 21707
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Bad Apple demo for SNES

Post by tepples » Sun Nov 17, 2013 7:00 am

The trolls will still claim superiority because the Genesis ROM runs in 320-pixel mode. One might have to use hires to beat that. Fortunately, FFmpeg has no problem scaling a 480x360 video to 512x224.

At this scale, I don't see how interframe compression would help much. Just about every non-solid tile would change each frame.

In any case, some sort of compression into an average of about 1280 bytes per frame would be needed to fit the thing into 8 MB. (At which point one of them is likely to haul out the Sega CD with every Touhou fan video known to man encoded in Cinepak.)

I took an equally spaced sample (one every 30 frames) and counted how many 8x8 pixel tiles were all black or all white. This is the key metric for figuring out how to fit everything in 12 KiB/frame of video memory bandwidth.
  • 512x224: 355099 of 394240 solid (90.07%)
  • 256x224: 171397 of 197120 solid (86.95%)

Have you tried disassembling the Genesis version to see how it manages 15:1 compression? I'm pretty sure it'll take more than just solid tile elimination. Perhaps there's some advantage to packed pixels.

But when watching a YouTube video of the Genesis version, I did notice a bunch of gray artifacts along certain near-horizontal edges. Perhaps this could be exploited to use one of four formats for each tile: solid black, solid white, 1bpp, or 2bpp.

There might also be a win in using RLE for runs of solid tiles. My sample showed that most solid tiles were after another solid tile.
  • 512x224: 355099 of 394240 solid (90.07%), 340911 solid after solid (86.47% of total)
  • 256x224: 171397 of 197120 solid (86.95%), 158682 solid after solid (80.50% of total)

Another cheat is to use fake widescreen. Encode only 168 pixels tall, keep tile rows outside this range black, then do some subtle horizontal scrolling over the affected area. This makes things look somewhat more cinematic, even if the trolls might call you out on reduced res.

I wonder how much of the video can be decomposed into areas where just two horizontal pixel runs differ from the background color. That might allow drawing much of the video with window registers.

And about the music: BRR (4.5 bits/sample) at 12 kHz mono for 220 seconds would take 1485000 bytes. I wonder to what extent the BRR data itself could be compressed.

User avatar
Bregalad
Posts: 7750
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: Bad Apple demo for SNES

Post by Bregalad » Sun Nov 17, 2013 9:13 am

I wonder to what extent the BRR data itself could be compressed.

Trust me, very poorly.
I have tested this. Even very advanced compressions such as BZIP2 will not compress anything when compressing BRR data.
The only thing you could possibly do is separate the BRR header data from the other data and compress the header efficiently, but even then you'll never compress more than 1/9 of the whole data which is very poor.

psycopathicteen
Posts: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Bad Apple demo for SNES

Post by psycopathicteen » Sun Nov 17, 2013 11:51 am

Shiru wrote:RLE is certainly not something well suitable for video, even a silhouette one.

It needs interframe compression, i.e. storing only difference between frames, with a fixed dictionary of often used elements (solid black and solid white at the least), maybe with loss of details (replacing tiles with similar entries of the dictionary set), maybe with Huffman or LZ on top of all this.


How do you store the differences between frames? Use motion vectors on tiles, and overlay a compressed tile over it?

tepples
Posts: 21707
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Bad Apple demo for SNES

Post by tepples » Sun Nov 17, 2013 12:06 pm

First what you need to do is see how the players for Bad Apple (Genesis) and the intro for Sonic 3D Blast work.

I'm not so sure you need motion compensation in the first place. Let's first figure out how to code keyframes efficiently. For example, I figured out how to encode tiles on the left or right edge of a silhouette at one-half bit per pixel. Each byte represents two rows, with nibbles taken from the following table:

Code: Select all

.byte $00, $80, $C0, $E0, $F0, $F8, $FC, $FE, $FF, $7F, $3F, $1F, $0F, $07, $03, $01

This allows efficient coding of edge tiles:

Code: Select all

0: . . . . . . . .
1: []. . . . . . .
2: [][]. . . . . .
3: [][][]. . . . .
4: [][][][]. . . .
5: [][][][][]. . .
6: [][][][][][]. .
7: [][][][][][][].
8: [][][][][][][][]
9: . [][][][][][][]
A: . . [][][][][][]
B: . . . [][][][][]
C: . . . . [][][][]
D: . . . . . [][][]
E: . . . . . . [][]
F: . . . . . . . []

More detailed edge tiles will likely need another method.

Or use "vector quantization", in which a representative set of a few tens of thousands of tiles are reused to form images.

psycopathicteen
Posts: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Bad Apple demo for SNES

Post by psycopathicteen » Mon Nov 18, 2013 4:49 pm

Okay, here is a simple algorithm to start with. Obviously it's not going to be the final algorithm, but it's a starting place.

mmrrrrrr

m: mode
00: solid black tile
01: solid white tile
10: 1 bpp tile
11: 2 bpp tile

r: run legnth (1-64)

BTW, aren't tiles in hi-res mode always 16 pixels across?

Shiru
Posts: 1161
Joined: Sat Jan 23, 2010 11:41 pm

Re: Bad Apple demo for SNES

Post by Shiru » Mon Nov 18, 2013 9:48 pm

Motion vectors is kind of overkill. Just check which tiles are changed (with amount threshold optionally) between frames, store them somehow efficiently enough, put the new tiles over previously decoded frame.

A dictionary I was talking about could contain not only solid colors, but also some common blocks, or blocks that could replace a number of similar looking blocks (this reduces quality, but saves room). Like, almost solid tile without few corner pixels, etc. Staticstics of common blocks could be collected from source frames before compression.

Stef
Posts: 251
Joined: Mon Jul 01, 2013 11:25 am

Re: Bad Apple demo for SNES

Post by Stef » Thu Nov 21, 2013 4:39 pm

If it can help, here are the sources of the genesis version :
https://dl.dropboxusercontent.com/u/933 ... ple_src.7z

Basically it does frame difference and only store tilemap and modified tiles, it mainly uses dictionaries to encode redundant tile data but there are severals compression schemes. I spent many time in building the video encoder but still it is not very efficient...
I used a tool to generate the dictionary tile unpack code, that explain why some part look weird and badly optimized (as some move.l #0x00000000, %d0 sequences).

I would really like to see what the SNES could do here but i am pessimist about the decompression part. It eats a lot of time on the 68000 and i don't see how the 65816 can compete here. Maybe by using simpler compression schemes but it would not fit in 8 MB then...
Still the MD offers some advantages as linear packed tile data and no bank stuff to deal with.
The SNES offer the native 2BPP mode that MD does not have but can be easily simulated using palette trick.

Good luck with your project, i really wish to see something coming from that :)

Sik
Posts: 1589
Joined: Thu Aug 12, 2010 3:43 am

Re: Bad Apple demo for SNES

Post by Sik » Sat Dec 28, 2013 1:09 pm

Bumping because I was away for almost a month.

First of all, let's remember there are multiple Bad Apple demos on the Mega Drive, OK? I don't know how MtChocolate's works, Stef released the source code to his, and then there's this which in my opinion is the best so far and the method is explained in that thread too (albeit no source code). The only glitches I noticed in the latter seemed to be more encoding bugs than actual limitations.

Also not sure how the 65816 competes in decompression, given that's something that usually works with small numbers so it shouldn't be at much of a disadvantage compared with the 68000. Register usage would be the biggest problem, in my opinion, and that depends a lot on the coder's skill.

By the way, at this rate we'll find a way to put videos on floppy disks =P

psycopathicteen
Posts: 2901
Joined: Wed May 19, 2010 6:12 pm

Re: Bad Apple demo for SNES

Post by psycopathicteen » Sat Dec 28, 2013 5:00 pm

I've been busy celebrating Christmas with family so I had limited time programming.

I think I'll use the method you posted since it's the simplest. I would need somebody to post a ROM with all the video data, because I don't know how to convert a video file.

Stef
Posts: 251
Joined: Mon Jul 01, 2013 11:25 am

Re: Bad Apple demo for SNES

Post by Stef » Sun Dec 29, 2013 4:13 am

Sik wrote:Bumping because I was away for almost a month.

First of all, let's remember there are multiple Bad Apple demos on the Mega Drive, OK? I don't know how MtChocolate's works, Stef released the source code to his, and then there's this which in my opinion is the best so far and the method is explained in that thread too (albeit no source code). The only glitches I noticed in the latter seemed to be more encoding bugs than actual limitations.

Also not sure how the 65816 competes in decompression, given that's something that usually works with small numbers so it shouldn't be at much of a disadvantage compared with the 68000. Register usage would be the biggest problem, in my opinion, and that depends a lot on the coder's skill.

By the way, at this rate we'll find a way to put videos on floppy disks =P


The version you are talking about is very interesting, first because it fits in 4MB (which is a big advantage to test on regular MD flash cart) and also because it is probably a far better candidate to port on SNES. The compression scheme is far lighter than my version (it does not even use the DMA) and can probably be ported to the SNES cpu without much troubles.
The drawback of this version is the blocky stuff you call glitches, they are due to the compression as you can't fit the whole video (and sound) in 4MB without loss (especially on such limited hardwares).
My 8 MB version is lossless for the video and that is quite an achievement (i believe), i initially had a 4MB lossless version (without sound) but i was not able to unpack it fast enough (between 10 and 30 FPS) so i had to use a simpler codec (i ended with 6.6 MB of video and 1.3 MB of sound).
The problem with the 65816 about decompression is not only the number of register but also the "fillrate" capabilities, still i guess a skilled coder could do some nice things with it :)

Post Reply