Home | History | Annotate | Download | only in zfs
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License (the "License").
      6  * You may not use this file except in compliance with the License.
      7  *
      8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
      9  * or http://www.opensolaris.org/os/licensing.
     10  * See the License for the specific language governing permissions
     11  * and limitations under the License.
     12  *
     13  * When distributing Covered Code, include this CDDL HEADER in each
     14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     15  * If applicable, add the following below this CDDL HEADER, with the
     16  * fields enclosed by brackets "[]" replaced with your own identifying
     17  * information: Portions Copyright [yyyy] [name of copyright owner]
     18  *
     19  * CDDL HEADER END
     20  */
     21 
     22 /*
     23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
     24  * Use is subject to license terms.
     25  */
     26 
     27 /*
     28  * Zero-length encoding.  This is a fast and simple algorithm to eliminate
     29  * runs of zeroes.  Each chunk of compressed data begins with a length byte, b.
     30  * If b < n (where n is the compression parameter) then the next b + 1 bytes
     31  * are literal values.  If b >= n then the next (256 - b + 1) bytes are zero.
     32  */
     33 #include <sys/types.h>
     34 #include <sys/sysmacros.h>
     35 
     36 size_t
     37 zle_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
     38 {
     39 	uchar_t *src = s_start;
     40 	uchar_t *dst = d_start;
     41 	uchar_t *s_end = src + s_len;
     42 	uchar_t *d_end = dst + d_len;
     43 
     44 	while (src < s_end && dst < d_end - 1) {
     45 		uchar_t *first = src;
     46 		uchar_t *len = dst++;
     47 		if (src[0] == 0) {
     48 			uchar_t *last = src + (256 - n);
     49 			while (src < MIN(last, s_end) && src[0] == 0)
     50 				src++;
     51 			*len = src - first - 1 + n;
     52 		} else {
     53 			uchar_t *last = src + n;
     54 			if (d_end - dst < n)
     55 				break;
     56 			while (src < MIN(last, s_end) - 1 && (src[0] | src[1]))
     57 				*dst++ = *src++;
     58 			if (src[0])
     59 				*dst++ = *src++;
     60 			*len = src - first - 1;
     61 		}
     62 	}
     63 	return (src == s_end ? dst - (uchar_t *)d_start : s_len);
     64 }
     65 
     66 int
     67 zle_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
     68 {
     69 	uchar_t *src = s_start;
     70 	uchar_t *dst = d_start;
     71 	uchar_t *s_end = src + s_len;
     72 	uchar_t *d_end = dst + d_len;
     73 
     74 	while (src < s_end && dst < d_end) {
     75 		int len = 1 + *src++;
     76 		if (len <= n) {
     77 			while (len-- != 0)
     78 				*dst++ = *src++;
     79 		} else {
     80 			len -= n;
     81 			while (len-- != 0)
     82 				*dst++ = 0;
     83 		}
     84 	}
     85 	return (dst == d_end ? 0 : -1);
     86 }
     87