Coding Competition #1

[Thorham]

Originally Posted by pandy71

Visibility depends on viewer but some people can notice this (only 16 levels may emphasize this).

All that matters is wether or not it looks good.

[Leffmann]

So, what are the results?

[a/b]

Anyone? Bueller?

[Thorham]

Is this still alive?

[a/b]

Looks like Dan is still recovering from the slivovitz induced comma (tea and milk next time, mate).
In the meanwhile, it's time for a little [ Show youtube player ] erm... disclosure.
My entries were:
- 40 bytes
- 224 cycles

[ross]

Originally Posted by a/b

- 224 cycles

WOW!
including registries saving and restoring?

Pozzetto

[a/b]

Yeah, regs save/restore and rts included in both numbers.

[meynaf]

No results published ? Did the OP just leave with the code ?

Perhaps it's time for another coding compo then. See here.

[Thorham]

It's probably just that he has to look through thousands of entries

[Nightfox]

More like he became a guru and started meditating

[Thorham]

[a/b]

EDIT: Of f*****g course....
So after going through the code bazillion times I didn't notice it. Right after posting it I took and shower and went through it for no reason one more time, didn't even think hard about it (heck, I barely thought about it in the past month, I've been coding something else in the meanwhile). And of course, it just popped up in my mind, another optimization, 14-8=6 cycles saved.
I'll just edit the damn thing....
EDIT END

It's been way too long and I want to get this out of the system and move on (to abcd )....
Here is my code (40 bytes, 214 cycles according to my count):

InterpolateShort
	movem.l	d3-d6,-(a7)		; 4
	moveq	#$0000000f,d3		; 2
	moveq	#$ffffffff,d4		; 2
.LoopRGB
	move.w	d0,d5			; 2
	move.w	d1,d6			; 2
	and.w	d3,d5			; 2
	and.w	d3,d6			; 2

	sub.w	d5,d6			; 2
	muls.w	d2,d6			; 2
	divs.w	#15,d6			; 4
	and.w	d4,d6			; 2
	add.w	d6,d0			; 2

	asl.w	#4,d4			; 2
	lsl.w	#4,d3			; 2
	bgt.s	.LoopRGB		; 2

	movem.l	(a7)+,d3-d6		; 4
	rts				; 2

BuildTable
	lea	(Table,pc),a0
	moveq	#-15,d7
.LoopColor
	moveq	#0,d6
.LoopScale
	move.w	d7,d0
	muls.w	d6,d0
	divs.w	#15,d0
	move.b	d0,(a0)+
;	clr.b	(a0)+
 asl.b	#4,d0
 move.b d0,(a0)+
	addq.w	#1,d6
	cmp.w	#16,d6
	bne.b	.LoopScale
	addq.w	#1,d7
	cmp.w	#16,d7
	bne.b	.LoopColor
	rts

InterpolateQuick
	move.w	d3,-(a7)		; 8
	move.w	d4,-(a7)		; 8
	move.w	#$0f0,d3		; 8
	add.w	d3,d2			; 4
	add.w	d2,d2			; 4

	move.w	d3,d4			; 4
	and.w	d0,d3			; 4
	and.w	d1,d4			; 4
	sub.w	d3,d4			; 4
	add.w	d4,d4			; 4
	add.w	d2,d4			; 4
;	move.w	(Table,pc,d4.w),d4	; 14
;	asr.w	#4,d4			; 6+2*4=14
;	add.w	d4,d0			; 4
; 14 cycles saved
;; move.b	(Table+1,pc,d4.w),d3	; 14
;; add.w	d3,d0			; 4
;; EDIT: fixed my infinite "wisdom" overflowing from G into R in some cases, also saves additional 4 cycles
 add.b	(Table+1,pc,d4.w),d0	; 14

	move.w	#$00f,d3		; 8
	move.w	d3,d4			; 4
	and.w	d0,d3			; 4
	and.w	d1,d4			; 4
	sub.w	d3,d4			; 4
	asl.w	#4+1,d4			; 6+2*5=16
	add.w	d2,d4			; 4
	add.b	(Table,pc,d4.w),d0	; 14

	move.w	d0,d3			; 4
	clr.b	d3			; 4
	clr.b	d1			; 4
	sub.w	d3,d1			; 4
	asr.w	#8-(4+1),d1		; 6+2*3=12
	add.w	d2,d1			; 4
;	add.w	(Table,pc,d1.w),d0	; 14
; 8 cycles lost
 move.w	(Table,pc,d1.w),d1	; 14
 clr.b	d1			; 4
 add.w	d1,d0			; 4

	move.w	(a7)+,d4		; 8
	move.w	(a7)+,d3		; 8
	rts				; 16

Table	DS.W	31*16		; [-15..15]x[0..15]

[ross]

Okay, let's call the cards.
Also my version is based on the same interpolate variation as a/b.
But i'm in search of a math precise results (see old post).
The muls/divs sequence give too little fractional part.
I've send at Dan a little C code to generate all variation of input value as a reference:

#include <stdio.h>
#include <stdlib.h>

const double steps=15.0;
const double rounding=0.5;

int interpolate(double start_value, double end_value, double step_select)
{
    return (end_value-start_value)*step_select/steps+start_value+rounding;
}

int main()
{
    FILE* file_txt=fopen("interpolated_value.txt","w");
    FILE* file_bin=fopen("interpolated_value.bin","wb");
    for (double s=0.0; s<=steps; s++) {
        for (double e=0.0; e<=steps; e++) {
            for (double i=0.0; i<=steps; i++) {
                int value=interpolate(s, e, i);
                printf("%d  ",value);
                fprintf(file_txt,"%d  ",value);
                fwrite(&value,1,1,file_bin);
            }
            printf("\n");
            fprintf(file_txt,"\n");
        }
    }
    fclose(file_txt);
    fclose(file_bin);
    return 0;
}

And the asm code that give the same results:

interpolate:
    movem.l d3-d6,-(sp)
    moveq   #0,d3
    moveq   #3,d4
ls: moveq   #15,d5
    moveq   #15,d6
    and.w   d0,d5
    and.w   d1,d6
    lsr.w   #4,d0
    lsr.w   #4,d1
    sub.w   d5,d6
    muls.w  d2,d6
    muls.w  #$1111,d6       ; (1/15)*2^16=4369,0x
    add.w   d6,d6
    swap    d6
    addx.w  d6,d5           ; +0.5
    or.w    d5,d3
    ror.w   #4,d3
    dbf     d4,ls
    move.l  d3,d0
    movem.l (sp)+,d3-d6
    rts

I've tried to apply the same code sequence of a/b but failed, the code becomes largest.
This is the minimum i've got for precise math (16bit fract).

Bye!
ross

[ross]

Originally Posted by a/b

Here is my code (40 bytes, 224 cycles according to my count):
<snip>

For a quasi-precise interpolation your code is GREAT!

Congrats,
ross

[meynaf]

Here is my code. Uses 8 bit fractional part. I don't know its speed, but there's no div in the loop.

 movem.l d1-d6,-(a7)
 moveq #15,d6
 lsl.w #8,d2
 divu d6,d2
.loop
 move.w d6,d4       ; (ex: 0f0)
 move.w d6,d5
 and.w d0,d4        ; d4=0v0
 and.w d1,d5        ; d5=0w0
 eor.w d4,d0        ; d0=v0v
 move.w d4,d3       ; d3=0v0
 sub.w d5,d4        ; d4=*d0
 muls d2,d4         ; d4=m*0
 lsr.l #8,d4        ; d4=*m*
 add.w d3,d4        ; d4=*c*
 and.w d6,d4        ; d4=0c0
 add.w d4,d0        ; d0=vcv
 lsl.w #4,d6
 bpl.s .loop        ; f000 -> n=1
 movem.l (a7)+,d1-d6
 rts

[ross]

Originally Posted by meynaf

Here is my code. Uses 8 bit fractional part. I don't know its speed, but there's no div in the loop.
<snip>

Nice!
For 8bit frac this excels (i've an 8bit version but two byte more )

Congrats,
ross

[Thorham]

Crappy naive version:

lerp
    movem.l d0-d5,-(sp)

    move.w  #$0f0f,d5
    move.w  d0,d3
    and.w   d5,d0
    eor.w   d0,d3
    move.w  d1,d4
    and.w   d5,d1
    eor.w   d1,d4
    mulu.w  d2,d0
    mulu.w  d2,d1
    eor.b   d5,d2
    mulu.w  d2,d3
    mulu.w  d2,d4
    add.w   d3,d0
    add.w   d4,d1
    eor.b   d5,d2
    divu.w  d2,d0
    divu.w  d2,d1
    and.w   d5,d0
    and.w   #$00f0,d1
    or.w    d1,d0

    movem.l (sp)+,d0-d5
    rts

[PeterK]

Since there is no feedback from the TO, an always drunken coder and a fool like me has some more OT:

What's going wrong in my broken brain when I look at your solutions?

It seems you're always dividing by 15 steps. Why that?

I would first find out what the highest difference of the 3 color components is, and then I would divide by this number, but not always by 15!

So, the component with the highest difference could make steps 1 by 1. But the two other components could only make steps by source +/- (0.5+(steps*currentDiff/highestDiff)).

You could make a table 14*14 for the division currentDiff/highestDiff shifted up by 5 bits and another table 14*31 for the results from the first table and the multiplikation with steps and the rounding and then shifted down by 5 bits (approximately, never tested).

That's my confused association for a solution, but not really sober anymore!

[a/b]

Because when you are interpolating more than one color you want them to begin and end at the same time, so the number of steps has to be constant. And it's much easier setting it to 15 than going through both palettes and find the maximum (which would more likely end up being 15 anyway).

[PeterK]

1.) Interpolating can only be done for 2 colors, not one and not more than two.

2.) What do you mean with "at the same time"? I'm thinking about 2 colors in the same color cube.

3.) The number of steps can NEVER be higher than the highest difference of the 3 color components. Ok, I should better say, more steps makes really no sense! And how much is a step then, if it is not exactly 1 for the highest difference ?? In your construction, "step 0" would not always be the source color (or not)? Can you explain that?

4.) Where do you see 2 palettes? I can only see 1 color cube with a source and a destination color.