www.retrosoftware.co.uk
http://www.retrosoftware.co.uk/forum/

Compression - Run Length Encoding
http://www.retrosoftware.co.uk/forum/viewtopic.php?f=73&t=695		 Page 1 of 1
Author:  PitfallJ [ Thu Oct 20, 2011 11:06 am ]
Post subject:  Compression - Run Length Encoding
Hi,

I've been recently playing around with file compression.

Here's a 7-bit run length decoder in 6502 and associated encoder/decoder in 'c'.

I pick up a byte - if bit 7 is set I assume it is a count where count = 2+(byte & $7F) else I assume it is a unique value and pass it on.
$FF marks the termination.

Not a bad saving! ( I ran it on some teletext pages. )

If anyone can improve it - please show me.

I do wish I could use 16 bit macros like ADD16 - 6502 code becomes so long winded.
Is there any advantage to using INC, BNE, INC instead off the adds I use?

On a related note - has anyone got a 6502 Huffman they could post?


Code:
;
 ;   UNRLE7
 ;      P. Jones
 ;


 source = $70
 dest   = &72
 tempc  = $74


 ._UNRLE7:

 .next:   LDY #0
   LDA (source),Y
   BMI run

   STA (dest),Y

   LDA source
   CLC
   ADC #1
   STA source
   LDA source+1
   ADC #0
   STA source+1

   LDA dest
   CLC
   ADC #1
   STA dest
   LDA dest+1
   ADC #0
   STA dest+1

   JMP next

.run:   CMP #$FF
   BEQ exit11

   AND #&7F
   CLC
   ADC #2
   TAX
   ; get next repeater byte
   INY
   LDA (source),Y
   STA tempc
   DEY

   LDA source
   CLC
   ADC #2
   STA source
   LDA source+1
   ADC #0
   STA source+1


 .loop:   
   LDA tempc
    STA (dest),Y
   INY
   DEX
   BNE loop

   TYA
   CLC
   ADC dest
   STA dest
   LDA dest+1
   ADC #0
   STA dest+1

   JMP next

.exit11:
   RTS



Attachment:
Rle7.zip [867 Bytes]
Downloaded 3 times
Author:  TomW [ Thu Oct 20, 2011 12:02 pm ]
Post subject:  Re: Compression - Run Length Encoding
PitfallJ wrote:
Is there any advantage to using INC, BNE, INC instead off the adds I use?


Yes, INC,BNE,INC is shorter + quicker.
Author:  RichTW [ Thu Oct 20, 2011 2:24 pm ]
Post subject:  Re: Compression - Run Length Encoding
PitfallJ wrote:
I do wish I could use 16 bit macros like ADD16 - 6502 code becomes so long winded.

If you're using BeebAsm for this, now you can use macros (since release 1.05 I think).

e.g.
Code:
; Add immediate constant 'val' to addr (optimised for various types of constant)
MACRO ADDI16 addr, val
    IF val=1
        INC addr
        BNE noincaddrhi1
        INC addr+1
        .noincaddrhi1
    ELIF (val AND &FFFF)<256
        CLC
        LDA addr
        ADC #val
        STA addr
        BCC noincaddrhi2
        INC addr+1
        .noincaddrhi2
    ELIF (val AND &FFFF)>=256
        CLC
        LDA addr
        ADC #LO(val AND &FFFF)
        STA addr
        LDA addr+1
        ADC #HI(val AND &FFFF)
        STA addr+1
    ENDIF
ENDMACRO

; Add addr2 to addr
MACRO ADD16 addr, addr2
    CLC
    LDA addr
    ADC addr2
    STA addr
    LDA addr+1
    ADC addr2+1
    STA addr+1
ENDMACRO

Code:
; Example of use
; (scrn) contains screen address
    LDY #0
    STA (scrn),Y
    ADDI16 scrn, 640    ; move to next row

The conditionals in the macro will be evaluated each time it is used, and so the optimal code will be generated. Beware that macros which assemble different code depending on the parameters passed in can set the flags inconsistently upon return (e.g. the ADDI16 macro sets C differently depending on the 'val' parameter), so be careful if you rely on this.
Author:  tricky [ Thu Oct 20, 2011 6:10 pm ]
Post subject:  Re: Compression - Run Length Encoding
While you have the macro, you might as well add the LSB=0 optimisations.

There is also SWEET16.

Richard
Author:  PitfallJ [ Fri Oct 21, 2011 5:32 pm ]
Post subject:  Macros in Beebasm
!!MACROS!! Terrific! You've made my day.

Now I have MOV, ADD16, CP16 and Long Jumps (JEQ etc.) - much easier to program.

INC16 and CMP16 don't seem to work - is it because they contain an existing keyword.

Sorry to be picky but it would be even cooler if it could tell the difference between:
ADD16 label,#23 and ADD16 label,address.

At the moment I use ADD16 (for immediates) and ADDM16 (for memory).
Also the
.label thing drives me crazy - I'm just too used to the 'standard'

label:

At lease it accepts

.label:

Thanks again

- PJ
Author:  RichTW [ Fri Oct 21, 2011 8:37 pm ]
Post subject:  Re: Macros in Beebasm
PitfallJ wrote:
INC16 and CMP16 don't seem to work - is it because they contain an existing keyword.

Yes, exactly. They are equivalent to INC &10 and CMP &10 respectively (because BeebAsm, like BBC BASIC, doesn't require spaces after its keywords). Maybe I'll make a change so that invoking macros takes priority over assembler opcodes, so that the likes of INC16 work ok (this would also be more consistent, given that it's possible to define macros with names like these). My best suggestion for now would be to prefix all macro names with an underscore character, both so that they stand out, and so there's no clashes with reserved words.

Quote:
Sorry to be picky but it would be even cooler if it could tell the difference between:
ADD16 label,#23 and ADD16 label,address.

When I was implementing macros, I wondered about this, but in the end I figured it didn't make sense. In your example, you'd want it to generate different code depending on whether it was an immediate constant or another address (due to the way the MSB would be handled - in the first, it'd be HI(val) and in the second it'd be addr+1), so there'd be no advantage in 'unifying' the two macros in this way. It could be done by implementing 'overloading' of macro definitions, i.e. the same name but with different parameter types, but this would just be getting far more complicated than would be worthwhile!

Quote:
Also the
.label thing drives me crazy - I'm just too used to the 'standard'

label:

At lease it accepts

.label:

When I wrote BeebAsm, my original intention was to create something which would let me write 6502 assembler in exactly the same way as I used to in BBC BASIC, in particular putting multiple instructions on one line, separated by colons. I couldn't find any other 6502 assembler that allowed this, and so I wrote my own! So that's why all the conventions are as per BBC BASIC, right down to the .label syntax, and even the names of the functions. It even uses P% (as well as the more conventional '*') to return the address currently being assembled at.

Of course, since those early days, it's grown quite a bit, and it's true that some of the original features, such as not requiring whitespace, aren't really all that useful.
Author:  jgharston [ Sun Nov 27, 2011 12:58 pm ]
Post subject:  Re: Compression - Run Length Encoding
PitfallJ wrote:
Not a bad saving! ( I ran it on some teletext pages. )
If anyone can improve it - please show me.
I used a run-length encoding in the *ScrSave/*ScrLoad commands. They just use simple RLE where everything is a two-byte pair of byte,length. Quite ok for screen images where almost everything is runs of similar data. Screens compressed with this are at http://mdfs.net/Mirror/Archive/JGH/ and http://mdfs.net/Mirror/Image/JGH/
Author:  DaveF [ Thu Sep 13, 2012 7:35 am ]
Post subject:  Re: Compression - Run Length Encoding
Don't forget there's also Pu Crunch which I have found useful :)
Page 1 of 1 All times are UTC [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/