[cairo] OVER / SOURCE optimization for cairo_paint

[Antoine Azar]

I've gone through my optimization again and found a few problematic 
cases which required complexifying the code quit a bit. I didn't run 
through all the tests yet, but I think this version is as fast as it 
can be while preserving the same output as the non-optimized route.

Main problems encountered with previous approach:
-Didn't support rotation as the source extents was computed with only 
2 points. I now compute all 4 points.
-Had border problems when non-nearest filtering was enabled along 
with a scaling and extend_none, as we would sample transparent pixels 
outside the image.
-Combinations of 2 problems above
-Was not always switching correctly to SOURCE

Here's a new patch that attempts to address those problems. Whenever 
possible, I replace a paint/OVER operation with a fill/SOURCE one. 
Otherwise I try a fill/OVER. And if not possible at all, we stick 
with the paint/OVER. The perf benchmarks are giving very similar 
results as before.

I also created a standalone function _cairo_gstate_get_source_extents 
but I have a feeling it's not at the right place. Let me know if this 
should be moved elsewhere.

Please ignore any styling or minor issues in the patch for now.

Looking forward to getting feedback,
Antoine
-------------- next part --------------
A non-text attachment was scrubbed...
Name: newOptim.patch
Type: application/octet-stream
Size: 12729 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20080217/3380364b/attachment-0001.obj 
-------------- next part --------------
[	# ]	backend-content	test-size	SPEEDUP (old median/new median)
[	0]	image-rgba	paint_solid_rgb_over-256	1.00
[	1]	image-rgba	paint_solid_rgb_source-256	1.00
[	2]	image-rgba	paint_image_rgb_over-256	5.81
[	3]	image-rgba	paint_image_rgb_source-256	0.99
[	4]	image-rgba	paint_linear_rgb_over-256	1.49
[	5]	image-rgba	paint_linear_rgb_source-256	1.00
[	6]	image-rgba	paint_radial_rgb_over-256	1.14
[	7]	image-rgba	paint_radial_rgb_source-256	0.99
[	8]	image-rgba	paint_solid_rgb_over-512	1.03
[	9]	image-rgba	paint_solid_rgb_source-512	0.99
[	10]	image-rgba	paint_image_rgb_over-512	3.52
[	11]	image-rgba	paint_image_rgb_source-512	0.99
[	12]	image-rgba	paint_linear_rgb_over-512	1.51
[	13]	image-rgba	paint_linear_rgb_source-512	0.99
[	14]	image-rgba	paint_radial_rgb_over-512	1.12
[	15]	image-rgba	paint_radial_rgb_source-512	1.05
[	0]	image-rgb	paint_solid_rgb_over-256	1.00
[	1]	image-rgb	paint_solid_rgb_source-256	1.00
[	2]	image-rgb	paint_image_rgb_over-256	11.39
[	3]	image-rgb	paint_image_rgb_source-256	0.97
[	4]	image-rgb	paint_linear_rgb_over-256	1.48
[	5]	image-rgb	paint_linear_rgb_source-256	1.01
[	6]	image-rgb	paint_radial_rgb_over-256	1.13
[	7]	image-rgb	paint_radial_rgb_source-256	1.00
[	8]	image-rgb	paint_solid_rgb_over-512	1.03
[	9]	image-rgb	paint_solid_rgb_source-512	1.00
[	10]	image-rgb	paint_image_rgb_over-512	4.15
[	11]	image-rgb	paint_image_rgb_source-512	1.01
[	12]	image-rgb	paint_linear_rgb_over-512	1.52
[	13]	image-rgb	paint_linear_rgb_source-512	1.01
[	14]	image-rgb	paint_radial_rgb_over-512	1.18
[	15]	image-rgb	paint_radial_rgb_source-512	0.99
[	0]	win32-rgb	paint_solid_rgb_over-256	1.00
[	1]	win32-rgb&	paint_solid_rgb_over-256	1.00
[	2]	win32-rgb	paint_solid_rgb_source-256	1.00
[	3]	win32-rgb&	paint_solid_rgb_source-256	1.00
[	4]	win32-rgb	paint_image_rgb_over-256	0.99
[	5]	win32-rgb&	paint_image_rgb_over-256	1.00
[	6]	win32-rgb	paint_image_rgb_source-256	0.97
[	7]	win32-rgb&	paint_image_rgb_source-256	0.98
[	8]	win32-rgb	paint_linear_rgb_over-256	1.55
[	9]	win32-rgb&	paint_linear_rgb_over-256	1.51
[	10]	win32-rgb	paint_linear_rgb_source-256	0.99
[	11]	win32-rgb&	paint_linear_rgb_source-256	1.01
[	12]	win32-rgb	paint_radial_rgb_over-256	1.15
[	13]	win32-rgb&	paint_radial_rgb_over-256	1.15
[	14]	win32-rgb	paint_radial_rgb_source-256	1.01
[	15]	win32-rgb&	paint_radial_rgb_source-256	1.00
[	16]	win32-rgb	paint_solid_rgb_over-512	0.79
[	17]	win32-rgb&	paint_solid_rgb_over-512	1.02
[	18]	win32-rgb	paint_solid_rgb_source-512	0.82
[	19]	win32-rgb&	paint_solid_rgb_source-512	0.98
[	20]	win32-rgb	paint_image_rgb_over-512	1.05
[	21]	win32-rgb&	paint_image_rgb_over-512	0.99
[	22]	win32-rgb	paint_image_rgb_source-512	1.02
[	23]	win32-rgb&	paint_image_rgb_source-512	1.00
[	24]	win32-rgb	paint_linear_rgb_over-512	1.49
[	25]	win32-rgb&	paint_linear_rgb_over-512	1.47
[	26]	win32-rgb	paint_linear_rgb_source-512	1.00
[	27]	win32-rgb&	paint_linear_rgb_source-512	1.00
[	28]	win32-rgb	paint_radial_rgb_over-512	1.12
[	29]	win32-rgb&	paint_radial_rgb_over-512	1.17
[	30]	win32-rgb	paint_radial_rgb_source-512	0.99
[	31]	win32-rgb&	paint_radial_rgb_source-512	1.01
[	0]	win32-rgba	paint_solid_rgb_over-256	1.03
[	1]	win32-rgba&	paint_solid_rgb_over-256	0.95
[	2]	win32-rgba	paint_solid_rgb_source-256	1.01
[	3]	win32-rgba&	paint_solid_rgb_source-256	0.99
[	4]	win32-rgba	paint_image_rgb_over-256	7.60
[	5]	win32-rgba&	paint_image_rgb_over-256	4.51
[	6]	win32-rgba	paint_image_rgb_source-256	0.99
[	7]	win32-rgba&	paint_image_rgb_source-256	0.99
[	8]	win32-rgba	paint_linear_rgb_over-256	1.54
[	9]	win32-rgba&	paint_linear_rgb_over-256	1.52
[	10]	win32-rgba	paint_linear_rgb_source-256	1.01
[	11]	win32-rgba&	paint_linear_rgb_source-256	0.98
[	12]	win32-rgba	paint_radial_rgb_over-256	1.14
[	13]	win32-rgba&	paint_radial_rgb_over-256	1.14
[	14]	win32-rgba	paint_radial_rgb_source-256	0.99
[	15]	win32-rgba&	paint_radial_rgb_source-256	1.00
[	16]	win32-rgba	paint_solid_rgb_over-512	1.00
[	17]	win32-rgba&	paint_solid_rgb_over-512	1.01
[	18]	win32-rgba	paint_solid_rgb_source-512	1.00
[	19]	win32-rgba&	paint_solid_rgb_source-512	1.00
[	20]	win32-rgba	paint_image_rgb_over-512	3.04
[	21]	win32-rgba&	paint_image_rgb_over-512	2.98
[	22]	win32-rgba	paint_image_rgb_source-512	1.01
[	23]	win32-rgba&	paint_image_rgb_source-512	0.99
[	24]	win32-rgba	paint_linear_rgb_over-512	1.48
[	25]	win32-rgba&	paint_linear_rgb_over-512	1.43
[	26]	win32-rgba	paint_linear_rgb_source-512	0.98
[	27]	win32-rgba&	paint_linear_rgb_source-512	1.00
[	28]	win32-rgba	paint_radial_rgb_over-512	1.10
[	29]	win32-rgba&	paint_radial_rgb_over-512	1.11
[	30]	win32-rgba	paint_radial_rgb_source-512	1.00
[	31]	win32-rgba&	paint_radial_rgb_source-512	1.00