Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(12)

Side by Side Diff: third_party/zlib/deflate.c

Issue 2669053004: Remove mixed-source.patch from zlib. (Closed)
Patch Set: delete mixed-source.patch Created 3 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/zlib/deflate.h ('k') | third_party/zlib/mixed-source.patch » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* deflate.c -- compress data using the deflation algorithm 1 /* deflate.c -- compress data using the deflation algorithm
2 * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler 2 * Copyright (C) 1995-2013 Jean-loup Gailly and Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 */ 4 */
5 5
6 /* 6 /*
7 * ALGORITHM 7 * ALGORITHM
8 * 8 *
9 * The "deflation" process depends on being able to identify portions 9 * The "deflation" process depends on being able to identify portions
10 * of the input text which are identical to earlier input (within a 10 * of the input text which are identical to earlier input (within a
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after
64 /* =========================================================================== 64 /* ===========================================================================
65 * Function prototypes. 65 * Function prototypes.
66 */ 66 */
67 typedef enum { 67 typedef enum {
68 need_more, /* block not completed, need more input or more output */ 68 need_more, /* block not completed, need more input or more output */
69 block_done, /* block flush performed */ 69 block_done, /* block flush performed */
70 finish_started, /* finish started, need only more output at next deflate */ 70 finish_started, /* finish started, need only more output at next deflate */
71 finish_done /* finish done, accept no more input or output */ 71 finish_done /* finish done, accept no more input or output */
72 } block_state; 72 } block_state;
73 73
74 typedef block_state (*compress_func) OF((deflate_state *s, int flush, 74 typedef block_state (*compress_func) OF((deflate_state *s, int flush));
75 int clas));
76 /* Compression function. Returns the block state after the call. */ 75 /* Compression function. Returns the block state after the call. */
77 76
78 local void fill_window OF((deflate_state *s)); 77 local void fill_window OF((deflate_state *s));
79 local block_state deflate_stored OF((deflate_state *s, int flush, int clas)); 78 local block_state deflate_stored OF((deflate_state *s, int flush));
80 local block_state deflate_fast OF((deflate_state *s, int flush, int clas)); 79 local block_state deflate_fast OF((deflate_state *s, int flush));
81 #ifndef FASTEST 80 #ifndef FASTEST
82 local block_state deflate_slow OF((deflate_state *s, int flush, int clas)); 81 local block_state deflate_slow OF((deflate_state *s, int flush));
83 #endif 82 #endif
84 local block_state deflate_rle OF((deflate_state *s, int flush)); 83 local block_state deflate_rle OF((deflate_state *s, int flush));
85 local block_state deflate_huff OF((deflate_state *s, int flush)); 84 local block_state deflate_huff OF((deflate_state *s, int flush));
86 local void lm_init OF((deflate_state *s)); 85 local void lm_init OF((deflate_state *s));
87 local void putShortMSB OF((deflate_state *s, uInt b)); 86 local void putShortMSB OF((deflate_state *s, uInt b));
88 local void flush_pending OF((z_streamp strm)); 87 local void flush_pending OF((z_streamp strm));
89 88
90 #ifdef ASMV 89 #ifdef ASMV
91 void match_init OF((void)); /* asm code initialization */ 90 void match_init OF((void)); /* asm code initialization */
92 uInt longest_match OF((deflate_state *s, IPos cur_match, int clas)); 91 uInt longest_match OF((deflate_state *s, IPos cur_match));
93 #else 92 #else
94 local uInt longest_match OF((deflate_state *s, IPos cur_match, int clas)); 93 local uInt longest_match OF((deflate_state *s, IPos cur_match));
95 #endif 94 #endif
96 95
97 #ifdef DEBUG 96 #ifdef DEBUG
98 local void check_match OF((deflate_state *s, IPos start, IPos match, 97 local void check_match OF((deflate_state *s, IPos start, IPos match,
99 int length)); 98 int length));
100 #endif 99 #endif
101 100
102 /* For fill_window_sse.c to use */ 101 /* For fill_window_sse.c to use */
103 ZLIB_INTERNAL int read_buf OF((z_streamp strm, Bytef *buf, unsigned size)); 102 ZLIB_INTERNAL int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
104 103
(...skipping 218 matching lines...) Expand 10 before | Expand all | Expand 10 after
323 s->hash_bits = memLevel + 7; 322 s->hash_bits = memLevel + 7;
324 } 323 }
325 324
326 s->hash_size = 1 << s->hash_bits; 325 s->hash_size = 1 << s->hash_bits;
327 s->hash_mask = s->hash_size - 1; 326 s->hash_mask = s->hash_size - 1;
328 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 327 s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
329 328
330 s->window = (Bytef *) ZALLOC(strm, s->w_size + window_padding, 2*sizeof(Byte )); 329 s->window = (Bytef *) ZALLOC(strm, s->w_size + window_padding, 2*sizeof(Byte ));
331 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 330 s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
332 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 331 s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
333 s->class_bitmap = NULL;
334 zmemzero(&s->cookie_locations, sizeof(s->cookie_locations));
335 strm->clas = 0;
336 332
337 s->high_water = 0; /* nothing written to s->window yet */ 333 s->high_water = 0; /* nothing written to s->window yet */
338 334
339 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 335 s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
340 336
341 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 337 overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
342 s->pending_buf = (uchf *) overlay; 338 s->pending_buf = (uchf *) overlay;
343 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 339 s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
344 340
345 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 341 if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after
435 return Z_STREAM_ERROR; 431 return Z_STREAM_ERROR;
436 } 432 }
437 433
438 strm->total_in = strm->total_out = 0; 434 strm->total_in = strm->total_out = 0;
439 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 435 strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
440 strm->data_type = Z_UNKNOWN; 436 strm->data_type = Z_UNKNOWN;
441 437
442 s = (deflate_state *)strm->state; 438 s = (deflate_state *)strm->state;
443 s->pending = 0; 439 s->pending = 0;
444 s->pending_out = s->pending_buf; 440 s->pending_out = s->pending_buf;
445 TRY_FREE(strm, s->class_bitmap);
446 s->class_bitmap = NULL;
447 441
448 if (s->wrap < 0) { 442 if (s->wrap < 0) {
449 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */ 443 s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
450 } 444 }
451 s->status = s->wrap ? INIT_STATE : BUSY_STATE; 445 s->status = s->wrap ? INIT_STATE : BUSY_STATE;
452 strm->adler = 446 strm->adler =
453 #ifdef GZIP 447 #ifdef GZIP
454 s->wrap == 2 ? crc32(0L, Z_NULL, 0) : 448 s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
455 #endif 449 #endif
456 adler32(0L, Z_NULL, 0); 450 adler32(0L, Z_NULL, 0);
(...skipping 474 matching lines...) Expand 10 before | Expand all | Expand 10 after
931 if (s->status == FINISH_STATE && strm->avail_in != 0) { 925 if (s->status == FINISH_STATE && strm->avail_in != 0) {
932 ERR_RETURN(strm, Z_BUF_ERROR); 926 ERR_RETURN(strm, Z_BUF_ERROR);
933 } 927 }
934 928
935 /* Start a new block or continue the current one. 929 /* Start a new block or continue the current one.
936 */ 930 */
937 if (strm->avail_in != 0 || s->lookahead != 0 || 931 if (strm->avail_in != 0 || s->lookahead != 0 ||
938 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 932 (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
939 block_state bstate; 933 block_state bstate;
940 934
941 if (strm->clas && s->class_bitmap == NULL) { 935 bstate = s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
942 /* This is the first time that we have seen alternative class 936 (s->strategy == Z_RLE ? deflate_rle(s, flush) :
943 * data. All data up till this point has been standard class. */ 937 (*(configuration_table[s->level].func))(s, flush));
944 s->class_bitmap = (Bytef*) ZALLOC(strm, s->w_size/4, sizeof(Byte));
945 zmemzero(s->class_bitmap, s->w_size/4);
946 }
947
948 if (strm->clas && s->strategy == Z_RLE) {
949 /* We haven't patched deflate_rle. */
950 ERR_RETURN(strm, Z_BUF_ERROR);
951 }
952
953 if (s->strategy == Z_HUFFMAN_ONLY) {
954 bstate = deflate_huff(s, flush);
955 } else if (s->strategy == Z_RLE) {
956 bstate = deflate_rle(s, flush);
957 } else {
958 bstate = (*(configuration_table[s->level].func))
959 (s, flush, strm->clas);
960 }
961 938
962 if (bstate == finish_started || bstate == finish_done) { 939 if (bstate == finish_started || bstate == finish_done) {
963 s->status = FINISH_STATE; 940 s->status = FINISH_STATE;
964 } 941 }
965 if (bstate == need_more || bstate == finish_started) { 942 if (bstate == need_more || bstate == finish_started) {
966 if (strm->avail_out == 0) { 943 if (strm->avail_out == 0) {
967 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 944 s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
968 } 945 }
969 return Z_OK; 946 return Z_OK;
970 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 947 /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after
1048 status != BUSY_STATE && 1025 status != BUSY_STATE &&
1049 status != FINISH_STATE) { 1026 status != FINISH_STATE) {
1050 return Z_STREAM_ERROR; 1027 return Z_STREAM_ERROR;
1051 } 1028 }
1052 1029
1053 /* Deallocate in reverse order of allocations: */ 1030 /* Deallocate in reverse order of allocations: */
1054 TRY_FREE(strm, strm->state->pending_buf); 1031 TRY_FREE(strm, strm->state->pending_buf);
1055 TRY_FREE(strm, strm->state->head); 1032 TRY_FREE(strm, strm->state->head);
1056 TRY_FREE(strm, strm->state->prev); 1033 TRY_FREE(strm, strm->state->prev);
1057 TRY_FREE(strm, strm->state->window); 1034 TRY_FREE(strm, strm->state->window);
1058 TRY_FREE(strm, strm->state->class_bitmap);
1059 1035
1060 ZFREE(strm, strm->state); 1036 ZFREE(strm, strm->state);
1061 strm->state = Z_NULL; 1037 strm->state = Z_NULL;
1062 1038
1063 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 1039 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
1064 } 1040 }
1065 1041
1066 /* ========================================================================= 1042 /* =========================================================================
1067 * Copy the source state to the destination state. 1043 * Copy the source state to the destination state.
1068 * To simplify the source, this is not supported for 16-bit MSDOS (which 1044 * To simplify the source, this is not supported for 16-bit MSDOS (which
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after
1182 s->match_length = s->prev_length = MIN_MATCH-1; 1158 s->match_length = s->prev_length = MIN_MATCH-1;
1183 s->match_available = 0; 1159 s->match_available = 0;
1184 s->ins_h = 0; 1160 s->ins_h = 0;
1185 #ifndef FASTEST 1161 #ifndef FASTEST
1186 #ifdef ASMV 1162 #ifdef ASMV
1187 match_init(); /* initialize the asm code */ 1163 match_init(); /* initialize the asm code */
1188 #endif 1164 #endif
1189 #endif 1165 #endif
1190 } 1166 }
1191 1167
1192 /* class_set sets bits [offset,offset+len) in s->class_bitmap to either 1 (if
1193 * class != 0) or 0 (otherwise). */
1194 local void class_set(s, offset, len, clas)
1195 deflate_state *s;
1196 IPos offset;
1197 uInt len;
1198 int clas;
1199 {
1200 IPos byte = offset >> 3;
1201 IPos bit = offset & 7;
1202 Bytef class_byte_value = clas ? 0xff : 0x00;
1203 Bytef class_bit_value = clas ? 1 : 0;
1204 static const Bytef mask[8] = {0xfe, 0xfd, 0xfb, 0xf7,
1205 0xef, 0xdf, 0xbf, 0x7f};
1206
1207 if (bit) {
1208 while (len) {
1209 s->class_bitmap[byte] &= mask[bit];
1210 s->class_bitmap[byte] |= class_bit_value << bit;
1211 bit++;
1212 len--;
1213 if (bit == 8) {
1214 bit = 0;
1215 byte++;
1216 break;
1217 }
1218 }
1219 }
1220
1221 while (len >= 8) {
1222 s->class_bitmap[byte++] = class_byte_value;
1223 len -= 8;
1224 }
1225
1226 while (len) {
1227 s->class_bitmap[byte] &= mask[bit];
1228 s->class_bitmap[byte] |= class_bit_value << bit;
1229 bit++;
1230 len--;
1231 }
1232 }
1233
1234 local int class_at(s, window_offset)
1235 deflate_state *s;
1236 IPos window_offset;
1237 {
1238 IPos byte = window_offset >> 3;
1239 IPos bit = window_offset & 7;
1240 return (s->class_bitmap[byte] >> bit) & 1;
1241 }
1242
1243 #ifndef FASTEST 1168 #ifndef FASTEST
1244 /* =========================================================================== 1169 /* ===========================================================================
1245 * Set match_start to the longest match starting at the given string and 1170 * Set match_start to the longest match starting at the given string and
1246 * return its length. Matches shorter or equal to prev_length are discarded, 1171 * return its length. Matches shorter or equal to prev_length are discarded,
1247 * in which case the result is equal to prev_length and match_start is 1172 * in which case the result is equal to prev_length and match_start is
1248 * garbage. 1173 * garbage.
1249 * IN assertions: cur_match is the head of the hash chain for the current 1174 * IN assertions: cur_match is the head of the hash chain for the current
1250 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 1175 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1251 * OUT assertion: the match length is not greater than s->lookahead. 1176 * OUT assertion: the match length is not greater than s->lookahead.
1252 */ 1177 */
1253 #ifndef ASMV 1178 #ifndef ASMV
1254 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or 1179 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1255 * match.S. The code will be functionally equivalent. 1180 * match.S. The code will be functionally equivalent.
1256 */ 1181 */
1257 local uInt longest_match(s, cur_match, clas) 1182 local uInt longest_match(s, cur_match)
1258 deflate_state *s; 1183 deflate_state *s;
1259 IPos cur_match; /* current match */ 1184 IPos cur_match; /* current match */
1260 int clas;
1261 { 1185 {
1262 unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1186 unsigned chain_length = s->max_chain_length;/* max hash chain length */
1263 register Bytef *scan = s->window + s->strstart; /* current string */ 1187 register Bytef *scan = s->window + s->strstart; /* current string */
1264 register Bytef *match; /* matched string */ 1188 register Bytef *match; /* matched string */
1265 register int len; /* length of current match */ 1189 register int len; /* length of current match */
1266 int best_len = s->prev_length; /* best match length so far */ 1190 int best_len = s->prev_length; /* best match length so far */
1267 int nice_match = s->nice_match; /* stop if match long enough */ 1191 int nice_match = s->nice_match; /* stop if match long enough */
1268 IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 1192 IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1269 s->strstart - (IPos)MAX_DIST(s) : NIL; 1193 s->strstart - (IPos)MAX_DIST(s) : NIL;
1270 /* Stop when cur_match becomes <= limit. To simplify the code, 1194 /* Stop when cur_match becomes <= limit. To simplify the code,
(...skipping 27 matching lines...) Expand all
1298 /* Do not look for matches beyond the end of the input. This is necessary 1222 /* Do not look for matches beyond the end of the input. This is necessary
1299 * to make deflate deterministic. 1223 * to make deflate deterministic.
1300 */ 1224 */
1301 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 1225 if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
1302 1226
1303 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1227 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1304 1228
1305 do { 1229 do {
1306 Assert(cur_match < s->strstart, "no future"); 1230 Assert(cur_match < s->strstart, "no future");
1307 match = s->window + cur_match; 1231 match = s->window + cur_match;
1308 /* If the matched data is in the wrong class, skip it. */
1309 if (s->class_bitmap && class_at(s, cur_match) != clas)
1310 continue;
1311 1232
1312 /* Skip to next match if the match length cannot increase 1233 /* Skip to next match if the match length cannot increase
1313 * or if the match length is less than 2. Note that the checks below 1234 * or if the match length is less than 2. Note that the checks below
1314 * for insufficient lookahead only occur occasionally for performance 1235 * for insufficient lookahead only occur occasionally for performance
1315 * reasons. Therefore uninitialized memory will be accessed, and 1236 * reasons. Therefore uninitialized memory will be accessed, and
1316 * conditional jumps will be made that depend on those values. 1237 * conditional jumps will be made that depend on those values.
1317 * However the length of the match is limited to the lookahead, so 1238 * However the length of the match is limited to the lookahead, so
1318 * the output of deflate is not affected by the uninitialized values. 1239 * the output of deflate is not affected by the uninitialized values.
1319 */ 1240 */
1320 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 1241 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
(...skipping 22 matching lines...) Expand all
1343 scan < strend); 1264 scan < strend);
1344 /* The funny "do {}" generates better code on most compilers */ 1265 /* The funny "do {}" generates better code on most compilers */
1345 1266
1346 /* Here, scan <= window+strstart+257 */ 1267 /* Here, scan <= window+strstart+257 */
1347 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1268 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1348 if (*scan == *match) scan++; 1269 if (*scan == *match) scan++;
1349 1270
1350 len = (MAX_MATCH - 1) - (int)(strend-scan); 1271 len = (MAX_MATCH - 1) - (int)(strend-scan);
1351 scan = strend - (MAX_MATCH-1); 1272 scan = strend - (MAX_MATCH-1);
1352 1273
1353 #error "UNALIGNED_OK hasn't been patched."
1354
1355 #else /* UNALIGNED_OK */ 1274 #else /* UNALIGNED_OK */
1356 1275
1357 if (match[best_len] != scan_end || 1276 if (match[best_len] != scan_end ||
1358 match[best_len-1] != scan_end1 || 1277 match[best_len-1] != scan_end1 ||
1359 *match != *scan || 1278 *match != *scan ||
1360 *++match != scan[1]) continue; 1279 *++match != scan[1]) continue;
1361 1280
1362 /* The check at best_len-1 can be removed because it will be made 1281 /* The check at best_len-1 can be removed because it will be made
1363 * again later. (This heuristic is not always a win.) 1282 * again later. (This heuristic is not always a win.)
1364 * It is not necessary to compare scan[2] and match[2] since they 1283 * It is not necessary to compare scan[2] and match[2] since they
1365 * are always equal when the other bytes match, given that 1284 * are always equal when the other bytes match, given that
1366 * the hash keys are equal and that HASH_BITS >= 8. 1285 * the hash keys are equal and that HASH_BITS >= 8.
1367 */ 1286 */
1368 scan += 2, match++; 1287 scan += 2, match++;
1369 Assert(*scan == *match, "match[2]?"); 1288 Assert(*scan == *match, "match[2]?");
1370 1289
1371 if (!s->class_bitmap) { 1290 /* We check for insufficient lookahead only every 8th comparison;
1372 /* We check for insufficient lookahead only every 8th comparison; 1291 * the 256th check will be made at strstart+258.
1373 * the 256th check will be made at strstart+258. 1292 */
1374 */ 1293 do {
1375 do { 1294 } while (*++scan == *++match && *++scan == *++match &&
1376 } while (*++scan == *++match && *++scan == *++match && 1295 *++scan == *++match && *++scan == *++match &&
1377 *++scan == *++match && *++scan == *++match && 1296 *++scan == *++match && *++scan == *++match &&
1378 *++scan == *++match && *++scan == *++match && 1297 *++scan == *++match && *++scan == *++match &&
1379 *++scan == *++match && *++scan == *++match && 1298 scan < strend);
1380 scan < strend);
1381 } else {
1382 /* We have to be mindful of the class of the data and not stray. */
1383 do {
1384 } while (*++scan == *++match &&
1385 class_at(s, match - s->window) == clas &&
1386 scan < strend);
1387 }
1388 1299
1389 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 1300 Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1390 1301
1391 len = MAX_MATCH - (int)(strend - scan); 1302 len = MAX_MATCH - (int)(strend - scan);
1392 scan = strend - MAX_MATCH; 1303 scan = strend - MAX_MATCH;
1393 1304
1394 #endif /* UNALIGNED_OK */ 1305 #endif /* UNALIGNED_OK */
1395 1306
1396 if (len > best_len) { 1307 if (len > best_len) {
1397 s->match_start = cur_match; 1308 s->match_start = cur_match;
1398 best_len = len; 1309 best_len = len;
1399 if (len >= nice_match) break; 1310 if (len >= nice_match) break;
1400 #ifdef UNALIGNED_OK 1311 #ifdef UNALIGNED_OK
1401 scan_end = *(ushf*)(scan+best_len-1); 1312 scan_end = *(ushf*)(scan+best_len-1);
1402 #else 1313 #else
1403 scan_end1 = scan[best_len-1]; 1314 scan_end1 = scan[best_len-1];
1404 scan_end = scan[best_len]; 1315 scan_end = scan[best_len];
1405 #endif 1316 #endif
1406 } 1317 }
1407 } while ((cur_match = prev[cur_match & wmask]) > limit 1318 } while ((cur_match = prev[cur_match & wmask]) > limit
1408 && --chain_length != 0); 1319 && --chain_length != 0);
1409 1320
1410 if ((uInt)best_len <= s->lookahead) return (uInt)best_len; 1321 if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
1411 return s->lookahead; 1322 return s->lookahead;
1412 } 1323 }
1413 #endif /* ASMV */ 1324 #endif /* ASMV */
1414 1325
1415 /* cookie_match is a replacement for longest_match in the case of cookie data.
1416 * Here we only wish to match the entire value so trying the partial matches in
1417 * longest_match is both wasteful and often fails to find the correct match.
1418 *
1419 * So we take the djb2 hash of the cookie and look up the last position for a
1420 * match in a special hash table. */
1421 local uInt cookie_match(s, start, len)
1422 deflate_state *s;
1423 IPos start;
1424 unsigned len;
1425 {
1426 unsigned hash = 5381;
1427 Bytef *str = s->window + start;
1428 unsigned i;
1429 IPos cookie_location;
1430
1431 if (len >= MAX_MATCH || len == 0)
1432 return 0;
1433
1434 for (i = 0; i < len; i++)
1435 hash = ((hash << 5) + hash) + str[i];
1436
1437 hash &= Z_COOKIE_HASH_MASK;
1438 cookie_location = s->cookie_locations[hash];
1439 s->cookie_locations[hash] = start;
1440 s->match_start = 0;
1441 if (cookie_location &&
1442 (start - cookie_location) > len &&
1443 (start - cookie_location) < MAX_DIST(s) &&
1444 len <= s->lookahead) {
1445 for (i = 0; i < len; i++) {
1446 if (s->window[start+i] != s->window[cookie_location+i] ||
1447 class_at(s, cookie_location+i) != 1) {
1448 return 0;
1449 }
1450 }
1451 /* Check that we aren't matching a prefix of another cookie by ensuring
1452 * that the final byte is either a semicolon (which cannot appear in a
1453 * cookie value), or non-cookie data. */
1454 if (s->window[cookie_location+len-1] != ';' &&
1455 class_at(s, cookie_location+len) != 0) {
1456 return 0;
1457 }
1458 s->match_start = cookie_location;
1459 return len;
1460 }
1461
1462 return 0;
1463 }
1464
1465
1466 #else /* FASTEST */ 1326 #else /* FASTEST */
1467 1327
1468 /* --------------------------------------------------------------------------- 1328 /* ---------------------------------------------------------------------------
1469 * Optimized version for FASTEST only 1329 * Optimized version for FASTEST only
1470 */ 1330 */
1471 local uInt longest_match(s, cur_match, clas) 1331 local uInt longest_match(s, cur_match)
1472 deflate_state *s; 1332 deflate_state *s;
1473 IPos cur_match; /* current match */ 1333 IPos cur_match; /* current match */
1474 int clas;
1475 { 1334 {
1476 register Bytef *scan = s->window + s->strstart; /* current string */ 1335 register Bytef *scan = s->window + s->strstart; /* current string */
1477 register Bytef *match; /* matched string */ 1336 register Bytef *match; /* matched string */
1478 register int len; /* length of current match */ 1337 register int len; /* length of current match */
1479 register Bytef *strend = s->window + s->strstart + MAX_MATCH; 1338 register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1480 1339
1481 #error "This code not patched"
1482
1483 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1340 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1484 * It is easy to get rid of this optimization if necessary. 1341 * It is easy to get rid of this optimization if necessary.
1485 */ 1342 */
1486 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 1343 Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1487 1344
1488 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 1345 Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1489 1346
1490 Assert(cur_match < s->strstart, "no future"); 1347 Assert(cur_match < s->strstart, "no future");
1491 1348
1492 match = s->window + cur_match; 1349 match = s->window + cur_match;
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after
1629 #ifndef FASTEST 1486 #ifndef FASTEST
1630 p = &s->prev[n]; 1487 p = &s->prev[n];
1631 do { 1488 do {
1632 m = *--p; 1489 m = *--p;
1633 *p = (Pos)(m >= wsize ? m-wsize : NIL); 1490 *p = (Pos)(m >= wsize ? m-wsize : NIL);
1634 /* If n is not on any hash chain, prev[n] is garbage but 1491 /* If n is not on any hash chain, prev[n] is garbage but
1635 * its value will never be used. 1492 * its value will never be used.
1636 */ 1493 */
1637 } while (--n); 1494 } while (--n);
1638 #endif 1495 #endif
1639 for (n = 0; n < Z_COOKIE_HASH_SIZE; n++) {
1640 if (s->cookie_locations[n] > wsize) {
1641 s->cookie_locations[n] -= wsize;
1642 } else {
1643 s->cookie_locations[n] = 0;
1644 }
1645 }
1646
1647 if (s->class_bitmap) {
1648 zmemcpy(s->class_bitmap, s->class_bitmap + s->w_size/8,
1649 s->w_size/8);
1650 zmemzero(s->class_bitmap + s->w_size/8, s->w_size/8);
1651 }
1652
1653 more += wsize; 1496 more += wsize;
1654 } 1497 }
1655 if (s->strm->avail_in == 0) break; 1498 if (s->strm->avail_in == 0) break;
1656 1499
1657 /* If there was no sliding: 1500 /* If there was no sliding:
1658 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 1501 * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1659 * more == window_size - lookahead - strstart 1502 * more == window_size - lookahead - strstart
1660 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 1503 * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1661 * => more >= window_size - 2*WSIZE + 2 1504 * => more >= window_size - 2*WSIZE + 2
1662 * In the BIG_MEM or MMAP case (not yet supported), 1505 * In the BIG_MEM or MMAP case (not yet supported),
1663 * window_size == input_size + MIN_LOOKAHEAD && 1506 * window_size == input_size + MIN_LOOKAHEAD &&
1664 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 1507 * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1665 * Otherwise, window_size == 2*WSIZE so more >= 2. 1508 * Otherwise, window_size == 2*WSIZE so more >= 2.
1666 * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 1509 * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1667 */ 1510 */
1668 Assert(more >= 2, "more < 2"); 1511 Assert(more >= 2, "more < 2");
1669 1512
1670 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more); 1513 n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1671 if (s->class_bitmap != NULL) {
1672 class_set(s, s->strstart + s->lookahead, n, s->strm->clas);
1673 }
1674 s->lookahead += n; 1514 s->lookahead += n;
1675 1515
1676 /* Initialize the hash value now that we have some input: */ 1516 /* Initialize the hash value now that we have some input: */
1677 if (s->lookahead + s->insert >= MIN_MATCH) { 1517 if (s->lookahead + s->insert >= MIN_MATCH) {
1678 uInt str = s->strstart - s->insert; 1518 uInt str = s->strstart - s->insert;
1679 s->ins_h = s->window[str]; 1519 s->ins_h = s->window[str];
1680 UPDATE_HASH(s, s->ins_h, s->window[str + 1]); 1520 UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
1681 #if MIN_MATCH != 3 1521 #if MIN_MATCH != 3
1682 Call UPDATE_HASH() MIN_MATCH-3 more times 1522 Call UPDATE_HASH() MIN_MATCH-3 more times
1683 #endif 1523 #endif
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after
1760 1600
1761 /* =========================================================================== 1601 /* ===========================================================================
1762 * Copy without compression as much as possible from the input stream, return 1602 * Copy without compression as much as possible from the input stream, return
1763 * the current block state. 1603 * the current block state.
1764 * This function does not insert new strings in the dictionary since 1604 * This function does not insert new strings in the dictionary since
1765 * uncompressible data is probably not useful. This function is used 1605 * uncompressible data is probably not useful. This function is used
1766 * only for the level=0 compression option. 1606 * only for the level=0 compression option.
1767 * NOTE: this function should be optimized to avoid extra copying from 1607 * NOTE: this function should be optimized to avoid extra copying from
1768 * window to pending_buf. 1608 * window to pending_buf.
1769 */ 1609 */
1770 local block_state deflate_stored(s, flush, clas) 1610 local block_state deflate_stored(s, flush)
1771 deflate_state *s; 1611 deflate_state *s;
1772 int flush; 1612 int flush;
1773 int clas;
1774 { 1613 {
1775 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 1614 /* Stored blocks are limited to 0xffff bytes, pending_buf is limited
1776 * to pending_buf_size, and each stored block has a 5 byte header: 1615 * to pending_buf_size, and each stored block has a 5 byte header:
1777 */ 1616 */
1778 ulg max_block_size = 0xffff; 1617 ulg max_block_size = 0xffff;
1779 ulg max_start; 1618 ulg max_start;
1780 1619
1781 if (max_block_size > s->pending_buf_size - 5) { 1620 if (max_block_size > s->pending_buf_size - 5) {
1782 max_block_size = s->pending_buf_size - 5; 1621 max_block_size = s->pending_buf_size - 5;
1783 } 1622 }
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
1825 return block_done; 1664 return block_done;
1826 } 1665 }
1827 1666
1828 /* =========================================================================== 1667 /* ===========================================================================
1829 * Compress as much as possible from the input stream, return the current 1668 * Compress as much as possible from the input stream, return the current
1830 * block state. 1669 * block state.
1831 * This function does not perform lazy evaluation of matches and inserts 1670 * This function does not perform lazy evaluation of matches and inserts
1832 * new strings in the dictionary only for unmatched strings or for short 1671 * new strings in the dictionary only for unmatched strings or for short
1833 * matches. It is used only for the fast compression options. 1672 * matches. It is used only for the fast compression options.
1834 */ 1673 */
1835 local block_state deflate_fast(s, flush, clas) 1674 local block_state deflate_fast(s, flush)
1836 deflate_state *s; 1675 deflate_state *s;
1837 int flush; 1676 int flush;
1838 int clas;
1839 { 1677 {
1840 IPos hash_head; /* head of the hash chain */ 1678 IPos hash_head; /* head of the hash chain */
1841 int bflush; /* set if current block must be flushed */ 1679 int bflush; /* set if current block must be flushed */
1842 1680
1843 if (clas != 0) {
1844 /* We haven't patched this code for alternative class data. */
1845 return Z_BUF_ERROR;
1846 }
1847
1848 for (;;) { 1681 for (;;) {
1849 /* Make sure that we always have enough lookahead, except 1682 /* Make sure that we always have enough lookahead, except
1850 * at the end of the input file. We need MAX_MATCH bytes 1683 * at the end of the input file. We need MAX_MATCH bytes
1851 * for the next match, plus MIN_MATCH bytes to insert the 1684 * for the next match, plus MIN_MATCH bytes to insert the
1852 * string following the next match. 1685 * string following the next match.
1853 */ 1686 */
1854 if (s->lookahead < MIN_LOOKAHEAD) { 1687 if (s->lookahead < MIN_LOOKAHEAD) {
1855 fill_window(s); 1688 fill_window(s);
1856 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1689 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1857 return need_more; 1690 return need_more;
(...skipping 10 matching lines...) Expand all
1868 } 1701 }
1869 1702
1870 /* Find the longest match, discarding those <= prev_length. 1703 /* Find the longest match, discarding those <= prev_length.
1871 * At this point we have always match_length < MIN_MATCH 1704 * At this point we have always match_length < MIN_MATCH
1872 */ 1705 */
1873 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 1706 if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1874 /* To simplify the code, we prevent matches with the string 1707 /* To simplify the code, we prevent matches with the string
1875 * of window index 0 (in particular we have to avoid a match 1708 * of window index 0 (in particular we have to avoid a match
1876 * of the string with itself at the start of the input file). 1709 * of the string with itself at the start of the input file).
1877 */ 1710 */
1878 s->match_length = longest_match (s, hash_head, clas); 1711 s->match_length = longest_match (s, hash_head);
1879 /* longest_match() sets match_start */ 1712 /* longest_match() sets match_start */
1880 } 1713 }
1881 if (s->match_length >= MIN_MATCH) { 1714 if (s->match_length >= MIN_MATCH) {
1882 check_match(s, s->strstart, s->match_start, s->match_length); 1715 check_match(s, s->strstart, s->match_start, s->match_length);
1883 1716
1884 _tr_tally_dist(s, s->strstart - s->match_start, 1717 _tr_tally_dist(s, s->strstart - s->match_start,
1885 s->match_length - MIN_MATCH, bflush); 1718 s->match_length - MIN_MATCH, bflush);
1886 1719
1887 s->lookahead -= s->match_length; 1720 s->lookahead -= s->match_length;
1888 1721
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after
1933 FLUSH_BLOCK(s, 0); 1766 FLUSH_BLOCK(s, 0);
1934 return block_done; 1767 return block_done;
1935 } 1768 }
1936 1769
1937 #ifndef FASTEST 1770 #ifndef FASTEST
1938 /* =========================================================================== 1771 /* ===========================================================================
1939 * Same as above, but achieves better compression. We use a lazy 1772 * Same as above, but achieves better compression. We use a lazy
1940 * evaluation for matches: a match is finally adopted only if there is 1773 * evaluation for matches: a match is finally adopted only if there is
1941 * no better match at the next window position. 1774 * no better match at the next window position.
1942 */ 1775 */
1943 local block_state deflate_slow(s, flush, clas) 1776 local block_state deflate_slow(s, flush)
1944 deflate_state *s; 1777 deflate_state *s;
1945 int flush; 1778 int flush;
1946 int clas;
1947 { 1779 {
1948 IPos hash_head; /* head of hash chain */ 1780 IPos hash_head; /* head of hash chain */
1949 int bflush; /* set if current block must be flushed */ 1781 int bflush; /* set if current block must be flushed */
1950 uInt input_length ;
1951 int first = 1; /* first says whether this is the first iteration
1952 of the loop, below. */
1953
1954 if (clas == Z_CLASS_COOKIE) {
1955 if (s->lookahead) {
1956 /* Alternative class data must always be presented at the beginning
1957 * of a block. */
1958 return Z_BUF_ERROR;
1959 }
1960 input_length = s->strm->avail_in;
1961 }
1962 1782
1963 /* Process the input block. */ 1783 /* Process the input block. */
1964 for (;;) { 1784 for (;;) {
1965 /* Make sure that we always have enough lookahead, except 1785 /* Make sure that we always have enough lookahead, except
1966 * at the end of the input file. We need MAX_MATCH bytes 1786 * at the end of the input file. We need MAX_MATCH bytes
1967 * for the next match, plus MIN_MATCH bytes to insert the 1787 * for the next match, plus MIN_MATCH bytes to insert the
1968 * string following the next match. 1788 * string following the next match.
1969 */ 1789 */
1970 if (s->lookahead < MIN_LOOKAHEAD) { 1790 if (s->lookahead < MIN_LOOKAHEAD) {
1971 fill_window(s); 1791 fill_window(s);
1972 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1792 if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1973 return need_more; 1793 return need_more;
1974 } 1794 }
1975 if (s->lookahead == 0) break; /* flush the current block */ 1795 if (s->lookahead == 0) break; /* flush the current block */
1976 } 1796 }
1977 1797
1978 /* Insert the string window[strstart .. strstart+2] in the 1798 /* Insert the string window[strstart .. strstart+2] in the
1979 * dictionary, and set hash_head to the head of the hash chain: 1799 * dictionary, and set hash_head to the head of the hash chain:
1980 */ 1800 */
1981 hash_head = NIL; 1801 hash_head = NIL;
1982 if (s->lookahead >= MIN_MATCH) { 1802 if (s->lookahead >= MIN_MATCH) {
1983 hash_head = insert_string(s, s->strstart); 1803 hash_head = insert_string(s, s->strstart);
1984 } 1804 }
1985 1805
1986 /* Find the longest match, discarding those <= prev_length. 1806 /* Find the longest match, discarding those <= prev_length.
1987 */ 1807 */
1988 s->prev_length = s->match_length, s->prev_match = s->match_start; 1808 s->prev_length = s->match_length, s->prev_match = s->match_start;
1989 s->match_length = MIN_MATCH-1; 1809 s->match_length = MIN_MATCH-1;
1990 1810
1991 if (clas == Z_CLASS_COOKIE && first) { 1811 if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1992 s->match_length = cookie_match(s, s->strstart, input_length); 1812 s->strstart - hash_head <= MAX_DIST(s)) {
1993 } else if (clas == Z_CLASS_STANDARD &&
1994 hash_head != NIL &&
1995 s->prev_length < s->max_lazy_match &&
1996 s->strstart - hash_head <= MAX_DIST(s)) {
1997 /* To simplify the code, we prevent matches with the string 1813 /* To simplify the code, we prevent matches with the string
1998 * of window index 0 (in particular we have to avoid a match 1814 * of window index 0 (in particular we have to avoid a match
1999 * of the string with itself at the start of the input file). 1815 * of the string with itself at the start of the input file).
2000 */ 1816 */
2001 s->match_length = longest_match (s, hash_head, clas); 1817 s->match_length = longest_match (s, hash_head);
2002
2003 /* longest_match() sets match_start */ 1818 /* longest_match() sets match_start */
2004 1819
2005 if (s->match_length <= 5 && (s->strategy == Z_FILTERED 1820 if (s->match_length <= 5 && (s->strategy == Z_FILTERED
2006 #if TOO_FAR <= 32767 1821 #if TOO_FAR <= 32767
2007 || (s->match_length == MIN_MATCH && 1822 || (s->match_length == MIN_MATCH &&
2008 s->strstart - s->match_start > TOO_FAR) 1823 s->strstart - s->match_start > TOO_FAR)
2009 #endif 1824 #endif
2010 )) { 1825 )) {
2011 1826
2012 /* If prev_match is also MIN_MATCH, match_start is garbage 1827 /* If prev_match is also MIN_MATCH, match_start is garbage
2013 * but we will ignore the current match anyway. 1828 * but we will ignore the current match anyway.
2014 */ 1829 */
2015 s->match_length = MIN_MATCH-1; 1830 s->match_length = MIN_MATCH-1;
2016 } 1831 }
2017 } 1832 }
2018 /* If there was a match at the previous step and the current 1833 /* If there was a match at the previous step and the current
2019 * match is not better, output the previous match: 1834 * match is not better, output the previous match:
2020 */ 1835 */
2021 first = 0; 1836 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
2022 if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length &&
2023 /* We will only accept an exact match for Z_CLASS_COOKIE data and
2024 * we won't match Z_CLASS_HUFFMAN_ONLY data at all. */
2025 (clas == Z_CLASS_STANDARD || (clas == Z_CLASS_COOKIE &&
2026 s->prev_length == input_length &&
2027 s->prev_match > 0 &&
2028 /* We require that a Z_CLASS_COOKIE match be
2029 * preceded by either a semicolon (which cannot be
2030 * part of a cookie), or non-cookie data. This is
2031 * to prevent a cookie from being a suffix of
2032 * another. */
2033 (class_at(s, s->prev_match-1) == Z_CLASS_STANDARD ||
2034 *(s->window + s->prev_match-1) == ';')))) {
2035 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 1837 uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
2036 /* Do not insert strings in hash table beyond this. */ 1838 /* Do not insert strings in hash table beyond this. */
2037 1839
2038 check_match(s, s->strstart-1, s->prev_match, s->prev_length); 1840 check_match(s, s->strstart-1, s->prev_match, s->prev_length);
2039 1841
2040 _tr_tally_dist(s, s->strstart -1 - s->prev_match, 1842 _tr_tally_dist(s, s->strstart -1 - s->prev_match,
2041 s->prev_length - MIN_MATCH, bflush); 1843 s->prev_length - MIN_MATCH, bflush);
2042 1844
2043 /* Insert in hash table all strings up to the end of the match. 1845 /* Insert in hash table all strings up to the end of the match.
2044 * strstart-1 and strstart are already inserted. If there is not 1846 * strstart-1 and strstart are already inserted. If there is not
(...skipping 191 matching lines...) Expand 10 before | Expand all | Expand 10 after
2236 #else 2038 #else
2237 /* This should never happen */ 2039 /* This should never happen */
2238 assert(0); 2040 assert(0);
2239 #endif 2041 #endif
2240 2042
2241 ret = s->head[h & s->hash_mask]; 2043 ret = s->head[h & s->hash_mask];
2242 s->head[h & s->hash_mask] = str; 2044 s->head[h & s->hash_mask] = str;
2243 s->prev[str & s->w_mask] = ret; 2045 s->prev[str & s->w_mask] = ret;
2244 return ret; 2046 return ret;
2245 } 2047 }
OLDNEW
« no previous file with comments | « third_party/zlib/deflate.h ('k') | third_party/zlib/mixed-source.patch » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698