diff options
-rwxr-xr-x | c/enc/backward_references_hq.c | 69 | ||||
-rwxr-xr-x | c/enc/backward_references_hq.h | 13 | ||||
-rw-r--r-- | c/enc/encode.c | 3 | ||||
-rwxr-xr-x | c/tools/brotli.c | 86 |
4 files changed, 90 insertions, 81 deletions
diff --git a/c/enc/backward_references_hq.c b/c/enc/backward_references_hq.c index 4545e80..1cea873 100755 --- a/c/enc/backward_references_hq.c +++ b/c/enc/backward_references_hq.c @@ -300,6 +300,7 @@ static size_t ComputeMinimumCopyLength(const float start_cost, static uint32_t ComputeDistanceShortcut(const size_t block_start, const size_t pos, const size_t max_backward, + const size_t gap, const ZopfliNode* nodes) { const size_t clen = ZopfliNodeCopyLength(&nodes[pos]); const size_t ilen = nodes[pos].insert_length; @@ -311,8 +312,8 @@ static uint32_t ComputeDistanceShortcut(const size_t block_start, does not update the last distances. */ if (pos == 0) { return 0; - } else if (dist + clen <= block_start + pos && - dist <= max_backward && + } else if (dist + clen <= block_start + pos + gap && + dist <= max_backward + gap && ZopfliNodeDistanceCode(&nodes[pos]) > 0) { return (uint32_t)pos; } else { @@ -350,12 +351,12 @@ static void ComputeDistanceCache(const size_t pos, is eligible. */ static void EvaluateNode( const size_t block_start, const size_t pos, const size_t max_backward_limit, - const int* starting_dist_cache, const ZopfliCostModel* model, - StartPosQueue* queue, ZopfliNode* nodes) { + const size_t gap, const int* starting_dist_cache, + const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) { /* Save cost, because ComputeDistanceCache invalidates it. */ float node_cost = nodes[pos].u.cost; nodes[pos].u.shortcut = ComputeDistanceShortcut( - block_start, pos, max_backward_limit, nodes); + block_start, pos, max_backward_limit, gap, nodes); if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) { PosData posdata; posdata.pos = pos; @@ -385,9 +386,10 @@ static size_t UpdateNodes( size_t min_len; size_t result = 0; size_t k; + size_t gap = 0; - EvaluateNode(block_start, pos, max_backward_limit, starting_dist_cache, model, - queue, nodes); + EvaluateNode(block_start, pos, max_backward_limit, gap, starting_dist_cache, + model, queue, nodes); { const PosData* posdata = StartPosQueueAt(queue, 0); @@ -415,25 +417,31 @@ static size_t UpdateNodes( const size_t backward = (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]); size_t prev_ix = cur_ix - backward; - if (prev_ix >= cur_ix) { - continue; + size_t len = 0; + uint8_t continuation = ringbuffer[cur_ix_masked + best_len]; + if (cur_ix_masked + best_len > ringbuffer_mask) { + break; } - if (BROTLI_PREDICT_FALSE(backward > max_distance)) { + if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) { continue; } - prev_ix &= ringbuffer_mask; + if (backward <= max_distance) { + if (prev_ix >= cur_ix) { + continue; + } - if (cur_ix_masked + best_len > ringbuffer_mask || - prev_ix + best_len > ringbuffer_mask || - ringbuffer[cur_ix_masked + best_len] != - ringbuffer[prev_ix + best_len]) { + prev_ix &= ringbuffer_mask; + if (prev_ix + best_len > ringbuffer_mask || + continuation != ringbuffer[prev_ix + best_len]) { + continue; + } + len = FindMatchLengthWithLimit(&ringbuffer[prev_ix], + &ringbuffer[cur_ix_masked], + max_len); + } else { continue; } { - const size_t len = - FindMatchLengthWithLimit(&ringbuffer[prev_ix], - &ringbuffer[cur_ix_masked], - max_len); const float dist_cost = base_cost + ZopfliCostModelGetDistanceCost(model, j); size_t l; @@ -464,7 +472,8 @@ static size_t UpdateNodes( for (j = 0; j < num_matches; ++j) { BackwardMatch match = matches[j]; size_t dist = match.distance; - BROTLI_BOOL is_dictionary_match = TO_BROTLI_BOOL(dist > max_distance); + BROTLI_BOOL is_dictionary_match = + TO_BROTLI_BOOL(dist > max_distance + gap); /* We already tried all possible last distance matches, so we can use normal distance code here. */ size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1; @@ -526,11 +535,14 @@ void BrotliZopfliCreateCommands(const size_t num_bytes, const ZopfliNode* nodes, int* dist_cache, size_t* last_insert_len, + const BrotliEncoderParams* params, Command* commands, size_t* num_literals) { size_t pos = 0; uint32_t offset = nodes[0].u.next; size_t i; + size_t gap = 0; + BROTLI_UNUSED(params); for (i = 0; offset != BROTLI_UINT32_MAX; i++) { const ZopfliNode* next = &nodes[pos + offset]; size_t copy_length = ZopfliNodeCopyLength(next); @@ -546,7 +558,7 @@ void BrotliZopfliCreateCommands(const size_t num_bytes, size_t len_code = ZopfliNodeLengthCode(next); size_t max_distance = BROTLI_MIN(size_t, block_start + pos, max_backward_limit); - BROTLI_BOOL is_dictionary = TO_BROTLI_BOOL(distance > max_distance); + BROTLI_BOOL is_dictionary = TO_BROTLI_BOOL(distance > max_distance + gap); size_t dist_code = ZopfliNodeDistanceCode(next); InitCommand(&commands[i], insert_length, @@ -572,6 +584,7 @@ static size_t ZopfliIterate(size_t num_bytes, size_t ringbuffer_mask, const BrotliEncoderParams* params, const size_t max_backward_limit, + const size_t gap, const int* dist_cache, const ZopfliCostModel* model, const uint32_t* num_matches, @@ -600,8 +613,8 @@ static size_t ZopfliIterate(size_t num_bytes, while (skip) { i++; if (i + 3 >= num_bytes) break; - EvaluateNode( - position, i, max_backward_limit, dist_cache, model, &queue, nodes); + EvaluateNode(position, i, max_backward_limit, gap, dist_cache, model, + &queue, nodes); cur_match_pos += num_matches[i]; skip--; } @@ -664,8 +677,8 @@ size_t BrotliZopfliComputeShortestPath(MemoryManager* m, while (skip) { i++; if (i + HashTypeLengthH10() - 1 >= num_bytes) break; - EvaluateNode( - position, i, max_backward_limit, dist_cache, &model, &queue, nodes); + EvaluateNode(position, i, max_backward_limit, gap, dist_cache, &model, + &queue, nodes); skip--; } } @@ -690,7 +703,7 @@ void BrotliCreateZopfliBackwardReferences( dist_cache, hasher, nodes); if (BROTLI_IS_OOM(m)) return; BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, nodes, - dist_cache, last_insert_len, commands, num_literals); + dist_cache, last_insert_len, params, commands, num_literals); BROTLI_FREE(m, nodes); } @@ -777,10 +790,10 @@ void BrotliCreateHqZopfliBackwardReferences( *last_insert_len = orig_last_insert_len; memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0])); *num_commands += ZopfliIterate(num_bytes, position, ringbuffer, - ringbuffer_mask, params, max_backward_limit, dist_cache, + ringbuffer_mask, params, max_backward_limit, gap, dist_cache, &model, num_matches, matches, nodes); BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, - nodes, dist_cache, last_insert_len, commands, num_literals); + nodes, dist_cache, last_insert_len, params, commands, num_literals); } CleanupZopfliCostModel(m, &model); BROTLI_FREE(m, nodes); diff --git a/c/enc/backward_references_hq.h b/c/enc/backward_references_hq.h index 0a768cd..7e3bd7e 100755 --- a/c/enc/backward_references_hq.h +++ b/c/enc/backward_references_hq.h @@ -83,14 +83,11 @@ BROTLI_INTERNAL size_t BrotliZopfliComputeShortestPath( const BrotliEncoderParams* params, const size_t max_backward_limit, const int* dist_cache, HasherHandle hasher, ZopfliNode* nodes); -BROTLI_INTERNAL void BrotliZopfliCreateCommands(const size_t num_bytes, - const size_t block_start, - const size_t max_backward_limit, - const ZopfliNode* nodes, - int* dist_cache, - size_t* last_insert_len, - Command* commands, - size_t* num_literals); +BROTLI_INTERNAL void BrotliZopfliCreateCommands( + const size_t num_bytes, const size_t block_start, + const size_t max_backward_limit, const ZopfliNode* nodes, + int* dist_cache, size_t* last_insert_len, const BrotliEncoderParams* params, + Command* commands, size_t* num_literals); #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ diff --git a/c/enc/encode.c b/c/enc/encode.c index 7d58aa2..e4cbf1d 100644 --- a/c/enc/encode.c +++ b/c/enc/encode.c @@ -1178,7 +1178,8 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( } BrotliZopfliCreateCommands(block_size, block_start, max_backward_limit, &nodes[0], dist_cache, &last_insert_len, - &commands[num_commands], &num_literals); + ¶ms, &commands[num_commands], + &num_literals); num_commands += path_size; block_start += block_size; metablock_size += block_size; diff --git a/c/tools/brotli.c b/c/tools/brotli.c index 557ec93..616ab50 100755 --- a/c/tools/brotli.c +++ b/c/tools/brotli.c @@ -22,6 +22,7 @@ #if !defined(_WIN32) #include <unistd.h> #include <utime.h> +#define MAKE_BINARY(FILENO) (FILENO) #else #include <io.h> #include <share.h> @@ -30,8 +31,8 @@ #define MAKE_BINARY(FILENO) (_setmode((FILENO), _O_BINARY), (FILENO)) #if !defined(__MINGW32__) -#define STDIN_FILENO MAKE_BINARY(_fileno(stdin)) -#define STDOUT_FILENO MAKE_BINARY(_fileno(stdout)) +#define STDIN_FILENO _fileno(stdin) +#define STDOUT_FILENO _fileno(stdout) #define S_IRUSR S_IREAD #define S_IWUSR S_IWRITE #endif @@ -384,50 +385,47 @@ static void PrintVersion(void) { int major = BROTLI_VERSION >> 24; int minor = (BROTLI_VERSION >> 12) & 0xFFF; int patch = BROTLI_VERSION & 0xFFF; - fprintf(stdout, "\ -brotli %d.%d.%d\n", - major, minor, patch); + fprintf(stdout, "brotli %d.%d.%d\n", major, minor, patch); } static void PrintHelp(const char* name) { /* String is cut to pieces with length less than 509, to conform C90 spec. */ - fprintf(stdout, "\ -Usage: %s [OPTION]... [FILE]...\n", + fprintf(stdout, +"Usage: %s [OPTION]... [FILE]...\n", name); - fprintf(stdout, "\ -Options:\n\ - -# compression level (0-9)\n\ - -c, --stdout write on standard output\n\ - -d, --decompress decompress\n\ - -f, --force force output file overwrite\n\ - -h, --help display this help and exit\n"); - fprintf(stdout, "\ - -j, --rm remove source file(s)\n\ - -k, --keep keep source file(s) (default)\n\ - -n, --no-copy-stat do not copy source file(s) attributes\n\ - -o FILE, --output=FILE output file (only if 1 input file)\n"); - fprintf(stdout, "\ - -q NUM, --quality=NUM compression level (%d-%d)\n", + fprintf(stdout, +"Options:\n" +" -# compression level (0-9)\n" +" -c, --stdout write on standard output\n" +" -d, --decompress decompress\n" +" -f, --force force output file overwrite\n" +" -h, --help display this help and exit\n"); + fprintf(stdout, +" -j, --rm remove source file(s)\n" +" -k, --keep keep source file(s) (default)\n" +" -n, --no-copy-stat do not copy source file(s) attributes\n" +" -o FILE, --output=FILE output file (only if 1 input file)\n"); + fprintf(stdout, +" -q NUM, --quality=NUM compression level (%d-%d)\n", BROTLI_MIN_QUALITY, BROTLI_MAX_QUALITY); - fprintf(stdout, "\ - -t, --test test compressed file integrity\n\ - -v, --verbose verbose mode\n"); - fprintf(stdout, "\ - -w NUM, --lgwin=NUM set LZ77 window size (0, %d-%d) (default:%d)\n", + fprintf(stdout, +" -t, --test test compressed file integrity\n" +" -v, --verbose verbose mode\n"); + fprintf(stdout, +" -w NUM, --lgwin=NUM set LZ77 window size (0, %d-%d) (default:%d)\n", BROTLI_MIN_WINDOW_BITS, BROTLI_MAX_WINDOW_BITS, DEFAULT_LGWIN); - fprintf(stdout, "\ - window size = 2**NUM - 16\n\ - 0 lets compressor decide over the optimal value\n\ -"); - fprintf(stdout, "\ - -S SUF, --suffix=SUF output file suffix (default:'%s')\n", + fprintf(stdout, +" window size = 2**NUM - 16\n" +" 0 lets compressor choose the optimal value\n"); + fprintf(stdout, +" -S SUF, --suffix=SUF output file suffix (default:'%s')\n", DEFAULT_SUFFIX); - fprintf(stdout, "\ - -V, --version display version and exit\n\ - -Z, --best use best compression level (11) (default)\n\ -Simple options could be coalesced, i.e. '-9kf' is equivalent to '-9 -k -f'.\n\ -With no FILE, or when FILE is -, read standard input.\n\ -All arguments after '--' are treated as files.\n"); + fprintf(stdout, +" -V, --version display version and exit\n" +" -Z, --best use best compression level (11) (default)\n" +"Simple options could be coalesced, i.e. '-9kf' is equivalent to '-9 -k -f'.\n" +"With no FILE, or when FILE is -, read standard input.\n" +"All arguments after '--' are treated as files.\n"); } static const char* PrintablePath(const char* path) { @@ -437,7 +435,7 @@ static const char* PrintablePath(const char* path) { static BROTLI_BOOL OpenInputFile(const char* input_path, FILE** f) { *f = NULL; if (!input_path) { - *f = fdopen(STDIN_FILENO, "rb"); + *f = fdopen(MAKE_BINARY(STDIN_FILENO), "rb"); return BROTLI_TRUE; } *f = fopen(input_path, "rb"); @@ -454,7 +452,7 @@ static BROTLI_BOOL OpenOutputFile(const char* output_path, FILE** f, int fd; *f = NULL; if (!output_path) { - *f = fdopen(STDOUT_FILENO, "wb"); + *f = fdopen(MAKE_BINARY(STDOUT_FILENO), "wb"); return BROTLI_TRUE; } fd = open(output_path, O_CREAT | (force ? 0 : O_EXCL) | O_WRONLY | O_TRUNC, @@ -474,7 +472,7 @@ static BROTLI_BOOL OpenOutputFile(const char* output_path, FILE** f, } /* Copy file times and permissions. - TODO(eustas): this is a "best effort" implementation; honest cross-platform + TODO: this is a "best effort" implementation; honest cross-platform fully featured implementation is way too hacky; add more hacks by request. */ static void CopyStat(const char* input_path, const char* output_path) { struct stat statbuf; @@ -648,7 +646,7 @@ static BROTLI_BOOL DecompressFile(Context* context, BrotliDecoderState* s) { if (result == BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT) { if (feof(context->fin)) { fprintf(stderr, "corrupt input [%s]\n", - PrintablePath(context->current_output_path)); + PrintablePath(context->current_input_path)); return BROTLI_FALSE; } available_in = fread(context->input, 1, kFileBufferSize, context->fin); @@ -663,13 +661,13 @@ static BROTLI_BOOL DecompressFile(Context* context, BrotliDecoderState* s) { } else if (result == BROTLI_DECODER_RESULT_SUCCESS) { if (available_in != 0 || !feof(context->fin)) { fprintf(stderr, "corrupt input [%s]\n", - PrintablePath(context->current_output_path)); + PrintablePath(context->current_input_path)); return BROTLI_FALSE; } return BROTLI_TRUE; } else { fprintf(stderr, "corrupt input [%s]\n", - PrintablePath(context->current_output_path)); + PrintablePath(context->current_input_path)); return BROTLI_FALSE; } |