18cd3d45aSPawel Jakub Dawidek /*-
24d846d26SWarner Losh * SPDX-License-Identifier: BSD-2-Clause
31de7b4b8SPedro F. Giffuni *
48cd3d45aSPawel Jakub Dawidek * Copyright (c) 2011 Pawel Jakub Dawidek <pawel@dawidek.net>
58cd3d45aSPawel Jakub Dawidek * All rights reserved.
68cd3d45aSPawel Jakub Dawidek *
78cd3d45aSPawel Jakub Dawidek * Redistribution and use in source and binary forms, with or without
88cd3d45aSPawel Jakub Dawidek * modification, are permitted provided that the following conditions
98cd3d45aSPawel Jakub Dawidek * are met:
108cd3d45aSPawel Jakub Dawidek * 1. Redistributions of source code must retain the above copyright
118cd3d45aSPawel Jakub Dawidek * notice, this list of conditions and the following disclaimer.
128cd3d45aSPawel Jakub Dawidek * 2. Redistributions in binary form must reproduce the above copyright
138cd3d45aSPawel Jakub Dawidek * notice, this list of conditions and the following disclaimer in the
148cd3d45aSPawel Jakub Dawidek * documentation and/or other materials provided with the distribution.
158cd3d45aSPawel Jakub Dawidek *
168cd3d45aSPawel Jakub Dawidek * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
178cd3d45aSPawel Jakub Dawidek * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
188cd3d45aSPawel Jakub Dawidek * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
198cd3d45aSPawel Jakub Dawidek * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
208cd3d45aSPawel Jakub Dawidek * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
218cd3d45aSPawel Jakub Dawidek * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
228cd3d45aSPawel Jakub Dawidek * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
238cd3d45aSPawel Jakub Dawidek * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
248cd3d45aSPawel Jakub Dawidek * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
258cd3d45aSPawel Jakub Dawidek * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
268cd3d45aSPawel Jakub Dawidek * SUCH DAMAGE.
278cd3d45aSPawel Jakub Dawidek */
288cd3d45aSPawel Jakub Dawidek
298cd3d45aSPawel Jakub Dawidek #include <sys/cdefs.h>
308cd3d45aSPawel Jakub Dawidek #include <sys/endian.h>
318cd3d45aSPawel Jakub Dawidek
328cd3d45aSPawel Jakub Dawidek #include <errno.h>
338cd3d45aSPawel Jakub Dawidek #include <string.h>
348cd3d45aSPawel Jakub Dawidek #include <strings.h>
358cd3d45aSPawel Jakub Dawidek
368cd3d45aSPawel Jakub Dawidek #include <hast.h>
378cd3d45aSPawel Jakub Dawidek #include <lzf.h>
388cd3d45aSPawel Jakub Dawidek #include <nv.h>
398cd3d45aSPawel Jakub Dawidek #include <pjdlog.h>
408cd3d45aSPawel Jakub Dawidek
418cd3d45aSPawel Jakub Dawidek #include "hast_compression.h"
428cd3d45aSPawel Jakub Dawidek
438cd3d45aSPawel Jakub Dawidek static bool
allzeros(const void * data,size_t size)448cd3d45aSPawel Jakub Dawidek allzeros(const void *data, size_t size)
458cd3d45aSPawel Jakub Dawidek {
468cd3d45aSPawel Jakub Dawidek const uint64_t *p = data;
478cd3d45aSPawel Jakub Dawidek unsigned int i;
488cd3d45aSPawel Jakub Dawidek uint64_t v;
498cd3d45aSPawel Jakub Dawidek
508cd3d45aSPawel Jakub Dawidek PJDLOG_ASSERT((size % sizeof(*p)) == 0);
518cd3d45aSPawel Jakub Dawidek
528cd3d45aSPawel Jakub Dawidek /*
538cd3d45aSPawel Jakub Dawidek * This is the fastest method I found for checking if the given
548cd3d45aSPawel Jakub Dawidek * buffer contain all zeros.
558cd3d45aSPawel Jakub Dawidek * Because inside the loop we don't check at every step, we would
568cd3d45aSPawel Jakub Dawidek * get an answer only after walking through entire buffer.
578cd3d45aSPawel Jakub Dawidek * To return early if the buffer doesn't contain all zeros, we probe
584b85a12fSUlrich Spörlein * 8 bytes at the beginning, in the middle and at the end of the buffer
598cd3d45aSPawel Jakub Dawidek * first.
608cd3d45aSPawel Jakub Dawidek */
618cd3d45aSPawel Jakub Dawidek
628cd3d45aSPawel Jakub Dawidek size >>= 3; /* divide by 8 */
638cd3d45aSPawel Jakub Dawidek if ((p[0] | p[size >> 1] | p[size - 1]) != 0)
648cd3d45aSPawel Jakub Dawidek return (false);
658cd3d45aSPawel Jakub Dawidek v = 0;
668cd3d45aSPawel Jakub Dawidek for (i = 0; i < size; i++)
678cd3d45aSPawel Jakub Dawidek v |= *p++;
688cd3d45aSPawel Jakub Dawidek return (v == 0);
698cd3d45aSPawel Jakub Dawidek }
708cd3d45aSPawel Jakub Dawidek
718cd3d45aSPawel Jakub Dawidek static void *
hast_hole_compress(const unsigned char * data,size_t * sizep)728cd3d45aSPawel Jakub Dawidek hast_hole_compress(const unsigned char *data, size_t *sizep)
738cd3d45aSPawel Jakub Dawidek {
748cd3d45aSPawel Jakub Dawidek uint32_t size;
758cd3d45aSPawel Jakub Dawidek void *newbuf;
768cd3d45aSPawel Jakub Dawidek
778cd3d45aSPawel Jakub Dawidek if (!allzeros(data, *sizep))
788cd3d45aSPawel Jakub Dawidek return (NULL);
798cd3d45aSPawel Jakub Dawidek
808cd3d45aSPawel Jakub Dawidek newbuf = malloc(sizeof(size));
818cd3d45aSPawel Jakub Dawidek if (newbuf == NULL) {
828cd3d45aSPawel Jakub Dawidek pjdlog_warning("Unable to compress (no memory: %zu).",
838cd3d45aSPawel Jakub Dawidek (size_t)*sizep);
848cd3d45aSPawel Jakub Dawidek return (NULL);
858cd3d45aSPawel Jakub Dawidek }
868cd3d45aSPawel Jakub Dawidek size = htole32((uint32_t)*sizep);
878cd3d45aSPawel Jakub Dawidek bcopy(&size, newbuf, sizeof(size));
888cd3d45aSPawel Jakub Dawidek *sizep = sizeof(size);
898cd3d45aSPawel Jakub Dawidek
908cd3d45aSPawel Jakub Dawidek return (newbuf);
918cd3d45aSPawel Jakub Dawidek }
928cd3d45aSPawel Jakub Dawidek
938cd3d45aSPawel Jakub Dawidek static void *
hast_hole_decompress(const unsigned char * data,size_t * sizep)948cd3d45aSPawel Jakub Dawidek hast_hole_decompress(const unsigned char *data, size_t *sizep)
958cd3d45aSPawel Jakub Dawidek {
968cd3d45aSPawel Jakub Dawidek uint32_t size;
978cd3d45aSPawel Jakub Dawidek void *newbuf;
988cd3d45aSPawel Jakub Dawidek
998cd3d45aSPawel Jakub Dawidek if (*sizep != sizeof(size)) {
1008cd3d45aSPawel Jakub Dawidek pjdlog_error("Unable to decompress (invalid size: %zu).",
1018cd3d45aSPawel Jakub Dawidek *sizep);
1028cd3d45aSPawel Jakub Dawidek return (NULL);
1038cd3d45aSPawel Jakub Dawidek }
1048cd3d45aSPawel Jakub Dawidek
1058cd3d45aSPawel Jakub Dawidek bcopy(data, &size, sizeof(size));
1068cd3d45aSPawel Jakub Dawidek size = le32toh(size);
1078cd3d45aSPawel Jakub Dawidek
1088cd3d45aSPawel Jakub Dawidek newbuf = malloc(size);
1098cd3d45aSPawel Jakub Dawidek if (newbuf == NULL) {
1108cd3d45aSPawel Jakub Dawidek pjdlog_error("Unable to decompress (no memory: %zu).",
1118cd3d45aSPawel Jakub Dawidek (size_t)size);
1128cd3d45aSPawel Jakub Dawidek return (NULL);
1138cd3d45aSPawel Jakub Dawidek }
1148cd3d45aSPawel Jakub Dawidek bzero(newbuf, size);
1158cd3d45aSPawel Jakub Dawidek *sizep = size;
1168cd3d45aSPawel Jakub Dawidek
1178cd3d45aSPawel Jakub Dawidek return (newbuf);
1188cd3d45aSPawel Jakub Dawidek }
1198cd3d45aSPawel Jakub Dawidek
1208cd3d45aSPawel Jakub Dawidek /* Minimum block size to try to compress. */
1218cd3d45aSPawel Jakub Dawidek #define HAST_LZF_COMPRESS_MIN 1024
1228cd3d45aSPawel Jakub Dawidek
1238cd3d45aSPawel Jakub Dawidek static void *
hast_lzf_compress(const unsigned char * data,size_t * sizep)1248cd3d45aSPawel Jakub Dawidek hast_lzf_compress(const unsigned char *data, size_t *sizep)
1258cd3d45aSPawel Jakub Dawidek {
1268cd3d45aSPawel Jakub Dawidek unsigned char *newbuf;
1278cd3d45aSPawel Jakub Dawidek uint32_t origsize;
1288cd3d45aSPawel Jakub Dawidek size_t newsize;
1298cd3d45aSPawel Jakub Dawidek
1308cd3d45aSPawel Jakub Dawidek origsize = *sizep;
1318cd3d45aSPawel Jakub Dawidek
1328cd3d45aSPawel Jakub Dawidek if (origsize <= HAST_LZF_COMPRESS_MIN)
1338cd3d45aSPawel Jakub Dawidek return (NULL);
1348cd3d45aSPawel Jakub Dawidek
1358cd3d45aSPawel Jakub Dawidek newsize = sizeof(origsize) + origsize - HAST_LZF_COMPRESS_MIN;
1368cd3d45aSPawel Jakub Dawidek newbuf = malloc(newsize);
1378cd3d45aSPawel Jakub Dawidek if (newbuf == NULL) {
1388cd3d45aSPawel Jakub Dawidek pjdlog_warning("Unable to compress (no memory: %zu).",
1398cd3d45aSPawel Jakub Dawidek newsize);
1408cd3d45aSPawel Jakub Dawidek return (NULL);
1418cd3d45aSPawel Jakub Dawidek }
1428cd3d45aSPawel Jakub Dawidek newsize = lzf_compress(data, *sizep, newbuf + sizeof(origsize),
1438cd3d45aSPawel Jakub Dawidek newsize - sizeof(origsize));
1448cd3d45aSPawel Jakub Dawidek if (newsize == 0) {
1458cd3d45aSPawel Jakub Dawidek free(newbuf);
1468cd3d45aSPawel Jakub Dawidek return (NULL);
1478cd3d45aSPawel Jakub Dawidek }
1488cd3d45aSPawel Jakub Dawidek origsize = htole32(origsize);
1498cd3d45aSPawel Jakub Dawidek bcopy(&origsize, newbuf, sizeof(origsize));
1508cd3d45aSPawel Jakub Dawidek
1518cd3d45aSPawel Jakub Dawidek *sizep = sizeof(origsize) + newsize;
1528cd3d45aSPawel Jakub Dawidek return (newbuf);
1538cd3d45aSPawel Jakub Dawidek }
1548cd3d45aSPawel Jakub Dawidek
1558cd3d45aSPawel Jakub Dawidek static void *
hast_lzf_decompress(const unsigned char * data,size_t * sizep)1568cd3d45aSPawel Jakub Dawidek hast_lzf_decompress(const unsigned char *data, size_t *sizep)
1578cd3d45aSPawel Jakub Dawidek {
1588cd3d45aSPawel Jakub Dawidek unsigned char *newbuf;
1598cd3d45aSPawel Jakub Dawidek uint32_t origsize;
1608cd3d45aSPawel Jakub Dawidek size_t newsize;
1618cd3d45aSPawel Jakub Dawidek
1628cd3d45aSPawel Jakub Dawidek PJDLOG_ASSERT(*sizep > sizeof(origsize));
1638cd3d45aSPawel Jakub Dawidek
1648cd3d45aSPawel Jakub Dawidek bcopy(data, &origsize, sizeof(origsize));
1658cd3d45aSPawel Jakub Dawidek origsize = le32toh(origsize);
1668cd3d45aSPawel Jakub Dawidek PJDLOG_ASSERT(origsize > HAST_LZF_COMPRESS_MIN);
1678cd3d45aSPawel Jakub Dawidek
1688cd3d45aSPawel Jakub Dawidek newbuf = malloc(origsize);
1698cd3d45aSPawel Jakub Dawidek if (newbuf == NULL) {
1708cd3d45aSPawel Jakub Dawidek pjdlog_error("Unable to decompress (no memory: %zu).",
1718cd3d45aSPawel Jakub Dawidek (size_t)origsize);
1728cd3d45aSPawel Jakub Dawidek return (NULL);
1738cd3d45aSPawel Jakub Dawidek }
1748cd3d45aSPawel Jakub Dawidek newsize = lzf_decompress(data + sizeof(origsize),
1758cd3d45aSPawel Jakub Dawidek *sizep - sizeof(origsize), newbuf, origsize);
1768cd3d45aSPawel Jakub Dawidek if (newsize == 0) {
1778cd3d45aSPawel Jakub Dawidek free(newbuf);
1788cd3d45aSPawel Jakub Dawidek pjdlog_error("Unable to decompress.");
1798cd3d45aSPawel Jakub Dawidek return (NULL);
1808cd3d45aSPawel Jakub Dawidek }
1818cd3d45aSPawel Jakub Dawidek PJDLOG_ASSERT(newsize == origsize);
1828cd3d45aSPawel Jakub Dawidek
1838cd3d45aSPawel Jakub Dawidek *sizep = newsize;
1848cd3d45aSPawel Jakub Dawidek return (newbuf);
1858cd3d45aSPawel Jakub Dawidek }
1868cd3d45aSPawel Jakub Dawidek
1878cd3d45aSPawel Jakub Dawidek const char *
compression_name(int num)1888cd3d45aSPawel Jakub Dawidek compression_name(int num)
1898cd3d45aSPawel Jakub Dawidek {
1908cd3d45aSPawel Jakub Dawidek
1918cd3d45aSPawel Jakub Dawidek switch (num) {
1928cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_NONE:
1938cd3d45aSPawel Jakub Dawidek return ("none");
1948cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_HOLE:
1958cd3d45aSPawel Jakub Dawidek return ("hole");
1968cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_LZF:
1978cd3d45aSPawel Jakub Dawidek return ("lzf");
1988cd3d45aSPawel Jakub Dawidek }
1998cd3d45aSPawel Jakub Dawidek return ("unknown");
2008cd3d45aSPawel Jakub Dawidek }
2018cd3d45aSPawel Jakub Dawidek
2028cd3d45aSPawel Jakub Dawidek int
compression_send(const struct hast_resource * res,struct nv * nv,void ** datap,size_t * sizep,bool * freedatap)2038cd3d45aSPawel Jakub Dawidek compression_send(const struct hast_resource *res, struct nv *nv, void **datap,
2048cd3d45aSPawel Jakub Dawidek size_t *sizep, bool *freedatap)
2058cd3d45aSPawel Jakub Dawidek {
2068cd3d45aSPawel Jakub Dawidek unsigned char *newbuf;
2078cd3d45aSPawel Jakub Dawidek int compression;
2088cd3d45aSPawel Jakub Dawidek size_t size;
2098cd3d45aSPawel Jakub Dawidek
2108cd3d45aSPawel Jakub Dawidek size = *sizep;
2118cd3d45aSPawel Jakub Dawidek compression = res->hr_compression;
2128cd3d45aSPawel Jakub Dawidek
2138cd3d45aSPawel Jakub Dawidek switch (compression) {
2148cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_NONE:
2158cd3d45aSPawel Jakub Dawidek return (0);
2168cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_HOLE:
2178cd3d45aSPawel Jakub Dawidek newbuf = hast_hole_compress(*datap, &size);
2188cd3d45aSPawel Jakub Dawidek break;
2198cd3d45aSPawel Jakub Dawidek case HAST_COMPRESSION_LZF:
2208cd3d45aSPawel Jakub Dawidek /* Try 'hole' compression first. */
2218cd3d45aSPawel Jakub Dawidek newbuf = hast_hole_compress(*datap, &size);
2228cd3d45aSPawel Jakub Dawidek if (newbuf != NULL)
2238cd3d45aSPawel Jakub Dawidek compression = HAST_COMPRESSION_HOLE;
2248cd3d45aSPawel Jakub Dawidek else
2258cd3d45aSPawel Jakub Dawidek newbuf = hast_lzf_compress(*datap, &size);
2268cd3d45aSPawel Jakub Dawidek break;
2278cd3d45aSPawel Jakub Dawidek default:
2288cd3d45aSPawel Jakub Dawidek PJDLOG_ABORT("Invalid compression: %d.", res->hr_compression);
2298cd3d45aSPawel Jakub Dawidek }
2308cd3d45aSPawel Jakub Dawidek
2318cd3d45aSPawel Jakub Dawidek if (newbuf == NULL) {
2328cd3d45aSPawel Jakub Dawidek /* Unable to compress the data. */
2338cd3d45aSPawel Jakub Dawidek return (0);
2348cd3d45aSPawel Jakub Dawidek }
2358cd3d45aSPawel Jakub Dawidek nv_add_string(nv, compression_name(compression), "compression");
2368cd3d45aSPawel Jakub Dawidek if (nv_error(nv) != 0) {
2378cd3d45aSPawel Jakub Dawidek free(newbuf);
2388cd3d45aSPawel Jakub Dawidek errno = nv_error(nv);
2398cd3d45aSPawel Jakub Dawidek return (-1);
2408cd3d45aSPawel Jakub Dawidek }
2418cd3d45aSPawel Jakub Dawidek if (*freedatap)
2428cd3d45aSPawel Jakub Dawidek free(*datap);
2438cd3d45aSPawel Jakub Dawidek *freedatap = true;
2448cd3d45aSPawel Jakub Dawidek *datap = newbuf;
2458cd3d45aSPawel Jakub Dawidek *sizep = size;
2468cd3d45aSPawel Jakub Dawidek
2478cd3d45aSPawel Jakub Dawidek return (0);
2488cd3d45aSPawel Jakub Dawidek }
2498cd3d45aSPawel Jakub Dawidek
2508cd3d45aSPawel Jakub Dawidek int
compression_recv(const struct hast_resource * res __unused,struct nv * nv,void ** datap,size_t * sizep,bool * freedatap)2518cd3d45aSPawel Jakub Dawidek compression_recv(const struct hast_resource *res __unused, struct nv *nv,
2528cd3d45aSPawel Jakub Dawidek void **datap, size_t *sizep, bool *freedatap)
2538cd3d45aSPawel Jakub Dawidek {
2548cd3d45aSPawel Jakub Dawidek unsigned char *newbuf;
2558cd3d45aSPawel Jakub Dawidek const char *algo;
2568cd3d45aSPawel Jakub Dawidek size_t size;
2578cd3d45aSPawel Jakub Dawidek
2588cd3d45aSPawel Jakub Dawidek algo = nv_get_string(nv, "compression");
2598cd3d45aSPawel Jakub Dawidek if (algo == NULL)
2608cd3d45aSPawel Jakub Dawidek return (0); /* No compression. */
2618cd3d45aSPawel Jakub Dawidek
2628cd3d45aSPawel Jakub Dawidek newbuf = NULL;
2638cd3d45aSPawel Jakub Dawidek size = *sizep;
2648cd3d45aSPawel Jakub Dawidek
2658cd3d45aSPawel Jakub Dawidek if (strcmp(algo, "hole") == 0)
2668cd3d45aSPawel Jakub Dawidek newbuf = hast_hole_decompress(*datap, &size);
2678cd3d45aSPawel Jakub Dawidek else if (strcmp(algo, "lzf") == 0)
2688cd3d45aSPawel Jakub Dawidek newbuf = hast_lzf_decompress(*datap, &size);
2698cd3d45aSPawel Jakub Dawidek else {
2708cd3d45aSPawel Jakub Dawidek pjdlog_error("Unknown compression algorithm '%s'.", algo);
2718cd3d45aSPawel Jakub Dawidek return (-1); /* Unknown compression algorithm. */
2728cd3d45aSPawel Jakub Dawidek }
2738cd3d45aSPawel Jakub Dawidek
2748cd3d45aSPawel Jakub Dawidek if (newbuf == NULL)
2758cd3d45aSPawel Jakub Dawidek return (-1);
2768cd3d45aSPawel Jakub Dawidek if (*freedatap)
2778cd3d45aSPawel Jakub Dawidek free(*datap);
2788cd3d45aSPawel Jakub Dawidek *freedatap = true;
2798cd3d45aSPawel Jakub Dawidek *datap = newbuf;
2808cd3d45aSPawel Jakub Dawidek *sizep = size;
2818cd3d45aSPawel Jakub Dawidek
2828cd3d45aSPawel Jakub Dawidek return (0);
2838cd3d45aSPawel Jakub Dawidek }
284