dbus/dbus-sha.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-sha.c SHA-1 implementation
   3  *
   4  * Copyright (C) 2003 Red Hat Inc.
   5  * Copyright (C) 1995 A. M. Kuchling
   6  *
   7  * Licensed under the Academic Free License version 2.1
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  *
  23  */
  24
  25 #include "dbus-internals.h"
  26 #include "dbus-sha.h"
  27 #include "dbus-marshal-basic.h" /* for byteswap routines */
  28 #include <string.h>
  29
  30 /* The following comments have the history of where this code
  31  * comes from. I actually copied it from GNet in GNOME CVS.
  32  * - hp@redhat.com
  33  */
  34
  35 /*
  36  *  sha.h : Implementation of the Secure Hash Algorithm
  37  *
  38  * Part of the Python Cryptography Toolkit, version 1.0.0
  39  *
  40  * Copyright (C) 1995, A.M. Kuchling
  41  *
  42  * Distribute and use freely; there are no restrictions on further
  43  * dissemination and usage except those imposed by the laws of your
  44  * country of residence.
  45  *
  46  */
  47
  48 /* SHA: NIST's Secure Hash Algorithm */
  49
  50 /* Based on SHA code originally posted to sci.crypt by Peter Gutmann
  51    in message <30ajo5$oe8@ccu2.auckland.ac.nz>.
  52    Modified to test for endianness on creation of SHA objects by AMK.
  53    Also, the original specification of SHA was found to have a weakness
  54    by NSA/NIST.  This code implements the fixed version of SHA.
  55 */
  56
  57 /* Here's the first paragraph of Peter Gutmann's posting:
  58
  59 The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
  60 SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
  61 what's changed in the new version.  The fix is a simple change which involves
  62 adding a single rotate in the initial expansion function.  It is unknown
  63 whether this is an optimal solution to the problem which was discovered in the
  64 SHA or whether it's simply a bandaid which fixes the problem with a minimum of
  65 effort (for example the reengineering of a great many Capstone chips).
  66 */
  67
  68 /**
  69  * @defgroup DBusSHA SHA implementation
  70  * @ingroup  DBusInternals
  71  * @brief SHA-1 hash
  72  *
  73  * Types and functions related to computing SHA-1 hash.
  74  */
  75
  76 /**
  77  * @defgroup DBusSHAInternals SHA implementation details
  78  * @ingroup  DBusInternals
  79  * @brief Internals of SHA implementation.
  80  *
  81  * The implementation of SHA-1 (see http://www.itl.nist.gov/fipspubs/fip180-1.htm).
  82  * This SHA implementation was written by A.M. Kuchling
  83  *
  84  * @{
  85  */
  86
  87 #ifndef DOXYGEN_SHOULD_SKIP_THIS
  88
  89 /* The SHA block size and message digest sizes, in bytes */
  90
  91 #define SHA_DATASIZE    64
  92 #define SHA_DIGESTSIZE  20
  93
  94 /* The SHA f()-functions.  The f1 and f3 functions can be optimized to
  95    save one boolean operation each - thanks to Rich Schroeppel,
  96    rcs@cs.arizona.edu for discovering this */
  97
  98 /*#define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )          // Rounds  0-19 */
  99 #define f1(x,y,z)  ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
 100 #define f2(x,y,z)  ( x ^ y ^ z )                       /* Rounds 20-39 */
 101 /*#define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) )   // Rounds 40-59 */
 102 #define f3(x,y,z)  ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
 103 #define f4(x,y,z)  ( x ^ y ^ z )                       /* Rounds 60-79 */
 104
 105 /* The SHA Mysterious Constants */
 106
 107 #define K1  0x5A827999L                                 /* Rounds  0-19 */
 108 #define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
 109 #define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
 110 #define K4  0xCA62C1D6L                                 /* Rounds 60-79 */
 111
 112 /* SHA initial values */
 113
 114 #define h0init  0x67452301L
 115 #define h1init  0xEFCDAB89L
 116 #define h2init  0x98BADCFEL
 117 #define h3init  0x10325476L
 118 #define h4init  0xC3D2E1F0L
 119
 120 /* Note that it may be necessary to add parentheses to these macros if they
 121    are to be called with expressions as arguments */
 122 /* 32-bit rotate left - kludged with shifts */
 123
 124 #define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
 125
 126 /* The initial expanding function.  The hash function is defined over an
 127    80-word expanded input array W, where the first 16 are copies of the input
 128    data, and the remaining 64 are defined by
 129
 130         W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
 131
 132    This implementation generates these values on the fly in a circular
 133    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
 134    optimization.
 135
 136    The updated SHA changes the expanding function by adding a rotate of 1
 137    bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
 138    for this information */
 139
 140 #define expand(W,i) ( W[ i & 15 ] = ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
 141                                                  W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
 142
 143
 144 /* The prototype SHA sub-round.  The fundamental sub-round is:
 145
 146         a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
 147         b' = a;
 148         c' = ROTL( 30, b );
 149         d' = c;
 150         e' = d;
 151
 152    but this is implemented by unrolling the loop 5 times and renaming the
 153    variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
 154    This code is then replicated 20 times for each of the 4 functions, using
 155    the next 20 values from the W[] array each time */
 156
 157 #define subRound(a, b, c, d, e, f, k, data) \
 158    ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
 159
 160 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
 161
 162 /* Perform the SHA transformation.  Note that this code, like MD5, seems to
 163    break some optimizing compilers due to the complexity of the expressions
 164    and the size of the basic block.  It may be necessary to split it into
 165    sections, e.g. based on the four subrounds
 166
 167    Note that this corrupts the context->data area */
 168
 169 static void
 170 SHATransform(dbus_uint32_t *digest, dbus_uint32_t *data)
 171 {
 172   dbus_uint32_t A, B, C, D, E;     /* Local vars */
 173   dbus_uint32_t eData[16];       /* Expanded data */
 174
 175   /* Set up first buffer and local data buffer */
 176   A = digest[0];
 177   B = digest[1];
 178   C = digest[2];
 179   D = digest[3];
 180   E = digest[4];
 181   memmove (eData, data, SHA_DATASIZE);
 182
 183   /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
 184   subRound (A, B, C, D, E, f1, K1, eData[0]);
 185   subRound (E, A, B, C, D, f1, K1, eData[1]);
 186   subRound (D, E, A, B, C, f1, K1, eData[2]);
 187   subRound (C, D, E, A, B, f1, K1, eData[3]);
 188   subRound (B, C, D, E, A, f1, K1, eData[4]);
 189   subRound (A, B, C, D, E, f1, K1, eData[5]);
 190   subRound (E, A, B, C, D, f1, K1, eData[6]);
 191   subRound (D, E, A, B, C, f1, K1, eData[7]);
 192   subRound (C, D, E, A, B, f1, K1, eData[8]);
 193   subRound (B, C, D, E, A, f1, K1, eData[9]);
 194   subRound (A, B, C, D, E, f1, K1, eData[10]);
 195   subRound (E, A, B, C, D, f1, K1, eData[11]);
 196   subRound (D, E, A, B, C, f1, K1, eData[12]);
 197   subRound (C, D, E, A, B, f1, K1, eData[13]);
 198   subRound (B, C, D, E, A, f1, K1, eData[14]);
 199   subRound (A, B, C, D, E, f1, K1, eData[15]);
 200   subRound (E, A, B, C, D, f1, K1, expand ( eData, 16) );
 201   subRound (D, E, A, B, C, f1, K1, expand ( eData, 17) );
 202   subRound (C, D, E, A, B, f1, K1, expand ( eData, 18) );
 203   subRound (B, C, D, E, A, f1, K1, expand ( eData, 19) );
 204
 205   subRound (A, B, C, D, E, f2, K2, expand ( eData, 20) );
 206   subRound (E, A, B, C, D, f2, K2, expand ( eData, 21) );
 207   subRound (D, E, A, B, C, f2, K2, expand ( eData, 22) );
 208   subRound (C, D, E, A, B, f2, K2, expand ( eData, 23) );
 209   subRound (B, C, D, E, A, f2, K2, expand ( eData, 24) );
 210   subRound (A, B, C, D, E, f2, K2, expand ( eData, 25) );
 211   subRound (E, A, B, C, D, f2, K2, expand ( eData, 26) );
 212   subRound (D, E, A, B, C, f2, K2, expand ( eData, 27) );
 213   subRound (C, D, E, A, B, f2, K2, expand ( eData, 28) );
 214   subRound (B, C, D, E, A, f2, K2, expand ( eData, 29) );
 215   subRound (A, B, C, D, E, f2, K2, expand ( eData, 30) );
 216   subRound (E, A, B, C, D, f2, K2, expand ( eData, 31) );
 217   subRound (D, E, A, B, C, f2, K2, expand ( eData, 32) );
 218   subRound (C, D, E, A, B, f2, K2, expand ( eData, 33) );
 219   subRound (B, C, D, E, A, f2, K2, expand ( eData, 34) );
 220   subRound (A, B, C, D, E, f2, K2, expand ( eData, 35) );
 221   subRound (E, A, B, C, D, f2, K2, expand ( eData, 36) );
 222   subRound (D, E, A, B, C, f2, K2, expand ( eData, 37) );
 223   subRound (C, D, E, A, B, f2, K2, expand ( eData, 38) );
 224   subRound (B, C, D, E, A, f2, K2, expand ( eData, 39) );
 225
 226   subRound (A, B, C, D, E, f3, K3, expand ( eData, 40) );
 227   subRound (E, A, B, C, D, f3, K3, expand ( eData, 41) );
 228   subRound (D, E, A, B, C, f3, K3, expand ( eData, 42) );
 229   subRound (C, D, E, A, B, f3, K3, expand ( eData, 43) );
 230   subRound (B, C, D, E, A, f3, K3, expand ( eData, 44) );
 231   subRound (A, B, C, D, E, f3, K3, expand ( eData, 45) );
 232   subRound (E, A, B, C, D, f3, K3, expand ( eData, 46) );
 233   subRound (D, E, A, B, C, f3, K3, expand ( eData, 47) );
 234   subRound (C, D, E, A, B, f3, K3, expand ( eData, 48) );
 235   subRound (B, C, D, E, A, f3, K3, expand ( eData, 49) );
 236   subRound (A, B, C, D, E, f3, K3, expand ( eData, 50) );
 237   subRound (E, A, B, C, D, f3, K3, expand ( eData, 51) );
 238   subRound (D, E, A, B, C, f3, K3, expand ( eData, 52) );
 239   subRound (C, D, E, A, B, f3, K3, expand ( eData, 53) );
 240   subRound (B, C, D, E, A, f3, K3, expand ( eData, 54) );
 241   subRound (A, B, C, D, E, f3, K3, expand ( eData, 55) );
 242   subRound (E, A, B, C, D, f3, K3, expand ( eData, 56) );
 243   subRound (D, E, A, B, C, f3, K3, expand ( eData, 57) );
 244   subRound (C, D, E, A, B, f3, K3, expand ( eData, 58) );
 245   subRound (B, C, D, E, A, f3, K3, expand ( eData, 59) );
 246
 247   subRound (A, B, C, D, E, f4, K4, expand ( eData, 60) );
 248   subRound (E, A, B, C, D, f4, K4, expand ( eData, 61) );
 249   subRound (D, E, A, B, C, f4, K4, expand ( eData, 62) );
 250   subRound (C, D, E, A, B, f4, K4, expand ( eData, 63) );
 251   subRound (B, C, D, E, A, f4, K4, expand ( eData, 64) );
 252   subRound (A, B, C, D, E, f4, K4, expand ( eData, 65) );
 253   subRound (E, A, B, C, D, f4, K4, expand ( eData, 66) );
 254   subRound (D, E, A, B, C, f4, K4, expand ( eData, 67) );
 255   subRound (C, D, E, A, B, f4, K4, expand ( eData, 68) );
 256   subRound (B, C, D, E, A, f4, K4, expand ( eData, 69) );
 257   subRound (A, B, C, D, E, f4, K4, expand ( eData, 70) );
 258   subRound (E, A, B, C, D, f4, K4, expand ( eData, 71) );
 259   subRound (D, E, A, B, C, f4, K4, expand ( eData, 72) );
 260   subRound (C, D, E, A, B, f4, K4, expand ( eData, 73) );
 261   subRound (B, C, D, E, A, f4, K4, expand ( eData, 74) );
 262   subRound (A, B, C, D, E, f4, K4, expand ( eData, 75) );
 263   subRound (E, A, B, C, D, f4, K4, expand ( eData, 76) );
 264   subRound (D, E, A, B, C, f4, K4, expand ( eData, 77) );
 265   subRound (C, D, E, A, B, f4, K4, expand ( eData, 78) );
 266   subRound (B, C, D, E, A, f4, K4, expand ( eData, 79) );
 267
 268   /* Build message digest */
 269   digest[0] += A;
 270   digest[1] += B;
 271   digest[2] += C;
 272   digest[3] += D;
 273   digest[4] += E;
 274 }
 275
 276 /* When run on a little-endian CPU we need to perform byte reversal on an
 277    array of longwords. */
 278
 279 #ifdef WORDS_BIGENDIAN
 280 #define swap_words(buffer, byte_count)
 281 #else
 282 static void
 283 swap_words (dbus_uint32_t *buffer,
 284             int            byte_count)
 285 {
 286   byte_count /= sizeof (dbus_uint32_t);
 287   while (byte_count--)
 288     {
 289       *buffer = DBUS_UINT32_SWAP_LE_BE (*buffer);
 290       ++buffer;
 291     }
 292 }
 293 #endif
 294
 295 static void
 296 sha_init (DBusSHAContext *context)
 297 {
 298   /* Set the h-vars to their initial values */
 299   context->digest[0] = h0init;
 300   context->digest[1] = h1init;
 301   context->digest[2] = h2init;
 302   context->digest[3] = h3init;
 303   context->digest[4] = h4init;
 304
 305   /* Initialise bit count */
 306   context->count_lo = context->count_hi = 0;
 307 }
 308
 309 static void
 310 sha_append (DBusSHAContext      *context,
 311             const unsigned char *buffer,
 312             unsigned int         count)
 313 {
 314   dbus_uint32_t tmp;
 315   unsigned int dataCount;
 316
 317   /* Update bitcount */
 318   tmp = context->count_lo;
 319   if (( context->count_lo = tmp + ( ( dbus_uint32_t) count << 3) ) < tmp)
 320     context->count_hi++;             /* Carry from low to high */
 321   context->count_hi += count >> 29;
 322
 323   /* Get count of bytes already in data */
 324   dataCount = (int) (tmp >> 3) & 0x3F;
 325
 326   /* Handle any leading odd-sized chunks */
 327   if (dataCount)
 328     {
 329       unsigned char *p = (unsigned char *) context->data + dataCount;
 330
 331       dataCount = SHA_DATASIZE - dataCount;
 332       if (count < dataCount)
 333         {
 334           memmove (p, buffer, count);
 335           return;
 336         }
 337       memmove (p, buffer, dataCount);
 338       swap_words (context->data, SHA_DATASIZE);
 339       SHATransform (context->digest, context->data);
 340       buffer += dataCount;
 341       count -= dataCount;
 342     }
 343
 344   /* Process data in SHA_DATASIZE chunks */
 345   while (count >= SHA_DATASIZE)
 346     {
 347       memmove (context->data, buffer, SHA_DATASIZE);
 348       swap_words (context->data, SHA_DATASIZE);
 349       SHATransform (context->digest, context->data);
 350       buffer += SHA_DATASIZE;
 351       count -= SHA_DATASIZE;
 352     }
 353
 354   /* Handle any remaining bytes of data. */
 355   memmove (context->data, buffer, count);
 356 }
 357
 358
 359 /* Final wrapup - pad to SHA_DATASIZE-byte boundary with the bit pattern
 360    1 0* (64-bit count of bits processed, MSB-first) */
 361
 362 static void
 363 sha_finish (DBusSHAContext *context, unsigned char digest[20])
 364 {
 365   int count;
 366   unsigned char *data_p;
 367
 368   /* Compute number of bytes mod 64 */
 369   count = (int) context->count_lo;
 370   count = (count >> 3) & 0x3F;
 371
 372   /* Set the first char of padding to 0x80.  This is safe since there is
 373      always at least one byte free */
 374   data_p = (unsigned char *) context->data + count;
 375   *data_p++ = 0x80;
 376
 377   /* Bytes of padding needed to make 64 bytes */
 378   count = SHA_DATASIZE - 1 - count;
 379
 380   /* Pad out to 56 mod 64 */
 381   if (count < 8)
 382     {
 383       /* Two lots of padding:  Pad the first block to 64 bytes */
 384       memset (data_p, 0, count);
 385       swap_words (context->data, SHA_DATASIZE);
 386       SHATransform (context->digest, context->data);
 387
 388       /* Now fill the next block with 56 bytes */
 389       memset (context->data, 0, SHA_DATASIZE - 8);
 390     }
 391   else
 392     /* Pad block to 56 bytes */
 393     memset (data_p, 0, count - 8);
 394
 395   /* Append length in bits and transform */
 396   context->data[14] = context->count_hi;
 397   context->data[15] = context->count_lo;
 398
 399   swap_words (context->data, SHA_DATASIZE - 8);
 400   SHATransform (context->digest, context->data);
 401   swap_words (context->digest, SHA_DIGESTSIZE);
 402   memmove (digest, context->digest, SHA_DIGESTSIZE);
 403 }
 404
 405 /** @} */ /* End of internals */
 406
 407 /**
 408  * @addtogroup DBusSHA
 409  *
 410  * @{
 411  */
 412
 413 /**
 414  * Initializes the SHA context.
 415  *
 416  * @param context an uninitialized context, typically on the stack.
 417  */
 418 void
 419 _dbus_sha_init (DBusSHAContext *context)
 420 {
 421   sha_init (context);
 422 }
 423
 424 /**
 425  * Feeds more data into an existing shasum computation.
 426  *
 427  * @param context the SHA context
 428  * @param data the additional data to hash
 429  */
 430 void
 431 _dbus_sha_update (DBusSHAContext   *context,
 432                   const DBusString *data)
 433 {
 434   unsigned int inputLen;
 435   const unsigned char *input;
 436
 437   input = (const unsigned char*) _dbus_string_get_const_data (data);
 438   inputLen = _dbus_string_get_length (data);
 439
 440   sha_append (context, input, inputLen);
 441 }
 442
 443 /**
 444  * SHA finalization. Ends an SHA message-digest operation, writing the
 445  * the message digest and zeroing the context.  The results are
 446  * returned as a raw 20-byte digest, not as the ascii-hex-digits
 447  * string form of the digest.
 448  *
 449  * @param context the SHA context
 450  * @param results string to append the 20-byte SHA digest to
 451  * @returns #FALSE if not enough memory to append the digest
 452  *
 453  */
 454 dbus_bool_t
 455 _dbus_sha_final (DBusSHAContext   *context,
 456                  DBusString       *results)
 457 {
 458   unsigned char digest[20];
 459
 460   sha_finish (context, digest);
 461
 462   if (!_dbus_string_append_len (results, digest, 20))
 463     return FALSE;
 464
 465   /* some kind of security paranoia, though it seems pointless
 466    * to me given the nonzeroed stuff flying around
 467    */
 468   memset ((void*)context, '\0', sizeof (DBusSHAContext));
 469
 470   return TRUE;
 471 }
 472
 473 /**
 474  * Computes the ASCII hex-encoded shasum of the given data and
 475  * appends it to the output string.
 476  *
 477  * @param data input data to be hashed
 478  * @param ascii_output string to append ASCII shasum to
 479  * @returns #FALSE if not enough memory
 480  */
 481 dbus_bool_t
 482 _dbus_sha_compute (const DBusString *data,
 483                    DBusString       *ascii_output)
 484 {
 485   DBusSHAContext context;
 486   DBusString digest;
 487
 488   _dbus_sha_init (&context);
 489
 490   _dbus_sha_update (&context, data);
 491
 492   if (!_dbus_string_init (&digest))
 493     return FALSE;
 494
 495   if (!_dbus_sha_final (&context, &digest))
 496     goto error;
 497
 498   if (!_dbus_string_hex_encode (&digest, 0, ascii_output,
 499                                 _dbus_string_get_length (ascii_output)))
 500     goto error;
 501
 502   _dbus_string_free (&digest);
 503
 504   return TRUE;
 505
 506  error:
 507   _dbus_string_free (&digest);
 508   return FALSE;
 509 }
 510
 511 /** @} */ /* end of exported functions */
 512
 513 #ifdef DBUS_BUILD_TESTS
 514 #include "dbus-test.h"
 515 #include <stdio.h>
 516
 517 static dbus_bool_t
 518 check_sha_binary (const unsigned char *input,
 519                   int                  input_len,
 520                   const char          *expected)
 521 {
 522   DBusString input_str;
 523   DBusString expected_str;
 524   DBusString results;
 525
 526   _dbus_string_init_const_len (&input_str, input, input_len);
 527   _dbus_string_init_const (&expected_str, expected);
 528
 529   if (!_dbus_string_init (&results))
 530     _dbus_assert_not_reached ("no memory for SHA-1 results");
 531
 532   if (!_dbus_sha_compute (&input_str, &results))
 533     _dbus_assert_not_reached ("no memory for SHA-1 results");
 534
 535   if (!_dbus_string_equal (&expected_str, &results))
 536     {
 537       _dbus_warn ("Expected hash %s got %s for SHA-1 sum\n",
 538                   expected,
 539                   _dbus_string_get_const_data (&results));
 540       _dbus_string_free (&results);
 541       return FALSE;
 542     }
 543
 544   _dbus_string_free (&results);
 545   return TRUE;
 546 }
 547
 548 static dbus_bool_t
 549 check_sha_str (const char *input,
 550                const char *expected)
 551 {
 552   return check_sha_binary (input, strlen (input), expected);
 553 }
 554
 555 static dbus_bool_t
 556 decode_compact_string (const DBusString *line,
 557                        DBusString       *decoded)
 558 {
 559   int n_bits;
 560   dbus_bool_t current_b;
 561   int offset;
 562   int next;
 563   long val;
 564   int length_bytes;
 565
 566   offset = 0;
 567   next = 0;
 568
 569   if (!_dbus_string_parse_int (line, offset, &val, &next))
 570     {
 571       fprintf (stderr, "could not parse length at start of compact string: %s\n",
 572                _dbus_string_get_const_data (line));
 573       return FALSE;
 574     }
 575
 576   _dbus_string_skip_blank (line, next, &next);
 577
 578   offset = next;
 579   if (!_dbus_string_parse_int (line, offset, &val, &next))
 580     {
 581       fprintf (stderr, "could not parse start bit 'b' in compact string: %s\n",
 582                _dbus_string_get_const_data (line));
 583       return FALSE;
 584     }
 585
 586   if (!(val == 0 || val == 1))
 587     {
 588       fprintf (stderr, "the value 'b' must be 0 or 1, see sha-1/Readme.txt\n");
 589       return FALSE;
 590     }
 591
 592   _dbus_string_skip_blank (line, next, &next);
 593
 594   current_b = val;
 595   n_bits = 0;
 596
 597   while (next < _dbus_string_get_length (line))
 598     {
 599       int total_bits;
 600
 601       offset = next;
 602
 603       if (_dbus_string_get_byte (line, offset) == '^')
 604         break;
 605
 606       if (!_dbus_string_parse_int (line, offset, &val, &next))
 607         {
 608           fprintf (stderr, "could not parse bit count in compact string\n");
 609           return FALSE;
 610         }
 611
 612       /* We now append "val" copies of "current_b" bits to the string */
 613       total_bits = n_bits + val;
 614       while (n_bits < total_bits)
 615         {
 616           int byte_containing_next_bit = n_bits / 8;
 617           int bit_containing_next_bit = 7 - (n_bits % 8);
 618           unsigned char old_byte;
 619
 620           if (byte_containing_next_bit >= _dbus_string_get_length (decoded))
 621             {
 622               if (!_dbus_string_set_length (decoded, byte_containing_next_bit + 1))
 623                 _dbus_assert_not_reached ("no memory to extend to next byte");
 624             }
 625
 626           old_byte = _dbus_string_get_byte (decoded, byte_containing_next_bit);
 627           old_byte |= current_b << bit_containing_next_bit;
 628
 629 #if 0
 630           printf ("Appending bit %d to byte %d at bit %d resulting in byte 0x%x\n",
 631                   current_b, byte_containing_next_bit,
 632                   bit_containing_next_bit, old_byte);
 633 #endif
 634
 635           _dbus_string_set_byte (decoded, byte_containing_next_bit, old_byte);
 636
 637           ++n_bits;
 638         }
 639
 640       _dbus_string_skip_blank (line, next, &next);
 641
 642       current_b = !current_b;
 643     }
 644
 645   length_bytes = (n_bits / 8 + ((n_bits % 8) ? 1 : 0));
 646
 647   if (_dbus_string_get_length (decoded) != length_bytes)
 648     {
 649       fprintf (stderr, "Expected length %d bytes %d bits for compact string, got %d bytes\n",
 650                length_bytes, n_bits, _dbus_string_get_length (decoded));
 651       return FALSE;
 652     }
 653   else
 654     return TRUE;
 655 }
 656
 657 static dbus_bool_t
 658 get_next_expected_result (DBusString *results,
 659                           DBusString *result)
 660 {
 661   DBusString line;
 662   dbus_bool_t retval;
 663
 664   retval = FALSE;
 665
 666   if (!_dbus_string_init (&line))
 667     _dbus_assert_not_reached ("no memory");
 668
 669  next_iteration:
 670   while (_dbus_string_pop_line (results, &line))
 671     {
 672       _dbus_string_delete_leading_blanks (&line);
 673
 674       if (_dbus_string_get_length (&line) == 0)
 675         goto next_iteration;
 676       else if (_dbus_string_starts_with_c_str (&line, "#"))
 677         goto next_iteration;
 678       else if (_dbus_string_starts_with_c_str (&line, "H>"))
 679         {
 680           /* don't print */
 681         }
 682       else if (_dbus_string_starts_with_c_str (&line, "D>") ||
 683                _dbus_string_starts_with_c_str (&line, "<D"))
 684         goto next_iteration;
 685       else
 686         {
 687           int i;
 688
 689           if (!_dbus_string_move (&line, 0, result, 0))
 690             _dbus_assert_not_reached ("no memory");
 691
 692           i = 0;
 693           while (i < _dbus_string_get_length (result))
 694             {
 695               switch (_dbus_string_get_byte (result, i))
 696                 {
 697                 case 'A':
 698                   _dbus_string_set_byte (result, i, 'a');
 699                   break;
 700                 case 'B':
 701                   _dbus_string_set_byte (result, i, 'b');
 702                   break;
 703                 case 'C':
 704                   _dbus_string_set_byte (result, i, 'c');
 705                   break;
 706                 case 'D':
 707                   _dbus_string_set_byte (result, i, 'd');
 708                   break;
 709                 case 'E':
 710                   _dbus_string_set_byte (result, i, 'e');
 711                   break;
 712                 case 'F':
 713                   _dbus_string_set_byte (result, i, 'f');
 714                   break;
 715                 case '^':
 716                 case ' ':
 717                   _dbus_string_delete (result, i, 1);
 718                   --i; /* to offset ++i below */
 719                   break;
 720                 }
 721
 722               ++i;
 723             }
 724
 725           break;
 726         }
 727     }
 728
 729   retval = TRUE;
 730
 731   /* out: */
 732   _dbus_string_free (&line);
 733   return retval;
 734 }
 735
 736 static dbus_bool_t
 737 process_test_data (const char *test_data_dir)
 738 {
 739   DBusString tests_file;
 740   DBusString results_file;
 741   DBusString tests;
 742   DBusString results;
 743   DBusString line;
 744   DBusString tmp;
 745   int line_no;
 746   dbus_bool_t retval;
 747   int success_count;
 748   DBusError error;
 749
 750   retval = FALSE;
 751
 752   if (!_dbus_string_init (&tests_file))
 753     _dbus_assert_not_reached ("no memory");
 754
 755   if (!_dbus_string_init (&results_file))
 756     _dbus_assert_not_reached ("no memory");
 757
 758   if (!_dbus_string_init (&tests))
 759     _dbus_assert_not_reached ("no memory");
 760
 761   if (!_dbus_string_init (&results))
 762     _dbus_assert_not_reached ("no memory");
 763
 764   if (!_dbus_string_init (&line))
 765     _dbus_assert_not_reached ("no memory");
 766
 767   if (!_dbus_string_append (&tests_file, test_data_dir))
 768     _dbus_assert_not_reached ("no memory");
 769
 770   if (!_dbus_string_append (&results_file, test_data_dir))
 771     _dbus_assert_not_reached ("no memory");
 772
 773   _dbus_string_init_const (&tmp, "sha-1/byte-messages.sha1");
 774   if (!_dbus_concat_dir_and_file (&tests_file, &tmp))
 775     _dbus_assert_not_reached ("no memory");
 776
 777   _dbus_string_init_const (&tmp, "sha-1/byte-hashes.sha1");
 778   if (!_dbus_concat_dir_and_file (&results_file, &tmp))
 779     _dbus_assert_not_reached ("no memory");
 780
 781   dbus_error_init (&error);
 782   if (!_dbus_file_get_contents (&tests, &tests_file, &error))
 783     {
 784       fprintf (stderr, "could not load test data file %s: %s\n",
 785                _dbus_string_get_const_data (&tests_file),
 786                error.message);
 787       dbus_error_free (&error);
 788       goto out;
 789     }
 790
 791   if (!_dbus_file_get_contents (&results, &results_file, &error))
 792     {
 793       fprintf (stderr, "could not load results data file %s: %s\n",
 794                _dbus_string_get_const_data (&results_file), error.message);
 795       dbus_error_free (&error);
 796       goto out;
 797     }
 798
 799   success_count = 0;
 800   line_no = 0;
 801  next_iteration:
 802   while (_dbus_string_pop_line (&tests, &line))
 803     {
 804       line_no += 1;
 805
 806       _dbus_string_delete_leading_blanks (&line);
 807
 808       if (_dbus_string_get_length (&line) == 0)
 809         goto next_iteration;
 810       else if (_dbus_string_starts_with_c_str (&line, "#"))
 811         goto next_iteration;
 812       else if (_dbus_string_starts_with_c_str (&line, "H>"))
 813         {
 814           printf ("SHA-1: %s\n", _dbus_string_get_const_data (&line));
 815
 816           if (_dbus_string_find (&line, 0, "Type 3", NULL))
 817             {
 818               /* See sha-1/Readme.txt - the "Type 3" tests are
 819                * random seeds, rather than data to be hashed.
 820                * we'd have to do a little bit more implementation
 821                * to use those tests.
 822                */
 823
 824               printf (" (ending tests due to Type 3 tests seen - this is normal)\n");
 825               break;
 826             }
 827         }
 828       else if (_dbus_string_starts_with_c_str (&line, "D>") ||
 829                _dbus_string_starts_with_c_str (&line, "<D"))
 830         goto next_iteration;
 831       else
 832         {
 833           DBusString test;
 834           DBusString result;
 835           DBusString next_line;
 836           DBusString expected;
 837           dbus_bool_t success;
 838
 839           success = FALSE;
 840
 841           if (!_dbus_string_init (&next_line))
 842             _dbus_assert_not_reached ("no memory");
 843
 844           if (!_dbus_string_init (&expected))
 845             _dbus_assert_not_reached ("no memory");
 846
 847           if (!_dbus_string_init (&test))
 848             _dbus_assert_not_reached ("no memory");
 849
 850           if (!_dbus_string_init (&result))
 851             _dbus_assert_not_reached ("no memory");
 852
 853           /* the "compact strings" are "^"-terminated not
 854            * newline-terminated so readahead to find the
 855            * "^"
 856            */
 857           while (!_dbus_string_find (&line, 0, "^", NULL) &&
 858                  _dbus_string_pop_line (&tests, &next_line))
 859             {
 860               if (!_dbus_string_append_byte (&line, ' ') ||
 861                   !_dbus_string_move (&next_line, 0, &line,
 862                                       _dbus_string_get_length (&line)))
 863                 _dbus_assert_not_reached ("no memory");
 864             }
 865
 866           if (!decode_compact_string (&line, &test))
 867             {
 868               fprintf (stderr, "Failed to decode line %d as a compact string\n",
 869                        line_no);
 870               goto failure;
 871             }
 872
 873           if (!_dbus_sha_compute (&test, &result))
 874             _dbus_assert_not_reached ("no memory for SHA-1 result");
 875
 876           if (!get_next_expected_result (&results, &expected))
 877             {
 878               fprintf (stderr, "Failed to read an expected result\n");
 879               goto failure;
 880             }
 881
 882           if (!_dbus_string_equal (&result, &expected))
 883             {
 884               fprintf (stderr, " for line %d got hash %s expected %s\n",
 885                        line_no,
 886                        _dbus_string_get_const_data (&result),
 887                        _dbus_string_get_const_data (&expected));
 888               goto failure;
 889             }
 890           else
 891             {
 892               success_count += 1;
 893             }
 894
 895           success = TRUE;
 896
 897         failure:
 898           _dbus_string_free (&test);
 899           _dbus_string_free (&result);
 900           _dbus_string_free (&next_line);
 901           _dbus_string_free (&expected);
 902
 903           if (!success)
 904             goto out;
 905         }
 906     }
 907
 908   retval = TRUE;
 909
 910   printf ("Passed the %d SHA-1 tests in the test file\n",
 911           success_count);
 912
 913  out:
 914   _dbus_string_free (&tests_file);
 915   _dbus_string_free (&results_file);
 916   _dbus_string_free (&tests);
 917   _dbus_string_free (&results);
 918   _dbus_string_free (&line);
 919
 920   return retval;
 921 }
 922
 923 /**
 924  * @ingroup DBusSHAInternals
 925  * Unit test for SHA computation.
 926  *
 927  * @returns #TRUE on success.
 928  */
 929 dbus_bool_t
 930 _dbus_sha_test (const char *test_data_dir)
 931 {
 932   unsigned char all_bytes[256];
 933   int i;
 934
 935   if (test_data_dir != NULL)
 936     {
 937       if (!process_test_data (test_data_dir))
 938         return FALSE;
 939     }
 940   else
 941     printf ("No test data dir\n");
 942
 943   i = 0;
 944   while (i < 256)
 945     {
 946       all_bytes[i] = i;
 947       ++i;
 948     }
 949
 950   if (!check_sha_binary (all_bytes, 256,
 951                          "4916d6bdb7f78e6803698cab32d1586ea457dfc8"))
 952     return FALSE;
 953
 954 #define CHECK(input,expected) if (!check_sha_str (input, expected)) return FALSE
 955
 956   CHECK ("", "da39a3ee5e6b4b0d3255bfef95601890afd80709");
 957   CHECK ("a", "86f7e437faa5a7fce15d1ddcb9eaeaea377667b8");
 958   CHECK ("abc", "a9993e364706816aba3e25717850c26c9cd0d89d");
 959   CHECK ("message digest", "c12252ceda8be8994d5fa0290a47231c1d16aae3");
 960   CHECK ("abcdefghijklmnopqrstuvwxyz", "32d10c7b8cf96570ca04ce37f2a19d84240d3a89");
 961   CHECK ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
 962          "761c457bf73b14d27e9e9265c46f4b4dda11f940");
 963   CHECK ("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
 964          "50abf5706a150990a08b2c5ea40fa0e585554732");
 965
 966   return TRUE;
 967 }
 968
 969 #endif /* DBUS_BUILD_TESTS */