home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Web / Utilities / wwwcount-2.3 / combine / signature.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-19  |  17.4 KB  |  543 lines
  1. /*
  2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  3. %                                                                             %
  4. %                                                                             %
  5. %        SSSSS  IIIII   GGGG  N   N   AAA   TTTTT  U   U  RRRR   EEEEE        %
  6. %        SS       I    G      NN  N  A   A    T    U   U  R   R  E            %
  7. %         SSS     I    G  GG  N N N  AAAAA    T    U   U  RRRR   EEE          %
  8. %           SS    I    G   G  N  NN  A   A    T    U   U  R R    E            %
  9. %        SSSSS  IIIII   GGG   N   N  A   A    T     UUU   R  R   EEEEE        %
  10. %                                                                             %
  11. %                                                                             %
  12. %               Compute a Digital Signature for a Image Colormap              %
  13. %                                                                             %
  14. %                                                                             %
  15. %                                                                             %
  16. %                           Software Design                                   %
  17. %                             John Cristy                                     %
  18. %                            December 1992                                    %
  19. %                                                                             %
  20. %  Copyright 1994 E. I. du Pont de Nemours and Company                        %
  21. %                                                                             %
  22. %  Permission to use, copy, modify, distribute, and sell this software and    %
  23. %  its documentation for any purpose is hereby granted without fee,           %
  24. %  provided that the above Copyright notice appear in all copies and that     %
  25. %  both that Copyright notice and this permission notice appear in            %
  26. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  27. %  and Company not be used in advertising or publicity pertaining to          %
  28. %  distribution of the software without specific, written prior               %
  29. %  permission.  E. I. du Pont de Nemours and Company makes no representations %
  30. %  about the suitability of this software for any purpose.  It is provided    %
  31. %  "as is" without express or implied warranty.                               %
  32. %                                                                             %
  33. %  E. I. du Pont de Nemours and Company disclaims all warranties with regard  %
  34. %  to this software, including all implied warranties of merchantability      %
  35. %  and fitness, in no event shall E. I. du Pont de Nemours and Company be     %
  36. %  liable for any special, indirect or consequential damages or any           %
  37. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  38. %  in an action of contract, negligence or other tortuous action, arising     %
  39. %  out of or in connection with the use or performance of this software.      %
  40. %                                                                             %
  41. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  42. %
  43. %  Routine ColormapSignature computes a digital signature from the image
  44. %  colormap.  This signature uniquely identifies the colormap and is convenient
  45. %  for determining if the colormap of a sequence of images is identical when
  46. %  animating.  The digital signature is from RSA Data Security MD5 Digest
  47. %  Algorithm described in Internet draft [MD5], July 1992.
  48. %
  49. %
  50. */
  51.  
  52. /*
  53.   Include declarations.
  54. */
  55. #include "combine.h"
  56. #include "defines.h"
  57.  
  58.  
  59. /*
  60.   Typedef declarations.
  61. */
  62. typedef struct _MessageDigest
  63. {
  64.   unsigned long
  65.     number_bits[2],
  66.     accumulator[4];
  67.  
  68.   unsigned char
  69.     message[64],
  70.     digest[16];
  71. } MessageDigest;
  72.  
  73. /*
  74.   Forward declarations.
  75. */
  76. static void
  77.   TransformMessageDigest _FD((MessageDigest *,unsigned long *)),
  78.   UpdateMessageDigest _FD((MessageDigest *,unsigned char *,unsigned long));
  79.  
  80. /*
  81. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  82. %                                                                             %
  83. %                                                                             %
  84. %                                                                             %
  85. %   C o m p u t e M e s s a g e D i g e s t                                   %
  86. %                                                                             %
  87. %                                                                             %
  88. %                                                                             %
  89. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  90. %
  91. %  Function ComputeMessageDigest computes the message digest.
  92. %
  93. %  The format of the ComputeMessageDigest routine is:
  94. %
  95. %      ComputeMessageDigest(message_digest,input_message,message_length)
  96. %
  97. %  A description of each parameter follows:
  98. %
  99. %    o message_digest: The address of a structure of type MessageDigest.
  100. %
  101. %
  102. */
  103. static void ComputeMessageDigest(message_digest)
  104. MessageDigest
  105.   *message_digest;
  106. {
  107.   int
  108.     number_bytes;
  109.  
  110.   register unsigned char
  111.     *p;
  112.  
  113.   register unsigned int
  114.     i;
  115.  
  116.   unsigned char
  117.     padding[64];
  118.  
  119.   unsigned long
  120.     message[16],
  121.     padding_length;
  122.  
  123.   /*
  124.     Save number of bits.
  125.   */
  126.   message[14]=message_digest->number_bits[0];
  127.   message[15]=message_digest->number_bits[1];
  128.   /*
  129.     Compute number of bytes mod 64.
  130.   */
  131.   number_bytes=(int) ((message_digest->number_bits[0] >> 3) & 0x3F);
  132.   /*
  133.     Pad message to 56 mod 64.
  134.   */
  135.   padding_length=(number_bytes < 56) ? (56-number_bytes) : (120-number_bytes);
  136.   padding[0]=0x80;
  137.   for (i=1; i < padding_length; i++)
  138.     padding[i]=(char) 0;
  139.   UpdateMessageDigest(message_digest,padding,padding_length);
  140.   /*
  141.     Append length in bits and transform.
  142.   */
  143.   p=message_digest->message;
  144.   for (i=0; i < 14; i++)
  145.   {
  146.     message[i]=(unsigned long) (*p++);
  147.     message[i]|=((unsigned long) (*p++)) << 8;
  148.     message[i]|=((unsigned long) (*p++)) << 16;
  149.     message[i]|=((unsigned long) (*p++)) << 24;
  150.   }
  151.   TransformMessageDigest(message_digest,message);
  152.   /*
  153.     Store message in digest.
  154.   */
  155.   p=message_digest->digest;
  156.   for (i=0; i < 4; i++)
  157.   {
  158.     *p++=(unsigned char) (message_digest->accumulator[i] & 0xff);
  159.     *p++=(unsigned char) ((message_digest->accumulator[i] >> 8) & 0xff);
  160.     *p++=(unsigned char) ((message_digest->accumulator[i] >> 16) & 0xff);
  161.     *p++=(unsigned char) ((message_digest->accumulator[i] >> 24) & 0xff);
  162.   }
  163. }
  164.  
  165. /*
  166. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  167. %                                                                             %
  168. %                                                                             %
  169. %                                                                             %
  170. %   I n i t i a l i z e M e s s a g e D i g e s t                             %
  171. %                                                                             %
  172. %                                                                             %
  173. %                                                                             %
  174. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  175. %
  176. %  Function InitializeMessageDigest initializes the message digest structure.
  177. %
  178. %  The format of the InitializeMessageDigest routine is:
  179. %
  180. %      InitializeMessageDigest(message_digest)
  181. %
  182. %  A description of each parameter follows:
  183. %
  184. %    o message_digest: The address of a structure of type MessageDigest.
  185. %
  186. %
  187. */
  188. static void InitializeMessageDigest(message_digest)
  189. MessageDigest
  190.   *message_digest;
  191. {
  192.   message_digest->number_bits[0]=(unsigned long) 0;
  193.   message_digest->number_bits[1]=(unsigned long) 0;
  194.   /*
  195.     Load magic initialization constants.
  196.   */
  197.   message_digest->accumulator[0]=(unsigned long) 0x67452301;
  198.   message_digest->accumulator[1]=(unsigned long) 0xefcdab89;
  199.   message_digest->accumulator[2]=(unsigned long) 0x98badcfe;
  200.   message_digest->accumulator[3]=(unsigned long) 0x10325476;
  201. }
  202.  
  203. /*
  204. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  205. %                                                                             %
  206. %                                                                             %
  207. %                                                                             %
  208. %   T r a n s f o r m M e s s a g e D i g e s t                               %
  209. %                                                                             %
  210. %                                                                             %
  211. %                                                                             %
  212. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  213. %
  214. %  Function TransformMessageDigest updates the message digest.
  215. %
  216. %  The format of the TransformMessageDigest routine is:
  217. %
  218. %      TransformMessageDigest(message_digest,message)
  219. %
  220. %  A description of each parameter follows:
  221. %
  222. %    o message_digest: The address of a structure of type MessageDigest.
  223. %
  224. %
  225. */
  226. static void TransformMessageDigest(message_digest,message)
  227. MessageDigest
  228.   *message_digest;
  229.  
  230. unsigned long
  231.   *message;
  232. {
  233. #define F(x,y,z)  (((x) & (y)) | ((~x) & (z)))
  234. #define G(x,y,z)  (((x) & (z)) | ((y) & (~z)))
  235. #define H(x,y,z)  ((x) ^ (y) ^ (z))
  236. #define I(x,y,z)  ((y) ^ ((x) | (~z)))
  237. #define RotateLeft(x,n)  (((x) << (n)) | (((x) & 0xffffffff) >> (32-(n))))
  238.  
  239.   static unsigned long
  240.     additive_constant[64]=  /* 4294967296*abs(sin(i)), i in radians */
  241.     {
  242.       0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf,
  243.       0x4787c62a, 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af,
  244.       0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e,
  245.       0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
  246.       0xd62f105d, 0x2441453,  0xd8a1e681, 0xe7d3fbc8, 0x21e1cde6,
  247.       0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
  248.       0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122,
  249.       0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
  250.       0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,  0xd9d4d039,
  251.       0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, 0xf4292244, 0x432aff97,
  252.       0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d,
  253.       0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
  254.       0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391,
  255.     };
  256.  
  257.   register int
  258.     i;
  259.  
  260.   register unsigned int
  261.     j;
  262.  
  263.   register unsigned long
  264.     a,
  265.     b,
  266.     c,
  267.     d,
  268.     *p;
  269.  
  270.   /*
  271.     Save accumulator.
  272.   */
  273.   a=message_digest->accumulator[0];
  274.   b=message_digest->accumulator[1];
  275.   c=message_digest->accumulator[2];
  276.   d=message_digest->accumulator[3];
  277.   /*
  278.     a=b+((a+F(b,c,d)+X[k]+t) <<< s).
  279.   */
  280.   p=additive_constant;
  281.   j=0;
  282.   for (i=0; i < 4; i++)
  283.   {
  284.     a+=F(b,c,d)+message[j & 0x0f]+(*p++);
  285.     a=RotateLeft(a,7)+b;
  286.     j++;
  287.     d+=F(a,b,c)+message[j & 0x0f]+(*p++);
  288.     d=RotateLeft(d,12)+a;
  289.     j++;
  290.     c+=F(d,a,b)+message[j & 0x0f]+(*p++);
  291.     c=RotateLeft(c,17)+d;
  292.     j++;
  293.     b+=F(c,d,a)+message[j & 0x0f]+(*p++);
  294.     b=RotateLeft(b,22)+c;
  295.     j++;
  296.   }
  297.   /*
  298.     a=b+((a+G(b,c,d)+X[k]+t) <<< s).
  299.   */
  300.   j=1;
  301.   for (i=0; i < 4; i++)
  302.   {
  303.     a+=G(b,c,d)+message[j & 0x0f]+(*p++);
  304.     a=RotateLeft(a,5)+b;
  305.     j+=5;
  306.     d+=G(a,b,c)+message[j & 0x0f]+(*p++);
  307.     d=RotateLeft(d,9)+a;
  308.     j+=5;
  309.     c+=G(d,a,b)+message[j & 0x0f]+(*p++);
  310.     c=RotateLeft(c,14)+d;
  311.     j+=5;
  312.     b+=G(c,d,a)+message[j & 0x0f]+(*p++);
  313.     b=RotateLeft(b,20)+c;
  314.     j+=5;
  315.   }
  316.   /*
  317.     a=b+((a+H(b,c,d)+X[k]+t) <<< s).
  318.   */
  319.   j=5;
  320.   for (i=0; i < 4; i++)
  321.   {
  322.     a+=H(b,c,d)+message[j & 0x0f]+(*p++);
  323.     a=RotateLeft(a,4)+b;
  324.     j+=3;
  325.     d+=H(a,b,c)+message[j & 0x0f]+(*p++);
  326.     d=RotateLeft(d,11)+a;
  327.     j+=3;
  328.     c+=H(d,a,b)+message[j & 0x0f]+(*p++);
  329.     c=RotateLeft(c,16)+d;
  330.     j+=3;
  331.     b+=H(c,d,a)+message[j & 0x0f]+(*p++);
  332.     b=RotateLeft(b,23)+c;
  333.     j+=3;
  334.   }
  335.   /*
  336.     a=b+((a+I(b,c,d)+X[k]+t) <<< s).
  337.   */
  338.   j=0;
  339.   for (i=0; i < 4; i++)
  340.   {
  341.     a+=I(b,c,d)+message[j & 0x0f]+(*p++);
  342.     a=RotateLeft(a,6)+b;
  343.     j+=7;
  344.     d+=I(a,b,c)+message[j & 0x0f]+(*p++);
  345.     d=RotateLeft(d,10)+a;
  346.     j+=7;
  347.     c+=I(d,a,b)+message[j & 0x0f]+(*p++);
  348.     c=RotateLeft(c,15)+d;
  349.     j+=7;
  350.     b+=I(c,d,a)+message[j & 0x0f]+(*p++);
  351.     b=RotateLeft(b,21)+c;
  352.     j+=7;
  353.   }
  354.   /*
  355.     Increment accumulator.
  356.   */
  357.   message_digest->accumulator[0]+=a;
  358.   message_digest->accumulator[1]+=b;
  359.   message_digest->accumulator[2]+=c;
  360.   message_digest->accumulator[3]+=d;
  361. }
  362.  
  363. /*
  364. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  365. %                                                                             %
  366. %                                                                             %
  367. %                                                                             %
  368. %   U p d a t e M e s s a g e D i g e s t                                     %
  369. %                                                                             %
  370. %                                                                             %
  371. %                                                                             %
  372. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  373. %
  374. %  Function UpdateMessageDigest updates the message digest.
  375. %
  376. %  The format of the UpdateMessageDigest routine is:
  377. %
  378. %      UpdateMessageDigest(message_digest,input_message,message_length)
  379. %
  380. %  A description of each parameter follows:
  381. %
  382. %    o message_digest: The address of a structure of type MessageDigest.
  383. %
  384. %
  385. */
  386. static void UpdateMessageDigest(message_digest,input_message,message_length)
  387. MessageDigest
  388.   *message_digest;
  389.  
  390. unsigned char
  391.   *input_message;
  392.  
  393. unsigned long
  394.   message_length;
  395. {
  396.   int
  397.     number_bytes;
  398.  
  399.   register unsigned char
  400.     *p;
  401.  
  402.   register unsigned int
  403.     i;
  404.  
  405.   unsigned long
  406.     message[16];
  407.  
  408.   /*
  409.     Compute number of bytes mod 64.
  410.   */
  411.   number_bytes=(int) ((message_digest->number_bits[0] >> 3) & 0x3F);
  412.   /*
  413.     Update number of bits.
  414.   */
  415.   if (((message_digest->number_bits[0]+(message_length << 3)) & 0xffffffff) <
  416.       message_digest->number_bits[0])
  417.     message_digest->number_bits[1]++;
  418.   message_digest->number_bits[0]+=message_length << 3;
  419.   message_digest->number_bits[1]+=message_length >> 29;
  420.   while (message_length--)
  421.   {
  422.     /*
  423.       Add new character to message.
  424.     */
  425.     message_digest->message[number_bytes++]=(*input_message++);
  426.     if (number_bytes == 0x40)
  427.       {
  428.         /*
  429.           Transform message digest 64 bytes at a time.
  430.         */
  431.         p=message_digest->message;
  432.         for (i=0; i < 16; i++)
  433.         {
  434.           message[i]=(unsigned long) (*p++);
  435.           message[i]|=((unsigned long) (*p++)) << 8;
  436.           message[i]|=((unsigned long) (*p++)) << 16;
  437.           message[i]|=((unsigned long) (*p++)) << 24;
  438.         }
  439.         TransformMessageDigest(message_digest,message);
  440.         number_bytes=0;
  441.       }
  442.   }
  443. }
  444.  
  445. /*
  446. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  447. %                                                                             %
  448. %                                                                             %
  449. %                                                                             %
  450. %   C o l o r m a p S i g n a t u r e                                         %
  451. %                                                                             %
  452. %                                                                             %
  453. %                                                                             %
  454. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  455. %
  456. %  Fucntion ColormapSignature computes a digital signature from the image
  457. %  colormap.  This signature uniquely identifies the colormap and is convenient
  458. %  for determining if the colormap of a sequence of images is identical when
  459. %  animating.  The digital signature is from RSA Data Security MD5 Digest
  460. %  Algorithm described in Internet draft [MD5], July 1992.
  461. %
  462. %  The format of the ColormapSignature routine is:
  463. %
  464. %      ColormapSignature(image)
  465. %
  466. %  A description of each parameter follows:
  467. %
  468. %    o image: The address of a structure of type Image.
  469. %
  470. %
  471. %
  472. */
  473. void ColormapSignature(image)
  474. Image
  475.   *image;
  476. {
  477.   char
  478.     *hex;
  479.  
  480.   MessageDigest
  481.     message_digest;
  482.  
  483.   register int
  484.     i;
  485.  
  486.   register unsigned char
  487.     *p;
  488.  
  489.   unsigned char
  490.     *colormap;
  491.  
  492.   if (image->class != PseudoClass)
  493.     return;
  494.   /*
  495.     Allocate colormap.
  496.   */
  497.   colormap=(unsigned char *) malloc(3*image->colors*sizeof(unsigned char));
  498.   if (colormap == (unsigned char *) NULL)
  499.     {
  500.       (void) fprintf (stderr,
  501.       "Unable to compute colormap signature, Memory allocation failed\n");
  502.       return;
  503.     }
  504.   p=colormap;
  505.   for (i=0; i < image->colors; i++)
  506.   {
  507.     *p++=image->colormap[i].red;
  508.     *p++=image->colormap[i].green;
  509.     *p++=image->colormap[i].blue;
  510.   }
  511.   /*
  512.     Compute program colormap signature.
  513.   */
  514.   InitializeMessageDigest(&message_digest);
  515.   UpdateMessageDigest(&message_digest,colormap,
  516.     (unsigned long) (image->colors*3));
  517.   ComputeMessageDigest(&message_digest);
  518.   (void) free((char *) colormap);
  519.   /*
  520.     Allocate memory for signature.
  521.   */
  522.   if (image->signature != (char *) NULL)
  523.     (void) free((char *) image->signature);
  524.   image->signature=(char *) malloc(33*sizeof(char));
  525.   if (image->signature == (char *) NULL)
  526.     {
  527.       (void) fprintf (stderr,
  528.       "Unable to compute colormap signature, Memory allocation failed\n");
  529.       return;
  530.     }
  531.   /*
  532.     Convert digital signature to a 32 character hex string.
  533.   */
  534.   p=(unsigned char *) image->signature;
  535.   hex="0123456789abcdef";
  536.   for (i=0; i < 16; i++)
  537.   {
  538.     *p++=hex[(message_digest.digest[i] >> 4) & 0xf];
  539.     *p++=hex[message_digest.digest[i] & 0xf];
  540.   }
  541.   *p='\0';
  542. }
  543.