* A match-finder for Lempel-Ziv compression based on bottom-up construction and
* traversal of the Longest Common Prefix (LCP) interval tree.
*
- * The following copying information applies to this specific source code file:
- *
- * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
- *
- * To the extent possible under law, the author(s) have dedicated all copyright
- * and related and neighboring rights to this software to the public domain
- * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
- * Dedication (the "CC0").
- *
- * This software is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
- * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
- *
- * You should have received a copy of the CC0 along with this software; if not
- * see <http://creativecommons.org/publicdomain/zero/1.0/>.
+ * Copyright 2022 Eric Biggers
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
*/
#ifdef HAVE_CONFIG_H
* around by just continuing until we get to a link that actually takes us
* higher in the tree. This can be described as a lazy-update scheme.
*/
-static inline u32
+static forceinline u32
lcpit_advance_one_byte(const u32 cur_pos,
u32 pos_data[restrict],
u32 intervals[restrict],
static void
expand_SA(void *p, u32 n)
{
- typedef u32 _may_alias_attribute aliased_u32_t;
- typedef u64 _may_alias_attribute aliased_u64_t;
+ typedef u32 __attribute__((may_alias)) aliased_u32_t;
+ typedef u64 __attribute__((may_alias)) aliased_u64_t;
aliased_u32_t *SA = p;
aliased_u64_t *SA64 = p;
/* Like lcpit_advance_one_byte(), but for buffers larger than
* MAX_NORMAL_BUFSIZE. */
-static inline u32
+static forceinline u32
lcpit_advance_one_byte_huge(const u32 cur_pos,
u32 pos_data[restrict],
u64 intervals64[restrict],
return matchptr - matches;
}
-static inline u64
+static forceinline u64
get_pos_data_size(size_t max_bufsize)
{
return (u64)max((u64)max_bufsize + PREFETCH_SAFETY,
DIVSUFSORT_TMP_LEN) * sizeof(u32);
}
-static inline u64
+static forceinline u64
get_intervals_size(size_t max_bufsize)
{
return ((u64)max_bufsize + PREFETCH_SAFETY) *
}
mf->min_match_len = min_match_len;
- mf->nice_match_len = min(nice_match_len,
- (max_bufsize <= MAX_NORMAL_BUFSIZE) ?
- LCP_MAX : HUGE_LCP_MAX);
+ mf->orig_nice_match_len = nice_match_len;
return true;
}
* References:
*
* Y. Mori. libdivsufsort, a lightweight suffix-sorting library.
- * https://code.google.com/p/libdivsufsort/.
+ * https://github.com/y-256/libdivsufsort
*
* G. Nong, S. Zhang, and W.H. Chan. 2009. Linear Suffix Array
* Construction by Almost Pure Induced-Sorting. Data Compression
build_SA(mf->intervals, T, n, mf->pos_data);
build_ISA(mf->pos_data, mf->intervals, n);
if (n <= MAX_NORMAL_BUFSIZE) {
+ mf->nice_match_len = min(mf->orig_nice_match_len, LCP_MAX);
for (u32 i = 0; i < PREFETCH_SAFETY; i++) {
mf->intervals[n + i] = 0;
mf->pos_data[n + i] = 0;
build_LCPIT(mf->intervals, mf->pos_data, n);
mf->huge_mode = false;
} else {
+ mf->nice_match_len = min(mf->orig_nice_match_len, HUGE_LCP_MAX);
for (u32 i = 0; i < PREFETCH_SAFETY; i++) {
mf->intervals64[n + i] = 0;
mf->pos_data[n + i] = 0;