Bug Summary

File:home/bhubbard/working/src/ceph/src/isa-l/igzip/igzip_icf_base.c
Warning:line 138, column 27
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'int'

Annotated Source Code

[?] Use j/k keys for keyboard navigation

/home/bhubbard/working/src/ceph/src/isa-l/igzip/igzip_icf_base.c

→
1#include <stdint.h>
2#include "igzip_lib.h"
3#include "huffman.h"
4#include "huff_codes.h"
5#include "encode_df.h"
6#include "igzip_level_buf_structs.h"
7
8static inline void write_deflate_icf(struct deflate_icf *icf, uint32_t lit_len,
9 uint32_t lit_dist, uint32_t extra_bits)
10{
11 icf->lit_len = lit_len;
12 icf->lit_dist = lit_dist;
13 icf->dist_extra = extra_bits;
14}
15
16static inline void update_state(struct isal_zstream *stream, uint8_t * start_in,
17 uint8_t * next_in, uint8_t * end_in,
18 struct deflate_icf *start_out, struct deflate_icf *next_out,
19 struct deflate_icf *end_out)
20{
21 stream->next_in = next_in;
22 stream->total_in += next_in - start_in;
23 stream->avail_in = end_in - next_in;
24
25 ((struct level_2_buf *)stream->level_buf)->icf_buf_next = next_out;
26 ((struct level_2_buf *)stream->level_buf)->icf_buf_avail_out = end_out - next_out;
27}
28
29void isal_deflate_icf_body_base(struct isal_zstream *stream)
30{
31 uint32_t literal, hash;
32 uint8_t *start_in, *next_in, *end_in, *end, *next_hash;
33 struct deflate_icf *start_out, *next_out, *end_out;
34 uint16_t match_length;
35 uint32_t dist;
36 uint32_t code, code2, extra_bits;
37 struct isal_zstate *state = &stream->internal_state;
38 uint16_t *last_seen = state->head;
39
40 if (stream->avail_in == 0) {
41 if (stream->end_of_stream || stream->flush != NO_FLUSH0)
42 state->state = ZSTATE_FLUSH_READ_BUFFER;
43 return;
44 }
45
46 start_in = stream->next_in;
47 end_in = start_in + stream->avail_in;
48 next_in = start_in;
49
50 start_out = ((struct level_2_buf *)stream->level_buf)->icf_buf_next;
51 end_out =
52 start_out + ((struct level_2_buf *)stream->level_buf)->icf_buf_avail_out /
53 sizeof(struct deflate_icf);
54 next_out = start_out;
55
56 while (next_in + ISAL_LOOK_AHEAD(18 * 16) < end_in) {
57
58 if (next_out >= end_out) {
59 state->state = ZSTATE_CREATE_HDR;
60 update_state(stream, start_in, next_in, end_in, start_out, next_out,
61 end_out);
62 return;
63 }
64
65 literal = *(uint32_t *) next_in;
66 hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1);
67 dist = (next_in - state->file_start - last_seen[hash]) & 0xFFFF;
68 last_seen[hash] = (uint64_t) (next_in - state->file_start);
69
70 /* The -1 are to handle the case when dist = 0 */
71 if (dist - 1 < IGZIP_HIST_SIZE(32*1024) - 1) {
72 assert(dist != 0)((void) (0));
73
74 match_length = compare258(next_in - dist, next_in, 258);
75
76 if (match_length >= SHORTEST_MATCH4) {
77 next_hash = next_in;
78#ifdef ISAL_LIMIT_HASH_UPDATE
79 end = next_hash + 3;
80#else
81 end = next_hash + match_length;
82#endif
83 next_hash++;
84
85 for (; next_hash < end; next_hash++) {
86 literal = *(uint32_t *) next_hash;
87 hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1);
88 last_seen[hash] =
89 (uint64_t) (next_hash - state->file_start);
90 }
91
92 get_len_icf_code(match_length, &code);
93 get_dist_icf_code(dist, &code2, &extra_bits);
94
95 state->hist.ll_hist[code]++;
96 state->hist.d_hist[code2]++;
97
98 write_deflate_icf(next_out, code, code2, extra_bits);
99 next_out++;
100 next_in += match_length;
101
102 continue;
103 }
104 }
105
106 get_lit_icf_code(literal & 0xFF, &code);
107 state->hist.ll_hist[code]++;
108 write_deflate_icf(next_out, code, NULL_DIST_SYM30, 0);
109 next_out++;
110 next_in++;
111 }
112
113 update_state(stream, start_in, next_in, end_in, start_out, next_out, end_out);
114
115 assert(stream->avail_in <= ISAL_LOOK_AHEAD)((void) (0));
116 if (stream->end_of_stream || stream->flush != NO_FLUSH0)
117 state->state = ZSTATE_FLUSH_READ_BUFFER;
118
119 return;
120
121}
122
123void isal_deflate_icf_finish_base(struct isal_zstream *stream)
124{
125 uint32_t literal = 0, hash;
126 uint8_t *start_in, *next_in, *end_in, *end, *next_hash;
127 struct deflate_icf *start_out, *next_out, *end_out;
128 uint16_t match_length;
129 uint32_t dist;
130 uint32_t code, code2, extra_bits;
131 struct isal_zstate *state = &stream->internal_state;
132 uint16_t *last_seen = state->head;
133
134 start_in = stream->next_in;
135 end_in = start_in + stream->avail_in;
136 next_in = start_in;
137
138 start_out = ((struct level_2_buf *)stream->level_buf)->icf_buf_next;
139 end_out = start_out + ((struct level_2_buf *)stream->level_buf)->icf_buf_avail_out /
140 sizeof(struct deflate_icf);
141 next_out = start_out;
142
143 while (next_in + 3 < end_in) {
1
Assuming the condition is true
→
2
←
Loop condition is true. Entering loop body
→
6
←
Assuming the condition is true
→
7
←
Loop condition is true. Entering loop body
→
12
←
Assuming the condition is true
→
13
←
Loop condition is true. Entering loop body
→
18
←
Assuming the condition is true
→
19
←
Loop condition is true. Entering loop body
→
144 if (next_out >= end_out) {
3
←
Taking false branch
→
8
←
Assuming 'next_out' is < 'end_out'
→
9
←
Taking false branch
→
14
←
Assuming 'next_out' is < 'end_out'
→
15
←
Taking false branch
→
20
←
Assuming 'next_out' is < 'end_out'
→
21
←
Taking false branch
→
145 state->state = ZSTATE_CREATE_HDR;
146 update_state(stream, start_in, next_in, end_in, start_out, next_out,
147 end_out);
148 return;
149 }
150
151 literal = *(uint32_t *) next_in;
152 hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1);
153 dist = (next_in - state->file_start - last_seen[hash]) & 0xFFFF;
154 last_seen[hash] = (uint64_t) (next_in - state->file_start);
155
156 if (dist - 1 < IGZIP_HIST_SIZE(32*1024) - 1) { /* The -1 are to handle the case when dist = 0 */
4
←
Assuming the condition is false
→
5
←
Taking false branch
→
10
←
Assuming the condition is false
→
11
←
Taking false branch
→
16
←
Assuming the condition is false
→
17
←
Taking false branch
→
22
←
Assuming the condition is true
→
23
←
Taking true branch
→
157 match_length = compare258(next_in - dist, next_in, end_in - next_in);
158
159 if (match_length >= SHORTEST_MATCH4) {
24
←
Taking true branch
→
160 next_hash = next_in;
161#ifdef ISAL_LIMIT_HASH_UPDATE
162 end = next_hash + 3;
163#else
164 end = next_hash + match_length;
165#endif
166 next_hash++;
167
168 for (; next_hash < end - 3; next_hash++) {
25
←
Loop condition is false. Execution continues on line 175
→
169 literal = *(uint32_t *) next_hash;
170 hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1);
171 last_seen[hash] =
172 (uint64_t) (next_hash - state->file_start);
173 }
174
175 get_len_icf_code(match_length, &code);
176 get_dist_icf_code(dist, &code2, &extra_bits);
26
←
Calling 'get_dist_icf_code'
→
177
178 state->hist.ll_hist[code]++;
179 state->hist.d_hist[code2]++;
180
181 write_deflate_icf(next_out, code, code2, extra_bits);
182
183 next_out++;
184 next_in += match_length;
185
186 continue;
187 }
188 }
189
190 get_lit_icf_code(literal & 0xFF, &code);
191 state->hist.ll_hist[code]++;
192 write_deflate_icf(next_out, code, NULL_DIST_SYM30, 0);
193 next_out++;
194 next_in++;
195
196 }
197
198 while (next_in < end_in) {
199 if (next_out >= end_out) {
200 state->state = ZSTATE_CREATE_HDR;
201 update_state(stream, start_in, next_in, end_in, start_out, next_out,
202 end_out);
203 return;
204 }
205
206 literal = *next_in;
207 get_lit_icf_code(literal & 0xFF, &code);
208 state->hist.ll_hist[code]++;
209 write_deflate_icf(next_out, code, NULL_DIST_SYM30, 0);
210 next_out++;
211 next_in++;
212
213 }
214
215 if (next_in == end_in) {
216 if (stream->end_of_stream || stream->flush != NO_FLUSH0)
217 state->state = ZSTATE_CREATE_HDR;
218 }
219
220 update_state(stream, start_in, next_in, end_in, start_out, next_out, end_out);
221
222 return;
223}
←

/home/bhubbard/working/src/ceph/src/isa-l/igzip/huffman.h

1/**********************************************************************
2 Copyright(c) 2011-2016 Intel Corporation All rights reserved.
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in
11 the documentation and/or other materials provided with the
12 distribution.
13 * Neither the name of Intel Corporation nor the names of its
14 contributors may be used to endorse or promote products derived
15 from this software without specific prior written permission.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28**********************************************************************/
29
30#include <stdint.h>
31#include <stdlib.h>
32#include <assert.h>
33#include "igzip_lib.h"
34
35#ifdef _MSC_VER
36# include <intrin.h>
37# define inline __inline
38#else
39# include <x86intrin.h>
40#endif
41
42static inline uint32_t bsr(uint32_t val)
43{
44 uint32_t msb;
45#ifdef __LZCNT__
46 msb = 16 - __lzcnt16(val);
47#else
48 for(msb = 0; val > 0; val >>= 1)
49 msb++;
50#endif
51 return msb;
52}
53
54static inline uint32_t tzcnt(uint64_t val)
55{
56 uint32_t cnt;
57
58#ifdef __x86_64__1
59
60 cnt = __builtin_ctzll(val) / 8;//__tzcnt_u64(val);
61
62#else
63 for(cnt = 8; val > 0; val <<= 8)
64 cnt -= 1;
65#endif
66 return cnt;
67}
68
69static void compute_dist_code(struct isal_hufftables *hufftables, uint16_t dist, uint64_t *p_code, uint64_t *p_len)
70{
71 assert(dist > IGZIP_DIST_TABLE_SIZE)((void) (0));
72
73 dist -= 1;
74 uint32_t msb;
75 uint32_t num_extra_bits;
76 uint32_t extra_bits;
77 uint32_t sym;
78 uint32_t len;
79 uint32_t code;
80
81 msb = bsr(dist);
82 assert(msb >= 1)((void) (0));
83 num_extra_bits = msb - 2;
84 extra_bits = dist & ((1 << num_extra_bits) - 1);
85 dist >>= num_extra_bits;
86 sym = dist + 2 * num_extra_bits;
87 assert(sym < 30)((void) (0));
88 code = hufftables->dcodes[sym - IGZIP_DECODE_OFFSET];
89 len = hufftables->dcodes_sizes[sym - IGZIP_DECODE_OFFSET];
90 *p_code = code | (extra_bits << len);
91 *p_len = len + num_extra_bits;
92}
93
94static inline void get_dist_code(struct isal_hufftables *hufftables, uint32_t dist, uint64_t *code, uint64_t *len)
95{
96 if (dist < 1)
97 dist = 0;
98 assert(dist >= 1)((void) (0));
99 assert(dist <= 32768)((void) (0));
100 if (dist <= IGZIP_DIST_TABLE_SIZE) {
101 uint64_t code_len;
102 code_len = hufftables->dist_table[dist - 1];
103 *code = code_len >> 5;
104 *len = code_len & 0x1F;
105 } else {
106 compute_dist_code(hufftables, dist, code, len);
107 }
108}
109
110static inline void get_len_code(struct isal_hufftables *hufftables, uint32_t length, uint64_t *code, uint64_t *len)
111{
112 assert(length >= 3)((void) (0));
113 assert(length <= 258)((void) (0));
114
115 uint64_t code_len;
116 code_len = hufftables->len_table[length - 3];
117 *code = code_len >> 5;
118 *len = code_len & 0x1F;
119}
120
121static inline void get_lit_code(struct isal_hufftables *hufftables, uint32_t lit, uint64_t *code, uint64_t *len)
122{
123 assert(lit <= 256)((void) (0));
124
125 *code = hufftables->lit_table[lit];
126 *len = hufftables->lit_table_sizes[lit];
127}
128
129static void compute_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits)
130{
131 uint32_t msb;
132 uint32_t num_extra_bits;
133
134 dist -= 1;
135 msb = bsr(dist);
136 assert(msb >= 1)((void) (0));
137 num_extra_bits = msb - 2;
138 *extra_bits = dist & ((1 << num_extra_bits) - 1);
30
←
The result of the left shift is undefined due to shifting by '4294967295', which is greater or equal to the width of type 'int'
139 dist >>= num_extra_bits;
140 *code = dist + 2 * num_extra_bits;
141 assert(*code < 30)((void) (0));
142}
143
144static inline void get_dist_icf_code(uint32_t dist, uint32_t *code, uint32_t *extra_bits)
145{
146 assert(dist >= 1)((void) (0));
147 assert(dist <= 32768)((void) (0));
148 if (dist <= 2) {
27
←
Assuming 'dist' is > 2
→
28
←
Taking false branch
→
149 *code = dist - 1;
150 *extra_bits = 0;
151 } else {
152 compute_dist_icf_code(dist, code, extra_bits);
29
←
Calling 'compute_dist_icf_code'
→
153 }
154}
155
156static inline void get_len_icf_code(uint32_t length, uint32_t *code)
157{
158 assert(length >= 3)((void) (0));
159 assert(length <= 258)((void) (0));
160
161 *code = length + 254;
162}
163
164static inline void get_lit_icf_code(uint32_t lit, uint32_t *code)
165{
166 assert(lit <= 256)((void) (0));
167
168 *code = lit;
169}
170
171/**
172 * @brief Returns a hash of the first 3 bytes of input data.
173 */
174static inline uint32_t compute_hash(uint32_t data)
175{
176#ifdef __SSE4_2__
177
178 return _mm_crc32_u32(0, data);
179
180#else
181 /* Use multiplication to create a hash, 0xBDD06057 is a prime number */
182 return ((uint64_t)data * 0xB2D06057) >> 16;
183
184#endif /* __SSE4_2__ */
185}
186
187
188/**
189 * @brief Returns how long str1 and str2 have the same symbols.
190 * @param str1: First input string.
191 * @param str2: Second input string.
192 * @param max_length: length of the smaller string.
193 */
194static inline int compare258(uint8_t * str1, uint8_t * str2, uint32_t max_length)
195{
196 uint32_t count;
197 uint64_t test;
198 uint64_t loop_length;
199
200 if(max_length > 258)
201 max_length = 258;
202
203 loop_length = max_length & ~0x7;
204
205 for(count = 0; count < loop_length; count += 8){
206 test = *(uint64_t *) str1;
207 test ^= *(uint64_t *) str2;
208 if(test != 0)
209 return count + tzcnt(test);
210 str1 += 8;
211 str2 += 8;
212 }
213
214 switch(max_length % 8){
215
216 case 7:
217 if(*str1++ != *str2++)
218 return count;
219 count++;
220 case 6:
221 if(*str1++ != *str2++)
222 return count;
223 count++;
224 case 5:
225 if(*str1++ != *str2++)
226 return count;
227 count++;
228 case 4:
229 if(*str1++ != *str2++)
230 return count;
231 count++;
232 case 3:
233 if(*str1++ != *str2++)
234 return count;
235 count++;
236 case 2:
237 if(*str1++ != *str2++)
238 return count;
239 count++;
240 case 1:
241 if(*str1 != *str2)
242 return count;
243 count++;
244 }
245
246 return count;
247}