libmicrohttpd2

HTTP server C library (MHD 2.x, alpha)
Log | Files | Refs | README | LICENSE

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 */