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 inline 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,const size_t width,size_t const height)257 static inline TileInfo AssignBestTileLocation(AshlarInfo *ashlar_info,
258 const size_t width,size_t const height)
259 {
260 NodeInfo
261 *node,
262 **previous,
263 *tail;
264
265 ssize_t
266 min_excess;
267
268 size_t
269 ashlar_width;
270
271 TileInfo
272 tile;
273
274 /*
275 Align along left edge.
276 */
277 tile.previous=(NodeInfo **) NULL;
278 ashlar_width=(width+ashlar_info->align-1);
279 ashlar_width-=ashlar_width % ashlar_info->align;
280 if ((ashlar_width > ashlar_info->width) || (height > ashlar_info->height))
281 {
282 /*
283 Tile can't fit, bail.
284 */
285 tile.x=0;
286 tile.y=0;
287 return(tile);
288 }
289 tile.x=(ssize_t) MAGICK_SSIZE_MAX;
290 tile.y=(ssize_t) MAGICK_SSIZE_MAX;
291 min_excess=(ssize_t) MAGICK_SSIZE_MAX;
292 node=ashlar_info->current;
293 previous=(&ashlar_info->current);
294 while ((ashlar_width+node->x) <= ashlar_info->width)
295 {
296 ssize_t
297 excess,
298 y;
299
300 y=FindMinimumTileLocation(node,node->x,ashlar_width,&excess);
301 if (ashlar_info->best_fit == MagickFalse)
302 {
303 if (y < tile.y)
304 {
305 tile.y=y;
306 tile.previous=previous;
307 }
308 }
309 else
310 {
311 if ((height+y) <= ashlar_info->height)
312 if ((y < tile.y) || ((y == tile.y) && (excess < min_excess)))
313 {
314 tile.y=y;
315 tile.previous=previous;
316 min_excess=excess;
317 }
318 }
319 previous=(&node->next);
320 node=node->next;
321 }
322 tile.x=(tile.previous == (NodeInfo **) NULL) ? 0 : (*tile.previous)->x;
323 if (ashlar_info->best_fit != MagickFalse)
324 {
325 /*
326 Align along both left and right edges.
327 */
328 tail=ashlar_info->current;
329 node=ashlar_info->current;
330 previous=(&ashlar_info->current);
331 while (tail->x < (ssize_t) ashlar_width)
332 tail=tail->next;
333 while (tail != (NodeInfo *) NULL)
334 {
335 ssize_t
336 excess,
337 x,
338 y;
339
340 x=tail->x-ashlar_width;
341 while (node->next->x <= x)
342 {
343 previous=(&node->next);
344 node=node->next;
345 }
346 y=FindMinimumTileLocation(node,x,ashlar_width,&excess);
347 if ((height+y) <= ashlar_info->height)
348 {
349 if (y <= tile.y)
350 if ((y < tile.y) || (excess < min_excess) ||
351 ((excess == min_excess) && (x < tile.x)))
352 {
353 tile.x=x;
354 tile.y=y;
355 min_excess=excess;
356 tile.previous=previous;
357 }
358 }
359 tail=tail->next;
360 }
361 }
362 return(tile);
363 }
364
AssignTileLocation(AshlarInfo * ashlar_info,const size_t width,const size_t height)365 static inline TileInfo AssignTileLocation(AshlarInfo *ashlar_info,
366 const size_t width,const size_t height)
367 {
368 NodeInfo
369 *current,
370 *node;
371
372 TileInfo
373 tile;
374
375 /*
376 Find the best location in the canvas for this tile.
377 */
378 tile=AssignBestTileLocation(ashlar_info,width,height);
379 if ((tile.previous == (NodeInfo **) NULL) ||
380 ((tile.y+(ssize_t) height) > (ssize_t) ashlar_info->height) ||
381 (ashlar_info->free == (NodeInfo *) NULL))
382 {
383 tile.previous=(NodeInfo **) NULL;
384 return(tile);
385 }
386 /*
387 Create a new node.
388 */
389 node=ashlar_info->free;
390 node->x=(ssize_t) tile.x;
391 node->y=(ssize_t) (tile.y+height);
392 ashlar_info->free=node->next;
393 /*
394 Insert node.
395 */
396 current=(*tile.previous);
397 if (current->x >= tile.x)
398 *tile.previous=node;
399 else
400 {
401 NodeInfo *next = current->next;
402 current->next=node;
403 current=next;
404 }
405 while ((current->next != (NodeInfo *) NULL) &&
406 (current->next->x <= (tile.x+(ssize_t) width)))
407 {
408 /*
409 Push current node to free list.
410 */
411 NodeInfo *next = current->next;
412 current->next=ashlar_info->free;
413 ashlar_info->free=current;
414 current=next;
415 }
416 node->next=current;
417 if (current->x < (tile.x+(ssize_t) width))
418 current->x=(ssize_t) (tile.x+width);
419 return(tile);
420 }
421
CompareTileHeight(const void * p_tile,const void * q_tile)422 static inline int CompareTileHeight(const void *p_tile,const void *q_tile)
423 {
424 const CanvasInfo
425 *p,
426 *q;
427
428 p=(const CanvasInfo *) p_tile;
429 q=(const CanvasInfo *) q_tile;
430 if (p->height > q->height)
431 return(-1);
432 if (p->height < q->height)
433 return(1);
434 return((p->width > q->width) ? -1 : (p->width < q->width) ? 1 : 0);
435 }
436
RestoreTileOrder(const void * p_tile,const void * q_tile)437 static inline int RestoreTileOrder(const void *p_tile,const void *q_tile)
438 {
439 const CanvasInfo
440 *p,
441 *q;
442
443 p=(const CanvasInfo *) p_tile;
444 q=(const CanvasInfo *) q_tile;
445 return((p->order < q->order) ? -1 : (p->order > q->order) ? 1 : 0);
446 }
447
PackAshlarTiles(AshlarInfo * ashlar_info,const size_t number_tiles,CanvasInfo * tiles)448 static inline MagickBooleanType PackAshlarTiles(AshlarInfo *ashlar_info,
449 const size_t number_tiles,CanvasInfo *tiles)
450 {
451 MagickBooleanType
452 status;
453
454 ssize_t
455 i;
456
457 /*
458 Pack tiles so they fit the canvas with minimum excess.
459 */
460 for (i=0; i < (ssize_t) number_tiles; i++)
461 tiles[i].order=(i);
462 qsort((void *) tiles,number_tiles,sizeof(*tiles),CompareTileHeight);
463 for (i=0; i < (ssize_t) number_tiles; i++)
464 {
465 tiles[i].x=0;
466 tiles[i].y=0;
467 if ((tiles[i].width != 0) && (tiles[i].height != 0))
468 {
469 TileInfo
470 tile_info;
471
472 tile_info=AssignTileLocation(ashlar_info,tiles[i].width,
473 tiles[i].height);
474 tiles[i].x=(ssize_t) tile_info.x;
475 tiles[i].y=(ssize_t) tile_info.y;
476 if (tile_info.previous == (NodeInfo **) NULL)
477 {
478 tiles[i].x=(ssize_t) MAGICK_SSIZE_MAX;
479 tiles[i].y=(ssize_t) MAGICK_SSIZE_MAX;
480 }
481 }
482 }
483 qsort((void *) tiles,number_tiles,sizeof(*tiles),RestoreTileOrder);
484 status=MagickTrue;
485 for (i=0; i < (ssize_t) number_tiles; i++)
486 {
487 tiles[i].order=(ssize_t) ((tiles[i].x != (ssize_t) MAGICK_SSIZE_MAX) ||
488 (tiles[i].y != (ssize_t) MAGICK_SSIZE_MAX) ? 1 : 0);
489 if (tiles[i].order == 0)
490 status=MagickFalse;
491 }
492 return(status); /* return true if room is found for all tiles */
493 }
494
WriteASHLARImage(const ImageInfo * image_info,Image * image,ExceptionInfo * exception)495 static MagickBooleanType WriteASHLARImage(const ImageInfo *image_info,
496 Image *image,ExceptionInfo *exception)
497 {
498 AshlarInfo
499 ashlar_info;
500
501 CanvasInfo
502 *tiles;
503
504 const char
505 *value;
506
507 Image
508 *ashlar_image,
509 *next;
510
511 ImageInfo
512 *write_info;
513
514 MagickBooleanType
515 status;
516
517 NodeInfo
518 *nodes;
519
520 RectangleInfo
521 extent,
522 geometry;
523
524 ssize_t
525 i,
526 n;
527
528 /*
529 Convert image sequence laid out in continuous irregular courses.
530 */
531 assert(image_info != (const ImageInfo *) NULL);
532 assert(image_info->signature == MagickCoreSignature);
533 assert(image != (Image *) NULL);
534 assert(image->signature == MagickCoreSignature);
535 if (image->debug != MagickFalse)
536 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
537 if (image_info->extract != (char *) NULL)
538 (void) ParseAbsoluteGeometry(image_info->extract,&geometry);
539 else
540 {
541 /*
542 Determine a sane canvas size and border width.
543 */
544 (void) ParseAbsoluteGeometry("0x0+0+0",&geometry);
545 for (next=image; next != (Image *) NULL; next=GetNextImageInList(next))
546 {
547 geometry.width+=next->columns;
548 geometry.height+=next->rows;
549 }
550 geometry.width=(size_t) geometry.width/7;
551 geometry.height=(size_t) geometry.height/7;
552 geometry.x=(ssize_t) pow((double) geometry.width,0.25);
553 geometry.y=(ssize_t) pow((double) geometry.height,0.25);
554 }
555 /*
556 Initialize image tiles.
557 */
558 ashlar_image=AcquireImage(image_info,exception);
559 status=SetImageExtent(ashlar_image,geometry.width,geometry.height,exception);
560 if (status == MagickFalse)
561 {
562 ashlar_image=DestroyImageList(ashlar_image);
563 return(MagickFalse);
564 }
565 (void) SetImageBackgroundColor(ashlar_image,exception);
566 tiles=(CanvasInfo *) AcquireQuantumMemory(GetImageListLength(image),
567 sizeof(*tiles));
568 ashlar_info.number_nodes=2*geometry.width;
569 nodes=(NodeInfo *) AcquireQuantumMemory(ashlar_info.number_nodes,
570 sizeof(*nodes));
571 if ((tiles == (CanvasInfo *) NULL) || (nodes == (NodeInfo *) NULL))
572 {
573 if (tiles != (CanvasInfo *) NULL)
574 tiles=(CanvasInfo *) RelinquishMagickMemory(tiles);
575 if (nodes != (NodeInfo *) NULL)
576 nodes=(NodeInfo *) RelinquishMagickMemory(tiles);
577 ashlar_image=DestroyImageList(ashlar_image);
578 ThrowWriterException(ResourceLimitError,"MemoryAllocationFailed");
579 }
580 /*
581 Interate until we find a tile size that fits the canvas.
582 */
583 value=GetImageOption(image_info,"ashlar:best-fit");
584 for (i=20; i > 0; i--)
585 {
586 ssize_t
587 j;
588
589 n=0;
590 for (next=image; next != (Image *) NULL; next=GetNextImageInList(next))
591 {
592 tiles[n].id=n;
593 tiles[n].width=(size_t) (0.05*i*next->columns+2*geometry.x);
594 tiles[n].height=(size_t) (0.05*i*next->rows+2*geometry.y);
595 n++;
596 }
597 for (j=0; j < (ssize_t) ashlar_info.number_nodes-1; j++)
598 nodes[j].next=nodes+j+1;
599 nodes[j].next=(NodeInfo *) NULL;
600 ashlar_info.best_fit=IsStringTrue(value) != MagickFalse ? MagickTrue :
601 MagickFalse;
602 ashlar_info.free=nodes;
603 ashlar_info.current=(&ashlar_info.head);
604 ashlar_info.width=geometry.width;
605 ashlar_info.height=geometry.height;
606 ashlar_info.align=(ssize_t) ((ashlar_info.width+ashlar_info.number_nodes-1)/
607 ashlar_info.number_nodes);
608 ashlar_info.head.x=0;
609 ashlar_info.head.y=0;
610 ashlar_info.head.next=(&ashlar_info.sentinal);
611 ashlar_info.sentinal.x=(ssize_t) geometry.width;
612 ashlar_info.sentinal.y=(ssize_t) MAGICK_SSIZE_MAX;
613 ashlar_info.sentinal.next=(NodeInfo *) NULL;
614 status=PackAshlarTiles(&ashlar_info,(size_t) n,tiles);
615 if (status != MagickFalse)
616 break;
617 }
618 /*
619 Determine layout of images tiles on the canvas.
620 */
621 value=GetImageOption(image_info,"label");
622 extent.width=0;
623 extent.height=0;
624 for (i=0; i < n; i++)
625 {
626 Image
627 *tile_image;
628
629 if ((tiles[i].x == (ssize_t) MAGICK_SSIZE_MAX) ||
630 (tiles[i].y == (ssize_t) MAGICK_SSIZE_MAX))
631 continue;
632 tile_image=ResizeImage(GetImageFromList(image,tiles[i].id),(size_t)
633 (tiles[i].width-2*geometry.x),(size_t) (tiles[i].height-2*geometry.y),
634 image->filter,exception);
635 if (tile_image == (Image *) NULL)
636 continue;
637 (void) CompositeImage(ashlar_image,tile_image,image->compose,MagickTrue,
638 tiles[i].x+geometry.x,tiles[i].y+geometry.y,exception);
639 if (value != (const char *) NULL)
640 {
641 char
642 *label,
643 offset[MagickPathExtent];
644
645 DrawInfo
646 *draw_info = CloneDrawInfo(image_info,(DrawInfo *) NULL);
647
648 label=InterpretImageProperties((ImageInfo *) image_info,tile_image,
649 value,exception);
650 if (label != (const char *) NULL)
651 {
652 (void) CloneString(&draw_info->text,label);
653 draw_info->pointsize=1.8*geometry.y;
654 (void) FormatLocaleString(offset,MagickPathExtent,"%+g%+g",(double)
655 tiles[i].x+geometry.x,(double) tiles[i].height+tiles[i].y+
656 geometry.y/2.0);
657 (void) CloneString(&draw_info->geometry,offset);
658 (void) AnnotateImage(ashlar_image,draw_info,exception);
659 }
660 }
661 if ((tiles[i].width+tiles[i].x) > extent.width)
662 extent.width=(size_t) (tiles[i].width+tiles[i].x);
663 if ((tiles[i].height+tiles[i].y+geometry.y+2) > extent.height)
664 extent.height=(size_t) (tiles[i].height+tiles[i].y+geometry.y+2);
665 tile_image=DestroyImage(tile_image);
666 }
667 (void) SetImageExtent(ashlar_image,extent.width,extent.height,exception);
668 nodes=(NodeInfo *) RelinquishMagickMemory(nodes);
669 tiles=(CanvasInfo *) RelinquishMagickMemory(tiles);
670 /*
671 Write ASHLAR canvas.
672 */
673 (void) CopyMagickString(ashlar_image->filename,image_info->filename,
674 MagickPathExtent);
675 write_info=CloneImageInfo(image_info);
676 *write_info->magick='\0';
677 (void) SetImageInfo(write_info,1,exception);
678 if ((*write_info->magick == '\0') ||
679 (LocaleCompare(write_info->magick,"ASHLAR") == 0))
680 (void) FormatLocaleString(ashlar_image->filename,MagickPathExtent,
681 "miff:%s",write_info->filename);
682 status=WriteImage(write_info,ashlar_image,exception);
683 ashlar_image=DestroyImage(ashlar_image);
684 write_info=DestroyImageInfo(write_info);
685 return(MagickTrue);
686 }
687