1 /*
2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 % %
4 % %
5 % %
6 % AAA SSSSS H H L AAA RRRR %
7 % A A SS H H L A A R R %
8 % AAAAA SSS HHHHH L AAAAA RRRR %
9 % A A SS H H L A A R R %
10 % A A SSSSS H H LLLLL A A R R %
11 % %
12 % %
13 % Write Ashlar Images %
14 % %
15 % Software Design %
16 % Cristy %
17 % July 2020 %
18 % %
19 % %
20 % Copyright 1999-2021 ImageMagick Studio LLC, a non-profit organization %
21 % dedicated to making software imaging solutions freely available. %
22 % %
23 % You may not use this file except in compliance with the License. You may %
24 % obtain a copy of the License at %
25 % %
26 % https://imagemagick.org/script/license.php %
27 % %
28 % Unless required by applicable law or agreed to in writing, software %
29 % distributed under the License is distributed on an "AS IS" BASIS, %
30 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
31 % See the License for the specific language governing permissions and %
32 % limitations under the License. %
33 % %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 %
36 %
37 */
38
39 /*
40 Include declarations.
41 */
42 #include "MagickCore/studio.h"
43 #include "MagickCore/annotate.h"
44 #include "MagickCore/blob.h"
45 #include "MagickCore/blob-private.h"
46 #include "MagickCore/client.h"
47 #include "MagickCore/constitute.h"
48 #include "MagickCore/display.h"
49 #include "MagickCore/exception.h"
50 #include "MagickCore/exception-private.h"
51 #include "MagickCore/image.h"
52 #include "MagickCore/image-private.h"
53 #include "MagickCore/list.h"
54 #include "MagickCore/magick.h"
55 #include "MagickCore/memory_.h"
56 #include "MagickCore/option.h"
57 #include "MagickCore/property.h"
58 #include "MagickCore/quantum-private.h"
59 #include "MagickCore/static.h"
60 #include "MagickCore/string_.h"
61 #include "MagickCore/module.h"
62 #include "MagickCore/utility.h"
63 #include "MagickCore/xwindow.h"
64 #include "MagickCore/xwindow-private.h"
65
66 /*
67 Forward declarations.
68 */
69 static MagickBooleanType
70 WriteASHLARImage(const ImageInfo *,Image *,ExceptionInfo *);
71
72 /*
73 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
74 % %
75 % %
76 % %
77 % R e g i s t e r A S H L A R I m a g e %
78 % %
79 % %
80 % %
81 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
82 %
83 % RegisterASHLARImage() adds attributes for the ASHLAR image format to
84 % the list of supported formats. The attributes include the image format
85 % tag, a method to read and/or write the format, whether the format
86 % supports the saving of more than one frame to the same file or blob,
87 % whether the format supports native in-memory I/O, and a brief
88 % description of the format.
89 %
90 % The format of the RegisterASHLARImage method is:
91 %
92 % size_t RegisterASHLARImage(void)
93 %
94 */
RegisterASHLARImage(void)95 ModuleExport size_t RegisterASHLARImage(void)
96 {
97 MagickInfo
98 *entry;
99
100 entry=AcquireMagickInfo("ASHLAR","ASHLAR",
101 "Image sequence laid out in continuous irregular courses");
102 entry->encoder=(EncodeImageHandler *) WriteASHLARImage;
103 (void) RegisterMagickInfo(entry);
104 return(MagickImageCoderSignature);
105 }
106
107 /*
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
109 % %
110 % %
111 % %
112 % U n r e g i s t e r A S H L A R I m a g e %
113 % %
114 % %
115 % %
116 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
117 %
118 % UnregisterASHLARImage() removes format registrations made by the
119 % ASHLAR module from the list of supported formats.
120 %
121 % The format of the UnregisterASHLARImage method is:
122 %
123 % UnregisterASHLARImage(void)
124 %
125 */
UnregisterASHLARImage(void)126 ModuleExport void UnregisterASHLARImage(void)
127 {
128 (void) UnregisterMagickInfo("ASHLAR");
129 }
130
131 /*
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
133 % %
134 % %
135 % %
136 % W r i t e A S H L A R I m a g e %
137 % %
138 % %
139 % %
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
141 %
142 % WriteASHLARImage() writes an image to a file in ASHLAR format.
143 %
144 % The format of the WriteASHLARImage method is:
145 %
146 % MagickBooleanType WriteASHLARImage(const ImageInfo *image_info,
147 % Image *image,ExceptionInfo *exception)
148 %
149 % A description of each parameter follows.
150 %
151 % o image_info: the image info.
152 %
153 % o image: The image.
154 %
155 % o exception: return any errors or warnings in this structure.
156 %
157 */
158
159 typedef struct _NodeInfo
160 {
161 ssize_t
162 x,
163 y;
164
165 struct _NodeInfo
166 *next;
167 } NodeInfo;
168
169 typedef struct _AshlarInfo
170 {
171 size_t
172 width,
173 height;
174
175 ssize_t
176 align;
177
178 size_t
179 number_nodes;
180
181 MagickBooleanType
182 best_fit;
183
184 NodeInfo
185 *current,
186 *free,
187 head,
188 sentinal;
189 } AshlarInfo;
190
191 typedef struct _CanvasInfo
192 {
193 ssize_t
194 id;
195
196 size_t
197 width,
198 height;
199
200 ssize_t
201 x,
202 y,
203 order;
204 } CanvasInfo;
205
206 typedef struct _TileInfo
207 {
208 ssize_t
209 x,
210 y;
211
212 NodeInfo
213 **previous;
214 } TileInfo;
215
FindMinimumTileLocation(NodeInfo * first,const ssize_t x,const size_t width,ssize_t * excess)216 static ssize_t FindMinimumTileLocation(NodeInfo *first,const ssize_t x,
217 const size_t width,ssize_t *excess)
218 {
219 NodeInfo
220 *node;
221
222 ssize_t
223 extent,
224 y;
225
226 /*
227 Find minimum y location if it starts at x.
228 */
229 *excess=0;
230 y=0;
231 extent=0;
232 node=first;
233 while (node->x < (ssize_t) (x+width))
234 {
235 if (node->y > y)
236 {
237 *excess+=extent*(node->y-y);
238 y=node->y;
239 if (node->x < x)
240 extent+=node->next->x-x;
241 else
242 extent+=node->next->x-node->x;
243 }
244 else
245 {
246 size_t delta = (size_t) (node->next->x-node->x);
247 if ((delta+extent) > width)
248 delta=width-extent;
249 *excess+=delta*(y-node->y);
250 extent+=delta;
251 }
252 node=node->next;
253 }
254 return(y);
255 }
256
AssignBestTileLocation(AshlarInfo * ashlar_info,size_t width,size_t height)257 static TileInfo AssignBestTileLocation(AshlarInfo *ashlar_info,
258 size_t width,size_t height)
259 {
260 NodeInfo
261 *node,
262 **previous,
263 *tail;
264
265 ssize_t
266 min_excess;
267
268 TileInfo
269 tile;
270
271 /*
272 Align along left edge.
273 */
274 tile.previous=(NodeInfo **) NULL;
275 width=(width+ashlar_info->align-1);
276 width-=width % ashlar_info->align;
277 if ((width > ashlar_info->width) || (height > ashlar_info->height))
278 {
279 /*
280 Tile can't fit, bail.
281 */
282 tile.x=0;
283 tile.y=0;
284 return(tile);
285 }
286 tile.x=(ssize_t) MAGICK_SSIZE_MAX;
287 tile.y=(ssize_t) MAGICK_SSIZE_MAX;
288 min_excess=(ssize_t) MAGICK_SSIZE_MAX;
289 node=ashlar_info->current;
290 previous=(&ashlar_info->current);
291 while ((width+node->x) <= ashlar_info->width)
292 {
293 ssize_t
294 excess,
295 y;
296
297 y=FindMinimumTileLocation(node,node->x,width,&excess);
298 if (ashlar_info->best_fit == MagickFalse)
299 {
300 if (y < tile.y)
301 {
302 tile.y=y;
303 tile.previous=previous;
304 }
305 }
306 else
307 {
308 if ((height+y) <= ashlar_info->height)
309 if ((y < tile.y) || ((y == tile.y) && (excess < min_excess)))
310 {
311 tile.y=y;
312 tile.previous=previous;
313 min_excess=excess;
314 }
315 }
316 previous=(&node->next);
317 node=node->next;
318 }
319 tile.x=(tile.previous == (NodeInfo **) NULL) ? 0 : (*tile.previous)->x;
320 if (ashlar_info->best_fit != MagickFalse)
321 {
322 /*
323 Align along both left and right edges.
324 */
325 tail=ashlar_info->current;
326 node=ashlar_info->current;
327 previous=(&ashlar_info->current);
328 while (tail->x < (ssize_t) width)
329 tail=tail->next;
330 while (tail != (NodeInfo *) NULL)
331 {
332 ssize_t
333 excess,
334 x,
335 y;
336
337 x=tail->x-width;
338 while (node->next->x <= x)
339 {
340 previous=(&node->next);
341 node=node->next;
342 }
343 y=FindMinimumTileLocation(node,x,width,&excess);
344 if ((height+y) <= ashlar_info->height)
345 {
346 if (y <= tile.y)
347 if ((y < tile.y) || (excess < min_excess) ||
348 ((excess == min_excess) && (x < tile.x)))
349 {
350 tile.x=x;
351 tile.y=y;
352 min_excess=excess;
353 tile.previous=previous;
354 }
355 }
356 tail=tail->next;
357 }
358 }
359 return(tile);
360 }
361
AssignTileLocation(AshlarInfo * ashlar_info,const size_t width,const size_t height)362 static TileInfo AssignTileLocation(AshlarInfo *ashlar_info,const size_t width,
363 const size_t height)
364 {
365 NodeInfo
366 *current,
367 *node;
368
369 TileInfo
370 tile;
371
372 /*
373 Find the best location in the canvas for this tile.
374 */
375 tile=AssignBestTileLocation(ashlar_info,width,height);
376 if ((tile.previous == (NodeInfo **) NULL) ||
377 ((tile.y+(ssize_t) height) > (ssize_t) ashlar_info->height) ||
378 (ashlar_info->free == (NodeInfo *) NULL))
379 {
380 tile.previous=(NodeInfo **) NULL;
381 return(tile);
382 }
383 /*
384 Create a new node.
385 */
386 node=ashlar_info->free;
387 node->x=(ssize_t) tile.x;
388 node->y=(ssize_t) (tile.y+height);
389 ashlar_info->free=node->next;
390 /*
391 Insert node.
392 */
393 current=(*tile.previous);
394 if (current->x >= tile.x)
395 *tile.previous=node;
396 else
397 {
398 NodeInfo *next = current->next;
399 current->next=node;
400 current=next;
401 }
402 while ((current->next != (NodeInfo *) NULL) &&
403 (current->next->x <= (tile.x+(ssize_t) width)))
404 {
405 /*
406 Push current node to free list.
407 */
408 NodeInfo *next = current->next;
409 current->next=ashlar_info->free;
410 ashlar_info->free=current;
411 current=next;
412 }
413 node->next=current;
414 if (current->x < (tile.x+(ssize_t) width))
415 current->x=(ssize_t) (tile.x+width);
416 return(tile);
417 }
418
CompareTileHeight(const void * p_tile,const void * q_tile)419 static int CompareTileHeight(const void *p_tile,const void *q_tile)
420 {
421 const CanvasInfo
422 *p,
423 *q;
424
425 p=(const CanvasInfo *) p_tile;
426 q=(const CanvasInfo *) q_tile;
427 if (p->height > q->height)
428 return(-1);
429 if (p->height < q->height)
430 return(1);
431 return((p->width > q->width) ? -1 : (p->width < q->width) ? 1 : 0);
432 }
433
RestoreTileOrder(const void * p_tile,const void * q_tile)434 static int RestoreTileOrder(const void *p_tile,const void *q_tile)
435 {
436 const CanvasInfo
437 *p,
438 *q;
439
440 p=(const CanvasInfo *) p_tile;
441 q=(const CanvasInfo *) q_tile;
442 return((p->order < q->order) ? -1 : (p->order > q->order) ? 1 : 0);
443 }
444
PackAshlarTiles(AshlarInfo * ashlar_info,CanvasInfo * tiles,const size_t number_tiles)445 static MagickBooleanType PackAshlarTiles(AshlarInfo *ashlar_info,
446 CanvasInfo *tiles,const size_t number_tiles)
447 {
448 MagickBooleanType
449 status;
450
451 ssize_t
452 i;
453
454 /*
455 Pack tiles so they fit the canvas with minimum excess.
456 */
457 for (i=0; i < (ssize_t) number_tiles; i++)
458 tiles[i].order=(i);
459 qsort((void *) tiles,number_tiles,sizeof(*tiles),CompareTileHeight);
460 for (i=0; i < (ssize_t) number_tiles; i++)
461 {
462 tiles[i].x=0;
463 tiles[i].y=0;
464 if ((tiles[i].width != 0) && (tiles[i].height != 0))
465 {
466 TileInfo
467 tile_info;
468
469 tile_info=AssignTileLocation(ashlar_info,tiles[i].width,
470 tiles[i].height);
471 tiles[i].x=(ssize_t) tile_info.x;
472 tiles[i].y=(ssize_t) tile_info.y;
473 if (tile_info.previous == (NodeInfo **) NULL)
474 {
475 tiles[i].x=(ssize_t) MAGICK_SSIZE_MAX;
476 tiles[i].y=(ssize_t) MAGICK_SSIZE_MAX;
477 }
478 }
479 }
480 qsort((void *) tiles,number_tiles,sizeof(*tiles),RestoreTileOrder);
481 status=MagickTrue;
482 for (i=0; i < (ssize_t) number_tiles; i++)
483 {
484 tiles[i].order=(ssize_t) ((tiles[i].x != (ssize_t) MAGICK_SSIZE_MAX) ||
485 (tiles[i].y != (ssize_t) MAGICK_SSIZE_MAX) ? 1 : 0);
486 if (tiles[i].order == 0)
487 status=MagickFalse;
488 }
489 return(status); /* return true if room is found for all tiles */
490 }
491
WriteASHLARImage(const ImageInfo * image_info,Image * image,ExceptionInfo * exception)492 static MagickBooleanType WriteASHLARImage(const ImageInfo *image_info,
493 Image *image,ExceptionInfo *exception)
494 {
495 AshlarInfo
496 ashlar_info;
497
498 CanvasInfo
499 *tiles;
500
501 const char
502 *value;
503
504 Image
505 *ashlar_image,
506 *next;
507
508 ImageInfo
509 *write_info;
510
511 MagickBooleanType
512 status;
513
514 NodeInfo
515 *nodes;
516
517 RectangleInfo
518 extent,
519 geometry;
520
521 ssize_t
522 i,
523 n;
524
525 /*
526 Convert image sequence laid out in continuous irregular courses.
527 */
528 assert(image_info != (const ImageInfo *) NULL);
529 assert(image_info->signature == MagickCoreSignature);
530 assert(image != (Image *) NULL);
531 assert(image->signature == MagickCoreSignature);
532 if (image->debug != MagickFalse)
533 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
534 if (image_info->extract != (char *) NULL)
535 (void) ParseAbsoluteGeometry(image_info->extract,&geometry);
536 else
537 {
538 /*
539 Determine a sane canvas size and border width.
540 */
541 (void) ParseAbsoluteGeometry("0x0+0+0",&geometry);
542 for (next=image; next != (Image *) NULL; next=GetNextImageInList(next))
543 {
544 geometry.width+=next->columns;
545 geometry.height+=next->rows;
546 }
547 geometry.width=(size_t) geometry.width/7;
548 geometry.height=(size_t) geometry.height/7;
549 geometry.x=(ssize_t) pow((double) geometry.width,0.25);
550 geometry.y=(ssize_t) pow((double) geometry.height,0.25);
551 }
552 /*
553 Initialize image tiles.
554 */
555 ashlar_image=AcquireImage(image_info,exception);
556 status=SetImageExtent(ashlar_image,geometry.width,geometry.height,exception);
557 if (status == MagickFalse)
558 {
559 ashlar_image=DestroyImageList(ashlar_image);
560 return(MagickFalse);
561 }
562 (void) SetImageBackgroundColor(ashlar_image,exception);
563 tiles=(CanvasInfo *) AcquireQuantumMemory(GetImageListLength(image),
564 sizeof(*tiles));
565 ashlar_info.number_nodes=2*geometry.width;
566 nodes=(NodeInfo *) AcquireQuantumMemory(ashlar_info.number_nodes,
567 sizeof(*nodes));
568 if ((tiles == (CanvasInfo *) NULL) || (nodes == (NodeInfo *) NULL))
569 {
570 if (tiles != (CanvasInfo *) NULL)
571 tiles=(CanvasInfo *) RelinquishMagickMemory(tiles);
572 if (nodes != (NodeInfo *) NULL)
573 nodes=(NodeInfo *) RelinquishMagickMemory(tiles);
574 ashlar_image=DestroyImageList(ashlar_image);
575 ThrowWriterException(ResourceLimitError,"MemoryAllocationFailed");
576 }
577 /*
578 Interate until we find a tile size that fits the canvas.
579 */
580 value=GetImageOption(image_info,"ashlar:best-fit");
581 for (i=20; i > 0; i--)
582 {
583 ssize_t
584 j;
585
586 n=0;
587 for (next=image; next != (Image *) NULL; next=GetNextImageInList(next))
588 {
589 tiles[n].id=n;
590 tiles[n].width=(size_t) (0.05*i*next->columns+2*geometry.x);
591 tiles[n].height=(size_t) (0.05*i*next->rows+2*geometry.y);
592 n++;
593 }
594 for (j=0; j < (ssize_t) ashlar_info.number_nodes-1; j++)
595 nodes[j].next=nodes+j+1;
596 nodes[j].next=(NodeInfo *) NULL;
597 ashlar_info.best_fit=IsStringTrue(value) != MagickFalse ? MagickTrue :
598 MagickFalse;
599 ashlar_info.free=nodes;
600 ashlar_info.current=(&ashlar_info.head);
601 ashlar_info.width=geometry.width;
602 ashlar_info.height=geometry.height;
603 ashlar_info.align=(ssize_t) ((ashlar_info.width+ashlar_info.number_nodes-1)/
604 ashlar_info.number_nodes);
605 ashlar_info.head.x=0;
606 ashlar_info.head.y=0;
607 ashlar_info.head.next=(&ashlar_info.sentinal);
608 ashlar_info.sentinal.x=(ssize_t) geometry.width;
609 ashlar_info.sentinal.y=(ssize_t) MAGICK_SSIZE_MAX;
610 ashlar_info.sentinal.next=(NodeInfo *) NULL;
611 status=PackAshlarTiles(&ashlar_info,tiles,(size_t) n);
612 if (status != MagickFalse)
613 break;
614 }
615 /*
616 Determine layout of images tiles on the canvas.
617 */
618 value=GetImageOption(image_info,"label");
619 extent.width=0;
620 extent.height=0;
621 for (i=0; i < n; i++)
622 {
623 Image
624 *tile_image;
625
626 if ((tiles[i].x == (ssize_t) MAGICK_SSIZE_MAX) ||
627 (tiles[i].y == (ssize_t) MAGICK_SSIZE_MAX))
628 continue;
629 tile_image=ResizeImage(GetImageFromList(image,tiles[i].id),(size_t)
630 (tiles[i].width-2*geometry.x),(size_t) (tiles[i].height-2*geometry.y),
631 image->filter,exception);
632 if (tile_image == (Image *) NULL)
633 continue;
634 (void) CompositeImage(ashlar_image,tile_image,image->compose,MagickTrue,
635 tiles[i].x+geometry.x,tiles[i].y+geometry.y,exception);
636 if (value != (const char *) NULL)
637 {
638 char
639 *label,
640 offset[MagickPathExtent];
641
642 DrawInfo
643 *draw_info=CloneDrawInfo(image_info,(DrawInfo *) NULL);
644
645 label=InterpretImageProperties((ImageInfo *) image_info,tile_image,
646 value,exception);
647 if (label != (const char *) NULL)
648 {
649 (void) CloneString(&draw_info->text,label);
650 draw_info->pointsize=1.8*geometry.y;
651 (void) FormatLocaleString(offset,MagickPathExtent,"%+g%+g",(double)
652 tiles[i].x+geometry.x,(double) tiles[i].height+tiles[i].y+
653 geometry.y/2.0);
654 (void) CloneString(&draw_info->geometry,offset);
655 (void) AnnotateImage(ashlar_image,draw_info,exception);
656 }
657 }
658 if ((tiles[i].width+tiles[i].x) > extent.width)
659 extent.width=(size_t) (tiles[i].width+tiles[i].x);
660 if ((tiles[i].height+tiles[i].y) > extent.height)
661 extent.height=(size_t) (tiles[i].height+tiles[i].y);
662 tile_image=DestroyImage(tile_image);
663 }
664 (void) SetImageExtent(ashlar_image,extent.width,extent.height,exception);
665 nodes=(NodeInfo *) RelinquishMagickMemory(nodes);
666 tiles=(CanvasInfo *) RelinquishMagickMemory(tiles);
667 /*
668 Write ASHLAR canvas.
669 */
670 (void) CopyMagickString(ashlar_image->filename,image_info->filename,
671 MagickPathExtent);
672 write_info=CloneImageInfo(image_info);
673 *write_info->magick='\0';
674 (void) SetImageInfo(write_info,1,exception);
675 if ((*write_info->magick == '\0') ||
676 (LocaleCompare(write_info->magick,"ASHLAR") == 0))
677 (void) FormatLocaleString(ashlar_image->filename,MagickPathExtent,
678 "miff:%s",write_info->filename);
679 status=WriteImage(write_info,ashlar_image,exception);
680 ashlar_image=DestroyImage(ashlar_image);
681 write_info=DestroyImageInfo(write_info);
682 return(MagickTrue);
683 }
684