858cb9a3b1f791edccbb6f2663f71fc8a3eb3983
[wimlib] / include / wimlib / lz_extend.h
1 /*
2  * lz_extend.h - fast match extension for Lempel-Ziv matchfinding
3  *
4  * The following copying information applies to this specific source code file:
5  *
6  * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
7  *
8  * To the extent possible under law, the author(s) have dedicated all copyright
9  * and related and neighboring rights to this software to the public domain
10  * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
11  * Dedication (the "CC0").
12  *
13  * This software is distributed in the hope that it will be useful, but WITHOUT
14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15  * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
16  *
17  * You should have received a copy of the CC0 along with this software; if not
18  * see <http://creativecommons.org/publicdomain/zero/1.0/>.
19  */
20
21 #ifndef _WIMLIB_LZ_EXTEND_H
22 #define _WIMLIB_LZ_EXTEND_H
23
24 #include "wimlib/bitops.h"
25 #include "wimlib/unaligned.h"
26
27 /* Return the number of bytes at @matchptr that match the bytes at @strptr, up
28  * to a maximum of @max_len.  Initially, @start_len bytes are matched.  */
29 static inline u32
30 lz_extend(const u8 * const strptr, const u8 * const matchptr,
31           const u32 start_len, const u32 max_len)
32 {
33         u32 len = start_len;
34         machine_word_t v_word;
35
36         if (UNALIGNED_ACCESS_IS_FAST) {
37
38                 if (likely(max_len - len >= 4 * WORDSIZE)) {
39
40                 #define COMPARE_WORD_STEP                                       \
41                         v_word = load_word_unaligned(&matchptr[len]) ^          \
42                                  load_word_unaligned(&strptr[len]);             \
43                         if (v_word != 0)                                        \
44                                 goto word_differs;                              \
45                         len += WORDSIZE;                                        \
46
47                         COMPARE_WORD_STEP
48                         COMPARE_WORD_STEP
49                         COMPARE_WORD_STEP
50                         COMPARE_WORD_STEP
51                 #undef COMPARE_WORD_STEP
52                 }
53
54                 while (len + WORDSIZE <= max_len) {
55                         v_word = load_word_unaligned(&matchptr[len]) ^
56                                  load_word_unaligned(&strptr[len]);
57                         if (v_word != 0)
58                                 goto word_differs;
59                         len += WORDSIZE;
60                 }
61         }
62
63         while (len < max_len && matchptr[len] == strptr[len])
64                 len++;
65         return len;
66
67 word_differs:
68         if (CPU_IS_LITTLE_ENDIAN)
69                 len += (ffsw(v_word) >> 3);
70         else
71                 len += (8 * WORDSIZE - 1 - flsw(v_word)) >> 3;
72         return len;
73 }
74
75 #endif /* _WIMLIB_LZ_EXTEND_H */