libmapi/lzfu.c

   1 /*
   2    OpenChange MAPI implementation.
   3
   4    This work is based on libpst-0.5.2, and the author(s) of
   5    that code will also hold appropriate copyrights.
   6
   7    Copyright (C) Julien Kerihuel 2007-2008.
   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 3 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, see <http://www.gnu.org/licenses/>.
  21  */
  22
  23 #include "libmapi/libmapi.h"
  24 #include "libmapi/libmapi_private.h"
  25
  26 #include <ctype.h>
  27
  28 /**
  29    \file lzfu.c
  30
  31    \brief Compressed RTF related functions
  32 */
  33
  34
  35 #if BYTE_ORDER == BIG_ENDIAN
  36 #define LE32_CPU(x)                 \
  37   x = ((((x) & 0xff000000) >> 24) | \
  38        (((x) & 0x00ff0000) >> 8 ) | \
  39        (((x) & 0x0000ff00) << 8 ) | \
  40        (((x) & 0x000000ff) << 24));
  41 #define LE16_CPU(x)            \
  42   x = ((((x) & 0xff00) >> 8) | \
  43        (((x) & 0x00ff) << 8));
  44 #elif BYTE_ORDER == LITTLE_ENDIAN
  45 #define LE32_CPU(x) {}
  46 #define LE16_CPU(x) {}
  47 #else
  48 #error Byte order not supported
  49 #endif /* BYTE_ORDER */
  50
  51 #define LZFU_COMPRESSED         0x75465a4c
  52 #define LZFU_UNCOMPRESSED       0x414c454d
  53
  54 /* Initial directory */
  55 #define LZFU_INITDICT                                   \
  56   "{\\rtf1\\ansi\\mac\\deff0\\deftab720{\\fonttbl;}"    \
  57   "{\\f0\\fnil \\froman \\fswiss \\fmodern \\fscrip"    \
  58   "t \\fdecor MS Sans SerifSymbolArialTimes Ne"         \
  59   "w RomanCourier{\\colortbl\\red0\\green0\\blue0"      \
  60   "\r\n\\par \\pard\\plain\\f0\\fs20\\b\\i\\u\\tab"     \
  61   "\\tx"
  62
  63 /* initial length of dictionary */
  64 #define LZFU_INITLENGTH         207
  65
  66 #define LZFU_DICTLENGTH         0x1000
  67 #define LZFU_HEADERLENGTH       0x10
  68
  69 /* header for compressed rtf */
  70 typedef struct _lzfuheader {
  71         uint32_t        cbSize;
  72         uint32_t        cbRawSize;
  73         uint32_t        dwMagic;
  74         uint32_t        dwCRC;
  75 } lzfuheader;
  76
  77
  78 /**
  79    \details creates a DATA_BLOB in uncompressed Rich Text Format (RTF)
  80    from the compressed format used in the PR_RTF_COMPRESSED property
  81    opened in the stream.
  82
  83    \param obj_stream stream object with RTF stream content
  84    \param rtf the output blob with uncompressed content
  85
  86    \return MAPI_E_SUCCESS on success, otherwise MAPI error. Possible
  87    MAPI error codes are:
  88    - MAPI_E_NOT_INITIALIZED: MAPI subsystem has not been initialized
  89    - MAPI_E_INVALID_PARAMETER: obj_stream is not a valid pointer
  90    - MAPI_E_CORRUPT_DATA: a problem was encountered while
  91      decompressing the RTF compressed data
  92    - MAPI_E_CALL_FAILED: A network problem was encountered during the
  93    transaction
  94
  95    \note Developers may also call GetLastError() to retrieve the last
  96    MAPI error code.
  97
  98    \note rtf->data needs to be freed with MAPIFreeBuffer
  99
 100    \sa OpenStream
 101 */
 102 _PUBLIC_ enum MAPISTATUS WrapCompressedRTFStream(mapi_object_t *obj_stream,
 103                                                  DATA_BLOB *rtf)
 104 {
 105         enum MAPISTATUS         retval;
 106         struct mapi_context     *mapi_ctx;
 107         struct mapi_session     *session;
 108         TALLOC_CTX              *mem_ctx;
 109         uint32_t                in_size;
 110         uint8_t                 *rtfcomp;
 111         uint16_t                read_size;
 112         unsigned char           buf[0x1000];
 113
 114         /* sanity check and init */
 115         OPENCHANGE_RETVAL_IF(!obj_stream, MAPI_E_INVALID_PARAMETER, NULL);
 116
 117         session = mapi_object_get_session(obj_stream);
 118         OPENCHANGE_RETVAL_IF(!session, MAPI_E_NOT_INITIALIZED, NULL);
 119
 120         mapi_ctx = session->mapi_ctx;
 121         OPENCHANGE_RETVAL_IF(!mapi_ctx, MAPI_E_NOT_INITIALIZED, NULL);
 122
 123         mem_ctx = mapi_ctx->mem_ctx;
 124
 125         /* Read the stream pointed by obj_stream */
 126         read_size = 0;
 127         in_size = 0;
 128         rtfcomp = talloc_zero(mem_ctx, uint8_t);
 129         do {
 130                 retval = ReadStream(obj_stream, buf, 0x1000, &read_size);
 131                 OPENCHANGE_RETVAL_IF(retval, GetLastError(), rtf->data);
 132                 if (read_size) {
 133                         rtfcomp = talloc_realloc(mem_ctx, rtfcomp, uint8_t,
 134                                                    in_size + read_size);
 135                         memcpy(&(rtfcomp[in_size]), buf, read_size);
 136                         in_size += read_size;
 137                 }
 138         } while (read_size);
 139
 140         return uncompress_rtf(mem_ctx, rtfcomp, in_size, rtf);
 141 }
 142
 143 typedef struct _decompression_state {
 144         uint8_t*        dict;
 145         uint32_t        dict_writeoffset;
 146         uint8_t*        compressed_data;
 147         uint32_t        in_size;
 148         uint32_t        in_pos;
 149 } decompression_state;
 150
 151 /**
 152   Initialise the decompression_state
 153
 154   \param mem_ctx the memory context to allocate the decompression state on
 155   \param dict the resulting decompression_state
 156 */
 157 static void initialise_decompression_state(TALLOC_CTX *mem_ctx, uint8_t *compressed_data,
 158                                            uint32_t in_size, decompression_state *state)
 159 {
 160         state->dict = talloc_array(mem_ctx, uint8_t, LZFU_DICTLENGTH);
 161
 162         memcpy(state->dict, LZFU_INITDICT, LZFU_INITLENGTH);
 163         state->dict_writeoffset = LZFU_INITLENGTH;
 164
 165         state->compressed_data = compressed_data;
 166         state->in_size = in_size;
 167         state->in_pos = LZFU_HEADERLENGTH;
 168 }
 169
 170 static void cleanup_decompression_state(decompression_state *state)
 171 {
 172         talloc_free(state->dict);
 173 }
 174
 175 typedef struct _output_state {
 176         uint32_t        out_size;
 177         uint32_t        out_pos;
 178         DATA_BLOB       *output_blob;
 179 } output_state;
 180
 181 static void initialise_output_state(TALLOC_CTX *mem_ctx, output_state *state, uint32_t rawSize, DATA_BLOB *output_blob)
 182 {
 183         state->out_pos = 0;
 184         state->out_size = rawSize + LZFU_HEADERLENGTH + 4;
 185         output_blob->data = talloc_size(mem_ctx, state->out_size);
 186         output_blob->length = 0;
 187         state->output_blob = output_blob;
 188 }
 189
 190 static void parse_header(uint8_t *header_data, lzfuheader *header)
 191 {
 192         memcpy(header, header_data, sizeof(*header));
 193         LE32_CPU(header->cbSize);
 194         LE32_CPU(header->cbRawSize);
 195         LE32_CPU(header->dwMagic);
 196         LE32_CPU(header->dwCRC);
 197
 198         DEBUG(2, ("COMPSIZE = 0x%x\n", header->cbSize));
 199         DEBUG(2, ("RAWSIZE = 0x%x\n", header->cbRawSize));
 200         DEBUG(2, ("COMPTYPE = 0x%08x\n", header->dwMagic)); // TODO: make this look like MS-OXRTFCP examples
 201         DEBUG(2, ("CRC = 0x%08x\n", header->dwCRC));
 202 }
 203
 204 static enum MAPISTATUS verify_header(uint8_t *header_data, uint32_t in_size, lzfuheader *header)
 205 {
 206         parse_header(header_data, header);
 207
 208         if (header->cbSize != in_size - 4) {
 209                 DEBUG(0, ("in_size mismatch:%u\n", in_size));
 210                 OPENCHANGE_RETVAL_ERR(MAPI_E_CORRUPT_DATA, NULL);
 211         }
 212
 213         if ((header->dwMagic != LZFU_COMPRESSED) && (header->dwMagic != LZFU_UNCOMPRESSED)) {
 214                 DEBUG(0, ("bad magic: 0x%x\n", header->dwMagic));
 215                 OPENCHANGE_RETVAL_ERR(MAPI_E_CORRUPT_DATA, NULL);
 216         }
 217
 218         return MAPI_E_SUCCESS;
 219 }
 220
 221 static uint8_t get_next_byte(decompression_state *state)
 222 {
 223         if (state->in_pos > state->in_size) {
 224                 return 0;
 225         }
 226         uint8_t next_byte = state->compressed_data[state->in_pos];
 227         state->in_pos += 1;
 228         return next_byte;
 229 }
 230
 231 static uint8_t get_next_control(decompression_state *state)
 232 {
 233         uint8_t c = get_next_byte(state);
 234         DEBUG(3, ("control: 0x%02x\n", c));
 235         return c;
 236 }
 237
 238 static uint8_t get_next_literal(decompression_state *state)
 239 {
 240         uint8_t c = get_next_byte(state);
 241         if (isprint(c)) {
 242                 DEBUG(3, ("literal %c\n", c));
 243         } else {
 244                 DEBUG(3, ("literal 0x%02x\n", c));
 245         }
 246         return c;
 247 }
 248
 249 typedef struct _dictionaryref {
 250         uint8_t         length;
 251         uint16_t         offset;
 252 } dictionaryref;
 253
 254 static dictionaryref get_next_dictionary_reference(decompression_state *state)
 255 {
 256         dictionaryref reference;
 257         uint8_t highbyte = get_next_byte(state);
 258         uint8_t lowbyte = get_next_byte(state);
 259         reference.length = lowbyte & 0x0F; /* low 4 bits are length */
 260         reference.length += 2; /* stored as two less than actual length */
 261         reference.offset = ((highbyte << 8) + lowbyte);
 262         reference.offset &= 0xFFF0; /* high 12 bits are offset */
 263         reference.offset >>= 4; /* shift the offset down */
 264         return reference;
 265 }
 266
 267 static void append_to_dictionary(decompression_state *state, char c)
 268 {
 269         state->dict[state->dict_writeoffset] = c;
 270         state->dict_writeoffset = (state->dict_writeoffset + 1) % LZFU_DICTLENGTH;
 271 }
 272
 273 static void append_to_output(output_state *output, char c)
 274 {
 275         output->output_blob->data[output->out_pos] = c;
 276         output->out_pos += 1;
 277         output->output_blob->length += 1;
 278 }
 279
 280 static char get_dictionary_entry(decompression_state *state, uint32_t index)
 281 {
 282         char c = state->dict[index % LZFU_DICTLENGTH];
 283         if (isprint(c)) {
 284                 DEBUG(3, ("dict entry %i: %c\n", index, c));
 285         } else {
 286                 DEBUG(3, ("dict entry 0x%04x: 0x%02x\n", index, c));
 287         }
 288         return c;
 289 }
 290
 291 static bool output_would_overflow(output_state *output)
 292 {
 293         bool would_overflow = (output->out_pos > output->out_size);
 294         if (would_overflow) {
 295                 DEBUG(0, (" overrun on out_pos: %u > %u\n", output->out_pos, output->out_size));
 296                 DEBUG(0, (" overrun data: %s\n", output->output_blob->data));
 297         }
 298         return would_overflow;
 299 }
 300
 301 static bool input_would_overflow(decompression_state *state)
 302 {
 303         bool would_overflow = (state->in_pos > state->in_size);
 304         if (would_overflow) {
 305                 DEBUG(0, ("input overrun at in_pos: %i (of %i)\n", state->in_pos, state->in_size));
 306         }
 307         return would_overflow;
 308 }
 309
 310 _PUBLIC_ enum MAPISTATUS uncompress_rtf(TALLOC_CTX *mem_ctx,
 311                                          uint8_t *rtfcomp, uint32_t in_size,
 312                                          DATA_BLOB *rtf)
 313 {
 314         lzfuheader              lzfuhdr;
 315         decompression_state     state;
 316         uint8_t                 bitmask_pos;
 317         output_state            output;
 318
 319         enum MAPISTATUS         retval;
 320
 321         if (in_size < sizeof(lzfuhdr)+1) {
 322                 OPENCHANGE_RETVAL_ERR(MAPI_E_CORRUPT_DATA, NULL);
 323         }
 324
 325         initialise_decompression_state(mem_ctx, rtfcomp, in_size, &state);
 326
 327         retval = verify_header(rtfcomp, state.in_size, &lzfuhdr);
 328         if (retval != MAPI_E_SUCCESS) {
 329                 cleanup_decompression_state(&state);
 330                 return retval;
 331         }
 332
 333         if (lzfuhdr.dwMagic == LZFU_UNCOMPRESSED) {
 334                 // TODO: handle uncompressed case
 335         }
 336
 337         initialise_output_state(mem_ctx, &output, lzfuhdr.cbRawSize, rtf);
 338
 339         while ((state.in_pos + 1) < state.in_size) {
 340                 uint8_t control = get_next_control(&state);
 341                 for(bitmask_pos = 0; bitmask_pos < 8; ++bitmask_pos) {
 342                         if (control & ( 1 << bitmask_pos)) { /* its a dictionary reference */
 343                                 dictionaryref dictref;
 344                                 int i;
 345                                 dictref = get_next_dictionary_reference(&state);
 346                                 if (dictref.offset == state.dict_writeoffset) {
 347                                         DEBUG(4, ("matching offset - done\n"));
 348                                         append_to_output(&output, '\0');
 349                                         cleanup_decompression_state(&state);
 350                                         return MAPI_E_SUCCESS;
 351                                 }
 352                                 for (i = 0; i < dictref.length; ++i) {
 353                                         if (output_would_overflow(&output)) {
 354                                                 cleanup_decompression_state(&state);
 355                                                 return MAPI_E_CORRUPT_DATA;
 356                                         }
 357                                         char c = get_dictionary_entry(&state, (dictref.offset + i));
 358                                         append_to_output(&output, c);
 359                                         append_to_dictionary(&state, c);
 360                                 }
 361                         } else { /* its a literal */
 362                                 if ( output_would_overflow(&output) || input_would_overflow(&state) ) {
 363                                         cleanup_decompression_state(&state);
 364                                         talloc_free(rtf->data);
 365                                         return MAPI_E_CORRUPT_DATA;
 366                                 }
 367                                 char c = get_next_literal(&state);
 368                                 append_to_output(&output, c);
 369                                 append_to_dictionary(&state, c);
 370                         }
 371                 }
 372         }
 373
 374         cleanup_decompression_state(&state);
 375
 376         OPENCHANGE_RETVAL_ERR(MAPI_E_SUCCESS, NULL);
 377 }
 378
 379 static uint32_t CRCTable[] = {
 380 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
 381 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
 382 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 383 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
 384 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 385 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 386 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
 387 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
 388 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 389 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 390 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
 391 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 392 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
 393 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 394 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 395 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
 396 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
 397 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 398 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
 399 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 400 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 401 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 402 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 403 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 404 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 405 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 406 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 407 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 408 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 409 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 410 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 411 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 412 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 413 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 414 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 415 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 416 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 417 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 418 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 419 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 420 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 421 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 422 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 423 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 424 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 425 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 426 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 427 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 428 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 429 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 430 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 431 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 432 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 433 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 434 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 435 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 436 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 437 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 438 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 439 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 440 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 441 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 442 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 443 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 444 };
 445
 446 uint32_t calculateCRC(uint8_t *input, uint32_t offset, uint32_t length)
 447 {
 448         uint32_t crc = 0;
 449         uint32_t i;
 450         for (i = offset; i < offset+length; ++i) {
 451                 DEBUG(5, ("input at %i: 0x%02x\n", i, input[i]));
 452                 uint8_t table_position = (crc ^ input[i]) & 0xFF;
 453                 DEBUG(5, ("table_position: 0x%02x\n", table_position));
 454                 uint32_t intermediateValue = crc >> 8;
 455                 DEBUG(5, ("intermediateValue: 0x%08x\n", intermediateValue));
 456                 crc = CRCTable[table_position] ^ intermediateValue;
 457                 DEBUG(5, ("tableValue: 0x%08x\n", CRCTable[table_position]));
 458                 DEBUG(5, ("crc: 0x%08x\n", crc));
 459         }
 460         return crc;
 461 }
 462 #define MIN(a,b) ((a) < (b) ? (a) : (b))
 463
 464 static size_t longest_match(const char *rtf, const size_t rtf_size, size_t input_idx, uint8_t *dict, size_t *dict_write_idx, size_t *dict_match_offset, size_t *dict_match_length)
 465 {
 466         size_t best_match_length = 0;
 467         size_t dict_iterator;
 468         for (dict_iterator = 0; dict_iterator < MIN(*dict_write_idx, LZFU_DICTLENGTH); ++dict_iterator) {
 469                 size_t match_length_from_this_pos = 0;
 470                 while ((rtf[input_idx + match_length_from_this_pos] == dict[dict_iterator + match_length_from_this_pos]) &&
 471                        ((dict_iterator + match_length_from_this_pos) < ((*dict_write_idx) % LZFU_DICTLENGTH)) && /* does this line need to have % LZFU_DICTLENGTH? */
 472                        ((input_idx + match_length_from_this_pos) < rtf_size) &&
 473                        (match_length_from_this_pos < 17)) {
 474                         match_length_from_this_pos += 1;
 475                         if (match_length_from_this_pos > best_match_length) {
 476                                 best_match_length = match_length_from_this_pos;
 477                                 dict[(*dict_write_idx) % LZFU_DICTLENGTH] = rtf[input_idx + match_length_from_this_pos - 1];
 478                                 *dict_write_idx += 1;
 479                                 *dict_match_offset = dict_iterator;
 480                         }
 481                 }
 482         }
 483         *dict_match_length = best_match_length;
 484         return best_match_length;
 485 }
 486
 487 _PUBLIC_ enum MAPISTATUS compress_rtf(TALLOC_CTX *mem_ctx, const char *rtf, const size_t rtf_size,
 488                                       uint8_t **rtfcomp, size_t *rtfcomp_size)
 489 {
 490         size_t                  input_idx = 0;
 491         lzfuheader              header;
 492         uint8_t                 *dict;
 493         size_t                  output_idx = 0;
 494         size_t                  control_byte_idx = 0;
 495         uint8_t                 control_bit = 0x01;
 496         size_t                  dict_write_idx = 0;
 497
 498         /* as an upper bound, assume that the output is no larger than 9/8 of the input size, plus the header size */
 499         *rtfcomp = talloc_size(mem_ctx, 9 * rtf_size / 8 + sizeof(lzfuheader));
 500         control_byte_idx = sizeof(lzfuheader);
 501         (*rtfcomp)[control_byte_idx] = 0x00;
 502         output_idx = control_byte_idx + 1;
 503
 504         /* allocate and initialise the dictionary */
 505         dict = talloc_zero_array(mem_ctx, uint8_t, LZFU_DICTLENGTH);
 506         memcpy(dict, LZFU_INITDICT, LZFU_INITLENGTH);
 507         dict_write_idx = LZFU_INITLENGTH;
 508
 509         while (input_idx < rtf_size) {
 510                 size_t dict_match_length = 0;
 511                 size_t dict_match_offset = 0;
 512                 DEBUG(4, ("compressing byte %zi of %zi\n", input_idx, rtf_size));
 513                 if (longest_match(rtf, rtf_size, input_idx, dict, &dict_write_idx, &dict_match_offset, &dict_match_length) > 1) {
 514                         uint16_t dict_ref = dict_match_offset << 4;
 515                         dict_ref += (dict_match_length - 2);
 516                         input_idx += dict_match_length;
 517                         (*rtfcomp)[control_byte_idx] |= control_bit;
 518                         /* append dictionary reference to output */
 519                         (*rtfcomp)[output_idx] = (dict_ref & 0xFF00) >> 8;
 520                         output_idx += 1;
 521                         (*rtfcomp)[output_idx] = (dict_ref & 0xFF);
 522                         output_idx += 1;
 523                 } else {
 524                         if (dict_match_length == 0) {
 525                                 /* we haven't written a literal to the dict yet */
 526                                 dict[dict_write_idx % LZFU_DICTLENGTH] = rtf[input_idx];
 527                                 dict_write_idx += 1;
 528                         }
 529                         /* append to output, and increment the output position */
 530                         (*rtfcomp)[output_idx] = rtf[input_idx];
 531                         output_idx += 1;
 532                         DEBUG(5, ("new output_idx = 0x%08zx (for char value 0x%02x)\n", output_idx, rtf[input_idx]));
 533                         /* increment the input position */
 534                         input_idx += 1;
 535                 }
 536                 if (control_bit == 0x80) {
 537                         control_bit = 0x01;
 538                         control_byte_idx = output_idx;
 539                         (*rtfcomp)[control_byte_idx] = 0x00;
 540                         output_idx = control_byte_idx + 1;
 541                         DEBUG(5, ("new output_idx cb = 0x%08zx\n", output_idx));
 542                 } else {
 543                         control_bit = control_bit << 1;
 544                 }
 545         }
 546         {
 547                 /* append final marker dictionary reference to output */
 548                 uint16_t dict_ref = (dict_write_idx % LZFU_DICTLENGTH) << 4;
 549                 // printf("dict ref: 0x%04x at 0x%08zx\n", dict_ref, output_idx);
 550                 (*rtfcomp)[control_byte_idx] |= control_bit;
 551                 // printf("dict ref hi: 0x%02x\n", (dict_ref & 0xFF00) >> 8);
 552                 (*rtfcomp)[output_idx] = (dict_ref & 0xFF00) >> 8;
 553                 output_idx += 1;
 554                 // printf("dict ref lo: 0x%02x\n", dict_ref & 0xFF);
 555                 (*rtfcomp)[output_idx] = (dict_ref & 0xFF);
 556                 output_idx += 1;
 557         }
 558
 559         header.cbSize = output_idx - sizeof(lzfuheader) + 12;
 560         header.cbRawSize = rtf_size;
 561         header.dwMagic = LZFU_COMPRESSED;
 562         header.dwCRC = calculateCRC(*rtfcomp, sizeof(lzfuheader), output_idx - sizeof(lzfuheader));
 563         memcpy(*rtfcomp, &header, sizeof(lzfuheader));
 564         *rtfcomp_size = output_idx;
 565         *rtfcomp = talloc_realloc_size(mem_ctx, *rtfcomp, *rtfcomp_size);
 566
 567         return MAPI_E_SUCCESS;
 568 }