Author Topic: Shrinkler Z80 decrunch routine  (Read 3189 times)

0 Members and 1 Guest are viewing this topic.

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Shrinkler Z80 decrunch routine
« on: 11:42, 31 January 18 »
Hi there, i made a decrunch routine for the Amiga Shrinkler cruncher
This statistic cruncher is a LZMA stripdown algo so it is very efficiently but also very slow and need 2.5k of memory to store probabilities
To compare with exomizer and the wellknown Boubler Dash executable, you gain 10% over exomizer
The decrunch speed is not dependant of the target size but of the crunched size -> expect more than 15s for a 4K intro

From 350 bytes, Thanks to Hicks, Antonio Villena & Urusergi the routine were quickly sized down to 245 bytes

Madram joined the game and sent me his version, reoptimised and simplified (D4 in 8 bits) 209 bytes for a recall version!


Parameters to use with the version:
IX=source
DE=destination


NOTICE: The source is supposed to be used with an assembler dealing with a correct operator priority. This need adaptations for old assemblers (remove parenthesis, use division instead of shifting, ...)




Shrinkler Amiga/Linux/Windows executables here: http://crinkler.net/shrinkler45.zip
Official topic here: http://ada.untergrund.net/?p=boardthread&id=264


With the cruncher use the options -d -p -9
-d in order to crunch without header in output
-p to avoid shit with windows (don't care with Linux)
-9 to crunch better, the default parameter is not enough to have good results on small files


sample test with a crunched screen (rasm source)

Code: [Select]

buildsna
bankset 0
org #100
run #100
di
ld sp,#100
ld ix,#4000
ld de,#C000
breakpoint
call shrinkler_decrunch
breakpoint
jr $


include 'shrinkler.asm'


org #4000
incbin 'defaultscr.shr'
« Last Edit: 20:33, 07 April 18 by roudoudou »
use RASM, the best assembler ever made :p

I will survive

Offline Targhan

  • Supporter
  • 6128 Plus
  • *
  • Posts: 677
  • Country: fr
  • Liked: 602
Re: Shrinkler Z80 decrunch routine
« Reply #1 on: 11:56, 31 January 18 »
Wow! Well done!

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #2 on: 12:04, 31 January 18 »
thanks: updated 1st post with official cruncher executables and official Amiga topic
use RASM, the best assembler ever made :p

I will survive

Offline krusty_benediction

  • CPC664
  • ***
  • Posts: 100
  • Country: fr
  • Liked: 81
Re: Shrinkler Z80 decrunch routine
« Reply #3 on: 12:28, 31 January 18 »
I'll look at it as soon as possible.
However with 1min to fill the banks, I doubt I'll use it

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #4 on: 12:33, 31 January 18 »
I'll look at it as soon as possible.
However with 1min to fill the banks, I doubt I'll use it


In fact i misled.


The decrunch speed is not dependant of the target size but of the crunched size  ;D  roughly 5000 nops per crunched bytes


My test was 2748 bytes crunched so 13.7s for 16k. Once the bits are decoded, that's just ldi or ldir


use RASM, the best assembler ever made :p

I will survive

Offline Urusergi

  • CPC6128
  • ****
  • Posts: 157
  • Country: es
  • Liked: 234
Re: Shrinkler Z80 decrunch routine
« Reply #5 on: 16:50, 31 January 18 »
I may send a commented version if people want to try to optimize the code

Yes, please, please  :)

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #6 on: 17:39, 31 January 18 »
Yeah! I gain 2 bytes more with an optim!


Updated the first post with new source and commented version
use RASM, the best assembler ever made :p

I will survive

Offline Ast

  • 6128 Plus
  • ******
  • Posts: 884
  • Country: fr
    • Amstrad cpc Website of Ast/iMPACT
  • Liked: 597
Re: Shrinkler Z80 decrunch routine
« Reply #7 on: 18:08, 31 January 18 »

Hi there, i made a decrunch routine for the Amiga Shrinkler cruncher
This statistic cruncher is a LZMA stripdown algo so it is very efficiently but also very slow and need memory to store probabilities
To compare with exomizer and the wellknown Boubler Dash executable, you gain 10% over exomizer
But...
But the decrunch routine is 180 bytes bigger and the buffer needs 3Kb anywhere in the memory
Speed decrunch performance is roughly 1kb/s
The decrunch speed is not dependant of the target size but of the crunched size -> 5000 nops per crunched byte
Do not hesitate to report me bugs
I may send a commented version if people want to try to optimize the code
The version here is supposed to be compliant with all assemblers


Shrinkler Amiga/Linux/Windows executables here: http://crinkler.net/shrinkler45.zip
Official topic here: http://ada.untergrund.net/?p=boardthread&id=264
Well done !
_____________________

Ast/iMP4CT. "By the power of Grayskull, i've the power"


Amstrad Plus French Forum

All friends are welcomed !

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #8 on: 19:34, 01 February 18 »
New file in the first post shrinkler_z80_330.asm



I re-wrote the variables initialization
I modified the spread of flags
I factored some call parameters
Finally, I re-wrote the many calls to the virtual registry D6


The result is that the binary is now 330 bytes  8)
use RASM, the best assembler ever made :p

I will survive

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #9 on: 23:44, 01 February 18 »
With Hicks advices, some size optimisations at the end -> now 326 bytes  ;D


First post updated with source
use RASM, the best assembler ever made :p

I will survive

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #10 on: 00:08, 02 February 18 »
323  ;D  319


« Last Edit: 00:44, 02 February 18 by roudoudou »
use RASM, the best assembler ever made :p

I will survive

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #11 on: 22:21, 02 February 18 »
The current version is now 304 bytes  :D
use RASM, the best assembler ever made :p

I will survive

Offline antoniovillena

  • CPC664
  • ***
  • Posts: 86
  • Liked: 87
Re: Shrinkler Z80 decrunch routine
« Reply #12 on: 01:11, 03 February 18 »
The current version is now 304 bytes  :D


-2 bytes


Code: [Select]

shrinkler_decrunch:
        ld      (shrinkler_a5+1), hl


        ; Init range decoder state
        ld      hl, shrinkler_dr+1536*2+8
        ld      bc, 1536*2
        ld      (hl), c
        inc     hl
        ld      (hl), $80
        ld      de, shrinkler_dr+1536*2+7
        lddr
        ld      c, $08
        dec     hl
        lddr
        inc     (hl)


shrinkler_lit:

Offline antoniovillena

  • CPC664
  • ***
  • Posts: 86
  • Liked: 87
Re: Shrinkler Z80 decrunch routine
« Reply #13 on: 02:02, 03 February 18 »
Another -2 bytes


Code: [Select]

shrinkler_lit:
        ; Literal
        scf
shrinkler_getlit:
        call    nc, shrinkler_getbit
        ld      hl, shrinkler_d6
        rl      (hl)
        jr      nc, shrinkler_getlit
shrinkler_a5:
        ld      de,  $1234
        ldi

Offline antoniovillena

  • CPC664
  • ***
  • Posts: 86
  • Liked: 87
Re: Shrinkler Z80 decrunch routine
« Reply #14 on: 02:04, 03 February 18 »
Easy -1 byte


Code: [Select]
        jr      nc, shrinkler_lit


        ; Reference
        sbc     hl, hl
        call    shrinkler_altgetbit

Offline ervin

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.147
  • Country: au
    • index.php?action=treasury
  • Liked: 780
Re: Shrinkler Z80 decrunch routine
« Reply #15 on: 09:34, 03 February 18 »
@roudoudo - have the optimisations found so far resulted in any speed increases?
My entry for the CPCRetroDev 2017 Competition http://www.cpcwiki.eu/forum/programming/my-cpcretrodev-2017-entry/
FAST line drawing in CPCtelera http://www.cpcwiki.eu/forum/programming/drawing-lines-with-cpctelera-sdcc/
RUNCPC My entry for the CPCRetroDev 2015 Competition http://www.pouet.net/prod.php?which=66566

Offline Hicks

  • CPC664
  • ***
  • Posts: 71
  • Country: fr
    • Vanity
  • Liked: 122
Re: Shrinkler Z80 decrunch routine
« Reply #16 on: 11:50, 03 February 18 »
I submitted to Roudoudou a lot of optimisations by PM, but I will write here now if other people work on it too (hi antonio!).

Code: [Select]
shrinkler_nonewword   
    ld (shrinkler_d4),de : ld (shrinkler_d4+2),hl ; written in little endian
    ex af,af' ; retrieve previous carry
    ld hl,(shrinkler_d2) : adc hl,hl : ld (shrinkler_d2),hl
    ld hl,(shrinkler_d3) : add hl,hl : ld (shrinkler_d3),hl ; 0x22

Becomes (for -1) :

Code: [Select]
shrinkler_nonewword   
    ld (shrinkler_d4),de : ld (shrinkler_d4+2),hl ; written in little endian
    ex af,af'
    ld hl,shrinkler_d2+1
    rl (hl) : dec hl : rl (hl) : dec hl
    sla (hl) : dec hl : rl (hl)

But you must modify the order of the labels : d3 - d6 - d2 becomes d3 - d2 - d6.
« Last Edit: 12:02, 03 February 18 by Hicks »

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #17 on: 11:52, 03 February 18 »
@roudoudo - have the optimisations found so far resulted in any speed increases?

The speed gain/loss is not significant. Thanks Antonio for the optims!
use RASM, the best assembler ever made :p

I will survive

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #18 on: 12:01, 03 February 18 »
Hicks, the registers order of d3 (first) & d6 (last) can't be changed without changing the init


I updated first post with 299 bytes version
use RASM, the best assembler ever made :p

I will survive

Offline Hicks

  • CPC664
  • ***
  • Posts: 71
  • Country: fr
    • Vanity
  • Liked: 122
Re: Shrinkler Z80 decrunch routine
« Reply #19 on: 12:04, 03 February 18 »
I modified my post: the same tricks works with d3 - d2 - d6 order...
First must be d3 and last d4 (no d6), so we can reverse d2 / d6.
« Last Edit: 12:19, 03 February 18 by Hicks »

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #20 on: 12:28, 03 February 18 »
... (2s)
« Last Edit: 12:30, 03 February 18 by roudoudou »
use RASM, the best assembler ever made :p

I will survive

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #21 on: 14:43, 03 February 18 »
ok, i succeed to make the rl optim


(updated the first post)




Code: [Select]

        ld hl,shrinkler_d3
        sla (hl) : inc hl : rl (hl) : inc hl
        ex af,af' ; retrieve previous carry
        rl (hl) : inc hl : rl (hl)
use RASM, the best assembler ever made :p

I will survive

Offline Hicks

  • CPC664
  • ***
  • Posts: 71
  • Country: fr
    • Vanity
  • Liked: 122
Re: Shrinkler Z80 decrunch routine
« Reply #22 on: 15:06, 03 February 18 »
This part:

Code: [Select]
shrinkler_readoffset:
    ld a,3
    call shrinkler_getnumber
    ; retour systématique avec carry et HL=BC
    ld hl,2
    xor a
    sbc hl,bc

Since Carry is always=1, then:

Code: [Select]
shrinkler_readoffset:
    ld a,3
    call shrinkler_getnumber
    ; retour systématique avec carry et HL=BC
    ld hl,2+1    ; +1 in order to compensate Carry
    sbc hl,bc

Then -1 byte
« Last Edit: 15:22, 03 February 18 by Hicks »

Offline Hicks

  • CPC664
  • ***
  • Posts: 71
  • Country: fr
    • Vanity
  • Liked: 122
Re: Shrinkler Z80 decrunch routine
« Reply #23 on: 15:18, 03 February 18 »
Another -1 byte:

Code: [Select]
shrinkler_d5:    ld de,#0101
    ld hl,(shrinkler_a5+1)
    push hl
    add hl,de
    pop de   

Becomes:

Code: [Select]
shrinkler_d5: ld hl,#0101
    ld de,(shrinkler_a5+1)
    add hl,de

A lot of CPU saved too!

Offline roudoudou

  • 464 Plus
  • *****
  • Posts: 493
  • Country: fr
    • urban exploration
  • Liked: 549
Re: Shrinkler Z80 decrunch routine
« Reply #24 on: 15:24, 03 February 18 »
I like where this tread is going  :)


296!
use RASM, the best assembler ever made :p

I will survive