Bug Summary

File:home/bhubbard/working/src/ceph/src/isa-l/igzip/igzip_base.c
Warning:line 84, column 26
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_base.c

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

/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);
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'
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)
26
←
Taking false branch
→
97 dist = 0;
98 assert(dist >= 1)((void) (0));
99 assert(dist <= 32768)((void) (0));
100 if (dist <= IGZIP_DIST_TABLE_SIZE) {
27
←
Assuming 'dist' is > IGZIP_DIST_TABLE_SIZE
→
28
←
Taking false branch
→
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);
29
←
Calling 'compute_dist_code'
→
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);
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) {
149 *code = dist - 1;
150 *extra_bits = 0;
151 } else {
152 compute_dist_icf_code(dist, code, extra_bits);
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}