2 * Copyright (c) 2017-present, Facebook, Inc.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
10 #include <stdlib.h> /* malloc, free */
11 #include <limits.h> /* UINT_MAX */
14 #define XXH_STATIC_LINKING_ONLY
15 #define XXH_NAMESPACE ZSTD_
18 #define ZSTD_STATIC_LINKING_ONLY
20 #include "zstd_errors.h"
22 #include "zstd_seekable.h"
24 #define CHECK_Z(f) { size_t const ret = (f); if (ret != 0) return ret; }
27 #define ERROR(name) ((size_t)-ZSTD_error_##name)
31 #define MIN(a, b) ((a) < (b) ? (a) : (b))
32 #define MAX(a, b) ((a) > (b) ? (a) : (b))
40 struct ZSTD_frameLog_s {
41 framelogEntry_t* entries;
47 /* for use when streaming out the seek table */
52 struct ZSTD_seekable_CStream_s {
53 ZSTD_CStream* cstream;
54 ZSTD_frameLog framelog;
59 XXH64_state_t xxhState;
66 size_t ZSTD_seekable_frameLog_allocVec(ZSTD_frameLog* fl)
68 /* allocate some initial space */
69 size_t const FRAMELOG_STARTING_CAPACITY = 16;
70 fl->entries = (framelogEntry_t*)malloc(
71 sizeof(framelogEntry_t) * FRAMELOG_STARTING_CAPACITY);
72 if (fl->entries == NULL) return ERROR(memory_allocation);
73 fl->capacity = FRAMELOG_STARTING_CAPACITY;
78 size_t ZSTD_seekable_frameLog_freeVec(ZSTD_frameLog* fl)
80 if (fl != NULL) free(fl->entries);
84 ZSTD_frameLog* ZSTD_seekable_createFrameLog(int checksumFlag)
86 ZSTD_frameLog* fl = malloc(sizeof(ZSTD_frameLog));
87 if (fl == NULL) return NULL;
89 if (ZSTD_isError(ZSTD_seekable_frameLog_allocVec(fl))) {
94 fl->checksumFlag = checksumFlag;
96 fl->seekTableIndex = 0;
102 size_t ZSTD_seekable_freeFrameLog(ZSTD_frameLog* fl)
104 ZSTD_seekable_frameLog_freeVec(fl);
109 ZSTD_seekable_CStream* ZSTD_seekable_createCStream()
111 ZSTD_seekable_CStream* zcs = malloc(sizeof(ZSTD_seekable_CStream));
113 if (zcs == NULL) return NULL;
115 memset(zcs, 0, sizeof(*zcs));
117 zcs->cstream = ZSTD_createCStream();
118 if (zcs->cstream == NULL) goto failed1;
120 if (ZSTD_isError(ZSTD_seekable_frameLog_allocVec(&zcs->framelog))) goto failed2;
125 ZSTD_freeCStream(zcs->cstream);
131 size_t ZSTD_seekable_freeCStream(ZSTD_seekable_CStream* zcs)
133 if (zcs == NULL) return 0; /* support free on null */
134 ZSTD_freeCStream(zcs->cstream);
135 ZSTD_seekable_frameLog_freeVec(&zcs->framelog);
141 size_t ZSTD_seekable_initCStream(ZSTD_seekable_CStream* zcs,
142 int compressionLevel,
144 unsigned maxFrameSize)
146 zcs->framelog.size = 0;
150 /* make sure maxFrameSize has a reasonable value */
151 if (maxFrameSize > ZSTD_SEEKABLE_MAX_FRAME_DECOMPRESSED_SIZE) {
152 return ERROR(frameParameter_unsupported);
155 zcs->maxFrameSize = maxFrameSize
157 : ZSTD_SEEKABLE_MAX_FRAME_DECOMPRESSED_SIZE;
159 zcs->framelog.checksumFlag = checksumFlag;
160 if (zcs->framelog.checksumFlag) {
161 XXH64_reset(&zcs->xxhState, 0);
164 zcs->framelog.seekTablePos = 0;
165 zcs->framelog.seekTableIndex = 0;
166 zcs->writingSeekTable = 0;
168 return ZSTD_initCStream(zcs->cstream, compressionLevel);
171 size_t ZSTD_seekable_logFrame(ZSTD_frameLog* fl,
172 unsigned compressedSize,
173 unsigned decompressedSize,
176 if (fl->size == ZSTD_SEEKABLE_MAXFRAMES)
177 return ERROR(frameIndex_tooLarge);
179 /* grow the buffer if required */
180 if (fl->size == fl->capacity) {
181 /* exponential size increase for constant amortized runtime */
182 size_t const newCapacity = fl->capacity * 2;
183 framelogEntry_t* const newEntries = realloc(fl->entries,
184 sizeof(framelogEntry_t) * newCapacity);
186 if (newEntries == NULL) return ERROR(memory_allocation);
188 fl->entries = newEntries;
189 assert(newCapacity <= UINT_MAX);
190 fl->capacity = (U32)newCapacity;
193 fl->entries[fl->size] = (framelogEntry_t){
194 compressedSize, decompressedSize, checksum
201 size_t ZSTD_seekable_endFrame(ZSTD_seekable_CStream* zcs, ZSTD_outBuffer* output)
203 size_t const prevOutPos = output->pos;
205 size_t ret = ZSTD_endStream(zcs->cstream, output);
207 zcs->frameCSize += output->pos - prevOutPos;
209 /* need to flush before doing the rest */
214 /* store the frame data for later */
215 ret = ZSTD_seekable_logFrame(
216 &zcs->framelog, zcs->frameCSize, zcs->frameDSize,
217 zcs->framelog.checksumFlag
218 ? XXH64_digest(&zcs->xxhState) & 0xFFFFFFFFU
222 /* reset for the next frame */
226 ZSTD_resetCStream(zcs->cstream, 0);
227 if (zcs->framelog.checksumFlag)
228 XXH64_reset(&zcs->xxhState, 0);
233 size_t ZSTD_seekable_compressStream(ZSTD_seekable_CStream* zcs, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
235 const BYTE* const inBase = (const BYTE*) input->src + input->pos;
236 size_t inLen = input->size - input->pos;
238 inLen = MIN(inLen, (size_t)(zcs->maxFrameSize - zcs->frameDSize));
240 /* if we haven't finished flushing the last frame, don't start writing a new one */
242 ZSTD_inBuffer inTmp = { inBase, inLen, 0 };
243 size_t const prevOutPos = output->pos;
245 size_t const ret = ZSTD_compressStream(zcs->cstream, output, &inTmp);
247 if (zcs->framelog.checksumFlag) {
248 XXH64_update(&zcs->xxhState, inBase, inTmp.pos);
251 zcs->frameCSize += output->pos - prevOutPos;
252 zcs->frameDSize += inTmp.pos;
254 input->pos += inTmp.pos;
256 if (ZSTD_isError(ret)) return ret;
259 if (zcs->maxFrameSize == zcs->frameDSize) {
260 /* log the frame and start over */
261 size_t const ret = ZSTD_seekable_endFrame(zcs, output);
262 if (ZSTD_isError(ret)) return ret;
264 /* get the client ready for the next frame */
265 return (size_t)zcs->maxFrameSize;
268 return (size_t)(zcs->maxFrameSize - zcs->frameDSize);
271 static inline size_t ZSTD_seekable_seekTableSize(const ZSTD_frameLog* fl)
273 size_t const sizePerFrame = 8 + (fl->checksumFlag?4:0);
274 size_t const seekTableLen = ZSTD_SKIPPABLEHEADERSIZE +
275 sizePerFrame * fl->size +
276 ZSTD_seekTableFooterSize;
281 static inline size_t ZSTD_stwrite32(ZSTD_frameLog* fl,
282 ZSTD_outBuffer* output, U32 const value,
285 if (fl->seekTablePos < offset + 4) {
286 BYTE tmp[4]; /* so that we can work with buffers too small to write a whole word to */
287 size_t const lenWrite =
288 MIN(output->size - output->pos, offset + 4 - fl->seekTablePos);
289 MEM_writeLE32(tmp, value);
290 memcpy((BYTE*)output->dst + output->pos,
291 tmp + (fl->seekTablePos - offset), lenWrite);
292 output->pos += lenWrite;
293 fl->seekTablePos += lenWrite;
295 if (lenWrite < 4) return ZSTD_seekable_seekTableSize(fl) - fl->seekTablePos;
300 size_t ZSTD_seekable_writeSeekTable(ZSTD_frameLog* fl, ZSTD_outBuffer* output)
302 /* seekTableIndex: the current index in the table and
303 * seekTableSize: the amount of the table written so far
305 * This function is written this way so that if it has to return early
306 * because of a small buffer, it can keep going where it left off.
309 size_t const sizePerFrame = 8 + (fl->checksumFlag?4:0);
310 size_t const seekTableLen = ZSTD_seekable_seekTableSize(fl);
312 CHECK_Z(ZSTD_stwrite32(fl, output, ZSTD_MAGIC_SKIPPABLE_START | 0xE, 0));
313 assert(seekTableLen <= (size_t)UINT_MAX);
314 CHECK_Z(ZSTD_stwrite32(fl, output, (U32)seekTableLen - ZSTD_SKIPPABLEHEADERSIZE, 4));
316 while (fl->seekTableIndex < fl->size) {
317 unsigned long long const start = ZSTD_SKIPPABLEHEADERSIZE + sizePerFrame * fl->seekTableIndex;
318 assert(start + 8 <= UINT_MAX);
319 CHECK_Z(ZSTD_stwrite32(fl, output,
320 fl->entries[fl->seekTableIndex].cSize,
323 CHECK_Z(ZSTD_stwrite32(fl, output,
324 fl->entries[fl->seekTableIndex].dSize,
327 if (fl->checksumFlag) {
328 CHECK_Z(ZSTD_stwrite32(
329 fl, output, fl->entries[fl->seekTableIndex].checksum,
333 fl->seekTableIndex++;
336 assert(seekTableLen <= UINT_MAX);
337 CHECK_Z(ZSTD_stwrite32(fl, output, fl->size,
338 (U32)seekTableLen - ZSTD_seekTableFooterSize));
340 if (output->size - output->pos < 1) return seekTableLen - fl->seekTablePos;
341 if (fl->seekTablePos < seekTableLen - 4) {
343 sfd |= (fl->checksumFlag) << 7;
345 ((BYTE*)output->dst)[output->pos] = sfd;
350 CHECK_Z(ZSTD_stwrite32(fl, output, ZSTD_SEEKABLE_MAGICNUMBER,
351 (U32)seekTableLen - 4));
353 if (fl->seekTablePos != seekTableLen) return ERROR(GENERIC);
357 size_t ZSTD_seekable_endStream(ZSTD_seekable_CStream* zcs, ZSTD_outBuffer* output)
359 if (!zcs->writingSeekTable && zcs->frameDSize) {
360 const size_t endFrame = ZSTD_seekable_endFrame(zcs, output);
361 if (ZSTD_isError(endFrame)) return endFrame;
362 /* return an accurate size hint */
363 if (endFrame) return endFrame + ZSTD_seekable_seekTableSize(&zcs->framelog);
366 zcs->writingSeekTable = 1;
368 return ZSTD_seekable_writeSeekTable(&zcs->framelog, output);