/* deflate.c -- compress data using the deflation algorithm
* Copyright (C) 1995-2005 Jean-loup Gailly.
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* ALGORITHM
*
* The "deflation" process depends on being able to identify portions
* of the input text which are identical to earlier input (within a
* sliding window trailing behind the input currently being processed).
*
* The most straightforward technique turns out to be the fastest for
* most input files: try all possible matches and select the longest.
* The key feature of this algorithm is that insertions into the string
* dictionary are very simple and thus fast, and deletions are avoided
* completely. Insertions are performed at each input character, whereas
* string matches are performed only when the previous match ends. So it
* is preferable to spend more time in matches to allow very fast string
* insertions and avoid deletions. The matching algorithm for small
* strings is inspired from that of Rabin & Karp. A brute force approach
* is used to find longer strings when a small match has been found.
* A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
* (by Leonid Broukhis).
* A previous version of this file used a more sophisticated algorithm
* (by Fiala and Greene) which is guaranteed to run in linear amortized
* time, but has a larger average cost, uses more memory and is patented.
* However the F&G algorithm may be faster for some highly redundant
* files if the parameter max_chain_length (described below) is too large.
*
* ACKNOWLEDGEMENTS
*
* The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
* I found it in 'freeze' written by Leonid Broukhis.
* Thanks to many people for bug reports and testing.
*
* REFERENCES
*
* Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
* Available in http://www.ietf.org/rfc/rfc1951.txt
*
* A description of the Rabin and Karp algorithm is given in the book
* "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
*
* Fiala,E.R., and Greene,D.H.
* Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
*
*/
/* @(#) $Id: deflate.c,v 3.6 2005/08/04 19:14:14 tor%cs.brown.edu Exp $ */
#include "deflate.h"
const char deflate_copyright[] =
" deflate 1.2.3 Copyright 1995-2005 Jean-loup Gailly ";
/*
If you use the zlib library in a product, an acknowledgment is welcome
in the documentation of your product. If for some reason you cannot
include such an acknowledgment, I would appreciate that you keep this
copyright string in the executable of your product.
*/
/* ===========================================================================
* Function prototypes.
*/
typedef enum {
need_more, /* block not completed, need more input or more output */
block_done, /* block flush performed */
finish_started, /* finish started, need only more output at next deflate */
finish_done /* finish done, accept no more input or output */
} block_state;
typedef block_state (*compress_func) OF((deflate_state *s, int flush));
/* Compression function. Returns the block state after the call. */
local void fill_window OF((deflate_state *s));
local block_state deflate_stored OF((deflate_state *s, int flush));
local block_state deflate_fast OF((deflate_state *s, int flush));
#ifndef FASTEST
local block_state deflate_slow OF((deflate_state *s, int flush));
#endif
local void lm_init OF((deflate_state *s));
local void putShortMSB OF((deflate_state *s, uInt b));
local void flush_pending OF((z_streamp strm));
local int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
#ifndef FASTEST
#ifdef ASMV
void match_init OF((void)); /* asm code initialization */
uInt longest_match OF((deflate_state *s, IPos cur_match));
#else
local uInt longest_match OF((deflate_state *s, IPos cur_match));
#endif
#endif
local uInt longest_match_fast OF((deflate_state *s, IPos cur_match));
#ifdef DEBUG
local void check_match OF((deflate_state *s, IPos start, IPos match,
int length));
#endif
/* ===========================================================================
* Local data
*/
#define NIL 0
/* Tail of hash chains */
#ifndef TOO_FAR
# define TOO_FAR 4096
#endif
/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
/* Minimum amount of lookahead, except at the end of the input file.
* See deflate.c for comments about the MIN_MATCH+1.
*/
/* Values for max_lazy_match, good_match and max_chain_length, depending on
* the desired pack level (0..9). The values given below have been tuned to
* exclude worst case performance for pathological files. Better values may be
* found for specific files.
*/
typedef struct config_s {
ush good_length; /* reduce lazy search above this match length */
ush max_lazy; /* do not perform lazy search above this match length */
ush nice_length; /* quit search above this match length */
ush max_chain;
compress_func func;
} config;
#ifdef FASTEST
local const config configuration_table[2] = {
/* good lazy nice chain */
/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
/* 1 */ {4, 4, 8, 4, deflate_fast}}; /* max speed, no lazy matches */
#else
local const config configuration_table[10] = {
/* good lazy nice chain */
/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */
/* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */
/* 2 */ {4, 5, 16, 8, deflate_fast},
/* 3 */ {4, 6, 32, 32, deflate_fast},
/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */
/* 5 */ {8, 16, 32, 32, deflate_slow},
/* 6 */ {8, 16, 128, 128, deflate_slow},
/* 7 */ {8, 32, 128, 256, deflate_slow},
/* 8 */ {32, 128, 258, 1024, deflate_slow},
/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
#endif
/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
* For deflate_fast() (levels <= 3) good is ignored and lazy has a different
* meaning.
*/
#define EQUAL 0
/* result of memcmp for equal strings */
#ifndef NO_DUMMY_DECL
struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
#endif
/* ===========================================================================
* Update a hash value with the given input byte
* IN assertion: all calls to to UPDATE_HASH are made with consecutive
* input characters, so that a running hash key can be computed from the
* previous key instead of complete recalculation each time.
*/
#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
/* ===========================================================================
* Insert string str in the dictionary and set match_head to the previous head
* of the hash chain (the most recent string with same hash key). Return
* the previous length of the hash chain.
* If this file is compiled with -DFASTEST, the compression level is forced
* to 1, and no hash chains are maintained.
* IN assertion: all calls to to INSERT_STRING are made with consecutive
* input characters and the first MIN_MATCH bytes of str are valid
* (except for the last MIN_MATCH-1 bytes of the input file).
*/
#ifdef FASTEST
#define INSERT_STRING(s, str, match_head) \
(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
match_head = s->head[s->ins_h], \
s->head[s->ins_h] = (Pos)(str))
#else
#define INSERT_STRING(s, str, match_head) \
(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
s->head[s->ins_h] = (Pos)(str))
#endif
/* ===========================================================================
chrome界面框架 代码
4星 · 超过85%的资源 需积分: 10 85 浏览量
2014-07-01
14:34:00
上传
评论
收藏 780KB RAR 举报 
chrome界面框架 代码 （431个子文件） 
test_view.aps 43KB deflate.c 63KB inflate.c 48KB trees.c 43KB gzio.c 31KB infback.c 22KB inftrees.c 13KB crc32.c 13KB inffast.c 12KB zutil.c 7KB adler32.c 5KB compress.c 2KB uncompr.c 2KB prtime.cc 48KB sha512.cc 35KB icu_utf.cc 8KB icu_utf.cc 7KB modp_b64.cc 7KB window_win.cpp 67KB view.cpp 54KB widget_win.cpp 51KB grid_layout.cpp 40KB string_util.cpp 35KB native_theme_win.cpp 33KB values.cpp 30KB root_view.cpp 27KB custom_frame_view.cpp 26KB canvas_gdiplus.cpp 25KB view_accessibility.cpp 24KB json_reader.cpp 23KB os_exchange_data_provider_win.cpp 22KB dialog_client_view.cpp 21KB focus_manager.cpp 21KB logging.cpp 20KB clipboard_util_win.cpp 20KB message_pump_win.cpp 19KB tooltip_manager_win.cpp 16KB text_button.cpp 16KB time.cpp 16KB resource_bundle.cpp 15KB message_loop.cpp 15KB file_util.cpp 14KB main.cpp 13KB string_number_conversions.cpp 12KB registry.cpp 12KB windows_util.cpp 11KB color_utils.cpp 11KB command_line.cpp 10KB debug_util.cpp 10KB pickle.cpp 10KB non_client_view.cpp 10KB focus_search.cpp 10KB platform_font_win.cpp 9KB md5.cpp 9KB custom_button.cpp 9KB bounds_animator.cpp 8KB native_control_win.cpp 8KB native_button.cpp 8KB platform_file.cpp 8KB scoped_variant.cpp 7KB main.cpp 7KB string_piece.cpp 7KB json_writer.cpp 7KB thread.cpp 7KB window_impl.cpp 7KB single_split_view.cpp 7KB native_view_host.cpp 7KB bitmap_operations.cpp 7KB painter.cpp 7KB thread_local_storage.cpp 6KB file_path.cpp 6KB rect.cpp 6KB data_pack.cpp 6KB image_button.cpp 6KB native_button_win.cpp 6KB native_view_host_win.cpp 5KB path_service.cpp 5KB string_split.cpp 5KB focus_util_win.cpp 5KB file_version_info.cpp 5KB drop_target.cpp 5KB aero_tooltip_manager.cpp 5KB win_util.cpp 5KB stringprintf.cpp 4KB drop_helper.cpp 4KB utf_string_conversion_utils.cpp 4KB system_monitor.cpp 4KB utf_string_conversions.cpp 3KB view_storage.cpp 3KB version.cpp 3KB event.cpp 3KB string_escape.cpp 3KB message_loop_proxy_impl.cpp 3KB waitable_event.cpp 3KB animation_container.cpp 3KB background.cpp 3KB animation.cpp 3KB box_layout.cpp 3KB environment.cpp 3KB os_exchange_data.cpp 3KB共 431 条
- 1
- 2
- 3
- 4
- 5
资源评论
yunhai9982015-06-15还可以,就是感觉有点乱
