It is currently Mon Nov 20, 2017 4:15 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 10 posts ] 
Author Message
PostPosted: Sun Mar 01, 2015 9:21 pm 
Offline
Formerly 43110
User avatar

Joined: Wed Feb 05, 2014 7:01 am
Posts: 313
Location: us-east
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


Last edited by JRoatch on Mon Mar 09, 2015 8:39 pm, edited 2 times in total.

Top
 Profile  
 
PostPosted: Mon Mar 02, 2015 1:34 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7271
Location: Chexbres, VD, Switzerland
This sounds similar to RLEINC2 algorithm that is included in CompressTools


Top
 Profile  
 
PostPosted: Mon Mar 02, 2015 10:44 am 
Offline
Formerly 43110
User avatar

Joined: Wed Feb 05, 2014 7:01 am
Posts: 313
Location: us-east
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.


Top
 Profile  
 
PostPosted: Mon Mar 02, 2015 1:55 pm 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7271
Location: Chexbres, VD, Switzerland
Oh ok, so it's like some kind of RLEINC3, then :)


Top
 Profile  
 
PostPosted: Tue Mar 03, 2015 12:35 pm 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 3950
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!


Top
 Profile  
 
PostPosted: Tue Mar 03, 2015 1:56 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19236
Location: NE Indiana, USA (NTSC)
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.


Top
 Profile  
 
PostPosted: Tue Mar 03, 2015 4:01 pm 
Offline
Formerly 43110
User avatar

Joined: Wed Feb 05, 2014 7:01 am
Posts: 313
Location: us-east
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.


Top
 Profile  
 
PostPosted: Tue Mar 03, 2015 4:11 pm 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19236
Location: NE Indiana, USA (NTSC)
But then "RLE" in 4-bit Windows bitmaps could likewise be considered LZ with a 2-pixel window.


Top
 Profile  
 
PostPosted: Mon Mar 09, 2015 8:42 pm 
Offline
Formerly 43110
User avatar

Joined: Wed Feb 05, 2014 7:01 am
Posts: 313
Location: us-east
I changed my format a bit to reduce the decoder size to 110 bytes. On the side, I made a 46 byte PackBits decoder.


Top
 Profile  
 
PostPosted: Mon Mar 09, 2015 9:29 pm 
Offline
User avatar

Joined: Sun Sep 19, 2004 9:28 pm
Posts: 3192
Location: Mountain View, CA, USA
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group