path: root/libntfs-3g/compress.c (plain)
blob: 69b39ed09b8e1815af7bfcca39694a9813f442dc

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-2013 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	u32 decompsz;
738
739	/*
740	* Compressed cb, decompress it into the temporary buffer, then
741	* copy the data to the destination range overlapping the cb.
742	*/
743	ntfs_log_debug("Found compressed compression block.\n");
744	/*
745	* Read the compressed data into the temporary buffer.
746	* NOTE: We cheat a little bit here by marking the attribute as
747	* not compressed in the ntfs_attr structure so that we can
748	* read the raw, compressed data by simply using
749	* ntfs_attr_pread(). (-8
750	* NOTE: We have to modify data_size and initialized_size
751	* temporarily as well...
752	*/
753	to_read = cb_size;
754	NAttrClearCompressed(na);
755	na->data_flags &= ~ATTR_COMPRESSION_MASK;
756	tdata_size = na->data_size;
757	tinitialized_size = na->initialized_size;
758	na->data_size = na->initialized_size = na->allocated_size;
759	do {
760	br = ntfs_attr_pread(na,
761	(vcn << vol->cluster_size_bits) +
762	(cb_pos - cb), to_read, cb_pos);
763	if (br <= 0) {
764	if (!br) {
765	ntfs_log_error("Failed to read a"
766	" compressed cluster, "
767	" inode %lld offs 0x%llx\n",
768	(long long)na->ni->mft_no,
769	(long long)(vcn << vol->cluster_size_bits));
770	errno = EIO;
771	}
772	err = errno;
773	na->data_size = tdata_size;
774	na->initialized_size = tinitialized_size;
775	na->ni->flags |= compression;
776	na->data_flags = data_flags;
777	free(cb);
778	free(dest);
779	if (total)
780	return total;
781	errno = err;
782	return br;
783	}
784	cb_pos += br;
785	to_read -= br;
786	} while (to_read > 0);
787	na->data_size = tdata_size;
788	na->initialized_size = tinitialized_size;
789	na->ni->flags |= compression;
790	na->data_flags = data_flags;
791	/* Just a precaution. */
792	if (cb_pos + 2 <= cb_end)
793	*(u16*)cb_pos = 0;
794	ntfs_log_debug("Successfully read the compression block.\n");
795	/* Do not decompress beyond the requested block */
796	to_read = min(count, cb_size - ofs);
797	decompsz = ((ofs + to_read - 1) | (NTFS_SB_SIZE - 1)) + 1;
798	if (ntfs_decompress(dest, decompsz, cb, cb_size) < 0) {
799	err = errno;
800	free(cb);
801	free(dest);
802	if (total)
803	return total;
804	errno = err;
805	return -1;
806	}
807	memcpy(b, dest + ofs, to_read);
808	total += to_read;
809	count -= to_read;
810	b = (u8*)b + to_read;
811	ofs = 0;
812	}
813	/* Do we have more work to do? */
814	if (nr_cbs)
815	goto do_next_cb;
816	/* We no longer need the buffers. */
817	free(cb);
818	free(dest);
819	/* Return number of bytes read. */
820	return total + total2;
821	}
822
823	/*
824	* Read data from a set of clusters
825	*
826	* Returns the amount of data read
827	*/
828
829	static u32 read_clusters(ntfs_volume *vol, const runlist_element *rl,
830	s64 offs, u32 to_read, char *inbuf)
831	{
832	u32 count;
833	int xgot;
834	u32 got;
835	s64 xpos;
836	BOOL first;
837	char *xinbuf;
838	const runlist_element *xrl;
839
840	got = 0;
841	xrl = rl;
842	xinbuf = inbuf;
843	first = TRUE;
844	do {
845	count = xrl->length << vol->cluster_size_bits;
846	xpos = xrl->lcn << vol->cluster_size_bits;
847	if (first) {
848	count -= offs;
849	xpos += offs;
850	}
851	if ((to_read - got) < count)
852	count = to_read - got;
853	xgot = ntfs_pread(vol->dev, xpos, count, xinbuf);
854	if (xgot == (int)count) {
855	got += count;
856	xpos += count;
857	xinbuf += count;
858	xrl++;
859	}
860	first = FALSE;
861	} while ((xgot == (int)count) && (got < to_read));
862	return (got);
863	}
864
865	/*
866	* Write data to a set of clusters
867	*
868	* Returns the amount of data written
869	*/
870
871	static s32 write_clusters(ntfs_volume *vol, const runlist_element *rl,
872	s64 offs, s32 to_write, const char *outbuf)
873	{
874	s32 count;
875	s32 put, xput;
876	s64 xpos;
877	BOOL first;
878	const char *xoutbuf;
879	const runlist_element *xrl;
880
881	put = 0;
882	xrl = rl;
883	xoutbuf = outbuf;
884	first = TRUE;
885	do {
886	count = xrl->length << vol->cluster_size_bits;
887	xpos = xrl->lcn << vol->cluster_size_bits;
888	if (first) {
889	count -= offs;
890	xpos += offs;
891	}
892	if ((to_write - put) < count)
893	count = to_write - put;
894	xput = ntfs_pwrite(vol->dev, xpos, count, xoutbuf);
895	if (xput == count) {
896	put += count;
897	xpos += count;
898	xoutbuf += count;
899	xrl++;
900	}
901	first = FALSE;
902	} while ((xput == count) && (put < to_write));
903	return (put);
904	}
905
906
907	/*
908	* Compress and write a set of blocks
909	*
910	* returns the size actually written (rounded to a full cluster)
911	* or 0 if all zeroes (nothing is written)
912	* or -1 if could not compress (nothing is written)
913	* or -2 if there were an irrecoverable error (errno set)
914	*/
915
916	static s32 ntfs_comp_set(ntfs_attr *na, runlist_element *rl,
917	s64 offs, u32 insz, const char *inbuf)
918	{
919	ntfs_volume *vol;
920	char *outbuf;
921	char *pbuf;
922	u32 compsz;
923	s32 written;
924	s32 rounded;
925	unsigned int clsz;
926	u32 p;
927	unsigned int sz;
928	unsigned int bsz;
929	BOOL fail;
930	BOOL allzeroes;
931	/* a single compressed zero */
932	static char onezero[] = { 0x01, 0xb0, 0x00, 0x00 } ;
933	/* a couple of compressed zeroes */
934	static char twozeroes[] = { 0x02, 0xb0, 0x00, 0x00, 0x00 } ;
935	/* more compressed zeroes, to be followed by some count */
936	static char morezeroes[] = { 0x03, 0xb0, 0x02, 0x00 } ;
937
938	vol = na->ni->vol;
939	written = -1; /* default return */
940	clsz = 1 << vol->cluster_size_bits;
941	/* may need 2 extra bytes per block and 2 more bytes */
942	outbuf = (char*)ntfs_malloc(na->compression_block_size
943	+ 2*(na->compression_block_size/NTFS_SB_SIZE)
944	+ 2);
945	if (outbuf) {
946	fail = FALSE;
947	compsz = 0;
948	allzeroes = TRUE;
949	for (p=0; (p<insz) && !fail; p+=NTFS_SB_SIZE) {
950	if ((p + NTFS_SB_SIZE) < insz)
951	bsz = NTFS_SB_SIZE;
952	else
953	bsz = insz - p;
954	pbuf = &outbuf[compsz];
955	sz = ntfs_compress_block(&inbuf[p],bsz,pbuf);
956	/* fail if all the clusters (or more) are needed */
957	if (!sz || ((compsz + sz + clsz + 2)
958	> na->compression_block_size))
959	fail = TRUE;
960	else {
961	if (allzeroes) {
962	/* check whether this is all zeroes */
963	switch (sz) {
964	case 4 :
965	allzeroes = !memcmp(
966	pbuf,onezero,4);
967	break;
968	case 5 :
969	allzeroes = !memcmp(
970	pbuf,twozeroes,5);
971	break;
972	case 6 :
973	allzeroes = !memcmp(
974	pbuf,morezeroes,4);
975	break;
976	default :
977	allzeroes = FALSE;
978	break;
979	}
980	}
981	compsz += sz;
982	}
983	}
984	if (!fail && !allzeroes) {
985	/* add a couple of null bytes, space has been checked */
986	outbuf[compsz++] = 0;
987	outbuf[compsz++] = 0;
988	/* write a full cluster, to avoid partial reading */
989	rounded = ((compsz - 1) | (clsz - 1)) + 1;
990	written = write_clusters(vol, rl, offs, rounded, outbuf);
991	if (written != rounded) {
992	/*
993	* TODO : previously written text has been
994	* spoilt, should return a specific error
995	*/
996	ntfs_log_error("error writing compressed data\n");
997	errno = EIO;
998	written = -2;
999	}
1000	} else
1001	if (!fail)
1002	written = 0;
1003	free(outbuf);
1004	}
1005	return (written);
1006	}
1007
1008	/*
1009	* Check the validity of a compressed runlist
1010	* The check starts at the beginning of current run and ends
1011	* at the end of runlist
1012	* errno is set if the runlist is not valid
1013	*/
1014
1015	static BOOL valid_compressed_run(ntfs_attr *na, runlist_element *rl,
1016	BOOL fullcheck, const char *text)
1017	{
1018	runlist_element *xrl;
1019	const char *err;
1020	BOOL ok = TRUE;
1021
1022	xrl = rl;
1023	while (xrl->vcn & (na->compression_block_clusters - 1))
1024	xrl--;
1025	err = (const char*)NULL;
1026	while (xrl->length) {
1027	if ((xrl->vcn + xrl->length) != xrl[1].vcn)
1028	err = "Runs not adjacent";
1029	if (xrl->lcn == LCN_HOLE) {
1030	if ((xrl->vcn + xrl->length)
1031	& (na->compression_block_clusters - 1)) {
1032	err = "Invalid hole";
1033	}
1034	if (fullcheck && (xrl[1].lcn == LCN_HOLE)) {
1035	err = "Adjacent holes";
1036	}
1037	}
1038	if (err) {
1039	ntfs_log_error("%s at %s index %ld inode %lld\n",
1040	err, text, (long)(xrl - na->rl),
1041	(long long)na->ni->mft_no);
1042	errno = EIO;
1043	ok = FALSE;
1044	err = (const char*)NULL;
1045	}
1046	xrl++;
1047	}
1048	return (ok);
1049	}
1050
1051	/*
1052	* Free unneeded clusters after overwriting compressed data
1053	*
1054	* This generally requires one or two empty slots at the end of runlist,
1055	* but we do not want to reallocate the runlist here because
1056	* there are many pointers to it.
1057	* So the empty slots have to be reserved beforehand
1058	*
1059	* Returns zero unless some error occurred (described by errno)
1060	*
1061	* +======= start of block =====+
1062	* 0 |A chunk may overflow | <-- rl usedcnt : A + B
1063	* |A on previous block | then B
1064	* |A |
1065	* +-- end of allocated chunk --+ freelength : C
1066	* |B | (incl overflow)
1067	* +== end of compressed data ==+
1068	* |C | <-- freerl freecnt : C + D
1069	* |C chunk may overflow |
1070	* |C on next block |
1071	* +-- end of allocated chunk --+
1072	* |D |
1073	* |D chunk may overflow |
1074	* 15 |D on next block |
1075	* +======== end of block ======+
1076	*
1077	*/
1078
1079	static int ntfs_compress_overwr_free(ntfs_attr *na, runlist_element *rl,
1080	s32 usedcnt, s32 freecnt, VCN *update_from)
1081	{
1082	BOOL beginhole;
1083	BOOL mergeholes;
1084	s32 oldlength;
1085	s32 freelength;
1086	s64 freelcn;
1087	s64 freevcn;
1088	runlist_element *freerl;
1089	ntfs_volume *vol;
1090	s32 carry;
1091	int res;
1092
1093	vol = na->ni->vol;
1094	res = 0;
1095	freelcn = rl->lcn + usedcnt;
1096	freevcn = rl->vcn + usedcnt;
1097	freelength = rl->length - usedcnt;
1098	beginhole = !usedcnt && !rl->vcn;
1099	/* can merge with hole before ? */
1100	mergeholes = !usedcnt
1101	&& rl[0].vcn
1102	&& (rl[-1].lcn == LCN_HOLE);
1103	/* truncate current run, carry to subsequent hole */
1104	carry = freelength;
1105	oldlength = rl->length;
1106	if (mergeholes) {
1107	/* merging with a hole before */
1108	freerl = rl;
1109	} else {
1110	rl->length -= freelength; /* warning : can be zero */
1111	freerl = ++rl;
1112	}
1113	if (!mergeholes && (usedcnt || beginhole)) {
1114	s32 freed;
1115	runlist_element *frl;
1116	runlist_element *erl;
1117	int holes = 0;
1118	BOOL threeparts;
1119
1120	/* free the unneeded clusters from initial run, then freerl */
1121	threeparts = (freelength > freecnt);
1122	freed = 0;
1123	frl = freerl;
1124	if (freelength) {
1125	res = ntfs_cluster_free_basic(vol,freelcn,
1126	(threeparts ? freecnt : freelength));
1127	if (!res)
1128	freed += (threeparts ? freecnt : freelength);
1129	if (!usedcnt) {
1130	holes++;
1131	freerl--;
1132	freerl->length += (threeparts
1133	? freecnt : freelength);
1134	if (freerl->vcn < *update_from)
1135	*update_from = freerl->vcn;
1136	}
1137	}
1138	while (!res && frl->length && (freed < freecnt)) {
1139	if (frl->length <= (freecnt - freed)) {
1140	res = ntfs_cluster_free_basic(vol, frl->lcn,
1141	frl->length);
1142	if (!res) {
1143	freed += frl->length;
1144	frl->lcn = LCN_HOLE;
1145	frl->length += carry;
1146	carry = 0;
1147	holes++;
1148	}
1149	} else {
1150	res = ntfs_cluster_free_basic(vol, frl->lcn,
1151	freecnt - freed);
1152	if (!res) {
1153	frl->lcn += freecnt - freed;
1154	frl->vcn += freecnt - freed;
1155	frl->length -= freecnt - freed;
1156	freed = freecnt;
1157	}
1158	}
1159	frl++;
1160	}
1161	na->compressed_size -= freed << vol->cluster_size_bits;
1162	switch (holes) {
1163	case 0 :
1164	/* there are no hole, must insert one */
1165	/* space for hole has been prereserved */
1166	if (freerl->lcn == LCN_HOLE) {
1167	if (threeparts) {
1168	erl = freerl;
1169	while (erl->length)
1170	erl++;
1171	do {
1172	erl[2] = *erl;
1173	} while (erl-- != freerl);
1174
1175	freerl[1].length = freelength - freecnt;
1176	freerl->length = freecnt;
1177	freerl[1].lcn = freelcn + freecnt;
1178	freerl[1].vcn = freevcn + freecnt;
1179	freerl[2].lcn = LCN_HOLE;
1180	freerl[2].vcn = freerl[1].vcn
1181	+ freerl[1].length;
1182	freerl->vcn = freevcn;
1183	} else {
1184	freerl->vcn = freevcn;
1185	freerl->length += freelength;
1186	}
1187	} else {
1188	erl = freerl;
1189	while (erl->length)
1190	erl++;
1191	if (threeparts) {
1192	do {
1193	erl[2] = *erl;
1194	} while (erl-- != freerl);
1195	freerl[1].lcn = freelcn + freecnt;
1196	freerl[1].vcn = freevcn + freecnt;
1197	freerl[1].length = oldlength - usedcnt - freecnt;
1198	} else {
1199	do {
1200	erl[1] = *erl;
1201	} while (erl-- != freerl);
1202	}
1203	freerl->lcn = LCN_HOLE;
1204	freerl->vcn = freevcn;
1205	freerl->length = freecnt;
1206	}
1207	break;
1208	case 1 :
1209	/* there is a single hole, may have to merge */
1210	freerl->vcn = freevcn;
1211	freerl->length = freecnt;
1212	if (freerl[1].lcn == LCN_HOLE) {
1213	freerl->length += freerl[1].length;
1214	erl = freerl;
1215	do {
1216	erl++;
1217	*erl = erl[1];
1218	} while (erl->length);
1219	}
1220	break;
1221	default :
1222	/* there were several holes, must merge them */
1223	freerl->lcn = LCN_HOLE;
1224	freerl->vcn = freevcn;
1225	freerl->length = freecnt;
1226	if (freerl[holes].lcn == LCN_HOLE) {
1227	freerl->length += freerl[holes].length;
1228	holes++;
1229	}
1230	erl = freerl;
1231	do {
1232	erl++;
1233	*erl = erl[holes - 1];
1234	} while (erl->length);
1235	break;
1236	}
1237	} else {
1238	s32 freed;
1239	runlist_element *frl;
1240	runlist_element *xrl;
1241
1242	freed = 0;
1243	frl = freerl--;
1244	if (freerl->vcn < *update_from)
1245	*update_from = freerl->vcn;
1246	while (!res && frl->length && (freed < freecnt)) {
1247	if (frl->length <= (freecnt - freed)) {
1248	freerl->length += frl->length;
1249	freed += frl->length;
1250	res = ntfs_cluster_free_basic(vol, frl->lcn,
1251	frl->length);
1252	frl++;
1253	} else {
1254	freerl->length += freecnt - freed;
1255	res = ntfs_cluster_free_basic(vol, frl->lcn,
1256	freecnt - freed);
1257	frl->lcn += freecnt - freed;
1258	frl->vcn += freecnt - freed;
1259	frl->length -= freecnt - freed;
1260	freed = freecnt;
1261	}
1262	}
1263	/* remove unneded runlist entries */
1264	xrl = freerl;
1265	/* group with next run if also a hole */
1266	if (frl->length && (frl->lcn == LCN_HOLE)) {
1267	xrl->length += frl->length;
1268	frl++;
1269	}
1270	while (frl->length) {
1271	*++xrl = *frl++;
1272	}
1273	*++xrl = *frl; /* terminator */
1274	na->compressed_size -= freed << vol->cluster_size_bits;
1275	}
1276	return (res);
1277	}
1278
1279
1280	/*
1281	* Free unneeded clusters after compression
1282	*
1283	* This generally requires one or two empty slots at the end of runlist,
1284	* but we do not want to reallocate the runlist here because
1285	* there are many pointers to it.
1286	* So the empty slots have to be reserved beforehand
1287	*
1288	* Returns zero unless some error occurred (described by errno)
1289	*/
1290
1291	static int ntfs_compress_free(ntfs_attr *na, runlist_element *rl,
1292	s64 used, s64 reserved, BOOL appending,
1293	VCN *update_from)
1294	{
1295	s32 freecnt;
1296	s32 usedcnt;
1297	int res;
1298	s64 freelcn;
1299	s64 freevcn;
1300	s32 freelength;
1301	BOOL mergeholes;
1302	BOOL beginhole;
1303	ntfs_volume *vol;
1304	runlist_element *freerl;
1305
1306	res = -1; /* default return */
1307	vol = na->ni->vol;
1308	freecnt = (reserved - used) >> vol->cluster_size_bits;
1309	usedcnt = (reserved >> vol->cluster_size_bits) - freecnt;
1310	if (rl->vcn < *update_from)
1311	*update_from = rl->vcn;
1312	/* skip entries fully used, if any */
1313	while (rl->length && (rl->length < usedcnt)) {
1314	usedcnt -= rl->length; /* must be > 0 */
1315	rl++;
1316	}
1317	if (rl->length) {
1318	/*
1319	* Splitting the current allocation block requires
1320	* an extra runlist element to create the hole.
1321	* The required entry has been prereserved when
1322	* mapping the runlist.
1323	*/
1324	/* get the free part in initial run */
1325	freelcn = rl->lcn + usedcnt;
1326	freevcn = rl->vcn + usedcnt;
1327	/* new count of allocated clusters */
1328	if (!((freevcn + freecnt)
1329	& (na->compression_block_clusters - 1))) {
1330	if (!appending)
1331	res = ntfs_compress_overwr_free(na,rl,
1332	usedcnt,freecnt,update_from);
1333	else {
1334	freelength = rl->length - usedcnt;
1335	beginhole = !usedcnt && !rl->vcn;
1336	mergeholes = !usedcnt
1337	&& rl[0].vcn
1338	&& (rl[-1].lcn == LCN_HOLE);
1339	if (mergeholes) {
1340	s32 carry;
1341
1342	/* shorten the runs which have free space */
1343	carry = freecnt;
1344	freerl = rl;
1345	while (freerl->length < carry) {
1346	carry -= freerl->length;
1347	freerl++;
1348	}
1349	freerl->length = carry;
1350	freerl = rl;
1351	} else {
1352	rl->length = usedcnt; /* can be zero ? */
1353	freerl = ++rl;
1354	}
1355	if ((freelength > 0)
1356	&& !mergeholes
1357	&& (usedcnt || beginhole)) {
1358	/*
1359	* move the unused part to the end. Doing so,
1360	* the vcn will be out of order. This does
1361	* not harm, the vcn are meaningless now, and
1362	* only the lcn are meaningful for freeing.
1363	*/
1364	/* locate current end */
1365	while (rl->length)
1366	rl++;
1367	/* new terminator relocated */
1368	rl[1].vcn = rl->vcn;
1369	rl[1].lcn = LCN_ENOENT;
1370	rl[1].length = 0;
1371	/* hole, currently allocated */
1372	rl->vcn = freevcn;
1373	rl->lcn = freelcn;
1374	rl->length = freelength;
1375	} else {
1376	/* why is this different from the begin hole case ? */
1377	if ((freelength > 0)
1378	&& !mergeholes
1379	&& !usedcnt) {
1380	freerl--;
1381	freerl->length = freelength;
1382	if (freerl->vcn < *update_from)
1383	*update_from
1384	= freerl->vcn;
1385	}
1386	}
1387	/* free the hole */
1388	res = ntfs_cluster_free_from_rl(vol,freerl);
1389	if (!res) {
1390	na->compressed_size -= freecnt
1391	<< vol->cluster_size_bits;
1392	if (mergeholes) {
1393	/* merge with adjacent hole */
1394	freerl--;
1395	freerl->length += freecnt;
1396	} else {
1397	if (beginhole)
1398	freerl--;
1399	/* mark hole as free */
1400	freerl->lcn = LCN_HOLE;
1401	freerl->vcn = freevcn;
1402	freerl->length = freecnt;
1403	}
1404	if (freerl->vcn < *update_from)
1405	*update_from = freerl->vcn;
1406	/* and set up the new end */
1407	freerl[1].lcn = LCN_ENOENT;
1408	freerl[1].vcn = freevcn + freecnt;
1409	freerl[1].length = 0;
1410	}
1411	}
1412	} else {
1413	ntfs_log_error("Bad end of a compression block set\n");
1414	errno = EIO;
1415	}
1416	} else {
1417	ntfs_log_error("No cluster to free after compression\n");
1418	errno = EIO;
1419	}
1420	return (res);
1421	}
1422
1423	/*
1424	* Read existing data, decompress and append buffer
1425	* Do nothing if something fails
1426	*/
1427
1428	static int ntfs_read_append(ntfs_attr *na, const runlist_element *rl,
1429	s64 offs, u32 compsz, s32 pos, BOOL appending,
1430	char *outbuf, s64 to_write, const void *b)
1431	{
1432	int fail = 1;
1433	char *compbuf;
1434	u32 decompsz;
1435	u32 got;
1436
1437	if (compsz == na->compression_block_size) {
1438	/* if the full block was requested, it was a hole */
1439	memset(outbuf,0,compsz);
1440	memcpy(&outbuf[pos],b,to_write);
1441	fail = 0;
1442	} else {
1443	compbuf = (char*)ntfs_malloc(compsz);
1444	if (compbuf) {
1445	/* must align to full block for decompression */
1446	if (appending)
1447	decompsz = ((pos - 1) | (NTFS_SB_SIZE - 1)) + 1;
1448	else
1449	decompsz = na->compression_block_size;
1450	got = read_clusters(na->ni->vol, rl, offs,
1451	compsz, compbuf);
1452	if ((got == compsz)
1453	&& !ntfs_decompress((u8*)outbuf,decompsz,
1454	(u8*)compbuf,compsz)) {
1455	memcpy(&outbuf[pos],b,to_write);
1456	fail = 0;
1457	}
1458	free(compbuf);
1459	}
1460	}
1461	return (fail);
1462	}
1463
1464	/*
1465	* Flush a full compression block
1466	*
1467	* returns the size actually written (rounded to a full cluster)
1468	* or 0 if could not compress (and written uncompressed)
1469	* or -1 if there were an irrecoverable error (errno set)
1470	*/
1471
1472	static s32 ntfs_flush(ntfs_attr *na, runlist_element *rl, s64 offs,
1473	const char *outbuf, s32 count, BOOL compress,
1474	BOOL appending, VCN *update_from)
1475	{
1476	s32 rounded;
1477	s32 written;
1478	int clsz;
1479
1480	if (compress) {
1481	written = ntfs_comp_set(na, rl, offs, count, outbuf);
1482	if (written == -1)
1483	compress = FALSE;
1484	if ((written >= 0)
1485	&& ntfs_compress_free(na,rl,offs + written,
1486	offs + na->compression_block_size, appending,
1487	update_from))
1488	written = -1;
1489	} else
1490	written = 0;
1491	if (!compress) {
1492	clsz = 1 << na->ni->vol->cluster_size_bits;
1493	rounded = ((count - 1) | (clsz - 1)) + 1;
1494	written = write_clusters(na->ni->vol, rl,
1495	offs, rounded, outbuf);
1496	if (written != rounded)
1497	written = -1;
1498	}
1499	return (written);
1500	}
1501
1502	/*
1503	* Write some data to be compressed.
1504	* Compression only occurs when a few clusters (usually 16) are
1505	* full. When this occurs an extra runlist slot may be needed, so
1506	* it has to be reserved beforehand.
1507	*
1508	* Returns the size of uncompressed data written,
1509	* or negative if an error occurred.
1510	* When the returned size is less than requested, new clusters have
1511	* to be allocated before the function is called again.
1512	*/
1513
1514	s64 ntfs_compressed_pwrite(ntfs_attr *na, runlist_element *wrl, s64 wpos,
1515	s64 offs, s64 to_write, s64 rounded,
1516	const void *b, int compressed_part,
1517	VCN *update_from)
1518	{
1519	ntfs_volume *vol;
1520	runlist_element *brl; /* entry containing the beginning of block */
1521	int compression_length;
1522	s64 written;
1523	s64 to_read;
1524	s64 to_flush;
1525	s64 roffs;
1526	s64 got;
1527	s64 start_vcn;
1528	s64 nextblock;
1529	s64 endwrite;
1530	u32 compsz;
1531	char *inbuf;
1532	char *outbuf;
1533	BOOL fail;
1534	BOOL done;
1535	BOOL compress;
1536	BOOL appending;
1537
1538	if (!valid_compressed_run(na,wrl,FALSE,"begin compressed write")) {
1539	return (-1);
1540	}
1541	if ((*update_from < 0)
1542	|| (compressed_part < 0)
1543	|| (compressed_part > (int)na->compression_block_clusters)) {
1544	ntfs_log_error("Bad update vcn or compressed_part %d for compressed write\n",
1545	compressed_part);
1546	errno = EIO;
1547	return (-1);
1548	}
1549	/* make sure there are two unused entries in runlist */
1550	if (na->unused_runs < 2) {
1551	ntfs_log_error("No unused runs for compressed write\n");
1552	errno = EIO;
1553	return (-1);
1554	}
1555	if (wrl->vcn < *update_from)
1556	*update_from = wrl->vcn;
1557	written = -1; /* default return */
1558	vol = na->ni->vol;
1559	compression_length = na->compression_block_clusters;
1560	compress = FALSE;
1561	done = FALSE;
1562	/*
1563	* Cannot accept writing beyond the current compression set
1564	* because when compression occurs, clusters are freed
1565	* and have to be reallocated.
1566	* (cannot happen with standard fuse 4K buffers)
1567	* Caller has to avoid this situation, or face consequences.
1568	*/
1569	nextblock = ((offs + (wrl->vcn << vol->cluster_size_bits))
1570	| (na->compression_block_size - 1)) + 1;
1571	/* determine whether we are appending to file */
1572	endwrite = offs + to_write + (wrl->vcn << vol->cluster_size_bits);
1573	appending = endwrite >= na->initialized_size;
1574	if (endwrite >= nextblock) {
1575	/* it is time to compress */
1576	compress = TRUE;
1577	/* only process what we can */
1578	to_write = rounded = nextblock
1579	- (offs + (wrl->vcn << vol->cluster_size_bits));
1580	}
1581	start_vcn = 0;
1582	fail = FALSE;
1583	brl = wrl;
1584	roffs = 0;
1585	/*
1586	* If we are about to compress or we need to decompress
1587	* existing data, we have to process a full set of blocks.
1588	* So relocate the parameters to the beginning of allocation
1589	* containing the first byte of the set of blocks.
1590	*/
1591	if (compress || compressed_part) {
1592	/* find the beginning of block */
1593	start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits))
1594	& -compression_length;
1595	if (start_vcn < *update_from)
1596	*update_from = start_vcn;
1597	while (brl->vcn && (brl->vcn > start_vcn)) {
1598	/* jumping back a hole means big trouble */
1599	if (brl->lcn == (LCN)LCN_HOLE) {
1600	ntfs_log_error("jump back over a hole when appending\n");
1601	fail = TRUE;
1602	errno = EIO;
1603	}
1604	brl--;
1605	offs += brl->length << vol->cluster_size_bits;
1606	}
1607	roffs = (start_vcn - brl->vcn) << vol->cluster_size_bits;
1608	}
1609	if (compressed_part && !fail) {
1610	/*
1611	* The set of compression blocks contains compressed data
1612	* (we are reopening an existing file to append to it)
1613	* Decompress the data and append
1614	*/
1615	compsz = (s32)compressed_part << vol->cluster_size_bits;
1616	outbuf = (char*)ntfs_malloc(na->compression_block_size);
1617	if (outbuf) {
1618	if (appending) {
1619	to_read = offs - roffs;
1620	to_flush = to_read + to_write;
1621	} else {
1622	to_read = na->data_size
1623	- (brl->vcn << vol->cluster_size_bits);
1624	if (to_read > na->compression_block_size)
1625	to_read = na->compression_block_size;
1626	to_flush = to_read;
1627	}
1628	if (!ntfs_read_append(na, brl, roffs, compsz,
1629	(s32)(offs - roffs), appending,
1630	outbuf, to_write, b)) {
1631	written = ntfs_flush(na, brl, roffs,
1632	outbuf, to_flush, compress, appending,
1633	update_from);
1634	if (written >= 0) {
1635	written = to_write;
1636	done = TRUE;
1637	}
1638	}
1639	free(outbuf);
1640	}
1641	} else {
1642	if (compress && !fail) {
1643	/*
1644	* we are filling up a block, read the full set
1645	* of blocks and compress it
1646	*/
1647	inbuf = (char*)ntfs_malloc(na->compression_block_size);
1648	if (inbuf) {
1649	to_read = offs - roffs;
1650	if (to_read)
1651	got = read_clusters(vol, brl, roffs,
1652	to_read, inbuf);
1653	else
1654	got = 0;
1655	if (got == to_read) {
1656	memcpy(&inbuf[to_read],b,to_write);
1657	written = ntfs_comp_set(na, brl, roffs,
1658	to_read + to_write, inbuf);
1659	/*
1660	* if compression was not successful,
1661	* only write the part which was requested
1662	*/
1663	if ((written >= 0)
1664	/* free the unused clusters */
1665	&& !ntfs_compress_free(na,brl,
1666	written + roffs,
1667	na->compression_block_size
1668	+ roffs,
1669	appending, update_from)) {
1670	done = TRUE;
1671	written = to_write;
1672	}
1673	}
1674	free(inbuf);
1675	}
1676	}
1677	if (!done) {
1678	/*
1679	* if the compression block is not full, or
1680	* if compression failed for whatever reason,
1681	* write uncompressed
1682	*/
1683	/* check we are not overflowing current allocation */
1684	if ((wpos + rounded)
1685	> ((wrl->lcn + wrl->length)
1686	<< vol->cluster_size_bits)) {
1687	ntfs_log_error("writing on unallocated clusters\n");
1688	errno = EIO;
1689	} else {
1690	written = ntfs_pwrite(vol->dev, wpos,
1691	rounded, b);
1692	if (written == rounded)
1693	written = to_write;
1694	}
1695	}
1696	}
1697	if ((written >= 0)
1698	&& !valid_compressed_run(na,wrl,TRUE,"end compressed write"))
1699	written = -1;
1700	return (written);
1701	}
1702
1703	/*
1704	* Close a file written compressed.
1705	* This compresses the last partial compression block of the file.
1706	* Two empty runlist slots have to be reserved beforehand.
1707	*
1708	* Returns zero if closing is successful.
1709	*/
1710
1711	int ntfs_compressed_close(ntfs_attr *na, runlist_element *wrl, s64 offs,
1712	VCN *update_from)
1713	{
1714	ntfs_volume *vol;
1715	runlist_element *brl; /* entry containing the beginning of block */
1716	int compression_length;
1717	s64 written;
1718	s64 to_read;
1719	s64 roffs;
1720	s64 got;
1721	s64 start_vcn;
1722	char *inbuf;
1723	BOOL fail;
1724	BOOL done;
1725
1726	if (na->unused_runs < 2) {
1727	ntfs_log_error("No unused runs for compressed close\n");
1728	errno = EIO;
1729	return (-1);
1730	}
1731	if (*update_from < 0) {
1732	ntfs_log_error("Bad update vcn for compressed close\n");
1733	errno = EIO;
1734	return (-1);
1735	}
1736	if (wrl->vcn < *update_from)
1737	*update_from = wrl->vcn;
1738	vol = na->ni->vol;
1739	compression_length = na->compression_block_clusters;
1740	done = FALSE;
1741	/*
1742	* There generally is an uncompressed block at end of file,
1743	* read the full block and compress it
1744	*/
1745	inbuf = (char*)ntfs_malloc(na->compression_block_size);
1746	if (inbuf) {
1747	start_vcn = (wrl->vcn + (offs >> vol->cluster_size_bits))
1748	& -compression_length;
1749	if (start_vcn < *update_from)
1750	*update_from = start_vcn;
1751	to_read = offs + ((wrl->vcn - start_vcn)
1752	<< vol->cluster_size_bits);
1753	brl = wrl;
1754	fail = FALSE;
1755	while (brl->vcn && (brl->vcn > start_vcn)) {
1756	if (brl->lcn == (LCN)LCN_HOLE) {
1757	ntfs_log_error("jump back over a hole when closing\n");
1758	fail = TRUE;
1759	errno = EIO;
1760	}
1761	brl--;
1762	}
1763	if (!fail) {
1764	/* roffs can be an offset from another uncomp block */
1765	roffs = (start_vcn - brl->vcn)
1766	<< vol->cluster_size_bits;
1767	if (to_read) {
1768	got = read_clusters(vol, brl, roffs, to_read,
1769	inbuf);
1770	if (got == to_read) {
1771	written = ntfs_comp_set(na, brl, roffs,
1772	to_read, inbuf);
1773	if ((written >= 0)
1774	/* free the unused clusters */
1775	&& !ntfs_compress_free(na,brl,
1776	written + roffs,
1777	na->compression_block_size + roffs,
1778	TRUE, update_from)) {
1779	done = TRUE;
1780	} else
1781	/* if compression failed, leave uncompressed */
1782	if (written == -1)
1783	done = TRUE;
1784	}
1785	} else
1786	done = TRUE;
1787	free(inbuf);
1788	}
1789	}
1790	if (done && !valid_compressed_run(na,wrl,TRUE,"end compressed close"))
1791	done = FALSE;
1792	return (!done);
1793	}
1794