M68K compatible

[leuat]

Hi there! I'm the creator of TRSE (www.turborascal.com), and I'm currently in the process of adding automatic packing + extraction of M68K resources (for the Amiga + Atari ST 520). I'm trying to get your decompression code to work on the M68K, but I'm having some problems, and was wondering if you would be able to help me

if we mange to get this work, this will be the de-facto way of compressing resources in TRSE, and you'll naturally be credited in the TRSE credits

I've compared the (compressed) files to the compressed output from fc8, and since the files are identical - the problem must reside with the decompression method. I've tried changing it to M68000 compatibility, but can't make it work. I'm suspecting that by (slow) byte copying method is incorrect, or perhaps the " lea _FC8_LENGTH_DECODE_LUT(pc),a5" that I'm not really getting. Any help would be very .. helpful!

Btw the only major things that I've changed are marked with "CHANGES HERE"

Nicolaas

Here's what I've tried to modify :

procedure Decompress(in, out : global pointer of integer; outsize : global long);
begin
;//#pragma parameter __D0 fc8_decode(__A0, __A1, __D1)
asm("
;asm unsigned short fc8_decode(unsigned char* in, unsigned char* out, unsigned long outsize)
;   machine 68020
FC8_HEADER_SIZE EQU 8
FC8_DECODED_SIZE_OFFSET  EQU 4
    movem.l d1-d7/a0-a6,-(sp)
    move.l compression_in,a0    
    move.l compression_out,a1   
    move.l compression_outsize,d1   
    move.l #32000,d1    

    bra     _Init_Decode

;// lookup table for decoding the copy length-1 parameter
_FC8_LENGTH_DECODE_LUT:
    dc.b    2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17
    dc.b    18,19,20,21,22,23,24,25,26,27,28,34,47,71,127,255

;//-------------------------------------------------------------------------------
;// _GetUINT32 - alignment independent reader for 32-bit integers
;// a0 = in
;// d6 = offset
;// d7 = result
;//-------------------------------------------------------------------------------
_GetUINT32:
    move.b  (a0,d6.w),d7
    asl.w   #8,d7
    move.b  1(a0,d6.w),d7
    swap    d7
    move.b  2(a0,d6.w),d7
    asl.w   #8,d7
    move.b  3(a0,d6.w),d7
    rts

_Init_Decode:
    ;// check magic ID
    cmp.b   #'F',(a0)
    bne _fail
    cmp.b   #'C',1(a0)
    bne _fail
    cmp.b   #'8',2(a0)
    bne _fail
    cmp.b   #'_',3(a0)
    bne _fail

    ;// check decoded size - enough space in the output buffer?
    moveq   #FC8_DECODED_SIZE_OFFSET,d6
    bsr.s   _GetUINT32
    cmp.l   d7,d1               
    bhi _fail

    ;// advance a0 to start of compressed data
    lea     FC8_HEADER_SIZE(a0),a0

    ;// a5 = base of length decode lookup table
    lea     _FC8_LENGTH_DECODE_LUT(pc),a5
    ;lea        -110(pc),a5 ;// fix PC offset manually after assembly

    ;// helpful constants
    move.l  #$0000001F,d1
    move.l  #$00000007,d2
    move.l  #$00000001,d3
    move.l  #$0000003F,d4       ;// Main decompression loop
_mainloop:
    move.b  (a0)+,d6            ;// d6 = next token
    bmi.s   _BR1_BR2            ;// BR1 and BR2 tokens have the high bit set

    btst    #6,d6               ;// check bit 6 to see if this is a BR0 or LIT token
    bne.s   _BR0

;// LIT 00aaaaaa - copy literal string of aaaaaa+1 bytes from input to output   
_LIT:                           
    move.l  a0,a4               ;// a4 = source ptr for copy
    and.w   d4,d6               ;// AND with 0x3F, d6 = length-1 word for copy
    lea     1(a0,d6.w),a0       ;// advance a0 to the end of the literal string
    bra.s   _copyLoop

;// BR0 01baaaaa - copy b+3 bytes from output backref aaaaa to output
_BR0:                               
    move.b  d6,d5
    and.l   d1,d5               ;// AND with 0x1F, d5 = offset for copy = (long)(t0 & 0x1F)
    beq     _done               ;// BR0 with 0 offset means EOF

    move.l  a1,a4
    sub.l   d5,a4               ;// a4 = source ptr for copy

    move.b  (a4)+,(a1)+     ;// copy 3 bytes, can't use move.w. or move.l because src and dest may overlap
    move.b  (a4)+,(a1)+
    move.b  (a4)+,(a1)+
    btst    #5,d6               ;// check b bit
    beq.s   _mainloop
    move.b  (a4)+,(a1)+     ;// copy 1 more byte
    bra.s   _mainloop

_BR1_BR2:
    btst    #6,d6               ;// check bit 6 to see if this is a BR1 or BR2 token
    bne.s   _BR2

;// BR1 10bbbaaa'aaaaaaaa - copy bbb+3 bytes from output backref aaa'aaaaaaaa to output
_BR1:                           
    move.b  d6,d5
    and.l   d2,d5               ;// AND with 0x07 
    lsl.l   #8,d5
    move.b  (a0)+,d5            ;// d5 = offset for copy = ((long)(t0 & 0x07) << 8) | t1
    lsr.b   #3,d6
    and.w   d2,d6               ;// AND with 0x07
    addq.w  #2,d6               ;// d6 = length-1 word for copy = ((word)(t0 >> 3) & 0x7) + 1
    bra.s   _copyBackref

;// BR2 11bbbbba'aaaaaaaa'aaaaaaaa - copy lookup_table[bbbbb] bytes from output backref a'aaaaaaaa'aaaaaaaa to output
_BR2:   
    move.b  d6,d5
    and.w   d3,d5               ;// AND with 0x01
    swap    d5
    move.w  (a0)+,d5            ;// d5 = offset for copy = ((long)(t0 & 0x01) << 16) | (t1 << 8) | t2
    lsr.b   #1,d6
    and.w   d1,d6               ;// AND with 0x1F
    move.b  (a5,d6.w),d6        ;// d6 = length-1 word for copy = ((word)(t0 >> 3) & 0x7) + 1
    ;// fall through to _copyBackref

    ;// copy data from a previous location in the output buffer
    ;// d5 = offset from current buffer position    
_copyBackref:
    move.l  a1,a4
    sub.l   d5,a4               ;// a4 = source ptr for copy
    cmpi.l  #4,d5   
    blt.s   _nearCopy           ;// must copy byte-by-byte if offset < 4, to avoid overlapping long copies

    ;// Partially unrolled block copy. Requires 68020 or better.
    ;// Uses move.l and move.w where possible, even though both source and dest may be unaligned.
    ;// It's still faster than multiple move.b instructions
    ;// d6 = length-1
_copyLoop:  
    cmpi.w  #16,d6
    bge.s   _copy17orMore   
    jmp _copyBytes_leuat

; CHANGES HERE  

_copyBytes_leuat:
    cmp.w #0,d6
    beq.s _mainloop

;     subi.w #1,d6 ;; Copy 1 byte less

_topp_leuat:
  move.b (a4)+,(a1)+
  dbf d6,_topp_leuat
  bra       _mainloop

; CHANGES HERE

_copy17orMore:
        move.l  (a4)+,(a1)+
        move.l  (a4)+,(a1)+
        move.l  (a4)+,(a1)+
        move.l  (a4)+,(a1)+
        subi.w  #16,d6
        cmpi.w  #16,d6
        bge.s   _copy17orMore   
        jmp _copyBytes_leuat

_nearCopy:  
        cmpi.l  #1,d5
        beq.s   _copyRLE    
_nearLoop:
        move.b  (a4)+,(a1)+
        dbf     d6,_nearLoop
        bra     _mainloop

_copyRLE:
        ;// assumes length is at least 3
        move.b  (a4),(a1)+      ;// copy first byte
        btst    #0,d6
        beq.s   _doRLE          ;// branch if copy length is odd (because d6 is length-1)
        move.b  (a4),(a1)+      ;// copy second byte
_doRLE:
        subq.w  #2,d6
        lsr.w   #1,d6           ;// length = (length-2) / 2
        move.w  (a4),d5 
_rleLoop:
        move.w  d5,(a1)+
        dbf     d6,_rleLoop
        bra     _mainloop

_fail:
    moveq.w #0,d0               ;// result = 0
    bra     _exit   

_done:
    moveq.w #1,d0               ;// result = 1

_exit:  
    movem.l (sp)+,d1-d7/a0-a6
    ");
end;

[steve-chamberlin]

The details of this code have faded from my mind since four years ago. Since this is just vanilla 68K code, I'd suggest running your modified version in an emulator like Easy68K, and stepping through it while it performs the decompression to find the point where the output is wrong. From a quick glance, I think you need to modify the code at _copy17orMore to use move.b instead of move.l, because the address might be unaligned and I don't think the 68000 supports unaligned memory access. There may also be some unaligned memory access happening in _doRLE and _rleLoop. For best performance on the 68000, you probably need to check if the source and destination addresses are aligned, copy a few bytes individually with move.b if necessary, and then copy the rest with aligned move.w or move.l copies.

[steve-chamberlin]

The lea _FC8_LENGTH_DECODE_LUT(pc),a5 is intended to set a5 to point to the beginning of _FC8_LENGTH_DECODE_LUT table, in a position-independent way relative to the PC. I seem to recall I had some difficulty getting this to work right, so I inspected the assembled code or ran it in an emulator, and then manually set the -110 offset to make it work. If you've modified any code that's before that lea statement, then you'll probably need to change that -110 to another number.

[leuat]

Thanks for the feedback! If I don't get it working, I'll probably just re-implement the whole thing in TRSE (kinda slow!) and then convert each part to assembly. I'm guessing that the crashes is due to the alignment, so I'll start there.

[steve-chamberlin]

As a starting point to get it working, I think you could use _nearLoop for all the copying, and delete _copyLoop and its related code as well as deleting _copyRLE, _doRLE, and _rleLoop. nearLoop is the most basic form of copying, and everything else is just intended to optimize specific cases. But I'm now noticing there might also be unaligned access in a few other places, like move.w (a0)+,d5 in BR2.

[leuat]

hehe I almost got it working, but not quite yet... check out this video: https://www.irio.co.uk/div/almost.mp4 , but the image still has artifacts. Yeah I don't really care about speed right now (usually, decompressing a single resource - like an image - won't have that much penalty in terms of speed)

[leuat]

ok I'll try to remove those other copying mechanisms

[leuat]

got it! Works like a charm! Check out https://www.irio.co.uk/div/almost.mp4 (when the first effect transitions, it reverts to the raw uncompressed data and scrambles) - but - thanks a bunch! Slow as %(#/%, but who cares.

I've added support in TRSE for an automatic "compression" flag, so the user will be able to include any resource as such: .. myData : incbin("myImage.bin") compressed; // this will automatically compress +include the data

and within each M68K system, I've added a "compression" library so you can simply do "Compression::Decompress(myData, uncompressed_storage);"

Since I'm using (a modified version) of both your C++ compression / m68K decompression code, I'll add you to the list of credits of TRSE (again, www.turborascal.com). Also, I'll retain the header you have in the .h file. Let me know if I should add anything else

regards

Nicolaas

[steve-chamberlin]

Great, glad to hear it works. Have you read this: https://www.bigmessowires.com/2016/05/06/fc8-faster-68k-decompression/

FC8 is a balance between compression density and decompression speed. If decompression speed isn't very important for your purposes, then tighter compression is definitely possible. See the "tradeoffs" section of the linked blog post.

[steve-chamberlin]

Could you also submit your 68000 changes as a patch or a separate file? I'm sure others would benefit.

[leuat]

yup well I'll have to rewrite the library first, add some comments and make it more accessible. Also, since it is written as a library within TRSE, there will be some hybrid stuff - Pascal mixed with assembler. For for the most part, it should be simple to copy-paste. And yes, most of the decompression will be of images and demo effect data - stuff that can be done while the music is playing + the raster irq can do some simple effects, so no problem if the load time is 2s instead of 1 for an image. Would therefore love to have higher compression rates, especially since I'd like to keep things in RAM (as opposed to loading resources from disk).

[leuat]

The M68K decompression library (for the Atari ST) in TRSE can be found here : https://github.com/leuat/TRSE/blob/master/Publish/tutorials/ATARI520ST/tru/compression.tru