News:

Printed Amstrad Addict magazine announced, check it out here!

Main Menu
avatar_roudoudou

Shrinkler Z80 decrunch routine

Started by roudoudou, 10:42, 31 January 18

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

antoniovillena

Another -1


shrinkler_readbit:
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2) ; lu en little endian
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
        ld      e, 4
        ex      af, af'
        add     ix, de
        ex      af, af'         ; injecte la CARRY précédente
        ld      l, (ix-1)
        ld      h, (ix-2)
        ld      e, (ix-3)
        ld      d, (ix-4)       ; DEHL=(a4) nouvelle valeur lue en big endian!
        adc     hl, hl
        ex      hl, de
shrinkler_rb1:
        adc     hl, hl
shrinkler_rb2:
        ex      af, af'         ; save carry
        ld      (shrinkler_d4+2), hl    ; mais écrite en little endian
        ld      (shrinkler_d4), de
        ld      hl, shrinkler_d3
        rl      (hl)
        inc     hl
        rl      (hl)
        inc     hl
        ex      af, af'                 ; retrieve previous carry
        rl      (hl)
        inc     hl
        rl      (hl)
        jr      shrinkler_getbit1

antoniovillena

Sorry again. I put whole file because many changes. 276 bytes.




shrinkler_getnumber:
        ; Out: Number in HL
        ld      bc, 1
        ld      hl, shrinkler_d6+2
        ld      (hl), a
        dec     hl
        ld      (hl), b
shrinkler_numberloop:
        inc     (hl)
        inc     (hl)
        call    shrinkler_getbit
        jr      c, shrinkler_numberloop
        dec     (hl)
shrinkler_bitsloop:
        call    shrinkler_getbit
        rl      c
        rl      b
        dec     (hl)
        dec     (hl)
        ret     m
        jr      shrinkler_bitsloop


;--------------------------------------------------
        ; Out: Bit in C
shrinkler_readbit:
        ld      hl, (shrinkler_d3+1)
        add     hl, hl
        ld      (shrinkler_d3+1), hl
shrinkler_d4l:
        ld      hl, 0
        adc     hl, hl
        ex      de, hl
shrinkler_d4h:
        ld      hl, $8000
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
        ld      e, 4
        ex      af, af'
        add     ix, de
        ex      af, af'         ; injecte la CARRY précédente
        ld      l, (ix-1)
        ld      h, (ix-2)
        ld      e, (ix-3)
        ld      d, (ix-4)       ; DEHL=(a4) nouvelle valeur lue en big endian!
        adc     hl, hl
        ex      hl, de
shrinkler_rb1:
        adc     hl, hl
shrinkler_rb2:
        ld      (shrinkler_d4h+1), hl    ; mais écrite en little endian
        ld      (shrinkler_d4l+1), de
shrinkler_d2:
        ld      hl, 0
        adc     hl, hl
        ld      (shrinkler_d2+1), hl
        jr      shrinkler_getbit1


;--------------------------------------------------
shrinkler_getkind:
        ;Use parity as context
        ld      (shrinkler_a5+1), de
        xor     a
        ld      l, a
        inc     a
        and     e
        ld      h, a
shrinkler_altgetbit:
        ld      (shrinkler_d6+1), hl


shrinkler_getbit:
        exx
shrinkler_getbit1:
        ld      a, (shrinkler_d3+2)     ; obligé de relire les 8 bits forts la valeur...
        add     a, a
        jr      nc, shrinkler_readbit


shrinkler_d6:
        ld      hl, 0
        add     hl, hl
        ld      de, shrinkler_pr+2        ; cause -1 context
        add     hl, de
        push    hl
        ld      e, (hl)
        inc     hl
        ld      d, (hl)
        ; D1 = One prob
        push    de
        ld      b, d
        ld      c, e            ; bc=de=d1 / hl=a1
        ld      a, $e1
shrinkler_shift4:
        srl     b
        rr      c
        add     a, a
        jr      c, shrinkler_shift4
        ex      hl, de
        sbc     hl, bc          ; hl=d1-d1/16
        ex      hl, de
        ld      (hl), d
        dec     hl
        ld      (hl), e
        pop     bc              ; bc=d1 initial
shrinkler_d3:
        ld      de, 1
; input: DE x BC
; output: DEHL
        sbc     hl, hl
shrinkler_muluw:
        add     hl, hl
        rl      e
        rl      d
        jr      nc, shrinkler_cont
        add     hl, bc
        jr      nc, shrinkler_cont
        inc     de
shrinkler_cont:
        dec     a
        jr      nz, shrinkler_muluw
        ld      hl, (shrinkler_d2+1)
        xor     a
        sbc     hl, de
        pop     bc
        jr      nc, shrinkler_zero


shrinkler_one:
        ; onebrob = 1 - (1 - oneprob) * (1 - adjust) = oneprob - oneprob * adjust + adjust
        ; move+add out of order!
        ld      a, (bc)
        sub     1
        ld      (bc), a
        inc     bc
        ld      a, (bc)
        sbc     a, $f0                  ; (a1)+#FFF
        ld      (bc), a
        ex      de, hl
        jr      shrinkler_d3ret


shrinkler_decrunch:
        ld      (shrinkler_a5+1), hl


        ; Init range decoder state
        ld      hl, shrinkler_pr+1
        ld      bc, 1536*2
        ld      (hl), $80
        dec     hl
        ld      (hl), c
        ld      de, shrinkler_pr+2
        ldir


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


        ; After literal
        call    shrinkler_getkind
        jr      nc, shrinkler_lit


        ; Reference
        sbc     hl, hl
        call    shrinkler_altgetbit
        jr      nc, shrinkler_readoffset
shrinkler_readlength:
        ld      a, 4
        call    shrinkler_getnumber
shrinkler_d5:
        ld      hl, $0101
shrinkler_a5:
        ld      de, 0
        add     hl, de
        ldir


        ; After reference
        call    shrinkler_getkind
        jr      nc, shrinkler_lit
shrinkler_readoffset:
        ld      a, 3
        call    shrinkler_getnumber
        ; return without carry and HL=BC
        ld      hl, 2
        sbc     hl, bc
        ld      (shrinkler_d5+1), hl
        jr      nz, shrinkler_readlength


shrinkler_zero:
        ; oneprob = oneprob * (1 - adjust) = oneprob - oneprob * adjust
        ld      (shrinkler_d2+1), hl
        ld      hl, (shrinkler_d3+1)
        sbc     hl, de


shrinkler_d3ret:
        ld      (shrinkler_d3+1), hl
        exx
        ret


shrinkler_pr EQU $






antoniovillena

The 276 version only allow one call to the routine. For a reentrant version take the latest 284 one and change this routine. You will have 283 bytes version.




shrinkler_readbit:
        ld      hl, (shrinkler_d3)
        add     hl, hl
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2) ; lu en little endian
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
        ld      e, 4
        ex      af, af'
        add     ix, de
        ex      af, af'         ; injecte la CARRY précédente
        ld      l, (ix-1)
        ld      h, (ix-2)
        ld      e, (ix-3)
        ld      d, (ix-4)       ; DEHL=(a4) nouvelle valeur lue en big endian!
        adc     hl, hl
        ex      hl, de
shrinkler_rb1:
        adc     hl, hl
shrinkler_rb2:
        ld      (shrinkler_d4+2), hl    ; mais écrite en little endian
        ld      (shrinkler_d4), de
        ld      hl, (shrinkler_d2)
        adc     hl, hl
        ld      (shrinkler_d2), hl
        jr      shrinkler_getbit1

roudoudou

sure, i will put the previous one and specify the difference
My pronouns are RASM and ACE

Hicks

Excellent work!
For the "1-call-only version", we can remove "ld (shrinkler_a5+1),hl" at "shrinkler_decrunch" label (beginning), and write destination address directly in "shrinkler_a5" label... Then -3 bytes: 273!

roudoudou

Obviously i will document it.the same opt is possible with the reusable one instead of setting HL

My pronouns are RASM and ACE

antoniovillena

-5 bytes and small speed improvement to the 283 bytes version (now 278)


-5 bytes=>changing shrinkler_a5 by iy
speed improvement=>moving shrinkler_d6 outside loop shrinkler_getlit




shrinkler_getnumber:
        ; Out: Number in HL
        ld      bc, 1
        ld      hl, shrinkler_d6+1
        ld      (hl), a
        dec     hl
        ld      (hl), b
shrinkler_numberloop:
        inc     (hl)
        inc     (hl)
        call    shrinkler_getbit
        jr      c, shrinkler_numberloop
        dec     (hl)
shrinkler_bitsloop:
        call    shrinkler_getbit
        rl      c
        rl      b
        dec     (hl)
        dec     (hl)
        ret     m
        jr      shrinkler_bitsloop


;--------------------------------------------------
        ; Out: Bit in C
shrinkler_readbit:
        ld      hl, (shrinkler_d3)
        add     hl, hl
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2) ; lu en little endian
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
        ld      e, 4
        ex      af, af'
        add     ix, de
        ex      af, af'         ; injecte la CARRY précédente
        ld      l, (ix-1)
        ld      h, (ix-2)
        ld      e, (ix-3)
        ld      d, (ix-4)       ; DEHL=(a4) nouvelle valeur lue en big endian!
        adc     hl, hl
        ex      hl, de
shrinkler_rb1:
        adc     hl, hl
shrinkler_rb2:
        ld      (shrinkler_d4+2), hl    ; mais écrite en little endian
        ld      (shrinkler_d4), de
        ld      hl, (shrinkler_d2)
        adc     hl, hl
        ld      (shrinkler_d2), hl
        jr      shrinkler_getbit1


;--------------------------------------------------
shrinkler_getkind:
        ;Use parity as context
        push    de
        pop     iy
        xor     a
        ld      l, a
        inc     a
        and     e
        ld      h, a
shrinkler_altgetbit:
        ld      (shrinkler_d6), hl


shrinkler_getbit:
        exx
shrinkler_getbit1:
        ld      a, (shrinkler_d3+1)     ; obligé de relire les 8 bits forts la valeur...
        add     a, a
        jr      nc, shrinkler_readbit


        ld      hl, (shrinkler_d6)
        add     hl, hl
        ld      de, shrinkler_pr+2      ; cause -1 context
        add     hl, de
        push    hl
        ld      e, (hl)
        inc     hl
        ld      d, (hl)
        ; D1 = One prob
        push    de
        ld      b, d
        ld      c, e            ; bc=de=d1 / hl=a1
        ld      a, $e1
shrinkler_shift4:
        srl     b
        rr      c
        add     a, a
        jr      c, shrinkler_shift4
        ex      hl, de
        sbc     hl, bc          ; hl=d1-d1/16
        ex      hl, de
        ld      (hl), d
        dec     hl
        ld      (hl), e
        pop     bc              ; bc=d1 initial
        ld      de, (shrinkler_d3)
; input: DE x BC
; output: DEHL
        sbc     hl, hl
shrinkler_muluw:
        add     hl, hl
        rl      e
        rl      d
        jr      nc, shrinkler_cont
        add     hl, bc
        jr      nc, shrinkler_cont
        inc     de
shrinkler_cont:
        dec     a
        jr      nz, shrinkler_muluw
        ld      hl, (shrinkler_d2)
        xor     a
        sbc     hl, de
        pop     bc
        jr      nc, shrinkler_zero


shrinkler_one:
        ; onebrob = 1 - (1 - oneprob) * (1 - adjust) = oneprob - oneprob * adjust + adjust
        ; move+add out of order!
        ld      a, (bc)
        sub     1
        ld      (bc), a
        inc     bc
        ld      a, (bc)
        sbc     a, $f0                  ; (a1)+#FFF
        ld      (bc), a
        ex      de, hl
        jr      shrinkler_d3ret


shrinkler_decrunch:
        ; 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, 8
        dec     hl
        lddr
        inc     (hl)


        ; Literal
shrinkler_lit:
        scf
        ld      hl, shrinkler_d6
shrinkler_getlit:
        call    nc, shrinkler_getbit
        rl      (hl)
        jr      nc, shrinkler_getlit
        push    iy
        pop     de
        ldi


        ; After literal
        call    shrinkler_getkind
        jr      nc, shrinkler_lit


        ; Reference
        sbc     hl, hl
        call    shrinkler_altgetbit
        jr      nc, shrinkler_readoffset
shrinkler_readlength:
        ld      a, 4
        call    shrinkler_getnumber
shrinkler_d5:
        ld      hl, 0
        push    iy
        pop     de
        add     hl, de
        ldir


        ; After reference
        call    shrinkler_getkind
        jr      nc, shrinkler_lit
shrinkler_readoffset:
        ld      a, 3
        call    shrinkler_getnumber
        ; return without carry and HL=BC
        ld      hl, 2
        sbc     hl, bc
        ld      (shrinkler_d5+1), hl
        jr      nz, shrinkler_readlength


shrinkler_zero:
        ; oneprob = oneprob * (1 - adjust) = oneprob - oneprob * adjust
        ld      (shrinkler_d2), hl
        ld      hl, (shrinkler_d3)
        sbc     hl, de


shrinkler_d3ret:
        ld      (shrinkler_d3), hl
        exx
        ret

antoniovillena


antoniovillena

-4 bytes




shrinkler_getbit:
        exx
shrinkler_getbit1:
        ld      hl, (shrinkler_d3)     ; obligé de relire les 8 bits forts la valeur...
        add     hl, hl
        jr      nc, shrinkler_readbit
...
shrinkler_readbit:
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)

ervin

#59
Are the following useful?


shrinkler_getkind:
        ;Use parity as context
        ;push    de
        ;pop     iy
        ld iyh,d
        ld iyl,e



shrinkler_getlit:
        call    nc, shrinkler_getbit
        rl      (hl)
        jr      nc, shrinkler_getlit
        ;push    iy
        ;pop     de
        ld d,iyh
        ld e,iyl



shrinkler_d5:
        ld      hl, 0
        ;push    iy
        ;pop     de
        ld d,iyh
        ld e,iyl


roudoudou

push de / pop de -> 1 byte
push iy / pop iy -> 2 bytes
ld <reg8>,<ireg8> -> 2 bytes


so no, not usefull
My pronouns are RASM and ACE

Hicks

Would it possible to update the two routines each time (1-call & normal one)?
Normal is 274, but actual "1-call" is 276, the last optimisations are not integrated (with the last, I think we are close from 265)...
Thanks Rdd!

ervin

Quote from: roudoudou on 09:35, 06 February 18
push de / pop de -> 1 byte
push iy / pop iy -> 2 bytes
ld <reg8>,<ireg8> -> 2 bytes

so no, not usefull

Indeed, it takes a few more bytes, but it also takes less NOPS.  ;D


roudoudou

#63
Quote from: Hicks on 11:15, 06 February 18
Would it possible to update the two routines each time (1-call & normal one)?
Normal is 274, but actual "1-call" is 276, the last optimisations are not integrated (with the last, I think we are close from 265)...
Thanks Rdd!


tonight ;)


Quote from: ervin on 12:17, 06 February 18Indeed, it takes a few more bytes, but it also takes less NOPS.  ;D



the impact is negligible.
the purpose of Shrinkler is to offer extreme compression for 4K intro

if you need speed, there is several alternatives
My pronouns are RASM and ACE

antoniovillena

Another -1


        ld      a, $eb
shrinkler_shift4:
        srl     b
        rr      c
        add     a, a
        jr      c, shrinkler_shift4-1
        sbc     hl, bc          ; hl=d1-d1/16
        ex      hl, de
...

shrinkler_cont:
        sub     $b
        jr      nz, shrinkler_muluw
        ld      hl, (shrinkler_d2)
        sbc     hl, de



roudoudou

My pronouns are RASM and ACE

Urusergi

-1 byte  ;D
SHRINKLER_READBIT:    LD (SHRINKLER_D3),HL
            LD HL,(SHRINKLER_D4)
            ADC HL,HL
            EX HL,DE
            LD HL,(SHRINKLER_D4+2)
            JR NZ,READBIT1
            ADC HL,HL
            JR NZ,READBIT2
            ; HL=DE=0
            LD E,&04
            ADD IX,DE
            LD L,(IX-1)
            LD H,(IX-2)
            LD E,(IX-3)
            LD D,(IX-4) ; DEHL=(a4) big endian value read!
            SCF
            ADC HL,HL
            EX HL,DE

READBIT1:        ADC HL,HL

READBIT2:        LD (SHRINKLER_D4),DE
            LD (SHRINKLER_D4+2),HL ; written in little endian
            LD HL,(SHRINKLER_D2)
            ADC HL,HL
            LD (SHRINKLER_D2),HL
            JR GETBIT1

antoniovillena

-2 bytes




shrinkler_readbit:
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2)
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
        ld      e, 4
        add     ix, de
        ld      l, (ix-1)
        ld      h, (ix-2)
        ld      e, (ix-3)
        ld      d, (ix-4)               ; DEHL=(a4) big endian value read!
        add     hl, hl
        inc     hl
        ex      de, hl

antoniovillena


Wow. We saw similar optimization at the same time

Quote from: Urusergi on 23:21, 19 February 18
-1 byte  ;D
SHRINKLER_READBIT:    LD (SHRINKLER_D3),HL
            LD HL,(SHRINKLER_D4)
            ADC HL,HL
            EX HL,DE
            LD HL,(SHRINKLER_D4+2)
            JR NZ,READBIT1
            ADC HL,HL
            JR NZ,READBIT2
            ; HL=DE=0
            LD E,&04
            ADD IX,DE
            LD L,(IX-1)
            LD H,(IX-2)
            LD E,(IX-3)
            LD D,(IX-4) ; DEHL=(a4) big endian value read!
            SCF
            ADC HL,HL
            EX HL,DE

READBIT1:        ADC HL,HL

READBIT2:        LD (SHRINKLER_D4),DE
            LD (SHRINKLER_D4+2),HL ; written in little endian
            LD HL,(SHRINKLER_D2)
            ADC HL,HL
            LD (SHRINKLER_D2),HL
            JR GETBIT1


Urusergi

-2 bytes  :doh: It was obvious  :-[

I take my hat off, you're the Master

antoniovillena


Also it was obvious the carry always after an ADC HL, HL with zero result. But It took much time to discover.



Quote from: Urusergi on 23:42, 19 February 18
-2 bytes  :doh: It was obvious  :-[

I take my hat off, you're the Master

antoniovillena

-1


This one is not obvious




shrinkler_readbit:
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2)
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
ruti:   ld      d, (ix)               ; DEHL=(a4) big endian value read!
        ld      e, (ix+1)
        ex      de, hl
        inc     ix
        inc     ix
        ret     nz
        call    ruti-1
        add     hl, hl
        inc     hl
        ex      de, hl

Urusergi

Quote from: antoniovillena on 00:07, 20 February 18
-1

This one is not obvious

Very good this one, I haven't checked but I get the impression that is slower?  ???

antoniovillena

Another -1




shrinkler_readbit:
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2)
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
shrinkler_rb0:
        ccf
        ld      d, (ix)               ; DEHL=(a4) big endian value read!
        ld      e, (ix+1)
        ex      de, hl
        inc     ix
        inc     ix
        jr      nc, shrinkler_rb0
        add     hl, hl
        inc     hl
        ex      de, hl
shrinkler_rb1:

antoniovillena

Quote from: Urusergi on 00:37, 20 February 18
Very good this one, I haven't checked but I get the impression that is slower?  ???


This one a little faster (same size):




shrinkler_readbit:
        ld      (shrinkler_d3), hl
        ld      hl, (shrinkler_d4)
        adc     hl, hl
        ex      de, hl
        ld      hl, (shrinkler_d4+2)
        jr      nz, shrinkler_rb1
        adc     hl, hl
        jr      nz, shrinkler_rb2
        ; HL=DE=0
shrinkler_rb0:
        ccf
        ld      d, (ix)               ; DEHL=(a4) big endian value read!
        ld      e, (ix+1)
        ex      de, hl
        inc     ix
        inc     ix
        jr      nc, shrinkler_rb0
        adc     hl, hl
        ex      de, hl
shrinkler_rb1:

Powered by SMFPacks Menu Editor Mod