/src/libdeflate/lib/x86/find_min_cost_path.h
Line | Count | Source |
1 | | /* |
2 | | * x86/find_min_cost_path.h - AVX2 implementation of deflate_min_packed_cost |
3 | | * |
4 | | * Copyright 2026 Google LLC |
5 | | * |
6 | | * Permission is hereby granted, free of charge, to any person |
7 | | * obtaining a copy of this software and associated documentation |
8 | | * files (the "Software"), to deal in the Software without |
9 | | * restriction, including without limitation the rights to use, |
10 | | * copy, modify, merge, publish, distribute, sublicense, and/or sell |
11 | | * copies of the Software, and to permit persons to whom the |
12 | | * Software is furnished to do so, subject to the following |
13 | | * conditions: |
14 | | * |
15 | | * The above copyright notice and this permission notice shall be |
16 | | * included in all copies or substantial portions of the Software. |
17 | | * |
18 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
19 | | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
20 | | * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
21 | | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
22 | | * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
23 | | * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
24 | | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
25 | | * OTHER DEALINGS IN THE SOFTWARE. |
26 | | */ |
27 | | |
28 | | #ifndef LIB_X86_FIND_MIN_COST_PATH_H |
29 | | #define LIB_X86_FIND_MIN_COST_PATH_H |
30 | | |
31 | | #include "cpu_features.h" |
32 | | |
33 | | #if defined(__GNUC__) || defined(__clang__) || defined(_MSC_VER) |
34 | | |
35 | | #define ATTRIBUTES _target_attribute("avx2") |
36 | | |
37 | | /* |
38 | | * Return the minimum of '(length_costs[len] + cost_to_end[len]) mod 2^32' over |
39 | | * 'start_len <= len <= max_len', assuming 'start_len <= max_len'. |
40 | | * |
41 | | * This is used to find the best length to choose for a match that has multiple |
42 | | * lengths available. For details, see find_min_cost_path_template.h. |
43 | | * |
44 | | * This implementation processes 8 lengths at a time using AVX2, and it can read |
45 | | * up to 'length_costs[max_len + 7]' and 'cost_to_end[max_len + 7]'. |
46 | | */ |
47 | | static forceinline ATTRIBUTES u32 |
48 | | deflate_min_packed_cost_avx2(const u32 *length_costs, const u32 *cost_to_end, |
49 | | const size_t start_len, const size_t max_len) |
50 | 0 | { |
51 | 0 | size_t len = start_len; |
52 | | /* Aligned to avoid a cacheline split */ |
53 | 0 | static const u32 _aligned_attribute(64) tail_masks[15] = { |
54 | 0 | 0, 0, 0, 0, 0, 0, 0, 0, ~0U, ~0U, ~0U, ~0U, ~0U, ~0U, ~0U, |
55 | 0 | }; |
56 | 0 | __m256i v_best, v_cost; |
57 | 0 | __m128i best128; |
58 | |
|
59 | 0 | STATIC_ASSERT(COST_SIMD_PADDING >= 7); |
60 | | |
61 | | /* |
62 | | * Compute the packed (cost, len) values for the first 8 lengths. If |
63 | | * fewer than 8 lengths are being considered, this loads entries past |
64 | | * max_len; that's safe because cost_to_end and length_costs have 7 |
65 | | * padding entries at the end, and the extra lanes are masked out below. |
66 | | */ |
67 | 0 | v_best = _mm256_add_epi32( |
68 | 0 | _mm256_loadu_si256((const __m256i *)&length_costs[len]), |
69 | 0 | _mm256_loadu_si256((const __m256i *)&cost_to_end[len])); |
70 | 0 | if (likely(len + 7 >= max_len)) { |
71 | | /* |
72 | | * <= 8 lengths: set the lanes past max_len to all 1s so that |
73 | | * they won't be chosen as the minimum. |
74 | | */ |
75 | 0 | v_best = _mm256_or_si256( |
76 | 0 | v_best, |
77 | 0 | _mm256_loadu_si256((const __m256i *)&tail_masks[len + 7 - max_len])); |
78 | 0 | } else { |
79 | | /* |
80 | | * > 8 lengths: process full vectors of 8, then use an |
81 | | * overlapping vector ending at max_len for the last 1..8. |
82 | | */ |
83 | 0 | len += 8; |
84 | 0 | while (len + 7 < max_len) { |
85 | 0 | v_cost = _mm256_add_epi32( |
86 | 0 | _mm256_loadu_si256((const __m256i *)&length_costs[len]), |
87 | 0 | _mm256_loadu_si256((const __m256i *)&cost_to_end[len])); |
88 | 0 | v_best = _mm256_min_epu32(v_cost, v_best); |
89 | 0 | len += 8; |
90 | 0 | } |
91 | 0 | len = max_len - 7; |
92 | 0 | v_cost = _mm256_add_epi32( |
93 | 0 | _mm256_loadu_si256((const __m256i *)&length_costs[len]), |
94 | 0 | _mm256_loadu_si256((const __m256i *)&cost_to_end[len])); |
95 | 0 | v_best = _mm256_min_epu32(v_cost, v_best); |
96 | 0 | } |
97 | | /* Return the minimum of the 8 lanes of v_best. */ |
98 | 0 | best128 = _mm_min_epu32(_mm256_castsi256_si128(v_best), |
99 | 0 | _mm256_extracti128_si256(v_best, 1)); |
100 | 0 | best128 = _mm_min_epu32(best128, _mm_shuffle_epi32(best128, 0x31)); |
101 | 0 | best128 = _mm_min_epu32(best128, _mm_shuffle_epi32(best128, 0x02)); |
102 | 0 | return _mm_cvtsi128_si32(best128); |
103 | 0 | } |
104 | 0 | #define deflate_min_packed_cost_simd deflate_min_packed_cost_avx2 |
105 | 0 | #define have_min_packed_cost_simd() HAVE_AVX2(get_x86_cpu_features()) |
106 | | |
107 | | #endif /* defined(__GNUC__) || defined(__clang__) || defined(_MSC_VER) */ |
108 | | |
109 | | #endif /* LIB_X86_FIND_MIN_COST_PATH_H */ |