Merge branch 'x86-spinlocks-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...
[linux-2.6-block.git] / lib / lz4 / lz4_compress.c
1 /*
2  * LZ4 - Fast LZ compression algorithm
3  * Copyright (C) 2011-2012, Yann Collet.
4  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
5
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are
8  * met:
9  *
10  *     * Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *     * Redistributions in binary form must reproduce the above
13  * copyright notice, this list of conditions and the following disclaimer
14  * in the documentation and/or other materials provided with the
15  * distribution.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28  *
29  * You can contact the author at :
30  * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
31  * - LZ4 source repository : http://code.google.com/p/lz4/
32  *
33  *  Changed for kernel use by:
34  *  Chanho Min <chanho.min@lge.com>
35  */
36
37 #include <linux/module.h>
38 #include <linux/kernel.h>
39 #include <linux/lz4.h>
40 #include <asm/unaligned.h>
41 #include "lz4defs.h"
42
43 /*
44  * LZ4_compressCtx :
45  * -----------------
46  * Compress 'isize' bytes from 'source' into an output buffer 'dest' of
47  * maximum size 'maxOutputSize'.  * If it cannot achieve it, compression
48  * will stop, and result of the function will be zero.
49  * return : the number of bytes written in buffer 'dest', or 0 if the
50  * compression fails
51  */
52 static inline int lz4_compressctx(void *ctx,
53                 const char *source,
54                 char *dest,
55                 int isize,
56                 int maxoutputsize)
57 {
58         HTYPE *hashtable = (HTYPE *)ctx;
59         const u8 *ip = (u8 *)source;
60 #if LZ4_ARCH64
61         const BYTE * const base = ip;
62 #else
63         const int base = 0;
64 #endif
65         const u8 *anchor = ip;
66         const u8 *const iend = ip + isize;
67         const u8 *const mflimit = iend - MFLIMIT;
68         #define MATCHLIMIT (iend - LASTLITERALS)
69
70         u8 *op = (u8 *) dest;
71         u8 *const oend = op + maxoutputsize;
72         int length;
73         const int skipstrength = SKIPSTRENGTH;
74         u32 forwardh;
75         int lastrun;
76
77         /* Init */
78         if (isize < MINLENGTH)
79                 goto _last_literals;
80
81         memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);
82
83         /* First Byte */
84         hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
85         ip++;
86         forwardh = LZ4_HASH_VALUE(ip);
87
88         /* Main Loop */
89         for (;;) {
90                 int findmatchattempts = (1U << skipstrength) + 3;
91                 const u8 *forwardip = ip;
92                 const u8 *ref;
93                 u8 *token;
94
95                 /* Find a match */
96                 do {
97                         u32 h = forwardh;
98                         int step = findmatchattempts++ >> skipstrength;
99                         ip = forwardip;
100                         forwardip = ip + step;
101
102                         if (unlikely(forwardip > mflimit))
103                                 goto _last_literals;
104
105                         forwardh = LZ4_HASH_VALUE(forwardip);
106                         ref = base + hashtable[h];
107                         hashtable[h] = ip - base;
108                 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
109
110                 /* Catch up */
111                 while ((ip > anchor) && (ref > (u8 *)source) &&
112                         unlikely(ip[-1] == ref[-1])) {
113                         ip--;
114                         ref--;
115                 }
116
117                 /* Encode Literal length */
118                 length = (int)(ip - anchor);
119                 token = op++;
120                 /* check output limit */
121                 if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
122                         (length >> 8) > oend))
123                         return 0;
124
125                 if (length >= (int)RUN_MASK) {
126                         int len;
127                         *token = (RUN_MASK << ML_BITS);
128                         len = length - RUN_MASK;
129                         for (; len > 254 ; len -= 255)
130                                 *op++ = 255;
131                         *op++ = (u8)len;
132                 } else
133                         *token = (length << ML_BITS);
134
135                 /* Copy Literals */
136                 LZ4_BLINDCOPY(anchor, op, length);
137 _next_match:
138                 /* Encode Offset */
139                 LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));
140
141                 /* Start Counting */
142                 ip += MINMATCH;
143                 /* MinMatch verified */
144                 ref += MINMATCH;
145                 anchor = ip;
146                 while (likely(ip < MATCHLIMIT - (STEPSIZE - 1))) {
147                         #if LZ4_ARCH64
148                         u64 diff = A64(ref) ^ A64(ip);
149                         #else
150                         u32 diff = A32(ref) ^ A32(ip);
151                         #endif
152                         if (!diff) {
153                                 ip += STEPSIZE;
154                                 ref += STEPSIZE;
155                                 continue;
156                         }
157                         ip += LZ4_NBCOMMONBYTES(diff);
158                         goto _endcount;
159                 }
160                 #if LZ4_ARCH64
161                 if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
162                         ip += 4;
163                         ref += 4;
164                 }
165                 #endif
166                 if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
167                         ip += 2;
168                         ref += 2;
169                 }
170                 if ((ip < MATCHLIMIT) && (*ref == *ip))
171                         ip++;
172 _endcount:
173                 /* Encode MatchLength */
174                 length = (int)(ip - anchor);
175                 /* Check output limit */
176                 if (unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend))
177                         return 0;
178                 if (length >= (int)ML_MASK) {
179                         *token += ML_MASK;
180                         length -= ML_MASK;
181                         for (; length > 509 ; length -= 510) {
182                                 *op++ = 255;
183                                 *op++ = 255;
184                         }
185                         if (length > 254) {
186                                 length -= 255;
187                                 *op++ = 255;
188                         }
189                         *op++ = (u8)length;
190                 } else
191                         *token += length;
192
193                 /* Test end of chunk */
194                 if (ip > mflimit) {
195                         anchor = ip;
196                         break;
197                 }
198
199                 /* Fill table */
200                 hashtable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;
201
202                 /* Test next position */
203                 ref = base + hashtable[LZ4_HASH_VALUE(ip)];
204                 hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
205                 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
206                         token = op++;
207                         *token = 0;
208                         goto _next_match;
209                 }
210
211                 /* Prepare next loop */
212                 anchor = ip++;
213                 forwardh = LZ4_HASH_VALUE(ip);
214         }
215
216 _last_literals:
217         /* Encode Last Literals */
218         lastrun = (int)(iend - anchor);
219         if (((char *)op - dest) + lastrun + 1
220                 + ((lastrun + 255 - RUN_MASK) / 255) > (u32)maxoutputsize)
221                 return 0;
222
223         if (lastrun >= (int)RUN_MASK) {
224                 *op++ = (RUN_MASK << ML_BITS);
225                 lastrun -= RUN_MASK;
226                 for (; lastrun > 254 ; lastrun -= 255)
227                         *op++ = 255;
228                 *op++ = (u8)lastrun;
229         } else
230                 *op++ = (lastrun << ML_BITS);
231         memcpy(op, anchor, iend - anchor);
232         op += iend - anchor;
233
234         /* End */
235         return (int)(((char *)op) - dest);
236 }
237
238 static inline int lz4_compress64kctx(void *ctx,
239                 const char *source,
240                 char *dest,
241                 int isize,
242                 int maxoutputsize)
243 {
244         u16 *hashtable = (u16 *)ctx;
245         const u8 *ip = (u8 *) source;
246         const u8 *anchor = ip;
247         const u8 *const base = ip;
248         const u8 *const iend = ip + isize;
249         const u8 *const mflimit = iend - MFLIMIT;
250         #define MATCHLIMIT (iend - LASTLITERALS)
251
252         u8 *op = (u8 *) dest;
253         u8 *const oend = op + maxoutputsize;
254         int len, length;
255         const int skipstrength = SKIPSTRENGTH;
256         u32 forwardh;
257         int lastrun;
258
259         /* Init */
260         if (isize < MINLENGTH)
261                 goto _last_literals;
262
263         memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);
264
265         /* First Byte */
266         ip++;
267         forwardh = LZ4_HASH64K_VALUE(ip);
268
269         /* Main Loop */
270         for (;;) {
271                 int findmatchattempts = (1U << skipstrength) + 3;
272                 const u8 *forwardip = ip;
273                 const u8 *ref;
274                 u8 *token;
275
276                 /* Find a match */
277                 do {
278                         u32 h = forwardh;
279                         int step = findmatchattempts++ >> skipstrength;
280                         ip = forwardip;
281                         forwardip = ip + step;
282
283                         if (forwardip > mflimit)
284                                 goto _last_literals;
285
286                         forwardh = LZ4_HASH64K_VALUE(forwardip);
287                         ref = base + hashtable[h];
288                         hashtable[h] = (u16)(ip - base);
289                 } while (A32(ref) != A32(ip));
290
291                 /* Catch up */
292                 while ((ip > anchor) && (ref > (u8 *)source)
293                         && (ip[-1] == ref[-1])) {
294                         ip--;
295                         ref--;
296                 }
297
298                 /* Encode Literal length */
299                 length = (int)(ip - anchor);
300                 token = op++;
301                 /* Check output limit */
302                 if (unlikely(op + length + (2 + 1 + LASTLITERALS)
303                         + (length >> 8) > oend))
304                         return 0;
305                 if (length >= (int)RUN_MASK) {
306                         *token = (RUN_MASK << ML_BITS);
307                         len = length - RUN_MASK;
308                         for (; len > 254 ; len -= 255)
309                                 *op++ = 255;
310                         *op++ = (u8)len;
311                 } else
312                         *token = (length << ML_BITS);
313
314                 /* Copy Literals */
315                 LZ4_BLINDCOPY(anchor, op, length);
316
317 _next_match:
318                 /* Encode Offset */
319                 LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));
320
321                 /* Start Counting */
322                 ip += MINMATCH;
323                 /* MinMatch verified */
324                 ref += MINMATCH;
325                 anchor = ip;
326
327                 while (ip < MATCHLIMIT - (STEPSIZE - 1)) {
328                         #if LZ4_ARCH64
329                         u64 diff = A64(ref) ^ A64(ip);
330                         #else
331                         u32 diff = A32(ref) ^ A32(ip);
332                         #endif
333
334                         if (!diff) {
335                                 ip += STEPSIZE;
336                                 ref += STEPSIZE;
337                                 continue;
338                         }
339                         ip += LZ4_NBCOMMONBYTES(diff);
340                         goto _endcount;
341                 }
342                 #if LZ4_ARCH64
343                 if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
344                         ip += 4;
345                         ref += 4;
346                 }
347                 #endif
348                 if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
349                         ip += 2;
350                         ref += 2;
351                 }
352                 if ((ip < MATCHLIMIT) && (*ref == *ip))
353                         ip++;
354 _endcount:
355
356                 /* Encode MatchLength */
357                 len = (int)(ip - anchor);
358                 /* Check output limit */
359                 if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
360                         return 0;
361                 if (len >= (int)ML_MASK) {
362                         *token += ML_MASK;
363                         len -= ML_MASK;
364                         for (; len > 509 ; len -= 510) {
365                                 *op++ = 255;
366                                 *op++ = 255;
367                         }
368                         if (len > 254) {
369                                 len -= 255;
370                                 *op++ = 255;
371                         }
372                         *op++ = (u8)len;
373                 } else
374                         *token += len;
375
376                 /* Test end of chunk */
377                 if (ip > mflimit) {
378                         anchor = ip;
379                         break;
380                 }
381
382                 /* Fill table */
383                 hashtable[LZ4_HASH64K_VALUE(ip-2)] = (u16)(ip - 2 - base);
384
385                 /* Test next position */
386                 ref = base + hashtable[LZ4_HASH64K_VALUE(ip)];
387                 hashtable[LZ4_HASH64K_VALUE(ip)] = (u16)(ip - base);
388                 if (A32(ref) == A32(ip)) {
389                         token = op++;
390                         *token = 0;
391                         goto _next_match;
392                 }
393
394                 /* Prepare next loop */
395                 anchor = ip++;
396                 forwardh = LZ4_HASH64K_VALUE(ip);
397         }
398
399 _last_literals:
400         /* Encode Last Literals */
401         lastrun = (int)(iend - anchor);
402         if (op + lastrun + 1 + (lastrun - RUN_MASK + 255) / 255 > oend)
403                 return 0;
404         if (lastrun >= (int)RUN_MASK) {
405                 *op++ = (RUN_MASK << ML_BITS);
406                 lastrun -= RUN_MASK;
407                 for (; lastrun > 254 ; lastrun -= 255)
408                         *op++ = 255;
409                 *op++ = (u8)lastrun;
410         } else
411                 *op++ = (lastrun << ML_BITS);
412         memcpy(op, anchor, iend - anchor);
413         op += iend - anchor;
414         /* End */
415         return (int)(((char *)op) - dest);
416 }
417
418 int lz4_compress(const unsigned char *src, size_t src_len,
419                         unsigned char *dst, size_t *dst_len, void *wrkmem)
420 {
421         int ret = -1;
422         int out_len = 0;
423
424         if (src_len < LZ4_64KLIMIT)
425                 out_len = lz4_compress64kctx(wrkmem, src, dst, src_len,
426                                 lz4_compressbound(src_len));
427         else
428                 out_len = lz4_compressctx(wrkmem, src, dst, src_len,
429                                 lz4_compressbound(src_len));
430
431         if (out_len < 0)
432                 goto exit;
433
434         *dst_len = out_len;
435
436         return 0;
437 exit:
438         return ret;
439 }
440 EXPORT_SYMBOL(lz4_compress);
441
442 MODULE_LICENSE("Dual BSD/GPL");
443 MODULE_DESCRIPTION("LZ4 compressor");