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 1.2
   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-marshal.h"
  27 #include "dbus-sha.h"
  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   unsigned char *input;
 436
 437   _dbus_string_get_const_data (data, (const char**) &input);
 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, _DBUS_INT_MAX))
 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, _DBUS_INT_MAX))
 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       const char *s;
 538       _dbus_string_get_const_data (&results, &s);
 539       _dbus_warn ("Expected hash %s got %s for SHA-1 sum\n",
 540                   expected, s);
 541       _dbus_string_free (&results);
 542       return FALSE;
 543     }
 544
 545   _dbus_string_free (&results);
 546   return TRUE;
 547 }
 548
 549 static dbus_bool_t
 550 check_sha_str (const char *input,
 551                const char *expected)
 552 {
 553   return check_sha_binary (input, strlen (input), expected);
 554 }
 555
 556 static dbus_bool_t
 557 decode_compact_string (const DBusString *line,
 558                        DBusString       *decoded)
 559 {
 560   int n_bits;
 561   dbus_bool_t current_b;
 562   int offset;
 563   int next;
 564   long val;
 565   int length_bytes;
 566
 567   offset = 0;
 568   next = 0;
 569
 570   if (!_dbus_string_parse_int (line, offset, &val, &next))
 571     {
 572       const char *s;
 573       _dbus_string_get_const_data (line, &s);
 574       fprintf (stderr, "could not parse length at start of compact string: %s\n",
 575                s);
 576       return FALSE;
 577     }
 578
 579   _dbus_string_skip_blank (line, next, &next);
 580
 581   offset = next;
 582   if (!_dbus_string_parse_int (line, offset, &val, &next))
 583     {
 584       const char *s;
 585       _dbus_string_get_const_data (line, &s);
 586       fprintf (stderr, "could not parse start bit 'b' in compact string: %s\n",
 587                s);
 588       return FALSE;
 589     }
 590
 591   if (!(val == 0 || val == 1))
 592     {
 593       fprintf (stderr, "the value 'b' must be 0 or 1, see sha-1/Readme.txt\n");
 594       return FALSE;
 595     }
 596
 597   _dbus_string_skip_blank (line, next, &next);
 598
 599   current_b = val;
 600   n_bits = 0;
 601
 602   while (next < _dbus_string_get_length (line))
 603     {
 604       int total_bits;
 605
 606       offset = next;
 607
 608       if (_dbus_string_get_byte (line, offset) == '^')
 609         break;
 610
 611       if (!_dbus_string_parse_int (line, offset, &val, &next))
 612         {
 613           fprintf (stderr, "could not parse bit count in compact string\n");
 614           return FALSE;
 615         }
 616
 617       /* We now append "val" copies of "current_b" bits to the string */
 618       total_bits = n_bits + val;
 619       while (n_bits < total_bits)
 620         {
 621           int byte_containing_next_bit = n_bits / 8;
 622           int bit_containing_next_bit = 7 - (n_bits % 8);
 623           unsigned char old_byte;
 624
 625           if (byte_containing_next_bit >= _dbus_string_get_length (decoded))
 626             {
 627               if (!_dbus_string_set_length (decoded, byte_containing_next_bit + 1))
 628                 _dbus_assert_not_reached ("no memory to extend to next byte");
 629             }
 630
 631           old_byte = _dbus_string_get_byte (decoded, byte_containing_next_bit);
 632           old_byte |= current_b << bit_containing_next_bit;
 633
 634 #if 0
 635           printf ("Appending bit %d to byte %d at bit %d resulting in byte 0x%x\n",
 636                   current_b, byte_containing_next_bit,
 637                   bit_containing_next_bit, old_byte);
 638 #endif
 639
 640           _dbus_string_set_byte (decoded, byte_containing_next_bit, old_byte);
 641
 642           ++n_bits;
 643         }
 644
 645       _dbus_string_skip_blank (line, next, &next);
 646
 647       current_b = !current_b;
 648     }
 649
 650   length_bytes = (n_bits / 8 + ((n_bits % 8) ? 1 : 0));
 651
 652   if (_dbus_string_get_length (decoded) != length_bytes)
 653     {
 654       fprintf (stderr, "Expected length %d bytes %d bits for compact string, got %d bytes\n",
 655                length_bytes, n_bits, _dbus_string_get_length (decoded));
 656       return FALSE;
 657     }
 658   else
 659     return TRUE;
 660 }
 661
 662 static dbus_bool_t
 663 get_next_expected_result (DBusString *results,
 664                           DBusString *result)
 665 {
 666   DBusString line;
 667   dbus_bool_t retval;
 668
 669   retval = FALSE;
 670
 671   if (!_dbus_string_init (&line, _DBUS_INT_MAX))
 672     _dbus_assert_not_reached ("no memory");
 673
 674  next_iteration:
 675   while (_dbus_string_pop_line (results, &line))
 676     {
 677       _dbus_string_delete_leading_blanks (&line);
 678
 679       if (_dbus_string_get_length (&line) == 0)
 680         goto next_iteration;
 681       else if (_dbus_string_starts_with_c_str (&line, "#"))
 682         goto next_iteration;
 683       else if (_dbus_string_starts_with_c_str (&line, "H>"))
 684         {
 685           const char *s;
 686           _dbus_string_get_const_data (&line, &s);
 687           /* don't print */
 688         }
 689       else if (_dbus_string_starts_with_c_str (&line, "D>") ||
 690                _dbus_string_starts_with_c_str (&line, "<D"))
 691         goto next_iteration;
 692       else
 693         {
 694           int i;
 695
 696           if (!_dbus_string_move (&line, 0, result, 0))
 697             _dbus_assert_not_reached ("no memory");
 698
 699           i = 0;
 700           while (i < _dbus_string_get_length (result))
 701             {
 702               switch (_dbus_string_get_byte (result, i))
 703                 {
 704                 case 'A':
 705                   _dbus_string_set_byte (result, i, 'a');
 706                   break;
 707                 case 'B':
 708                   _dbus_string_set_byte (result, i, 'b');
 709                   break;
 710                 case 'C':
 711                   _dbus_string_set_byte (result, i, 'c');
 712                   break;
 713                 case 'D':
 714                   _dbus_string_set_byte (result, i, 'd');
 715                   break;
 716                 case 'E':
 717                   _dbus_string_set_byte (result, i, 'e');
 718                   break;
 719                 case 'F':
 720                   _dbus_string_set_byte (result, i, 'f');
 721                   break;
 722                 case '^':
 723                 case ' ':
 724                   _dbus_string_delete (result, i, 1);
 725                   --i; /* to offset ++i below */
 726                   break;
 727                 }
 728
 729               ++i;
 730             }
 731
 732           break;
 733         }
 734     }
 735
 736   retval = TRUE;
 737
 738   /* out: */
 739   _dbus_string_free (&line);
 740   return retval;
 741 }
 742
 743 static dbus_bool_t
 744 process_test_data (const char *test_data_dir)
 745 {
 746   DBusString tests_file;
 747   DBusString results_file;
 748   DBusString tests;
 749   DBusString results;
 750   DBusString line;
 751   DBusString tmp;
 752   int line_no;
 753   dbus_bool_t retval;
 754   int success_count;
 755
 756   retval = FALSE;
 757
 758   if (!_dbus_string_init (&tests_file, _DBUS_INT_MAX))
 759     _dbus_assert_not_reached ("no memory");
 760
 761   if (!_dbus_string_init (&results_file, _DBUS_INT_MAX))
 762     _dbus_assert_not_reached ("no memory");
 763
 764   if (!_dbus_string_init (&tests, _DBUS_INT_MAX))
 765     _dbus_assert_not_reached ("no memory");
 766
 767   if (!_dbus_string_init (&results, _DBUS_INT_MAX))
 768     _dbus_assert_not_reached ("no memory");
 769
 770   if (!_dbus_string_init (&line, _DBUS_INT_MAX))
 771     _dbus_assert_not_reached ("no memory");
 772
 773   if (!_dbus_string_append (&tests_file, test_data_dir))
 774     _dbus_assert_not_reached ("no memory");
 775
 776   if (!_dbus_string_append (&results_file, test_data_dir))
 777     _dbus_assert_not_reached ("no memory");
 778
 779   _dbus_string_init_const (&tmp, "sha-1/byte-messages.sha1");
 780   if (!_dbus_concat_dir_and_file (&tests_file, &tmp))
 781     _dbus_assert_not_reached ("no memory");
 782
 783   _dbus_string_init_const (&tmp, "sha-1/byte-hashes.sha1");
 784   if (!_dbus_concat_dir_and_file (&results_file, &tmp))
 785     _dbus_assert_not_reached ("no memory");
 786
 787   if (_dbus_file_get_contents (&tests, &tests_file) != DBUS_RESULT_SUCCESS)
 788     {
 789       const char *s;
 790       _dbus_string_get_const_data (&tests_file, &s);
 791       fprintf (stderr, "could not load test data file %s\n",
 792                s);
 793       goto out;
 794     }
 795
 796   if (_dbus_file_get_contents (&results, &results_file) != DBUS_RESULT_SUCCESS)
 797     {
 798       const char *s;
 799       _dbus_string_get_const_data (&results_file, &s);
 800       fprintf (stderr, "could not load results data file %s\n",
 801                s);
 802       goto out;
 803     }
 804
 805   success_count = 0;
 806   line_no = 0;
 807  next_iteration:
 808   while (_dbus_string_pop_line (&tests, &line))
 809     {
 810       line_no += 1;
 811
 812       _dbus_string_delete_leading_blanks (&line);
 813
 814       if (_dbus_string_get_length (&line) == 0)
 815         goto next_iteration;
 816       else if (_dbus_string_starts_with_c_str (&line, "#"))
 817         goto next_iteration;
 818       else if (_dbus_string_starts_with_c_str (&line, "H>"))
 819         {
 820           const char *s;
 821           _dbus_string_get_const_data (&line, &s);
 822           printf ("SHA-1: %s\n", s);
 823
 824           if (_dbus_string_find (&line, 0, "Type 3", NULL))
 825             {
 826               /* See sha-1/Readme.txt - the "Type 3" tests are
 827                * random seeds, rather than data to be hashed.
 828                * we'd have to do a little bit more implementation
 829                * to use those tests.
 830                */
 831
 832               printf (" (ending tests due to Type 3 tests seen - this is normal)\n");
 833               break;
 834             }
 835         }
 836       else if (_dbus_string_starts_with_c_str (&line, "D>") ||
 837                _dbus_string_starts_with_c_str (&line, "<D"))
 838         goto next_iteration;
 839       else
 840         {
 841           DBusString test;
 842           DBusString result;
 843           DBusString next_line;
 844           DBusString expected;
 845           dbus_bool_t success;
 846
 847           success = FALSE;
 848
 849           if (!_dbus_string_init (&next_line, _DBUS_INT_MAX))
 850             _dbus_assert_not_reached ("no memory");
 851
 852           if (!_dbus_string_init (&expected, _DBUS_INT_MAX))
 853             _dbus_assert_not_reached ("no memory");
 854
 855           if (!_dbus_string_init (&test, _DBUS_INT_MAX))
 856             _dbus_assert_not_reached ("no memory");
 857
 858           if (!_dbus_string_init (&result, _DBUS_INT_MAX))
 859             _dbus_assert_not_reached ("no memory");
 860
 861           /* the "compact strings" are "^"-terminated not
 862            * newline-terminated so readahead to find the
 863            * "^"
 864            */
 865           while (!_dbus_string_find (&line, 0, "^", NULL) &&
 866                  _dbus_string_pop_line (&tests, &next_line))
 867             {
 868               if (!_dbus_string_append_byte (&line, ' ') ||
 869                   !_dbus_string_move (&next_line, 0, &line,
 870                                       _dbus_string_get_length (&line)))
 871                 _dbus_assert_not_reached ("no memory");
 872             }
 873
 874           if (!decode_compact_string (&line, &test))
 875             {
 876               fprintf (stderr, "Failed to decode line %d as a compact string\n",
 877                        line_no);
 878               goto failure;
 879             }
 880
 881           if (!_dbus_sha_compute (&test, &result))
 882             _dbus_assert_not_reached ("no memory for SHA-1 result");
 883
 884           if (!get_next_expected_result (&results, &expected))
 885             {
 886               fprintf (stderr, "Failed to read an expected result\n");
 887               goto failure;
 888             }
 889
 890           if (!_dbus_string_equal (&result, &expected))
 891             {
 892               const char *s1;
 893               const char *s2;
 894
 895               _dbus_string_get_const_data (&result, &s1);
 896               _dbus_string_get_const_data (&expected, &s2);
 897
 898               fprintf (stderr, " for line %d got hash %s expected %s\n",
 899                        line_no, s1, s2);
 900               goto failure;
 901             }
 902           else
 903             {
 904               const char *s;
 905               _dbus_string_get_const_data (&result, &s);
 906               /* printf (" Got expected: %s\n", s); */
 907               success_count += 1;
 908             }
 909
 910           success = TRUE;
 911
 912         failure:
 913           _dbus_string_free (&test);
 914           _dbus_string_free (&result);
 915           _dbus_string_free (&next_line);
 916           _dbus_string_free (&expected);
 917
 918           if (!success)
 919             goto out;
 920         }
 921     }
 922
 923   retval = TRUE;
 924
 925   printf ("Passed the %d SHA-1 tests in the test file\n",
 926           success_count);
 927
 928  out:
 929   _dbus_string_free (&tests_file);
 930   _dbus_string_free (&results_file);
 931   _dbus_string_free (&tests);
 932   _dbus_string_free (&results);
 933   _dbus_string_free (&line);
 934
 935   return retval;
 936 }
 937
 938 /**
 939  * @ingroup DBusSHAInternals
 940  * Unit test for SHA computation.
 941  *
 942  * @returns #TRUE on success.
 943  */
 944 dbus_bool_t
 945 _dbus_sha_test (const char *test_data_dir)
 946 {
 947   unsigned char all_bytes[256];
 948   int i;
 949
 950   if (test_data_dir != NULL)
 951     {
 952       if (!process_test_data (test_data_dir))
 953         return FALSE;
 954     }
 955   else
 956     printf ("No test data dir\n");
 957
 958   i = 0;
 959   while (i < 256)
 960     {
 961       all_bytes[i] = i;
 962       ++i;
 963     }
 964
 965   if (!check_sha_binary (all_bytes, 256,
 966                          "4916d6bdb7f78e6803698cab32d1586ea457dfc8"))
 967     return FALSE;
 968
 969 #define CHECK(input,expected) if (!check_sha_str (input, expected)) return FALSE
 970
 971   CHECK ("", "da39a3ee5e6b4b0d3255bfef95601890afd80709");
 972   CHECK ("a", "86f7e437faa5a7fce15d1ddcb9eaeaea377667b8");
 973   CHECK ("abc", "a9993e364706816aba3e25717850c26c9cd0d89d");
 974   CHECK ("message digest", "c12252ceda8be8994d5fa0290a47231c1d16aae3");
 975   CHECK ("abcdefghijklmnopqrstuvwxyz", "32d10c7b8cf96570ca04ce37f2a19d84240d3a89");
 976   CHECK ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
 977          "761c457bf73b14d27e9e9265c46f4b4dda11f940");
 978   CHECK ("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
 979          "50abf5706a150990a08b2c5ea40fa0e585554732");
 980
 981   return TRUE;
 982 }
 983
 984 #endif /* DBUS_BUILD_TESTS */