Another nametable compression format

This is an archive of a topic from NESdev BBS, taken in mid-October 2019 before a server upgrade.
View original topic
Another nametable compression format
by on (#142292)
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:
    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
Re: Another RLE nametable compression format
by on (#142293)
This sounds similar to RLEINC2 algorithm that is included in CompressTools
Re: Another RLE nametable compression format
by on (#142310)
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.
Re: Another RLE nametable compression format
by on (#142316)
Oh ok, so it's like some kind of RLEINC3, then :)
Re: Another RLE nametable compression format
by on (#142356)
It wouldn't take much to turn it into a LZ format...
Re: Another RLE nametable compression format
by on (#142358)
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.
Re: Another RLE nametable compression format
by on (#142367)
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.
Re: Another RLE nametable compression format
by on (#142368)
But then "RLE" in 4-bit Windows bitmaps could likewise be considered LZ with a 2-pixel window.
Re: Another nametable compression format
by on (#142697)
I changed my format a bit to reduce the decoder size to 110 bytes. On the side, I made a 46 byte PackBits decoder.
Re: Another nametable compression format
by on (#142703)
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:
; 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