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