Factor Language Blog

I want to play around with improved overflow check elimination. The Factor compiler already does some elementary overflow check elimination, but is only applicable to counted loops iterating over arrays. I want to generalize this in order to speed up Chris Double’s YUV to RGB conversion. YUV to RGB conversion performs a lot of integer additions and multiplications, none of which ever overflow to bignums. If the compiler can infer this fact, then it can replace generic arithmetic with machine arithmetic, resulting in a nice speedup. So as a first step I cooked up an interval arithmetic library, which represents a closed interval as a pair of numbers. I was pleasantly surprised at how simple it was:

: cartesian ( seq1 seq2 -- seq3 )
    [ swap [ swap 2array ] map-with ] map-with concat ;

: interval-op ( i1 i2 quot -- i3 )
    -rot cartesian [ first2 rot call ] map-with
    dup infimum swap supremum 2array ; inline

: >int ( n -- interval ) dup 2array ;

: int+ ( i1 i2 -- i3 ) [ + ] interval-op ;

: int- ( i1 i2 -- i3 ) [ - ] interval-op ;

: int* ( i1 i2 -- i3 ) [ * ] interval-op ;

: int-shift ( i1 n -- i2 ) >int [ shift ] interval-op ;

: int/ ( i1 i2 -- i3 ) [ / ] interval-op ;

: int/i ( i1 i2 -- i3 ) [ /i ] interval-op ;

: int-intersect ( i1 i2 -- i3/f )
    [ [ first ] 2apply max ] 2keep [ second ] 2apply min
    2dup > [ 2drop f ] [ 2array ] if ;

It is worth noting that the int+ and int- words can be made more efficient:

: int+ ( i1 i2 -- i3 ) v+ ;
: int- ( i1 i2 -- i3 ) reverse v- ;