Anyone up for an ASM coding competition?

[ross]

Originally Posted by meynaf

Next try, did it in 32 bytes
I'm starting to believe it can't be done shorter...

Hi meynaf!
I've to triple check the results but maybe the 'impossible' 30 byte is coming

[Thorham]

I'd much rather optimize code for speed.

[meynaf]

Originally Posted by ross

Hi meynaf!
I've to triple check the results but maybe the 'impossible' 30 byte is coming

It took me much efforts to reach 32, but, hey, why not 30. I wonder if we'll end up using the same tricks

Originally Posted by Thorham

I'd much rather optimize code for speed.

Speed depends on the cpu you're running the code. Code size does not.
90% of a program doesn't need optimising for speed, only a handful routines do -- but code size matters everywhere.
This is why I like short code more than fast code - and for fast code one could just get a faster cpu...

[Thorham]

Originally Posted by meynaf

90% of a program doesn't need optimising for speed

Code that doesn't require speed should be written for clarity (unless it bloats the code a lot). A good example would be using multiplies instead of shifts and adds.

Originally Posted by meynaf

for fast code one could just get a faster cpu...

Now you're talking like Microsoft Do you think your image viewer would be as fast as it is now with that mentality? Since you've gotten a peecee you've turned to the dark side

When software is written properly, code size doesn't matter one bit, because you're not bloating it with code you don't need.

[meynaf]

Originally Posted by Thorham

A good example would be using multiplies instead of shifts and adds.

This also leads to short code...

Originally Posted by Thorham

Now you're talking like Microsoft Do you think your image viewer would be as fast as it is now with that mentality? Since you've gotten a peecee you've turned to the dark side

Don't worry i still value fast code but let's face the facts : code that's smaller is usually faster as well (for same algorithm) and shaving a few clocks by destroying code quality isn't really a good move.

For example, you might be happy with some self-modifying code on 68000 and then you discover it no longer works on another cpu. Or you replaced muls by shifts and adds and it becomes slower on machines with a fast multiply.

You speak about my picture viewer but if you examine its code you won't see huge unrolled loops or bad quality trades for speed.

Originally Posted by Thorham

When software is written properly, code size doesn't matter one bit, because you're not bloating it with code you don't need.

Properly written software leads to short code as well.
That said, i would indeed not waste readability for code that's just slightly shorter (or slightly faster, as said above).

[matthey]

Originally Posted by Thorham

When software is written properly, code size doesn't matter one bit, because you're not bloating it with code you don't need.

Code size always matters for CPU efficiency (doing more processing with less resources). Software which is written properly (efficiently) is like a ship sailing with the wind. However, ISA does still matter where you start in terms of efficiency. An efficient algorithm with good code quality on a PPC core would need 32kB ICache to have similar ICache performance (miss percentage) as equally efficient code using 8kB ICache on an enhanced 68k CPU core. The ISA made significantly more difference to efficiency than your "efficient code". The CPU design is important also.

Originally Posted by meynaf

Properly written software leads to short code as well.

Efficiently created processor designs (with efficient ISAs) should try to make the smallest code the fastest code too. The most efficient places to employ extra hardware in a CPU are places which improve code density. These resources often at least partially pay for themselves. A good example is the innate code compression in the 68k where the advantages of smaller code easily outweigh the small latency and extra transistors used in decoding. Extra hardware could be added to reduce the advantages of loop unrolling, function inlining and need for wasted alignment padding and this would be partially paid for if it reduces code size. In contrast, trying to make big code fast is like sailing into the wind which destroyed many a sail of RISC ships and has sunk several. The least code dense Alpha and PA-RISC are sunk and the next least MIPS, SPARC and PPC are dead in the water with their crews bailing water.

[meynaf]

Anyway here's the 32 byte version I told about :

 move.l d3,d0
 moveq #16,d1
 asl.l d1,d0
 bvs.s .ns
 addq.b #8,d1
 asl.l #8,d0
 bvs.s .ns
 addq.b #2,d1
.ns
 move.l d3,d0
 lsr.l #8,d0    
 bne.s .nu0
 addq.b #1,d1
.nu0
 lsr.l #8,d0    
 bne.s .nu1
 addq.b #4,d1
.nu1
 rts

Waiting for the 30-byte version now

Originally Posted by matthey

Efficiently created processor designs (with efficient ISAs) should try to make the smallest code the fastest code too. The most efficient places to employ extra hardware in a CPU are places which improve code density. These resources often at least partially pay for themselves. A good example is the innate code compression in the 68k where the advantages of smaller code easily outweigh the small latency and extra transistors used in decoding. Extra hardware could be added to reduce the advantages of loop unrolling, function inlining and need for wasted alignment padding and this would be partially paid for if it reduces code size. In contrast, trying to make big code fast is like sailing into the wind which destroyed many a sail of RISC ships and has sunk several. The least code dense Alpha and PA-RISC are sunk and the next least MIPS, SPARC and PPC are dead in the water with their crews bailing water.

Yup, very right.
But the 68k isn't the best thing we could have. By reencoding it and adding a few key features we could beat it by at least 10% (got 18% for the above example).

[ross]

30 byte (28 if flag not in low bit *):

    ; d0.l input value
    ; d1   output flag

    moveq   #1,d2
    swap    d2
.l  move.l  d0,d3
    sub.l   d2,d3
    addx    d1,d1
    add.l   d2,d3
    move.l  d2,d4
    lsr.l   #1,d4
    add.l   d4,d3
    sub.l   d2,d3
    addx    d1,d1
    lsr.l   #8,d2
    bne.s   .l
    lsr.b   #2,d1    *
    rts

[meynaf]

Too bad it's much slower, but still great

However, how could you miss this :

 moveq #1,d2
 swap d2
.l
 move.l d0,d3
 sub.l d2,d3
 addx.l d1,d1
 move.l d2,d3
 lsr.l #1,d3
 add.l d0,d3
 sub.l d2,d3
 addx.l d1,d1
 lsr.l #8,d2
 bne.s .l
 rts

Yeah, 2 bytes less

[ross]

Originally Posted by meynaf

Too bad it's much slower, but still great

However, how could you miss this :

Because i've broken my mind making the 30byte version
What i make with d4 is absurd . Thanks meynaf!

This is really funny, i create a very alternative 'think mode' and losing the simple trick (same as CRC Boot..).

Bye,

[meynaf]

Originally Posted by ross

This is really funny, i create a very alternative 'think mode' and losing the simple trick (same as CRC Boot..).

Several pairs of eyes are always better than one

[ross]

[OT]
scusate ma non resisto (two is megl' che uan):
[ Show youtube player ]
il mio inglese maccheronico e quello che ha scritto meynaf me l'ha fatto venire in mente
[/OF]

sorry, some italian humor about 'two is better than one' joint with my spaghetti english

[ross]

Originally Posted by meynaf

Several pairs of eyes are always better than one

Yes, You're absolutely right!

[Thorham]

Originally Posted by meynaf

code that's smaller is usually faster as well

Yes, but probably not always (can't think of an example, though ).

Originally Posted by meynaf

For example, you might be happy with some self-modifying code on 68000 and then you discover it no longer works on another cpu.

If you need the best speed on a 68000, then SMC might still be the way to go. Just write two versions of the same routine.

Originally Posted by meynaf

Or you replaced muls by shifts and adds and it becomes slower on machines with a fast multiply.

Of course, but I rather have code that's close to as fast as possible on a 68020/30 than a 68060. If you also want top performance on a 60, write two versions.

Originally Posted by meynaf

That said, i would indeed not waste readability for code that's just slightly shorter (or slightly faster, as said above).

I certainly will sacrifice readability for speed in tight loops.

Anyway, the way I interpreted what you wrote made me fear the worst

[meynaf]

Originally Posted by Thorham

Yes, but probably not always (can't think of an example, though ).

I wrote 'usually', not 'always'. Yes of course there are examples but most of them involve changing something in the method.

Originally Posted by Thorham

If you need the best speed on a 68000, then SMC might still be the way to go. Just write two versions of the same routine.

Frankly i don't care about the 68000 anymore. At least, not enough to do dirty things.
Look at all these great demos of the past. How many of them still run fine on accelerated machines ?

Originally Posted by Thorham

Of course, but I rather have code that's close to as fast as possible on a 68020/30 than a 68060. If you also want top performance on a 60, write two versions.

I prefer having more or less cpu agnostic code that's reasonably fast everywhere.

Originally Posted by Thorham

I certainly will sacrifice readability for speed in tight loops.

Not me

Originally Posted by Thorham

Anyway, the way I interpreted what you wrote made me fear the worst

Perhaps I shouldn't have added this last remark, but if a cpu is underpowered for a task then there is little we can do about it aside of getting a faster one...

[paraj]

Originally Posted by ross

38byte, i don't know if I can do better


EDIT: 36! (34 with 15 bit offset)

Would you mind sharing your work (or some hints)? For my trackmo-adventures (http://eab.abime.net/showthread.php?t=86467) I'm think of using a similar approach. I figured it'd be interesting to look into something that works with sectors (possibly interleaving the MFM decoding, but since shifts are so slow on 68k it's probably better to just have a blitter pass). I would have used the packfire routines, but since the encoder is closed-source I'd probably be hard to adapt to outputting 512-byte compatible blocks.

Here's my efforts (without tweaking the encoder / hurting performance too much). Byte-oriented like your approach with the mode (control) bits kept in a separate byte.

Format of encoded data: 8 control bits ($00 = special) followed by 8 times either a literal (if control bit is 0) or a 16-bit match (11 bits of offset, 5 bits for length). $00 control byte followed by $00 = 8 literals, otherwise the next byte is -8-symbols_in_this_block (i.e. -1 -> 7 lz symbols follow), followed by the control bits for the last symbols. This leaves 1..$f7 unused for now.

I'm not too satisfied about the special cases and there's lots of instructions from my current 58 to something worth bragging about

Main decoding routine:

LENBITS=5
WINBITS=11

; a0 = output
; a1 = input
; a2 = input end
unpack_getcontrolbits:
	cmp.l	a1, a2				; are we done?
	bne.s	unpack				; no go to main routine
        rts					; done - return
unpack:						; MAIN ENTRY POINT
        moveq   #8, d3                          ; d3 = remaining control bits
        move.b  (a1)+, d0                       ; d0 = control bits
	bne.s	.loop                           ; not special case
	move.b	(a1)+, d0			; grab next byte in stream
	beq.s	.loop                           ; the control bits just happened to be zero
	add.b	d0, d3				; d3 = 8+byte read (=num control bits)
	move.b	(a1)+, d0			; load control bits
.loop:
        subq.b  #1, d3				; we consumed a control bit
        bmi.s   unpack_getcontrolbits		; need to refill control byte?
        add.b   d0, d0                          ; grab control bit
        bcs.s   .handlematch                    ; copy from window?
        move.b  (a1)+, (a0)+                    ; copy literal
        bra.s   .loop				; and continue with unpacking
.handlematch:
	move.b	(a1)+, -(a7)			; grab 8 MSB of offset
	move.w	(a7)+, d1			; to upper byte of d1.w
	move.b	(a1)+, d1			; lower bits
        moveq	#(1<<LENBITS)-1, d2		; length mask
        and.b	d1, d2				; d2 = length
        addq.b	#2, d2				; d2 = length + min_match_length(3) - 1
        lsr.w	#LENBITS, d1			; shift offset into place
        not.w   d1                              ; d1 = -1-offset (-1..-(1<<WINBITS))
.copy:
        move.b  (a0,d1.w), (a0)+                ; copy match
        dbf     d2, .copy
        bra.s   .loop

[ross]

Originally Posted by paraj

Would you mind sharing your work (or some hints)? For my trackmo-adventures (http://eab.abime.net/showthread.php?t=86467) I'm think of using a similar approach. I figured it'd be interesting to look into something that works with sectors (possibly interleaving the MFM decoding, but since shifts are so slow on 68k it's probably better to just have a blitter pass). I would have used the packfire routines, but since the encoder is closed-source I'd probably be hard to adapt to outputting 512-byte compatible blocks.

Here's my efforts (without tweaking the encoder / hurting performance too much). Byte-oriented like your approach with the mode (control) bits kept in a separate byte.

Format of encoded data: 8 control bits ($00 = special) followed by 8 times either a literal (if control bit is 0) or a 16-bit match (11 bits of offset, 5 bits for length). $00 control byte followed by $00 = 8 literals, otherwise the next byte is -8-symbols_in_this_block (i.e. -1 -> 7 lz symbols follow), followed by the control bits for the last symbols. This leaves 1..$f7 unused for now.

I'm not too satisfied about the special cases and there's lots of instructions from my current 58 to something worth bragging about

Hi paraj.
The format, like Thorham suggested, is made for a totally byte oriented approach.
But with a big problem (for pure 68k): offset in 16bit.
So You need some trick or simply two separate stream for byte/word token (blazing fast, but no more in place unpacking).

This is the code (not rechecked, maybe later):

ls: moveq   #8,d2
    move.b  (a0)+,d1
la: subq.w  #1,d2
    bmi.s   ls
    move.b  (a0)+,d0
    beq.s   exit
    movea.l a0,a2
    add.b   d1,d1
lb: bcc.b   ll
lz: move.b  (a0)+,-(sp)
    move.w  (sp)+,d3
    move.b  (a0)+,d3
    suba.w  d3,a2
ll: move.b  (a2)+,(a1)+
    subq.b  #1,d0
    bne.b   ll
    bra.b   la
exit:    
    rts

Feel free to ask for clarification.

Bye!


EDIT: two stream version, even more compact (28 byte)

ls: moveq   #8,d2
    move.b  (a0)+,d1
la: subq.w  #1,d2
    bmi.s   ls
    move.b  (a0)+,d0
    beq.s   exit
    movea.l a0,a2
    add.b   d1,d1
lb: bcc.b   ll
lz: suba.w  (a3)+,a2
ll: move.b  (a2)+,(a1)+
    subq.b  #1,d0
    bne.b   ll
    bra.b   la
exit:

[paraj]

Originally Posted by ross

Hi paraj.
The format, like Thorham suggested, is made for a totally byte oriented approach.
But with a big problem (for pure 68k): offset in 16bit.
So You need some trick or simply two separate stream for byte/word token (blazing fast, but no more in place unpacking).

Very nice, thanks a bunch

Here's the code with my comments. Did I understand the code right?

If yes, I think I'll have to make some adaptions to get it working in my scenario: I want to copy from the uncompressed area instead of from the compressed stream, but overall lots of new information for me to look at!

ls:     moveq   #8,d2           ; d2 = number of control bits
        move.b  (a0)+,d1        ; d1 = control byte
la:     subq.w  #1,d2           ; we'll consume one control bit
        bmi.s   ls              ; need to refill?
        move.b  (a0)+,d0        ; d0 = match length/literal count
        beq.s   exit            ; zero conveniently means exit!
        movea.l a0,a2           ; a2 = offset of next src byte
        add.b   d1,d1           ; get control bit
lb      bcc.b   ll              ; literal?
lz:     move.b  (a0)+,-(sp)     ; use stack trick to get...
        move.w  (sp)+,d3        ; upper byte to d3.w
        move.b  (a0)+,d3        ; lower byte to d3.w
        suba.w  d3,a2           ; offset by -d3 (note: copy from compressed stream)
ll:     move.b  (a2)+,(a1)+     ; copy match/literal
        subq.b  #1,d0           ; one more byte done
        bne.b   ll              ; continue with copy
        bra.b   la              ; process next control bit
exit:   rts

Originally Posted by ross

EDIT: two stream version, even more compact (28 byte)

I'll have to study this for more nice tricks! Once again thanks a lot

[ross]

Originally Posted by paraj

Very nice, thanks a bunch

Here's the code with my comments. Did I understand the code right?

If yes, I think I'll have to make some adaptions to get it working in my scenario: I want to copy from the uncompressed area instead of from the compressed stream, but overall lots of new information for me to look at!

You're right, my mistake. Haste, not a proper check..
Right code:

ls:     moveq   #8,d2           ; d2 = number of control bits
        move.b  (a0)+,d1        ; d1 = control byte
la:     subq.w  #1,d2           ; we'll consume one control bit
        bmi.s   ls              ; need to refill?
        move.b  (a0)+,d0        ; d0 = match length/literal count
        beq.s   exit            ; zero conveniently means exit!
        movea.l a0,a2           ; a2 = prepare for literal copy
        add.b   d1,d1           ; get control bit
lb      bcc.b   ll              ; literal?
lz:     movea.l a1,a2           ; a2 = prepare for match copy
        move.b  (a0)+,-(sp)     ; use stack trick to get...
        move.w  (sp)+,d3        ; upper byte to d3.w
        move.b  (a0)+,d3        ; lower byte to d3.w
        suba.w  d3,a2           ; offset by -d3 (note: copy from uncompressed stream)
ll:     move.b  (a2)+,(a1)+     ; copy match/literal
        subq.b  #1,d0           ; one more byte done
        bne.b   ll              ; continue with copy
        bra.b   la              ; process next control bit
exit:   rts

I'll have to study this for more nice tricks! Once again thanks a lot

This is simply the same code without stack trick to get 16bit.
A separate stream in a3 give the offset.
So:
a0=first stream (byte token)
a3=second stream (word token, 15bit negative offset)

ls: moveq   #8,d2
    move.b  (a0)+,d1
la: subq.w  #1,d2
    bmi.s   ls
    move.b  (a0)+,d0
    beq.s   exit
    movea.l a0,a2
    add.b   d1,d1
lb: bcc.b   ll
lz: movea.l a1,a2   [same mistake :p]
    suba.w  (a3)+,a2
ll: move.b  (a2)+,(a1)+
    subq.b  #1,d0
    bne.b   ll
    bra.b   la
exit:

Bye!

[paraj]

After spending way too much time on this silly project, I think I'm finally done creating odd LZ-variants And this might actually be useful for situations where larger packers won't fit (I'm telling myself...)

Playing around with various parameters, I've settled on the following word oriented format: 16-bits of control/mode bits (MSB->LSB, 1=literal 0=match). Literals are 16-bit and matches are coded with 11-bits for the offset, 5 bits for length-1. A zero match word signals end of data).

42-byte inner loop can't quite match the best of Ross', but the extra instructions gave improvements on my test data. Of course adding more instructions gave better results, but this is what I ended up with.

; a0 = output
; a1 = input (compressed data)
; trashes d0-d3/a0-a2
unpack:
.refill:
        moveq   #16, d1     	; d1 = number of control bits
        move.w  (a1)+, d0   	; d0 = control bits
.mainloop:
        subq.w  #1, d1		; consume a control bit
        bmi.s   .refill		; need to refill?
        add.w   d0, d0		; extract next control bit
        bcc.s   .copymatch	; match?
        move.w  (a1)+, (a0)+	; copy literal
        bra.s   .mainloop	; one more loop
.copymatch:
        move.w  (a1)+, d2	; get match length and offset
        beq.s	.quit		; done?
        moveq   #(1<<lenbits)-1, d3 ; d3 = length mask
        and.w   d2, d3          ; d3 = length
        eor.w	d3, d2		; d2 = offset<<lenbits
        lsr.w   #lenbits-1, d2  ; d2 = offset<<1
        move.l	a0, a2		; a2 = &output[pos]
        sub.w	d2, a2		; a2 = &output[pos-offset]
.copy:
        move.w  (a2)+, (a0)+	; copy match
        dbf     d3, .copy	; done?
        bra.s   .mainloop	; continue with main loop
.quit:
	rts