fix method index entry for add_file_magic()
[imager.git] / hlines.c
CommitLineData
fc414e6a 1#define IMAGER_NO_CONTEXT
92bda632 2#include "imageri.h"
39f94030
TC
3#include <stdlib.h>
4
5#define OVERLAPPED(start1, end1, start2, end2) \
6 (im_max((start1), (start2)) <= im_min((end1), (end2)))
7
8/*
9=head1 NAME
10
11hlines.c - implements a "class" for managing sets of horizontal line segments
12
13=head1 SYNOPSIS
14
15 i_int_hlines hlines;
16 // just for the specified range of y
17 i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x);
18 // to cover a whole image
19 i_int_init_hlines_img(&hlines, img);
20 // add a hline segment, merging into existing
21 i_int_hlines_add(&hlines, y, x, width);
22
23 // work over the lines
24 for (y = hlines.start; y < hlines.limit; ++y) {
25 i_int_hline_entry *entry = hlines.entries[i];
26 if (entry) {
27 for (i = 0; i < entry->count; ++i) {
28 i_int_hline_seg *seg = entry->segs+i;
29 // do something on line y for seg->minx to x_limit
30 }
31 }
32 }
33
34 // free it all up
35 i_int_hlines_destroy(&hlines);
36
37=head1 DESCRIPTION
38
39Provides a class to manage sets of horizontal line segments. The
40intent is that when drawing shapes where the algorithm used might
41cause overlaps we can use this class to resolve the overlaps.
42
43Note that segment lists are intended to remain small, if we end up
44with a need for longer lists we should use different structure for the
45segment lists.
46
47=over
48
49=item i_int_init_hlines
50
51i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
52
53Initializes the structure based on drawing an object within the given
54range. Any x or y values outside the given ranges will be ignored.
55
56=cut
57
58*/
59
60void
61i_int_init_hlines(
62 i_int_hlines *hlines,
8d14daab
TC
63 i_img_dim start_y,
64 i_img_dim count_y,
65 i_img_dim start_x,
66 i_img_dim width_x
39f94030
TC
67 )
68{
8d14daab 69 size_t bytes = count_y * sizeof(i_int_hline_entry *);
39f94030
TC
70
71 if (bytes / count_y != sizeof(i_int_hline_entry *)) {
8ebac85f
TC
72 dIMCTX;
73 im_fatal(aIMCTX, 3, "integer overflow calculating memory allocation\n");
39f94030
TC
74 }
75
76 hlines->start_y = start_y;
77 hlines->limit_y = start_y + count_y;
78 hlines->start_x = start_x;
79 hlines->limit_x = start_x + width_x;
80 hlines->entries = mymalloc(bytes);
81 memset(hlines->entries, 0, bytes);
82}
83
84/*
85=item i_int_init_hlines_img
86
87i_int_init_hlines_img(img);
88
89Initialize a hlines object as if we could potentially draw anywhere on
90the image.
91
92=cut
93*/
94
95void
96i_int_init_hlines_img(i_int_hlines *hlines, i_img *img)
97{
98 i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
99}
100
101/*
102=item i_int_hlines_add
103
104i_int_hlines_add(hlines, y, x, width)
105
106Add to the list, merging with existing entries.
107
108=cut
109*/
110
111void
8d14daab
TC
112i_int_hlines_add(i_int_hlines *hlines, i_img_dim y, i_img_dim x, i_img_dim width) {
113 i_img_dim x_limit = x + width;
39f94030
TC
114
115 if (width < 0) {
8ebac85f
TC
116 dIMCTX;
117 im_fatal(aIMCTX, 3, "negative width %d passed to i_int_hlines_add\n", width);
39f94030
TC
118 }
119
120 /* just return if out of range */
121 if (y < hlines->start_y || y >= hlines->limit_y)
122 return;
123
124 if (x >= hlines->limit_x || x_limit < hlines->start_x)
125 return;
126
127 /* adjust x to our range */
128 if (x < hlines->start_x)
129 x = hlines->start_x;
130 if (x_limit > hlines->limit_x)
131 x_limit = hlines->limit_x;
132
133 if (x == x_limit)
134 return;
135
136 if (hlines->entries[y - hlines->start_y]) {
137 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
8d14daab 138 i_img_dim i, found = -1;
39f94030
TC
139
140 for (i = 0; i < entry->count; ++i) {
141 i_int_hline_seg *seg = entry->segs + i;
142 if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
143 found = i;
144 break;
145 }
146 }
147 if (found >= 0) {
148 /* ok, we found an overlapping segment, any other overlapping
149 segments need to be merged into the one we found */
150 i_int_hline_seg *merge_seg = entry->segs + found;
151
152 /* merge in the segment we found */
153 x = im_min(x, merge_seg->minx);
154 x_limit = im_max(x_limit, merge_seg->x_limit);
155
156 /* look for other overlapping segments */
157 /* this could be a for(), but I'm using continue */
158 i = found + 1;
159 while (i < entry->count) {
160 i_int_hline_seg *seg = entry->segs + i;
161 if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
162 /* merge this into the current working segment, then
163 delete it by moving the last segment (if this isn't it)
164 into it's place */
165 x = im_min(x, seg->minx);
166 x_limit = im_max(x_limit, seg->x_limit);
167 if (i < entry->count-1) {
168 *seg = entry->segs[entry->count-1];
169 --entry->count;
170 continue;
171 }
172 else {
173 --entry->count;
174 break;
175 }
176 }
177 ++i;
178 }
179
180 /* store it back */
181 merge_seg->minx = x;
182 merge_seg->x_limit = x_limit;
183 }
184 else {
185 i_int_hline_seg *seg;
186 /* add a new segment */
187 if (entry->count == entry->alloc) {
188 /* expand it */
8d14daab 189 size_t alloc = entry->alloc * 3 / 2;
39f94030
TC
190 entry = myrealloc(entry, sizeof(i_int_hline_entry) +
191 sizeof(i_int_hline_seg) * (alloc - 1));
192 entry->alloc = alloc;
193 hlines->entries[y - hlines->start_y] = entry;
194 }
195 seg = entry->segs + entry->count++;
196 seg->minx = x;
197 seg->x_limit = x_limit;
198 }
199 }
200 else {
201 /* make a new one - start with space for 10 */
202 i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
203 sizeof(i_int_hline_seg) * 9);
204 entry->alloc = 10;
205 entry->count = 1;
206 entry->segs[0].minx = x;
207 entry->segs[0].x_limit = x_limit;
208 hlines->entries[y - hlines->start_y] = entry;
209 }
210}
211
212/*
213=item i_int_hlines_destroy
214
215i_int_hlines_destroy(&hlines)
216
217Releases all memory associated with the structure.
218
219=cut
220*/
221
222void
223i_int_hlines_destroy(i_int_hlines *hlines) {
8d14daab
TC
224 size_t entry_count = hlines->limit_y - hlines->start_y;
225 size_t i;
39f94030
TC
226
227 for (i = 0; i < entry_count; ++i) {
228 if (hlines->entries[i])
229 myfree(hlines->entries[i]);
230 }
231 myfree(hlines->entries);
232}
233
234/*
235=item i_int_hlines_fill_color
236
237i_int_hlines_fill(im, hlines, color)
238
239Fill the areas given by hlines with color.
240
241=cut
242*/
243
244void
97ac0a96 245i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, const i_color *col) {
8d14daab 246 i_img_dim y, i, x;
39f94030
TC
247
248 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
249 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
250 if (entry) {
251 for (i = 0; i < entry->count; ++i) {
252 i_int_hline_seg *seg = entry->segs + i;
253 for (x = seg->minx; x < seg->x_limit; ++x) {
254 i_ppix(im, x, y, col);
255 }
256 }
257 }
258 }
259}
260
261/*
262=item i_int_hlines_fill_fill
263
264i_int_hlines_fill_fill(im, hlines, fill)
265
12db268a 266=cut
39f94030
TC
267*/
268void
269i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
9b1ec2b8 270 i_render r;
8d14daab 271 i_img_dim y, i;
39f94030 272
9b1ec2b8
TC
273 i_render_init(&r, im, im->xsize);
274
275 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
276 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
277 if (entry) {
278 for (i = 0; i < entry->count; ++i) {
279 i_int_hline_seg *seg = entry->segs + i;
8d14daab 280 i_img_dim width = seg->x_limit-seg->minx;
9b1ec2b8
TC
281
282 i_render_fill(&r, seg->minx, y, width, NULL, fill);
283 }
284 }
285 }
286 i_render_done(&r);
287
288#if 1
289#else
39f94030
TC
290 if (im->bits == i_8_bits && fill->fill_with_color) {
291 i_color *line = mymalloc(sizeof(i_color) * im->xsize);
292 i_color *work = NULL;
293 if (fill->combine)
294 work = mymalloc(sizeof(i_color) * im->xsize);
295 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
296 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
297 if (entry) {
298 for (i = 0; i < entry->count; ++i) {
299 i_int_hline_seg *seg = entry->segs + i;
8d14daab 300 i_img_dim width = seg->x_limit-seg->minx;
39f94030
TC
301
302 if (fill->combine) {
303 i_glin(im, seg->minx, seg->x_limit, y, line);
304 (fill->fill_with_color)(fill, seg->minx, y, width,
305 im->channels, work);
306 (fill->combine)(line, work, im->channels, width);
307 }
308 else {
309 (fill->fill_with_color)(fill, seg->minx, y, width,
310 im->channels, line);
311 }
312 i_plin(im, seg->minx, seg->x_limit, y, line);
313 }
314 }
315 }
316
317 myfree(line);
318 if (work)
319 myfree(work);
320 }
321 else {
322 i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
323 i_fcolor *work = NULL;
324 if (fill->combinef)
325 work = mymalloc(sizeof(i_fcolor) * im->xsize);
326 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
327 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
328 if (entry) {
329 for (i = 0; i < entry->count; ++i) {
330 i_int_hline_seg *seg = entry->segs + i;
8d14daab 331 i_img_dim width = seg->x_limit-seg->minx;
39f94030
TC
332
333 if (fill->combinef) {
334 i_glinf(im, seg->minx, seg->x_limit, y, line);
335 (fill->fill_with_fcolor)(fill, seg->minx, y, width,
336 im->channels, work);
337 (fill->combinef)(line, work, im->channels, width);
338 }
339 else {
340 (fill->fill_with_fcolor)(fill, seg->minx, y, width,
341 im->channels, line);
342 }
343 i_plinf(im, seg->minx, seg->x_limit, y, line);
344 }
345 }
346 }
347
348 myfree(line);
349 if (work)
350 myfree(work);
351 }
9b1ec2b8 352#endif
39f94030
TC
353}
354
355/*
356=back
357
358=head1 AUTHOR
359
5b480b14 360Tony Cook <tonyc@cpan.org>
39f94030
TC
361
362=head1 REVISION
363
364$Revision$
365
366=cut
367*/