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