[gs-devel] Re: Another good excercise, ,

[Leonardo]

Thanks for suggestion.
A disadvantage of this code is the necessity of a dynamic check
whether the index is within the signed_eo array.
In the worst case the array size is twice the number of turns
of a contour around any point. Unfortunately
I can't know it in advance.

Leo.


----- Original Message ----- 
From: "lazer1" <lazer1 at blueyonder.co.uk>
To: "Leonardo" <leonardo at artifex.com>; <gs-devel at ghostscript.com>
Cc: "tech" <tech at artifex.com>
Sent: Thursday, January 11, 2007 7:01 PM
Subject: Re: [gs-devel] Re: Another good excercise, xefitra,


>
> I think I have to postfix the subject line with "xefitra" when replying
> otherwise the reply vanishes, resending this email with a further comment
> at the end,
>
>
> On 10-Jan-07, Leonardo wrote:
>>Folks,
>
>>Thanks to all who responded to this.
>>Here I update it with Alex's observation :
>
>>#define signed_eo(a) ((a) < 0 ? -((a) & 1) : ((a) & 1))
>>#define ADVANCE_WINDING(inside, alp, ll) \
>>{ int k = alp->contour_count; \
>>  int v = ll->windings[k]; \
>>  inside -= signed_eo(v); \
>>  v = ll->windings[k] += alp->direction; \
>>  inside += signed_eo(v); \
>>}
>
> if v is guaranteed to be "small" perhaps you can use a lookup table
> for signed_eo(a) eg:
>
> int x[] = { -1, 0, -1, 0, -1, 0, 1, 0, 1, 0, 1 } ;
> register int *signed_eo = &x[ 5 ] ; /* I think! */
> register int v ;
>
> (done dynamically if say v is 16 bit)
>
> and then use signed_eo[ v ] instead of signed_eo( v )
>
> as signed_eo[ v ] could be 1 asm instruction as signed_eo and v
> are both registers,
>
> furthermore you can eliminate v above thus:
>
> { int k = alp->contour_count ; \
>  inside -= signed_eo[ ll->windings[k] ]; \
>  inside += signed_eo[ ll->windings[k] += alp->direction ]; \
> }
>
> here v isnt necessary as compilers usually evaluate intermediate 
> expressions
> to registers. You cannot eliminate thus with the original version as
> the macro would expand too much.
>
> (I hope there are no bugs in the fragments I gave),
>
> the macro version of signed_eo() could avoid the memory access which
> the lookup table does, however it is more instructions which are
> themselves memory accesses (comparison, conditional branch, &, -,
> unconditional branch). Depends on instruction cache vs L1 cache speeds,
> needs to be benchmarked to determine which is faster. The lookup table is
> simpler code so less bug-prone. Sufficiently simpler that you dont even 
> need
> to use any macros.
>
>
>
>
>