Another nametable compression format

A place where you can keep others updated about your NES-related projects through screenshots, videos or information in general.

Moderator: Moderators

Post Reply
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Another nametable compression format

Post by JRoatch »

While working on redoing Solar Wars I decided to take the whole month of February researching nametable compression. I gathered a bunch of raw picture data to develop another nametable compression format. I don't know what to name it so I currently call it "Nametable format D".

Edit: I've changed my format, to accommodate a few more features. The compression ratio is not impacted much.

Code: Select all

    000nnnnn ...    : 32-N literal bytes.
    00111111        : End stream.
    00111110 xx yy  : * Set PPU_ADDR to yyxx
    001nnnnn xx yy  : For 32-N times, emit alternately X and Y.
    01011111        : * toggle BG transperency. (initially opaque)
    010nnnnn xx     : 32-N run of X.
    01111111 xx     : Set BG to X. (initially BG = 0)
    011nnnnn xx     : 32-N incrementing run starting at X.
    1nnnnnnn        : 128-N Run of BG.
    * = Not present in lite variant.
On average it saves about 710 (69%) bytes per nametable. That's compared to PackBits which saves about 562 (55%) bytes.

A decoder used to be attached, but there's not much sense in attaching a decoder without an encoder. You can find the current encoder plus the data I worked off of at https://jroatch.nfshost.com/2015/nes/na ... ession.zip
Last edited by JRoatch on Mon Mar 09, 2015 8:39 pm, edited 2 times in total.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Another RLE nametable compression format

Post by Bregalad »

This sounds similar to RLEINC2 algorithm that is included in CompressTools
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Another RLE nametable compression format

Post by JRoatch »

Bregalad wrote:This sounds similar to RLEINC2 algorithm that is included in CompressTools
It is similar because I directly copied the double byte run idea from RLEINC2.
The improvements in decoder simplicity and stream size comes from carefully arranging the code points and reducing the space taken by ordinary runs.
User avatar
Bregalad
Posts: 8055
Joined: Fri Nov 12, 2004 2:49 pm
Location: Divonne-les-bains, France

Re: Another RLE nametable compression format

Post by Bregalad »

Oh ok, so it's like some kind of RLEINC3, then :)
User avatar
Dwedit
Posts: 4922
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Another RLE nametable compression format

Post by Dwedit »

It wouldn't take much to turn it into a LZ format...
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Another RLE nametable compression format

Post by tepples »

It already is an LZ format, just with a window length of 2. The limiting factor for LZ on NES is work RAM for decompression, as window lengths longer than your existing VRAM transfer buffer become impractical. Random read access to video memory isn't very efficient, and video memory readback is in fact unreliable while a DPCM sample is playing.
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Another RLE nametable compression format

Post by JRoatch »

Initially I did think I would use a 64 byte window with some metatile interleaving, but I found that a 2 byte window worked quite well. I should probably take a look at aPLib and LZMPi (mentioned a while ago in this forum) to see how that's dome and how well they work.

The thing that's currently annoying me with my current format is that it leaves way too many '0' bytes in the literals.
And yes I should probably stop calling it RLE.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Another RLE nametable compression format

Post by tepples »

But then "RLE" in 4-bit Windows bitmaps could likewise be considered LZ with a 2-pixel window.
JRoatch
Formerly 43110
Posts: 422
Joined: Wed Feb 05, 2014 7:01 am
Contact:

Re: Another nametable compression format

Post by JRoatch »

I changed my format a bit to reduce the decoder size to 110 bytes. On the side, I made a 46 byte PackBits decoder.
User avatar
koitsu
Posts: 4201
Joined: Sun Sep 19, 2004 9:28 pm
Location: A world gone mad

Re: Another nametable compression format

Post by koitsu »

I used a simple/basic RLE compression mechanism (for CHR data) in my FF2e intro, which I've been revamping as of late. I was going for size (due to limited ROM space) and not speed. It got a 1264 byte CHR file down to 610 bytes. One drawback is that it can only handle lengths between 0 and 127. Here's the code, since I figure it would benefit someone somewhere:

Code: Select all

; Copyright (C) 1998-2015 Jeremy Chadwick. All rights reserved.
;
; Redistribution and use in source and binary forms, with or without
; modification, are permitted provided that the following conditions
; are met:
;
; 1. Redistributions of source code must retain the above copyright
;    notice, this list of conditions and the following disclaimer.
; 2. Redistributions in binary form must reproduce the above copyright
;    notice, this list of conditions and the following disclaimer in the
;    documentation and/or other materials provided with the distribution.
;
; THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
; ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
; IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
; ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
; FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
; DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
; OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
; HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
; OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
; SUCH DAMAGE.

; This is an RLE decompression routine for CHR data.  LOGO_ADDR (a
; 16-bit pointer) is used to reference the base address of the data in
; question.  The format of the data is simple:
;
; Offset 0: Count: Number of times Value should be repeated.
;           If the MSB is set, indicates this is the last entry to be
;           handled.  Number of times is therefore limited to $00-7F
; Offset 1: Value: Raw 8-bit value (i.e. tile number)
; ...repeat...
;
; An example set of compressed data would be:
;
;   .byte $10, $32   ; Repeat sixteen ($10) times the value $32
;   .byte $06, $FA   ; Repeat six ($06) times the value $FA
;   .byte $9F, $1D   ; Repeat thirty-one ($1F) times the value $1D, then done
;
.proc Load_RLE_Data
L1: ldy #0
    lda (LO_ADDR),y          ; Get Count from data structure
    pha                      ; ...and temporarily back it up for later use
    and #$7f                 ; Strip off the MSB
    tax                      ; ...and use the result as our loop counter
    iny                      ; Move on to next byte in data structure
    lda (LO_ADDR),y          ; Get Value from data structure
:   sta $2006                ; Write it $2006
    dex                      ; Decrement the iteration count (for this value)
    bne :-                   ; ...and repeat writing until 0
    pla                      ; Restore the original Count value
    bmi Done                 ; If MSB is set (negative flag set), we're done
    lda LO_ADDR              ; ...otherwise increment LO_ADDR (low byte) by 2
    clc
    adc #2
    sta LO_ADDR              ; ...if the ADC set the carry (indicating unsigned
    bcc :+                   ; ...overflow), then we know we wrapped ($FF->00)
    inc LO_ADDR+1            ; ...and need to increment the high byte
:   jmp L1                   ; Move on to the next entry
Done:
    rts                      ; ...and we're completely done
.endproc
Post Reply