http_method_parse.c (27242B)
1 /* SPDX-License-Identifier: LGPL-2.1-or-later OR (GPL-2.0-or-later WITH eCos-exception-2.0) */ 2 /* 3 This file is part of GNU libmicrohttpd. 4 Copyright (C) 2026 Evgeny Grin (Karlson2k) 5 6 GNU libmicrohttpd is free software; you can redistribute it and/or 7 modify it under the terms of the GNU Lesser General Public 8 License as published by the Free Software Foundation; either 9 version 2.1 of the License, or (at your option) any later version. 10 11 GNU libmicrohttpd is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 Alternatively, you can redistribute GNU libmicrohttpd and/or 17 modify it under the terms of the GNU General Public License as 18 published by the Free Software Foundation; either version 2 of 19 the License, or (at your option) any later version, together 20 with the eCos exception, as follows: 21 22 As a special exception, if other files instantiate templates or 23 use macros or inline functions from this file, or you compile this 24 file and link it with other works to produce a work based on this 25 file, this file does not by itself cause the resulting work to be 26 covered by the GNU General Public License. However the source code 27 for this file must still be made available in accordance with 28 section (3) of the GNU General Public License v2. 29 30 This exception does not invalidate any other reasons why a work 31 based on this file might be covered by the GNU General Public 32 License. 33 34 You should have received copies of the GNU Lesser General Public 35 License and the GNU General Public License along with this library; 36 if not, see <https://www.gnu.org/licenses/>. 37 */ 38 39 /** 40 * @file src/mhd2/http_method_parse.c 41 * @brief The implementation of the HTTP method string parsing function 42 * @author Karlson2k (Evgeny Grin) 43 * 44 * Identification of the standard HTTP method in a request. 45 * This is done for every request, so the code is optimised for speed. The file 46 * has three versions of the function: for 64-bit platforms and two for 32-bit 47 * platforms (fast and compact). One of them is selected at build time. 48 */ 49 50 #include "mhd_sys_options.h" 51 52 #include "mhd_assert.h" 53 54 #include "sys_base_types.h" 55 56 #if defined(_MSC_FULL_VER) && !defined(__clang__) 57 # include <string.h> 58 /* Request intrinsic memcpy() for the data loads: otherwise MSVC /O1 calls 59 the library function. This must precede the inline definitions in 60 mhd_bithelpers.h. */ 61 # pragma intrinsic(memcpy) 62 #endif 63 64 #include "mhd_byteorder.h" 65 #include "mhd_bithelpers.h" 66 #include "mhd_constexpr.h" 67 #include "mhd_predict.h" 68 69 #if defined(MHD_UNIT_TESTING) && defined(mhd_H_M_TEST_UNKNOWN_ORDER) 70 /* Exercise the lookup's unknown-byte-order path. Only the lookup's choice 71 of representation is changed; the load helpers retain the host settings. */ 72 # undef mhd_BYTE_ORDER 73 #endif 74 75 #if defined(mhd_BYTE_ORDER) && (mhd_BYTE_ORDER == mhd_LITTLE_ENDIAN) 76 /* Define nothing: data is loaded and processed as little-endian. 77 On LE hosts data is loaded natively, on non-LE hosts the bytes are 78 swapped on load. */ 79 #elif defined(mhd_BYTE_ORDER) && (mhd_BYTE_ORDER == mhd_BIG_ENDIAN) 80 /** 81 * Process loaded data as big-endian. 82 * When not defined, data is loaded and processed as little-endian. 83 */ 84 # define mhd_H_M_PROCESS_AS_BE 1 85 #endif 86 87 #include "http_method_parse.h" 88 89 /* All standard method names have lengths 3..7, except for "*", which is 90 handled separately. OTHER below denotes mhd_HTTP_METHOD_OTHER, returned 91 for every name outside this set. The bytes of a name are called letters 92 below, whatever their values. 93 94 For names of at least three letters, two groups of four bytes are loaded 95 as 32-bit values: the first bytes (bytes 0..3) and the last bytes (bytes 96 len-3..len: the last three letters and the required terminating zero). 97 For example, OPTIONS gives "OPTI" and "ONS\0"; GET gives "GET\0" for both. 98 At lengths 3..7 the first and the last bytes cover every letter, so 99 comparing both at the correct length verifies the name. Shorter names are 100 handled before these loads, and no padding beyond the terminating zero is 101 needed. */ 102 103 /* Select mhd_H_M_FUNC_FOR_64 (64-bit keys), mhd_H_M_FUNC_FOR_32_FAST or 104 mhd_H_M_FUNC_FOR_32_COMPACT (32-bit values), unless one is predefined. 105 Use 64-bit keys when size_t or uint_fast32_t is at least 64 bits wide. 106 Otherwise MHD_FAVOR_SMALL_CODE selects the compact version; the fast 107 version is the default. */ 108 #if !defined(mhd_H_M_FUNC_FOR_64) && !defined(mhd_H_M_FUNC_FOR_32_FAST) && \ 109 !defined(mhd_H_M_FUNC_FOR_32_COMPACT) 110 # if ((SIZEOF_SIZE_T + 0) >= 8) || ((SIZEOF_UINT_FAST32_T + 0) >= 8) 111 # define mhd_H_M_FUNC_FOR_64 1 112 # elif defined(MHD_FAVOR_SMALL_CODE) 113 # define mhd_H_M_FUNC_FOR_32_COMPACT 1 114 # else 115 # define mhd_H_M_FUNC_FOR_32_FAST 1 116 # endif 117 #endif 118 119 /* Sanity check */ 120 #if defined(mhd_H_M_FUNC_FOR_64) && (mhd_H_M_FUNC_FOR_64 + 0) != 1 121 # error mhd_H_M_FUNC_FOR_64 must be defined as 1 or not defined 122 #endif 123 #if defined(mhd_H_M_FUNC_FOR_32_FAST) && (mhd_H_M_FUNC_FOR_32_FAST + 0) != 1 124 # error mhd_H_M_FUNC_FOR_32_FAST must be defined as 1 or not defined 125 #endif 126 #if defined(mhd_H_M_FUNC_FOR_32_COMPACT) && \ 127 (mhd_H_M_FUNC_FOR_32_COMPACT + 0) != 1 128 # error mhd_H_M_FUNC_FOR_32_COMPACT must be defined as 1 or not defined 129 #endif 130 #if (defined(mhd_H_M_FUNC_FOR_64) + defined(mhd_H_M_FUNC_FOR_32_FAST) \ 131 + defined(mhd_H_M_FUNC_FOR_32_COMPACT)) != 1 132 # error Exactly one mhd_H_M_FUNC_FOR_* macro must be defined 133 #endif 134 135 /* Loads of the name (mhd_H_M_LOAD32()) and table initialisers 136 (mhd_H_M_PACK32()) use the same byte order, so equal bytes give equal 137 32-bit values. At a known byte order this allows native loads without 138 byte swaps; otherwise the helpers assemble bytes into little-endian 32-bit 139 values. A wider uint_least32_t only adds zero bits. */ 140 141 /** 142 * Read four bytes at the possibly unaligned address @p p as a 32-bit value 143 */ 144 #if !defined(mhd_H_M_PROCESS_AS_BE) 145 # define mhd_H_M_LOAD32(p) mhd_GET_32BIT_LE_UNALIGN (p) 146 #else 147 # define mhd_H_M_LOAD32(p) mhd_GET_32BIT_BE_UNALIGN (p) 148 #endif 149 150 /** 151 * Pack bytes @p b0 .. @p b3 in memory order into a 32-bit value, matching 152 * what #mhd_H_M_LOAD32() would return for those bytes. 153 * Expands to an integer constant expression for table initialisers. 154 */ 155 #if !defined(mhd_H_M_PROCESS_AS_BE) 156 # define mhd_H_M_PACK32(b0, b1, b2, b3) \ 157 ((uint_least32_t) ((uint_least32_t) (uint8_t) (b0) \ 158 | ((uint_least32_t) (uint8_t) (b1) << 8u) \ 159 | ((uint_least32_t) (uint8_t) (b2) << 16u) \ 160 | ((uint_least32_t) (uint8_t) (b3) << 24u))) 161 #else 162 # define mhd_H_M_PACK32(b0, b1, b2, b3) \ 163 ((uint_least32_t) (((uint_least32_t) (uint8_t) (b0) << 24u) \ 164 | ((uint_least32_t) (uint8_t) (b1) << 16u) \ 165 | ((uint_least32_t) (uint8_t) (b2) << 8u) \ 166 | (uint_least32_t) (uint8_t) (b3))) 167 #endif 168 169 /** 170 * Encode @p code for storing in a table: XOR with OTHER. 171 * The stored code of OTHER is zero. 172 */ 173 #define mhd_H_M_XOR_CODE(code) ((uint8_t) ((code) ^ mhd_HTTP_METHOD_OTHER)) 174 175 176 /** 177 * Handle lengths outside 3..7; the only standard method here is "*". 178 * @param len the length of the @p mtd name 179 * @param mtd the method name 180 * @return #mhd_HTTP_METHOD_ASTERISK or #mhd_HTTP_METHOD_OTHER 181 */ 182 #define mhd_PARSE_HTTP_METHOD_OUTSIDE_3_7(len, mtd) \ 183 ((mhd_COND_VERY_RARELY ((1u == (len)) && ('*' == (mtd)[0]))) ? \ 184 mhd_HTTP_METHOD_ASTERISK : mhd_HTTP_METHOD_OTHER) 185 186 187 #if defined(mhd_H_M_FUNC_FOR_64) 188 189 /* The 64-bit lookup compares 64-bit keys: the first bytes in the low half and 190 the last bytes in the high half of the key. 191 192 The length selects row = min (len, 8) - 3. Rows 0..4 cover lengths 3..7; 193 row 5 handles longer names and has no standard methods. Each row has two 194 candidate keys, at slots "row" and "5 + row": 195 196 row (length) 0 (3) 1 (4) 2 (5) 3 (6) 4 (7) 5 (above 7) 197 first GET POST TRACE DELETE OPTIONS slot 5 (PUT) 198 second PUT HEAD slot 7 slot 8 CONNECT slot 10 (zero) 199 200 Lengths 5 and 6 each have only one method, so their second candidate slots 201 (7 and 8) hold the stored codes (the codes XORed with OTHER) instead of 202 keys. The stored code indices are "2 * row" and "2 * row + 1" for the 203 first and second candidates. Reusing these slots keeps the keys and the 204 stored codes in one table with a shared base address: it is smaller and 205 keeps related loads close together to favour data-cache locality on the 206 request path. Being both small and fast, this version serves both speed 207 and size builds. 208 209 Row 5 also reuses the PUT key at slot 5 instead of reserving another key 210 slot. 211 Unused candidates and all of row 5 have zero stored codes. Matches 212 against the repurposed code slots or row 5's keys therefore yield OTHER. */ 213 214 /** 215 * Build the key of a method from its first bytes @p b0 .. @p b3 and its last 216 * bytes: the last three letters @p e0 .. @p e2 and the terminating zero. 217 */ 218 # define mhd_H_M_KEY64(b0, b1, b2, b3, e0, e1, e2) \ 219 (((uint_least64_t) mhd_H_M_PACK32 ((b0), (b1), (b2), (b3))) \ 220 | (((uint_least64_t) mhd_H_M_PACK32 ((e0), (e1), (e2), 0u)) \ 221 << 32u)) 222 223 /** 224 * Defined if the stored codes can be read directly from slots 7 and 8. 225 * Otherwise each stored code is extracted numerically from its slot value. 226 * 227 * Direct access requires a known byte order and no gap in memory between the 228 * stored codes of slots 7 and 8. A wider uint_least64_t would introduce such 229 * a gap. 230 * For little-endian values the packing is the same for either access method, 231 * so #mhd_H_M_CODE64() can check the slot width with sizeof(). Big-endian 232 * byte packing also depends on the slot width, which must therefore be known 233 * before choosing the packing. Other or unknown byte orders use numerical 234 * extraction throughout. 235 */ 236 # if defined(mhd_BYTE_ORDER) && (mhd_BYTE_ORDER == mhd_BIG_ENDIAN) && \ 237 defined(SIZEOF_UINT_LEAST64_T) && (8 == SIZEOF_UINT_LEAST64_T) 238 # define mhd_H_M_CODES_DIRECT 1 239 # elif defined(mhd_BYTE_ORDER) && (mhd_BYTE_ORDER == mhd_LITTLE_ENDIAN) 240 # define mhd_H_M_CODES_DIRECT 1 241 # endif 242 243 /** 244 * Pack the stored codes @p b0 .. @p b7 into a slot value. 245 * With #mhd_H_M_CODES_DIRECT, @p b0 is the first byte in memory; otherwise it 246 * is the least significant byte, as expected by #mhd_H_M_CODE64_BY_VAL(). 247 */ 248 # if defined(mhd_H_M_CODES_DIRECT) && (mhd_BYTE_ORDER == mhd_BIG_ENDIAN) 249 # define mhd_H_M_PACK64(b0, b1, b2, b3, b4, b5, b6, b7) \ 250 (((uint_least64_t) (b0) << 56u) | ((uint_least64_t) (b1) << 48u) \ 251 | ((uint_least64_t) (b2) << 40u) | ((uint_least64_t) (b3) << 32u) \ 252 | ((uint_least64_t) (b4) << 24u) | ((uint_least64_t) (b5) << 16u) \ 253 | ((uint_least64_t) (b6) << 8u) | (uint_least64_t) (b7)) 254 # else 255 # define mhd_H_M_PACK64(b0, b1, b2, b3, b4, b5, b6, b7) \ 256 ((uint_least64_t) (b0) | ((uint_least64_t) (b1) << 8u) \ 257 | ((uint_least64_t) (b2) << 16u) | ((uint_least64_t) (b3) << 24u) \ 258 | ((uint_least64_t) (b4) << 32u) | ((uint_least64_t) (b5) << 40u) \ 259 | ((uint_least64_t) (b6) << 48u) | ((uint_least64_t) (b7) << 56u)) 260 # endif 261 262 /** 263 * Method keys and stored codes, arranged as described above. 264 */ 265 mhd_constexpr uint_least64_t mhd_h_m_tbl_64[11] = { 266 mhd_H_M_KEY64 ('G', 'E', 'T', 0u, 'G', 'E', 'T'), /* Slot 0, row 0 */ 267 mhd_H_M_KEY64 ('P', 'O', 'S', 'T', 'O', 'S', 'T'), /* Slot 1, row 1 */ 268 mhd_H_M_KEY64 ('T', 'R', 'A', 'C', 'A', 'C', 'E'), /* Slot 2, row 2 */ 269 mhd_H_M_KEY64 ('D', 'E', 'L', 'E', 'E', 'T', 'E'), /* Slot 3, row 3 */ 270 mhd_H_M_KEY64 ('O', 'P', 'T', 'I', 'O', 'N', 'S'), /* Slot 4, row 4 */ 271 mhd_H_M_KEY64 ('P', 'U', 'T', 0u, 'P', 'U', 'T'), /* Slot 5, rows 0, 5 */ 272 mhd_H_M_KEY64 ('H', 'E', 'A', 'D', 'E', 'A', 'D'), /* Slot 6, row 1 */ 273 /* Slot 7, row 2: no key, the stored codes 0..7 of the rows 0..3 */ 274 mhd_H_M_PACK64 (mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_GET), /* Row 0 */ 275 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_PUT), 276 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_POST), /* Row 1 */ 277 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_HEAD), 278 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_TRACE), /* Row 2 */ 279 0u, 280 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_DELETE), /* Row 3 */ 281 0u), 282 /* Slot 8, row 3: no key, the stored codes 8..11 of the rows 4..5 */ 283 mhd_H_M_PACK64 (mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_OPTIONS), /* Row 4 */ 284 mhd_H_M_XOR_CODE (mhd_HTTP_METHOD_CONNECT), 285 0u, /* Row 5 */ 286 0u, 287 0u, 0u, 0u, 0u), /* Unused */ 288 mhd_H_M_KEY64 ('C', 'O', 'N', 'N', 'E', 'C', 'T'), /* Slot 9, row 4 */ 289 0u /* Slot 10, row 5 */ 290 }; 291 292 /** 293 * Extract the stored code @p i from the value of its slot 294 */ 295 # define mhd_H_M_CODE64_BY_VAL(i) \ 296 ((uint8_t) (mhd_h_m_tbl_64[7u + (i) / 8u] >> (8u * ((i) % 8u)))) 297 298 /** 299 * Read the stored code @p i from slots 7 and 8 300 */ 301 # if defined(mhd_H_M_CODES_DIRECT) 302 # define mhd_H_M_CODE64(i) \ 303 ((uint8_t) ((8u == sizeof(mhd_h_m_tbl_64[0])) ? \ 304 ((const uint8_t *) (mhd_h_m_tbl_64 + 7u))[(i)] : \ 305 mhd_H_M_CODE64_BY_VAL (i))) 306 # else 307 # define mhd_H_M_CODE64(i) mhd_H_M_CODE64_BY_VAL (i) 308 # endif 309 310 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ MHD_FN_PAR_IN_ (2) MHD_FN_PAR_CSTR_ (2) 311 MHD_FN_PURE_ enum mhd_HTTP_Method 312 mhd_parse_http_method (size_t len, 313 const char *mtd) 314 { 315 mhd_assert ('\0' == mtd[len]); 316 /* The required terminating zero makes four-byte loads safe at length 3 */ 317 if (mhd_COND_ALMOST_ALWAYS (3u <= len)) 318 { 319 /* Rows 0..4 cover lengths 3..7. Longer names use row 5, whose stored 320 codes are zero, so they always yield OTHER. */ 321 const size_t row = ((7u < len) ? 8u : len) - 3u; 322 const uint_least32_t first_bytes = mhd_H_M_LOAD32 (mtd); 323 const uint_least32_t last_bytes = mhd_H_M_LOAD32 (mtd + len - 3u); 324 /* The first and the last bytes can overlap. At lengths 3..7 they cover 325 every letter, so the key includes the entire name. */ 326 const uint_least64_t key = 327 ((uint_least64_t)first_bytes) | (((uint_least64_t)last_bytes) << 32u); 328 /* Subtracting an equality result (0 or 1) from unsigned zero gives an 329 all-zero or all-ones mask. The candidate keys differ, so at most one 330 of mask0 and mask1 can be non-zero. */ 331 const unsigned int mask0 = 332 0u - (unsigned int)(mhd_h_m_tbl_64[row] == key); 333 const unsigned int mask1 = 334 0u - (unsigned int)(mhd_h_m_tbl_64[5u + row] == key); 335 336 /* The stored codes are code ^ OTHER. Each mask retains the stored code 337 of its matching candidate and clears it otherwise. With no match the 338 result is OTHER; one match gives OTHER ^ (code ^ OTHER), restoring the 339 code. An unused candidate's stored code is zero, so even a matching 340 key leaves OTHER. */ 341 return (enum mhd_HTTP_Method)(mhd_HTTP_METHOD_OTHER 342 ^ (mhd_H_M_CODE64 (2u * row) & mask0) 343 ^ (mhd_H_M_CODE64 (2u * row + 1u) & mask1)); 344 } 345 return mhd_PARSE_HTTP_METHOD_OUTSIDE_3_7 (len, mtd); 346 } 347 348 349 #else /* mhd_H_M_FUNC_FOR_32_FAST || mhd_H_M_FUNC_FOR_32_COMPACT */ 350 351 /* The 32-bit versions avoid 64-bit key construction and comparison by keeping 352 the first bytes and the last bytes as separate 32-bit values. The length 353 and bits of the first letter select one candidate, so only that record 354 needs to be checked. 355 356 The last bytes contain the last three letters and the terminating zero. 357 The caller guarantees that zero, so its value is known and need not be 358 stored in the table. A record uses this byte for the stored code instead: 359 360 last bytes of the name: [ letter ][ letter ][ letter ][ zero ] 361 last bytes of a record: [ letter ][ letter ][ letter ][ code ] 362 363 The diagram follows the byte order of the name. mhd_H_M_LAST_LETTERS_MASK 364 excludes the stored code from comparison; mhd_H_M_NUL_BIT locates it for 365 extraction in the chosen byte order. Keeping the stored code in the same 366 record avoids an extra field or a separate code-table lookup. */ 367 368 /** 369 * Bit offset of the first letter in the first bytes 370 */ 371 # if !defined(mhd_H_M_PROCESS_AS_BE) 372 # define mhd_H_M_FIRST_BIT 0u 373 # else 374 # define mhd_H_M_FIRST_BIT 24u 375 # endif 376 377 /** 378 * Bit offset of the terminating zero in the last bytes. 379 * A record stores its code at the same offset. 380 */ 381 # if !defined(mhd_H_M_PROCESS_AS_BE) 382 # define mhd_H_M_NUL_BIT 24u 383 # else 384 # define mhd_H_M_NUL_BIT 0u 385 # endif 386 387 /** 388 * Mask of the last bytes selecting the last three letters and excluding the 389 * terminating zero 390 */ 391 # define mhd_H_M_LAST_LETTERS_MASK mhd_H_M_PACK32 (0xFFu, 0xFFu, 0xFFu, 0u) 392 393 /** 394 * A record with the letters and the stored code of a method 395 */ 396 struct mhd_HttpMethodEntry32 397 { 398 /** 399 * The first bytes, including the terminating zero for length 3 400 */ 401 uint_least32_t first_bytes; 402 /** 403 * The last bytes: the last three letters of the method and the stored code 404 * in place of the terminating zero 405 */ 406 uint_least32_t last_bytes; 407 }; 408 409 410 # if defined(mhd_H_M_FUNC_FOR_32_FAST) 411 412 /* The fast version uses direct indexing into rows of four records. 413 The length selects row = min (len, 8) - 3: rows 0..4 cover lengths 3..7, 414 and row 5 handles longer names. The selector, bits 3..4 of the first 415 letter, selects a record within the row, distinguishing methods of the 416 same length (letter, its code -> selector): 417 418 length 3 GET G 0x47 -> 0 PUT P 0x50 -> 2 419 length 4 HEAD H 0x48 -> 1 POST P 0x50 -> 2 420 length 5 TRACE T 0x54 -> 2 421 length 6 DELETE D 0x44 -> 0 422 length 7 CONNECT C 0x43 -> 0 OPTIONS O 0x4F -> 1 423 424 The index of the selected record is 4 * row + selector. Leaving empty 425 records keeps this formula simple and avoids an intermediate index table. 426 427 The codes are stored XORed with OTHER, so empty records have zero stored 428 codes and therefore yield OTHER. Row 5 uses this rule to keep longer 429 extension methods on the ordinary lookup path, avoiding a separate 430 rejection by length in mixed method traffic. */ 431 432 /** 433 * Build a record from the first bytes @p b0 .. @p b3, the last three letters 434 * @p e0 .. @p e2 and the code @p code, stored encoded by #mhd_H_M_XOR_CODE(). 435 */ 436 # define mhd_H_M_ENTRY32F(b0, b1, b2, b3, e0, e1, e2, code) \ 437 { mhd_H_M_PACK32 ((b0), (b1), (b2), (b3)), \ 438 mhd_H_M_PACK32 ((e0), (e1), (e2), mhd_H_M_XOR_CODE (code)) } 439 440 /** 441 * The empty record: may match a name, but gives OTHER 442 */ 443 # define mhd_H_M_ENTRY32F_EMPTY { 0u, 0u } 444 445 /** 446 * Method records arranged for direct indexing as described above 447 */ 448 mhd_constexpr struct mhd_HttpMethodEntry32 mhd_h_m_tbl_32f[24] = { 449 /* Row 0, length 3 */ 450 mhd_H_M_ENTRY32F ('G', 'E', 'T', 0u, 'G', 'E', 'T', mhd_HTTP_METHOD_GET), 451 mhd_H_M_ENTRY32F_EMPTY, 452 mhd_H_M_ENTRY32F ('P', 'U', 'T', 0u, 'P', 'U', 'T', mhd_HTTP_METHOD_PUT), 453 mhd_H_M_ENTRY32F_EMPTY, 454 /* Row 1, length 4 */ 455 mhd_H_M_ENTRY32F_EMPTY, 456 mhd_H_M_ENTRY32F ('H', 'E', 'A', 'D', 'E', 'A', 'D', mhd_HTTP_METHOD_HEAD), 457 mhd_H_M_ENTRY32F ('P', 'O', 'S', 'T', 'O', 'S', 'T', mhd_HTTP_METHOD_POST), 458 mhd_H_M_ENTRY32F_EMPTY, 459 /* Row 2, length 5 */ 460 mhd_H_M_ENTRY32F_EMPTY, 461 mhd_H_M_ENTRY32F_EMPTY, 462 mhd_H_M_ENTRY32F ('T', 'R', 'A', 'C', 'A', 'C', 'E', mhd_HTTP_METHOD_TRACE), 463 mhd_H_M_ENTRY32F_EMPTY, 464 /* Row 3, length 6 */ 465 mhd_H_M_ENTRY32F ('D', 'E', 'L', 'E', 'E', 'T', 'E', mhd_HTTP_METHOD_DELETE), 466 mhd_H_M_ENTRY32F_EMPTY, 467 mhd_H_M_ENTRY32F_EMPTY, 468 mhd_H_M_ENTRY32F_EMPTY, 469 /* Row 4, length 7 */ 470 mhd_H_M_ENTRY32F ('C', 'O', 'N', 'N', 'E', 'C', 'T', mhd_HTTP_METHOD_CONNECT), 471 mhd_H_M_ENTRY32F ('O', 'P', 'T', 'I', 'O', 'N', 'S', mhd_HTTP_METHOD_OPTIONS), 472 mhd_H_M_ENTRY32F_EMPTY, 473 mhd_H_M_ENTRY32F_EMPTY, 474 /* Row 5, lengths above 7 */ 475 mhd_H_M_ENTRY32F_EMPTY, 476 mhd_H_M_ENTRY32F_EMPTY, 477 mhd_H_M_ENTRY32F_EMPTY, 478 mhd_H_M_ENTRY32F_EMPTY 479 }; 480 481 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ MHD_FN_PAR_IN_ (2) MHD_FN_PAR_CSTR_ (2) 482 MHD_FN_PURE_ enum mhd_HTTP_Method 483 mhd_parse_http_method (size_t len, 484 const char *mtd) 485 { 486 mhd_assert ('\0' == mtd[len]); 487 /* The required terminating zero makes four-byte loads safe at length 3 */ 488 if (mhd_COND_ALMOST_ALWAYS (3u <= len)) 489 { 490 /* Lengths above 7 use an empty row, so they follow the lookup path but 491 cannot produce a standard method code. */ 492 const size_t row = ((7u < len) ? 8u : len) - 3u; 493 const uint_least32_t first_bytes = mhd_H_M_LOAD32 (mtd); 494 const uint_least32_t last_bytes = mhd_H_M_LOAD32 (mtd + len - 3u); 495 /* Bits 3..4 of the first letter select one candidate within this row */ 496 const uint_least32_t selector = 497 (first_bytes >> (mhd_H_M_FIRST_BIT + 3u)) & 3u; 498 const struct mhd_HttpMethodEntry32 *const entry = 499 mhd_h_m_tbl_32f + 4u * row + selector; 500 /* The record stores its code in place of the terminating zero. Ignore 501 that byte and OR the XOR differences of the first and the last bytes. 502 Testing the combined difference against zero gives 1 on a match and 503 0 otherwise. Subtract that result from zero to obtain an all-ones or 504 all-zero mask. */ 505 const uint_least32_t mask = 506 (uint_least32_t) 507 (0u 508 - (uint_least32_t)(0u == ((first_bytes ^ entry->first_bytes) 509 | ((last_bytes ^ entry->last_bytes) 510 & mhd_H_M_LAST_LETTERS_MASK)))); 511 512 /* Keep only the stored code (code ^ OTHER). A zero mask or an empty 513 record leaves OTHER; otherwise the final XOR restores the code. */ 514 return (enum mhd_HTTP_Method) 515 (mhd_HTTP_METHOD_OTHER 516 ^ ((entry->last_bytes >> mhd_H_M_NUL_BIT) & 0xFFu & mask)); 517 } 518 return mhd_PARSE_HTTP_METHOD_OUTSIDE_3_7 (len, 519 mtd); 520 } 521 522 523 # else /* mhd_H_M_FUNC_FOR_32_COMPACT */ 524 525 /* The compact version stores one record per method, with no empty records. 526 With no spare row for longer methods, lengths outside 3..7 must be rejected 527 before indexing. It trades extra index arithmetic and the range check for 528 a smaller table. 529 530 The records of one length form a row of one or two records. With 531 row = len - 3, base = row + min (row, 2) locates the first record of the 532 row. The selector, bit 1 XOR bit 3 of the first letter, distinguishes 533 methods of the same length: P, T, D and O give 0; G, H and C give 1. 534 The index of the selected record is base + selector: 535 536 length 3 4 5 6 7 537 base 0 2 4 5 6 538 selector 0 PUT POST TRACE DELETE OPTIONS 539 selector 1 GET HEAD - - CONNECT 540 541 At lengths 5 and 6, selector 1 uses the next length's record, whose first 542 letter cannot match the first letter of the name. */ 543 544 /** 545 * Build a record from the first bytes @p b0 .. @p b3, the last three letters 546 * @p e0 .. @p e2 and the code @p code, stored without XOR encoding. 547 */ 548 # define mhd_H_M_ENTRY32C(b0, b1, b2, b3, e0, e1, e2, code) \ 549 { mhd_H_M_PACK32 ((b0), (b1), (b2), (b3)), \ 550 mhd_H_M_PACK32 ((e0), (e1), (e2), (code)) } 551 552 /** 553 * Method records arranged for compact indexing as described above 554 */ 555 mhd_constexpr struct mhd_HttpMethodEntry32 mhd_h_m_tbl_32c[8] = { 556 /* Length 3, base 0: selector 0, selector 1 */ 557 mhd_H_M_ENTRY32C ('P', 'U', 'T', 0u, 'P', 'U', 'T', mhd_HTTP_METHOD_PUT), 558 mhd_H_M_ENTRY32C ('G', 'E', 'T', 0u, 'G', 'E', 'T', mhd_HTTP_METHOD_GET), 559 /* Length 4, base 2: selector 0, selector 1 */ 560 mhd_H_M_ENTRY32C ('P', 'O', 'S', 'T', 'O', 'S', 'T', mhd_HTTP_METHOD_POST), 561 mhd_H_M_ENTRY32C ('H', 'E', 'A', 'D', 'E', 'A', 'D', mhd_HTTP_METHOD_HEAD), 562 /* Length 5, base 4 */ 563 mhd_H_M_ENTRY32C ('T', 'R', 'A', 'C', 'A', 'C', 'E', mhd_HTTP_METHOD_TRACE), 564 /* Length 6, base 5 */ 565 mhd_H_M_ENTRY32C ('D', 'E', 'L', 'E', 'E', 'T', 'E', mhd_HTTP_METHOD_DELETE), 566 /* Length 7, base 6: selector 0, selector 1 */ 567 mhd_H_M_ENTRY32C ('O', 'P', 'T', 'I', 'O', 'N', 'S', mhd_HTTP_METHOD_OPTIONS), 568 mhd_H_M_ENTRY32C ('C', 'O', 'N', 'N', 'E', 'C', 'T', mhd_HTTP_METHOD_CONNECT) 569 }; 570 571 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ MHD_FN_PAR_IN_ (2) MHD_FN_PAR_CSTR_ (2) 572 MHD_FN_PURE_ enum mhd_HTTP_Method 573 mhd_parse_http_method (size_t len, 574 const char *mtd) 575 { 576 uint_least32_t first_bytes; 577 uint_least32_t last_bytes; 578 uint_least32_t row; 579 uint_least32_t selector; 580 uint_least32_t rec_idx; 581 uint_least32_t diff; 582 uint_least32_t code; 583 const struct mhd_HttpMethodEntry32 *entry; 584 585 mhd_assert ('\0' == mtd[len]); 586 587 /* Lengths 3..7 become 0..4 after subtraction. Shorter lengths wrap to 588 large size_t values; longer lengths exceed 4. Reject both before the 589 loads of the first and the last bytes and before access to the table, 590 which has no spare records. */ 591 if (4u < (size_t)(len - 3u)) 592 return mhd_PARSE_HTTP_METHOD_OUTSIDE_3_7 (len, 593 mtd); 594 595 /* The last bytes include the required terminating zero; the records store 596 the code in its place. */ 597 first_bytes = mhd_H_M_LOAD32 (mtd); 598 last_bytes = mhd_H_M_LOAD32 (mtd + len - 3u); 599 /* Lengths 3..7 give rows 0..4 */ 600 row = (uint_least32_t)len - 3u; 601 /* Bits 1 and 3 of the first letter distinguish methods of the same 602 length */ 603 selector = ((first_bytes >> (mhd_H_M_FIRST_BIT + 1u)) 604 ^ (first_bytes >> (mhd_H_M_FIRST_BIT + 3u))) & 1u; 605 /* base + selector, where the bases of rows 0..4 are 0, 2, 4, 5 and 6. 606 At lengths 5 and 6, selector 1 reaches the next length's record, whose 607 first letter has selector 0 and therefore cannot match the first letter 608 of the name. */ 609 rec_idx = row + ((2u > row) ? row : 2u) + selector; 610 entry = mhd_h_m_tbl_32c + rec_idx; 611 /* Compare the first bytes and the last three letters, excluding the 612 stored code. A zero combined difference means the name matches. */ 613 diff = (first_bytes ^ entry->first_bytes) 614 | ((last_bytes ^ entry->last_bytes) & mhd_H_M_LAST_LETTERS_MASK); 615 /* Shift the stored code into the low byte; the uint8_t cast keeps only 616 that byte. Return it only on a match, otherwise return OTHER. */ 617 code = entry->last_bytes >> mhd_H_M_NUL_BIT; 618 return (0u == diff) ? (enum mhd_HTTP_Method)(uint8_t)code : 619 mhd_HTTP_METHOD_OTHER; 620 } 621 622 623 # endif /* mhd_H_M_FUNC_FOR_32_COMPACT */ 624 625 #endif /* mhd_H_M_FUNC_FOR_32_FAST || mhd_H_M_FUNC_FOR_32_COMPACT */