]>
git.proxmox.com Git - mirror_zfs-debian.git/blob - module/zfs/lzjb.c
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.
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.
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]
23 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
28 * We keep our own copy of this algorithm for 2 main reasons:
29 * 1. If we didn't, anyone modifying common/os/compress.c would
30 * directly break our on disk format
31 * 2. Our version of lzjb does not have a number of checks that the
32 * common/os version needs and uses
33 * 3. We initialize the lempel to ensure deterministic results,
34 * so that identical blocks can always be deduplicated.
35 * In particular, we are adding the "feature" that compress() can
36 * take a destination buffer size and return -1 if the data will not
37 * compress to d_len or less.
40 #include <sys/types.h>
44 #define MATCH_MAX ((1 << MATCH_BITS) + (MATCH_MIN - 1))
45 #define OFFSET_MASK ((1 << (16 - MATCH_BITS)) - 1)
46 #define LEMPEL_SIZE 1024
50 lzjb_compress(void *s_start
, void *d_start
, size_t s_len
, size_t d_len
, int n
)
52 uchar_t
*src
= s_start
;
53 uchar_t
*dst
= d_start
;
54 uchar_t
*cpy
, *copymap
;
55 int copymask
= 1 << (NBBY
- 1);
56 int mlen
, offset
, hash
;
58 uint16_t lempel
[LEMPEL_SIZE
] = { 0 };
60 while (src
< (uchar_t
*)s_start
+ s_len
) {
61 if ((copymask
<<= 1) == (1 << NBBY
)) {
62 if (dst
>= (uchar_t
*)d_start
+ d_len
- 1 - 2 * NBBY
)
68 if (src
> (uchar_t
*)s_start
+ s_len
- MATCH_MAX
) {
72 hash
= (src
[0] << 16) + (src
[1] << 8) + src
[2];
75 hp
= &lempel
[hash
& (LEMPEL_SIZE
- 1)];
76 offset
= (intptr_t)(src
- *hp
) & OFFSET_MASK
;
77 *hp
= (uint16_t)(uintptr_t)src
;
79 if (cpy
>= (uchar_t
*)s_start
&& cpy
!= src
&&
80 src
[0] == cpy
[0] && src
[1] == cpy
[1] && src
[2] == cpy
[2]) {
82 for (mlen
= MATCH_MIN
; mlen
< MATCH_MAX
; mlen
++)
83 if (src
[mlen
] != cpy
[mlen
])
85 *dst
++ = ((mlen
- MATCH_MIN
) << (NBBY
- MATCH_BITS
)) |
87 *dst
++ = (uchar_t
)offset
;
93 return (dst
- (uchar_t
*)d_start
);
98 lzjb_decompress(void *s_start
, void *d_start
, size_t s_len
, size_t d_len
, int n
)
100 uchar_t
*src
= s_start
;
101 uchar_t
*dst
= d_start
;
102 uchar_t
*d_end
= (uchar_t
*)d_start
+ d_len
;
103 uchar_t
*cpy
, copymap
;
104 int copymask
= 1 << (NBBY
- 1);
106 while (dst
< d_end
) {
107 if ((copymask
<<= 1) == (1 << NBBY
)) {
111 if (copymap
& copymask
) {
112 int mlen
= (src
[0] >> (NBBY
- MATCH_BITS
)) + MATCH_MIN
;
113 int offset
= ((src
[0] << NBBY
) | src
[1]) & OFFSET_MASK
;
115 if ((cpy
= dst
- offset
) < (uchar_t
*)d_start
)
117 while (--mlen
>= 0 && dst
< d_end
)