dbus/dbus-sha.c

   1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
   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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  22  *
  23  */
  24
  25 #include <config.h>
  26 #include "dbus-internals.h"
  27 #include "dbus-sha.h"
  28 #include "dbus-marshal-basic.h" /* for byteswap routines */
  29 #include <string.h>
  30
  31 /* The following comments have the history of where this code
  32  * comes from. I actually copied it from GNet in GNOME CVS.
  33  * - hp@redhat.com
  34  */
  35
  36 /*
  37  *  sha.h : Implementation of the Secure Hash Algorithm
  38  *
  39  * Part of the Python Cryptography Toolkit, version 1.0.0
  40  *
  41  * Copyright (C) 1995, A.M. Kuchling
  42  *
  43  * Distribute and use freely; there are no restrictions on further
  44  * dissemination and usage except those imposed by the laws of your
  45  * country of residence.
  46  *
  47  */
  48
  49 /* SHA: NIST's Secure Hash Algorithm */
  50
  51 /* Based on SHA code originally posted to sci.crypt by Peter Gutmann
  52    in message <30ajo5$oe8@ccu2.auckland.ac.nz>.
  53    Modified to test for endianness on creation of SHA objects by AMK.
  54    Also, the original specification of SHA was found to have a weakness
  55    by NSA/NIST.  This code implements the fixed version of SHA.
  56 */
  57
  58 /* Here's the first paragraph of Peter Gutmann's posting:
  59
  60 The following is my SHA (FIPS 180) code updated to allow use of the "fixed"
  61 SHA, thanks to Jim Gillogly and an anonymous contributor for the information on
  62 what's changed in the new version.  The fix is a simple change which involves
  63 adding a single rotate in the initial expansion function.  It is unknown
  64 whether this is an optimal solution to the problem which was discovered in the
  65 SHA or whether it's simply a bandaid which fixes the problem with a minimum of
  66 effort (for example the reengineering of a great many Capstone chips).
  67 */
  68
  69 /**
  70  * @defgroup DBusSHA SHA implementation
  71  * @ingroup  DBusInternals
  72  * @brief SHA-1 hash
  73  *
  74  * Types and functions related to computing SHA-1 hash.
  75  */
  76
  77 /**
  78  * @defgroup DBusSHAInternals SHA implementation details
  79  * @ingroup  DBusInternals
  80  * @brief Internals of SHA implementation.
  81  *
  82  * The implementation of SHA-1 (see http://www.itl.nist.gov/fipspubs/fip180-1.htm).
  83  * This SHA implementation was written by A.M. Kuchling
  84  *
  85  * @{
  86  */
  87
  88 #ifndef DOXYGEN_SHOULD_SKIP_THIS
  89
  90 /* The SHA block size and message digest sizes, in bytes */
  91
  92 #define SHA_DATASIZE    64
  93 #define SHA_DIGESTSIZE  20
  94
  95 /* The SHA f()-functions.  The f1 and f3 functions can be optimized to
  96    save one boolean operation each - thanks to Rich Schroeppel,
  97    rcs@cs.arizona.edu for discovering this */
  98
  99 /*#define f1(x,y,z) ( ( x & y ) | ( ~x & z ) )          // Rounds  0-19 */
 100 #define f1(x,y,z)  ( z ^ ( x & ( y ^ z ) ) )           /* Rounds  0-19 */
 101 #define f2(x,y,z)  ( x ^ y ^ z )                       /* Rounds 20-39 */
 102 /*#define f3(x,y,z) ( ( x & y ) | ( x & z ) | ( y & z ) )   // Rounds 40-59 */
 103 #define f3(x,y,z)  ( ( x & y ) | ( z & ( x | y ) ) )   /* Rounds 40-59 */
 104 #define f4(x,y,z)  ( x ^ y ^ z )                       /* Rounds 60-79 */
 105
 106 /* The SHA Mysterious Constants */
 107
 108 #define K1  0x5A827999L                                 /* Rounds  0-19 */
 109 #define K2  0x6ED9EBA1L                                 /* Rounds 20-39 */
 110 #define K3  0x8F1BBCDCL                                 /* Rounds 40-59 */
 111 #define K4  0xCA62C1D6L                                 /* Rounds 60-79 */
 112
 113 /* SHA initial values */
 114
 115 #define h0init  0x67452301L
 116 #define h1init  0xEFCDAB89L
 117 #define h2init  0x98BADCFEL
 118 #define h3init  0x10325476L
 119 #define h4init  0xC3D2E1F0L
 120
 121 /* Note that it may be necessary to add parentheses to these macros if they
 122    are to be called with expressions as arguments */
 123 /* 32-bit rotate left - kludged with shifts */
 124
 125 #define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
 126
 127 /* The initial expanding function.  The hash function is defined over an
 128    80-word expanded input array W, where the first 16 are copies of the input
 129    data, and the remaining 64 are defined by
 130
 131         W[ i ] = W[ i - 16 ] ^ W[ i - 14 ] ^ W[ i - 8 ] ^ W[ i - 3 ]
 132
 133    This implementation generates these values on the fly in a circular
 134    buffer - thanks to Colin Plumb, colin@nyx10.cs.du.edu for this
 135    optimization.
 136
 137    The updated SHA changes the expanding function by adding a rotate of 1
 138    bit.  Thanks to Jim Gillogly, jim@rand.org, and an anonymous contributor
 139    for this information */
 140
 141 #define expand(W,i) ( W[ i & 15 ] = ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
 142                                                  W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
 143
 144
 145 /* The prototype SHA sub-round.  The fundamental sub-round is:
 146
 147         a' = e + ROTL( 5, a ) + f( b, c, d ) + k + data;
 148         b' = a;
 149         c' = ROTL( 30, b );
 150         d' = c;
 151         e' = d;
 152
 153    but this is implemented by unrolling the loop 5 times and renaming the
 154    variables ( e, a, b, c, d ) = ( a', b', c', d', e' ) each iteration.
 155    This code is then replicated 20 times for each of the 4 functions, using
 156    the next 20 values from the W[] array each time */
 157
 158 #define subRound(a, b, c, d, e, f, k, data) \
 159    ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
 160
 161 #endif /* !DOXYGEN_SHOULD_SKIP_THIS */
 162
 163 /* Perform the SHA transformation.  Note that this code, like MD5, seems to
 164    break some optimizing compilers due to the complexity of the expressions
 165    and the size of the basic block.  It may be necessary to split it into
 166    sections, e.g. based on the four subrounds
 167
 168    Note that this corrupts the context->data area */
 169
 170 static void
 171 SHATransform(dbus_uint32_t *digest, dbus_uint32_t *data)
 172 {
 173   dbus_uint32_t A, B, C, D, E;     /* Local vars */
 174   dbus_uint32_t eData[16];       /* Expanded data */
 175
 176   /* Set up first buffer and local data buffer */
 177   A = digest[0];
 178   B = digest[1];
 179   C = digest[2];
 180   D = digest[3];
 181   E = digest[4];
 182   memmove (eData, data, SHA_DATASIZE);
 183
 184   /* Heavy mangling, in 4 sub-rounds of 20 interations each. */
 185   subRound (A, B, C, D, E, f1, K1, eData[0]);
 186   subRound (E, A, B, C, D, f1, K1, eData[1]);
 187   subRound (D, E, A, B, C, f1, K1, eData[2]);
 188   subRound (C, D, E, A, B, f1, K1, eData[3]);
 189   subRound (B, C, D, E, A, f1, K1, eData[4]);
 190   subRound (A, B, C, D, E, f1, K1, eData[5]);
 191   subRound (E, A, B, C, D, f1, K1, eData[6]);
 192   subRound (D, E, A, B, C, f1, K1, eData[7]);
 193   subRound (C, D, E, A, B, f1, K1, eData[8]);
 194   subRound (B, C, D, E, A, f1, K1, eData[9]);
 195   subRound (A, B, C, D, E, f1, K1, eData[10]);
 196   subRound (E, A, B, C, D, f1, K1, eData[11]);
 197   subRound (D, E, A, B, C, f1, K1, eData[12]);
 198   subRound (C, D, E, A, B, f1, K1, eData[13]);
 199   subRound (B, C, D, E, A, f1, K1, eData[14]);
 200   subRound (A, B, C, D, E, f1, K1, eData[15]);
 201   subRound (E, A, B, C, D, f1, K1, expand ( eData, 16) );
 202   subRound (D, E, A, B, C, f1, K1, expand ( eData, 17) );
 203   subRound (C, D, E, A, B, f1, K1, expand ( eData, 18) );
 204   subRound (B, C, D, E, A, f1, K1, expand ( eData, 19) );
 205
 206   subRound (A, B, C, D, E, f2, K2, expand ( eData, 20) );
 207   subRound (E, A, B, C, D, f2, K2, expand ( eData, 21) );
 208   subRound (D, E, A, B, C, f2, K2, expand ( eData, 22) );
 209   subRound (C, D, E, A, B, f2, K2, expand ( eData, 23) );
 210   subRound (B, C, D, E, A, f2, K2, expand ( eData, 24) );
 211   subRound (A, B, C, D, E, f2, K2, expand ( eData, 25) );
 212   subRound (E, A, B, C, D, f2, K2, expand ( eData, 26) );
 213   subRound (D, E, A, B, C, f2, K2, expand ( eData, 27) );
 214   subRound (C, D, E, A, B, f2, K2, expand ( eData, 28) );
 215   subRound (B, C, D, E, A, f2, K2, expand ( eData, 29) );
 216   subRound (A, B, C, D, E, f2, K2, expand ( eData, 30) );
 217   subRound (E, A, B, C, D, f2, K2, expand ( eData, 31) );
 218   subRound (D, E, A, B, C, f2, K2, expand ( eData, 32) );
 219   subRound (C, D, E, A, B, f2, K2, expand ( eData, 33) );
 220   subRound (B, C, D, E, A, f2, K2, expand ( eData, 34) );
 221   subRound (A, B, C, D, E, f2, K2, expand ( eData, 35) );
 222   subRound (E, A, B, C, D, f2, K2, expand ( eData, 36) );
 223   subRound (D, E, A, B, C, f2, K2, expand ( eData, 37) );
 224   subRound (C, D, E, A, B, f2, K2, expand ( eData, 38) );
 225   subRound (B, C, D, E, A, f2, K2, expand ( eData, 39) );
 226
 227   subRound (A, B, C, D, E, f3, K3, expand ( eData, 40) );
 228   subRound (E, A, B, C, D, f3, K3, expand ( eData, 41) );
 229   subRound (D, E, A, B, C, f3, K3, expand ( eData, 42) );
 230   subRound (C, D, E, A, B, f3, K3, expand ( eData, 43) );
 231   subRound (B, C, D, E, A, f3, K3, expand ( eData, 44) );
 232   subRound (A, B, C, D, E, f3, K3, expand ( eData, 45) );
 233   subRound (E, A, B, C, D, f3, K3, expand ( eData, 46) );
 234   subRound (D, E, A, B, C, f3, K3, expand ( eData, 47) );
 235   subRound (C, D, E, A, B, f3, K3, expand ( eData, 48) );
 236   subRound (B, C, D, E, A, f3, K3, expand ( eData, 49) );
 237   subRound (A, B, C, D, E, f3, K3, expand ( eData, 50) );
 238   subRound (E, A, B, C, D, f3, K3, expand ( eData, 51) );
 239   subRound (D, E, A, B, C, f3, K3, expand ( eData, 52) );
 240   subRound (C, D, E, A, B, f3, K3, expand ( eData, 53) );
 241   subRound (B, C, D, E, A, f3, K3, expand ( eData, 54) );
 242   subRound (A, B, C, D, E, f3, K3, expand ( eData, 55) );
 243   subRound (E, A, B, C, D, f3, K3, expand ( eData, 56) );
 244   subRound (D, E, A, B, C, f3, K3, expand ( eData, 57) );
 245   subRound (C, D, E, A, B, f3, K3, expand ( eData, 58) );
 246   subRound (B, C, D, E, A, f3, K3, expand ( eData, 59) );
 247
 248   subRound (A, B, C, D, E, f4, K4, expand ( eData, 60) );
 249   subRound (E, A, B, C, D, f4, K4, expand ( eData, 61) );
 250   subRound (D, E, A, B, C, f4, K4, expand ( eData, 62) );
 251   subRound (C, D, E, A, B, f4, K4, expand ( eData, 63) );
 252   subRound (B, C, D, E, A, f4, K4, expand ( eData, 64) );
 253   subRound (A, B, C, D, E, f4, K4, expand ( eData, 65) );
 254   subRound (E, A, B, C, D, f4, K4, expand ( eData, 66) );
 255   subRound (D, E, A, B, C, f4, K4, expand ( eData, 67) );
 256   subRound (C, D, E, A, B, f4, K4, expand ( eData, 68) );
 257   subRound (B, C, D, E, A, f4, K4, expand ( eData, 69) );
 258   subRound (A, B, C, D, E, f4, K4, expand ( eData, 70) );
 259   subRound (E, A, B, C, D, f4, K4, expand ( eData, 71) );
 260   subRound (D, E, A, B, C, f4, K4, expand ( eData, 72) );
 261   subRound (C, D, E, A, B, f4, K4, expand ( eData, 73) );
 262   subRound (B, C, D, E, A, f4, K4, expand ( eData, 74) );
 263   subRound (A, B, C, D, E, f4, K4, expand ( eData, 75) );
 264   subRound (E, A, B, C, D, f4, K4, expand ( eData, 76) );
 265   subRound (D, E, A, B, C, f4, K4, expand ( eData, 77) );
 266   subRound (C, D, E, A, B, f4, K4, expand ( eData, 78) );
 267   subRound (B, C, D, E, A, f4, K4, expand ( eData, 79) );
 268
 269   /* Build message digest */
 270   digest[0] += A;
 271   digest[1] += B;
 272   digest[2] += C;
 273   digest[3] += D;
 274   digest[4] += E;
 275 }
 276
 277 /* When run on a little-endian CPU we need to perform byte reversal on an
 278    array of longwords. */
 279
 280 #ifdef WORDS_BIGENDIAN
 281 #define swap_words(buffer, byte_count)
 282 #else
 283 static void
 284 swap_words (dbus_uint32_t *buffer,
 285             int            byte_count)
 286 {
 287   byte_count /= sizeof (dbus_uint32_t);
 288   while (byte_count--)
 289     {
 290       *buffer = DBUS_UINT32_SWAP_LE_BE (*buffer);
 291       ++buffer;
 292     }
 293 }
 294 #endif
 295
 296 static void
 297 sha_init (DBusSHAContext *context)
 298 {
 299   /* Set the h-vars to their initial values */
 300   context->digest[0] = h0init;
 301   context->digest[1] = h1init;
 302   context->digest[2] = h2init;
 303   context->digest[3] = h3init;
 304   context->digest[4] = h4init;
 305
 306   /* Initialise bit count */
 307   context->count_lo = context->count_hi = 0;
 308 }
 309
 310 static void
 311 sha_append (DBusSHAContext      *context,
 312             const unsigned char *buffer,
 313             unsigned int         count)
 314 {
 315   dbus_uint32_t tmp;
 316   unsigned int dataCount;
 317
 318   /* Update bitcount */
 319   tmp = context->count_lo;
 320   if (( context->count_lo = tmp + ( ( dbus_uint32_t) count << 3) ) < tmp)
 321     context->count_hi++;             /* Carry from low to high */
 322   context->count_hi += count >> 29;
 323
 324   /* Get count of bytes already in data */
 325   dataCount = (int) (tmp >> 3) & 0x3F;
 326
 327   /* Handle any leading odd-sized chunks */
 328   if (dataCount)
 329     {
 330       unsigned char *p = (unsigned char *) context->data + dataCount;
 331
 332       dataCount = SHA_DATASIZE - dataCount;
 333       if (count < dataCount)
 334         {
 335           memmove (p, buffer, count);
 336           return;
 337         }
 338       memmove (p, buffer, dataCount);
 339       swap_words (context->data, SHA_DATASIZE);
 340       SHATransform (context->digest, context->data);
 341       buffer += dataCount;
 342       count -= dataCount;
 343     }
 344
 345   /* Process data in SHA_DATASIZE chunks */
 346   while (count >= SHA_DATASIZE)
 347     {
 348       memmove (context->data, buffer, SHA_DATASIZE);
 349       swap_words (context->data, SHA_DATASIZE);
 350       SHATransform (context->digest, context->data);
 351       buffer += SHA_DATASIZE;
 352       count -= SHA_DATASIZE;
 353     }
 354
 355   /* Handle any remaining bytes of data. */
 356   memmove (context->data, buffer, count);
 357 }
 358
 359
 360 /* Final wrapup - pad to SHA_DATASIZE-byte boundary with the bit pattern
 361    1 0* (64-bit count of bits processed, MSB-first) */
 362
 363 static void
 364 sha_finish (DBusSHAContext *context, unsigned char digest[20])
 365 {
 366   int count;
 367   unsigned char *data_p;
 368
 369   /* Compute number of bytes mod 64 */
 370   count = (int) context->count_lo;
 371   count = (count >> 3) & 0x3F;
 372
 373   /* Set the first char of padding to 0x80.  This is safe since there is
 374      always at least one byte free */
 375   data_p = (unsigned char *) context->data + count;
 376   *data_p++ = 0x80;
 377
 378   /* Bytes of padding needed to make 64 bytes */
 379   count = SHA_DATASIZE - 1 - count;
 380
 381   /* Pad out to 56 mod 64 */
 382   if (count < 8)
 383     {
 384       /* Two lots of padding:  Pad the first block to 64 bytes */
 385       memset (data_p, 0, count);
 386       swap_words (context->data, SHA_DATASIZE);
 387       SHATransform (context->digest, context->data);
 388
 389       /* Now fill the next block with 56 bytes */
 390       memset (context->data, 0, SHA_DATASIZE - 8);
 391     }
 392   else
 393     /* Pad block to 56 bytes */
 394     memset (data_p, 0, count - 8);
 395
 396   /* Append length in bits and transform */
 397   context->data[14] = context->count_hi;
 398   context->data[15] = context->count_lo;
 399
 400   swap_words (context->data, SHA_DATASIZE - 8);
 401   SHATransform (context->digest, context->data);
 402   swap_words (context->digest, SHA_DIGESTSIZE);
 403   memmove (digest, context->digest, SHA_DIGESTSIZE);
 404 }
 405
 406 /** @} */ /* End of internals */
 407
 408 /**
 409  * @addtogroup DBusSHA
 410  *
 411  * @{
 412  */
 413
 414 /**
 415  * Initializes the SHA context.
 416  *
 417  * @param context an uninitialized context, typically on the stack.
 418  */
 419 void
 420 _dbus_sha_init (DBusSHAContext *context)
 421 {
 422   sha_init (context);
 423 }
 424
 425 /**
 426  * Feeds more data into an existing shasum computation.
 427  *
 428  * @param context the SHA context
 429  * @param data the additional data to hash
 430  */
 431 void
 432 _dbus_sha_update (DBusSHAContext   *context,
 433                   const DBusString *data)
 434 {
 435   unsigned int inputLen;
 436   const unsigned char *input;
 437
 438   input = (const unsigned char*) _dbus_string_get_const_data (data);
 439   inputLen = _dbus_string_get_length (data);
 440
 441   sha_append (context, input, inputLen);
 442 }
 443
 444 /**
 445  * SHA finalization. Ends an SHA message-digest operation, writing the
 446  * the message digest and zeroing the context.  The results are
 447  * returned as a raw 20-byte digest, not as the ascii-hex-digits
 448  * string form of the digest.
 449  *
 450  * @param context the SHA context
 451  * @param results string to append the 20-byte SHA digest to
 452  * @returns #FALSE if not enough memory to append the digest
 453  *
 454  */
 455 dbus_bool_t
 456 _dbus_sha_final (DBusSHAContext   *context,
 457                  DBusString       *results)
 458 {
 459   unsigned char digest[20];
 460
 461   sha_finish (context, digest);
 462
 463   if (!_dbus_string_append_len (results, digest, 20))
 464     return FALSE;
 465
 466   /* some kind of security paranoia, though it seems pointless
 467    * to me given the nonzeroed stuff flying around
 468    */
 469   _DBUS_ZERO(*context);
 470
 471   return TRUE;
 472 }
 473
 474 /**
 475  * Computes the ASCII hex-encoded shasum of the given data and
 476  * appends it to the output string.
 477  *
 478  * @param data input data to be hashed
 479  * @param ascii_output string to append ASCII shasum to
 480  * @returns #FALSE if not enough memory
 481  */
 482 dbus_bool_t
 483 _dbus_sha_compute (const DBusString *data,
 484                    DBusString       *ascii_output)
 485 {
 486   DBusSHAContext context;
 487   DBusString digest;
 488
 489   _dbus_sha_init (&context);
 490
 491   _dbus_sha_update (&context, data);
 492
 493   if (!_dbus_string_init (&digest))
 494     return FALSE;
 495
 496   if (!_dbus_sha_final (&context, &digest))
 497     goto error;
 498
 499   if (!_dbus_string_hex_encode (&digest, 0, ascii_output,
 500                                 _dbus_string_get_length (ascii_output)))
 501     goto error;
 502
 503   _dbus_string_free (&digest);
 504
 505   return TRUE;
 506
 507  error:
 508   _dbus_string_free (&digest);
 509   return FALSE;
 510 }
 511
 512 /** @} */ /* end of exported functions */
 513
 514 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 515 #include "dbus-test.h"
 516 #include <stdio.h>
 517
 518 static dbus_bool_t
 519 check_sha_binary (const unsigned char *input,
 520                   int                  input_len,
 521                   const char          *expected)
 522 {
 523   DBusString input_str;
 524   DBusString expected_str;
 525   DBusString results;
 526
 527   _dbus_string_init_const_len (&input_str, input, input_len);
 528   _dbus_string_init_const (&expected_str, expected);
 529
 530   if (!_dbus_string_init (&results))
 531     _dbus_assert_not_reached ("no memory for SHA-1 results");
 532
 533   if (!_dbus_sha_compute (&input_str, &results))
 534     _dbus_assert_not_reached ("no memory for SHA-1 results");
 535
 536   if (!_dbus_string_equal (&expected_str, &results))
 537     {
 538       _dbus_warn ("Expected hash %s got %s for SHA-1 sum\n",
 539                   expected,
 540                   _dbus_string_get_const_data (&results));
 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       fprintf (stderr, "could not parse length at start of compact string: %s\n",
 573                _dbus_string_get_const_data (line));
 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       fprintf (stderr, "could not parse start bit 'b' in compact string: %s\n",
 583                _dbus_string_get_const_data (line));
 584       return FALSE;
 585     }
 586
 587   if (!(val == 0 || val == 1))
 588     {
 589       fprintf (stderr, "the value 'b' must be 0 or 1, see sha-1/Readme.txt\n");
 590       return FALSE;
 591     }
 592
 593   _dbus_string_skip_blank (line, next, &next);
 594
 595   current_b = val;
 596   n_bits = 0;
 597
 598   while (next < _dbus_string_get_length (line))
 599     {
 600       int total_bits;
 601
 602       offset = next;
 603
 604       if (_dbus_string_get_byte (line, offset) == '^')
 605         break;
 606
 607       if (!_dbus_string_parse_int (line, offset, &val, &next))
 608         {
 609           fprintf (stderr, "could not parse bit count in compact string\n");
 610           return FALSE;
 611         }
 612
 613       /* We now append "val" copies of "current_b" bits to the string */
 614       total_bits = n_bits + val;
 615       while (n_bits < total_bits)
 616         {
 617           int byte_containing_next_bit = n_bits / 8;
 618           int bit_containing_next_bit = 7 - (n_bits % 8);
 619           unsigned char old_byte;
 620
 621           if (byte_containing_next_bit >= _dbus_string_get_length (decoded))
 622             {
 623               if (!_dbus_string_set_length (decoded, byte_containing_next_bit + 1))
 624                 _dbus_assert_not_reached ("no memory to extend to next byte");
 625             }
 626
 627           old_byte = _dbus_string_get_byte (decoded, byte_containing_next_bit);
 628           old_byte |= current_b << bit_containing_next_bit;
 629
 630 #if 0
 631           printf ("Appending bit %d to byte %d at bit %d resulting in byte 0x%x\n",
 632                   current_b, byte_containing_next_bit,
 633                   bit_containing_next_bit, old_byte);
 634 #endif
 635
 636           _dbus_string_set_byte (decoded, byte_containing_next_bit, old_byte);
 637
 638           ++n_bits;
 639         }
 640
 641       _dbus_string_skip_blank (line, next, &next);
 642
 643       current_b = !current_b;
 644     }
 645
 646   length_bytes = (n_bits / 8 + ((n_bits % 8) ? 1 : 0));
 647
 648   if (_dbus_string_get_length (decoded) != length_bytes)
 649     {
 650       fprintf (stderr, "Expected length %d bytes %d bits for compact string, got %d bytes\n",
 651                length_bytes, n_bits, _dbus_string_get_length (decoded));
 652       return FALSE;
 653     }
 654   else
 655     return TRUE;
 656 }
 657
 658 static dbus_bool_t
 659 get_next_expected_result (DBusString *results,
 660                           DBusString *result)
 661 {
 662   DBusString line;
 663   dbus_bool_t retval;
 664
 665   retval = FALSE;
 666
 667   if (!_dbus_string_init (&line))
 668     _dbus_assert_not_reached ("no memory");
 669
 670  next_iteration:
 671   while (_dbus_string_pop_line (results, &line))
 672     {
 673       _dbus_string_delete_leading_blanks (&line);
 674
 675       if (_dbus_string_get_length (&line) == 0)
 676         goto next_iteration;
 677       else if (_dbus_string_starts_with_c_str (&line, "#"))
 678         goto next_iteration;
 679       else if (_dbus_string_starts_with_c_str (&line, "H>"))
 680         {
 681           /* don't print */
 682         }
 683       else if (_dbus_string_starts_with_c_str (&line, "D>") ||
 684                _dbus_string_starts_with_c_str (&line, "<D"))
 685         goto next_iteration;
 686       else
 687         {
 688           int i;
 689
 690           if (!_dbus_string_move (&line, 0, result, 0))
 691             _dbus_assert_not_reached ("no memory");
 692
 693           i = 0;
 694           while (i < _dbus_string_get_length (result))
 695             {
 696               switch (_dbus_string_get_byte (result, i))
 697                 {
 698                 case 'A':
 699                   _dbus_string_set_byte (result, i, 'a');
 700                   break;
 701                 case 'B':
 702                   _dbus_string_set_byte (result, i, 'b');
 703                   break;
 704                 case 'C':
 705                   _dbus_string_set_byte (result, i, 'c');
 706                   break;
 707                 case 'D':
 708                   _dbus_string_set_byte (result, i, 'd');
 709                   break;
 710                 case 'E':
 711                   _dbus_string_set_byte (result, i, 'e');
 712                   break;
 713                 case 'F':
 714                   _dbus_string_set_byte (result, i, 'f');
 715                   break;
 716                 case '^':
 717                 case ' ':
 718                   _dbus_string_delete (result, i, 1);
 719                   --i; /* to offset ++i below */
 720                   break;
 721                 }
 722
 723               ++i;
 724             }
 725
 726           break;
 727         }
 728     }
 729
 730   retval = TRUE;
 731
 732   /* out: */
 733   _dbus_string_free (&line);
 734   return retval;
 735 }
 736
 737 static dbus_bool_t
 738 process_test_data (const char *test_data_dir)
 739 {
 740   DBusString tests_file;
 741   DBusString results_file;
 742   DBusString tests;
 743   DBusString results;
 744   DBusString line;
 745   DBusString tmp;
 746   int line_no;
 747   dbus_bool_t retval;
 748   int success_count;
 749   DBusError error = DBUS_ERROR_INIT;
 750
 751   retval = FALSE;
 752
 753   if (!_dbus_string_init (&tests_file))
 754     _dbus_assert_not_reached ("no memory");
 755
 756   if (!_dbus_string_init (&results_file))
 757     _dbus_assert_not_reached ("no memory");
 758
 759   if (!_dbus_string_init (&tests))
 760     _dbus_assert_not_reached ("no memory");
 761
 762   if (!_dbus_string_init (&results))
 763     _dbus_assert_not_reached ("no memory");
 764
 765   if (!_dbus_string_init (&line))
 766     _dbus_assert_not_reached ("no memory");
 767
 768   if (!_dbus_string_append (&tests_file, test_data_dir))
 769     _dbus_assert_not_reached ("no memory");
 770
 771   if (!_dbus_string_append (&results_file, test_data_dir))
 772     _dbus_assert_not_reached ("no memory");
 773
 774   _dbus_string_init_const (&tmp, "sha-1/byte-messages.sha1");
 775   if (!_dbus_concat_dir_and_file (&tests_file, &tmp))
 776     _dbus_assert_not_reached ("no memory");
 777
 778   _dbus_string_init_const (&tmp, "sha-1/byte-hashes.sha1");
 779   if (!_dbus_concat_dir_and_file (&results_file, &tmp))
 780     _dbus_assert_not_reached ("no memory");
 781
 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_ENABLE_EMBEDDED_TESTS */