d47e0976d5836ff0214dcfc6563bec63911a559d
[wimlib] / include / wimlib / lz_extend.h
1 /*
2  * lz_extend.h
3  *
4  * Fast match extension for Lempel-Ziv matchfinding.
5  *
6  * The author dedicates this file to the public domain.
7  * You can do whatever you want with this file.
8  */
9
10 #ifndef _WIMLIB_LZ_EXTEND_H
11 #define _WIMLIB_LZ_EXTEND_H
12
13 #include "wimlib/bitops.h"
14 #include "wimlib/unaligned.h"
15
16 /* Return the number of bytes at @matchptr that match the bytes at @strptr, up
17  * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
18 static inline u32
19 lz_extend(const u8 * const strptr, const u8 * const matchptr,
20           const u32 start_len, const u32 max_len)
21 {
22         u32 len = start_len;
23
24         if (UNALIGNED_ACCESS_IS_FAST && CPU_IS_LITTLE_ENDIAN) {
25
26                 machine_word_t v_word;
27
28                 if (likely(max_len - len >= 4 * WORDSIZE)) {
29
30                 #define COMPARE_WORD_STEP                                       \
31                         v_word = load_word_unaligned(&matchptr[len]) ^          \
32                                  load_word_unaligned(&strptr[len]);             \
33                         if (v_word != 0)                                        \
34                                 goto word_differs;                              \
35                         len += WORDSIZE;                                        \
36
37                         COMPARE_WORD_STEP
38                         COMPARE_WORD_STEP
39                         COMPARE_WORD_STEP
40                         COMPARE_WORD_STEP
41                 #undef COMPARE_WORD_STEP
42                 }
43
44                 while (len + WORDSIZE <= max_len) {
45                         v_word = load_word_unaligned(&matchptr[len]) ^
46                                  load_word_unaligned(&strptr[len]);
47                         if (v_word != 0)
48                                 goto word_differs;
49                         len += WORDSIZE;
50                 }
51
52                 while (len < max_len && matchptr[len] == strptr[len])
53                         len++;
54                 return len;
55
56         word_differs:
57                 return len + (ffsw(v_word) >> 3);
58         } else {
59                 while (len < max_len && matchptr[len] == strptr[len])
60                         len++;
61                 return len;
62         }
63 }
64
65 #endif /* _WIMLIB_LZ_EXTEND_H */