dbus/dbus-string.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-string.c String utility class (internal to D-BUS implementation)
   3  *
   4  * Copyright (C) 2002  Red Hat, Inc.
   5  *
   6  * Licensed under the Academic Free License version 1.2
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  */
  23
  24 #include "dbus-internals.h"
  25 #include "dbus-string.h"
  26 /* we allow a system header here, for speed/convenience */
  27 #include <string.h>
  28
  29 /**
  30  * @defgroup DBusString string class
  31  * @ingroup  DBusInternals
  32  * @brief DBusString data structure
  33  *
  34  * Types and functions related to DBusString. DBusString is intended
  35  * to be a string class that makes it hard to mess up security issues
  36  * (and just in general harder to write buggy code).  It should be
  37  * used (or extended and then used) rather than the libc stuff in
  38  * string.h.  The string class is a bit inconvenient at spots because
  39  * it handles out-of-memory failures and tries to be extra-robust.
  40  *
  41  * A DBusString has a maximum length set at initialization time; this
  42  * can be used to ensure that a buffer doesn't get too big.  The
  43  * _dbus_string_lengthen() method checks for overflow, and for max
  44  * length being exceeded.
  45  *
  46  * Try to avoid conversion to a plain C string, i.e. add methods on
  47  * the string object instead, only convert to C string when passing
  48  * things out to the public API. In particular, no sprintf, strcpy,
  49  * strcat, any of that should be used. The GString feature of
  50  * accepting negative numbers for "length of string" is also absent,
  51  * because it could keep us from detecting bogus huge lengths. i.e. if
  52  * we passed in some bogus huge length it would be taken to mean
  53  * "current length of string" instead of "broken crack"
  54  */
  55
  56 /**
  57  * @defgroup DBusStringInternals DBusString implementation details
  58  * @ingroup  DBusInternals
  59  * @brief DBusString implementation details
  60  *
  61  * The guts of DBusString.
  62  *
  63  * @{
  64  */
  65
  66 /**
  67  * @brief Internals of DBusString.
  68  *
  69  * DBusString internals. DBusString is an opaque objects, it must be
  70  * used via accessor functions.
  71  */
  72 typedef struct
  73 {
  74   unsigned char *str;            /**< String data, plus nul termination */
  75   int            len;            /**< Length without nul */
  76   int            allocated;      /**< Allocated size of data */
  77   int            max_length;     /**< Max length of this string. */
  78   unsigned int   constant : 1;   /**< String data is not owned by DBusString */
  79   unsigned int   locked : 1;     /**< DBusString has been locked and can't be changed */
  80   unsigned int   invalid : 1;    /**< DBusString is invalid (e.g. already freed) */
  81 } DBusRealString;
  82
  83 /**
  84  * Checks a bunch of assertions about a string object
  85  *
  86  * @param real the DBusRealString
  87  */
  88 #define DBUS_GENERIC_STRING_PREAMBLE(real) _dbus_assert ((real) != NULL); _dbus_assert (!(real)->invalid); _dbus_assert ((real)->len >= 0); _dbus_assert ((real)->allocated >= 0); _dbus_assert ((real)->max_length >= 0); _dbus_assert ((real)->len <= (real)->allocated); _dbus_assert ((real)->len <= (real)->max_length)
  89
  90 /**
  91  * Checks assertions about a string object that needs to be
  92  * modifiable - may not be locked or const. Also declares
  93  * the "real" variable pointing to DBusRealString.
  94  * @param str the string
  95  */
  96 #define DBUS_STRING_PREAMBLE(str) DBusRealString *real = (DBusRealString*) str; \
  97   DBUS_GENERIC_STRING_PREAMBLE (real);                                          \
  98   _dbus_assert (!(real)->constant);                                             \
  99   _dbus_assert (!(real)->locked)
 100
 101 /**
 102  * Checks assertions about a string object that may be locked but
 103  * can't be const. i.e. a string object that we can free.  Also
 104  * declares the "real" variable pointing to DBusRealString.
 105  *
 106  * @param str the string
 107  */
 108 #define DBUS_LOCKED_STRING_PREAMBLE(str) DBusRealString *real = (DBusRealString*) str; \
 109   DBUS_GENERIC_STRING_PREAMBLE (real);                                                 \
 110   _dbus_assert (!(real)->constant)
 111
 112 /**
 113  * Checks assertions about a string that may be const or locked.  Also
 114  * declares the "real" variable pointing to DBusRealString.
 115  * @param str the string.
 116  */
 117 #define DBUS_CONST_STRING_PREAMBLE(str) const DBusRealString *real = (DBusRealString*) str; \
 118   DBUS_GENERIC_STRING_PREAMBLE (real)
 119
 120 /** @} */
 121
 122 /**
 123  * @addtogroup DBusString
 124  * @{
 125  */
 126
 127 /** Assert that the string's memory is 8-byte aligned.
 128  *
 129  *  @todo Currently we just hope libc returns 8-byte aligned memory
 130  *  (which is true for GNU libc), but really we need to ensure it by
 131  *  allocating 8 extra bytes and keeping an "align_offset : 3" field
 132  *  in DBusString, or something along those lines.
 133  */
 134 #define ASSERT_8_BYTE_ALIGNED(s) \
 135   _dbus_assert (_DBUS_ALIGN_ADDRESS (((const DBusRealString*)s)->str, 8) == ((const DBusRealString*)s)->str)
 136
 137 /**
 138  * Initializes a string. The maximum length may be _DBUS_INT_MAX for
 139  * no maximum. The string starts life with zero length.
 140  * The string must eventually be freed with _dbus_string_free().
 141  *
 142  * @param str memory to hold the string
 143  * @param max_length the maximum size of the string
 144  * @returns #TRUE on success
 145  */
 146 dbus_bool_t
 147 _dbus_string_init (DBusString *str,
 148                    int         max_length)
 149 {
 150   DBusRealString *real;
 151
 152   _dbus_assert (str != NULL);
 153   _dbus_assert (max_length >= 0);
 154
 155   _dbus_assert (sizeof (DBusString) == sizeof (DBusRealString));
 156
 157   real = (DBusRealString*) str;
 158
 159   /* It's very important not to touch anything
 160    * other than real->str if we're going to fail,
 161    * since we also use this function to reset
 162    * an existing string, e.g. in _dbus_string_steal_data()
 163    */
 164
 165 #define INITIAL_ALLOC 2
 166
 167   real->str = dbus_malloc (INITIAL_ALLOC);
 168   if (real->str == NULL)
 169     return FALSE;
 170
 171   real->allocated = INITIAL_ALLOC;
 172   real->len = 0;
 173   real->str[real->len] = '\0';
 174
 175   real->max_length = max_length;
 176   real->constant = FALSE;
 177   real->locked = FALSE;
 178   real->invalid = FALSE;
 179
 180   ASSERT_8_BYTE_ALIGNED (str);
 181
 182   return TRUE;
 183 }
 184
 185 /**
 186  * Initializes a constant string. The value parameter is not copied
 187  * (should be static), and the string may never be modified.
 188  * It is safe but not necessary to call _dbus_string_free()
 189  * on a const string.
 190  *
 191  * @param str memory to use for the string
 192  * @param value a string to be stored in str (not copied!!!)
 193  */
 194 void
 195 _dbus_string_init_const (DBusString *str,
 196                          const char *value)
 197 {
 198   _dbus_string_init_const_len (str, value,
 199                                strlen (value));
 200 }
 201
 202 /**
 203  * Initializes a constant string with a length. The value parameter is
 204  * not copied (should be static), and the string may never be
 205  * modified.  It is safe but not necessary to call _dbus_string_free()
 206  * on a const string.
 207  *
 208  * @param str memory to use for the string
 209  * @param value a string to be stored in str (not copied!!!)
 210  * @param len the length to use
 211  */
 212 void
 213 _dbus_string_init_const_len (DBusString *str,
 214                              const char *value,
 215                              int         len)
 216 {
 217   DBusRealString *real;
 218
 219   _dbus_assert (str != NULL);
 220   _dbus_assert (value != NULL);
 221
 222   real = (DBusRealString*) str;
 223
 224   real->str = (char*) value;
 225   real->len = len;
 226   real->allocated = real->len;
 227   real->max_length = real->len;
 228   real->constant = TRUE;
 229   real->invalid = FALSE;
 230
 231   /* We don't require const strings to be 8-byte aligned as the
 232    * memory is coming from elsewhere.
 233    */
 234 }
 235
 236 /**
 237  * Frees a string created by _dbus_string_init().
 238  *
 239  * @param str memory where the string is stored.
 240  */
 241 void
 242 _dbus_string_free (DBusString *str)
 243 {
 244   DBUS_LOCKED_STRING_PREAMBLE (str);
 245
 246   if (real->constant)
 247     return;
 248
 249   dbus_free (real->str);
 250
 251   real->invalid = TRUE;
 252 }
 253
 254 /**
 255  * Locks a string such that any attempts to change the string
 256  * will result in aborting the program. Also, if the string
 257  * is wasting a lot of memory (allocation is larger than what
 258  * the string is really using), _dbus_string_lock() will realloc
 259  * the string's data to "compact" it.
 260  *
 261  * @param str the string to lock.
 262  */
 263 void
 264 _dbus_string_lock (DBusString *str)
 265 {
 266   DBUS_LOCKED_STRING_PREAMBLE (str); /* can lock multiple times */
 267
 268   real->locked = TRUE;
 269
 270   /* Try to realloc to avoid excess memory usage, since
 271    * we know we won't change the string further
 272    */
 273 #define MAX_WASTE 24
 274   if (real->allocated > (real->len + MAX_WASTE))
 275     {
 276       char *new_str;
 277       int new_allocated;
 278
 279       new_allocated = real->len + 1;
 280
 281       new_str = dbus_realloc (real->str, new_allocated);
 282       if (new_str != NULL)
 283         {
 284           real->str = new_str;
 285           real->allocated = new_allocated;
 286           ASSERT_8_BYTE_ALIGNED (str);
 287         }
 288     }
 289 }
 290
 291 /**
 292  * Gets the raw character buffer from the string.  The returned buffer
 293  * will be nul-terminated, but note that strings may contain binary
 294  * data so there may be extra nul characters prior to the termination.
 295  * This function should be little-used, extend DBusString or add
 296  * stuff to dbus-sysdeps.c instead. It's an error to use this
 297  * function on a const string.
 298  *
 299  * @param str the string
 300  * @param data_return place to store the returned data
 301  */
 302 void
 303 _dbus_string_get_data (DBusString        *str,
 304                        char             **data_return)
 305 {
 306   DBUS_STRING_PREAMBLE (str);
 307   _dbus_assert (data_return != NULL);
 308
 309   *data_return = real->str;
 310 }
 311
 312 /**
 313  * Gets the raw character buffer from a const string.
 314  *
 315  * @param str the string
 316  * @param data_return location to store returned data
 317  */
 318 void
 319 _dbus_string_get_const_data (const DBusString  *str,
 320                              const char       **data_return)
 321 {
 322   DBUS_CONST_STRING_PREAMBLE (str);
 323   _dbus_assert (data_return != NULL);
 324
 325   *data_return = real->str;
 326 }
 327
 328 /**
 329  * Gets a sub-portion of the raw character buffer from the
 330  * string. The "len" field is required simply for error
 331  * checking, to be sure you don't try to use more
 332  * string than exists. The nul termination of the
 333  * returned buffer remains at the end of the entire
 334  * string, not at start + len.
 335  *
 336  * @param str the string
 337  * @param data_return location to return the buffer
 338  * @param start byte offset to return
 339  * @param len length of segment to return
 340  */
 341 void
 342 _dbus_string_get_data_len (DBusString *str,
 343                            char      **data_return,
 344                            int         start,
 345                            int         len)
 346 {
 347   DBUS_STRING_PREAMBLE (str);
 348   _dbus_assert (data_return != NULL);
 349   _dbus_assert (start >= 0);
 350   _dbus_assert (len >= 0);
 351   _dbus_assert ((start + len) <= real->len);
 352
 353   *data_return = real->str + start;
 354 }
 355
 356 /**
 357  * const version of _dbus_string_get_data_len().
 358  *
 359  * @param str the string
 360  * @param data_return location to return the buffer
 361  * @param start byte offset to return
 362  * @param len length of segment to return
 363  */
 364 void
 365 _dbus_string_get_const_data_len (const DBusString  *str,
 366                                  const char       **data_return,
 367                                  int                start,
 368                                  int                len)
 369 {
 370   DBUS_CONST_STRING_PREAMBLE (str);
 371   _dbus_assert (data_return != NULL);
 372   _dbus_assert (start >= 0);
 373   _dbus_assert (len >= 0);
 374   _dbus_assert ((start + len) <= real->len);
 375
 376   *data_return = real->str + start;
 377 }
 378
 379 /**
 380  * Gets the byte at the given position.
 381  *
 382  * @param str the string
 383  * @param start the position
 384  * @returns the byte at that position
 385  */
 386 char
 387 _dbus_string_get_byte (const DBusString  *str,
 388                        int                start)
 389 {
 390   DBUS_CONST_STRING_PREAMBLE (str);
 391   _dbus_assert (start < real->len);
 392
 393   return real->str[start];
 394 }
 395
 396 /**
 397  * Like _dbus_string_get_data(), but removes the
 398  * gotten data from the original string. The caller
 399  * must free the data returned. This function may
 400  * fail due to lack of memory, and return #FALSE.
 401  *
 402  * @param str the string
 403  * @param data_return location to return the buffer
 404  * @returns #TRUE on success
 405  */
 406 dbus_bool_t
 407 _dbus_string_steal_data (DBusString        *str,
 408                          char             **data_return)
 409 {
 410   DBUS_STRING_PREAMBLE (str);
 411   _dbus_assert (data_return != NULL);
 412
 413   *data_return = real->str;
 414
 415   /* reset the string */
 416   if (!_dbus_string_init (str, real->max_length))
 417     {
 418       /* hrm, put it back then */
 419       real->str = *data_return;
 420       *data_return = NULL;
 421       return FALSE;
 422     }
 423
 424   return TRUE;
 425 }
 426
 427 /**
 428  * Like _dbus_string_get_data_len(), but removes the gotten data from
 429  * the original string. The caller must free the data returned. This
 430  * function may fail due to lack of memory, and return #FALSE.
 431  * The returned string is nul-terminated and has length len.
 432  *
 433  * @param str the string
 434  * @param data_return location to return the buffer
 435  * @param start the start of segment to steal
 436  * @param len the length of segment to steal
 437  * @returns #TRUE on success
 438  */
 439 dbus_bool_t
 440 _dbus_string_steal_data_len (DBusString        *str,
 441                              char             **data_return,
 442                              int                start,
 443                              int                len)
 444 {
 445   DBusString dest;
 446
 447   DBUS_STRING_PREAMBLE (str);
 448   _dbus_assert (data_return != NULL);
 449   _dbus_assert (start >= 0);
 450   _dbus_assert (len >= 0);
 451   _dbus_assert ((start + len) <= real->len);
 452
 453   if (!_dbus_string_init (&dest, real->max_length))
 454     return FALSE;
 455
 456   if (!_dbus_string_move_len (str, start, len, &dest, 0))
 457     {
 458       _dbus_string_free (&dest);
 459       return FALSE;
 460     }
 461
 462   if (!_dbus_string_steal_data (&dest, data_return))
 463     {
 464       _dbus_string_free (&dest);
 465       return FALSE;
 466     }
 467
 468   _dbus_string_free (&dest);
 469   return TRUE;
 470 }
 471
 472 /**
 473  * Gets the length of a string (not including nul termination).
 474  *
 475  * @returns the length.
 476  */
 477 int
 478 _dbus_string_get_length (const DBusString  *str)
 479 {
 480   DBUS_CONST_STRING_PREAMBLE (str);
 481
 482   return real->len;
 483 }
 484
 485 static dbus_bool_t
 486 set_length (DBusRealString *real,
 487             int             new_length)
 488 {
 489   /* Note, we are setting the length without nul termination */
 490
 491   /* exceeding max length is the same as failure to allocate memory */
 492   if (new_length > real->max_length)
 493     return FALSE;
 494
 495   while (new_length >= real->allocated)
 496     {
 497       int new_allocated;
 498       char *new_str;
 499
 500       new_allocated = 2 + real->allocated * 2;
 501       if (new_allocated < real->allocated)
 502         return FALSE; /* overflow */
 503
 504       new_str = dbus_realloc (real->str, new_allocated);
 505       if (new_str == NULL)
 506         return FALSE;
 507
 508       real->str = new_str;
 509       real->allocated = new_allocated;
 510
 511       ASSERT_8_BYTE_ALIGNED (real);
 512     }
 513
 514   real->len = new_length;
 515   real->str[real->len] = '\0';
 516
 517   return TRUE;
 518 }
 519
 520 /**
 521  * Makes a string longer by the given number of bytes.  Checks whether
 522  * adding additional_length to the current length would overflow an
 523  * integer, and checks for exceeding a string's max length.
 524  * The new bytes are not initialized, other than nul-terminating
 525  * the end of the string. The uninitialized bytes may contain
 526  * unexpected nul bytes or other junk.
 527  *
 528  * @param str a string
 529  * @param additional_length length to add to the string.
 530  * @returns #TRUE on success.
 531  */
 532 dbus_bool_t
 533 _dbus_string_lengthen (DBusString *str,
 534                        int         additional_length)
 535 {
 536   DBUS_STRING_PREAMBLE (str);
 537   _dbus_assert (additional_length >= 0);
 538
 539   if ((real->len + additional_length) < real->len)
 540     return FALSE; /* overflow */
 541
 542   return set_length (real,
 543                      real->len + additional_length);
 544 }
 545
 546 /**
 547  * Makes a string shorter by the given number of bytes.
 548  *
 549  * @param str a string
 550  * @param length_to_remove length to remove from the string.
 551  */
 552 void
 553 _dbus_string_shorten (DBusString *str,
 554                       int         length_to_remove)
 555 {
 556   DBUS_STRING_PREAMBLE (str);
 557   _dbus_assert (length_to_remove >= 0);
 558   _dbus_assert (length_to_remove <= real->len);
 559
 560   set_length (real,
 561               real->len - length_to_remove);
 562 }
 563
 564 /**
 565  * Sets the length of a string. Can be used to truncate or lengthen
 566  * the string. If the string is lengthened, the function may fail and
 567  * return #FALSE. Newly-added bytes are not initialized, as with
 568  * _dbus_string_lengthen().
 569  *
 570  * @param str a string
 571  * @param length new length of the string.
 572  * @returns #FALSE on failure.
 573  */
 574 dbus_bool_t
 575 _dbus_string_set_length (DBusString *str,
 576                          int         length)
 577 {
 578   DBUS_STRING_PREAMBLE (str);
 579   _dbus_assert (length >= 0);
 580
 581   return set_length (real, length);
 582 }
 583
 584 /**
 585  * Align the length of a string to a specific alignment (typically 4 or 8)
 586  * by appending nul bytes to the string.
 587  *
 588  * @param str a string
 589  * @param alignment the alignment
 590  * @returns #FALSE if no memory
 591  */
 592 dbus_bool_t
 593 _dbus_string_align_length (DBusString *str,
 594                            int         alignment)
 595 {
 596   int new_len;
 597   int delta;
 598   DBUS_STRING_PREAMBLE (str);
 599   _dbus_assert (alignment >= 1);
 600   _dbus_assert (alignment <= 16); /* arbitrary */
 601
 602   new_len = _DBUS_ALIGN_VALUE (real->len, alignment);
 603
 604   delta = new_len - real->len;
 605   _dbus_assert (delta >= 0);
 606
 607   if (delta == 0)
 608     return TRUE;
 609
 610   if (!set_length (real, new_len))
 611     return FALSE;
 612
 613   memset (real->str + (new_len - delta),
 614           '\0', delta);
 615
 616   return TRUE;
 617 }
 618
 619 static dbus_bool_t
 620 append (DBusRealString *real,
 621         const char     *buffer,
 622         int             buffer_len)
 623 {
 624   if (buffer_len == 0)
 625     return TRUE;
 626
 627   if (!_dbus_string_lengthen ((DBusString*)real, buffer_len))
 628     return FALSE;
 629
 630   memcpy (real->str + (real->len - buffer_len),
 631           buffer,
 632           buffer_len);
 633
 634   return TRUE;
 635 }
 636
 637 /**
 638  * Appends a nul-terminated C-style string to a DBusString.
 639  *
 640  * @param str the DBusString
 641  * @param buffer the nul-terminated characters to append
 642  * @returns #FALSE if not enough memory.
 643  */
 644 dbus_bool_t
 645 _dbus_string_append (DBusString *str,
 646                      const char *buffer)
 647 {
 648   int buffer_len;
 649
 650   DBUS_STRING_PREAMBLE (str);
 651   _dbus_assert (buffer != NULL);
 652
 653   buffer_len = strlen (buffer);
 654
 655   return append (real, buffer, buffer_len);
 656 }
 657
 658 /**
 659  * Appends block of bytes with the given length to a DBusString.
 660  *
 661  * @param str the DBusString
 662  * @param buffer the bytes to append
 663  * @param len the number of bytes to append
 664  * @returns #FALSE if not enough memory.
 665  */
 666 dbus_bool_t
 667 _dbus_string_append_len (DBusString *str,
 668                          const char *buffer,
 669                          int         len)
 670 {
 671   DBUS_STRING_PREAMBLE (str);
 672   _dbus_assert (buffer != NULL);
 673   _dbus_assert (len >= 0);
 674
 675   return append (real, buffer, len);
 676 }
 677
 678 /**
 679  * Appends a single byte to the string, returning #FALSE
 680  * if not enough memory.
 681  *
 682  * @param str the string
 683  * @param byte the byte to append
 684  * @returns #TRUE on success
 685  */
 686 dbus_bool_t
 687 _dbus_string_append_byte (DBusString    *str,
 688                           unsigned char  byte)
 689 {
 690   DBUS_STRING_PREAMBLE (str);
 691
 692   if (!set_length (real, real->len + 1))
 693     return FALSE;
 694
 695   real->str[real->len-1] = byte;
 696
 697   return TRUE;
 698 }
 699
 700 /**
 701  * Appends a single Unicode character, encoding the character
 702  * in UTF-8 format.
 703  *
 704  * @param str the string
 705  * @param ch the Unicode character
 706  */
 707 dbus_bool_t
 708 _dbus_string_append_unichar (DBusString    *str,
 709                              dbus_unichar_t ch)
 710 {
 711   int len;
 712   int first;
 713   int i;
 714   char *out;
 715
 716   DBUS_STRING_PREAMBLE (str);
 717
 718   /* this code is from GLib but is pretty standard I think */
 719
 720   len = 0;
 721
 722   if (ch < 0x80)
 723     {
 724       first = 0;
 725       len = 1;
 726     }
 727   else if (ch < 0x800)
 728     {
 729       first = 0xc0;
 730       len = 2;
 731     }
 732   else if (ch < 0x10000)
 733     {
 734       first = 0xe0;
 735       len = 3;
 736     }
 737    else if (ch < 0x200000)
 738     {
 739       first = 0xf0;
 740       len = 4;
 741     }
 742   else if (ch < 0x4000000)
 743     {
 744       first = 0xf8;
 745       len = 5;
 746     }
 747   else
 748     {
 749       first = 0xfc;
 750       len = 6;
 751     }
 752
 753   if (!set_length (real, real->len + len))
 754     return FALSE;
 755
 756   out = real->str + (real->len - len);
 757
 758   for (i = len - 1; i > 0; --i)
 759     {
 760       out[i] = (ch & 0x3f) | 0x80;
 761       ch >>= 6;
 762     }
 763   out[0] = ch | first;
 764
 765   return TRUE;
 766 }
 767
 768 static void
 769 delete (DBusRealString *real,
 770         int             start,
 771         int             len)
 772 {
 773   if (len == 0)
 774     return;
 775
 776   memmove (real->str + start, real->str + start + len, real->len - (start + len));
 777   real->len -= len;
 778   real->str[real->len] = '\0';
 779 }
 780
 781 /**
 782  * Deletes a segment of a DBusString with length len starting at
 783  * start. (Hint: to clear an entire string, setting length to 0
 784  * with _dbus_string_set_length() is easier.)
 785  *
 786  * @param str the DBusString
 787  * @param start where to start deleting
 788  * @param len the number of bytes to delete
 789  */
 790 void
 791 _dbus_string_delete (DBusString       *str,
 792                      int               start,
 793                      int               len)
 794 {
 795   DBUS_STRING_PREAMBLE (str);
 796   _dbus_assert (start >= 0);
 797   _dbus_assert (len >= 0);
 798   _dbus_assert ((start + len) <= real->len);
 799
 800   delete (real, start, len);
 801 }
 802
 803 static dbus_bool_t
 804 open_gap (int             len,
 805           DBusRealString *dest,
 806           int             insert_at)
 807 {
 808   if (len == 0)
 809     return TRUE;
 810
 811   if (!set_length (dest, dest->len + len))
 812     return FALSE;
 813
 814   memmove (dest->str + insert_at + len,
 815            dest->str + insert_at,
 816            dest->len - len - insert_at);
 817
 818   return TRUE;
 819 }
 820
 821 static dbus_bool_t
 822 copy (DBusRealString *source,
 823       int             start,
 824       int             len,
 825       DBusRealString *dest,
 826       int             insert_at)
 827 {
 828   if (len == 0)
 829     return TRUE;
 830
 831   if (!open_gap (len, dest, insert_at))
 832     return FALSE;
 833
 834   memcpy (dest->str + insert_at,
 835           source->str + start,
 836           len);
 837
 838   return TRUE;
 839 }
 840
 841 /**
 842  * Checks assertions for two strings we're copying a segment between,
 843  * and declares real_source/real_dest variables.
 844  *
 845  * @param source the source string
 846  * @param start the starting offset
 847  * @param dest the dest string
 848  * @param insert_at where the copied segment is inserted
 849  */
 850 #define DBUS_STRING_COPY_PREAMBLE(source, start, dest, insert_at)       \
 851   DBusRealString *real_source = (DBusRealString*) source;               \
 852   DBusRealString *real_dest = (DBusRealString*) dest;                   \
 853   _dbus_assert ((source) != (dest));                                    \
 854   DBUS_GENERIC_STRING_PREAMBLE (real_source);                           \
 855   DBUS_GENERIC_STRING_PREAMBLE (real_dest);                             \
 856   _dbus_assert (!real_source->constant);                                \
 857   _dbus_assert (!real_source->locked);                                  \
 858   _dbus_assert (!real_dest->constant);                                  \
 859   _dbus_assert (!real_dest->locked);                                    \
 860   _dbus_assert ((start) >= 0);                                          \
 861   _dbus_assert ((start) <= real_source->len);                           \
 862   _dbus_assert ((insert_at) >= 0);                                      \
 863   _dbus_assert ((insert_at) <= real_dest->len)
 864
 865 /**
 866  * Moves the end of one string into another string. Both strings
 867  * must be initialized, valid strings.
 868  *
 869  * @param source the source string
 870  * @param start where to chop off the source string
 871  * @param dest the destination string
 872  * @param insert_at where to move the chopped-off part of source string
 873  * @returns #FALSE if not enough memory
 874  */
 875 dbus_bool_t
 876 _dbus_string_move (DBusString       *source,
 877                    int               start,
 878                    DBusString       *dest,
 879                    int               insert_at)
 880 {
 881   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
 882
 883   if (!copy (real_source, start,
 884              real_source->len - start,
 885              real_dest,
 886              insert_at))
 887     return FALSE;
 888
 889   delete (real_source, start,
 890           real_source->len - start);
 891
 892   return TRUE;
 893 }
 894
 895 /**
 896  * Like _dbus_string_move(), but does not delete the section
 897  * of the source string that's copied to the dest string.
 898  *
 899  * @param source the source string
 900  * @param start where to start copying the source string
 901  * @param dest the destination string
 902  * @param insert_at where to place the copied part of source string
 903  * @returns #FALSE if not enough memory
 904  */
 905 dbus_bool_t
 906 _dbus_string_copy (const DBusString *source,
 907                    int               start,
 908                    DBusString       *dest,
 909                    int               insert_at)
 910 {
 911   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
 912
 913   return copy (real_source, start,
 914                real_source->len - start,
 915                real_dest,
 916                insert_at);
 917 }
 918
 919 /**
 920  * Like _dbus_string_move(), but can move a segment from
 921  * the middle of the source string.
 922  *
 923  * @param source the source string
 924  * @param start first byte of source string to move
 925  * @param len length of segment to move
 926  * @param dest the destination string
 927  * @param insert_at where to move the bytes from the source string
 928  * @returns #FALSE if not enough memory
 929  */
 930 dbus_bool_t
 931 _dbus_string_move_len (DBusString       *source,
 932                        int               start,
 933                        int               len,
 934                        DBusString       *dest,
 935                        int               insert_at)
 936
 937 {
 938   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
 939   _dbus_assert (len >= 0);
 940   _dbus_assert ((start + len) <= real_source->len);
 941
 942   if (!copy (real_source, start, len,
 943              real_dest,
 944              insert_at))
 945     return FALSE;
 946
 947   delete (real_source, start,
 948           len);
 949
 950   return TRUE;
 951 }
 952
 953 /**
 954  * Like _dbus_string_copy(), but can copy a segment from the middle of
 955  * the source string.
 956  *
 957  * @param source the source string
 958  * @param start where to start copying the source string
 959  * @param len length of segment to copy
 960  * @param dest the destination string
 961  * @param insert_at where to place the copied segment of source string
 962  * @returns #FALSE if not enough memory
 963  */
 964 dbus_bool_t
 965 _dbus_string_copy_len (const DBusString *source,
 966                        int               start,
 967                        int               len,
 968                        DBusString       *dest,
 969                        int               insert_at)
 970 {
 971   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
 972   _dbus_assert (len >= 0);
 973   _dbus_assert ((start + len) <= real_source->len);
 974
 975   return copy (real_source, start, len,
 976                real_dest,
 977                insert_at);
 978 }
 979
 980 /**
 981  * Replaces a segment of dest string with a segment of source string.
 982  *
 983  * @todo optimize the case where the two lengths are the same, and
 984  * avoid memmoving the data in the trailing part of the string twice.
 985  *
 986  * @param source the source string
 987  * @param start where to start copying the source string
 988  * @param len length of segment to copy
 989  * @param dest the destination string
 990  * @param replace_at start of segment of dest string to replace
 991  * @param replace_len length of segment of dest string to replace
 992  * @returns #FALSE if not enough memory
 993  *
 994  */
 995 dbus_bool_t
 996 _dbus_string_replace_len (const DBusString *source,
 997                           int               start,
 998                           int               len,
 999                           DBusString       *dest,
1000                           int               replace_at,
1001                           int               replace_len)
1002 {
1003   DBUS_STRING_COPY_PREAMBLE (source, start, dest, replace_at);
1004   _dbus_assert (len >= 0);
1005   _dbus_assert ((start + len) <= real_source->len);
1006   _dbus_assert (replace_at >= 0);
1007   _dbus_assert ((replace_at + replace_len) <= real_dest->len);
1008
1009   if (!copy (real_source, start, len,
1010              real_dest, replace_at))
1011     return FALSE;
1012
1013   delete (real_dest, replace_at + len, replace_len);
1014
1015   return TRUE;
1016 }
1017
1018 /* Unicode macros from GLib */
1019
1020 /** computes length and mask of a unicode character
1021  * @param Char the char
1022  * @param Mask the mask variable to assign to
1023  * @param Len the length variable to assign to
1024  */
1025 #define UTF8_COMPUTE(Char, Mask, Len)                                         \
1026   if (Char < 128)                                                             \
1027     {                                                                         \
1028       Len = 1;                                                                \
1029       Mask = 0x7f;                                                            \
1030     }                                                                         \
1031   else if ((Char & 0xe0) == 0xc0)                                             \
1032     {                                                                         \
1033       Len = 2;                                                                \
1034       Mask = 0x1f;                                                            \
1035     }                                                                         \
1036   else if ((Char & 0xf0) == 0xe0)                                             \
1037     {                                                                         \
1038       Len = 3;                                                                \
1039       Mask = 0x0f;                                                            \
1040     }                                                                         \
1041   else if ((Char & 0xf8) == 0xf0)                                             \
1042     {                                                                         \
1043       Len = 4;                                                                \
1044       Mask = 0x07;                                                            \
1045     }                                                                         \
1046   else if ((Char & 0xfc) == 0xf8)                                             \
1047     {                                                                         \
1048       Len = 5;                                                                \
1049       Mask = 0x03;                                                            \
1050     }                                                                         \
1051   else if ((Char & 0xfe) == 0xfc)                                             \
1052     {                                                                         \
1053       Len = 6;                                                                \
1054       Mask = 0x01;                                                            \
1055     }                                                                         \
1056   else                                                                        \
1057     Len = -1;
1058
1059 /**
1060  * computes length of a unicode character in UTF-8
1061  * @param Char the char
1062  */
1063 #define UTF8_LENGTH(Char)              \
1064   ((Char) < 0x80 ? 1 :                 \
1065    ((Char) < 0x800 ? 2 :               \
1066     ((Char) < 0x10000 ? 3 :            \
1067      ((Char) < 0x200000 ? 4 :          \
1068       ((Char) < 0x4000000 ? 5 : 6)))))
1069
1070 /**
1071  * Gets a UTF-8 value.
1072  *
1073  * @param Result variable for extracted unicode char.
1074  * @param Chars the bytes to decode
1075  * @param Count counter variable
1076  * @param Mask mask for this char
1077  * @param Len length for this char in bytes
1078  */
1079 #define UTF8_GET(Result, Chars, Count, Mask, Len)                             \
1080   (Result) = (Chars)[0] & (Mask);                                             \
1081   for ((Count) = 1; (Count) < (Len); ++(Count))                               \
1082     {                                                                         \
1083       if (((Chars)[(Count)] & 0xc0) != 0x80)                                  \
1084         {                                                                     \
1085           (Result) = -1;                                                      \
1086           break;                                                              \
1087         }                                                                     \
1088       (Result) <<= 6;                                                         \
1089       (Result) |= ((Chars)[(Count)] & 0x3f);                                  \
1090     }
1091
1092 /**
1093  * Check whether a unicode char is in a valid range.
1094  *
1095  * @param Char the character
1096  */
1097 #define UNICODE_VALID(Char)                   \
1098     ((Char) < 0x110000 &&                     \
1099      ((Char) < 0xD800 || (Char) >= 0xE000) && \
1100      (Char) != 0xFFFE && (Char) != 0xFFFF)
1101
1102 /**
1103  * Gets a unicode character from a UTF-8 string. Does no validation;
1104  * you must verify that the string is valid UTF-8 in advance and must
1105  * pass in the start of a character.
1106  *
1107  * @param str the string
1108  * @param start the start of the UTF-8 character.
1109  * @param ch_return location to return the character
1110  * @param end_return location to return the byte index of next character
1111  * @returns #TRUE on success, #FALSE otherwise.
1112  */
1113 void
1114 _dbus_string_get_unichar (const DBusString *str,
1115                           int               start,
1116                           dbus_unichar_t   *ch_return,
1117                           int              *end_return)
1118 {
1119   int i, mask, len;
1120   dbus_unichar_t result;
1121   unsigned char c;
1122   unsigned char *p;
1123   DBUS_CONST_STRING_PREAMBLE (str);
1124
1125   if (ch_return)
1126     *ch_return = 0;
1127   if (end_return)
1128     *end_return = real->len;
1129
1130   mask = 0;
1131   p = real->str + start;
1132   c = *p;
1133
1134   UTF8_COMPUTE (c, mask, len);
1135   if (len == -1)
1136     return;
1137   UTF8_GET (result, p, i, mask, len);
1138
1139   if (result == (dbus_unichar_t)-1)
1140     return;
1141
1142   if (ch_return)
1143     *ch_return = result;
1144   if (end_return)
1145     *end_return = start + len;
1146 }
1147
1148 /**
1149  * Finds the given substring in the string,
1150  * returning #TRUE and filling in the byte index
1151  * where the substring was found, if it was found.
1152  * Returns #FALSE if the substring wasn't found.
1153  * Sets *start to the length of the string if the substring
1154  * is not found.
1155  *
1156  * @param str the string
1157  * @param start where to start looking
1158  * @param substr the substring
1159  * @param found return location for where it was found, or #NULL
1160  * @returns #TRUE if found
1161  */
1162 dbus_bool_t
1163 _dbus_string_find (const DBusString *str,
1164                    int               start,
1165                    const char       *substr,
1166                    int              *found)
1167 {
1168   int i;
1169   DBUS_CONST_STRING_PREAMBLE (str);
1170   _dbus_assert (substr != NULL);
1171   _dbus_assert (start <= real->len);
1172
1173   /* we always "find" an empty string */
1174   if (*substr == '\0')
1175     {
1176       if (found)
1177         *found = 0;
1178       return TRUE;
1179     }
1180
1181   i = start;
1182   while (i < real->len)
1183     {
1184       if (real->str[i] == substr[0])
1185         {
1186           int j = i + 1;
1187
1188           while (j < real->len)
1189             {
1190               if (substr[j - i] == '\0')
1191                 break;
1192               else if (real->str[j] != substr[j - i])
1193                 break;
1194
1195               ++j;
1196             }
1197
1198           if (substr[j - i] == '\0')
1199             {
1200               if (found)
1201                 *found = i;
1202               return TRUE;
1203             }
1204         }
1205
1206       ++i;
1207     }
1208
1209   if (found)
1210     *found = real->len;
1211
1212   return FALSE;
1213 }
1214
1215 /**
1216  * Finds a blank (space or tab) in the string. Returns #TRUE
1217  * if found, #FALSE otherwise. If a blank is not found sets
1218  * *found to the length of the string.
1219  *
1220  * @param str the string
1221  * @param start byte index to start looking
1222  * @param found place to store the location of the first blank
1223  * @returns #TRUE if a blank was found
1224  */
1225 dbus_bool_t
1226 _dbus_string_find_blank (const DBusString *str,
1227                          int               start,
1228                          int              *found)
1229 {
1230   int i;
1231   DBUS_CONST_STRING_PREAMBLE (str);
1232   _dbus_assert (start <= real->len);
1233
1234   i = start;
1235   while (i < real->len)
1236     {
1237       if (real->str[i] == ' ' ||
1238           real->str[i] == '\t')
1239         {
1240           if (found)
1241             *found = i;
1242           return TRUE;
1243         }
1244
1245       ++i;
1246     }
1247
1248   if (found)
1249     *found = real->len;
1250
1251   return FALSE;
1252 }
1253
1254 /**
1255  * Skips blanks from start, storing the first non-blank in *end
1256  *
1257  * @param str the string
1258  * @param start where to start
1259  * @param end where to store the first non-blank byte index
1260  */
1261 void
1262 _dbus_string_skip_blank (const DBusString *str,
1263                          int               start,
1264                          int              *end)
1265 {
1266   int i;
1267   DBUS_CONST_STRING_PREAMBLE (str);
1268   _dbus_assert (start <= real->len);
1269
1270   i = start;
1271   while (i < real->len)
1272     {
1273       if (!(real->str[i] == ' ' ||
1274             real->str[i] == '\t'))
1275         break;
1276
1277       ++i;
1278     }
1279
1280   _dbus_assert (i == real->len || !(real->str[i] == ' ' ||
1281                                     real->str[i] == '\t'));
1282
1283   if (end)
1284     *end = i;
1285 }
1286
1287 /**
1288  * Tests two DBusString for equality.
1289  *
1290  * @param a first string
1291  * @param b second string
1292  * @returns #TRUE if equal
1293  */
1294 dbus_bool_t
1295 _dbus_string_equal (const DBusString *a,
1296                     const DBusString *b)
1297 {
1298   const unsigned char *ap;
1299   const unsigned char *bp;
1300   const unsigned char *a_end;
1301   const DBusRealString *real_a = (const DBusRealString*) a;
1302   const DBusRealString *real_b = (const DBusRealString*) b;
1303   DBUS_GENERIC_STRING_PREAMBLE (real_a);
1304   DBUS_GENERIC_STRING_PREAMBLE (real_b);
1305
1306   if (real_a->len != real_b->len)
1307     return FALSE;
1308
1309   ap = real_a->str;
1310   bp = real_b->str;
1311   a_end = real_a->str + real_a->len;
1312   while (ap != a_end)
1313     {
1314       if (*ap != *bp)
1315         return FALSE;
1316
1317       ++ap;
1318       ++bp;
1319     }
1320
1321   return TRUE;
1322 }
1323
1324 /**
1325  * Checks whether a string is equal to a C string.
1326  *
1327  * @param a the string
1328  * @param c_str the C string
1329  * @returns #TRUE if equal
1330  */
1331 dbus_bool_t
1332 _dbus_string_equal_c_str (const DBusString *a,
1333                           const char       *c_str)
1334 {
1335   const unsigned char *ap;
1336   const unsigned char *bp;
1337   const unsigned char *a_end;
1338   const DBusRealString *real_a = (const DBusRealString*) a;
1339   DBUS_GENERIC_STRING_PREAMBLE (real_a);
1340
1341   ap = real_a->str;
1342   bp = (const unsigned char*) c_str;
1343   a_end = real_a->str + real_a->len;
1344   while (ap != a_end && *bp)
1345     {
1346       if (*ap != *bp)
1347         return FALSE;
1348
1349       ++ap;
1350       ++bp;
1351     }
1352
1353   if (*ap && *bp == '\0')
1354     return FALSE;
1355   else if (ap == a_end && *bp)
1356     return FALSE;
1357
1358   return TRUE;
1359 }
1360
1361 static const signed char base64_table[] = {
1362   /* 0 */ 'A',
1363   /* 1 */ 'B',
1364   /* 2 */ 'C',
1365   /* 3 */ 'D',
1366   /* 4 */ 'E',
1367   /* 5 */ 'F',
1368   /* 6 */ 'G',
1369   /* 7 */ 'H',
1370   /* 8 */ 'I',
1371   /* 9 */ 'J',
1372   /* 10 */ 'K',
1373   /* 11 */ 'L',
1374   /* 12 */ 'M',
1375   /* 13 */ 'N',
1376   /* 14 */ 'O',
1377   /* 15 */ 'P',
1378   /* 16 */ 'Q',
1379   /* 17 */ 'R',
1380   /* 18 */ 'S',
1381   /* 19 */ 'T',
1382   /* 20 */ 'U',
1383   /* 21 */ 'V',
1384   /* 22 */ 'W',
1385   /* 23 */ 'X',
1386   /* 24 */ 'Y',
1387   /* 25 */ 'Z',
1388   /* 26 */ 'a',
1389   /* 27 */ 'b',
1390   /* 28 */ 'c',
1391   /* 29 */ 'd',
1392   /* 30 */ 'e',
1393   /* 31 */ 'f',
1394   /* 32 */ 'g',
1395   /* 33 */ 'h',
1396   /* 34 */ 'i',
1397   /* 35 */ 'j',
1398   /* 36 */ 'k',
1399   /* 37 */ 'l',
1400   /* 38 */ 'm',
1401   /* 39 */ 'n',
1402   /* 40 */ 'o',
1403   /* 41 */ 'p',
1404   /* 42 */ 'q',
1405   /* 43 */ 'r',
1406   /* 44 */ 's',
1407   /* 45 */ 't',
1408   /* 46 */ 'u',
1409   /* 47 */ 'v',
1410   /* 48 */ 'w',
1411   /* 49 */ 'x',
1412   /* 50 */ 'y',
1413   /* 51 */ 'z',
1414   /* 52 */ '0',
1415   /* 53 */ '1',
1416   /* 54 */ '2',
1417   /* 55 */ '3',
1418   /* 56 */ '4',
1419   /* 57 */ '5',
1420   /* 58 */ '6',
1421   /* 59 */ '7',
1422   /* 60 */ '8',
1423   /* 61 */ '9',
1424   /* 62 */ '+',
1425   /* 63 */ '/'
1426 };
1427
1428 /** The minimum char that's a valid char in Base64-encoded text */
1429 #define UNBASE64_MIN_CHAR (43)
1430 /** The maximum char that's a valid char in Base64-encoded text */
1431 #define UNBASE64_MAX_CHAR (122)
1432 /** Must subtract this from a char's integer value before offsetting
1433  * into unbase64_table
1434  */
1435 #define UNBASE64_TABLE_OFFSET UNBASE64_MIN_CHAR
1436 static const signed char unbase64_table[] = {
1437   /* 43 + */ 62,
1438   /* 44 , */ -1,
1439   /* 45 - */ -1,
1440   /* 46 . */ -1,
1441   /* 47 / */ 63,
1442   /* 48 0 */ 52,
1443   /* 49 1 */ 53,
1444   /* 50 2 */ 54,
1445   /* 51 3 */ 55,
1446   /* 52 4 */ 56,
1447   /* 53 5 */ 57,
1448   /* 54 6 */ 58,
1449   /* 55 7 */ 59,
1450   /* 56 8 */ 60,
1451   /* 57 9 */ 61,
1452   /* 58 : */ -1,
1453   /* 59 ; */ -1,
1454   /* 60 < */ -1,
1455   /* 61 = */ -1,
1456   /* 62 > */ -1,
1457   /* 63 ? */ -1,
1458   /* 64 @ */ -1,
1459   /* 65 A */ 0,
1460   /* 66 B */ 1,
1461   /* 67 C */ 2,
1462   /* 68 D */ 3,
1463   /* 69 E */ 4,
1464   /* 70 F */ 5,
1465   /* 71 G */ 6,
1466   /* 72 H */ 7,
1467   /* 73 I */ 8,
1468   /* 74 J */ 9,
1469   /* 75 K */ 10,
1470   /* 76 L */ 11,
1471   /* 77 M */ 12,
1472   /* 78 N */ 13,
1473   /* 79 O */ 14,
1474   /* 80 P */ 15,
1475   /* 81 Q */ 16,
1476   /* 82 R */ 17,
1477   /* 83 S */ 18,
1478   /* 84 T */ 19,
1479   /* 85 U */ 20,
1480   /* 86 V */ 21,
1481   /* 87 W */ 22,
1482   /* 88 X */ 23,
1483   /* 89 Y */ 24,
1484   /* 90 Z */ 25,
1485   /* 91 [ */ -1,
1486   /* 92 \ */ -1,
1487   /* 93 ] */ -1,
1488   /* 94 ^ */ -1,
1489   /* 95 _ */ -1,
1490   /* 96 ` */ -1,
1491   /* 97 a */ 26,
1492   /* 98 b */ 27,
1493   /* 99 c */ 28,
1494   /* 100 d */ 29,
1495   /* 101 e */ 30,
1496   /* 102 f */ 31,
1497   /* 103 g */ 32,
1498   /* 104 h */ 33,
1499   /* 105 i */ 34,
1500   /* 106 j */ 35,
1501   /* 107 k */ 36,
1502   /* 108 l */ 37,
1503   /* 109 m */ 38,
1504   /* 110 n */ 39,
1505   /* 111 o */ 40,
1506   /* 112 p */ 41,
1507   /* 113 q */ 42,
1508   /* 114 r */ 43,
1509   /* 115 s */ 44,
1510   /* 116 t */ 45,
1511   /* 117 u */ 46,
1512   /* 118 v */ 47,
1513   /* 119 w */ 48,
1514   /* 120 x */ 49,
1515   /* 121 y */ 50,
1516   /* 122 z */ 51
1517 };
1518
1519 /**
1520  * Encodes a string using Base64, as documented in RFC 2045.
1521  *
1522  * @param source the string to encode
1523  * @param start byte index to start encoding
1524  * @param dest string where encoded data should be placed
1525  * @param insert_at where to place encoded data
1526  * @returns #TRUE if encoding was successful, #FALSE if no memory etc.
1527  */
1528 dbus_bool_t
1529 _dbus_string_base64_encode (const DBusString *source,
1530                             int               start,
1531                             DBusString       *dest,
1532                             int               insert_at)
1533 {
1534   int source_len;
1535   int dest_len;
1536   const unsigned char *s;
1537   unsigned char *d;
1538   const unsigned char *triplet_end;
1539   const unsigned char *final_end;
1540   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
1541   _dbus_assert (source != dest);
1542
1543   /* For each 24 bits (3 bytes) of input, we have 4 chars of
1544    * output.
1545    */
1546   source_len = real_source->len - start;
1547   dest_len = (source_len / 3) * 4;
1548   if (source_len % 3 != 0)
1549     dest_len += 4;
1550
1551   if (source_len == 0)
1552     return TRUE;
1553
1554   if (!open_gap (dest_len, real_dest, insert_at))
1555     return FALSE;
1556
1557   d = real_dest->str + insert_at;
1558   s = real_source->str + start;
1559   final_end = real_source->str + (start + source_len);
1560   triplet_end = final_end - (source_len % 3);
1561   _dbus_assert (triplet_end <= final_end);
1562   _dbus_assert ((final_end - triplet_end) < 3);
1563
1564 #define ENCODE_64(v) (base64_table[ (unsigned char) (v) ])
1565 #define SIX_BITS_MASK (0x3f)
1566   _dbus_assert (SIX_BITS_MASK < _DBUS_N_ELEMENTS (base64_table));
1567
1568   while (s != triplet_end)
1569     {
1570       unsigned int triplet;
1571
1572       triplet = s[0] | (s[1] << 8) | (s[2] << 16);
1573
1574       /* Encode each 6 bits */
1575
1576       *d++ = ENCODE_64 (triplet >> 18);
1577       *d++ = ENCODE_64 ((triplet >> 12) & SIX_BITS_MASK);
1578       *d++ = ENCODE_64 ((triplet >> 6) & SIX_BITS_MASK);
1579       *d++ = ENCODE_64 (triplet & SIX_BITS_MASK);
1580
1581       s += 3;
1582     }
1583
1584   switch (final_end - triplet_end)
1585     {
1586     case 2:
1587       {
1588         unsigned int doublet;
1589
1590         doublet = s[0] | (s[1] << 8);
1591
1592         *d++ = ENCODE_64 (doublet >> 12);
1593         *d++ = ENCODE_64 ((doublet >> 6) & SIX_BITS_MASK);
1594         *d++ = ENCODE_64 (doublet & SIX_BITS_MASK);
1595         *d++ = '=';
1596       }
1597       break;
1598     case 1:
1599       {
1600         unsigned int singlet;
1601
1602         singlet = s[0];
1603
1604         *d++ = ENCODE_64 ((singlet >> 6) & SIX_BITS_MASK);
1605         *d++ = ENCODE_64 (singlet & SIX_BITS_MASK);
1606         *d++ = '=';
1607         *d++ = '=';
1608       }
1609       break;
1610     case 0:
1611       break;
1612     }
1613
1614   _dbus_assert (d == (real_dest->str + (insert_at + dest_len)));
1615
1616   return TRUE;
1617 }
1618
1619
1620 /**
1621  * Decodes a string from Base64, as documented in RFC 2045.
1622  *
1623  * @param source the string to decode
1624  * @param start byte index to start decode
1625  * @param dest string where decoded data should be placed
1626  * @param insert_at where to place decoded data
1627  * @returns #TRUE if decoding was successful, #FALSE if no memory etc.
1628  */
1629 dbus_bool_t
1630 _dbus_string_base64_decode (const DBusString *source,
1631                             int               start,
1632                             DBusString       *dest,
1633                             int               insert_at)
1634 {
1635   int source_len;
1636   const char *s;
1637   const char *end;
1638   DBusString result;
1639   unsigned int triplet = 0;
1640   int sextet_count;
1641   int pad_count;
1642   DBUS_STRING_COPY_PREAMBLE (source, start, dest, insert_at);
1643   _dbus_assert (source != dest);
1644
1645   source_len = real_source->len - start;
1646   s = real_source->str + start;
1647   end = real_source->str + source_len;
1648
1649   if (source_len == 0)
1650     return TRUE;
1651
1652   if (!_dbus_string_init (&result, _DBUS_INT_MAX))
1653     return FALSE;
1654
1655   pad_count = 0;
1656   sextet_count = 0;
1657   while (s != end)
1658     {
1659       /* The idea is to just skip anything that isn't
1660        * a base64 char - it's allowed to have whitespace,
1661        * newlines, etc. in here. We also ignore trailing
1662        * base64 chars, though that's suspicious.
1663        */
1664
1665       if (*s >= UNBASE64_MIN_CHAR &&
1666           *s <= UNBASE64_MAX_CHAR)
1667         {
1668           if (*s == '=')
1669             {
1670               /* '=' is padding, doesn't represent additional data
1671                * but does increment our count.
1672                */
1673               pad_count += 1;
1674               sextet_count += 1;
1675             }
1676           else
1677             {
1678               int val;
1679
1680               val = unbase64_table[(*s) - UNBASE64_TABLE_OFFSET];
1681
1682               if (val >= 0)
1683                 {
1684                   triplet <<= 6;
1685                   triplet |= (unsigned int) val;
1686                   sextet_count += 1;
1687                 }
1688             }
1689
1690           if (sextet_count == 4)
1691             {
1692               /* no pad = 3 bytes, 1 pad = 2 bytes, 2 pad = 1 byte */
1693
1694               _dbus_string_append_byte (&result,
1695                                         triplet & 0xff);
1696
1697               if (pad_count < 2)
1698                 _dbus_string_append_byte (&result,
1699                                           (triplet >> 8) & 0xff);
1700
1701               if (pad_count < 1)
1702                 _dbus_string_append_byte (&result,
1703                                           triplet >> 16);
1704
1705               sextet_count = 0;
1706               pad_count = 0;
1707               triplet = 0;
1708             }
1709         }
1710
1711       ++s;
1712     }
1713
1714   if (!_dbus_string_move (&result, 0, dest, insert_at))
1715     {
1716       _dbus_string_free (&result);
1717       return FALSE;
1718     }
1719
1720   _dbus_string_free (&result);
1721
1722   return TRUE;
1723 }
1724
1725 /**
1726  * Checks that the given range of the string
1727  * is valid ASCII. If the given range is not contained
1728  * in the string, returns #FALSE.
1729  *
1730  * @param str the string
1731  * @param start first byte index to check
1732  * @param len number of bytes to check
1733  * @returns #TRUE if the byte range exists and is all valid ASCII
1734  */
1735 dbus_bool_t
1736 _dbus_string_validate_ascii (const DBusString *str,
1737                              int               start,
1738                              int               len)
1739 {
1740   const unsigned char *s;
1741   const unsigned char *end;
1742   DBUS_CONST_STRING_PREAMBLE (str);
1743   _dbus_assert (start >= 0);
1744   _dbus_assert (len >= 0);
1745
1746   if ((start + len) > real->len)
1747     return FALSE;
1748
1749   s = real->str + start;
1750   end = s + len;
1751   while (s != end)
1752     {
1753       if (*s == '\0' ||
1754           ((*s & ~0x7f) != 0))
1755         return FALSE;
1756
1757       ++s;
1758     }
1759
1760   return TRUE;
1761 }
1762
1763 /** @} */
1764
1765 #ifdef DBUS_BUILD_TESTS
1766 #include "dbus-test.h"
1767 #include <stdio.h>
1768
1769 static void
1770 test_max_len (DBusString *str,
1771               int         max_len)
1772 {
1773   if (max_len > 0)
1774     {
1775       if (!_dbus_string_set_length (str, max_len - 1))
1776         _dbus_assert_not_reached ("setting len to one less than max should have worked");
1777     }
1778
1779   if (!_dbus_string_set_length (str, max_len))
1780     _dbus_assert_not_reached ("setting len to max len should have worked");
1781
1782   if (_dbus_string_set_length (str, max_len + 1))
1783     _dbus_assert_not_reached ("setting len to one more than max len should not have worked");
1784
1785   if (!_dbus_string_set_length (str, 0))
1786     _dbus_assert_not_reached ("setting len to zero should have worked");
1787 }
1788
1789 static void
1790 test_base64_roundtrip (const unsigned char *data,
1791                        int                  len)
1792 {
1793   DBusString orig;
1794   DBusString encoded;
1795   DBusString decoded;
1796
1797   if (len < 0)
1798     len = strlen (data);
1799
1800   if (!_dbus_string_init (&orig, _DBUS_INT_MAX))
1801     _dbus_assert_not_reached ("could not init string");
1802
1803   if (!_dbus_string_init (&encoded, _DBUS_INT_MAX))
1804     _dbus_assert_not_reached ("could not init string");
1805
1806   if (!_dbus_string_init (&decoded, _DBUS_INT_MAX))
1807     _dbus_assert_not_reached ("could not init string");
1808
1809   if (!_dbus_string_append_len (&orig, data, len))
1810     _dbus_assert_not_reached ("couldn't append orig data");
1811
1812   if (!_dbus_string_base64_encode (&orig, 0, &encoded, 0))
1813     _dbus_assert_not_reached ("could not encode");
1814
1815   if (!_dbus_string_base64_decode (&encoded, 0, &decoded, 0))
1816     _dbus_assert_not_reached ("could not decode");
1817
1818   if (!_dbus_string_equal (&orig, &decoded))
1819     {
1820       const char *s;
1821
1822       printf ("Original string %d bytes encoded %d bytes decoded %d bytes\n",
1823               _dbus_string_get_length (&orig),
1824               _dbus_string_get_length (&encoded),
1825               _dbus_string_get_length (&decoded));
1826       printf ("Original: %s\n", data);
1827       _dbus_string_get_const_data (&decoded, &s);
1828       printf ("Decoded: %s\n", s);
1829       _dbus_assert_not_reached ("original string not the same as string decoded from base64");
1830     }
1831
1832   _dbus_string_free (&orig);
1833   _dbus_string_free (&encoded);
1834   _dbus_string_free (&decoded);
1835 }
1836
1837 /**
1838  * @ingroup DBusStringInternals
1839  * Unit test for DBusString.
1840  *
1841  * @todo Need to write tests for _dbus_string_copy() and
1842  * _dbus_string_move() moving to/from each of start/middle/end of a
1843  * string. Also need tests for _dbus_string_move_len ()
1844  *
1845  * @returns #TRUE on success.
1846  */
1847 dbus_bool_t
1848 _dbus_string_test (void)
1849 {
1850   DBusString str;
1851   DBusString other;
1852   int i, end;
1853   long v;
1854   double d;
1855   int lens[] = { 0, 1, 2, 3, 4, 5, 10, 16, 17, 18, 25, 31, 32, 33, 34, 35, 63, 64, 65, 66, 67, 68, 69, 70, 71, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136 };
1856   char *s;
1857   dbus_unichar_t ch;
1858
1859   i = 0;
1860   while (i < _DBUS_N_ELEMENTS (lens))
1861     {
1862       if (!_dbus_string_init (&str, lens[i]))
1863         _dbus_assert_not_reached ("failed to init string");
1864
1865       test_max_len (&str, lens[i]);
1866       _dbus_string_free (&str);
1867
1868       ++i;
1869     }
1870
1871   /* Test shortening and setting length */
1872   i = 0;
1873   while (i < _DBUS_N_ELEMENTS (lens))
1874     {
1875       int j;
1876
1877       if (!_dbus_string_init (&str, lens[i]))
1878         _dbus_assert_not_reached ("failed to init string");
1879
1880       if (!_dbus_string_set_length (&str, lens[i]))
1881         _dbus_assert_not_reached ("failed to set string length");
1882
1883       j = lens[i];
1884       while (j > 0)
1885         {
1886           _dbus_assert (_dbus_string_get_length (&str) == j);
1887           if (j > 0)
1888             {
1889               _dbus_string_shorten (&str, 1);
1890               _dbus_assert (_dbus_string_get_length (&str) == (j - 1));
1891             }
1892           --j;
1893         }
1894
1895       _dbus_string_free (&str);
1896
1897       ++i;
1898     }
1899
1900   /* Test appending data */
1901   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
1902     _dbus_assert_not_reached ("failed to init string");
1903
1904   i = 0;
1905   while (i < 10)
1906     {
1907       if (!_dbus_string_append (&str, "a"))
1908         _dbus_assert_not_reached ("failed to append string to string\n");
1909
1910       _dbus_assert (_dbus_string_get_length (&str) == i * 2 + 1);
1911
1912       if (!_dbus_string_append_byte (&str, 'b'))
1913         _dbus_assert_not_reached ("failed to append byte to string\n");
1914
1915       _dbus_assert (_dbus_string_get_length (&str) == i * 2 + 2);
1916
1917       ++i;
1918     }
1919
1920   _dbus_string_free (&str);
1921
1922   /* Check steal_data */
1923
1924   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
1925     _dbus_assert_not_reached ("failed to init string");
1926
1927   if (!_dbus_string_append (&str, "Hello World"))
1928     _dbus_assert_not_reached ("could not append to string");
1929
1930   i = _dbus_string_get_length (&str);
1931
1932   if (!_dbus_string_steal_data (&str, &s))
1933     _dbus_assert_not_reached ("failed to steal data");
1934
1935   _dbus_assert (_dbus_string_get_length (&str) == 0);
1936   _dbus_assert (((int)strlen (s)) == i);
1937
1938   dbus_free (s);
1939
1940   /* Check move */
1941
1942   if (!_dbus_string_append (&str, "Hello World"))
1943     _dbus_assert_not_reached ("could not append to string");
1944
1945   i = _dbus_string_get_length (&str);
1946
1947   if (!_dbus_string_init (&other, _DBUS_INT_MAX))
1948     _dbus_assert_not_reached ("could not init string");
1949
1950   if (!_dbus_string_move (&str, 0, &other, 0))
1951     _dbus_assert_not_reached ("could not move");
1952
1953   _dbus_assert (_dbus_string_get_length (&str) == 0);
1954   _dbus_assert (_dbus_string_get_length (&other) == i);
1955
1956   if (!_dbus_string_append (&str, "Hello World"))
1957     _dbus_assert_not_reached ("could not append to string");
1958
1959   if (!_dbus_string_move (&str, 0, &other, _dbus_string_get_length (&other)))
1960     _dbus_assert_not_reached ("could not move");
1961
1962   _dbus_assert (_dbus_string_get_length (&str) == 0);
1963   _dbus_assert (_dbus_string_get_length (&other) == i * 2);
1964
1965     if (!_dbus_string_append (&str, "Hello World"))
1966     _dbus_assert_not_reached ("could not append to string");
1967
1968   if (!_dbus_string_move (&str, 0, &other, _dbus_string_get_length (&other) / 2))
1969     _dbus_assert_not_reached ("could not move");
1970
1971   _dbus_assert (_dbus_string_get_length (&str) == 0);
1972   _dbus_assert (_dbus_string_get_length (&other) == i * 3);
1973
1974   _dbus_string_free (&other);
1975
1976   /* Check copy */
1977
1978   if (!_dbus_string_append (&str, "Hello World"))
1979     _dbus_assert_not_reached ("could not append to string");
1980
1981   i = _dbus_string_get_length (&str);
1982
1983   if (!_dbus_string_init (&other, _DBUS_INT_MAX))
1984     _dbus_assert_not_reached ("could not init string");
1985
1986   if (!_dbus_string_copy (&str, 0, &other, 0))
1987     _dbus_assert_not_reached ("could not copy");
1988
1989   _dbus_assert (_dbus_string_get_length (&str) == i);
1990   _dbus_assert (_dbus_string_get_length (&other) == i);
1991
1992   if (!_dbus_string_copy (&str, 0, &other, _dbus_string_get_length (&other)))
1993     _dbus_assert_not_reached ("could not copy");
1994
1995   _dbus_assert (_dbus_string_get_length (&str) == i);
1996   _dbus_assert (_dbus_string_get_length (&other) == i * 2);
1997   _dbus_assert (_dbus_string_equal_c_str (&other,
1998                                           "Hello WorldHello World"));
1999
2000   if (!_dbus_string_copy (&str, 0, &other, _dbus_string_get_length (&other) / 2))
2001     _dbus_assert_not_reached ("could not copy");
2002
2003   _dbus_assert (_dbus_string_get_length (&str) == i);
2004   _dbus_assert (_dbus_string_get_length (&other) == i * 3);
2005   _dbus_assert (_dbus_string_equal_c_str (&other,
2006                                           "Hello WorldHello WorldHello World"));
2007
2008   _dbus_string_free (&str);
2009   _dbus_string_free (&other);
2010
2011   /* Check replace */
2012
2013   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
2014     _dbus_assert_not_reached ("failed to init string");
2015
2016   if (!_dbus_string_append (&str, "Hello World"))
2017     _dbus_assert_not_reached ("could not append to string");
2018
2019   i = _dbus_string_get_length (&str);
2020
2021   if (!_dbus_string_init (&other, _DBUS_INT_MAX))
2022     _dbus_assert_not_reached ("could not init string");
2023
2024   if (!_dbus_string_replace_len (&str, 0, _dbus_string_get_length (&str),
2025                                  &other, 0, _dbus_string_get_length (&other)))
2026     _dbus_assert_not_reached ("could not replace");
2027
2028   _dbus_assert (_dbus_string_get_length (&str) == i);
2029   _dbus_assert (_dbus_string_get_length (&other) == i);
2030   _dbus_assert (_dbus_string_equal_c_str (&other, "Hello World"));
2031
2032   if (!_dbus_string_replace_len (&str, 0, _dbus_string_get_length (&str),
2033                                  &other, 5, 1))
2034     _dbus_assert_not_reached ("could not replace center space");
2035
2036   _dbus_assert (_dbus_string_get_length (&str) == i);
2037   _dbus_assert (_dbus_string_get_length (&other) == i * 2 - 1);
2038   _dbus_assert (_dbus_string_equal_c_str (&other,
2039                                           "HelloHello WorldWorld"));
2040
2041
2042   if (!_dbus_string_replace_len (&str, 1, 1,
2043                                  &other,
2044                                  _dbus_string_get_length (&other) - 1,
2045                                  1))
2046     _dbus_assert_not_reached ("could not replace end character");
2047
2048   _dbus_assert (_dbus_string_get_length (&str) == i);
2049   _dbus_assert (_dbus_string_get_length (&other) == i * 2 - 1);
2050   _dbus_assert (_dbus_string_equal_c_str (&other,
2051                                           "HelloHello WorldWorle"));
2052
2053   _dbus_string_free (&str);
2054   _dbus_string_free (&other);
2055
2056   /* Check append/get unichar */
2057
2058   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
2059     _dbus_assert_not_reached ("failed to init string");
2060
2061   ch = 0;
2062   if (!_dbus_string_append_unichar (&str, 0xfffc))
2063     _dbus_assert_not_reached ("failed to append unichar");
2064
2065   _dbus_string_get_unichar (&str, 0, &ch, &i);
2066
2067   _dbus_assert (ch == 0xfffc);
2068   _dbus_assert (i == _dbus_string_get_length (&str));
2069
2070   _dbus_string_free (&str);
2071
2072   /* Check append/parse int/double */
2073
2074   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
2075     _dbus_assert_not_reached ("failed to init string");
2076
2077   if (!_dbus_string_append_int (&str, 27))
2078     _dbus_assert_not_reached ("failed to append int");
2079
2080   i = _dbus_string_get_length (&str);
2081
2082   if (!_dbus_string_parse_int (&str, 0, &v, &end))
2083     _dbus_assert_not_reached ("failed to parse int");
2084
2085   _dbus_assert (v == 27);
2086   _dbus_assert (end == i);
2087
2088   _dbus_string_free (&str);
2089
2090   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
2091     _dbus_assert_not_reached ("failed to init string");
2092
2093   if (!_dbus_string_append_double (&str, 50.3))
2094     _dbus_assert_not_reached ("failed to append float");
2095
2096   i = _dbus_string_get_length (&str);
2097
2098   if (!_dbus_string_parse_double (&str, 0, &d, &end))
2099     _dbus_assert_not_reached ("failed to parse float");
2100
2101   _dbus_assert (d > (50.3 - 1e-6) && d < (50.3 + 1e-6));
2102   _dbus_assert (end == i);
2103
2104   _dbus_string_free (&str);
2105
2106   /* Test find */
2107   if (!_dbus_string_init (&str, _DBUS_INT_MAX))
2108     _dbus_assert_not_reached ("failed to init string");
2109
2110   if (!_dbus_string_append (&str, "Hello"))
2111     _dbus_assert_not_reached ("couldn't append to string");
2112
2113   if (!_dbus_string_find (&str, 0, "He", &i))
2114     _dbus_assert_not_reached ("didn't find 'He'");
2115   _dbus_assert (i == 0);
2116
2117   if (!_dbus_string_find (&str, 0, "ello", &i))
2118     _dbus_assert_not_reached ("didn't find 'ello'");
2119   _dbus_assert (i == 1);
2120
2121   if (!_dbus_string_find (&str, 0, "lo", &i))
2122     _dbus_assert_not_reached ("didn't find 'lo'");
2123   _dbus_assert (i == 3);
2124
2125   if (!_dbus_string_find (&str, 2, "lo", &i))
2126     _dbus_assert_not_reached ("didn't find 'lo'");
2127   _dbus_assert (i == 3);
2128
2129   if (_dbus_string_find (&str, 4, "lo", &i))
2130     _dbus_assert_not_reached ("did find 'lo'");
2131
2132   if (!_dbus_string_find (&str, 0, "l", &i))
2133     _dbus_assert_not_reached ("didn't find 'l'");
2134   _dbus_assert (i == 2);
2135
2136   if (!_dbus_string_find (&str, 0, "H", &i))
2137     _dbus_assert_not_reached ("didn't find 'H'");
2138   _dbus_assert (i == 0);
2139
2140   if (!_dbus_string_find (&str, 0, "", &i))
2141     _dbus_assert_not_reached ("didn't find ''");
2142   _dbus_assert (i == 0);
2143
2144   if (_dbus_string_find (&str, 0, "Hello!", NULL))
2145     _dbus_assert_not_reached ("Did find 'Hello!'");
2146
2147   if (_dbus_string_find (&str, 0, "Oh, Hello", NULL))
2148     _dbus_assert_not_reached ("Did find 'Oh, Hello'");
2149
2150   if (_dbus_string_find (&str, 0, "ill", NULL))
2151     _dbus_assert_not_reached ("Did find 'ill'");
2152
2153   if (_dbus_string_find (&str, 0, "q", NULL))
2154     _dbus_assert_not_reached ("Did find 'q'");
2155
2156   _dbus_string_free (&str);
2157
2158   /* Base 64 */
2159   test_base64_roundtrip ("Hello this is a string\n", -1);
2160   test_base64_roundtrip ("Hello this is a string\n1", -1);
2161   test_base64_roundtrip ("Hello this is a string\n12", -1);
2162   test_base64_roundtrip ("Hello this is a string\n123", -1);
2163   test_base64_roundtrip ("Hello this is a string\n1234", -1);
2164   test_base64_roundtrip ("Hello this is a string\n12345", -1);
2165   test_base64_roundtrip ("", 0);
2166   test_base64_roundtrip ("1", 1);
2167   test_base64_roundtrip ("12", 2);
2168   test_base64_roundtrip ("123", 3);
2169   test_base64_roundtrip ("1234", 4);
2170   test_base64_roundtrip ("12345", 5);
2171   test_base64_roundtrip ("", 1);
2172   test_base64_roundtrip ("1", 2);
2173   test_base64_roundtrip ("12", 3);
2174   test_base64_roundtrip ("123", 4);
2175   test_base64_roundtrip ("1234", 5);
2176   test_base64_roundtrip ("12345", 6);
2177   {
2178     unsigned char buf[512];
2179     i = 0;
2180     while (i < _DBUS_N_ELEMENTS (buf))
2181       {
2182         buf[i] = i;
2183         ++i;
2184       }
2185     i = 0;
2186     while (i < _DBUS_N_ELEMENTS (buf))
2187       {
2188         test_base64_roundtrip (buf, i);
2189         ++i;
2190       }
2191   }
2192
2193   return TRUE;
2194 }
2195
2196 #endif /* DBUS_BUILD_TESTS */