libkern/zlib/deflate.c

45  *      string matches are performed only when the previous match ends. So it
49  *      is used to find longer strings when a small match has been found.
124 local  void check_match OF((deflate_state *s, IPos start, IPos match,
151    ush good_length; /* reduce lazy search above this match length */
152    ush max_lazy;    /* do not perform lazy search above this match length */
153    ush nice_length; /* quit search above this match length */
1013  * Initialize the "longest match" routines for a new zlib stream
1044  * Set match_start to the longest match starting at the given string and
1050  * OUT assertion: the match length is not greater than s->lookahead.
1053 /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1054  * match.S. The code will be functionally equivalent.
1058     IPos cur_match;                             /* current match */
1062     register Bytef *match;                       /* matched string */
1063     register int len;                           /* length of current match */
1064     int best_len = s->prev_length;              /* best match length so far */
1065     int nice_match = s->nice_match;             /* stop if match long enough */
1092     /* Do not waste too much time if we already have a good match: */
1105         match = s->window + cur_match;
1107         /* Skip to next match if the match length cannot increase
1108          * or if the match length is less than 2.  Note that the checks below
1112          * However the length of the match is limited to the lookahead, so
1119         if (*(ushf*)(match+best_len-1) != scan_end ||
1120             *(ushf*)match != scan_start) continue;
1122         /* It is not necessary to compare scan[2] and match[2] since they are
1123          * always equal when the other bytes match, given that the hash keys
1131         Assert(scan[2] == match[2], "scan[2]?");
1132         scan++, match++;
1134         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1135                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1136                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1137                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1143         if (*scan == *match) scan++;
1150         if (match[best_len]   != scan_end  ||
1151             match[best_len-1] != scan_end1 ||
1152             *match            != *scan     ||
1153             *++match          != scan[1])      continue;
1157          * It is not necessary to compare scan[2] and match[2] since they
1158          * are always equal when the other bytes match, given that
1161         scan += 2, match++;
1162         Assert(*scan == *match, "match[2]?");
1168         } while (*++scan == *++match && *++scan == *++match &&
1169                  *++scan == *++match && *++scan == *++match &&
1170                  *++scan == *++match && *++scan == *++match &&
1171                  *++scan == *++match && *++scan == *++match &&
1206     IPos cur_match;                             /* current match */
1209     register Bytef *match;                       /* matched string */
1210     register int len;                           /* length of current match */
1222     match = s->window + cur_match;
1224     /* Return failure if the match length is less than 2:
1226     if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
1230      * It is not necessary to compare scan[2] and match[2] since they
1231      * are always equal when the other bytes match, given that
1234     scan += 2, match += 2;
1235     Assert(*scan == *match, "match[2]?");
1241     } while (*++scan == *++match && *++scan == *++match &&
1242              *++scan == *++match && *++scan == *++match &&
1243              *++scan == *++match && *++scan == *++match &&
1244              *++scan == *++match && *++scan == *++match &&
1259  * Check that the match at match_start is indeed a match.
1261 local void check_match(s, start, match, length)
1263     IPos start, match;
1266     /* check that the match is indeed a match */
1267     if (zmemcmp(s->window + match,
1269         fprintf(stderr, " start %u, match %u, length %d\n",
1270                 start, match, length);
1272             fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1274         z_error("invalid match");
1277         fprintf(stderr,"\\[%d,%d]", start-match, length);
1282 #  define check_match(s, start, match, length)
1391  * IN assertion: strstart is set to the end of the current match.
1487          * for the next match, plus MIN_MATCH bytes to insert the
1488          * string following the next match.
1505         /* Find the longest match, discarding those <= prev_length.
1510              * of window index 0 (in particular we have to avoid a match
1535             /* Insert new strings in the hash table only if the match length
1565             /* No match, output a literal byte */
1580  * evaluation for matches: a match is finally adopted only if there is
1581  * no better match at the next window position.
1594          * for the next match, plus MIN_MATCH bytes to insert the
1595          * string following the next match.
1612         /* Find the longest match, discarding those <= prev_length.
1620              * of window index 0 (in particular we have to avoid a match
1638                  * but we will ignore the current match anyway.
1643         /* If there was a match at the previous step and the current
1644          * match is not better, output the previous match:
1655             /* Insert in hash table all strings up to the end of the match.
1674             /* If there was no match at the previous position, output a
1675              * single literal. If there was a match but the current match
1676              * is longer, truncate the previous match to a single literal.
1687             /* There is no previous match to compare with, wait for
1719     uInt prev;          /* byte at distance one to match */
1747         /* Emit match if have run of MIN_MATCH or longer, else emit literal */
1754             /* No match, output a literal byte */