Suffix array based matchfinder updates
[wimlib] / src / lcpit_matchfinder.c
1 /*
2  * lcpit_matchfinder.h
3  *
4  * A match-finder for Lempel-Ziv compression based on bottom-up construction and
5  * traversal of the Longest Common Prefix (LCP) interval tree.
6  *
7  * Author:      Eric Biggers
8  * Year:        2014, 2015
9  *
10  * The author dedicates this file to the public domain.
11  * You can do whatever you want with this file.
12  */
13
14 #include <limits.h>
15 #include <string.h>
16
17 #include "wimlib/divsufsort.h"
18 #include "wimlib/lcpit_matchfinder.h"
19 #include "wimlib/util.h"
20
21 #define LCP_BITS                6
22 #define LCP_MASK                ((1 << LCP_BITS) - 1)
23 #define LCP_MAX                 LCP_MASK
24 #define NORMAL_UNVISITED_TAG    ((u32)1 << 31)
25 #define MAX_NORMAL_BUFSIZE      ((u32)1 << (31 - LCP_BITS))
26 #define HUGE_UNVISITED_TAG      ((u64)1 << 63)
27 #define SA_and_LCP_LCP_SHIFT    (32 - LCP_BITS)
28 #define SA_and_LCP_POS_MASK     (((u32)1 << SA_and_LCP_LCP_SHIFT) - 1)
29
30 /*
31  * Include the template header to define the functions build_LCP(),
32  * build_LCPIT(), and lcpit_advance_one_byte().  There are "normal" and "huge"
33  * versions of each function.  The normal versions assume that a buffer position
34  * and LCP value can be packed into a 32-bit integer, whereas the huge versions
35  * assume that 64 bits is needed.
36  *
37  * Both versions cap LCP values to 6 bits. This limits the depth of the
38  * lcp-interval tree without hurting the compression ratio too much.  Matches of
39  * length 63 are sufficiently long that the compression ratio doesn't change
40  * significantly if we choose one such match over another.
41  */
42 #define HUGE_MODE 1
43 #include "lcpit_matchfinder_templates.h"
44 #undef HUGE_MODE
45
46 #define HUGE_MODE 0
47 #include "lcpit_matchfinder_templates.h"
48 #undef HUGE_MODE
49
50 /*
51  * Calculate the number of bytes of memory needed for the LCP-interval tree
52  * matchfinder.
53  *
54  * @max_bufsize - maximum buffer size to support
55  *
56  * Returns the number of bytes required.
57  */
58 u64
59 lcpit_matchfinder_get_needed_memory(size_t max_bufsize)
60 {
61         u64 size = 0;
62
63         /* pos_data (+1 is for prefetch) */
64         size += ((u64)max_bufsize + 1) * sizeof(u32);
65
66         /* intervals or intervals64  */
67         size += max((u64)max_bufsize, DIVSUFSORT_TMP_LEN) *
68                 (max_bufsize <= MAX_NORMAL_BUFSIZE ? sizeof(u32) : sizeof(u64));
69
70         /* SA */
71         size += (u64)max_bufsize * sizeof(u32);
72
73         return size;
74 }
75
76 /*
77  * Initialize the LCP-interval tree matchfinder.
78  *
79  * @mf - the matchfinder structure to initialize
80  * @max_bufsize - maximum buffer size to support
81  * @min_match_len - minimum match length in bytes
82  * @nice_match_len - only consider this many bytes of each match
83  *
84  * Returns true if successfully initialized; false if out of memory.
85  */
86 bool
87 lcpit_matchfinder_init(struct lcpit_matchfinder *mf, size_t max_bufsize,
88                        u32 min_match_len, u32 nice_match_len)
89 {
90         if (lcpit_matchfinder_get_needed_memory(max_bufsize) > SIZE_MAX)
91                 return false;
92
93         mf->pos_data = MALLOC((max_bufsize + 1) * sizeof(u32));
94         mf->intervals = MALLOC(max((u64)max_bufsize, DIVSUFSORT_TMP_LEN) *
95                                (max_bufsize <= MAX_NORMAL_BUFSIZE ?
96                                 sizeof(u32) : sizeof(u64)));
97         mf->SA = MALLOC(max_bufsize * sizeof(u32));
98
99         if (!mf->pos_data || !mf->intervals || !mf->SA) {
100                 lcpit_matchfinder_destroy(mf);
101                 return false;
102         }
103
104         mf->min_match_len = min_match_len;
105         mf->nice_match_len = min(nice_match_len, LCP_MAX);
106         return true;
107 }
108
109 /*
110  * Build the suffix array SA for the specified byte array T of length n.
111  *
112  * The suffix array is a sorted array of the byte array's suffixes, represented
113  * by indices into the byte array.  It can equivalently be viewed as a mapping
114  * from suffix rank to suffix position.
115  *
116  * To build the suffix array, we use libdivsufsort, which uses an
117  * induced-sorting-based algorithm.  In practice, this seems to be the fastest
118  * suffix array construction algorithm currently available.
119  *
120  * References:
121  *
122  *      Y. Mori.  libdivsufsort, a lightweight suffix-sorting library.
123  *      https://code.google.com/p/libdivsufsort/.
124  *
125  *      G. Nong, S. Zhang, and W.H. Chan.  2009.  Linear Suffix Array
126  *      Construction by Almost Pure Induced-Sorting.  Data Compression
127  *      Conference, 2009.  DCC '09.  pp. 193 - 202.
128  *
129  *      S.J. Puglisi, W.F. Smyth, and A. Turpin.  2007.  A Taxonomy of Suffix
130  *      Array Construction Algorithms.  ACM Computing Surveys (CSUR) Volume 39
131  *      Issue 2, 2007 Article No. 4.
132  */
133 static void
134 build_SA(u32 SA[], const u8 T[], u32 n, u32 *tmp)
135 {
136         /* Note: divsufsort() needs temporary space --- one array with 256
137          * spaces and one array with 65536 spaces.  The implementation of
138          * divsufsort() has been modified from the original to use the provided
139          * temporary space instead of allocating its own, since we don't want to
140          * have to deal with malloc() failures here.  */
141         divsufsort(T, SA, n, tmp);
142 }
143
144 /*
145  * Build the inverse suffix array ISA from the suffix array SA.
146  *
147  * Whereas the suffix array is a mapping from suffix rank to suffix position,
148  * the inverse suffix array is a mapping from suffix position to suffix rank.
149  */
150 static void
151 build_ISA(u32 ISA[restrict], const u32 SA[restrict], u32 n)
152 {
153         for (u32 r = 0; r < n; r++)
154                 ISA[SA[r]] = r;
155 }
156
157 /*
158  * Prepare the LCP-interval tree matchfinder for a new input buffer.
159  *
160  * @mf - the initialized matchfinder structure
161  * @T - the input buffer
162  * @n - size of the input buffer in bytes.  This may be at most the max_bufsize
163  *      with which lcpit_matchfinder_init() was called.
164  */
165 void
166 lcpit_matchfinder_load_buffer(struct lcpit_matchfinder *mf, const u8 *T, u32 n)
167 {
168         if (n == 0)
169                 return;
170
171         build_SA(mf->SA, T, n, mf->intervals);
172         build_ISA(mf->pos_data, mf->SA, n);
173         if (n <= MAX_NORMAL_BUFSIZE) {
174                 /* "Normal" sized buffer  */
175
176                 /* Build LCP, packing it into ->SA  */
177                 build_LCP_normal(mf->SA, mf->pos_data, T, n,
178                                  mf->min_match_len, mf->nice_match_len);
179                 /* Prepare ->intervals and ->pos_data  */
180                 build_LCPIT_normal(mf->SA, mf->intervals, mf->pos_data, n);
181                 mf->huge_mode = false;
182         } else {
183                 /* "Huge" sized buffer  */
184
185                 /* Build LCP in the second half of ->intervals64.  It may be
186                  * partially overwritten in build_LCPIT_huge(), but this is okay
187                  * since each LCP entry is guaranteed to be consumed before it
188                  * can possibly be overwritten.  */
189                 build_LCP_huge(mf->intervals + n, mf->SA, mf->pos_data, T, n,
190                                mf->min_match_len, mf->nice_match_len);
191                 /* Prepare ->intervals64 and ->pos_data  */
192                 build_LCPIT_huge(mf->SA, mf->intervals + n, mf->intervals64,
193                                  mf->pos_data, n);
194                 mf->huge_mode = true;
195         }
196         mf->cur_pos = 0; /* starting at beginning of input buffer  */
197         mf->pos_data[n] = 0; /* safety entry for prefetch() overrun  */
198 }
199
200 /*
201  * Retrieve a list of matches with the next position.
202  *
203  * The matches will be recorded in the @matches array, ordered by strictly
204  * decreasing length and strictly decreasing offset.
205  *
206  * The return value is the number of matches found and written to @matches.
207  * This can be any value in [0, nice_match_len - min_match_len + 1].
208  *
209  * If the caller attempts to advance beyond the end of the input buffer, the
210  * behavior is undefined.
211  */
212 u32
213 lcpit_matchfinder_get_matches(struct lcpit_matchfinder *mf,
214                               struct lz_match *matches)
215 {
216         if (mf->huge_mode)
217                 return lcpit_advance_one_byte_huge(mf, matches, true);
218         else
219                 return lcpit_advance_one_byte_normal(mf, matches, true);
220 }
221
222 /*
223  * Skip the next @count bytes (don't search for matches at them).  @count is
224  * assumed to be > 0.
225  *
226  * If the caller attempts to advance beyond the end of the input buffer, the
227  * behavior is undefined.
228  */
229 void
230 lcpit_matchfinder_skip_bytes(struct lcpit_matchfinder *mf, u32 count)
231 {
232         if (mf->huge_mode) {
233                 do {
234                         lcpit_advance_one_byte_huge(mf, NULL, false);
235                 } while (--count);
236         } else {
237                 do {
238                         lcpit_advance_one_byte_normal(mf, NULL, false);
239                 } while (--count);
240         }
241 }
242
243 /*
244  * Destroy an LCP-interval tree matchfinder that was previously initialized with
245  * lcpit_matchfinder_init().
246  *
247  * If the struct has been zeroed out, this has no effect.
248  */
249 void
250 lcpit_matchfinder_destroy(struct lcpit_matchfinder *mf)
251 {
252         FREE(mf->pos_data);
253         FREE(mf->intervals);
254         FREE(mf->SA);
255         memset(mf, 0, sizeof(*mf));
256 }