1/*-
2 * Copyright (c) 2011 Pawel Jakub Dawidek <pawel@dawidek.net>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
28__FBSDID("$FreeBSD$");
29
30#include <sys/endian.h>
31
32#include <errno.h>
33#include <string.h>
34#include <strings.h>
35
36#include <hast.h>
37#include <lzf.h>
38#include <nv.h>
39#include <pjdlog.h>
40
41#include "hast_compression.h"
42
43static bool
44allzeros(const void *data, size_t size)
45{
46	const uint64_t *p = data;
47	unsigned int i;
48	uint64_t v;
49
50	PJDLOG_ASSERT((size % sizeof(*p)) == 0);
51
52	/*
53	 * This is the fastest method I found for checking if the given
54	 * buffer contain all zeros.
55	 * Because inside the loop we don't check at every step, we would
56	 * get an answer only after walking through entire buffer.
57	 * To return early if the buffer doesn't contain all zeros, we probe
58	 * 8 bytes at the beginning, in the middle and at the end of the buffer
59	 * first.
60	 */
61
62	size >>= 3;	/* divide by 8 */
63	if ((p[0] | p[size >> 1] | p[size - 1]) != 0)
64		return (false);
65	v = 0;
66	for (i = 0; i < size; i++)
67		v |= *p++;
68	return (v == 0);
69}
70
71static void *
72hast_hole_compress(const unsigned char *data, size_t *sizep)
73{
74	uint32_t size;
75	void *newbuf;
76
77	if (!allzeros(data, *sizep))
78		return (NULL);
79
80	newbuf = malloc(sizeof(size));
81	if (newbuf == NULL) {
82		pjdlog_warning("Unable to compress (no memory: %zu).",
83		    (size_t)*sizep);
84		return (NULL);
85	}
86	size = htole32((uint32_t)*sizep);
87	bcopy(&size, newbuf, sizeof(size));
88	*sizep = sizeof(size);
89
90	return (newbuf);
91}
92
93static void *
94hast_hole_decompress(const unsigned char *data, size_t *sizep)
95{
96	uint32_t size;
97	void *newbuf;
98
99	if (*sizep != sizeof(size)) {
100		pjdlog_error("Unable to decompress (invalid size: %zu).",
101		    *sizep);
102		return (NULL);
103	}
104
105	bcopy(data, &size, sizeof(size));
106	size = le32toh(size);
107
108	newbuf = malloc(size);
109	if (newbuf == NULL) {
110		pjdlog_error("Unable to decompress (no memory: %zu).",
111		    (size_t)size);
112		return (NULL);
113	}
114	bzero(newbuf, size);
115	*sizep = size;
116
117	return (newbuf);
118}
119
120/* Minimum block size to try to compress. */
121#define	HAST_LZF_COMPRESS_MIN	1024
122
123static void *
124hast_lzf_compress(const unsigned char *data, size_t *sizep)
125{
126	unsigned char *newbuf;
127	uint32_t origsize;
128	size_t newsize;
129
130	origsize = *sizep;
131
132	if (origsize <= HAST_LZF_COMPRESS_MIN)
133		return (NULL);
134
135	newsize = sizeof(origsize) + origsize - HAST_LZF_COMPRESS_MIN;
136	newbuf = malloc(newsize);
137	if (newbuf == NULL) {
138		pjdlog_warning("Unable to compress (no memory: %zu).",
139		    newsize);
140		return (NULL);
141	}
142	newsize = lzf_compress(data, *sizep, newbuf + sizeof(origsize),
143	    newsize - sizeof(origsize));
144	if (newsize == 0) {
145		free(newbuf);
146		return (NULL);
147	}
148	origsize = htole32(origsize);
149	bcopy(&origsize, newbuf, sizeof(origsize));
150
151	*sizep = sizeof(origsize) + newsize;
152	return (newbuf);
153}
154
155static void *
156hast_lzf_decompress(const unsigned char *data, size_t *sizep)
157{
158	unsigned char *newbuf;
159	uint32_t origsize;
160	size_t newsize;
161
162	PJDLOG_ASSERT(*sizep > sizeof(origsize));
163
164	bcopy(data, &origsize, sizeof(origsize));
165	origsize = le32toh(origsize);
166	PJDLOG_ASSERT(origsize > HAST_LZF_COMPRESS_MIN);
167
168	newbuf = malloc(origsize);
169	if (newbuf == NULL) {
170		pjdlog_error("Unable to decompress (no memory: %zu).",
171		    (size_t)origsize);
172		return (NULL);
173	}
174	newsize = lzf_decompress(data + sizeof(origsize),
175	    *sizep - sizeof(origsize), newbuf, origsize);
176	if (newsize == 0) {
177		free(newbuf);
178		pjdlog_error("Unable to decompress.");
179		return (NULL);
180	}
181	PJDLOG_ASSERT(newsize == origsize);
182
183	*sizep = newsize;
184	return (newbuf);
185}
186
187const char *
188compression_name(int num)
189{
190
191	switch (num) {
192	case HAST_COMPRESSION_NONE:
193		return ("none");
194	case HAST_COMPRESSION_HOLE:
195		return ("hole");
196	case HAST_COMPRESSION_LZF:
197		return ("lzf");
198	}
199	return ("unknown");
200}
201
202int
203compression_send(const struct hast_resource *res, struct nv *nv, void **datap,
204    size_t *sizep, bool *freedatap)
205{
206	unsigned char *newbuf;
207	int compression;
208	size_t size;
209
210	size = *sizep;
211	compression = res->hr_compression;
212
213	switch (compression) {
214	case HAST_COMPRESSION_NONE:
215		return (0);
216	case HAST_COMPRESSION_HOLE:
217		newbuf = hast_hole_compress(*datap, &size);
218		break;
219	case HAST_COMPRESSION_LZF:
220		/* Try 'hole' compression first. */
221		newbuf = hast_hole_compress(*datap, &size);
222		if (newbuf != NULL)
223			compression = HAST_COMPRESSION_HOLE;
224		else
225			newbuf = hast_lzf_compress(*datap, &size);
226		break;
227	default:
228		PJDLOG_ABORT("Invalid compression: %d.", res->hr_compression);
229	}
230
231	if (newbuf == NULL) {
232		/* Unable to compress the data. */
233		return (0);
234	}
235	nv_add_string(nv, compression_name(compression), "compression");
236	if (nv_error(nv) != 0) {
237		free(newbuf);
238		errno = nv_error(nv);
239		return (-1);
240	}
241	if (*freedatap)
242		free(*datap);
243	*freedatap = true;
244	*datap = newbuf;
245	*sizep = size;
246
247	return (0);
248}
249
250int
251compression_recv(const struct hast_resource *res __unused, struct nv *nv,
252    void **datap, size_t *sizep, bool *freedatap)
253{
254	unsigned char *newbuf;
255	const char *algo;
256	size_t size;
257
258	algo = nv_get_string(nv, "compression");
259	if (algo == NULL)
260		return (0);	/* No compression. */
261
262	newbuf = NULL;
263	size = *sizep;
264
265	if (strcmp(algo, "hole") == 0)
266		newbuf = hast_hole_decompress(*datap, &size);
267	else if (strcmp(algo, "lzf") == 0)
268		newbuf = hast_lzf_decompress(*datap, &size);
269	else {
270		pjdlog_error("Unknown compression algorithm '%s'.", algo);
271		return (-1);	/* Unknown compression algorithm. */
272	}
273
274	if (newbuf == NULL)
275		return (-1);
276	if (*freedatap)
277		free(*datap);
278	*freedatap = true;
279	*datap = newbuf;
280	*sizep = size;
281
282	return (0);
283}
284