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