1 /* reorder.c ... manage reorder reordering
2 *
3 * 11/1/17
4 * - first version
5 */
6
7 /*
8
9 This file is part of VIPS.
10
11 VIPS is free software; you can redistribute it and/or modify
12 it under the terms of the GNU Lesser General Public License as published by
13 the Free Software Foundation; either version 2 of the License, or
14 (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU Lesser General Public License for more details.
20
21 You should have received a copy of the GNU Lesser General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
24 02110-1301 USA
25
26 */
27
28 /*
29
30 These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk
31
32 */
33
34 /*
35 #define DEBUG
36 */
37
38 #ifdef HAVE_CONFIG_H
39 #include <config.h>
40 #endif /*HAVE_CONFIG_H*/
41 #include <vips/intl.h>
42
43 #include <vips/vips.h>
44 #include <vips/internal.h>
45 #include <vips/debug.h>
46
47 /* Have one of these on every image, identified by a quark.
48 */
49 typedef struct _VipsReorder {
50 /* The image we are attached to.
51 */
52 VipsImage *image;
53
54 /* The direct inputs to this image, so a copy of the array that is
55 * passed to vips_image_pipeline_array(), and in the same order.
56 * NULL-terminated.
57 *
58 * Score is the priority we give to the inputs as we de-dupe the source
59 * arrays.
60 *
61 * The recomp order is the order we prepare regions in ... just make a
62 * range then sort by score.
63 */
64 int n_inputs;
65 VipsImage **input;
66 int *score;
67 int *recomp_order;
68
69 /* Source images are images with no input images, so file load,
70 * vips_black(), etc. NULL-terminated array.
71 *
72 * The cumulative margin is the total margin that has been added to
73 * each source image up to this point in the pipeline.
74 */
75 int n_sources;
76 VipsImage **source;
77 int *cumulative_margin;
78
79 } VipsReorder;
80
81 GQuark vips__image_reorder_quark = 0;
82
83 #ifdef DEBUG
84 static void
vips_reorder_print(VipsReorder * reorder)85 vips_reorder_print( VipsReorder *reorder )
86 {
87 int i;
88
89 printf( "vips_reorder_print: " );
90 vips_object_print_name( VIPS_OBJECT( reorder->image ) );
91 printf( "\n" );
92
93 printf( "n_inputs = %d\n", reorder->n_inputs );
94 printf( " n score order\n" );
95 for( i = 0; i < reorder->n_inputs; i++ ) {
96 printf( "%2d - %8d, %8d, ",
97 i, reorder->score[i], reorder->recomp_order[i] );
98 vips_object_print_name( VIPS_OBJECT( reorder->input[i] ) );
99 printf( "\n" );
100 }
101
102 printf( "n_sources = %d\n", reorder->n_sources );
103 printf( " n margin\n" );
104 for( i = 0; i < reorder->n_sources; i++ ) {
105 printf( "%2d - %8d, ",
106 i, reorder->cumulative_margin[i] );
107 vips_object_print_name( VIPS_OBJECT( reorder->source[i] ) );
108 printf( "\n" );
109 }
110
111 }
112 #endif /*DEBUG*/
113
114 static void
vips_reorder_free(VipsReorder * reorder)115 vips_reorder_free( VipsReorder *reorder )
116 {
117 /* We free explicitly, rather than using VIPS_ARRAY( image ... ), since
118 * we need to make sure these pointers are valid to this point in the
119 * close cycle.
120 */
121 VIPS_FREE( reorder->input );
122 VIPS_FREE( reorder->score );
123 VIPS_FREE( reorder->recomp_order );
124 VIPS_FREE( reorder->source );
125 VIPS_FREE( reorder->cumulative_margin );
126 }
127
128 static void
vips_reorder_destroy(VipsReorder * reorder)129 vips_reorder_destroy( VipsReorder *reorder )
130 {
131 vips_reorder_free( reorder );
132 VIPS_FREE( reorder );
133 }
134
135 static VipsReorder *
vips_reorder_get(VipsImage * image)136 vips_reorder_get( VipsImage *image )
137 {
138 VipsReorder *reorder;
139
140 if( (reorder = g_object_get_qdata( G_OBJECT( image ),
141 vips__image_reorder_quark )) )
142 return( reorder );
143
144 reorder = VIPS_NEW( NULL, VipsReorder );
145 reorder->image = image;
146 reorder->n_inputs = 0;
147 reorder->input = NULL;
148 reorder->score = NULL;
149 reorder->recomp_order = NULL;
150 reorder->n_sources = 0;
151 reorder->source = NULL;
152 reorder->cumulative_margin = NULL;
153
154 g_object_set_qdata_full( G_OBJECT( image ), vips__image_reorder_quark,
155 reorder, (GDestroyNotify) vips_reorder_destroy );
156
157 return( reorder );
158 }
159
160 static int
vips_reorder_compare_score(const void * a,const void * b,void * arg)161 vips_reorder_compare_score( const void *a, const void *b, void *arg )
162 {
163 int i1 = *((int *) a);
164 int i2 = *((int *) b);
165 VipsReorder *reorder = (VipsReorder *) arg;
166
167 return( reorder->score[i2] - reorder->score[i1] );
168 }
169
170 int
vips__reorder_set_input(VipsImage * image,VipsImage ** in)171 vips__reorder_set_input( VipsImage *image, VipsImage **in )
172 {
173 VipsReorder *reorder = vips_reorder_get( image );
174
175 int i;
176 int total;
177
178 /* We have to support being called more than once on the same image.
179 * Two cases:
180 *
181 * 1. in the first call, no images were set ... we throw away
182 * everything from the first call and try again. foreign can do this.
183 *
184 * 2. warn if the args were different and do nothing.
185 */
186 if( reorder->source ) {
187 if( reorder->n_inputs == 0 ) {
188 reorder->n_sources = 0;
189 vips_reorder_free( reorder );
190 }
191 else {
192 for( i = 0; in[i]; i++ )
193 if( i >= reorder->n_inputs ||
194 in[i] != reorder->input[i] ) {
195 /* Should never happen.
196 */
197 g_warning( "vips__reorder_set_input: "
198 "args differ\n" );
199 break;
200 }
201
202 return( 0 );
203 }
204 }
205
206 /* Make a copy of the input array.
207 */
208 for( i = 0; in[i]; i++ )
209 ;
210 reorder->n_inputs = i;
211 reorder->input = VIPS_ARRAY( NULL, reorder->n_inputs + 1, VipsImage * );
212 reorder->score = VIPS_ARRAY( NULL, reorder->n_inputs, int );
213 reorder->recomp_order = VIPS_ARRAY( NULL, reorder->n_inputs, int );
214 if( !reorder->input )
215 return( -1 );
216 if( reorder->n_inputs &&
217 (!reorder->score ||
218 !reorder->recomp_order) )
219 return( -1 );
220
221 for( i = 0; i < reorder->n_inputs; i++ ) {
222 reorder->input[i] = in[i];
223 reorder->score[i] = 0;
224 reorder->recomp_order[i] = i;
225 }
226 reorder->input[i] = NULL;
227
228 /* Find the total number of source images -- this gives an upper bound
229 * to the size of the unique source image array we will need.
230 */
231 total = 0;
232 for( i = 0; i < reorder->n_inputs; i++ )
233 total += vips_reorder_get( reorder->input[i] )->n_sources;
234
235 /* No source images means this must itself be a source image, so it has
236 * a source image of itself.
237 */
238 total = VIPS_MAX( 1, total );
239
240 reorder->source = VIPS_ARRAY( NULL, total + 1, VipsImage * );
241 reorder->cumulative_margin = VIPS_ARRAY( NULL, total, int );
242 if( !reorder->source ||
243 !reorder->cumulative_margin )
244 return( -1 );
245
246 /* Copy source images over, removing duplicates. If we find a
247 * duplicate, we have a reordering opportunity, and we adjust the
248 * scores of the two images containing the dupe.
249 */
250 for( i = 0; i < reorder->n_inputs; i++ ) {
251 VipsReorder *input = vips_reorder_get( reorder->input[i] );
252
253 int j;
254
255 for( j = 0; j < input->n_sources; j++ ) {
256 int k;
257
258 /* Search for dupe.
259 */
260 for( k = 0; k < reorder->n_sources; k++ )
261 if( reorder->source[k] == input->source[j] )
262 break;
263
264 if( k < reorder->n_sources ) {
265 /* Found a dupe. Does this new use of
266 * input->source[j] have a larger or smaller
267 * margin? Adjust the score to reflect the
268 * change, note the new max.
269 */
270 reorder->score[i] +=
271 input->cumulative_margin[j] -
272 reorder->cumulative_margin[k];
273
274 reorder->cumulative_margin[k] = VIPS_MAX(
275 reorder->cumulative_margin[k],
276 input->cumulative_margin[j] );
277
278 }
279 else {
280 /* No dupe, just add to the table.
281 */
282 reorder->source[reorder->n_sources] =
283 input->source[j];
284 reorder->cumulative_margin[reorder->n_sources] =
285 input->cumulative_margin[j];
286 reorder->n_sources += 1;
287 }
288 }
289 }
290
291 /* Sort recomp_order by score. qsort_r() is a GNU libc thing, don't use
292 * it.
293 */
294 if( reorder->n_inputs > 1 )
295 g_qsort_with_data( reorder->recomp_order,
296 reorder->n_inputs,
297 sizeof( int ),
298 vips_reorder_compare_score, reorder );
299
300 /* No sources ... make one, us!
301 */
302 if( reorder->n_inputs == 0 ) {
303 reorder->source[0] = image;
304 reorder->cumulative_margin[0] = 0;
305 reorder->n_sources = 1;
306 }
307
308 #ifdef DEBUG
309 vips_reorder_print( reorder );
310 #endif /*DEBUG*/
311
312 return( 0 );
313 }
314
315 /**
316 * vips_reorder_prepare_many: (method)
317 * @image: the image that's being written
318 * @regions: (array) (element-type VipsRegion): the set of regions to prepare
319 * @r: the #VipsRect to prepare on each region
320 *
321 * vips_reorder_prepare_many() runs vips_region_prepare() on each region in
322 * @regions, requesting the pixels in @r.
323 *
324 * It tries to request the regions in the order which will cause least
325 * recomputation. This can give a large speedup, in some cases.
326 *
327 * See also: vips_region_prepare(), vips_reorder_margin_hint().
328 *
329 * Returns: 0 on success, or -1 on error.
330 */
331 int
vips_reorder_prepare_many(VipsImage * image,VipsRegion ** regions,VipsRect * r)332 vips_reorder_prepare_many( VipsImage *image, VipsRegion **regions, VipsRect *r )
333 {
334 VipsReorder *reorder = vips_reorder_get( image );
335
336 int i;
337
338 for( i = 0; i < reorder->n_inputs; i++ ) {
339 g_assert( regions[i] );
340
341 if( vips_region_prepare(
342 regions[reorder->recomp_order[i]], r ) )
343 return( -1 );
344 }
345
346 return( 0 );
347 }
348
349 /**
350 * vips_reorder_margin_hint: (method)
351 * @image: the image to hint on
352 * @margin: the size of the margin this operation has added
353 *
354 * vips_reorder_margin_hint() sets a hint that @image contains a margin, that
355 * is, that each vips_region_prepare() on @image will request a slightly larger
356 * region from it's inputs. A good value for @margin is (width * height) for
357 * the window the operation uses.
358 *
359 * This information is used by vips_image_prepare_many() to attempt to reorder
360 * computations to minimise recomputation.
361 *
362 * See also: vips_image_prepare_many().
363 */
364 void
vips_reorder_margin_hint(VipsImage * image,int margin)365 vips_reorder_margin_hint( VipsImage *image, int margin )
366 {
367 VipsReorder *reorder = vips_reorder_get( image );
368
369 int i;
370
371 for( i = 0; i < reorder->n_sources; i++ )
372 reorder->cumulative_margin[i] += margin;
373 }
374
375 void
vips__reorder_clear(VipsImage * image)376 vips__reorder_clear( VipsImage *image )
377 {
378 g_object_set_qdata( G_OBJECT( image ),
379 vips__image_reorder_quark, NULL );
380 }
381
382 void
vips__reorder_init(void)383 vips__reorder_init( void )
384 {
385 if( !vips__image_reorder_quark )
386 vips__image_reorder_quark =
387 g_quark_from_static_string( "vips-image-reorder" );
388 }
389