1fa9e4066Sahrens /*
2fa9e4066Sahrens * CDDL HEADER START
3fa9e4066Sahrens *
4fa9e4066Sahrens * The contents of this file are subject to the terms of the
512054bfcSnd * Common Development and Distribution License (the "License").
612054bfcSnd * You may not use this file except in compliance with the License.
7fa9e4066Sahrens *
8fa9e4066Sahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9fa9e4066Sahrens * or http://www.opensolaris.org/os/licensing.
10fa9e4066Sahrens * See the License for the specific language governing permissions
11fa9e4066Sahrens * and limitations under the License.
12fa9e4066Sahrens *
13fa9e4066Sahrens * When distributing Covered Code, include this CDDL HEADER in each
14fa9e4066Sahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15fa9e4066Sahrens * If applicable, add the following below this CDDL HEADER, with the
16fa9e4066Sahrens * fields enclosed by brackets "[]" replaced with your own identifying
17fa9e4066Sahrens * information: Portions Copyright [yyyy] [name of copyright owner]
18fa9e4066Sahrens *
19fa9e4066Sahrens * CDDL HEADER END
20fa9e4066Sahrens */
21c9431fa1Sahl
22fa9e4066Sahrens /*
2391de656bSNeil Perrin * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
24fa9e4066Sahrens */
25fa9e4066Sahrens
26fa9e4066Sahrens /*
2791de656bSNeil Perrin * We keep our own copy of this algorithm for 3 main reasons:
28b24ab676SJeff Bonwick * 1. If we didn't, anyone modifying common/os/compress.c would
2912054bfcSnd * directly break our on disk format
30b24ab676SJeff Bonwick * 2. Our version of lzjb does not have a number of checks that the
3112054bfcSnd * common/os version needs and uses
32b24ab676SJeff Bonwick * 3. We initialize the lempel to ensure deterministic results,
33b24ab676SJeff Bonwick * so that identical blocks can always be deduplicated.
34fa9e4066Sahrens * In particular, we are adding the "feature" that compress() can
3591de656bSNeil Perrin * take a destination buffer size and returns the compressed length, or the
3691de656bSNeil Perrin * source length if compression would overflow the destination buffer.
37fa9e4066Sahrens */
38fa9e4066Sahrens
39fa9e4066Sahrens #include <sys/types.h>
40*d5285caeSGeorge Wilson #include <sys/param.h>
41fa9e4066Sahrens
42fa9e4066Sahrens #define MATCH_BITS 6
43fa9e4066Sahrens #define MATCH_MIN 3
44fa9e4066Sahrens #define MATCH_MAX ((1 << MATCH_BITS) + (MATCH_MIN - 1))
45fa9e4066Sahrens #define OFFSET_MASK ((1 << (16 - MATCH_BITS)) - 1)
46b24ab676SJeff Bonwick #define LEMPEL_SIZE 1024
47fa9e4066Sahrens
48c9431fa1Sahl /*ARGSUSED*/
49fa9e4066Sahrens size_t
lzjb_compress(void * s_start,void * d_start,size_t s_len,size_t d_len,int n)50c9431fa1Sahl lzjb_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
51fa9e4066Sahrens {
52fa9e4066Sahrens uchar_t *src = s_start;
53fa9e4066Sahrens uchar_t *dst = d_start;
54*d5285caeSGeorge Wilson uchar_t *cpy;
55*d5285caeSGeorge Wilson uchar_t *copymap = NULL;
56fa9e4066Sahrens int copymask = 1 << (NBBY - 1);
57b24ab676SJeff Bonwick int mlen, offset, hash;
58fa9e4066Sahrens uint16_t *hp;
59b24ab676SJeff Bonwick uint16_t lempel[LEMPEL_SIZE] = { 0 };
60fa9e4066Sahrens
61fa9e4066Sahrens while (src < (uchar_t *)s_start + s_len) {
62fa9e4066Sahrens if ((copymask <<= 1) == (1 << NBBY)) {
63b24ab676SJeff Bonwick if (dst >= (uchar_t *)d_start + d_len - 1 - 2 * NBBY)
64fa9e4066Sahrens return (s_len);
65fa9e4066Sahrens copymask = 1;
66fa9e4066Sahrens copymap = dst;
67fa9e4066Sahrens *dst++ = 0;
68fa9e4066Sahrens }
69fa9e4066Sahrens if (src > (uchar_t *)s_start + s_len - MATCH_MAX) {
70fa9e4066Sahrens *dst++ = *src++;
71fa9e4066Sahrens continue;
72fa9e4066Sahrens }
73b24ab676SJeff Bonwick hash = (src[0] << 16) + (src[1] << 8) + src[2];
74b24ab676SJeff Bonwick hash += hash >> 9;
75b24ab676SJeff Bonwick hash += hash >> 5;
76b24ab676SJeff Bonwick hp = &lempel[hash & (LEMPEL_SIZE - 1)];
77fa9e4066Sahrens offset = (intptr_t)(src - *hp) & OFFSET_MASK;
78fa9e4066Sahrens *hp = (uint16_t)(uintptr_t)src;
79fa9e4066Sahrens cpy = src - offset;
80fa9e4066Sahrens if (cpy >= (uchar_t *)s_start && cpy != src &&
81fa9e4066Sahrens src[0] == cpy[0] && src[1] == cpy[1] && src[2] == cpy[2]) {
82fa9e4066Sahrens *copymap |= copymask;
83fa9e4066Sahrens for (mlen = MATCH_MIN; mlen < MATCH_MAX; mlen++)
84fa9e4066Sahrens if (src[mlen] != cpy[mlen])
85fa9e4066Sahrens break;
86fa9e4066Sahrens *dst++ = ((mlen - MATCH_MIN) << (NBBY - MATCH_BITS)) |
87fa9e4066Sahrens (offset >> NBBY);
88fa9e4066Sahrens *dst++ = (uchar_t)offset;
89fa9e4066Sahrens src += mlen;
90fa9e4066Sahrens } else {
91fa9e4066Sahrens *dst++ = *src++;
92fa9e4066Sahrens }
93fa9e4066Sahrens }
94fa9e4066Sahrens return (dst - (uchar_t *)d_start);
95fa9e4066Sahrens }
96fa9e4066Sahrens
97fa9e4066Sahrens /*ARGSUSED*/
98fa9e4066Sahrens int
lzjb_decompress(void * s_start,void * d_start,size_t s_len,size_t d_len,int n)99c9431fa1Sahl lzjb_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
100fa9e4066Sahrens {
101fa9e4066Sahrens uchar_t *src = s_start;
102fa9e4066Sahrens uchar_t *dst = d_start;
103fa9e4066Sahrens uchar_t *d_end = (uchar_t *)d_start + d_len;
104*d5285caeSGeorge Wilson uchar_t *cpy;
105*d5285caeSGeorge Wilson uchar_t copymap = 0;
106fa9e4066Sahrens int copymask = 1 << (NBBY - 1);
107fa9e4066Sahrens
108fa9e4066Sahrens while (dst < d_end) {
109fa9e4066Sahrens if ((copymask <<= 1) == (1 << NBBY)) {
110fa9e4066Sahrens copymask = 1;
111fa9e4066Sahrens copymap = *src++;
112fa9e4066Sahrens }
113fa9e4066Sahrens if (copymap & copymask) {
114fa9e4066Sahrens int mlen = (src[0] >> (NBBY - MATCH_BITS)) + MATCH_MIN;
115fa9e4066Sahrens int offset = ((src[0] << NBBY) | src[1]) & OFFSET_MASK;
116fa9e4066Sahrens src += 2;
117fa9e4066Sahrens if ((cpy = dst - offset) < (uchar_t *)d_start)
118fa9e4066Sahrens return (-1);
119fa9e4066Sahrens while (--mlen >= 0 && dst < d_end)
120fa9e4066Sahrens *dst++ = *cpy++;
121fa9e4066Sahrens } else {
122fa9e4066Sahrens *dst++ = *src++;
123fa9e4066Sahrens }
124fa9e4066Sahrens }
125fa9e4066Sahrens return (0);
126fa9e4066Sahrens }
127