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 43 static bool 44 allzeros(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 71 static void * 72 hast_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 93 static void * 94 hast_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 123 static void * 124 hast_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 155 static void * 156 hast_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 187 const char * 188 compression_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 202 int 203 compression_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 250 int 251 compression_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