1/*
2Copyright (c) 2015-2016, Apple Inc. All rights reserved.
3
4Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
5
61. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
7
82. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
9 in the documentation and/or other materials provided with the distribution.
10
113. Neither the name of the copyright holder(s) nor the names of any contributors may be used to endorse or promote products derived
12 from this software without specific prior written permission.
13
14THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
15LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
16COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
17(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
18HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
19ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
20*/
21
22// LZFSE encode API
23
24#include "lzfse.h"
25#include "lzfse_internal.h"
26
27size_t lzfse_encode_scratch_size() {
28 size_t s1 = sizeof(lzfse_encoder_state);
29 size_t s2 = lzvn_encode_scratch_size();
30 return (s1 > s2) ? s1 : s2; // max(lzfse,lzvn)
31}
32
33size_t lzfse_encode_buffer(uint8_t *__restrict dst_buffer, size_t dst_size,
34 const uint8_t *__restrict src_buffer,
35 size_t src_size, void *__restrict scratch_buffer) {
36 const size_t original_size = src_size;
37
38 // If input is really really small, go directly to uncompressed buffer
39 // (because LZVN will refuse to encode it, and we will report a failure)
40 if (src_size < LZVN_ENCODE_MIN_SRC_SIZE)
41 goto try_uncompressed;
42
43 // If input is too small, try encoding with LZVN
44 if (src_size < LZFSE_ENCODE_LZVN_THRESHOLD) {
45 // need header + end-of-stream marker
46 size_t extra_size = 4 + sizeof(lzvn_compressed_block_header);
47 if (dst_size <= extra_size)
48 goto try_uncompressed; // DST is really too small, give up
49
50 size_t sz = lzvn_encode_buffer(
51 dst_buffer + sizeof(lzvn_compressed_block_header),
52 dst_size - extra_size, src_buffer, src_size, scratch_buffer);
53 if (sz == 0 || sz >= src_size)
54 goto try_uncompressed; // failed, or no compression, fall back to
55 // uncompressed block
56
57 // If we could encode, setup header and end-of-stream marker (we left room
58 // for them, no need to test)
59 lzvn_compressed_block_header header;
60 header.magic = LZFSE_COMPRESSEDLZVN_BLOCK_MAGIC;
61 header.n_raw_bytes = (uint32_t)src_size;
62 header.n_payload_bytes = (uint32_t)sz;
63 memcpy(dst_buffer, &header, sizeof(header));
64 store4(dst_buffer + sizeof(lzvn_compressed_block_header) + sz,
65 LZFSE_ENDOFSTREAM_BLOCK_MAGIC);
66
67 return sz + extra_size;
68 }
69
70 // Try encoding with LZFSE
71 {
72 lzfse_encoder_state *state = scratch_buffer;
73 memset(state, 0x00, sizeof *state);
74 if (lzfse_encode_init(state) != LZFSE_STATUS_OK)
75 goto try_uncompressed;
76 state->dst = dst_buffer;
77 state->dst_begin = dst_buffer;
78 state->dst_end = &dst_buffer[dst_size];
79 state->src = src_buffer;
80 state->src_encode_i = 0;
81
82 if (src_size >= 0xffffffffU) {
83 // lzfse only uses 32 bits for offsets internally, so if the input
84 // buffer is really huge, we need to process it in smaller chunks.
85 // Note that we switch over to this path for sizes much smaller
86 // 2GB because it's actually faster to change algorithms well before
87 // it's necessary for correctness.
88 // The first chunk, we just process normally.
89 const lzfse_offset encoder_block_size = 262144;
90 state->src_end = encoder_block_size;
91 if (lzfse_encode_base(state) != LZFSE_STATUS_OK)
92 goto try_uncompressed;
93 src_size -= encoder_block_size;
94 while (src_size >= encoder_block_size) {
95 // All subsequent chunks require a translation to keep the offsets
96 // from getting too big. Note that we are always going from
97 // encoder_block_size up to 2*encoder_block_size so that the
98 // offsets remain positive (as opposed to resetting to zero and
99 // having negative offsets).
100 state->src_end = 2 * encoder_block_size;
101 if (lzfse_encode_base(state) != LZFSE_STATUS_OK)
102 goto try_uncompressed;
103 lzfse_encode_translate(state, encoder_block_size);
104 src_size -= encoder_block_size;
105 }
106 // Set the end for the final chunk.
107 state->src_end = encoder_block_size + (lzfse_offset)src_size;
108 }
109 // If the source buffer is small enough to use 32-bit offsets, we simply
110 // encode the whole thing in a single chunk.
111 else
112 state->src_end = (lzfse_offset)src_size;
113 // This is either the trailing chunk (if the source file is huge), or
114 // the whole source file.
115 if (lzfse_encode_base(state) != LZFSE_STATUS_OK)
116 goto try_uncompressed;
117 if (lzfse_encode_finish(state) != LZFSE_STATUS_OK)
118 goto try_uncompressed;
119 // No error occured, return compressed size.
120 return state->dst - dst_buffer;
121 }
122
123try_uncompressed:
124 // Compression failed for some reason. If we can fit the data into the
125 // output buffer uncompressed, go ahead and do that instead.
126 if (original_size + 12 <= dst_size && original_size < INT32_MAX) {
127 uncompressed_block_header header = {.magic = LZFSE_UNCOMPRESSED_BLOCK_MAGIC,
128 .n_raw_bytes = (uint32_t)src_size};
129 uint8_t *dst_end = dst_buffer;
130 memcpy(dst_end, &header, sizeof header);
131 dst_end += sizeof header;
132 memcpy(dst_end, src_buffer, original_size);
133 dst_end += original_size;
134 store4(dst_end, LZFSE_ENDOFSTREAM_BLOCK_MAGIC);
135 dst_end += 4;
136 return dst_end - dst_buffer;
137 }
138
139 // Otherwise, there's nothing we can do, so return zero.
140 return 0;
141}
142