release/src/router/ntfs-3g/libntfs-3g/compress.c

   1 /**
   2  * compress.c - Compressed attribute handling code.  Originated from the Linux-NTFS
   3  *              project.
   4  *
   5  * Copyright (c) 2004-2005 Anton Altaparmakov
   6  * Copyright (c) 2004-2006 Szabolcs Szakacsits
   7  * Copyright (c)      2005 Yura Pakhuchiy
   8  * Copyright (c) 2009-2011 Jean-Pierre Andre
   9  *
  10  * This program/include file is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU General Public License as published
  12  * by the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program/include file is distributed in the hope that it will be
  16  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  17  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program (in the main directory of the NTFS-3G
  22  * distribution in the file COPYING); if not, write to the Free Software
  23  * Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24  *
  25  * A part of the compression algorithm is based on lzhuf.c whose header
  26  * describes the roles of the original authors (with no apparent copyright
  27  * notice, and according to http://home.earthlink.net/~neilbawd/pall.html
  28  * this was put into public domain in 1988 by Haruhiko OKUMURA).
  29  *
  30  * LZHUF.C English version 1.0
  31  * Based on Japanese version 29-NOV-1988
  32  * LZSS coded by Haruhiko OKUMURA
  33  * Adaptive Huffman Coding coded by Haruyasu YOSHIZAKI
  34  * Edited and translated to English by Kenji RIKITAKE
  35  */
  36
  37 #ifdef HAVE_CONFIG_H
  38 #include "config.h"
  39 #endif
  40
  41 #ifdef HAVE_STDIO_H
  42 #include <stdio.h>
  43 #endif
  44 #ifdef HAVE_STRING_H
  45 #include <string.h>
  46 #endif
  47 #ifdef HAVE_STDLIB_H
  48 #include <stdlib.h>
  49 #endif
  50 #ifdef HAVE_ERRNO_H
  51 #include <errno.h>
  52 #endif
  53
  54 #include "attrib.h"
  55 #include "debug.h"
  56 #include "volume.h"
  57 #include "types.h"
  58 #include "layout.h"
  59 #include "runlist.h"
  60 #include "compress.h"
  61 #include "lcnalloc.h"
  62 #include "logging.h"
  63 #include "misc.h"
  64
  65 #undef le16_to_cpup
  66 /* the standard le16_to_cpup() crashes for unaligned data on some processors */
  67 #define le16_to_cpup(p) (*(u8*)(p) + (((u8*)(p))[1] << 8))
  68
  69 /**
  70  * enum ntfs_compression_constants - constants used in the compression code
  71  */
  72 typedef enum {
  73         /* Token types and access mask. */
  74         NTFS_SYMBOL_TOKEN       =       0,
  75         NTFS_PHRASE_TOKEN       =       1,
  76         NTFS_TOKEN_MASK         =       1,
  77
  78         /* Compression sub-block constants. */
  79         NTFS_SB_SIZE_MASK       =       0x0fff,
  80         NTFS_SB_SIZE            =       0x1000,
  81         NTFS_SB_IS_COMPRESSED   =       0x8000,
  82 } ntfs_compression_constants;
  83
  84 struct COMPRESS_CONTEXT {
  85         const unsigned char *inbuf;
  86         int bufsize;
  87         int size;
  88         int rel;
  89         int mxsz;
  90         s16 head[256];
  91         s16 lson[NTFS_SB_SIZE];
  92         s16 rson[NTFS_SB_SIZE];
  93 } ;
  94
  95 /*
  96  *              Search for the longest sequence matching current position
  97  *
  98  *      A binary tree is maintained to locate all previously met sequences,
  99  *      and this function has to be called for all of them.
 100  *
 101  *      This function is heavily used, it has to be optimized carefully
 102  *
 103  *      Returns the size of the longest match,
 104  *              zero if no match is found.
 105  */
 106
 107 static int ntfs_best_match(struct COMPRESS_CONTEXT *pctx, int i)
 108 {
 109         s16 *prev;
 110         int node;
 111         register long j;
 112         long maxpos;
 113         long startj;
 114         long bestj;
 115         int bufsize;
 116         int bestnode;
 117         register const unsigned char *p1,*p2;
 118
 119         p1 = pctx->inbuf;
 120         node = pctx->head[p1[i] & 255];
 121         if (node >= 0) {
 122                 /* search the best match at current position */
 123                 bestnode = node;
 124                 bufsize = pctx->bufsize;
 125                 /* restrict matches to the longest allowed sequence */
 126                 maxpos = bufsize;
 127                 if ((i + pctx->mxsz) < maxpos)
 128                         maxpos = i + pctx->mxsz;
 129                 startj = i + 1 - maxpos;
 130                 bestj = startj;
 131                 /* make indexes relative to end of allowed position */
 132                 p1 = &p1[maxpos];
 133                 if (startj < 0) {
 134                         do {
 135                         /* indexes are negative */
 136                                 p2 = &p1[node - i];
 137                         /* no need to compare the first byte */
 138                                 j = startj;
 139                         /* the second byte cannot lead to useful compression */
 140                                 if (p1[j] == p2[j]) {
 141                                         j++;
 142                                         if (j < 0) {
 143                                                 do {
 144                                                 } while ((p1[j] == p2[j])
 145                                                                 && (++j < 0));
 146                                         }
 147                                         /* remember the match, if better */
 148                                         if (j > bestj) {
 149                                                 bestj = j;
 150                                                 bestnode = node;
 151                                         }
 152                                 }
 153                                 /* walk in the tree in the right direction */
 154                                 if ((j < 0) && (p1[j] < p2[j]))
 155                                         prev = &pctx->lson[node];
 156                                 else
 157                                         prev = &pctx->rson[node];
 158                                 node = *prev;
 159                                 /* stop if reaching a leaf or maximum length */
 160                         } while ((node >= 0) && (j < 0));
 161                         /* put the node into the tree if we reached a leaf */
 162                         if (node < 0)
 163                                 *prev = i;
 164                 }
 165                         /* done, return the best match */
 166                 pctx->size = bestj + maxpos - i;
 167                 pctx->rel = bestnode - i;
 168         } else {
 169                 pctx->head[p1[i] & 255] = i;
 170                 pctx->size = 0;
 171                 pctx->rel = 0;
 172         }
 173         return (pctx->size);
 174 }
 175
 176 /*
 177  *              Compress a 4096-byte block
 178  *
 179  *      Returns a header of two bytes followed by the compressed data.
 180  *      If compression is not effective, the header and an uncompressed
 181  *      block is returned.
 182  *
 183  *      Note : two bytes may be output before output buffer overflow
 184  *      is detected, so a 4100-bytes output buffer must be reserved.
 185  *
 186  *      Returns the size of the compressed block, including the
 187  *                      header (minimal size is 2, maximum size is 4098)
 188  *              0 if an error has been met.
 189  */
 190
 191 static unsigned int ntfs_compress_block(const char *inbuf, int bufsize,
 192                                 char *outbuf)
 193 {
 194         struct COMPRESS_CONTEXT *pctx;
 195         int i; /* current position */
 196         int j; /* end of best match from current position */
 197         int k; /* end of best match from next position */
 198         int offs; /* offset to best match */
 199         int n;
 200         int bp; /* bits to store offset */
 201         int mxoff; /* max match offset : 1 << bp */
 202         int mxsz2;
 203         unsigned int xout;
 204         unsigned int q; /* aggregated offset and size */
 205         int done;
 206         char *ptag; /* location reserved for a tag */
 207         int tag;    /* current value of tag */
 208         int ntag;   /* count of bits still undefined in tag */
 209
 210         pctx = (struct COMPRESS_CONTEXT*)ntfs_malloc(sizeof(struct COMPRESS_CONTEXT));
 211         if (pctx) {
 212                 for (n=0; n<NTFS_SB_SIZE; n++)
 213                         pctx->lson[n] = pctx->rson[n] = -1;
 214                 for (n=0; n<256; n++)
 215                         pctx->head[n] = -1;
 216                 pctx->inbuf = (const unsigned char*)inbuf;
 217                 pctx->bufsize = bufsize;
 218                 xout = 2;
 219                 n = 0;
 220                 i = 0;
 221                 bp = 4;
 222                 mxoff = 1 << bp;
 223                 pctx->mxsz = (1 << (16 - bp)) + 2;
 224                 tag = 0;
 225                 done = -1;
 226                 ntag = 8;
 227                 ptag = &outbuf[xout++];
 228                 while ((i < bufsize) && (xout < (NTFS_SB_SIZE + 2))) {
 229                    /* adjust the longest match we can output */
 230                         while (mxoff < i) {
 231                                 bp++;
 232                                 mxoff <<= 1;
 233                                 pctx->mxsz = (pctx->mxsz + 2) >> 1;
 234                         }
 235                 /* search the best match at current position */
 236                         if (done < i)
 237                                 do {
 238                                         ntfs_best_match(pctx,++done);
 239                                 } while (done < i);
 240                         j = i + pctx->size;
 241                         if ((j - i) > pctx->mxsz)
 242                                 j = i + pctx->mxsz;
 243
 244                         if ((j - i) > 2) {
 245                                 offs = pctx->rel;
 246                   /* check whether there is a better run at i+1 */
 247                                 ntfs_best_match(pctx,i+1);
 248                                 done = i+1;
 249                                 k = i + 1 + pctx->size;
 250                                 mxsz2 = pctx->mxsz;
 251                                 if (mxoff <= i)
 252                                         mxsz2 = (pctx->mxsz + 2) >> 1;
 253                                 if ((k - i) > mxsz2)
 254                                         k = i + mxsz2;
 255                                 if (k > (j + 1)) {
 256                                         /* issue a single byte */
 257                                         outbuf[xout++] = inbuf[i];
 258                                         i++;
 259                                 } else {
 260                                         q = (~offs << (16 - bp))
 261                                                 + (j - i - 3);
 262                                         outbuf[xout++] = q & 255;
 263                                         outbuf[xout++] = (q >> 8) & 255;
 264                                         tag |= (1 << (8 - ntag));
 265                                         i = j;
 266                                 }
 267                         } else {
 268                                 outbuf[xout++] = inbuf[i];
 269                                 i++;
 270                         }
 271                                 /* store the tag if fully used */
 272                         if (!--ntag) {
 273                                 *ptag = tag;
 274                                 ntag = 8;
 275                                 ptag = &outbuf[xout++];
 276                                 tag = 0;
 277                         }
 278                 }
 279                         /* store the last tag, if partially used */
 280                 if (ntag == 8)
 281                         xout--;
 282                 else
 283                         *ptag = tag;
 284                 /* uncompressed must be full size, accept if better */
 285                 if ((i >= bufsize) && (xout < (NTFS_SB_SIZE + 2))) {
 286                         outbuf[0] = (xout - 3) & 255;
 287                         outbuf[1] = 0xb0 + (((xout - 3) >> 8) & 15);
 288                 } else {
 289                         memcpy(&outbuf[2],inbuf,bufsize);
 290                         if (bufsize < NTFS_SB_SIZE)
 291                                 memset(&outbuf[bufsize+2], 0,
 292                                                 NTFS_SB_SIZE - bufsize);
 293                         outbuf[0] = 0xff;
 294                         outbuf[1] = 0x3f;
 295                         xout = NTFS_SB_SIZE + 2;
 296                 }
 297                 free(pctx);
 298         } else {
 299                 xout = 0;
 300                 errno = ENOMEM;
 301         }
 302         return (xout);
 303 }
 304
 305 /**
 306  * ntfs_decompress - decompress a compression block into an array of pages
 307  * @dest:       buffer to which to write the decompressed data
 308  * @dest_size:  size of buffer @dest in bytes
 309  * @cb_start:   compression block to decompress
 310  * @cb_size:    size of compression block @cb_start in bytes
 311  *
 312  * This decompresses the compression block @cb_start into the destination
 313  * buffer @dest.
 314  *
 315  * @cb_start is a pointer to the compression block which needs decompressing
 316  * and @cb_size is the size of @cb_start in bytes (8-64kiB).
 317  *
 318  * Return 0 if success or -EOVERFLOW on error in the compressed stream.
 319  */
 320 static int ntfs_decompress(u8 *dest, const u32 dest_size,
 321                 u8 *const cb_start, const u32 cb_size)
 322 {
 323         /*
 324          * Pointers into the compressed data, i.e. the compression block (cb),
 325          * and the therein contained sub-blocks (sb).
 326          */
 327         u8 *cb_end = cb_start + cb_size; /* End of cb. */
 328         u8 *cb = cb_start;      /* Current position in cb. */
 329         u8 *cb_sb_start = cb;   /* Beginning of the current sb in the cb. */
 330         u8 *cb_sb_end;          /* End of current sb / beginning of next sb. */
 331         /* Variables for uncompressed data / destination. */
 332         u8 *dest_end = dest + dest_size;        /* End of dest buffer. */
 333         u8 *dest_sb_start;      /* Start of current sub-block in dest. */
 334         u8 *dest_sb_end;        /* End of current sb in dest. */
 335         /* Variables for tag and token parsing. */
 336         u8 tag;                 /* Current tag. */
 337         int token;              /* Loop counter for the eight tokens in tag. */
 338
 339         ntfs_log_trace("Entering, cb_size = 0x%x.\n", (unsigned)cb_size);
 340 do_next_sb:
 341         ntfs_log_debug("Beginning sub-block at offset = %d in the cb.\n",
 342                         (int)(cb - cb_start));
 343         /*
 344          * Have we reached the end of the compression block or the end of the
 345          * decompressed data?  The latter can happen for example if the current
 346          * position in the compression block is one byte before its end so the
 347          * first two checks do not detect it.
 348          */
 349         if (cb == cb_end || !le16_to_cpup((le16*)cb) || dest == dest_end) {
 350                 ntfs_log_debug("Completed. Returning success (0).\n");
 351                 return 0;
 352         }
 353         /* Setup offset for the current sub-block destination. */
 354         dest_sb_start = dest;
 355         dest_sb_end = dest + NTFS_SB_SIZE;
 356         /* Check that we are still within allowed boundaries. */
 357         if (dest_sb_end > dest_end)
 358                 goto return_overflow;
 359         /* Does the minimum size of a compressed sb overflow valid range? */
 360         if (cb + 6 > cb_end)
 361                 goto return_overflow;
 362         /* Setup the current sub-block source pointers and validate range. */
 363         cb_sb_start = cb;
 364         cb_sb_end = cb_sb_start + (le16_to_cpup((le16*)cb) & NTFS_SB_SIZE_MASK)
 365                         + 3;
 366         if (cb_sb_end > cb_end)
 367                 goto return_overflow;
 368         /* Now, we are ready to process the current sub-block (sb). */
 369         if (!(le16_to_cpup((le16*)cb) & NTFS_SB_IS_COMPRESSED)) {
 370                 ntfs_log_debug("Found uncompressed sub-block.\n");
 371                 /* This sb is not compressed, just copy it into destination. */
 372                 /* Advance source position to first data byte. */
 373                 cb += 2;
 374                 /* An uncompressed sb must be full size. */
 375                 if (cb_sb_end - cb != NTFS_SB_SIZE)
 376                         goto return_overflow;
 377                 /* Copy the block and advance the source position. */
 378                 memcpy(dest, cb, NTFS_SB_SIZE);
 379                 cb += NTFS_SB_SIZE;
 380                 /* Advance destination position to next sub-block. */
 381                 dest += NTFS_SB_SIZE;
 382                 goto do_next_sb;
 383         }
 384         ntfs_log_debug("Found compressed sub-block.\n");
 385         /* This sb is compressed, decompress it into destination. */
 386         /* Forward to the first tag in the sub-block. */
 387         cb += 2;
 388 do_next_tag:
 389         if (cb == cb_sb_end) {
 390                 /* Check if the decompressed sub-block was not full-length. */
 391                 if (dest < dest_sb_end) {
 392                         int nr_bytes = dest_sb_end - dest;
 393
 394                         ntfs_log_debug("Filling incomplete sub-block with zeroes.\n");
 395                         /* Zero remainder and update destination position. */
 396                         memset(dest, 0, nr_bytes);
 397                         dest += nr_bytes;
 398                 }
 399                 /* We have finished the current sub-block. */
 400                 goto do_next_sb;
 401         }
 402         /* Check we are still in range. */
 403         if (cb > cb_sb_end || dest > dest_sb_end)
 404                 goto return_overflow;
 405         /* Get the next tag and advance to first token. */
 406         tag = *cb++;
 407         /* Parse the eight tokens described by the tag. */
 408         for (token = 0; token < 8; token++, tag >>= 1) {
 409                 u16 lg, pt, length, max_non_overlap;
 410                 register u16 i;
 411                 u8 *dest_back_addr;
 412
 413                 /* Check if we are done / still in range. */
 414                 if (cb >= cb_sb_end || dest > dest_sb_end)
 415                         break;
 416                 /* Determine token type and parse appropriately.*/
 417                 if ((tag & NTFS_TOKEN_MASK) == NTFS_SYMBOL_TOKEN) {
 418                         /*
 419                          * We have a symbol token, copy the symbol across, and
 420                          * advance the source and destination positions.
 421                          */
 422                         *dest++ = *cb++;
 423                         /* Continue with the next token. */
 424                         continue;
 425                 }
 426                 /*
 427                  * We have a phrase token. Make sure it is not the first tag in
 428                  * the sb as this is illegal and would confuse the code below.
 429                  */
 430                 if (dest == dest_sb_start)
 431                         goto return_overflow;
 432                 /*
 433                  * Determine the number of bytes to go back (p) and the number
 434                  * of bytes to copy (l). We use an optimized algorithm in which
 435                  * we first calculate log2(current destination position in sb),
 436                  * which allows determination of l and p in O(1) rather than
 437                  * O(n). We just need an arch-optimized log2() function now.
 438                  */
 439                 lg = 0;
 440                 for (i = dest - dest_sb_start - 1; i >= 0x10; i >>= 1)
 441                         lg++;
 442                 /* Get the phrase token into i. */
 443                 pt = le16_to_cpup((le16*)cb);
 444                 /*
 445                  * Calculate starting position of the byte sequence in
 446                  * the destination using the fact that p = (pt >> (12 - lg)) + 1
 447                  * and make sure we don't go too far back.
 448                  */
 449                 dest_back_addr = dest - (pt >> (12 - lg)) - 1;
 450                 if (dest_back_addr < dest_sb_start)
 451                         goto return_overflow;
 452                 /* Now calculate the length of the byte sequence. */
 453                 length = (pt & (0xfff >> lg)) + 3;
 454                 /* Verify destination is in range. */
 455                 if (dest + length > dest_sb_end)
 456                         goto return_overflow;
 457                 /* The number of non-overlapping bytes. */
 458                 max_non_overlap = dest - dest_back_addr;
 459                 if (length <= max_non_overlap) {
 460                         /* The byte sequence doesn't overlap, just copy it. */
 461                         memcpy(dest, dest_back_addr, length);
 462                         /* Advance destination pointer. */
 463                         dest += length;
 464                 } else {
 465                         /*
 466                          * The byte sequence does overlap, copy non-overlapping
 467                          * part and then do a slow byte by byte copy for the
 468                          * overlapping part. Also, advance the destination
 469                          * pointer.
 470                          */
 471                         memcpy(dest, dest_back_addr, max_non_overlap);
 472                         dest += max_non_overlap;
 473                         dest_back_addr += max_non_overlap;
 474                         length -= max_non_overlap;
 475                         while (length--)
 476                                 *dest++ = *dest_back_addr++;
 477                 }
 478                 /* Advance source position and continue with the next token. */
 479                 cb += 2;
 480         }
 481         /* No tokens left in the current tag. Continue with the next tag. */
 482         goto do_next_tag;
 483 return_overflow:
 484         errno = EOVERFLOW;
 485         ntfs_log_perror("Failed to decompress file");
 486         return -1;
 487 }
 488
 489 /**
 490  * ntfs_is_cb_compressed - internal function, do not use
 491  *
 492  * This is a very specialised function determining if a cb is compressed or
 493  * uncompressed.  It is assumed that checking for a sparse cb has already been
 494  * performed and that the cb is not sparse.  It makes all sorts of other
 495  * assumptions as well and hence it is not useful anywhere other than where it
 496  * is used at the moment.  Please, do not make this function available for use
 497  * outside of compress.c as it is bound to confuse people and not do what they
 498  * want.
 499  *
 500  * Return TRUE on errors so that the error will be detected later on in the
 501  * code.  Might be a bit confusing to debug but there really should never be
 502  * errors coming from here.
 503  */
 504 static BOOL ntfs_is_cb_compressed(ntfs_attr *na, runlist_element *rl,
 505                                   VCN cb_start_vcn, int cb_clusters)
 506 {
 507         /*
 508          * The simplest case: the run starting at @cb_start_vcn contains
 509          * @cb_clusters clusters which are all not sparse, thus the cb is not
 510          * compressed.
 511          */
 512 restart:
 513         cb_clusters -= rl->length - (cb_start_vcn - rl->vcn);
 514         while (cb_clusters > 0) {
 515                 /* Go to the next run. */
 516                 rl++;
 517                 /* Map the next runlist fragment if it is not mapped. */
 518                 if (rl->lcn < LCN_HOLE || !rl->length) {
 519                         cb_start_vcn = rl->vcn;
 520                         rl = ntfs_attr_find_vcn(na, rl->vcn);
 521                         if (!rl || rl->lcn < LCN_HOLE || !rl->length)
 522                                 return TRUE;
 523                         /*
 524                          * If the runs were merged need to deal with the
 525                          * resulting partial run so simply restart.
 526                          */
 527                         if (rl->vcn < cb_start_vcn)
 528                                 goto restart;
 529                 }
 530                 /* If the current run is sparse, the cb is compressed. */
 531                 if (rl->lcn == LCN_HOLE)
 532                         return TRUE;
 533                 /* If the whole cb is not sparse, it is not compressed. */
 534                 if (rl->length >= cb_clusters)
 535                         return FALSE;
 536                 cb_clusters -= rl->length;
 537         };
 538         /* All cb_clusters were not sparse thus the cb is not compressed. */
 539         return FALSE;
 540 }
 541
 542 /**
 543  * ntfs_compressed_attr_pread - read from a compressed attribute
 544  * @na:         ntfs attribute to read from
 545  * @pos:        byte position in the attribute to begin reading from
 546  * @count:      number of bytes to read
 547  * @b:          output data buffer
 548  *
 549  * NOTE:  You probably want to be using attrib.c::ntfs_attr_pread() instead.
 550  *
 551  * This function will read @count bytes starting at offset @pos from the
 552  * compressed ntfs attribute @na into the data buffer @b.
 553  *
 554  * On success, return the number of successfully read bytes.  If this number
 555  * is lower than @count this means that the read reached end of file or that
 556  * an error was encountered during the read so that the read is partial.
 557  * 0 means end of file or nothing was read (also return 0 when @count is 0).
 558  *
 559  * On error and nothing has been read, return -1 with errno set appropriately
 560  * to the return code of ntfs_pread(), or to EINVAL in case of invalid
 561  * arguments.
 562  */
 563 s64 ntfs_compressed_attr_pread(ntfs_attr *na, s64 pos, s64 count, void *b)
 564 {
 565         s64 br, to_read, ofs, total, total2;
 566         u64 cb_size_mask;
 567         VCN start_vcn, vcn, end_vcn;
 568         ntfs_volume *vol;
 569         runlist_element *rl;
 570         u8 *dest, *cb, *cb_pos, *cb_end;
 571         u32 cb_size;
 572         int err;
 573         ATTR_FLAGS data_flags;
 574         FILE_ATTR_FLAGS compression;
 575         unsigned int nr_cbs, cb_clusters;
 576
 577         ntfs_log_trace("Entering for inode 0x%llx, attr 0x%x, pos 0x%llx, count 0x%llx.\n",
 578                         (unsigned long long)na->ni->mft_no, na->type,
 579                         (long long)pos, (long long)count);
 580         data_flags = na->data_flags;
 581         compression = na->ni->flags & FILE_ATTR_COMPRESSED;
 582         if (!na || !na->ni || !na->ni->vol || !b
 583                         || ((data_flags & ATTR_COMPRESSION_MASK)
 584                                 != ATTR_IS_COMPRESSED)
 585                         || pos < 0 || count < 0) {
 586                 errno = EINVAL;
 587                 return -1;
 588         }
 589         /*
 590          * Encrypted attributes are not supported.  We return access denied,
 591          * which is what Windows NT4 does, too.
 592          */
 593         if (NAttrEncrypted(na)) {
 594                 errno = EACCES;
 595                 return -1;
 596         }
 597         if (!count)
 598                 return 0;
 599         /* Truncate reads beyond end of attribute. */
 600         if (pos + count > na->data_size) {
 601                 if (pos >= na->data_size) {
 602                         return 0;
 603                 }
 604                 count = na->data_size - pos;
 605         }
 606         /* If it is a resident attribute, simply use ntfs_attr_pread(). */
 607         if (!NAttrNonResident(na))
 608                 return ntfs_attr_pread(na, pos, count, b);
 609         total = total2 = 0;
 610         /* Zero out reads beyond initialized size. */
 611         if (pos + count > na->initialized_size) {
 612                 if (pos >= na->initialized_size) {
 613                         memset(b, 0, count);
 614                         return count;
 615                 }
 616                 total2 = pos + count - na->initialized_size;
 617                 count -= total2;
 618                 memset((u8*)b + count, 0, total2);
 619         }
 620         vol = na->ni->vol;
 621         cb_size = na->compression_block_size;
 622         cb_size_mask = cb_size - 1UL;
 623         cb_clusters = na->compression_block_clusters;
 624
 625         /* Need a temporary buffer for each loaded compression block. */
 626         cb = (u8*)ntfs_malloc(cb_size);
 627         if (!cb)
 628                 return -1;
 629
 630         /* Need a temporary buffer for each uncompressed block. */
 631         dest = (u8*)ntfs_malloc(cb_size);
 632         if (!dest) {
 633                 free(cb);
 634                 return -1;
 635         }
 636         /*
 637          * The first vcn in the first compression block (cb) which we need to
 638          * decompress.
 639          */
 640         start_vcn = (pos & ~cb_size_mask) >> vol->cluster_size_bits;
 641         /* Offset in the uncompressed cb at which to start reading data. */
 642         ofs = pos & cb_size_mask;
 643         /*
 644          * The first vcn in the cb after the last cb which we need to
 645          * decompress.
 646          */
 647         end_vcn = ((pos + count + cb_size - 1) & ~cb_size_mask) >>
 648                         vol->cluster_size_bits;
 649         /* Number of compression blocks (cbs) in the wanted vcn range. */
 650         nr_cbs = (end_vcn - start_vcn) << vol->cluster_size_bits >>
 651                         na->compression_block_size_bits;
 652         cb_end = cb + cb_size;
 653 do_next_cb:
 654         nr_cbs--;
 655         cb_pos = cb;
 656         vcn = start_vcn;
 657         start_vcn += cb_clusters;
 658
 659         /* Check whether the compression block is sparse. */
 660         rl = ntfs_attr_find_vcn(na, vcn);
 661         if (!rl || rl->lcn < LCN_HOLE) {
 662                 free(cb);
 663                 free(dest);
 664                 if (total)
 665                         return total;
 666                 /* FIXME: Do we want EIO or the error code? (AIA) */
 667                 errno = EIO;
 668                 return -1;
 669         }
 670         if (rl->lcn == LCN_HOLE) {
 671                 /* Sparse cb, zero out destination range overlapping the cb. */
 672                 ntfs_log_debug("Found sparse compression block.\n");
 673                 to_read = min(count, cb_size - ofs);
 674                 memset(b, 0, to_read);
 675                 ofs = 0;
 676                 total += to_read;
 677                 count -= to_read;
 678                 b = (u8*)b + to_read;
 679         } else if (!ntfs_is_cb_compressed(na, rl, vcn, cb_clusters)) {
 680                 s64 tdata_size, tinitialized_size;
 681                 /*
 682                  * Uncompressed cb, read it straight into the destination range
 683                  * overlapping the cb.
 684                  */
 685                 ntfs_log_debug("Found uncompressed compression block.\n");
 686                 /*
 687                  * Read the uncompressed data into the destination buffer.
 688                  * NOTE: We cheat a little bit here by marking the attribute as
 689                  * not compressed in the ntfs_attr structure so that we can
 690                  * read the data by simply using ntfs_attr_pread().  (-8
 691                  * NOTE: we have to modify data_size and initialized_size
 692                  * temporarily as well...
 693                  */
 694                 to_read = min(count, cb_size - ofs);
 695                 ofs += vcn << vol->cluster_size_bits;
 696                 NAttrClearCompressed(na);
 697                 na->data_flags &= ~ATTR_COMPRESSION_MASK;
 698                 tdata_size = na->data_size;
 699                 tinitialized_size = na->initialized_size;
 700                 na->data_size = na->initialized_size = na->allocated_size;
 701                 do {
 702                         br = ntfs_attr_pread(na, ofs, to_read, b);
 703                         if (br <= 0) {
 704                                 if (!br) {
 705                                         ntfs_log_error("Failed to read an"
 706                                                 " uncompressed cluster,"
 707                                                 " inode %lld offs 0x%llx\n",
 708                                                 (long long)na->ni->mft_no,
 709                                                 (long long)ofs);
 710                                         errno = EIO;
 711                                 }
 712                                 err = errno;
 713                                 na->data_size = tdata_size;
 714                                 na->initialized_size = tinitialized_size;
 715                                 na->ni->flags |= compression;
 716                                 na->data_flags = data_flags;
 717                                 free(cb);
 718                                 free(dest);
 719                                 if (total)
 720                                         return total;
 721                                 errno = err;
 722                                 return br;
 723                         }
 724                         total += br;
 725                         count -= br;
 726                         b = (u8*)b + br;
 727                         to_read -= br;
 728                         ofs += br;
 729                 } while (to_read > 0);
 730                 na->data_size = tdata_size;
 731                 na->initialized_size = tinitialized_size;
 732                 na->ni->flags |= compression;
 733                 na->data_flags = data_flags;
 734                 ofs = 0;
 735         } else {
 736                 s64 tdata_size, tinitialized_size;
 737
 738                 /*
 739                  * Compressed cb, decompress it into the temporary buffer, then
 740                  * copy the data to the destination range overlapping the cb.
 741                  */
 742                 ntfs_log_debug("Found compressed compression block.\n");
 743                 /*
 744                  * Read the compressed data into the temporary buffer.
 745                  * NOTE: We cheat a little bit here by marking the attribute as
 746                  * not compressed in the ntfs_attr structure so that we can
 747                  * read the raw, compressed data by simply using
 748                  * ntfs_attr_pread().  (-8
 749                  * NOTE: We have to modify data_size and initialized_size
 750                  * temporarily as well...
 751                  */
 752                 to_read = cb_size;
 753                 NAttrClearCompressed(na);
 754                 na->data_flags &= ~ATTR_COMPRESSION_MASK;
 755                 tdata_size = na->data_size;
 756                 tinitialized_size = na->initialized_size;
 757                 na->data_size = na->initialized_size = na->allocated_size;
 758                 do {
 759                         br = ntfs_attr_pread(na,
 760                                         (vcn << vol->cluster_size_bits) +
 761                                         (cb_pos - cb), to_read, cb_pos);
 762                         if (br <= 0) {
 763                                 if (!br) {
 764                                         ntfs_log_error("Failed to read a"
 765                                                 " compressed cluster, "
 766                                                 " inode %lld offs 0x%llx\n",
 767                                                 (long long)na->ni->mft_no,
 768                                                 (long long)(vcn << vol->cluster_size_bits));
 769                                         errno = EIO;
 770                                 }
 771                                 err = errno;
 772                                 na->data_size = tdata_size;
 773                                 na->initialized_size = tinitialized_size;
 774                                 na->ni->flags |= compression;
 775                                 na->data_flags = data_flags;
 776                                 free(cb);
 777                                 free(dest);
 778                                 if (total)
 779                                         return total;
 780                                 errno = err;
 781                                 return br;
 782                         }
 783                         cb_pos += br;
 784                         to_read -= br;
 785                 } while (to_read > 0);
 786                 na->data_size = tdata_size;
 787                 na->initialized_size = tinitialized_size;
 788                 na->ni->flags |= compression;
 789                 na->data_flags = data_flags;
 790                 /* Just a precaution. */
 791                 if (cb_pos + 2 <= cb_end)
 792                         *(u16*)cb_pos = 0;
 793                 ntfs_log_debug("Successfully read the compression block.\n");
 794                 if (ntfs_decompress(dest, cb_size, cb, cb_size) < 0) {
 795                         err = errno;
 796                         free(cb);
 797                         free(dest);
 798                         if (total)
 799                                 return total;
 800                         errno = err;
 801                         return -1;
 802                 }
 803                 to_read = min(count, cb_size - ofs);
 804                 memcpy(b, dest + ofs, to_read);
 805                 total += to_read;
 806                 count -= to_read;
 807                 b = (u8*)b + to_read;
 808                 ofs = 0;
 809         }
 810         /* Do we have more work to do? */
 811         if (nr_cbs)
 812                 goto do_next_cb;
 813         /* We no longer need the buffers. */
 814         free(cb);
 815         free(dest);
 816         /* Return number of bytes read. */
 817         return total + total2;
 818 }
 819
 820 /*
 821  *              Read data from a set of clusters
 822  *
 823  *      Returns the amount of data read
 824  */
 825
 826 static u32 read_clusters(ntfs_volume *vol, const runlist_element *rl,
 827                         s64 offs, u32 to_read, char *inbuf)
 828 {
 829         u32 count;
 830         int xgot;
 831         u32 got;
 832         s64 xpos;
 833         BOOL first;
 834         char *xinbuf;
 835         const runlist_element *xrl;
 836
 837         got = 0;
 838         xrl = rl;
 839         xinbuf = inbuf;
 840         first = TRUE;
 841         do {
 842                 count = xrl->length << vol->cluster_size_bits;
 843                 xpos = xrl->lcn << vol->cluster_size_bits;
 844                 if (first) {
 845                         count -= offs;
 846                         xpos += offs;
 847                 }
 848                 if ((to_read - got) < count)
 849                         count = to_read - got;
 850                 xgot = ntfs_pread(vol->dev, xpos, count, xinbuf);
 851                 if (xgot == (int)count) {
 852                         got += count;
 853                         xpos += count;
 854                         xinbuf += count;
 855                         xrl++;
 856                 }
 857                 first = FALSE;
 858         } while ((xgot == (int)count) && (got < to_read));
 859         return (got);
 860 }
 861
 862 /*
 863  *              Write data to a set of clusters
 864  *
 865  *      Returns the amount of data written
 866  */
 867
 868 static s32 write_clusters(ntfs_volume *vol, const runlist_element *rl,
 869                         s64 offs, s32 to_write, const char *outbuf)
 870 {
 871         s32 count;
 872         s32 put, xput;
 873         s64 xpos;
 874         BOOL first;
 875         const char *xoutbuf;
 876         const runlist_element *xrl;
 877
 878         put = 0;
 879         xrl = rl;
 880         xoutbuf = outbuf;
 881         first = TRUE;
 882         do {
 883                 count = xrl->length << vol->cluster_size_bits;
 884                 xpos = xrl->lcn << vol->cluster_size_bits;
 885                 if (first) {
 886                         count -= offs;
 887                         xpos += offs;
 888                 }
 889                 if ((to_write - put) < count)
 890                         count = to_write - put;
 891                 xput = ntfs_pwrite(vol->dev, xpos, count, xoutbuf);
 892                 if (xput == count) {
 893                         put += count;
 894                         xpos += count;
 895                         xoutbuf += count;
 896                         xrl++;
 897                 }
 898                 first = FALSE;
 899         } while ((xput == count) && (put < to_write));
 900         return (put);
 901 }
 902
 903
 904 /*
 905  *              Compress and write a set of blocks
 906  *
 907  *      returns the size actually written (rounded to a full cluster)
 908  *              or 0 if all zeroes (nothing is written)
 909  *              or -1 if could not compress (nothing is written)
 910  *              or -2 if there were an irrecoverable error (errno set)
 911  */
 912
 913 static s32 ntfs_comp_set(ntfs_attr *na, runlist_element *rl,
 914                         s64 offs, u32 insz, const char *inbuf)
 915 {
 916         ntfs_volume *vol;
 917         char *outbuf;
 918         char *pbuf;
 919         u32 compsz;
 920         s32 written;
 921         s32 rounded;
 922         unsigned int clsz;
 923         u32 p;
 924         unsigned int sz;
 925         unsigned int bsz;
 926         BOOL fail;
 927         BOOL allzeroes;
 928                 /* a single compressed zero */
 929         static char onezero[] = { 0x01, 0xb0, 0x00, 0x00 } ;
 930                 /* a couple of compressed zeroes */
 931         static char twozeroes[] = { 0x02, 0xb0, 0x00, 0x00, 0x00 } ;
 932                 /* more compressed zeroes, to be followed by some count */
 933         static char morezeroes[] = { 0x03, 0xb0, 0x02, 0x00 } ;
 934
 935         vol = na->ni->vol;
 936         written = -1; /* default return */
 937         clsz = 1 << vol->cluster_size_bits;
 938                 /* may need 2 extra bytes per block and 2 more bytes */
 939         outbuf = (char*)ntfs_malloc(na->compression_block_size
 940                         + 2*(na->compression_block_size/NTFS_SB_SIZE)
 941                         + 2);
 942         if (outbuf) {
 943                 fail = FALSE;
 944                 compsz = 0;
 945                 allzeroes = TRUE;
 946                 for (p=0; (p<insz) && !fail; p+=NTFS_SB_SIZE) {
 947                         if ((p + NTFS_SB_SIZE) < insz)
 948                                 bsz = NTFS_SB_SIZE;
 949                         else
 950                                 bsz = insz - p;
 951                         pbuf = &outbuf[compsz];
 952                         sz = ntfs_compress_block(&inbuf[p],bsz,pbuf);
 953                         /* fail if all the clusters (or more) are needed */
 954                         if (!sz || ((compsz + sz + clsz + 2)
 955                                          > na->compression_block_size))
 956                                 fail = TRUE;
 957                         else {
 958                                 if (allzeroes) {
 959                                 /* check whether this is all zeroes */
 960                                         switch (sz) {
 961                                         case 4 :
 962                                                 allzeroes = !memcmp(
 963                                                         pbuf,onezero,4);
 964                                                 break;
 965                                         case 5 :
 966                                                 allzeroes = !memcmp(
 967                                                         pbuf,twozeroes,5);
 968                                                 break;
 969                                         case 6 :
 970                                                 allzeroes = !memcmp(
 971                                                         pbuf,morezeroes,4);
 972                                                 break;
 973                                         default :
 974                                                 allzeroes = FALSE;
 975                                                 break;
 976                                         }
 977                                 }
 978                         compsz += sz;
 979                         }
 980                 }
 981                 if (!fail && !allzeroes) {
 982                         /* add a couple of null bytes, space has been checked */
 983                         outbuf[compsz++] = 0;
 984                         outbuf[compsz++] = 0;
 985                         /* write a full cluster, to avoid partial reading */
 986                         rounded = ((compsz - 1) | (clsz - 1)) + 1;
 987                         written = write_clusters(vol, rl, offs, rounded, outbuf);
 988                         if (written != rounded) {
 989                                 /*
 990                                  * TODO : previously written text has been
 991                                  * spoilt, should return a specific error
 992                                  */
 993                                 ntfs_log_error("error writing compressed data\n");
 994                                 errno = EIO;
 995                                 written = -2;
 996                         }
 997                 } else
 998                         if (!fail)
 999                                 written = 0;
1000                 free(outbuf);
1001         }
1002         return (written);
1003 }
1004
1005 /*
1006  *              Check the validity of a compressed runlist
1007  *      The check starts at the beginning of current run and ends
1008  *      at the end of runlist
1009  *      errno is set if the runlist is not valid
1010  */
1011
1012 static BOOL valid_compressed_run(ntfs_attr *na, runlist_element *rl,
1013                         BOOL fullcheck, const char *text)
1014 {
1015         runlist_element *xrl;
1016         const char *err;
1017         BOOL ok = TRUE;
1018
1019         xrl = rl;
1020         while (xrl->vcn & (na->compression_block_clusters - 1))
1021                 xrl--;
1022         err = (const char*)NULL;
1023         while (xrl->length) {
1024                 if ((xrl->vcn + xrl->length) != xrl[1].vcn)
1025                         err = "Runs not adjacent";
1026                 if (xrl->lcn == LCN_HOLE) {
1027                         if ((xrl->vcn + xrl->length)
1028                             & (na->compression_block_clusters - 1)) {
1029                                 err = "Invalid hole";
1030                         }
1031                         if (fullcheck && (xrl[1].lcn == LCN_HOLE)) {
1032                                 err = "Adjacent holes";
1033                         }
1034                 }
1035                 if (err) {
1036                         ntfs_log_error("%s at %s index %ld inode %lld\n",
1037                                 err, text, (long)(xrl - na->rl),
1038                                 (long long)na->ni->mft_no);
1039                         errno = EIO;
1040                         ok = FALSE;
1041                         err = (const char*)NULL;
1042                 }
1043                 xrl++;
1044         }
1045         return (ok);
1046 }
1047
1048 /*
1049  *              Free unneeded clusters after overwriting compressed data
1050  *
1051  *      This generally requires one or two empty slots at the end of runlist,
1052  *      but we do not want to reallocate the runlist here because
1053  *      there are many pointers to it.
1054  *      So the empty slots have to be reserved beforehand
1055  *
1056  *      Returns zero unless some error occurred (described by errno)
1057  *
1058  *         +======= start of block =====+
1059  *      0  |A     chunk may overflow    | <-- rl         usedcnt : A + B
1060  *         |A     on previous block     |                        then B
1061  *         |A                           |
1062  *         +-- end of allocated chunk --+                freelength : C
1063  *         |B                           |                      (incl overflow)
1064  *         +== end of compressed data ==+
1065  *         |C                           | <-- freerl     freecnt : C + D
1066  *         |C     chunk may overflow    |
1067  *         |C     on next block         |
1068  *         +-- end of allocated chunk --+
1069  *         |D                           |
1070  *         |D     chunk may overflow    |
1071  *     15  |D     on next block         |
1072  *         +======== end of block ======+
1073  *
1074  */
1075
1076 static int ntfs_compress_overwr_free(ntfs_attr *na, runlist_element *rl,
1077                         s32 usedcnt, s32 freecnt, VCN *update_from)
1078 {
1079         BOOL beginhole;
1080         BOOL mergeholes;
1081         s32 oldlength;
1082         s32 freelength;
1083         s64 freelcn;
1084         s64 freevcn;
1085         runlist_element *freerl;
1086         ntfs_volume *vol;
1087         s32 carry;
1088         int res;
1089
1090         vol = na->ni->vol;
1091         res = 0;
1092         freelcn = rl->lcn + usedcnt;
1093         freevcn = rl->vcn + usedcnt;
1094         freelength = rl->length - usedcnt;
1095         beginhole = !usedcnt && !rl->vcn;
1096                 /* can merge with hole before ? */
1097         mergeholes = !usedcnt
1098                         && rl[0].vcn
1099                         && (rl[-1].lcn == LCN_HOLE);
1100                 /* truncate current run, carry to subsequent hole */
1101         carry = freelength;
1102         oldlength = rl->length;
1103         if (mergeholes) {
1104                         /* merging with a hole before */
1105                 freerl = rl;
1106         } else {
1107                 rl->length -= freelength; /* warning : can be zero */
1108                 freerl = ++rl;
1109         }
1110         if (!mergeholes && (usedcnt || beginhole)) {
1111                 s32 freed;
1112                 runlist_element *frl;
1113                 runlist_element *erl;
1114                 int holes = 0;
1115                 BOOL threeparts;
1116
1117                 /* free the unneeded clusters from initial run, then freerl */
1118                 threeparts = (freelength > freecnt);
1119                 freed = 0;
1120                 frl = freerl;
1121                 if (freelength) {
1122                         res = ntfs_cluster_free_basic(vol,freelcn,
1123                                 (threeparts ? freecnt : freelength));
1124                         if (!res)
1125                                 freed += (threeparts ? freecnt : freelength);
1126                         if (!usedcnt) {
1127                                 holes++;
1128                                 freerl--;
1129                                 freerl->length += (threeparts
1130                                                 ? freecnt : freelength);
1131                                 if (freerl->vcn < *update_from)
1132                                         *update_from = freerl->vcn;
1133                         }
1134                 }
1135                 while (!res && frl->length && (freed < freecnt)) {
1136                         if (frl->length <= (freecnt - freed)) {
1137                                 res = ntfs_cluster_free_basic(vol, frl->lcn,
1138                                                 frl->length);
1139                                 if (!res) {
1140                                         freed += frl->length;
1141                                         frl->lcn = LCN_HOLE;
1142                                         frl->length += carry;
1143                                         carry = 0;
1144                                         holes++;
1145                                 }
1146                         } else {
1147                                 res = ntfs_cluster_free_basic(vol, frl->lcn,
1148                                                 freecnt - freed);
1149                                 if (!res) {
1150                                         frl->lcn += freecnt - freed;
1151                                         frl->vcn += freecnt - freed;
1152                                         frl->length -= freecnt - freed;
1153                                         freed = freecnt;
1154                                 }
1155                         }
1156                         frl++;
1157                 }
1158                 na->compressed_size -= freed << vol->cluster_size_bits;
1159                 switch (holes) {
1160                 case 0 :
1161                         /* there are no hole, must insert one */
1162                         /* space for hole has been prereserved */
1163                         if (freerl->lcn == LCN_HOLE) {
1164                                 if (threeparts) {
1165                                         erl = freerl;
1166                                         while (erl->length)
1167                                                 erl++;
1168                                         do {
1169                                                 erl[2] = *erl;
1170                                         } while (erl-- != freerl);
1171
1172                                         freerl[1].length = freelength - freecnt;
1173                                         freerl->length = freecnt;
1174                                         freerl[1].lcn = freelcn + freecnt;
1175                                         freerl[1].vcn = freevcn + freecnt;
1176                                         freerl[2].lcn = LCN_HOLE;
1177                                         freerl[2].vcn = freerl[1].vcn
1178                                                         + freerl[1].length;
1179                                         freerl->vcn = freevcn;
1180                                 } else {
1181                                         freerl->vcn = freevcn;
1182                                         freerl->length += freelength;
1183                                 }
1184                         } else {
1185                                 erl = freerl;
1186                                 while (erl->length)
1187                                         erl++;
1188                                 if (threeparts) {
1189                                         do {
1190                                                 erl[2] = *erl;
1191                                         } while (erl-- != freerl);
1192                                         freerl[1].lcn = freelcn + freecnt;
1193                                         freerl[1].vcn = freevcn + freecnt;
1194                                         freerl[1].length = oldlength - usedcnt - freecnt;
1195                                 } else {
1196                                         do {
1197                                                 erl[1] = *erl;
1198                                         } while (erl-- != freerl);
1199                                 }
1200                                 freerl->lcn = LCN_HOLE;
1201                                 freerl->vcn = freevcn;
1202                                 freerl->length = freecnt;
1203                         }
1204                         break;
1205                 case 1 :
1206                         /* there is a single hole, may have to merge */
1207                         freerl->vcn = freevcn;
1208                         freerl->length = freecnt;
1209                         if (freerl[1].lcn == LCN_HOLE) {
1210                                 freerl->length += freerl[1].length;
1211                                 erl = freerl;
1212                                 do {
1213                                         erl++;
1214                                         *erl = erl[1];
1215                                 } while (erl->length);
1216                         }
1217                         break;
1218                 default :
1219                         /* there were several holes, must merge them */
1220                         freerl->lcn = LCN_HOLE;
1221                         freerl->vcn = freevcn;
1222                         freerl->length = freecnt;
1223                         if (freerl[holes].lcn == LCN_HOLE) {
1224                                 freerl->length += freerl[holes].length;
1225                                 holes++;
1226                         }
1227                         erl = freerl;
1228                         do {
1229                                 erl++;
1230                                 *erl = erl[holes - 1];
1231                         } while (erl->length);
1232                         break;
1233                 }
1234         } else {
1235                 s32 freed;
1236                 runlist_element *frl;
1237                 runlist_element *xrl;
1238
1239                 freed = 0;
1240                 frl = freerl--;
1241                 if (freerl->vcn < *update_from)
1242                         *update_from = freerl->vcn;
1243                 while (!res && frl->length && (freed < freecnt)) {
1244                         if (frl->length <= (freecnt - freed)) {
1245                                 freerl->length += frl->length;
1246                                 freed += frl->length;
1247                                 res = ntfs_cluster_free_basic(vol, frl->lcn,
1248                                                 frl->length);
1249                                 frl++;
1250                         } else {
1251                                 freerl->length += freecnt - freed;
1252                                 res = ntfs_cluster_free_basic(vol, frl->lcn,
1253                                                 freecnt - freed);
1254                                 frl->lcn += freecnt - freed;
1255                                 frl->vcn += freecnt - freed;
1256                                 frl->length -= freecnt - freed;
1257                                 freed = freecnt;
1258                         }
1259                 }
1260                         /* remove unneded runlist entries */
1261                 xrl = freerl;
1262                         /* group with next run if also a hole */
1263                 if (frl->length && (frl->lcn == LCN_HOLE)) {
1264                         xrl->length += frl->length;
1265                         frl++;
1266                 }
1267                 while (frl->length) {
1268                         *++xrl = *frl++;
1269                 }
1270                 *++xrl = *frl; /* terminator */
1271         na->compressed_size -= freed << vol->cluster_size_bits;
1272         }
1273         return (res);
1274 }
1275
1276
1277 /*
1278  *              Free unneeded clusters after compression
1279  *
1280  *      This generally requires one or two empty slots at the end of runlist,
1281  *      but we do not want to reallocate the runlist here because
1282  *      there are many pointers to it.
1283  *      So the empty slots have to be reserved beforehand
1284  *
1285  *      Returns zero unless some error occurred (described by errno)
1286  */
1287
1288 static int ntfs_compress_free(ntfs_attr *na, runlist_element *rl,
1289                                 s64 used, s64 reserved, BOOL appending,
1290                                 VCN *update_from)
1291 {
1292         s32 freecnt;
1293         s32 usedcnt;
1294         int res;
1295         s64 freelcn;
1296         s64 freevcn;
1297         s32 freelength;
1298         BOOL mergeholes;
1299         BOOL beginhole;
1300         ntfs_volume *vol;
1301         runlist_element *freerl;
1302
1303         res = -1; /* default return */
1304         vol = na->ni->vol;
1305         freecnt = (reserved - used) >> vol->cluster_size_bits;
1306         usedcnt = (reserved >> vol->cluster_size_bits) - freecnt;
1307         if (rl->vcn < *update_from)
1308                 *update_from = rl->vcn;
1309                 /* skip entries fully used, if any */
1310         while (rl->length && (rl->length < usedcnt)) {
1311                 usedcnt -= rl->length; /* must be > 0 */
1312                 rl++;
1313         }
1314         if (rl->length) {
1315                 /*
1316                  * Splitting the current allocation block requires
1317                  * an extra runlist element to create the hole.
1318                  * The required entry has been prereserved when
1319                  * mapping the runlist.
1320                  */
1321                         /* get the free part in initial run */
1322                 freelcn = rl->lcn + usedcnt;
1323                 freevcn = rl->vcn + usedcnt;
1324                         /* new count of allocated clusters */
1325                 if (!((freevcn + freecnt)
1326                             & (na->compression_block_clusters - 1))) {
1327                         if (!appending)
1328                                 res = ntfs_compress_overwr_free(na,rl,
1329                                                 usedcnt,freecnt,update_from);
1330                         else {
1331                                 freelength = rl->length - usedcnt;
1332                                 beginhole = !usedcnt && !rl->vcn;
1333                                 mergeholes = !usedcnt
1334                                                 && rl[0].vcn
1335                                                 && (rl[-1].lcn == LCN_HOLE);
1336                                 if (mergeholes) {
1337                                         s32 carry;
1338
1339                                 /* shorten the runs which have free space */
1340                                         carry = freecnt;
1341                                         freerl = rl;
1342                                         while (freerl->length < carry) {
1343                                                 carry -= freerl->length;
1344                                                 freerl++;
1345                                         }
1346                                         freerl->length = carry;
1347                                         freerl = rl;
1348                                 } else {
1349                                         rl->length = usedcnt; /* can be zero ? */
1350                                         freerl = ++rl;
1351                                 }
1352                                 if ((freelength > 0)
1353                                     && !mergeholes
1354                                     && (usedcnt || beginhole)) {
1355                                 /*
1356                                  * move the unused part to the end. Doing so,
1357                                  * the vcn will be out of order. This does
1358                                  * not harm, the vcn are meaningless now, and
1359                                  * only the lcn are meaningful for freeing.
1360                                  */
1361                                         /* locate current end */
1362                                         while (rl->length)
1363                                                 rl++;
1364                                         /* new terminator relocated */
1365                                         rl[1].vcn = rl->vcn;
1366                                         rl[1].lcn = LCN_ENOENT;
1367                                         rl[1].length = 0;
1368                                         /* hole, currently allocated */
1369                                         rl->vcn = freevcn;
1370                                         rl->lcn = freelcn;
1371                                         rl->length = freelength;
1372                                 } else {
1373         /* why is this different from the begin hole case ? */
1374                                         if ((freelength > 0)
1375                                             && !mergeholes
1376                                             && !usedcnt) {
1377                                                 freerl--;
1378                                                 freerl->length = freelength;
1379                                                 if (freerl->vcn < *update_from)
1380                                                         *update_from
1381                                                                 = freerl->vcn;
1382                                         }
1383                                 }
1384                                 /* free the hole */
1385                                 res = ntfs_cluster_free_from_rl(vol,freerl);
1386                                 if (!res) {
1387                                         na->compressed_size -= freecnt
1388                                                 << vol->cluster_size_bits;
1389                                         if (mergeholes) {
1390                                                 /* merge with adjacent hole */
1391                                                 freerl--;
1392                                                 freerl->length += freecnt;
1393                                         } else {
1394                                                 if (beginhole)
1395                                                         freerl--;
1396                                                 /* mark hole as free */
1397                                                 freerl->lcn = LCN_HOLE;
1398                                                 freerl->vcn = freevcn;
1399                                                 freerl->length = freecnt;
1400                                         }
1401                                         if (freerl->vcn < *update_from)
1402                                                 *update_from = freerl->vcn;
1403                                                 /* and set up the new end */
1404                                         freerl[1].lcn = LCN_ENOENT;
1405                                         freerl[1].vcn = freevcn + freecnt;
1406                                         freerl[1].length = 0;
1407                                 }
1408                         }
1409                 } else {
1410                         ntfs_log_error("Bad end of a compression block set\n");
1411                         errno = EIO;
1412                 }
1413         } else {
1414                 ntfs_log_error("No cluster to free after compression\n");
1415                 errno = EIO;
1416         }
1417         return (res);
1418 }
1419
1420 /*
1421  *              Read existing data, decompress and append buffer
1422  *      Do nothing if something fails
1423  */
1424
1425 static int ntfs_read_append(ntfs_attr *na, const runlist_element *rl,
1426                         s64 offs, u32 compsz, s32 pos, BOOL appending,
1427                         char *outbuf, s64 to_write, const void *b)
1428 {
1429         int fail = 1;
1430         char *compbuf;
1431         u32 decompsz;
1432         u32 got;
1433
1434         if (compsz == na->compression_block_size) {
1435                         /* if the full block was requested, it was a hole */
1436                 memset(outbuf,0,compsz);
1437                 memcpy(&outbuf[pos],b,to_write);
1438                 fail = 0;
1439         } else {
1440                 compbuf = (char*)ntfs_malloc(compsz);
1441                 if (compbuf) {
1442                         /* must align to full block for decompression */
1443                         if (appending)
1444                                 decompsz = ((pos - 1) | (NTFS_SB_SIZE - 1)) + 1;
1445                         else
1446                                 decompsz = na->compression_block_size;
1447                         got = read_clusters(na->ni->vol, rl, offs,
1448                                         compsz, compbuf);
1449                         if ((got == compsz)
1450                             && !ntfs_decompress((u8*)outbuf,decompsz,
1451                                         (u8*)compbuf,compsz)) {
1452                                 memcpy(&outbuf[pos],b,to_write);
1453                                 fail = 0;
1454                         }
1455                         free(compbuf);
1456                 }
1457         }
1458         return (fail);
1459 }
1460
1461 /*
1462  *              Flush a full compression block
1463  *
1464  *      returns the size actually written (rounded to a full cluster)
1465  *              or 0 if could not compress (and written uncompressed)
1466  *              or -1 if there were an irrecoverable error (errno set)
1467  */
1468
1469 static s32 ntfs_flush(ntfs_attr *na, runlist_element *rl, s64 offs,
1470                         const char *outbuf, s32 count, BOOL compress,
1471                         BOOL appending, VCN *update_from)
1472 {
1473         s32 rounded;
1474         s32 written;
1475         int clsz;
1476
1477         if (compress) {
1478                 written = ntfs_comp_set(na, rl, offs, count, outbuf);
1479                 if (written == -1)
1480                         compress = FALSE;
1481                 if ((written >= 0)
1482                    && ntfs_compress_free(na,rl,offs + written,
1483                                 offs + na->compression_block_size, appending,
1484                                 update_from))
1485                         written = -1;
1486         } else
1487                 written = 0;
1488         if (!compress) {
1489                 clsz = 1 << na->ni->vol->cluster_size_bits;
1490                 rounded = ((count - 1) | (clsz - 1)) + 1;
1491                 written = write_clusters(na->ni->vol, rl,
1492                                 offs, rounded, outbuf);
1493                 if (written != rounded)
1494                         written = -1;
1495         }
1496         return (written);
1497 }
1498
1499 /*
1500  *              Write some data to be compressed.
1501  *      Compression only occurs when a few clusters (usually 16) are
1502  *      full. When this occurs an extra runlist slot may be needed, so
1503  *      it has to be reserved beforehand.
1504  *
1505  *      Returns the size of uncompressed data written,
1506  *              or negative if an error occurred.
1507  *      When the returned size is less than requested, new clusters have
1508  *      to be allocated before the function is called again.
1509  */
1510
1511 s64 ntfs_compressed_pwrite(ntfs_attr *na, runlist_element *wrl, s64 wpos,
1512                                 s64 offs, s64 to_write, s64 rounded,
1513                                 const void *b, int compressed_part,
1514                                 VCN *update_from)
1515 {
1516         ntfs_volume *vol;
1517         runlist_element *brl; /* entry containing the beginning of block */
1518         int compression_length;
1519         s64 written;
1520         s64 to_read;
1521         s64 to_flush;
1522         s64 roffs;
1523         s64 got;
1524         s64 start_vcn;
1525         s64 nextblock;
1526         s64 endwrite;
1527         u32 compsz;
1528         char *inbuf;
1529         char *outbuf;
1530         BOOL fail;
1531         BOOL done;
1532         BOOL compress;
1533         BOOL appending;
1534
1535         if (!valid_compressed_run(na,wrl,FALSE,"begin compressed write")) {
1536                 return (-1);
1537         }
1538         if ((*update_from < 0)
1539             || (compressed_part < 0)
1540             || (compressed_part > (int)na->compression_block_clusters)) {
1541                 ntfs_log_error("Bad update vcn or compressed_part %d for compressed write\n",
1542                         compressed_part);
1543                 errno = EIO;
1544                 return (-1);
1545         }
1546                 /* make sure there are two unused entries in runlist */
1547         if (na->unused_runs < 2) {
1548                 ntfs_log_error("No unused runs for compressed write\n");
1549                 errno = EIO;
1550                 return (-1);
1551         }
1552         if (wrl->vcn < *update_from)
1553                 *update_from = wrl->vcn;
1554         written = -1; /* default return */
1555         vol = na->ni->vol;
1556         compression_length = na->compression_block_clusters;
1557         compress = FALSE;
1558         done = FALSE;
1559                 /*
1560                  * Cannot accept writing beyond the current compression set
1561                  * because when compression occurs, clusters are freed
1562                  * and have to be reallocated.
1563                  * (cannot happen with standard fuse 4K buffers)
1564                  * Caller has to avoid this situation, or face consequences.
1565                  */
1566         nextblock = ((offs + (wrl->vcn << vol->cluster_size_bits))
1567                         | (na->compression_block_size - 1)) + 1;
1568                 /* determine whether we are appending to file */
1569         endwrite = offs + to_write + (wrl->vcn << vol->cluster_size_bits);
1570         appending = endwrite >= na->initialized_size;
1571         if (endwrite >= nextblock) {
1572                         /* it is time to compress */
1573                 compress = TRUE;
1574                         /* only process what we can */
1575                 to_write = rounded = nextblock
1576                         - (offs + (wrl->vcn << vol->cluster_size_bits));
1577         }
1578         start_vcn = 0;
1579         fail = FALSE;
1580         brl = wrl;
1581         roffs = 0;
1582                 /*
1583                  * If we are about to compress or we need to decompress
1584                  * existing data, we have to process a full set of blocks.
1585                  * So relocate the parameters to the beginning of allocation
1586                  * containing the first byte of the set of blocks.
1587                  */
1588         if (compress || compressed_part) {
1589                 /* find the beginning of block */
1590                 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits))
1591                                 & -compression_length;
1592                 if (start_vcn < *update_from)
1593                         *update_from = start_vcn;
1594                 while (brl->vcn && (brl->vcn > start_vcn)) {
1595                         /* jumping back a hole means big trouble */
1596                         if (brl->lcn == (LCN)LCN_HOLE) {
1597                                 ntfs_log_error("jump back over a hole when appending\n");
1598                                 fail = TRUE;
1599                                 errno = EIO;
1600                         }
1601                         brl--;
1602                         offs += brl->length << vol->cluster_size_bits;
1603                 }
1604                 roffs = (start_vcn - brl->vcn) << vol->cluster_size_bits;
1605         }
1606         if (compressed_part && !fail) {
1607                 /*
1608                  * The set of compression blocks contains compressed data
1609                  * (we are reopening an existing file to append to it)
1610                  * Decompress the data and append
1611                  */
1612                 compsz = (s32)compressed_part << vol->cluster_size_bits;
1613                 outbuf = (char*)ntfs_malloc(na->compression_block_size);
1614                 if (outbuf) {
1615                         if (appending) {
1616                                 to_read = offs - roffs;
1617                                 to_flush = to_read + to_write;
1618                         } else {
1619                                 to_read = na->data_size
1620                                         - (brl->vcn << vol->cluster_size_bits);
1621                                 if (to_read > na->compression_block_size)
1622                                         to_read = na->compression_block_size;
1623                                 to_flush = to_read;
1624                         }
1625                         if (!ntfs_read_append(na, brl, roffs, compsz,
1626                                         (s32)(offs - roffs), appending,
1627                                         outbuf, to_write, b)) {
1628                                 written = ntfs_flush(na, brl, roffs,
1629                                         outbuf, to_flush, compress, appending,
1630                                         update_from);
1631                                 if (written >= 0) {
1632                                         written = to_write;
1633                                         done = TRUE;
1634                                 }
1635                         }
1636                 free(outbuf);
1637                 }
1638         } else {
1639                 if (compress && !fail) {
1640                         /*
1641                          * we are filling up a block, read the full set
1642                          * of blocks and compress it
1643                          */
1644                         inbuf = (char*)ntfs_malloc(na->compression_block_size);
1645                         if (inbuf) {
1646                                 to_read = offs - roffs;
1647                                 if (to_read)
1648                                         got = read_clusters(vol, brl, roffs,
1649                                                         to_read, inbuf);
1650                                 else
1651                                         got = 0;
1652                                 if (got == to_read) {
1653                                         memcpy(&inbuf[to_read],b,to_write);
1654                                         written = ntfs_comp_set(na, brl, roffs,
1655                                                 to_read + to_write, inbuf);
1656                                 /*
1657                                  * if compression was not successful,
1658                                  * only write the part which was requested
1659                                  */
1660                                         if ((written >= 0)
1661                                                 /* free the unused clusters */
1662                                           && !ntfs_compress_free(na,brl,
1663                                                     written + roffs,
1664                                                     na->compression_block_size
1665                                                          + roffs,
1666                                                     appending, update_from)) {
1667                                                 done = TRUE;
1668                                                 written = to_write;
1669                                         }
1670                                 }
1671                                 free(inbuf);
1672                         }
1673                 }
1674                 if (!done) {
1675                         /*
1676                          * if the compression block is not full, or
1677                          * if compression failed for whatever reason,
1678                          * write uncompressed
1679                          */
1680                         /* check we are not overflowing current allocation */
1681                         if ((wpos + rounded)
1682                             > ((wrl->lcn + wrl->length)
1683                                  << vol->cluster_size_bits)) {
1684                                 ntfs_log_error("writing on unallocated clusters\n");
1685                                 errno = EIO;
1686                         } else {
1687                                 written = ntfs_pwrite(vol->dev, wpos,
1688                                         rounded, b);
1689                                 if (written == rounded)
1690                                         written = to_write;
1691                         }
1692                 }
1693         }
1694         if ((written >= 0)
1695             && !valid_compressed_run(na,wrl,TRUE,"end compressed write"))
1696                 written = -1;
1697         return (written);
1698 }
1699
1700 /*
1701  *              Close a file written compressed.
1702  *      This compresses the last partial compression block of the file.
1703  *      Two empty runlist slots have to be reserved beforehand.
1704  *
1705  *      Returns zero if closing is successful.
1706  */
1707
1708 int ntfs_compressed_close(ntfs_attr *na, runlist_element *wrl, s64 offs,
1709                         VCN *update_from)
1710 {
1711         ntfs_volume *vol;
1712         runlist_element *brl; /* entry containing the beginning of block */
1713         int compression_length;
1714         s64 written;
1715         s64 to_read;
1716         s64 roffs;
1717         s64 got;
1718         s64 start_vcn;
1719         char *inbuf;
1720         BOOL fail;
1721         BOOL done;
1722
1723         if (na->unused_runs < 2) {
1724                 ntfs_log_error("No unused runs for compressed close\n");
1725                 errno = EIO;
1726                 return (-1);
1727         }
1728         if (*update_from < 0) {
1729                 ntfs_log_error("Bad update vcn for compressed close\n");
1730                 errno = EIO;
1731                 return (-1);
1732         }
1733         if (wrl->vcn < *update_from)
1734                 *update_from = wrl->vcn;
1735         vol = na->ni->vol;
1736         compression_length = na->compression_block_clusters;
1737         done = FALSE;
1738                 /*
1739                  * There generally is an uncompressed block at end of file,
1740                  * read the full block and compress it
1741                  */
1742         inbuf = (char*)ntfs_malloc(na->compression_block_size);
1743         if (inbuf) {
1744                 start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits))
1745                                 & -compression_length;
1746                 if (start_vcn < *update_from)
1747                         *update_from = start_vcn;
1748                 to_read = offs + ((wrl->vcn - start_vcn)
1749                                         << vol->cluster_size_bits);
1750                 brl = wrl;
1751                 fail = FALSE;
1752                 while (brl->vcn && (brl->vcn > start_vcn)) {
1753                         if (brl->lcn == (LCN)LCN_HOLE) {
1754                                 ntfs_log_error("jump back over a hole when closing\n");
1755                                 fail = TRUE;
1756                                 errno = EIO;
1757                         }
1758                         brl--;
1759                 }
1760                 if (!fail) {
1761                         /* roffs can be an offset from another uncomp block */
1762                         roffs = (start_vcn - brl->vcn)
1763                                                 << vol->cluster_size_bits;
1764                         if (to_read) {
1765                                 got = read_clusters(vol, brl, roffs, to_read,
1766                                                  inbuf);
1767                                 if (got == to_read) {
1768                                         written = ntfs_comp_set(na, brl, roffs,
1769                                                         to_read, inbuf);
1770                                         if ((written >= 0)
1771                                         /* free the unused clusters */
1772                                             && !ntfs_compress_free(na,brl,
1773                                                         written + roffs,
1774                                                         na->compression_block_size + roffs,
1775                                                         TRUE, update_from)) {
1776                                                 done = TRUE;
1777                                         } else
1778                                 /* if compression failed, leave uncompressed */
1779                                                 if (written == -1)
1780                                                         done = TRUE;
1781                                 }
1782                         } else
1783                                 done = TRUE;
1784                         free(inbuf);
1785                 }
1786         }
1787         if (done && !valid_compressed_run(na,wrl,TRUE,"end compressed close"))
1788                 done = FALSE;
1789         return (!done);
1790 }