Bug Summary

File:statuslookupgen.c
Warning:line 13, column 14
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'uint32_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name statuslookupgen.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -fno-plt -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/buildbot/lwan-worker/clang-analyze/build/src/bin/tools -resource-dir /usr/lib/clang/16 -include /home/buildbot/lwan-worker/clang-analyze/build/lwan-build-config.h -D _FILE_OFFSET_BITS=64 -D _TIME_BITS=64 -I /home/buildbot/lwan-worker/clang-analyze/build/src/lib/missing -I /home/buildbot/lwan-worker/clang-analyze/build -I /usr/include/luajit-2.1 -I /usr/include/valgrind -I /home/buildbot/lwan-worker/clang-analyze/build/src/lib -internal-isystem /usr/lib/clang/16/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/13.2.1/../../../../x86_64-pc-linux-gnu/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-unused-parameter -Wno-override-init -Wno-free-nonheap-object -std=gnu11 -fdebug-compilation-dir=/home/buildbot/lwan-worker/clang-analyze/build/src/bin/tools -ferror-limit 19 -stack-protector 2 -fgnuc-version=4.2.1 -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/buildbot/lwan-worker/clang-analyze/CLANG/2023-11-18-202937-2620130-1 -x c /home/buildbot/lwan-worker/clang-analyze/build/src/bin/tools/statuslookupgen.c
1/* Naïve brute-force perfect hash table generator for HTTP status lookup */
2
3#include <limits.h>
4#include <stdint.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8
9#include "../../lib/lwan-http-status.h"
10
11static inline uint32_t rotate(uint32_t v, int n)
12{
13 return v << (32 - n) | v >> n;
70
←
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'uint32_t'
14}
15
16int main(void)
17{
18 uint32_t max_key = 0;
19 int min_key = INT_MAX2147483647;
20#define COMPARE_MAX(ignore1, key, ignore2, ignore3) \
21 do { \
22 if (key > max_key) \
23 max_key = key; \
24 if (key < min_key) \
25 min_key = key; \
26 } while (0);
27 FOR_EACH_HTTP_STATUS(COMPARE_MAX)COMPARE_MAX(SWITCHING_PROTOCOLS, 101, "Switching protocols", "Protocol is switching over from HTTP"
) COMPARE_MAX(OK, 200, "OK", "Success") COMPARE_MAX(PARTIAL_CONTENT
, 206, "Partial content", "Delivering part of requested resource"
) COMPARE_MAX(MOVED_PERMANENTLY, 301, "Moved permanently", "This content has moved to another place"
) COMPARE_MAX(NOT_MODIFIED, 304, "Not modified", "The content has not changed since previous request"
) COMPARE_MAX(TEMPORARY_REDIRECT, 307, "Temporary Redirect", "This content can be temporarily found at a different location"
) COMPARE_MAX(BAD_REQUEST, 400, "Bad request", "The client has issued a bad request"
) COMPARE_MAX(NOT_AUTHORIZED, 401, "Not authorized", "Client has no authorization to access this resource"
) COMPARE_MAX(FORBIDDEN, 403, "Forbidden", "Access to this resource has been denied"
) COMPARE_MAX(NOT_FOUND, 404, "Not found", "The requested resource could not be found on this server"
) COMPARE_MAX(NOT_ALLOWED, 405, "Not allowed", "The requested method is not allowed by this server"
) COMPARE_MAX(NOT_ACCEPTABLE, 406, "Not acceptable", "No suitable accepted-encoding header provided"
) COMPARE_MAX(TIMEOUT, 408, "Request timeout", "Client did not produce a request within expected timeframe"
) COMPARE_MAX(TOO_LARGE, 413, "Request too large", "The request entity is too large"
) COMPARE_MAX(RANGE_UNSATISFIABLE, 416, "Requested range unsatisfiable"
, "The server can't supply the requested portion of the requested resource"
) COMPARE_MAX(I_AM_A_TEAPOT, 418, "I'm a teapot", "Client requested to brew coffee but device is a teapot"
) COMPARE_MAX(CLIENT_TOO_HIGH, 420, "Client too high", "Client is too high to make a request"
) COMPARE_MAX(INTERNAL_ERROR, 500, "Internal server error", "The server encountered an internal error that couldn't be recovered from"
) COMPARE_MAX(NOT_IMPLEMENTED, 501, "Not implemented", "Server lacks the ability to fulfil the request"
) COMPARE_MAX(UNAVAILABLE, 503, "Service unavailable", "The server is either overloaded or down for maintenance"
) COMPARE_MAX(SERVER_TOO_HIGH, 520, "Server too high", "The server is too high to answer the request"
)
1
Taking true branch
→
2
←
Taking true branch
→
3
←
Loop condition is false. Exiting loop
→
4
←
Taking true branch
→
5
←
Taking false branch
→
6
←
Loop condition is false. Exiting loop
→
7
←
Taking true branch
→
8
←
Taking false branch
→
9
←
Loop condition is false. Exiting loop
→
10
←
Taking true branch
→
11
←
Taking false branch
→
12
←
Loop condition is false. Exiting loop
→
13
←
Taking true branch
→
14
←
Taking false branch
→
15
←
Loop condition is false. Exiting loop
→
16
←
Taking true branch
→
17
←
Taking false branch
→
18
←
Loop condition is false. Exiting loop
→
19
←
Taking true branch
→
20
←
Taking false branch
→
21
←
Loop condition is false. Exiting loop
→
22
←
Taking true branch
→
23
←
Taking false branch
→
24
←
Loop condition is false. Exiting loop
→
25
←
Taking true branch
→
26
←
Taking false branch
→
27
←
Loop condition is false. Exiting loop
→
28
←
Taking true branch
→
29
←
Taking false branch
→
30
←
Loop condition is false. Exiting loop
→
31
←
Taking true branch
→
32
←
Taking false branch
→
33
←
Loop condition is false. Exiting loop
→
34
←
Taking true branch
→
35
←
Taking false branch
→
36
←
Loop condition is false. Exiting loop
→
37
←
Taking true branch
→
38
←
Taking false branch
→
39
←
Loop condition is false. Exiting loop
→
40
←
Taking true branch
→
41
←
Taking false branch
→
42
←
Loop condition is false. Exiting loop
→
43
←
Taking true branch
→
44
←
Taking false branch
→
45
←
Loop condition is false. Exiting loop
→
46
←
Taking true branch
→
47
←
Taking false branch
→
48
←
Loop condition is false. Exiting loop
→
49
←
Taking true branch
→
50
←
Taking false branch
→
51
←
Loop condition is false. Exiting loop
→
52
←
Taking true branch
→
53
←
Taking false branch
→
54
←
Loop condition is false. Exiting loop
→
55
←
Taking true branch
→
56
←
Taking false branch
→
57
←
Loop condition is false. Exiting loop
→
58
←
Taking true branch
→
59
←
Taking false branch
→
60
←
Loop condition is false. Exiting loop
→
61
←
Taking true branch
→
62
←
Taking false branch
→
63
←
Loop condition is false. Exiting loop
→
28#undef COMPARE_MAX
29
30#define SELECT_KEY(ignore1, key, ignore2, ignore3) key,
31 const int keys[] = {FOR_EACH_HTTP_STATUS(SELECT_KEY)SELECT_KEY(SWITCHING_PROTOCOLS, 101, "Switching protocols", "Protocol is switching over from HTTP"
) SELECT_KEY(OK, 200, "OK", "Success") SELECT_KEY(PARTIAL_CONTENT
, 206, "Partial content", "Delivering part of requested resource"
) SELECT_KEY(MOVED_PERMANENTLY, 301, "Moved permanently", "This content has moved to another place"
) SELECT_KEY(NOT_MODIFIED, 304, "Not modified", "The content has not changed since previous request"
) SELECT_KEY(TEMPORARY_REDIRECT, 307, "Temporary Redirect", "This content can be temporarily found at a different location"
) SELECT_KEY(BAD_REQUEST, 400, "Bad request", "The client has issued a bad request"
) SELECT_KEY(NOT_AUTHORIZED, 401, "Not authorized", "Client has no authorization to access this resource"
) SELECT_KEY(FORBIDDEN, 403, "Forbidden", "Access to this resource has been denied"
) SELECT_KEY(NOT_FOUND, 404, "Not found", "The requested resource could not be found on this server"
) SELECT_KEY(NOT_ALLOWED, 405, "Not allowed", "The requested method is not allowed by this server"
) SELECT_KEY(NOT_ACCEPTABLE, 406, "Not acceptable", "No suitable accepted-encoding header provided"
) SELECT_KEY(TIMEOUT, 408, "Request timeout", "Client did not produce a request within expected timeframe"
) SELECT_KEY(TOO_LARGE, 413, "Request too large", "The request entity is too large"
) SELECT_KEY(RANGE_UNSATISFIABLE, 416, "Requested range unsatisfiable"
, "The server can't supply the requested portion of the requested resource"
) SELECT_KEY(I_AM_A_TEAPOT, 418, "I'm a teapot", "Client requested to brew coffee but device is a teapot"
) SELECT_KEY(CLIENT_TOO_HIGH, 420, "Client too high", "Client is too high to make a request"
) SELECT_KEY(INTERNAL_ERROR, 500, "Internal server error", "The server encountered an internal error that couldn't be recovered from"
) SELECT_KEY(NOT_IMPLEMENTED, 501, "Not implemented", "Server lacks the ability to fulfil the request"
) SELECT_KEY(UNAVAILABLE, 503, "Service unavailable", "The server is either overloaded or down for maintenance"
) SELECT_KEY(SERVER_TOO_HIGH, 520, "Server too high", "The server is too high to answer the request"
)};
32#undef SELECT_KEY
33
34#define N_KEYS((int)(sizeof(keys) / sizeof(keys[0]))) ((int)(sizeof(keys) / sizeof(keys[0])))
35
36 int best_rot = INT_MAX2147483647;
37 uint32_t best_mod = 64;
38 uint32_t best_subtract = UINT_MAX(2147483647 *2U +1U);
39
40 if (N_KEYS((int)(sizeof(keys) / sizeof(keys[0]))) >= best_mod) {
64
←
Taking false branch
→
41 fprintf(stderrstderr, "table too large!\n");
42 return 1;
43 }
44
45 for (uint32_t subtract = 0; subtract < max_key; subtract++) {
65
←
Loop condition is true. Entering loop body
→
46 for (int rot = 0; rot < 32; rot++) {
66
←
Loop condition is true. Entering loop body
→
47 for (uint32_t mod = N_KEYS((int)(sizeof(keys) / sizeof(keys[0]))); mod < best_mod; mod++) {
67
←
Loop condition is true. Entering loop body
→
48 uint64_t set = 0;
49 int set_bits = 0;
50
51 for (int key = 0; key < N_KEYS((int)(sizeof(keys) / sizeof(keys[0]))); key++) {
68
←
Loop condition is true. Entering loop body
→
52 uint32_t k = rotate((uint32_t)keys[key] - subtract, rot) % mod;
69
←
Calling 'rotate'
→
53
54 if (set & 1ull<<k)
55 break;
56
57 set |= 1ull<<k;
58 set_bits++;
59 }
60
61 if (set_bits == N_KEYS((int)(sizeof(keys) / sizeof(keys[0]))) && mod < best_mod) {
62 best_rot = rot;
63 best_mod = mod;
64 best_subtract = subtract;
65 }
66 }
67 }
68 }
69
70 if (best_rot == INT_MAX2147483647) {
71 fprintf(stderrstderr, "could not figure out the hash table parameters!\n");
72 return 1;
73 }
74
75 uint64_t set_values = ~0ull;
76 printf("static ALWAYS_INLINE const char *lwan_lookup_http_status_impl(enum lwan_http_status status) {\n");
77 printf(" static const char *table[] = {\n");
78#define PRINT_V(ignored1, key, short_desc, long_desc) do { \
79 uint32_t k = rotate((uint32_t)key - (uint32_t)best_subtract, best_rot) % best_mod; \
80 set_values &= ~(1ull<<k); \
81 printf(" [%d] = \"%d %s\\0%s\",\n", k, key, short_desc, long_desc); \
82 } while(0);
83 FOR_EACH_HTTP_STATUS(PRINT_V)PRINT_V(SWITCHING_PROTOCOLS, 101, "Switching protocols", "Protocol is switching over from HTTP"
) PRINT_V(OK, 200, "OK", "Success") PRINT_V(PARTIAL_CONTENT, 206
, "Partial content", "Delivering part of requested resource")
PRINT_V(MOVED_PERMANENTLY, 301, "Moved permanently", "This content has moved to another place"
) PRINT_V(NOT_MODIFIED, 304, "Not modified", "The content has not changed since previous request"
) PRINT_V(TEMPORARY_REDIRECT, 307, "Temporary Redirect", "This content can be temporarily found at a different location"
) PRINT_V(BAD_REQUEST, 400, "Bad request", "The client has issued a bad request"
) PRINT_V(NOT_AUTHORIZED, 401, "Not authorized", "Client has no authorization to access this resource"
) PRINT_V(FORBIDDEN, 403, "Forbidden", "Access to this resource has been denied"
) PRINT_V(NOT_FOUND, 404, "Not found", "The requested resource could not be found on this server"
) PRINT_V(NOT_ALLOWED, 405, "Not allowed", "The requested method is not allowed by this server"
) PRINT_V(NOT_ACCEPTABLE, 406, "Not acceptable", "No suitable accepted-encoding header provided"
) PRINT_V(TIMEOUT, 408, "Request timeout", "Client did not produce a request within expected timeframe"
) PRINT_V(TOO_LARGE, 413, "Request too large", "The request entity is too large"
) PRINT_V(RANGE_UNSATISFIABLE, 416, "Requested range unsatisfiable"
, "The server can't supply the requested portion of the requested resource"
) PRINT_V(I_AM_A_TEAPOT, 418, "I'm a teapot", "Client requested to brew coffee but device is a teapot"
) PRINT_V(CLIENT_TOO_HIGH, 420, "Client too high", "Client is too high to make a request"
) PRINT_V(INTERNAL_ERROR, 500, "Internal server error", "The server encountered an internal error that couldn't be recovered from"
) PRINT_V(NOT_IMPLEMENTED, 501, "Not implemented", "Server lacks the ability to fulfil the request"
) PRINT_V(UNAVAILABLE, 503, "Service unavailable", "The server is either overloaded or down for maintenance"
) PRINT_V(SERVER_TOO_HIGH, 520, "Server too high", "The server is too high to answer the request"
)
84#undef PRINT_V
85
86 for (uint32_t i = 0; i < best_mod; i++) {
87 if (set_values & 1ull<<i)
88 printf(" [%d] = \"999 Invalid\\0Invalid HTTP status code requested\",\n", i);
89 }
90
91 printf(" };\n");
92
93 printf("\n");
94 printf(" const uint32_t k = (uint32_t)status - %d;\n", best_subtract);
95 printf(" return table[((k << %d) | (k >> %d)) %% %d];\n", 32 - best_rot, best_rot, best_mod);
96
97 printf("}\n");
98
99}