1 | /* |
2 | * LZ4 - Fast LZ compression algorithm |
3 | * Copyright (C) 2011 - 2016, Yann Collet. |
4 | * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php) |
5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions are |
7 | * met: |
8 | * * Redistributions of source code must retain the above copyright |
9 | * notice, this list of conditions and the following disclaimer. |
10 | * * Redistributions in binary form must reproduce the above |
11 | * copyright notice, this list of conditions and the following disclaimer |
12 | * in the documentation and/or other materials provided with the |
13 | * distribution. |
14 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
15 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
16 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
17 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
18 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
19 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
20 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
21 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
22 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
23 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
24 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
25 | * You can contact the author at : |
26 | * - LZ4 homepage : http://www.lz4.org |
27 | * - LZ4 source repository : https://github.com/lz4/lz4 |
28 | * |
29 | * Changed for kernel usage by: |
30 | * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> |
31 | */ |
32 | |
33 | /*-************************************ |
34 | * Dependencies |
35 | **************************************/ |
36 | #include <linux/lz4.h> |
37 | #include "lz4defs.h" |
38 | #include <linux/module.h> |
39 | #include <linux/kernel.h> |
40 | #include <asm/unaligned.h> |
41 | |
42 | static const int LZ4_minLength = (MFLIMIT + 1); |
43 | static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1)); |
44 | |
45 | /*-****************************** |
46 | * Compression functions |
47 | ********************************/ |
48 | static FORCE_INLINE U32 LZ4_hash4( |
49 | U32 sequence, |
50 | tableType_t const tableType) |
51 | { |
52 | if (tableType == byU16) |
53 | return ((sequence * 2654435761U) |
54 | >> ((MINMATCH * 8) - (LZ4_HASHLOG + 1))); |
55 | else |
56 | return ((sequence * 2654435761U) |
57 | >> ((MINMATCH * 8) - LZ4_HASHLOG)); |
58 | } |
59 | |
60 | static FORCE_INLINE U32 LZ4_hash5( |
61 | U64 sequence, |
62 | tableType_t const tableType) |
63 | { |
64 | const U32 hashLog = (tableType == byU16) |
65 | ? LZ4_HASHLOG + 1 |
66 | : LZ4_HASHLOG; |
67 | |
68 | #if LZ4_LITTLE_ENDIAN |
69 | static const U64 prime5bytes = 889523592379ULL; |
70 | |
71 | return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); |
72 | #else |
73 | static const U64 prime8bytes = 11400714785074694791ULL; |
74 | |
75 | return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog)); |
76 | #endif |
77 | } |
78 | |
79 | static FORCE_INLINE U32 LZ4_hashPosition( |
80 | const void *p, |
81 | tableType_t const tableType) |
82 | { |
83 | #if LZ4_ARCH64 |
84 | if (tableType == byU32) |
85 | return LZ4_hash5(sequence: LZ4_read_ARCH(ptr: p), tableType); |
86 | #endif |
87 | |
88 | return LZ4_hash4(sequence: LZ4_read32(ptr: p), tableType); |
89 | } |
90 | |
91 | static void LZ4_putPositionOnHash( |
92 | const BYTE *p, |
93 | U32 h, |
94 | void *tableBase, |
95 | tableType_t const tableType, |
96 | const BYTE *srcBase) |
97 | { |
98 | switch (tableType) { |
99 | case byPtr: |
100 | { |
101 | const BYTE **hashTable = (const BYTE **)tableBase; |
102 | |
103 | hashTable[h] = p; |
104 | return; |
105 | } |
106 | case byU32: |
107 | { |
108 | U32 *hashTable = (U32 *) tableBase; |
109 | |
110 | hashTable[h] = (U32)(p - srcBase); |
111 | return; |
112 | } |
113 | case byU16: |
114 | { |
115 | U16 *hashTable = (U16 *) tableBase; |
116 | |
117 | hashTable[h] = (U16)(p - srcBase); |
118 | return; |
119 | } |
120 | } |
121 | } |
122 | |
123 | static FORCE_INLINE void LZ4_putPosition( |
124 | const BYTE *p, |
125 | void *tableBase, |
126 | tableType_t tableType, |
127 | const BYTE *srcBase) |
128 | { |
129 | U32 const h = LZ4_hashPosition(p, tableType); |
130 | |
131 | LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); |
132 | } |
133 | |
134 | static const BYTE *LZ4_getPositionOnHash( |
135 | U32 h, |
136 | void *tableBase, |
137 | tableType_t tableType, |
138 | const BYTE *srcBase) |
139 | { |
140 | if (tableType == byPtr) { |
141 | const BYTE **hashTable = (const BYTE **) tableBase; |
142 | |
143 | return hashTable[h]; |
144 | } |
145 | |
146 | if (tableType == byU32) { |
147 | const U32 * const hashTable = (U32 *) tableBase; |
148 | |
149 | return hashTable[h] + srcBase; |
150 | } |
151 | |
152 | { |
153 | /* default, to ensure a return */ |
154 | const U16 * const hashTable = (U16 *) tableBase; |
155 | |
156 | return hashTable[h] + srcBase; |
157 | } |
158 | } |
159 | |
160 | static FORCE_INLINE const BYTE *LZ4_getPosition( |
161 | const BYTE *p, |
162 | void *tableBase, |
163 | tableType_t tableType, |
164 | const BYTE *srcBase) |
165 | { |
166 | U32 const h = LZ4_hashPosition(p, tableType); |
167 | |
168 | return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); |
169 | } |
170 | |
171 | |
172 | /* |
173 | * LZ4_compress_generic() : |
174 | * inlined, to ensure branches are decided at compilation time |
175 | */ |
176 | static FORCE_INLINE int LZ4_compress_generic( |
177 | LZ4_stream_t_internal * const dictPtr, |
178 | const char * const source, |
179 | char * const dest, |
180 | const int inputSize, |
181 | const int maxOutputSize, |
182 | const limitedOutput_directive outputLimited, |
183 | const tableType_t tableType, |
184 | const dict_directive dict, |
185 | const dictIssue_directive dictIssue, |
186 | const U32 acceleration) |
187 | { |
188 | const BYTE *ip = (const BYTE *) source; |
189 | const BYTE *base; |
190 | const BYTE *lowLimit; |
191 | const BYTE * const lowRefLimit = ip - dictPtr->dictSize; |
192 | const BYTE * const dictionary = dictPtr->dictionary; |
193 | const BYTE * const dictEnd = dictionary + dictPtr->dictSize; |
194 | const size_t dictDelta = dictEnd - (const BYTE *)source; |
195 | const BYTE *anchor = (const BYTE *) source; |
196 | const BYTE * const iend = ip + inputSize; |
197 | const BYTE * const mflimit = iend - MFLIMIT; |
198 | const BYTE * const matchlimit = iend - LASTLITERALS; |
199 | |
200 | BYTE *op = (BYTE *) dest; |
201 | BYTE * const olimit = op + maxOutputSize; |
202 | |
203 | U32 forwardH; |
204 | size_t refDelta = 0; |
205 | |
206 | /* Init conditions */ |
207 | if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) { |
208 | /* Unsupported inputSize, too large (or negative) */ |
209 | return 0; |
210 | } |
211 | |
212 | switch (dict) { |
213 | case noDict: |
214 | default: |
215 | base = (const BYTE *)source; |
216 | lowLimit = (const BYTE *)source; |
217 | break; |
218 | case withPrefix64k: |
219 | base = (const BYTE *)source - dictPtr->currentOffset; |
220 | lowLimit = (const BYTE *)source - dictPtr->dictSize; |
221 | break; |
222 | case usingExtDict: |
223 | base = (const BYTE *)source - dictPtr->currentOffset; |
224 | lowLimit = (const BYTE *)source; |
225 | break; |
226 | } |
227 | |
228 | if ((tableType == byU16) |
229 | && (inputSize >= LZ4_64Klimit)) { |
230 | /* Size too large (not within 64K limit) */ |
231 | return 0; |
232 | } |
233 | |
234 | if (inputSize < LZ4_minLength) { |
235 | /* Input too small, no compression (all literals) */ |
236 | goto _last_literals; |
237 | } |
238 | |
239 | /* First Byte */ |
240 | LZ4_putPosition(p: ip, tableBase: dictPtr->hashTable, tableType, srcBase: base); |
241 | ip++; |
242 | forwardH = LZ4_hashPosition(p: ip, tableType); |
243 | |
244 | /* Main Loop */ |
245 | for ( ; ; ) { |
246 | const BYTE *match; |
247 | BYTE *token; |
248 | |
249 | /* Find a match */ |
250 | { |
251 | const BYTE *forwardIp = ip; |
252 | unsigned int step = 1; |
253 | unsigned int searchMatchNb = acceleration << LZ4_SKIPTRIGGER; |
254 | |
255 | do { |
256 | U32 const h = forwardH; |
257 | |
258 | ip = forwardIp; |
259 | forwardIp += step; |
260 | step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); |
261 | |
262 | if (unlikely(forwardIp > mflimit)) |
263 | goto _last_literals; |
264 | |
265 | match = LZ4_getPositionOnHash(h, |
266 | tableBase: dictPtr->hashTable, |
267 | tableType, srcBase: base); |
268 | |
269 | if (dict == usingExtDict) { |
270 | if (match < (const BYTE *)source) { |
271 | refDelta = dictDelta; |
272 | lowLimit = dictionary; |
273 | } else { |
274 | refDelta = 0; |
275 | lowLimit = (const BYTE *)source; |
276 | } } |
277 | |
278 | forwardH = LZ4_hashPosition(p: forwardIp, |
279 | tableType); |
280 | |
281 | LZ4_putPositionOnHash(p: ip, h, tableBase: dictPtr->hashTable, |
282 | tableType, srcBase: base); |
283 | } while (((dictIssue == dictSmall) |
284 | ? (match < lowRefLimit) |
285 | : 0) |
286 | || ((tableType == byU16) |
287 | ? 0 |
288 | : (match + MAX_DISTANCE < ip)) |
289 | || (LZ4_read32(ptr: match + refDelta) |
290 | != LZ4_read32(ptr: ip))); |
291 | } |
292 | |
293 | /* Catch up */ |
294 | while (((ip > anchor) & (match + refDelta > lowLimit)) |
295 | && (unlikely(ip[-1] == match[refDelta - 1]))) { |
296 | ip--; |
297 | match--; |
298 | } |
299 | |
300 | /* Encode Literals */ |
301 | { |
302 | unsigned const int litLength = (unsigned int)(ip - anchor); |
303 | |
304 | token = op++; |
305 | |
306 | if ((outputLimited) && |
307 | /* Check output buffer overflow */ |
308 | (unlikely(op + litLength + |
309 | (2 + 1 + LASTLITERALS) + |
310 | (litLength / 255) > olimit))) |
311 | return 0; |
312 | |
313 | if (litLength >= RUN_MASK) { |
314 | int len = (int)litLength - RUN_MASK; |
315 | |
316 | *token = (RUN_MASK << ML_BITS); |
317 | |
318 | for (; len >= 255; len -= 255) |
319 | *op++ = 255; |
320 | *op++ = (BYTE)len; |
321 | } else |
322 | *token = (BYTE)(litLength << ML_BITS); |
323 | |
324 | /* Copy Literals */ |
325 | LZ4_wildCopy(dstPtr: op, srcPtr: anchor, dstEnd: op + litLength); |
326 | op += litLength; |
327 | } |
328 | |
329 | _next_match: |
330 | /* Encode Offset */ |
331 | LZ4_writeLE16(memPtr: op, value: (U16)(ip - match)); |
332 | op += 2; |
333 | |
334 | /* Encode MatchLength */ |
335 | { |
336 | unsigned int matchCode; |
337 | |
338 | if ((dict == usingExtDict) |
339 | && (lowLimit == dictionary)) { |
340 | const BYTE *limit; |
341 | |
342 | match += refDelta; |
343 | limit = ip + (dictEnd - match); |
344 | |
345 | if (limit > matchlimit) |
346 | limit = matchlimit; |
347 | |
348 | matchCode = LZ4_count(pIn: ip + MINMATCH, |
349 | pMatch: match + MINMATCH, pInLimit: limit); |
350 | |
351 | ip += MINMATCH + matchCode; |
352 | |
353 | if (ip == limit) { |
354 | unsigned const int more = LZ4_count(pIn: ip, |
355 | pMatch: (const BYTE *)source, |
356 | pInLimit: matchlimit); |
357 | |
358 | matchCode += more; |
359 | ip += more; |
360 | } |
361 | } else { |
362 | matchCode = LZ4_count(pIn: ip + MINMATCH, |
363 | pMatch: match + MINMATCH, pInLimit: matchlimit); |
364 | ip += MINMATCH + matchCode; |
365 | } |
366 | |
367 | if (outputLimited && |
368 | /* Check output buffer overflow */ |
369 | (unlikely(op + |
370 | (1 + LASTLITERALS) + |
371 | (matchCode >> 8) > olimit))) |
372 | return 0; |
373 | |
374 | if (matchCode >= ML_MASK) { |
375 | *token += ML_MASK; |
376 | matchCode -= ML_MASK; |
377 | LZ4_write32(memPtr: op, value: 0xFFFFFFFF); |
378 | |
379 | while (matchCode >= 4 * 255) { |
380 | op += 4; |
381 | LZ4_write32(memPtr: op, value: 0xFFFFFFFF); |
382 | matchCode -= 4 * 255; |
383 | } |
384 | |
385 | op += matchCode / 255; |
386 | *op++ = (BYTE)(matchCode % 255); |
387 | } else |
388 | *token += (BYTE)(matchCode); |
389 | } |
390 | |
391 | anchor = ip; |
392 | |
393 | /* Test end of chunk */ |
394 | if (ip > mflimit) |
395 | break; |
396 | |
397 | /* Fill table */ |
398 | LZ4_putPosition(p: ip - 2, tableBase: dictPtr->hashTable, tableType, srcBase: base); |
399 | |
400 | /* Test next position */ |
401 | match = LZ4_getPosition(p: ip, tableBase: dictPtr->hashTable, |
402 | tableType, srcBase: base); |
403 | |
404 | if (dict == usingExtDict) { |
405 | if (match < (const BYTE *)source) { |
406 | refDelta = dictDelta; |
407 | lowLimit = dictionary; |
408 | } else { |
409 | refDelta = 0; |
410 | lowLimit = (const BYTE *)source; |
411 | } |
412 | } |
413 | |
414 | LZ4_putPosition(p: ip, tableBase: dictPtr->hashTable, tableType, srcBase: base); |
415 | |
416 | if (((dictIssue == dictSmall) ? (match >= lowRefLimit) : 1) |
417 | && (match + MAX_DISTANCE >= ip) |
418 | && (LZ4_read32(ptr: match + refDelta) == LZ4_read32(ptr: ip))) { |
419 | token = op++; |
420 | *token = 0; |
421 | goto _next_match; |
422 | } |
423 | |
424 | /* Prepare next loop */ |
425 | forwardH = LZ4_hashPosition(p: ++ip, tableType); |
426 | } |
427 | |
428 | _last_literals: |
429 | /* Encode Last Literals */ |
430 | { |
431 | size_t const lastRun = (size_t)(iend - anchor); |
432 | |
433 | if ((outputLimited) && |
434 | /* Check output buffer overflow */ |
435 | ((op - (BYTE *)dest) + lastRun + 1 + |
436 | ((lastRun + 255 - RUN_MASK) / 255) > (U32)maxOutputSize)) |
437 | return 0; |
438 | |
439 | if (lastRun >= RUN_MASK) { |
440 | size_t accumulator = lastRun - RUN_MASK; |
441 | *op++ = RUN_MASK << ML_BITS; |
442 | for (; accumulator >= 255; accumulator -= 255) |
443 | *op++ = 255; |
444 | *op++ = (BYTE) accumulator; |
445 | } else { |
446 | *op++ = (BYTE)(lastRun << ML_BITS); |
447 | } |
448 | |
449 | LZ4_memcpy(op, anchor, lastRun); |
450 | |
451 | op += lastRun; |
452 | } |
453 | |
454 | /* End */ |
455 | return (int) (((char *)op) - dest); |
456 | } |
457 | |
458 | static int LZ4_compress_fast_extState( |
459 | void *state, |
460 | const char *source, |
461 | char *dest, |
462 | int inputSize, |
463 | int maxOutputSize, |
464 | int acceleration) |
465 | { |
466 | LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse; |
467 | #if LZ4_ARCH64 |
468 | const tableType_t tableType = byU32; |
469 | #else |
470 | const tableType_t tableType = byPtr; |
471 | #endif |
472 | |
473 | LZ4_resetStream(LZ4_stream: (LZ4_stream_t *)state); |
474 | |
475 | if (acceleration < 1) |
476 | acceleration = LZ4_ACCELERATION_DEFAULT; |
477 | |
478 | if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) { |
479 | if (inputSize < LZ4_64Klimit) |
480 | return LZ4_compress_generic(dictPtr: ctx, source, |
481 | dest, inputSize, maxOutputSize: 0, |
482 | outputLimited: noLimit, tableType: byU16, dict: noDict, |
483 | dictIssue: noDictIssue, acceleration); |
484 | else |
485 | return LZ4_compress_generic(dictPtr: ctx, source, |
486 | dest, inputSize, maxOutputSize: 0, |
487 | outputLimited: noLimit, tableType, dict: noDict, |
488 | dictIssue: noDictIssue, acceleration); |
489 | } else { |
490 | if (inputSize < LZ4_64Klimit) |
491 | return LZ4_compress_generic(dictPtr: ctx, source, |
492 | dest, inputSize, |
493 | maxOutputSize, outputLimited: limitedOutput, tableType: byU16, dict: noDict, |
494 | dictIssue: noDictIssue, acceleration); |
495 | else |
496 | return LZ4_compress_generic(dictPtr: ctx, source, |
497 | dest, inputSize, |
498 | maxOutputSize, outputLimited: limitedOutput, tableType, dict: noDict, |
499 | dictIssue: noDictIssue, acceleration); |
500 | } |
501 | } |
502 | |
503 | int LZ4_compress_fast(const char *source, char *dest, int inputSize, |
504 | int maxOutputSize, int acceleration, void *wrkmem) |
505 | { |
506 | return LZ4_compress_fast_extState(state: wrkmem, source, dest, inputSize, |
507 | maxOutputSize, acceleration); |
508 | } |
509 | EXPORT_SYMBOL(LZ4_compress_fast); |
510 | |
511 | int LZ4_compress_default(const char *source, char *dest, int inputSize, |
512 | int maxOutputSize, void *wrkmem) |
513 | { |
514 | return LZ4_compress_fast(source, dest, inputSize, |
515 | maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem); |
516 | } |
517 | EXPORT_SYMBOL(LZ4_compress_default); |
518 | |
519 | /*-****************************** |
520 | * *_destSize() variant |
521 | ********************************/ |
522 | static int LZ4_compress_destSize_generic( |
523 | LZ4_stream_t_internal * const ctx, |
524 | const char * const src, |
525 | char * const dst, |
526 | int * const srcSizePtr, |
527 | const int targetDstSize, |
528 | const tableType_t tableType) |
529 | { |
530 | const BYTE *ip = (const BYTE *) src; |
531 | const BYTE *base = (const BYTE *) src; |
532 | const BYTE *lowLimit = (const BYTE *) src; |
533 | const BYTE *anchor = ip; |
534 | const BYTE * const iend = ip + *srcSizePtr; |
535 | const BYTE * const mflimit = iend - MFLIMIT; |
536 | const BYTE * const matchlimit = iend - LASTLITERALS; |
537 | |
538 | BYTE *op = (BYTE *) dst; |
539 | BYTE * const oend = op + targetDstSize; |
540 | BYTE * const oMaxLit = op + targetDstSize - 2 /* offset */ |
541 | - 8 /* because 8 + MINMATCH == MFLIMIT */ - 1 /* token */; |
542 | BYTE * const oMaxMatch = op + targetDstSize |
543 | - (LASTLITERALS + 1 /* token */); |
544 | BYTE * const oMaxSeq = oMaxLit - 1 /* token */; |
545 | |
546 | U32 forwardH; |
547 | |
548 | /* Init conditions */ |
549 | /* Impossible to store anything */ |
550 | if (targetDstSize < 1) |
551 | return 0; |
552 | /* Unsupported input size, too large (or negative) */ |
553 | if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) |
554 | return 0; |
555 | /* Size too large (not within 64K limit) */ |
556 | if ((tableType == byU16) && (*srcSizePtr >= LZ4_64Klimit)) |
557 | return 0; |
558 | /* Input too small, no compression (all literals) */ |
559 | if (*srcSizePtr < LZ4_minLength) |
560 | goto _last_literals; |
561 | |
562 | /* First Byte */ |
563 | *srcSizePtr = 0; |
564 | LZ4_putPosition(p: ip, tableBase: ctx->hashTable, tableType, srcBase: base); |
565 | ip++; forwardH = LZ4_hashPosition(p: ip, tableType); |
566 | |
567 | /* Main Loop */ |
568 | for ( ; ; ) { |
569 | const BYTE *match; |
570 | BYTE *token; |
571 | |
572 | /* Find a match */ |
573 | { |
574 | const BYTE *forwardIp = ip; |
575 | unsigned int step = 1; |
576 | unsigned int searchMatchNb = 1 << LZ4_SKIPTRIGGER; |
577 | |
578 | do { |
579 | U32 h = forwardH; |
580 | |
581 | ip = forwardIp; |
582 | forwardIp += step; |
583 | step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); |
584 | |
585 | if (unlikely(forwardIp > mflimit)) |
586 | goto _last_literals; |
587 | |
588 | match = LZ4_getPositionOnHash(h, tableBase: ctx->hashTable, |
589 | tableType, srcBase: base); |
590 | forwardH = LZ4_hashPosition(p: forwardIp, |
591 | tableType); |
592 | LZ4_putPositionOnHash(p: ip, h, |
593 | tableBase: ctx->hashTable, tableType, |
594 | srcBase: base); |
595 | |
596 | } while (((tableType == byU16) |
597 | ? 0 |
598 | : (match + MAX_DISTANCE < ip)) |
599 | || (LZ4_read32(ptr: match) != LZ4_read32(ptr: ip))); |
600 | } |
601 | |
602 | /* Catch up */ |
603 | while ((ip > anchor) |
604 | && (match > lowLimit) |
605 | && (unlikely(ip[-1] == match[-1]))) { |
606 | ip--; |
607 | match--; |
608 | } |
609 | |
610 | /* Encode Literal length */ |
611 | { |
612 | unsigned int litLength = (unsigned int)(ip - anchor); |
613 | |
614 | token = op++; |
615 | if (op + ((litLength + 240) / 255) |
616 | + litLength > oMaxLit) { |
617 | /* Not enough space for a last match */ |
618 | op--; |
619 | goto _last_literals; |
620 | } |
621 | if (litLength >= RUN_MASK) { |
622 | unsigned int len = litLength - RUN_MASK; |
623 | *token = (RUN_MASK<<ML_BITS); |
624 | for (; len >= 255; len -= 255) |
625 | *op++ = 255; |
626 | *op++ = (BYTE)len; |
627 | } else |
628 | *token = (BYTE)(litLength << ML_BITS); |
629 | |
630 | /* Copy Literals */ |
631 | LZ4_wildCopy(dstPtr: op, srcPtr: anchor, dstEnd: op + litLength); |
632 | op += litLength; |
633 | } |
634 | |
635 | _next_match: |
636 | /* Encode Offset */ |
637 | LZ4_writeLE16(memPtr: op, value: (U16)(ip - match)); op += 2; |
638 | |
639 | /* Encode MatchLength */ |
640 | { |
641 | size_t matchLength = LZ4_count(pIn: ip + MINMATCH, |
642 | pMatch: match + MINMATCH, pInLimit: matchlimit); |
643 | |
644 | if (op + ((matchLength + 240)/255) > oMaxMatch) { |
645 | /* Match description too long : reduce it */ |
646 | matchLength = (15 - 1) + (oMaxMatch - op) * 255; |
647 | } |
648 | ip += MINMATCH + matchLength; |
649 | |
650 | if (matchLength >= ML_MASK) { |
651 | *token += ML_MASK; |
652 | matchLength -= ML_MASK; |
653 | while (matchLength >= 255) { |
654 | matchLength -= 255; |
655 | *op++ = 255; |
656 | } |
657 | *op++ = (BYTE)matchLength; |
658 | } else |
659 | *token += (BYTE)(matchLength); |
660 | } |
661 | |
662 | anchor = ip; |
663 | |
664 | /* Test end of block */ |
665 | if (ip > mflimit) |
666 | break; |
667 | if (op > oMaxSeq) |
668 | break; |
669 | |
670 | /* Fill table */ |
671 | LZ4_putPosition(p: ip - 2, tableBase: ctx->hashTable, tableType, srcBase: base); |
672 | |
673 | /* Test next position */ |
674 | match = LZ4_getPosition(p: ip, tableBase: ctx->hashTable, tableType, srcBase: base); |
675 | LZ4_putPosition(p: ip, tableBase: ctx->hashTable, tableType, srcBase: base); |
676 | |
677 | if ((match + MAX_DISTANCE >= ip) |
678 | && (LZ4_read32(ptr: match) == LZ4_read32(ptr: ip))) { |
679 | token = op++; *token = 0; |
680 | goto _next_match; |
681 | } |
682 | |
683 | /* Prepare next loop */ |
684 | forwardH = LZ4_hashPosition(p: ++ip, tableType); |
685 | } |
686 | |
687 | _last_literals: |
688 | /* Encode Last Literals */ |
689 | { |
690 | size_t lastRunSize = (size_t)(iend - anchor); |
691 | |
692 | if (op + 1 /* token */ |
693 | + ((lastRunSize + 240) / 255) /* litLength */ |
694 | + lastRunSize /* literals */ > oend) { |
695 | /* adapt lastRunSize to fill 'dst' */ |
696 | lastRunSize = (oend - op) - 1; |
697 | lastRunSize -= (lastRunSize + 240) / 255; |
698 | } |
699 | ip = anchor + lastRunSize; |
700 | |
701 | if (lastRunSize >= RUN_MASK) { |
702 | size_t accumulator = lastRunSize - RUN_MASK; |
703 | |
704 | *op++ = RUN_MASK << ML_BITS; |
705 | for (; accumulator >= 255; accumulator -= 255) |
706 | *op++ = 255; |
707 | *op++ = (BYTE) accumulator; |
708 | } else { |
709 | *op++ = (BYTE)(lastRunSize<<ML_BITS); |
710 | } |
711 | LZ4_memcpy(op, anchor, lastRunSize); |
712 | op += lastRunSize; |
713 | } |
714 | |
715 | /* End */ |
716 | *srcSizePtr = (int) (((const char *)ip) - src); |
717 | return (int) (((char *)op) - dst); |
718 | } |
719 | |
720 | static int LZ4_compress_destSize_extState( |
721 | LZ4_stream_t *state, |
722 | const char *src, |
723 | char *dst, |
724 | int *srcSizePtr, |
725 | int targetDstSize) |
726 | { |
727 | #if LZ4_ARCH64 |
728 | const tableType_t tableType = byU32; |
729 | #else |
730 | const tableType_t tableType = byPtr; |
731 | #endif |
732 | |
733 | LZ4_resetStream(LZ4_stream: state); |
734 | |
735 | if (targetDstSize >= LZ4_COMPRESSBOUND(*srcSizePtr)) { |
736 | /* compression success is guaranteed */ |
737 | return LZ4_compress_fast_extState( |
738 | state, source: src, dest: dst, inputSize: *srcSizePtr, |
739 | maxOutputSize: targetDstSize, acceleration: 1); |
740 | } else { |
741 | if (*srcSizePtr < LZ4_64Klimit) |
742 | return LZ4_compress_destSize_generic( |
743 | ctx: &state->internal_donotuse, |
744 | src, dst, srcSizePtr, |
745 | targetDstSize, tableType: byU16); |
746 | else |
747 | return LZ4_compress_destSize_generic( |
748 | ctx: &state->internal_donotuse, |
749 | src, dst, srcSizePtr, |
750 | targetDstSize, tableType); |
751 | } |
752 | } |
753 | |
754 | |
755 | int LZ4_compress_destSize( |
756 | const char *src, |
757 | char *dst, |
758 | int *srcSizePtr, |
759 | int targetDstSize, |
760 | void *wrkmem) |
761 | { |
762 | return LZ4_compress_destSize_extState(state: wrkmem, src, dst, srcSizePtr, |
763 | targetDstSize); |
764 | } |
765 | EXPORT_SYMBOL(LZ4_compress_destSize); |
766 | |
767 | /*-****************************** |
768 | * Streaming functions |
769 | ********************************/ |
770 | void LZ4_resetStream(LZ4_stream_t *LZ4_stream) |
771 | { |
772 | memset(LZ4_stream, 0, sizeof(LZ4_stream_t)); |
773 | } |
774 | |
775 | int LZ4_loadDict(LZ4_stream_t *LZ4_dict, |
776 | const char *dictionary, int dictSize) |
777 | { |
778 | LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse; |
779 | const BYTE *p = (const BYTE *)dictionary; |
780 | const BYTE * const dictEnd = p + dictSize; |
781 | const BYTE *base; |
782 | |
783 | if ((dict->initCheck) |
784 | || (dict->currentOffset > 1 * GB)) { |
785 | /* Uninitialized structure, or reuse overflow */ |
786 | LZ4_resetStream(LZ4_stream: LZ4_dict); |
787 | } |
788 | |
789 | if (dictSize < (int)HASH_UNIT) { |
790 | dict->dictionary = NULL; |
791 | dict->dictSize = 0; |
792 | return 0; |
793 | } |
794 | |
795 | if ((dictEnd - p) > 64 * KB) |
796 | p = dictEnd - 64 * KB; |
797 | dict->currentOffset += 64 * KB; |
798 | base = p - dict->currentOffset; |
799 | dict->dictionary = p; |
800 | dict->dictSize = (U32)(dictEnd - p); |
801 | dict->currentOffset += dict->dictSize; |
802 | |
803 | while (p <= dictEnd - HASH_UNIT) { |
804 | LZ4_putPosition(p, tableBase: dict->hashTable, tableType: byU32, srcBase: base); |
805 | p += 3; |
806 | } |
807 | |
808 | return dict->dictSize; |
809 | } |
810 | EXPORT_SYMBOL(LZ4_loadDict); |
811 | |
812 | static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict, |
813 | const BYTE *src) |
814 | { |
815 | if ((LZ4_dict->currentOffset > 0x80000000) || |
816 | ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { |
817 | /* address space overflow */ |
818 | /* rescale hash table */ |
819 | U32 const delta = LZ4_dict->currentOffset - 64 * KB; |
820 | const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; |
821 | int i; |
822 | |
823 | for (i = 0; i < LZ4_HASH_SIZE_U32; i++) { |
824 | if (LZ4_dict->hashTable[i] < delta) |
825 | LZ4_dict->hashTable[i] = 0; |
826 | else |
827 | LZ4_dict->hashTable[i] -= delta; |
828 | } |
829 | LZ4_dict->currentOffset = 64 * KB; |
830 | if (LZ4_dict->dictSize > 64 * KB) |
831 | LZ4_dict->dictSize = 64 * KB; |
832 | LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; |
833 | } |
834 | } |
835 | |
836 | int LZ4_saveDict(LZ4_stream_t *LZ4_dict, char *safeBuffer, int dictSize) |
837 | { |
838 | LZ4_stream_t_internal * const dict = &LZ4_dict->internal_donotuse; |
839 | const BYTE * const previousDictEnd = dict->dictionary + dict->dictSize; |
840 | |
841 | if ((U32)dictSize > 64 * KB) { |
842 | /* useless to define a dictionary > 64 * KB */ |
843 | dictSize = 64 * KB; |
844 | } |
845 | if ((U32)dictSize > dict->dictSize) |
846 | dictSize = dict->dictSize; |
847 | |
848 | memmove(safeBuffer, previousDictEnd - dictSize, dictSize); |
849 | |
850 | dict->dictionary = (const BYTE *)safeBuffer; |
851 | dict->dictSize = (U32)dictSize; |
852 | |
853 | return dictSize; |
854 | } |
855 | EXPORT_SYMBOL(LZ4_saveDict); |
856 | |
857 | int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source, |
858 | char *dest, int inputSize, int maxOutputSize, int acceleration) |
859 | { |
860 | LZ4_stream_t_internal *streamPtr = &LZ4_stream->internal_donotuse; |
861 | const BYTE * const dictEnd = streamPtr->dictionary |
862 | + streamPtr->dictSize; |
863 | |
864 | const BYTE *smallest = (const BYTE *) source; |
865 | |
866 | if (streamPtr->initCheck) { |
867 | /* Uninitialized structure detected */ |
868 | return 0; |
869 | } |
870 | |
871 | if ((streamPtr->dictSize > 0) && (smallest > dictEnd)) |
872 | smallest = dictEnd; |
873 | |
874 | LZ4_renormDictT(LZ4_dict: streamPtr, src: smallest); |
875 | |
876 | if (acceleration < 1) |
877 | acceleration = LZ4_ACCELERATION_DEFAULT; |
878 | |
879 | /* Check overlapping input/dictionary space */ |
880 | { |
881 | const BYTE *sourceEnd = (const BYTE *) source + inputSize; |
882 | |
883 | if ((sourceEnd > streamPtr->dictionary) |
884 | && (sourceEnd < dictEnd)) { |
885 | streamPtr->dictSize = (U32)(dictEnd - sourceEnd); |
886 | if (streamPtr->dictSize > 64 * KB) |
887 | streamPtr->dictSize = 64 * KB; |
888 | if (streamPtr->dictSize < 4) |
889 | streamPtr->dictSize = 0; |
890 | streamPtr->dictionary = dictEnd - streamPtr->dictSize; |
891 | } |
892 | } |
893 | |
894 | /* prefix mode : source data follows dictionary */ |
895 | if (dictEnd == (const BYTE *)source) { |
896 | int result; |
897 | |
898 | if ((streamPtr->dictSize < 64 * KB) && |
899 | (streamPtr->dictSize < streamPtr->currentOffset)) { |
900 | result = LZ4_compress_generic( |
901 | dictPtr: streamPtr, source, dest, inputSize, |
902 | maxOutputSize, outputLimited: limitedOutput, tableType: byU32, |
903 | dict: withPrefix64k, dictIssue: dictSmall, acceleration); |
904 | } else { |
905 | result = LZ4_compress_generic( |
906 | dictPtr: streamPtr, source, dest, inputSize, |
907 | maxOutputSize, outputLimited: limitedOutput, tableType: byU32, |
908 | dict: withPrefix64k, dictIssue: noDictIssue, acceleration); |
909 | } |
910 | streamPtr->dictSize += (U32)inputSize; |
911 | streamPtr->currentOffset += (U32)inputSize; |
912 | return result; |
913 | } |
914 | |
915 | /* external dictionary mode */ |
916 | { |
917 | int result; |
918 | |
919 | if ((streamPtr->dictSize < 64 * KB) && |
920 | (streamPtr->dictSize < streamPtr->currentOffset)) { |
921 | result = LZ4_compress_generic( |
922 | dictPtr: streamPtr, source, dest, inputSize, |
923 | maxOutputSize, outputLimited: limitedOutput, tableType: byU32, |
924 | dict: usingExtDict, dictIssue: dictSmall, acceleration); |
925 | } else { |
926 | result = LZ4_compress_generic( |
927 | dictPtr: streamPtr, source, dest, inputSize, |
928 | maxOutputSize, outputLimited: limitedOutput, tableType: byU32, |
929 | dict: usingExtDict, dictIssue: noDictIssue, acceleration); |
930 | } |
931 | streamPtr->dictionary = (const BYTE *)source; |
932 | streamPtr->dictSize = (U32)inputSize; |
933 | streamPtr->currentOffset += (U32)inputSize; |
934 | return result; |
935 | } |
936 | } |
937 | EXPORT_SYMBOL(LZ4_compress_fast_continue); |
938 | |
939 | MODULE_LICENSE("Dual BSD/GPL" ); |
940 | MODULE_DESCRIPTION("LZ4 compressor" ); |
941 | |