home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / x / volume20 / imagemgc / part33 < prev    next >
Encoding:
Text File  |  1993-07-13  |  50.3 KB  |  1,428 lines

  1. Newsgroups: comp.sources.x
  2. From: cristy@eplrx7.es.duPont.com (Cristy)
  3. Subject: v20i089:  imagemagic - X11 image processing and display, Part33/38
  4. Message-ID: <1993Jul14.232220.23319@sparky.sterling.com>
  5. X-Md4-Signature: ec31088fd201c700d23f4f459271de9b
  6. Sender: chris@sparky.sterling.com (Chris Olson)
  7. Organization: Sterling Software
  8. Date: Wed, 14 Jul 1993 23:22:20 GMT
  9. Approved: chris@sterling.com
  10.  
  11. Submitted-by: cristy@eplrx7.es.duPont.com (Cristy)
  12. Posting-number: Volume 20, Issue 89
  13. Archive-name: imagemagic/part33
  14. Environment: X11
  15. Supersedes: imagemagic: Volume 13, Issue 17-37
  16.  
  17. #!/bin/sh
  18. # this is magick.33 (part 33 of ImageMagick)
  19. # do not concatenate these parts, unpack them in order with /bin/sh
  20. # file ImageMagick/utility.c continued
  21. #
  22. if test ! -r _shar_seq_.tmp; then
  23.     echo 'Please unpack part 1 first!'
  24.     exit 1
  25. fi
  26. (read Scheck
  27.  if test "$Scheck" != 33; then
  28.     echo Please unpack part "$Scheck" next!
  29.     exit 1
  30.  else
  31.     exit 0
  32.  fi
  33. ) < _shar_seq_.tmp || exit 1
  34. if test ! -f _shar_wnt_.tmp; then
  35.     echo 'x - still skipping ImageMagick/utility.c'
  36. else
  37. echo 'x - continuing file ImageMagick/utility.c'
  38. sed 's/^X//' << 'SHAR_EOF' >> 'ImageMagick/utility.c' &&
  39. X  buffer[1]=(unsigned char) ((value) >> 8);
  40. X  (void) fwrite((char *) buffer,1,2,file);
  41. }
  42. X
  43. /*
  44. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  45. %                                                                             %
  46. %                                                                             %
  47. %                                                                             %
  48. %  M S B F i r s t O r d e r L o n g                                          %
  49. %                                                                             %
  50. %                                                                             %
  51. %                                                                             %
  52. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  53. %
  54. %  Function MSBFirstOrderLong converts a least-significant byte first buffer
  55. %  of longegers to most-significant byte first.
  56. %
  57. %  The format of the MSBFirstOrderLong routine is:
  58. %
  59. %       MSBFirstOrderLong(p,length);
  60. %
  61. %  A description of each parameter follows.
  62. %
  63. %   o  p:  Specifies a pointer to a buffer of integers.
  64. %
  65. %   o  length:  Specifies the length of the buffer.
  66. %
  67. %
  68. */
  69. void MSBFirstOrderLong(p,length)
  70. register char
  71. X  *p;
  72. X
  73. register unsigned int
  74. X  length;
  75. {
  76. X  register char
  77. X    c,
  78. X    *q,
  79. X    *sp;
  80. X
  81. X  q=p+length;
  82. X  while (p < q)
  83. X  {
  84. X    sp=p+3;
  85. X    c=(*sp);
  86. X    *sp=(*p);
  87. X    *p++=c;
  88. X    sp=p+1;
  89. X    c=(*sp);
  90. X    *sp=(*p);
  91. X    *p++=c;
  92. X    p+=2;
  93. X  }
  94. }
  95. X
  96. /*
  97. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  98. %                                                                             %
  99. %                                                                             %
  100. %                                                                             %
  101. %  M S B F i r s t O r d e r S h o r t                                        %
  102. %                                                                             %
  103. %                                                                             %
  104. %                                                                             %
  105. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  106. %
  107. %  Function MSBFirstOrderShort converts a least-significant byte first buffer
  108. %  of shortegers to most-significant byte first.
  109. %
  110. %  The format of the MSBFirstOrderShort routine is:
  111. %
  112. %       MSBFirstOrderLongShort(p,length);
  113. %
  114. %  A description of each parameter follows.
  115. %
  116. %   o  p:  Specifies a pointer to a buffer of integers.
  117. %
  118. %   o  length:  Specifies the length of the buffer.
  119. %
  120. %
  121. */
  122. void MSBFirstOrderShort(p,length)
  123. register char
  124. X  *p;
  125. X
  126. register unsigned int
  127. X  length;
  128. {
  129. X  register char
  130. X    c,
  131. X    *q;
  132. X
  133. X  q=p+length;
  134. X  while (p < q)
  135. X  {
  136. X    c=(*p);
  137. X    *p=(*(p+1));
  138. X    p++;
  139. X    *p++=c;
  140. X  }
  141. }
  142. X
  143. /*
  144. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  145. %                                                                             %
  146. %                                                                             %
  147. %                                                                             %
  148. %  M S B F i r s t R e a d S h o r t                                          %
  149. %                                                                             %
  150. %                                                                             %
  151. %                                                                             %
  152. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  153. %
  154. %  Function MSBFirstReadShort reads a short value as a 16 bit quantity in
  155. %  most-significant byte first order.
  156. %
  157. %  The format of the MSBFirstReadShort routine is:
  158. %
  159. %       value=MSBFirstReadShort(file)
  160. %
  161. %  A description of each parameter follows.
  162. %
  163. %    o value:  Function MSBFirstReadShort returns an unsigned short read from
  164. %      the file.
  165. %
  166. %   o  file:  Specifies the file to read the data from.
  167. %
  168. %
  169. */
  170. unsigned short MSBFirstReadShort(file)
  171. FILE
  172. X  *file;
  173. {
  174. X  unsigned char
  175. X    buffer[2];
  176. X
  177. X  unsigned int
  178. X    status;
  179. X
  180. X  unsigned short
  181. X    value;
  182. X
  183. X  status=ReadData((char *) buffer,1,2,file);
  184. X  if (status == False)
  185. X    return((unsigned long) ~0);
  186. X  value=(unsigned int) (buffer[0] << 8);
  187. X  value|=(unsigned int) (buffer[1]);
  188. X  return(value);
  189. }
  190. X
  191. /*
  192. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  193. %                                                                             %
  194. %                                                                             %
  195. %                                                                             %
  196. %  M S B F i r s t R e a d L o n g                                            %
  197. %                                                                             %
  198. %                                                                             %
  199. %                                                                             %
  200. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  201. %
  202. %  Function MSBFirstReadLong reads a long value as a 32 bit quantity in
  203. %  most-significant byte first order.
  204. %
  205. %  The format of the MSBFirstReadLong routine is:
  206. %
  207. %       value=MSBFirstReadLong(file)
  208. %
  209. %  A description of each parameter follows.
  210. %
  211. %    o value:  Function MSBFirstReadLong returns an unsigned long read from
  212. %      the file.
  213. %
  214. %   o  file:  Specifies the file to read the data from.
  215. %
  216. %
  217. */
  218. unsigned long MSBFirstReadLong(file)
  219. FILE
  220. X  *file;
  221. {
  222. X  unsigned char
  223. X    buffer[4];
  224. X
  225. X  unsigned int
  226. X    status;
  227. X
  228. X  unsigned long
  229. X    value;
  230. X
  231. X  status=ReadData((char *) buffer,1,4,file);
  232. X  if (status == False)
  233. X    return((unsigned long) ~0);
  234. X  value=(unsigned int) (buffer[0] << 24);
  235. X  value|=(unsigned int) (buffer[1] << 16);
  236. X  value|=(unsigned int) (buffer[2] << 8);
  237. X  value|=(unsigned int) (buffer[3]);
  238. X  return(value);
  239. }
  240. X
  241. /*
  242. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  243. %                                                                             %
  244. %                                                                             %
  245. %                                                                             %
  246. %  M S B F i r s t W r i t e L o n g                                          %
  247. %                                                                             %
  248. %                                                                             %
  249. %                                                                             %
  250. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  251. %
  252. %  Function MSBFirstWriteLong writes a long value as a 32 bit quantity in
  253. %  most-significant byte first order.
  254. %
  255. %  The format of the MSBFirstWriteLong routine is:
  256. %
  257. %       MSBFirstWriteLong(value,file)
  258. %
  259. %  A description of each parameter follows.
  260. %
  261. %   o  value:  Specifies the value to write.
  262. %
  263. %   o  file:  Specifies the file to write the data to.
  264. %
  265. %
  266. */
  267. void MSBFirstWriteLong(value,file)
  268. unsigned long
  269. X  value;
  270. X
  271. FILE
  272. X  *file;
  273. {
  274. X  unsigned char
  275. X    buffer[4];
  276. X
  277. X  buffer[0]=(unsigned char) ((value) >> 24);
  278. X  buffer[1]=(unsigned char) ((value) >> 16);
  279. X  buffer[2]=(unsigned char) ((value) >> 8);
  280. X  buffer[3]=(unsigned char) (value);
  281. X  (void) fwrite((char *) buffer,1,4,file);
  282. }
  283. X
  284. /*
  285. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  286. %                                                                             %
  287. %                                                                             %
  288. %                                                                             %
  289. %  M S B F i r s t W r i t e S h o r t                                        %
  290. %                                                                             %
  291. %                                                                             %
  292. %                                                                             %
  293. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  294. %
  295. %  Function MSBFirstWriteShort writes a long value as a 16 bit quantity in
  296. %  most-significant byte first order.
  297. %
  298. %  The format of the MSBFirstWriteShort routine is:
  299. %
  300. %       MSBFirstWriteShort(value,file)
  301. %
  302. %  A description of each parameter follows.
  303. %
  304. %   o  value:  Specifies the value to write.
  305. %
  306. %   o  file:  Specifies the file to write the data to.
  307. %
  308. %
  309. */
  310. void MSBFirstWriteShort(value,file)
  311. unsigned int
  312. X  value;
  313. X
  314. FILE
  315. X  *file;
  316. {
  317. X  unsigned char
  318. X    buffer[2];
  319. X
  320. X  buffer[0]=(unsigned char) ((value) >> 8);
  321. X  buffer[1]=(unsigned char) (value);
  322. X  (void) fwrite((char *) buffer,1,2,file);
  323. }
  324. X
  325. /*
  326. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  327. %                                                                             %
  328. %                                                                             %
  329. %                                                                             %
  330. %  R e a d D a t a                                                            %
  331. %                                                                             %
  332. %                                                                             %
  333. %                                                                             %
  334. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  335. %
  336. %  Function ReadData reads data from the image file and returns it.  If it
  337. %  cannot read the requested number of items, False is returned indicating
  338. %  an error.
  339. %
  340. %  The format of the ReadData routine is:
  341. %
  342. %      status=ReadData(data,size,number_items,file)
  343. %
  344. %  A description of each parameter follows:
  345. %
  346. %    o status:  Function ReadData returns True if all the data requested
  347. %      is obtained without error, otherwise False.
  348. %
  349. %    o data:  Specifies an area to place the information reuested from
  350. %      the file.
  351. %
  352. %    o size:  Specifies an integer representing the length of an
  353. %      individual item to be read from the file.
  354. %
  355. %    o number_items:  Specifies an integer representing the number of items
  356. %      to read from the file.
  357. %
  358. %    o file:  Specifies a file to read the data.
  359. %
  360. %
  361. */
  362. unsigned int ReadData(data,size,number_items,file)
  363. char
  364. X  *data;
  365. X
  366. int
  367. X  size,
  368. X  number_items;
  369. X
  370. FILE
  371. X  *file;
  372. {
  373. X  size*=number_items;
  374. X  while (size > 0)
  375. X  {
  376. X    number_items=fread(data,1,size,file);
  377. X    if (number_items <= 0)
  378. X      return(False);
  379. X    size-=number_items;
  380. X    data+=number_items;
  381. X  }
  382. X  return(True);
  383. }
  384. X
  385. /*
  386. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  387. %                                                                             %
  388. %                                                                             %
  389. %                                                                             %
  390. %  R e a d D a t a B l o c k                                                  %
  391. %                                                                             %
  392. %                                                                             %
  393. %                                                                             %
  394. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  395. %
  396. %  Function ReadDataBlock reads data from the image file and returns it.  The
  397. %  amount of data is determined by first reading a count byte.  If
  398. %  ReadDataBlock cannot read the requested number of items, `-1' is returned
  399. %  indicating an error.
  400. %
  401. %  The format of the ReadData routine is:
  402. %
  403. %      status=ReadData(data,file)
  404. %
  405. %  A description of each parameter follows:
  406. %
  407. %    o status:  Function ReadData returns the number of characters read
  408. %      unless the is an error, otherwise `-1'.
  409. %
  410. %    o data:  Specifies an area to place the information reuested from
  411. %      the file.
  412. %
  413. %    o file:  Specifies a file to read the data.
  414. %
  415. %
  416. */
  417. int ReadDataBlock(data,file)
  418. char
  419. X  *data;
  420. X
  421. FILE
  422. X  *file;
  423. {
  424. X  unsigned char
  425. X    count;
  426. X
  427. X  unsigned int
  428. X    status;
  429. X
  430. X  status=ReadData((char *) &count,1,1,file);
  431. X  if (status == False)
  432. X    return(-1);
  433. X  if (count == 0)
  434. X    return(0);
  435. X  status=ReadData(data,1,(int) count,file);
  436. X  if (status == False)
  437. X    return(-1);
  438. X  return(count);
  439. }
  440. SHAR_EOF
  441. echo 'File ImageMagick/utility.c is complete' &&
  442. chmod 0644 ImageMagick/utility.c ||
  443. echo 'restore of ImageMagick/utility.c failed'
  444. Wc_c="`wc -c < 'ImageMagick/utility.c'`"
  445. test 21343 -eq "$Wc_c" ||
  446.     echo 'ImageMagick/utility.c: original size 21343, current size' "$Wc_c"
  447. rm -f _shar_wnt_.tmp
  448. fi
  449. # ============= ImageMagick/quantize.man ==============
  450. if test -f 'ImageMagick/quantize.man' -a X"$1" != X"-c"; then
  451.     echo 'x - skipping ImageMagick/quantize.man (File already exists)'
  452.     rm -f _shar_wnt_.tmp
  453. else
  454. > _shar_wnt_.tmp
  455. echo 'x - extracting ImageMagick/quantize.man (Text)'
  456. sed 's/^X//' << 'SHAR_EOF' > 'ImageMagick/quantize.man' &&
  457. .ad l
  458. .nh
  459. .TH quantize 9 "10 October 1992" "ImageMagick"
  460. .SH NAME
  461. Quantize - ImageMagick's color reduction algorithm.
  462. .SH SYNOPSIS
  463. .B #include <image.h>
  464. .SH DESCRIPTION
  465. This document describes how \fBImageMagick\fP performs color reduction on an
  466. image.  To fully understand this document, you should have a knowledge
  467. of basic imaging techniques and the tree data structure and terminology.
  468. .PP
  469. For purposes of color allocation, an image is a set of \fIn\fP pixels,
  470. where each pixel is a point in RGB space.  RGB space is a 3-dimensional
  471. vector space, and each pixel, \fIp\d\s-3i\s0\u\fP,  is defined by an
  472. ordered triple of red, green, and blue coordinates, (\fIr\d\s-3i\s0\u,
  473. g\d\s-3i\s0\u, b\d\s-3i\s0\u\fP).
  474. .PP
  475. Each primary color component (red, green, or blue) represents an
  476. intensity which varies linearly from 0 to a maximum value,
  477. \fIc\d\s-3max\s0\u\fP, which corresponds to full saturation of that
  478. color.  Color allocation is defined over a domain consisting of the
  479. cube in RGB space with opposite vertices at (0,0,0) and
  480. (\fIc\d\s-3max\s0\u,c\d\s-3max\s0\u,c\d\s-3max\s0\u\fP).  \fBImageMagick\fP
  481. requires \fIc\d\s-3max\s0\u = 255\fP.
  482. .PP
  483. The algorithm maps this domain onto a tree in which each node
  484. represents a cube within that domain.  In the following discussion,
  485. these cubes are defined by the coordinate of two opposite vertices: The
  486. vertex nearest the origin in RGB space and the vertex farthest from the
  487. origin.
  488. .PP
  489. The tree's root node represents the the entire domain, (0,0,0) through
  490. (\fIc\d\s-3max\s0\u,c\d\s-3max\s0\u,c\d\s-3max\s0\u\fP).  Each lower level in
  491. the tree is generated by subdividing one node's cube into eight smaller
  492. cubes of equal size.  This corresponds to bisecting the parent cube
  493. with planes passing through the midpoints of each edge.
  494. .PP
  495. The basic algorithm operates in three phases:  \fBClassification,
  496. Reduction\fP, and \fBAssignment\fP.  \fBClassification\fP builds a
  497. color description tree for the image.  \fBReduction\fP collapses the
  498. tree until the number it represents, at most, is the number of colors
  499. desired in the output image.  \fBAssignment\fP defines the output
  500. image's color map and sets each pixel's color by reclassification in
  501. the reduced tree.
  502. .PP
  503. \fBClassification\fP begins by initializing a color description tree of
  504. sufficient depth to represent each possible input color in a leaf.
  505. However, it is impractical to generate a fully-formed color description
  506. tree in the classification phase for realistic values of
  507. \fIc\d\s-3max\s0\u\fP.  If color components in the input image are
  508. quantized to \fIk\fP-bit precision, so that \fIc\d\s-3max\s0\u =
  509. 2\u\s-3k\s0\d-1\fP, the tree would need \fIk\fP levels below the root
  510. node to allow representing each possible input color in a leaf.  This
  511. becomes prohibitive because the tree's total number of nodes is
  512. .PP
  513. X        \fI\s+6\(*S\u\s-9 k\d\di=1\s0 8k\fP\s0\u
  514. .PP
  515. A complete tree would require 19,173,961 nodes for \fIk = 8,
  516. c\d\s-3max\s0\u = 255\fP.  Therefore, to avoid building a fully
  517. populated tree, \fBImageMagick\fP: (1) Initializes data structures for
  518. nodes only as they are needed; (2) Chooses a maximum depth for the tree
  519. as a function of the desired number of colors in the output image
  520. (currently \fIlog\d\s-34\s0\u(colormap size)\+2\fP).  A tree of this
  521. depth generally allows the best representation of the source image with
  522. the fastest computational speed and the least amount of memory.
  523. However, the default depth is inappropriate for some images.
  524. Therefore, the caller can request a specific tree depth.
  525. .PP
  526. For each pixel in the input image, classification scans downward from
  527. the root of the color description tree.  At each level of the tree, it
  528. identifies the single node which represents a cube in RGB space
  529. containing the pixel's color.  It updates the following data for each
  530. such node:
  531. .TP 5
  532. .B n\d\s-31\s0\u:
  533. Number of pixels whose color is contained in the RGB cube which this
  534. node represents;
  535. .TP 5
  536. .B n\d\s-32\s0\u:
  537. Number of pixels whose color is not represented in a node at lower
  538. depth in the tree;  initially,  \fIn\d\s-32\s0\u = 0\fP for all nodes
  539. except leaves of the tree.
  540. .TP 5
  541. .B S\d\s-3r\s0\u, S\d\s-3g\s0\u, S\d\s-3b\s0\u:
  542. Sums of the red, green, and blue component values for all pixels not
  543. classified at a lower depth.  The combination of these sums and
  544. \fIn\d\s-32\s0\u\fP will ultimately characterize the mean color of a
  545. set of pixels represented by this node.
  546. .PP
  547. \fBReduction\fP repeatedly prunes the tree until the number of nodes with
  548. \fIn\d\s-32\s0\u  > 0\fP is less than or equal to the maximum number of colors
  549. allowed in the output image.  On any given iteration over the tree, it
  550. selects those nodes whose \fIn\d\s-31\s0\u\fP count is minimal for pruning and
  551. merges their color statistics upward.  It uses a pruning threshold,
  552. \fIn\d\s-3p\s0\u\fP, to govern node selection as follows:
  553. .PP
  554. X  n\d\s-3p\s0\u = 0
  555. X  while number of nodes with (n\d\s-32\s0\u > 0) > required maximum number of colors
  556. X      prune all nodes such that n\d\s-31\s0\u <= n\d\s-3p\s0\u
  557. X      Set n\d\s-3p\s0\u  to minimum n\d\s-31\s0\u  in remaining nodes
  558. .PP
  559. When a node to be pruned has offspring, the pruning procedure invokes
  560. itself recursively in order to prune the tree from the leaves upward.
  561. The values of \fIn\d\s-32\s0\u  S\d\s-3r\s0\u, S\d\s-3g\s0\u,\fP  and
  562. \fIS\d\s-3b\s0\u\fP in a node being pruned are always added to the
  563. corresponding data in that node's parent.  This retains the pruned
  564. node's color characteristics for later averaging.
  565. .PP
  566. For each node,  \fIn\d\s-32\s0\u\fP pixels exist for which that node
  567. represents the smallest volume in RGB space containing those pixel's
  568. colors.  When \fIn\d\s-32\s0\u  > 0\fP the node will uniquely define a
  569. color in the output image.  At the beginning of reduction,
  570. \fIn\d\s-32\s0\u = 0\fP  for all nodes except the leaves of the tree
  571. which represent colors present in the input image.
  572. .PP
  573. The other pixel count, \fIn\d\s-31\s0\u\fP,  indicates the total
  574. number of colors within the cubic volume which the node represents.
  575. This includes \fIn\d\s-31\s0\u - n\d\s-32\s0\u\fP pixels whose colors
  576. should be defined by nodes at a lower level in the tree.
  577. .PP
  578. \fBAssignment\fP generates the output image from the pruned tree.  The
  579. output image consists of two parts:  (1)  A color map, which is an
  580. array of color descriptions (RGB triples) for each color present in the
  581. output image; (2)  A pixel array, which represents each pixel as an
  582. index into the color map array.
  583. .PP
  584. First, the assignment phase makes one pass over the pruned color
  585. description tree to establish the image's color map.  For each node
  586. with \fIn\d\s-32\s0\u > 0\fP, it divides \fIS\d\s-3r\s0\u,
  587. S\d\s-3g\s0\u\fP, and \fPS\d\s-3b\s0\u\fP by \fIn\d\s-32\s0\u\fP.  This
  588. produces the mean color of all pixels that classify no lower than this
  589. node.  Each of these colors becomes an entry in the color map.
  590. .PP
  591. Finally, the assignment phase reclassifies each pixel in the pruned
  592. tree to identify the deepest node containing the pixel's color.  The
  593. pixel's value in the pixel array becomes the index of this node's mean
  594. color in the color map.
  595. .PP
  596. Empirical evidence suggests that distances in color spaces such as
  597. YUV, or YIQ correspond to perceptual color differences more closely
  598. than do distances in RGB space.  These color spaces may give better
  599. results when color reducing an image.  Here the algorithm is as described
  600. except each pixel is a point in the alternate color space.  For convenience,
  601. the color components are normalized to the range 0 to a maximum value,
  602. \fIc\d\s-3max\s0\u\fP.  The color reduction can then proceed as described.
  603. .SH "MEASURING COLOR REDUCTION ERROR"
  604. .PP
  605. Depending on the image, the color reduction error may be obvious or
  606. invisible.  Images with high spatial frequencies (such as hair or
  607. grass) will show error much less than pictures with large smoothly
  608. shaded areas (such as faces).  This is because the high-frequency
  609. contour edges introduced by the color reduction process are masked by
  610. the high frequencies in the image.
  611. .PP
  612. To measure the difference between the original and color reduced images
  613. (the total color reduction error), \fBImageMagick\fP sums over all pixels
  614. in an image the distance squared in RGB space between each original
  615. pixel value and its color reduced value. \fBImageMagick\fP prints several error
  616. measurements including the mean error per pixel, the normalized mean error,
  617. and the normalized maximum error.
  618. .PP
  619. The normalized error measurement can be used to compare images.  In
  620. general, the closer the mean error is to zero the more the quantized
  621. image resembles the source image.  Ideally, the error should be
  622. perceptually-based, since the human eye is the final judge of
  623. quantization quality.
  624. .PP
  625. These errors are measured and printed when \fB-verbose\fP and \fB-colors\fI
  626. are specified on the command line:
  627. .TP 5
  628. .B mean error per pixel:
  629. is the mean error for any single pixel in the image.
  630. .TP 5
  631. .B normalized mean square error:
  632. is the normalized mean square quantization error for any single pixel in the
  633. image.
  634. X
  635. This distance measure is normalized to a range between 0 and 1.  It is
  636. independent of the range of red, green, and blue values in the image.
  637. .TP 5
  638. .B normalized maximum square error:
  639. is the largest normalized square quantization error for any single
  640. pixel in the image.
  641. X
  642. This distance measure is normalized to a range between 0 and 1.  It is
  643. independent of the range of red, green, and blue values in the image.
  644. .SH SEE ALSO
  645. .B
  646. display(1), animate(1), mogrify(1), import(1), miff(5)
  647. .SH COPYRIGHT
  648. Copyright 1993 E. I. du Pont de Nemours & Company
  649. .PP
  650. Permission to use, copy, modify, distribute, and sell this software and
  651. its documentation for any purpose is hereby granted without fee,
  652. provided that the above copyright notice appear in all copies and that
  653. both that copyright notice and this permission notice appear in
  654. supporting documentation, and that the name of E. I. du Pont de Nemours
  655. & Company not be used in advertising or publicity pertaining to
  656. distribution of the software without specific, written prior
  657. permission.  E. I. du Pont de Nemours & Company makes no representations
  658. about the suitability of this software for any purpose.  It is provided
  659. "as is" without express or implied warranty.
  660. .PP
  661. E. I. du Pont de Nemours & Company disclaims all warranties with regard
  662. to this software, including all implied warranties of merchantability
  663. and fitness, in no event shall E. I. du Pont de Nemours & Company be
  664. liable for any special, indirect or consequential damages or any
  665. damages whatsoever resulting from loss of use, data or profits, whether
  666. in an action of contract, negligence or other tortious action, arising
  667. out of or in connection with the use or performance of this software.
  668. .SH ACKNOWLEDGEMENTS
  669. Paul Raveling, USC Information Sciences Institute, for the original
  670. idea of using space subdivision for the color reduction algorithm.
  671. With Paul's permission, this document is an adaptation from a document he
  672. wrote.
  673. .SH AUTHORS
  674. John Cristy, E.I. du Pont de Nemours & Company Incorporated
  675. SHAR_EOF
  676. chmod 0644 ImageMagick/quantize.man ||
  677. echo 'restore of ImageMagick/quantize.man failed'
  678. Wc_c="`wc -c < 'ImageMagick/quantize.man'`"
  679. test 11046 -eq "$Wc_c" ||
  680.     echo 'ImageMagick/quantize.man: original size 11046, current size' "$Wc_c"
  681. rm -f _shar_wnt_.tmp
  682. fi
  683. # ============= ImageMagick/utility.h ==============
  684. if test -f 'ImageMagick/utility.h' -a X"$1" != X"-c"; then
  685.     echo 'x - skipping ImageMagick/utility.h (File already exists)'
  686.     rm -f _shar_wnt_.tmp
  687. else
  688. > _shar_wnt_.tmp
  689. echo 'x - extracting ImageMagick/utility.h (Text)'
  690. sed 's/^X//' << 'SHAR_EOF' > 'ImageMagick/utility.h' &&
  691. X
  692. /*
  693. X  Utilities routines.
  694. */
  695. extern int
  696. X  ReadDataBlock _Declare((char *,FILE *));
  697. X
  698. extern unsigned int
  699. X  ReadData _Declare((char *,int,int,FILE *));
  700. X
  701. extern unsigned long
  702. X  LSBFirstReadLong _Declare((FILE *)),
  703. X  MSBFirstReadLong _Declare((FILE *));
  704. X
  705. extern unsigned short
  706. X  LSBFirstReadShort _Declare((FILE *)),
  707. X  MSBFirstReadShort _Declare((FILE *));
  708. X
  709. extern void
  710. X  LSBFirstWriteLong _Declare((unsigned long,FILE *)),
  711. X  LSBFirstWriteShort _Declare((unsigned int,FILE *)),
  712. X  MSBFirstOrderLong _Declare((char *,unsigned int)),
  713. X  MSBFirstOrderShort _Declare((char *,unsigned int)),
  714. X  MSBFirstWriteLong _Declare((unsigned long,FILE *)),
  715. X  MSBFirstWriteShort _Declare((unsigned int,FILE *));
  716. SHAR_EOF
  717. chmod 0644 ImageMagick/utility.h ||
  718. echo 'restore of ImageMagick/utility.h failed'
  719. Wc_c="`wc -c < 'ImageMagick/utility.h'`"
  720. test 690 -eq "$Wc_c" ||
  721.     echo 'ImageMagick/utility.h: original size 690, current size' "$Wc_c"
  722. rm -f _shar_wnt_.tmp
  723. fi
  724. # ============= ImageMagick/signature.c ==============
  725. if test -f 'ImageMagick/signature.c' -a X"$1" != X"-c"; then
  726.     echo 'x - skipping ImageMagick/signature.c (File already exists)'
  727.     rm -f _shar_wnt_.tmp
  728. else
  729. > _shar_wnt_.tmp
  730. echo 'x - extracting ImageMagick/signature.c (Text)'
  731. sed 's/^X//' << 'SHAR_EOF' > 'ImageMagick/signature.c' &&
  732. /*
  733. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  734. %                                                                             %
  735. %                                                                             %
  736. %        SSSSS  IIIII   GGGG  N   N   AAA   TTTTT  U   U  RRRR   EEEEE        %
  737. %        SS       I    G      NN  N  A   A    T    U   U  R   R  E            %
  738. %         SSS     I    G  GG  N N N  AAAAA    T    U   U  RRRR   EEE          %
  739. %           SS    I    G   G  N  NN  A   A    T    U   U  R R    E            %
  740. %        SSSSS  IIIII   GGG   N   N  A   A    T     UUU   R  R   EEEEE        %
  741. %                                                                             %
  742. %                                                                             %
  743. %               Compute a Digital Signature for a Image Colormap              %
  744. %                                                                             %
  745. %                                                                             %
  746. %                                                                             %
  747. %                           Software Design                                   %
  748. %                             John Cristy                                     %
  749. %                            December 1992                                    %
  750. %                                                                             %
  751. %  Copyright 1993 E. I. du Pont de Nemours & Company                          %
  752. %                                                                             %
  753. %  Permission to use, copy, modify, distribute, and sell this software and    %
  754. %  its documentation for any purpose is hereby granted without fee,           %
  755. %  provided that the above Copyright notice appear in all copies and that     %
  756. %  both that Copyright notice and this permission notice appear in            %
  757. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  758. %  & Company not be used in advertising or publicity pertaining to            %
  759. %  distribution of the software without specific, written prior               %
  760. %  permission.  E. I. du Pont de Nemours & Company makes no representations   %
  761. %  about the suitability of this software for any purpose.  It is provided    %
  762. %  "as is" without express or implied warranty.                               %
  763. %                                                                             %
  764. %  E. I. du Pont de Nemours & Company disclaims all warranties with regard    %
  765. %  to this software, including all implied warranties of merchantability      %
  766. %  and fitness, in no event shall E. I. du Pont de Nemours & Company be       %
  767. %  liable for any special, indirect or consequential damages or any           %
  768. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  769. %  in an action of contract, negligence or other tortious action, arising     %
  770. %  out of or in connection with the use or performance of this software.      %
  771. %                                                                             %
  772. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  773. %
  774. %  Routine ColormapSignature computes a digital signature from the image
  775. %  colormap.  This signature uniquely identifies the colormap and is convenient
  776. %  for determining if the colormap of a sequence of images is identical when
  777. %  animating.  The digital signature is from RSA Data Security MD5 Digest
  778. %  Algorithm described in Internet draft [MD5], July 1992.
  779. %
  780. %
  781. */
  782. X
  783. /*
  784. X  Include declarations.
  785. */
  786. #include "display.h"
  787. #include "image.h"
  788. X
  789. /*
  790. X  Typedef declarations.
  791. */
  792. typedef struct _MessageDigest
  793. {
  794. X  unsigned long
  795. X    number_bits[2],
  796. X    accumulator[4];
  797. X
  798. X  unsigned char
  799. X    message[64],
  800. X    digest[16];
  801. } MessageDigest;
  802. X
  803. /*
  804. X  External declarations.
  805. */
  806. extern char
  807. X  *client_name;
  808. X
  809. /*
  810. X  Forward declarations.
  811. */
  812. static void
  813. X  TransformMessageDigest _Declare((MessageDigest *,unsigned long *)),
  814. X  UpdateMessageDigest _Declare((MessageDigest *,unsigned char *,unsigned long));
  815. X
  816. /*
  817. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  818. %                                                                             %
  819. %                                                                             %
  820. %                                                                             %
  821. %   C o m p u t e M e s s a g e D i g e s t                                   %
  822. %                                                                             %
  823. %                                                                             %
  824. %                                                                             %
  825. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  826. %
  827. %  Function ComputeMessageDigest computes the message digest.
  828. %
  829. %  The format of the ComputeMessageDigest routine is:
  830. %
  831. %      ComputeMessageDigest(message_digest,input_message,message_length)
  832. %
  833. %  A description of each parameter follows:
  834. %
  835. %    o message_digest: The address of a structure of type MessageDigest.
  836. %
  837. %
  838. */
  839. static void ComputeMessageDigest(message_digest)
  840. MessageDigest
  841. X  *message_digest;
  842. {
  843. X  int
  844. X    number_bytes;
  845. X
  846. X  register unsigned char
  847. X    *p;
  848. X
  849. X  register unsigned int
  850. X    i;
  851. X
  852. X  unsigned char
  853. X    padding[64];
  854. X
  855. X  unsigned long
  856. X    message[16],
  857. X    padding_length;
  858. X
  859. X  /*
  860. X    Save number of bits.
  861. X  */
  862. X  message[14]=message_digest->number_bits[0];
  863. X  message[15]=message_digest->number_bits[1];
  864. X  /*
  865. X    Compute number of bytes mod 64.
  866. X  */
  867. X  number_bytes=(int) ((message_digest->number_bits[0] >> 3) & 0x3F);
  868. X  /*
  869. X    Pad message to 56 mod 64.
  870. X  */
  871. X  padding_length=(number_bytes < 56) ? (56-number_bytes) : (120-number_bytes);
  872. X  padding[0]=0x80;
  873. X  for (i=1; i < padding_length; i++)
  874. X    padding[i]=(char) 0;
  875. X  UpdateMessageDigest(message_digest,padding,padding_length);
  876. X  /*
  877. X    Append length in bits and transform.
  878. X  */
  879. X  p=message_digest->message;
  880. X  for (i=0; i < 14; i++)
  881. X  {
  882. X    message[i]=(unsigned long) (*p++);
  883. X    message[i]|=((unsigned long) (*p++)) << 8;
  884. X    message[i]|=((unsigned long) (*p++)) << 16;
  885. X    message[i]|=((unsigned long) (*p++)) << 24;
  886. X  }
  887. X  TransformMessageDigest(message_digest,message);
  888. X  /*
  889. X    Store message in digest.
  890. X  */
  891. X  p=message_digest->digest;
  892. X  for (i=0; i < 4; i++)
  893. X  {
  894. X    *p++=(unsigned char) (message_digest->accumulator[i] & 0xff);
  895. X    *p++=(unsigned char) ((message_digest->accumulator[i] >> 8) & 0xff);
  896. X    *p++=(unsigned char) ((message_digest->accumulator[i] >> 16) & 0xff);
  897. X    *p++=(unsigned char) ((message_digest->accumulator[i] >> 24) & 0xff);
  898. X  }
  899. }
  900. X
  901. /*
  902. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  903. %                                                                             %
  904. %                                                                             %
  905. %                                                                             %
  906. %   I n i t i a l i z e M e s s a g e D i g e s t                             %
  907. %                                                                             %
  908. %                                                                             %
  909. %                                                                             %
  910. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  911. %
  912. %  Function InitializeMessageDigest initializes the message digest structure.
  913. %
  914. %  The format of the InitializeMessageDigest routine is:
  915. %
  916. %      InitializeMessageDigest(message_digest)
  917. %
  918. %  A description of each parameter follows:
  919. %
  920. %    o message_digest: The address of a structure of type MessageDigest.
  921. %
  922. %
  923. */
  924. static void InitializeMessageDigest(message_digest)
  925. MessageDigest
  926. X  *message_digest;
  927. {
  928. X  message_digest->number_bits[0]=(unsigned long) 0;
  929. X  message_digest->number_bits[1]=(unsigned long) 0;
  930. X  /*
  931. X    Load magic initialization constants.
  932. X  */
  933. X  message_digest->accumulator[0]=(unsigned long) 0x67452301;
  934. X  message_digest->accumulator[1]=(unsigned long) 0xefcdab89;
  935. X  message_digest->accumulator[2]=(unsigned long) 0x98badcfe;
  936. X  message_digest->accumulator[3]=(unsigned long) 0x10325476;
  937. }
  938. X
  939. /*
  940. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  941. %                                                                             %
  942. %                                                                             %
  943. %                                                                             %
  944. %   T r a n s f o r m M e s s a g e D i g e s t                               %
  945. %                                                                             %
  946. %                                                                             %
  947. %                                                                             %
  948. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  949. %
  950. %  Function TransformMessageDigest updates the message digest.
  951. %
  952. %  The format of the TransformMessageDigest routine is:
  953. %
  954. %      TransformMessageDigest(message_digest,message)
  955. %
  956. %  A description of each parameter follows:
  957. %
  958. %    o message_digest: The address of a structure of type MessageDigest.
  959. %
  960. %
  961. */
  962. static void TransformMessageDigest(message_digest,message)
  963. MessageDigest
  964. X  *message_digest;
  965. X
  966. unsigned long
  967. X  *message;
  968. {
  969. #define F(x,y,z)  (((x) & (y)) | ((~x) & (z)))
  970. #define G(x,y,z)  (((x) & (z)) | ((y) & (~z)))
  971. #define H(x,y,z)  ((x) ^ (y) ^ (z))
  972. #define I(x,y,z)  ((y) ^ ((x) | (~z)))
  973. #define RotateLeft(x,n)  (((x) << (n)) | (((x) & 0xffffffff) >> (32-(n))))
  974. X
  975. X  static unsigned long
  976. X    additive_constant[64]=  /* 4294967296*abs(sin(i)), i in radians */
  977. X    {
  978. X      0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf,
  979. X      0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af,
  980. X      0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e,
  981. X      0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
  982. X      0xd62f105d, 0x2441453,  0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6,
  983. X      0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
  984. X      0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122,
  985. X      0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
  986. X      0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,  0xd9d4d039,
  987. X      0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244, 0x432aff97,
  988. X      0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d,
  989. X      0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
  990. X      0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391,
  991. X    };
  992. X
  993. X  register int
  994. X    i;
  995. X
  996. X  register unsigned int
  997. X    j;
  998. X
  999. X  register unsigned long
  1000. X    a,
  1001. X    b,
  1002. X    c,
  1003. X    d,
  1004. X    *p;
  1005. X
  1006. X  /*
  1007. X    Save accumulator.
  1008. X  */
  1009. X  a=message_digest->accumulator[0];
  1010. X  b=message_digest->accumulator[1];
  1011. X  c=message_digest->accumulator[2];
  1012. X  d=message_digest->accumulator[3];
  1013. X  /*
  1014. X    a=b+((a+F(b,c,d)+X[k]+t) <<< s).
  1015. X  */
  1016. X  p=additive_constant;
  1017. X  j=0;
  1018. X  for (i=0; i < 4; i++)
  1019. X  {
  1020. X    a+=F(b,c,d)+message[j & 0x0f]+(*p++);
  1021. X    a=RotateLeft(a,7)+b;
  1022. X    j++;
  1023. X    d+=F(a,b,c)+message[j & 0x0f]+(*p++);
  1024. X    d=RotateLeft(d,12)+a;
  1025. X    j++;
  1026. X    c+=F(d,a,b)+message[j & 0x0f]+(*p++);
  1027. X    c=RotateLeft(c,17)+d;
  1028. X    j++;
  1029. X    b+=F(c,d,a)+message[j & 0x0f]+(*p++);
  1030. X    b=RotateLeft(b,22)+c;
  1031. X    j++;
  1032. X  }
  1033. X  /*
  1034. X    a=b+((a+G(b,c,d)+X[k]+t) <<< s).
  1035. X  */
  1036. X  j=1;
  1037. X  for (i=0; i < 4; i++)
  1038. X  {
  1039. X    a+=G(b,c,d)+message[j & 0x0f]+(*p++);
  1040. X    a=RotateLeft(a,5)+b;
  1041. X    j+=5;
  1042. X    d+=G(a,b,c)+message[j & 0x0f]+(*p++);
  1043. X    d=RotateLeft(d,9)+a;
  1044. X    j+=5;
  1045. X    c+=G(d,a,b)+message[j & 0x0f]+(*p++);
  1046. X    c=RotateLeft(c,14)+d;
  1047. X    j+=5;
  1048. X    b+=G(c,d,a)+message[j & 0x0f]+(*p++);
  1049. X    b=RotateLeft(b,20)+c;
  1050. X    j+=5;
  1051. X  }
  1052. X  /*
  1053. X    a=b+((a+H(b,c,d)+X[k]+t) <<< s).
  1054. X  */
  1055. X  j=5;
  1056. X  for (i=0; i < 4; i++)
  1057. X  {
  1058. X    a+=H(b,c,d)+message[j & 0x0f]+(*p++);
  1059. X    a=RotateLeft(a,4)+b;
  1060. X    j+=3;
  1061. X    d+=H(a,b,c)+message[j & 0x0f]+(*p++);
  1062. X    d=RotateLeft(d,11)+a;
  1063. X    j+=3;
  1064. X    c+=H(d,a,b)+message[j & 0x0f]+(*p++);
  1065. X    c=RotateLeft(c,16)+d;
  1066. X    j+=3;
  1067. X    b+=H(c,d,a)+message[j & 0x0f]+(*p++);
  1068. X    b=RotateLeft(b,23)+c;
  1069. X    j+=3;
  1070. X  }
  1071. X  /*
  1072. X    a=b+((a+I(b,c,d)+X[k]+t) <<< s).
  1073. X  */
  1074. X  j=0;
  1075. X  for (i=0; i < 4; i++)
  1076. X  {
  1077. X    a+=I(b,c,d)+message[j & 0x0f]+(*p++);
  1078. X    a=RotateLeft(a,6)+b;
  1079. X    j+=7;
  1080. X    d+=I(a,b,c)+message[j & 0x0f]+(*p++);
  1081. X    d=RotateLeft(d,10)+a;
  1082. X    j+=7;
  1083. X    c+=I(d,a,b)+message[j & 0x0f]+(*p++);
  1084. X    c=RotateLeft(c,15)+d;
  1085. X    j+=7;
  1086. X    b+=I(c,d,a)+message[j & 0x0f]+(*p++);
  1087. X    b=RotateLeft(b,21)+c;
  1088. X    j+=7;
  1089. X  }
  1090. X  /*
  1091. X    Increment accumulator.
  1092. X  */
  1093. X  message_digest->accumulator[0]+=a;
  1094. X  message_digest->accumulator[1]+=b;
  1095. X  message_digest->accumulator[2]+=c;
  1096. X  message_digest->accumulator[3]+=d;
  1097. }
  1098. X
  1099. /*
  1100. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1101. %                                                                             %
  1102. %                                                                             %
  1103. %                                                                             %
  1104. %   U p d a t e M e s s a g e D i g e s t                                     %
  1105. %                                                                             %
  1106. %                                                                             %
  1107. %                                                                             %
  1108. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1109. %
  1110. %  Function UpdateMessageDigest updates the message digest.
  1111. %
  1112. %  The format of the UpdateMessageDigest routine is:
  1113. %
  1114. %      UpdateMessageDigest(message_digest,input_message,message_length)
  1115. %
  1116. %  A description of each parameter follows:
  1117. %
  1118. %    o message_digest: The address of a structure of type MessageDigest.
  1119. %
  1120. %
  1121. */
  1122. static void UpdateMessageDigest(message_digest,input_message,message_length)
  1123. MessageDigest
  1124. X  *message_digest;
  1125. X
  1126. unsigned char
  1127. X  *input_message;
  1128. X
  1129. unsigned long
  1130. X  message_length;
  1131. {
  1132. X  int
  1133. X    number_bytes;
  1134. X
  1135. X  register unsigned char
  1136. X    *p;
  1137. X
  1138. X  register unsigned int
  1139. X    i;
  1140. X
  1141. X  unsigned long
  1142. X    message[16];
  1143. X
  1144. X  /*
  1145. X    Compute number of bytes mod 64.
  1146. X  */
  1147. X  number_bytes=(int) ((message_digest->number_bits[0] >> 3) & 0x3F);
  1148. X  /*
  1149. X    Update number of bits.
  1150. X  */
  1151. X  if (((message_digest->number_bits[0]+(message_length << 3)) & 0xffffffff) <
  1152. X      message_digest->number_bits[0])
  1153. X    message_digest->number_bits[1]++;
  1154. X  message_digest->number_bits[0]+=message_length << 3;
  1155. X  message_digest->number_bits[1]+=message_length >> 29;
  1156. X  while (message_length--)
  1157. X  {
  1158. X    /*
  1159. X      Add new character to message.
  1160. X    */
  1161. X    message_digest->message[number_bytes++]=(*input_message++);
  1162. X    if (number_bytes == 0x40)
  1163. X      {
  1164. X        /*
  1165. X          Transform message digest 64 bytes at a time.
  1166. X        */
  1167. X        p=message_digest->message;
  1168. X        for (i=0; i < 16; i++)
  1169. X        {
  1170. X          message[i]=(unsigned long) (*p++);
  1171. X          message[i]|=((unsigned long) (*p++)) << 8;
  1172. X          message[i]|=((unsigned long) (*p++)) << 16;
  1173. X          message[i]|=((unsigned long) (*p++)) << 24;
  1174. X        }
  1175. X        TransformMessageDigest(message_digest,message);
  1176. X        number_bytes=0;
  1177. X      }
  1178. X  }
  1179. }
  1180. X
  1181. /*
  1182. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1183. %                                                                             %
  1184. %                                                                             %
  1185. %                                                                             %
  1186. %   C o l o r m a p S i g n a t u r e                                         %
  1187. %                                                                             %
  1188. %                                                                             %
  1189. %                                                                             %
  1190. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1191. %
  1192. %  Fucntion ColormapSignature computes a digital signature from the image
  1193. %  colormap.  This signature uniquely identifies the colormap and is convenient
  1194. %  for determining if the colormap of a sequence of images is identical when
  1195. %  animating.  The digital signature is from RSA Data Security MD5 Digest
  1196. %  Algorithm described in Internet draft [MD5], July 1992.
  1197. %
  1198. %  The format of the ColormapSignature routine is:
  1199. %
  1200. %      ColormapSignature(image)
  1201. %
  1202. %  A description of each parameter follows:
  1203. %
  1204. %    o image: The address of a structure of type Image.
  1205. %
  1206. %
  1207. %
  1208. */
  1209. void ColormapSignature(image)
  1210. Image
  1211. X  *image;
  1212. {
  1213. X  char
  1214. X    *hex;
  1215. X
  1216. X  MessageDigest
  1217. X    message_digest;
  1218. X
  1219. X  register int
  1220. X    i;
  1221. X
  1222. X  register unsigned char
  1223. X    *p;
  1224. X
  1225. X  unsigned char
  1226. X    *colormap;
  1227. X
  1228. X  if (image->class != PseudoClass)
  1229. X    return;
  1230. X  /*
  1231. X    Allocate colormap.
  1232. X  */
  1233. X  colormap=(unsigned char *) malloc(3*image->colors*sizeof(unsigned char));
  1234. X  if (colormap == (unsigned char *) NULL)
  1235. X    {
  1236. X      Warning("unable to compute colormap signature",
  1237. X        "memory allocation failed");
  1238. X      return;
  1239. X    }
  1240. X  p=colormap;
  1241. X  for (i=0; i < image->colors; i++)
  1242. X  {
  1243. X    *p++=image->colormap[i].red;
  1244. X    *p++=image->colormap[i].green;
  1245. X    *p++=image->colormap[i].blue;
  1246. X  }
  1247. X  /*
  1248. X    Compute program colormap signature.
  1249. X  */
  1250. X  InitializeMessageDigest(&message_digest);
  1251. X  UpdateMessageDigest(&message_digest,colormap,
  1252. X    (unsigned long) (image->colors*3));
  1253. X  ComputeMessageDigest(&message_digest);
  1254. X  (void) free((char *) colormap);
  1255. X  /*
  1256. X    Allocate memory for signature.
  1257. X  */
  1258. X  if (image->signature != (char *) NULL)
  1259. X    (void) free((char *) image->signature);
  1260. X  image->signature=(char *) malloc(33*sizeof(char));
  1261. X  if (image->signature == (char *) NULL)
  1262. X    {
  1263. X      Warning("unable to compute colormap signature",
  1264. X        "memory allocation failed");
  1265. X      return;
  1266. X    }
  1267. X  /*
  1268. X    Convert digital signature to a 32 character hex string.
  1269. X  */
  1270. X  p=(unsigned char *) image->signature;
  1271. X  hex="0123456789abcdef";
  1272. X  for (i=0; i < 16; i++)
  1273. X  {
  1274. X    *p++=hex[(message_digest.digest[i] >> 4) & 0xf];
  1275. X    *p++=hex[message_digest.digest[i] & 0xf];
  1276. X  }
  1277. X  *p='\0';
  1278. }
  1279. SHAR_EOF
  1280. chmod 0644 ImageMagick/signature.c ||
  1281. echo 'restore of ImageMagick/signature.c failed'
  1282. Wc_c="`wc -c < 'ImageMagick/signature.c'`"
  1283. test 17852 -eq "$Wc_c" ||
  1284.     echo 'ImageMagick/signature.c: original size 17852, current size' "$Wc_c"
  1285. rm -f _shar_wnt_.tmp
  1286. fi
  1287. # ============= ImageMagick/encode.c ==============
  1288. if test -f 'ImageMagick/encode.c' -a X"$1" != X"-c"; then
  1289.     echo 'x - skipping ImageMagick/encode.c (File already exists)'
  1290.     rm -f _shar_wnt_.tmp
  1291. else
  1292. > _shar_wnt_.tmp
  1293. echo 'x - extracting ImageMagick/encode.c (Text)'
  1294. sed 's/^X//' << 'SHAR_EOF' > 'ImageMagick/encode.c' &&
  1295. /*
  1296. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1297. %                                                                             %
  1298. %                                                                             %
  1299. %                   EEEEE  N   N   CCCC   OOO   DDDD   EEEEE                  %
  1300. %                   E      NN  N  C      O   O  D   D  E                      %
  1301. %                   EEE    N N N  C      O   O  D   D  EEE                    %
  1302. %                   E      N  NN  C      O   O  D   D  E                      %
  1303. %                   EEEEE  N   N   CCCC   OOO   DDDD   EEEEE                  %
  1304. %                                                                             %
  1305. %                                                                             %
  1306. %                    Utility Routines to Write Image Formats                  %
  1307. %                                                                             %
  1308. %                                                                             %
  1309. %                                                                             %
  1310. %                             Software Design                                 %
  1311. %                               John Cristy                                   %
  1312. %                              January 1992                                   %
  1313. %                                                                             %
  1314. %                                                                             %
  1315. %  Copyright 1993 E. I. du Pont de Nemours & Company                          %
  1316. %                                                                             %
  1317. %  Permission to use, copy, modify, distribute, and sell this software and    %
  1318. %  its documentation for any purpose is hereby granted without fee,           %
  1319. %  provided that the above Copyright notice appear in all copies and that     %
  1320. %  both that Copyright notice and this permission notice appear in            %
  1321. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  1322. %  & Company not be used in advertising or publicity pertaining to            %
  1323. %  distribution of the software without specific, written prior               %
  1324. %  permission.  E. I. du Pont de Nemours & Company makes no representations   %
  1325. %  about the suitability of this software for any purpose.  It is provided    %
  1326. %  "as is" without express or implied warranty.                               %
  1327. %                                                                             %
  1328. %  E. I. du Pont de Nemours & Company disclaims all warranties with regard    %
  1329. %  to this software, including all implied warranties of merchantability      %
  1330. %  and fitness, in no event shall E. I. du Pont de Nemours & Company be       %
  1331. %  liable for any special, indirect or consequential damages or any           %
  1332. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  1333. %  in an action of contract, negligence or other tortious action, arising     %
  1334. %  out of or in connection with the use or performance of this software.      %
  1335. %                                                                             %
  1336. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1337. %
  1338. %  Functions in this library convert to and from `alien' image formats to the
  1339. %  MIFF image format.
  1340. %
  1341. %
  1342. */
  1343. X
  1344. /*
  1345. X  Include declarations.
  1346. */
  1347. #include "display.h"
  1348. #include "image.h"
  1349. #include "X.h"
  1350. #include "compress.h"
  1351. #include "utility.h"
  1352. #include "XWDFile.h"
  1353. X
  1354. /*
  1355. X  Forward declarations.
  1356. */
  1357. static unsigned int
  1358. X  WriteMIFFImage _Declare((Image *));
  1359. X
  1360. /*
  1361. X  External declarations.
  1362. */
  1363. extern char
  1364. X  *client_name;
  1365. X
  1366. /*
  1367. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1368. %                                                                             %
  1369. %                                                                             %
  1370. %                                                                             %
  1371. %   W r i t e A L P H A I m a g e                                             %
  1372. %                                                                             %
  1373. %                                                                             %
  1374. %                                                                             %
  1375. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  1376. %
  1377. %  Function WriteALPHAImage writes an mage of alpha bytes to a file.  It
  1378. %  consists of data from the alpha component of the image [0..255].
  1379. %
  1380. %  The format of the WriteALPHAImage routine is:
  1381. %
  1382. %      status=WriteALPHAImage(image)
  1383. %
  1384. %  A description of each parameter follows.
  1385. %
  1386. %    o status: Function WriteALPHAImage return True if the image is written.
  1387. %      False is returned is there is a memory shortage or if the image file
  1388. %      fails to write.
  1389. %
  1390. %    o image:  A pointer to a Image structure.
  1391. %
  1392. %
  1393. */
  1394. static unsigned int WriteALPHAImage(image)
  1395. Image
  1396. X  *image;
  1397. {
  1398. X  register int
  1399. X    i,
  1400. X    j;
  1401. X
  1402. X  register RunlengthPacket
  1403. X    *p;
  1404. X
  1405. X  register unsigned char
  1406. X    *q;
  1407. X
  1408. X  unsigned char
  1409. X    *alpha_pixels;
  1410. X
  1411. X  if (image->class != DirectClass)
  1412. X    {
  1413. X      Warning("image must be of type DirectClass",image->filename);
  1414. SHAR_EOF
  1415. true || echo 'restore of ImageMagick/encode.c failed'
  1416. fi
  1417. echo 'End of ImageMagick part 33'
  1418. echo 'File ImageMagick/encode.c is continued in part 34'
  1419. echo 34 > _shar_seq_.tmp
  1420. exit 0
  1421.  
  1422. exit 0 # Just in case...
  1423. -- 
  1424.   // chris@Sterling.COM           | Send comp.sources.x submissions to:
  1425. \X/  Amiga - The only way to fly! |    sources-x@sterling.com
  1426.  "It's intuitively obvious to the |
  1427.   most casual observer..."        | GCS d+/-- p+ c++ l+ m+ s++/+ g+ w+ t+ r+ x+
  1428.