aboutsummaryrefslogtreecommitdiff
path: root/src/liblzma/common/delta_coder.c
blob: ec8c6d59aa7d41d95c4cf692e1339ceebf848c2c (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
///////////////////////////////////////////////////////////////////////////////
//
/// \file       delta_coder.c
/// \brief      Encoder and decoder for the Delta filter
//
//  Copyright (C) 2007 Lasse Collin
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
///////////////////////////////////////////////////////////////////////////////

#include "delta_coder.h"


struct lzma_coder_s {
	/// Next coder in the chain
	lzma_next_coder next;

	/// Uncompressed size - This is needed when we are the last
	/// filter in the chain.
	lzma_vli uncompressed_size;

	/// Delta distance
	size_t distance;

	/// True if we are encoding; false if decoding
	bool is_encoder;

	/// Position in history[]
	uint8_t pos;

	/// Buffer to hold history of the original data
	uint8_t history[LZMA_DELTA_DISTANCE_MAX];
};


static void
encode_buffer(lzma_coder *coder, uint8_t *buffer, size_t size)
{
	const size_t distance = coder->distance;

	for (size_t i = 0; i < size; ++i) {
		const uint8_t tmp = coder->history[
				(distance + coder->pos) & 0xFF];
		coder->history[coder->pos--] = buffer[i];
		buffer[i] -= tmp;
	}

	return;
}


static void
decode_buffer(lzma_coder *coder, uint8_t *buffer, size_t size)
{
	const size_t distance = coder->distance;

	for (size_t i = 0; i < size; ++i) {
		buffer[i] += coder->history[(distance + coder->pos) & 0xFF];
		coder->history[coder->pos--] = buffer[i];
	}

	return;
}


static lzma_ret
delta_code(lzma_coder *coder, lzma_allocator *allocator,
		const uint8_t *restrict in, size_t *restrict in_pos,
		size_t in_size, uint8_t *restrict out,
		size_t *restrict out_pos, size_t out_size, lzma_action action)
{
	const size_t out_start = *out_pos;
	size_t size;
	lzma_ret ret;

	if (coder->next.code == NULL) {
		const size_t in_avail = in_size - *in_pos;

		if (coder->is_encoder) {
			// Check that we don't have too much input.
			if ((lzma_vli)(in_avail) > coder->uncompressed_size)
				return LZMA_DATA_ERROR;

			// Check that once LZMA_FINISH has been given, the
			// amount of input matches uncompressed_size if it
			// is known.
			if (action == LZMA_FINISH && coder->uncompressed_size
						!= LZMA_VLI_VALUE_UNKNOWN
					&& coder->uncompressed_size
						!= (lzma_vli)(in_avail))
				return LZMA_DATA_ERROR;

		} else {
			// Limit in_size so that we don't copy too much.
			if ((lzma_vli)(in_avail) > coder->uncompressed_size)
				in_size = *in_pos + (size_t)(
						coder->uncompressed_size);
		}

		size = bufcpy(in, in_pos, in_size, out, out_pos, out_size);

		if (coder->uncompressed_size != LZMA_VLI_VALUE_UNKNOWN)
			coder->uncompressed_size -= size;

		// action can be LZMA_FINISH only in the encoder.
		ret = (action == LZMA_FINISH && *in_pos == in_size)
					|| coder->uncompressed_size == 0
				? LZMA_STREAM_END : LZMA_OK;

	} else {
		ret = coder->next.code(coder->next.coder, allocator,
				in, in_pos, in_size, out, out_pos, out_size,
				action);
		if (ret != LZMA_OK && ret != LZMA_STREAM_END)
			return ret;

		size = *out_pos - out_start;
	}

	if (coder->is_encoder)
		encode_buffer(coder, out + out_start, size);
	else
		decode_buffer(coder, out + out_start, size);

	return ret;
}


static void
delta_coder_end(lzma_coder *coder, lzma_allocator *allocator)
{
	lzma_next_coder_end(&coder->next, allocator);
	lzma_free(coder, allocator);
	return;
}


static lzma_ret
delta_coder_init(lzma_next_coder *next, lzma_allocator *allocator,
		const lzma_filter_info *filters, bool is_encoder)
{
	// Allocate memory for the decoder if needed.
	if (next->coder == NULL) {
		next->coder = lzma_alloc(sizeof(lzma_coder), allocator);
		if (next->coder == NULL)
			return LZMA_MEM_ERROR;

		next->code = &delta_code;
		next->end = &delta_coder_end;
		next->coder->next = LZMA_NEXT_CODER_INIT;
	}

	// Copy Uncompressed Size which is used to limit the output size.
	next->coder->uncompressed_size = filters[0].uncompressed_size;

	// The coder acts slightly differently as encoder and decoder.
	next->coder->is_encoder = is_encoder;

	// Set the delta distance.
	if (filters[0].options == NULL)
		return LZMA_PROG_ERROR;
	next->coder->distance = ((lzma_options_delta *)(filters[0].options))
			->distance;
	if (next->coder->distance < LZMA_DELTA_DISTANCE_MIN
			|| next->coder->distance > LZMA_DELTA_DISTANCE_MAX)
		return LZMA_HEADER_ERROR;

	// Initialize the rest of the variables.
	next->coder->pos = 0;
	memzero(next->coder->history, LZMA_DELTA_DISTANCE_MAX);

	// Initialize the next decoder in the chain, if any.
	{
		const lzma_ret ret = lzma_next_filter_init(&next->coder->next,
				allocator, filters + 1);
		if (ret != LZMA_OK)
			return ret;
	}

	return LZMA_OK;
}


#ifdef HAVE_ENCODER
extern lzma_ret
lzma_delta_encoder_init(lzma_next_coder *next, lzma_allocator *allocator,
		const lzma_filter_info *filters)
{
	return delta_coder_init(next, allocator, filters, true);
}
#endif


#ifdef HAVE_DECODER
extern lzma_ret
lzma_delta_decoder_init(lzma_next_coder *next, lzma_allocator *allocator,
		const lzma_filter_info *filters)
{
	return delta_coder_init(next, allocator, filters, false);
}
#endif