FM / util

/srv/osrm/osrm-backend/include/util

Name	Size	Mode	Actions
guidance/	-	0755	rm
alias.hpp	6870	0644	edit dl rm
assert.hpp	1964	0644	edit dl rm
attributes.hpp	357	0644	edit dl rm
bearing.hpp	3964	0644	edit dl rm
bit_range.hpp	2950	0644	edit dl rm
cheap_ruler.hpp	2124	0644	edit dl rm
concurrent_id_map.hpp	2148	0644	edit dl rm
conditional_restrictions.hpp	627	0644	edit dl rm
connectivity_checksum.hpp	1931	0644	edit dl rm
coordinate.hpp	9244	0644	edit dl rm
coordinate_calculation.hpp	16297	0644	edit dl rm
deallocating_vector.hpp	11205	0644	edit dl rm
debug.hpp	5958	0644	edit dl rm
dist_table_wrapper.hpp	2299	0644	edit dl rm
dynamic_graph.hpp	15951	0644	edit dl rm
exception.hpp	5126	0644	edit dl rm
exception_utils.hpp	609	0644	edit dl rm
exclude_flag.hpp	975	0644	edit dl rm
filtered_graph.hpp	5402	0644	edit dl rm
filtered_integer_range.hpp	3097	0644	edit dl rm
fingerprint.hpp	1166	0644	edit dl rm
for_each_indexed.hpp	634	0644	edit dl rm
for_each_pair.hpp	990	0644	edit dl rm
for_each_range.hpp	477	0644	edit dl rm
geojson_debug_logger.hpp	6330	0644	edit dl rm
geojson_debug_policies.hpp	1810	0644	edit dl rm
geojson_debug_policy_toolkit.hpp	3258	0644	edit dl rm
geojson_validation.hpp	2899	0644	edit dl rm
graph_traits.hpp	1245	0644	edit dl rm
graph_utils.hpp	3141	0644	edit dl rm
group_by.hpp	722	0644	edit dl rm
hilbert_value.hpp	3010	0644	edit dl rm
indexed_data.hpp	15039	0644	edit dl rm
integer_range.hpp	3286	0644	edit dl rm
isatty.hpp	610	0644	edit dl rm
json_container.hpp	3181	0644	edit dl rm
json_deep_compare.hpp	4732	0644	edit dl rm
json_renderer.hpp	4160	0644	edit dl rm
json_util.hpp	544	0644	edit dl rm
log.hpp	2187	0644	edit dl rm
lua_util.hpp	891	0644	edit dl rm
matrix_graph_wrapper.hpp	1294	0644	edit dl rm
meminfo.hpp	660	0644	edit dl rm
mmap_file.hpp	2776	0644	edit dl rm
mmap_tar.hpp	1007	0644	edit dl rm
msb.hpp	1178	0644	edit dl rm
node_based_graph.hpp	3530	0644	edit dl rm
opening_hours.hpp	8338	0644	edit dl rm
packed_vector.hpp	21691	0644	edit dl rm
percent.hpp	2106	0644	edit dl rm
permutation.hpp	1991	0644	edit dl rm
query_heap.hpp	10205	0644	edit dl rm
range_table.hpp	7119	0644	edit dl rm
rectangle.hpp	5900	0644	edit dl rm
serialization.hpp	5902	0644	edit dl rm
static_assert.hpp	640	0644	edit dl rm
static_graph.hpp	10702	0644	edit dl rm
static_rtree.hpp	34147	0644	edit dl rm
std_hash.hpp	1035	0644	edit dl rm
string_util.hpp	3400	0644	edit dl rm
tarjan_scc.hpp	6646	0644	edit dl rm
timed_histogram.hpp	2576	0644	edit dl rm
timezones.hpp	1417	0644	edit dl rm
timing_util.hpp	1485	0644	edit dl rm
to_osm_link.hpp	694	0644	edit dl rm
trigonometry_table.hpp	35906	0644	edit dl rm
typedefs.hpp	7627	0644	edit dl rm
vector_tile.hpp	303	0644	edit dl rm
vector_view.hpp	8000	0644	edit dl rm
version.hpp.in	406	0644	edit dl rm
viewport.hpp	1579	0644	edit dl rm
web_mercator.hpp	6480	0644	edit dl rm
xor_fast_hash.hpp	1797	0644	edit dl rm
xor_fast_hash_storage.hpp	2195	0644	edit dl rm

Edit: /srv/osrm/osrm-backend/include/util/hilbert_value.hpp (3010B)

#ifndef HILBERT_VALUE_HPP
#define HILBERT_VALUE_HPP

#include "osrm/coordinate.hpp"

#include <climits>
#include <cstdint>

namespace osrm::util
{

// Transform x and y to Hilbert SFC linear coordinate
// using N most significant bits of x and y.
//   References:
// [1] Arndt, Jörg. Matters Computational Ideas, Algorithms, Source Code, 2010. 1.31.1 The Hilbert
//     curve p. 86
// [2] FSM implementation from http://www.hackersdelight.org/hdcodetxt/hilbert/hil_s_from_xy.c.txt
//    The method is to employ the following state transition table:
// ----------------------------------------------------------
// If the current   And the next bits   then append  and enter
//   state is        of x and y are      to result     state
// ----------------------------------------------------------
//      A                 (0, 0)            00           B
//      A                 (0, 1)            01           A
//      A                 (1, 0)            11           D
//      A                 (1, 1)            10           A
//      B                 (0, 0)            00           A
//      B                 (0, 1)            11           C
//      B                 (1, 0)            01           B
//      B                 (1, 1)            10           B
//      C                 (0, 0)            10           D
//      C                 (0, 1)            11           B
//      C                 (1, 0)            01           C
//      C                 (1, 1)            00           D
//      D                 (0, 0)            10           C
//      D                 (0, 1)            01           D
//      D                 (1, 0)            11           A
//      D                 (1, 1)            00           C
template <int N = 32, typename T = std::uint32_t, typename R = std::uint64_t>
inline R HilbertToLinear(T x, T y)
{
    static_assert(N <= sizeof(T) * CHAR_BIT, "input type is smaller than N");
    static_assert(2 * N <= sizeof(R) * CHAR_BIT, "output type is smaller than 2N");

R result = 0;
    unsigned state = 0;
    for (int i = 0; i < N; ++i)
    {
        const unsigned xi = (x >> (sizeof(T) * CHAR_BIT - 1)) & 1;
        const unsigned yi = (y >> (sizeof(T) * CHAR_BIT - 1)) & 1;
        x <<= 1;
        y <<= 1;

const unsigned row = 4 * state | 2 * xi | yi;
        result = (result << 2) | ((0x361E9CB4 >> 2 * row) & 3);
        state = (0x8FE65831 >> 2 * row) & 3;
    }
    return result;
}

// Computes a 64 bit value that corresponds to the hilbert space filling curve
inline std::uint64_t GetHilbertCode(const Coordinate &coordinate)
{
    const std::uint32_t x = static_cast<std::int32_t>(coordinate.lon) +
                            static_cast<std::int32_t>(180 * COORDINATE_PRECISION);
    const std::uint32_t y = static_cast<std::int32_t>(coordinate.lat) +
                            static_cast<std::int32_t>(90 * COORDINATE_PRECISION);
    return HilbertToLinear(x, y);
}
} // namespace osrm::util

#endif /* HILBERT_VALUE_HPP */

cmd: