ntfs/libntfs/runlist.c

55  * @dst:
63 static void ntfs_rl_mm(runlist_element *base, int dst, int src, int size)
65 	if ((dst != src) && (size > 0))
66 		memmove(base + dst, base + src, size * sizeof(*base));
72  * @dst:
81 static void ntfs_rl_mc(runlist_element *dstbase, int dst,
85 		memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
153  * @dst:	original runlist
154  * @src:	new runlist to test for mergeability with @dst
162 static BOOL ntfs_rl_are_mergeable(runlist_element *dst, runlist_element *src)
164 	if (!dst || !src) {
171 	if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
174 	if ((dst->vcn + dst->length) != src->vcn)
177 	if ((dst->lcn >= 0) && (src->lcn >= 0) &&
178 		((dst->lcn + dst->length) == src->lcn))
181 	if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
189  * @dst:	original, destination runlist
190  * @src:	new runlist to merge with @dst
192  * Merge the two runlists, writing into the destination runlist @dst. The
196 static void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
198 	dst->length += src->length;
203  * @dst:	original runlist to be worked on
204  * @dsize:	number of elements in @dst (including end marker)
205  * @src:	runlist to be inserted into @dst
207  * @loc:	append the new runlist @src after this element in @dst
209  * Append the runlist @src after element @loc in @dst.  Merge the right end of
214  * runlists @dst and @src are deallocated before returning so you cannot use
216  * may be the same as @dst but this is irrelevant.)
221 static runlist_element *ntfs_rl_append(runlist_element *dst, int dsize,
227 	if (!dst || !src) {
236 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
238 	/* Space required: @dst size + @src size, less one if we merged. */
239 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
240 	if (!dst)
249 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
254 	/* Move the tail of @dst out of the way, then copy in @src. */
255 	ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - loc - 1 - right);
256 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
259 	dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
262 	if (dst[marker].lcn == LCN_ENOENT)
263 		dst[marker].vcn = dst[marker-1].vcn + dst[marker-1].length;
265 	return dst;
270  * @dst:	original runlist to be worked on
271  * @dsize:	number of elements in @dst (including end marker)
274  * @loc:	insert the new runlist @src before this element in @dst
276  * Insert the runlist @src before element @loc in the runlist @dst. Merge the
281  * runlists @dst and @src are deallocated before returning so you cannot use
283  * may be the same as @dst but this is irrelevant.)
288 static runlist_element *ntfs_rl_insert(runlist_element *dst, int dsize,
292 	BOOL disc = FALSE;	/* Discontinuity between @dst and @src */
295 	if (!dst || !src) {
302 	/* disc => Discontinuity between the end of @dst and the start of @src.
310 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
312 		merged_length = dst[loc - 1].length;
316 		disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
319 	/* Space required: @dst size + @src size, less one if we merged, plus
322 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
323 	if (!dst)
331 		__ntfs_rl_merge(dst + loc - 1, src);
336 	 * If "left", then the first run in @src has been merged with one in @dst.
337 	 * If "disc", then @dst and @src don't meet and we need an extra run to fill the gap.
341 	/* Move the tail of @dst out of the way, then copy in @src. */
342 	ntfs_rl_mm(dst, marker, loc, dsize - loc);
343 	ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
346 	dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
348 	if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
349 		dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
354 			dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
355 			dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
357 			dst[loc].vcn = 0;
358 			dst[loc].length = dst[loc + 1].vcn;
360 		dst[loc].lcn = LCN_RL_NOT_MAPPED;
362 	return dst;
367  * @dst:	original runlist to be worked on
368  * @dsize:	number of elements in @dst (including end marker)
371  * @loc:	index in runlist @dst to overwrite with @src
373  * Replace the runlist element @dst at @loc with @src. Merge the left and
377  * runlists @dst and @src are deallocated before returning so you cannot use
379  * may be the same as @dst but this is irrelevant.)
384 static runlist_element *ntfs_rl_replace(runlist_element *dst, int dsize,
391 	int tail;		/* Start of tail of @dst */
394 	if (!dst || !src) {
403 		right = ntfs_rl_are_mergeable(src + ssize - 1, dst + loc + 1);
405 		left = ntfs_rl_are_mergeable(dst + loc - 1, src);
412 		dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
413 		if (!dst)
423 		__ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
425 		__ntfs_rl_merge(dst + loc - 1, src);
428 	 * tail - Offset of the tail of @dst
430 	 * If "right", then one of @dst's runs is already merged into @src.
437 	 * If "left", then the first run in @src has been merged with one in @dst.
441 	/* Move the tail of @dst out of the way, then copy in @src. */
442 	ntfs_rl_mm(dst, marker, tail, dsize - tail);
443 	ntfs_rl_mc(dst, loc, src, left, ssize - left);
446 	if (((dsize - tail) > 0) && (dst[marker].lcn == LCN_ENOENT))
447 		dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
449 	return dst;
454  * @dst:	original runlist to be worked on
455  * @dsize:	number of elements in @dst (including end marker)
458  * @loc:	index in runlist @dst at which to split and insert @src
460  * Split the runlist @dst at @loc into two and insert @new in between the two
465  * runlists @dst and @src are deallocated before returning so you cannot use
467  * may be the same as @dst but this is irrelevant.)
472 static runlist_element *ntfs_rl_split(runlist_element *dst, int dsize,
475 	if (!dst || !src) {
481 	/* Space required: @dst size + @src size + one new hole. */
482 	dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
483 	if (!dst)
484 		return dst;
490 	/* Move the tail of @dst out of the way, then copy in @src. */
491 	ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
492 	ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
495 	dst[loc].length		= dst[loc+1].vcn       - dst[loc].vcn;
496 	dst[loc+ssize+1].vcn	= dst[loc+ssize].vcn   + dst[loc+ssize].length;
497 	dst[loc+ssize+1].length	= dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
499 	return dst;
518 	ntfs_log_debug("dst:\n");
737  * may be the same as @dst but this is irrelevant.)
1419  * @dst:	destination buffer to write to
1423  * Store in @dst, the minimum bytes of the number @n which are required to
1425  * @dest_max, the maximum position within @dst to which we are allowed to
1433  * destination buffer @dst is too small, return -1 with errno set ENOSPC.
1435 int ntfs_write_significant_bytes(u8 *dst, const u8 *dst_max, const s64 n)
1441 	if (dst > dst_max)
1443 	*dst++ = l;
1446 		if (dst > dst_max)
1449 		*dst++ = l;
1461  * @dst:	destination buffer to which to write the mapping pairs array
1462  * @dst_len:	size of destination buffer @dst in bytes
1468  * @start_vcn and save the array in @dst.  @dst_len is the size of @dst in
1472  * If @rl is NULL, just write a single terminator byte to @dst.
1475  * the first vcn outside the destination buffer. Note that on error @dst has
1489 int ntfs_mapping_pairs_build(const ntfs_volume *vol, u8 *dst,
1518 	dst_max = dst + dst_len - 1;
1529 		len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1547 			lcn_len = ntfs_write_significant_bytes(dst + 1 +
1553 		dst_next = dst + len_len + lcn_len + 1;
1557 		*dst = lcn_len << 4 | len_len;
1559 		dst = dst_next;
1568 		len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
1583 			lcn_len = ntfs_write_significant_bytes(dst + 1 +
1590 		dst_next = dst + len_len + lcn_len + 1;
1594 		*dst = lcn_len << 4 | len_len;
1596 		dst += 1 + len_len + lcn_len;
1603 	*dst = 0;
1611 	*dst = 0;
1847 	printf("dst:\n");
1944 	runlist_element *dst;
1948 	dst = ntfs_malloc(4096);
1949 	if (!src || !dst) {
1954 	memcpy(dst, file, size);
1957 	res = test_rl_runlists_merge(dst, src);