1 | #include <Common/formatIPv6.h> |
2 | #include <Common/hex.h> |
3 | #include <Common/StringUtils/StringUtils.h> |
4 | |
5 | #include <ext/range.h> |
6 | #include <array> |
7 | #include <algorithm> |
8 | |
9 | namespace DB |
10 | { |
11 | |
12 | // To be used in formatIPv4, maps a byte to it's string form prefixed with length (so save strlen call). |
13 | extern const char one_byte_to_string_lookup_table[256][4] = |
14 | { |
15 | {1, '0'}, {1, '1'}, {1, '2'}, {1, '3'}, {1, '4'}, {1, '5'}, {1, '6'}, {1, '7'}, {1, '8'}, {1, '9'}, |
16 | {2, '1', '0'}, {2, '1', '1'}, {2, '1', '2'}, {2, '1', '3'}, {2, '1', '4'}, {2, '1', '5'}, {2, '1', '6'}, {2, '1', '7'}, {2, '1', '8'}, {2, '1', '9'}, |
17 | {2, '2', '0'}, {2, '2', '1'}, {2, '2', '2'}, {2, '2', '3'}, {2, '2', '4'}, {2, '2', '5'}, {2, '2', '6'}, {2, '2', '7'}, {2, '2', '8'}, {2, '2', '9'}, |
18 | {2, '3', '0'}, {2, '3', '1'}, {2, '3', '2'}, {2, '3', '3'}, {2, '3', '4'}, {2, '3', '5'}, {2, '3', '6'}, {2, '3', '7'}, {2, '3', '8'}, {2, '3', '9'}, |
19 | {2, '4', '0'}, {2, '4', '1'}, {2, '4', '2'}, {2, '4', '3'}, {2, '4', '4'}, {2, '4', '5'}, {2, '4', '6'}, {2, '4', '7'}, {2, '4', '8'}, {2, '4', '9'}, |
20 | {2, '5', '0'}, {2, '5', '1'}, {2, '5', '2'}, {2, '5', '3'}, {2, '5', '4'}, {2, '5', '5'}, {2, '5', '6'}, {2, '5', '7'}, {2, '5', '8'}, {2, '5', '9'}, |
21 | {2, '6', '0'}, {2, '6', '1'}, {2, '6', '2'}, {2, '6', '3'}, {2, '6', '4'}, {2, '6', '5'}, {2, '6', '6'}, {2, '6', '7'}, {2, '6', '8'}, {2, '6', '9'}, |
22 | {2, '7', '0'}, {2, '7', '1'}, {2, '7', '2'}, {2, '7', '3'}, {2, '7', '4'}, {2, '7', '5'}, {2, '7', '6'}, {2, '7', '7'}, {2, '7', '8'}, {2, '7', '9'}, |
23 | {2, '8', '0'}, {2, '8', '1'}, {2, '8', '2'}, {2, '8', '3'}, {2, '8', '4'}, {2, '8', '5'}, {2, '8', '6'}, {2, '8', '7'}, {2, '8', '8'}, {2, '8', '9'}, |
24 | {2, '9', '0'}, {2, '9', '1'}, {2, '9', '2'}, {2, '9', '3'}, {2, '9', '4'}, {2, '9', '5'}, {2, '9', '6'}, {2, '9', '7'}, {2, '9', '8'}, {2, '9', '9'}, |
25 | {3, '1', '0', '0'}, {3, '1', '0', '1'}, {3, '1', '0', '2'}, {3, '1', '0', '3'}, {3, '1', '0', '4'}, {3, '1', '0', '5'}, {3, '1', '0', '6'}, {3, '1', '0', '7'}, {3, '1', '0', '8'}, {3, '1', '0', '9'}, |
26 | {3, '1', '1', '0'}, {3, '1', '1', '1'}, {3, '1', '1', '2'}, {3, '1', '1', '3'}, {3, '1', '1', '4'}, {3, '1', '1', '5'}, {3, '1', '1', '6'}, {3, '1', '1', '7'}, {3, '1', '1', '8'}, {3, '1', '1', '9'}, |
27 | {3, '1', '2', '0'}, {3, '1', '2', '1'}, {3, '1', '2', '2'}, {3, '1', '2', '3'}, {3, '1', '2', '4'}, {3, '1', '2', '5'}, {3, '1', '2', '6'}, {3, '1', '2', '7'}, {3, '1', '2', '8'}, {3, '1', '2', '9'}, |
28 | {3, '1', '3', '0'}, {3, '1', '3', '1'}, {3, '1', '3', '2'}, {3, '1', '3', '3'}, {3, '1', '3', '4'}, {3, '1', '3', '5'}, {3, '1', '3', '6'}, {3, '1', '3', '7'}, {3, '1', '3', '8'}, {3, '1', '3', '9'}, |
29 | {3, '1', '4', '0'}, {3, '1', '4', '1'}, {3, '1', '4', '2'}, {3, '1', '4', '3'}, {3, '1', '4', '4'}, {3, '1', '4', '5'}, {3, '1', '4', '6'}, {3, '1', '4', '7'}, {3, '1', '4', '8'}, {3, '1', '4', '9'}, |
30 | {3, '1', '5', '0'}, {3, '1', '5', '1'}, {3, '1', '5', '2'}, {3, '1', '5', '3'}, {3, '1', '5', '4'}, {3, '1', '5', '5'}, {3, '1', '5', '6'}, {3, '1', '5', '7'}, {3, '1', '5', '8'}, {3, '1', '5', '9'}, |
31 | {3, '1', '6', '0'}, {3, '1', '6', '1'}, {3, '1', '6', '2'}, {3, '1', '6', '3'}, {3, '1', '6', '4'}, {3, '1', '6', '5'}, {3, '1', '6', '6'}, {3, '1', '6', '7'}, {3, '1', '6', '8'}, {3, '1', '6', '9'}, |
32 | {3, '1', '7', '0'}, {3, '1', '7', '1'}, {3, '1', '7', '2'}, {3, '1', '7', '3'}, {3, '1', '7', '4'}, {3, '1', '7', '5'}, {3, '1', '7', '6'}, {3, '1', '7', '7'}, {3, '1', '7', '8'}, {3, '1', '7', '9'}, |
33 | {3, '1', '8', '0'}, {3, '1', '8', '1'}, {3, '1', '8', '2'}, {3, '1', '8', '3'}, {3, '1', '8', '4'}, {3, '1', '8', '5'}, {3, '1', '8', '6'}, {3, '1', '8', '7'}, {3, '1', '8', '8'}, {3, '1', '8', '9'}, |
34 | {3, '1', '9', '0'}, {3, '1', '9', '1'}, {3, '1', '9', '2'}, {3, '1', '9', '3'}, {3, '1', '9', '4'}, {3, '1', '9', '5'}, {3, '1', '9', '6'}, {3, '1', '9', '7'}, {3, '1', '9', '8'}, {3, '1', '9', '9'}, |
35 | {3, '2', '0', '0'}, {3, '2', '0', '1'}, {3, '2', '0', '2'}, {3, '2', '0', '3'}, {3, '2', '0', '4'}, {3, '2', '0', '5'}, {3, '2', '0', '6'}, {3, '2', '0', '7'}, {3, '2', '0', '8'}, {3, '2', '0', '9'}, |
36 | {3, '2', '1', '0'}, {3, '2', '1', '1'}, {3, '2', '1', '2'}, {3, '2', '1', '3'}, {3, '2', '1', '4'}, {3, '2', '1', '5'}, {3, '2', '1', '6'}, {3, '2', '1', '7'}, {3, '2', '1', '8'}, {3, '2', '1', '9'}, |
37 | {3, '2', '2', '0'}, {3, '2', '2', '1'}, {3, '2', '2', '2'}, {3, '2', '2', '3'}, {3, '2', '2', '4'}, {3, '2', '2', '5'}, {3, '2', '2', '6'}, {3, '2', '2', '7'}, {3, '2', '2', '8'}, {3, '2', '2', '9'}, |
38 | {3, '2', '3', '0'}, {3, '2', '3', '1'}, {3, '2', '3', '2'}, {3, '2', '3', '3'}, {3, '2', '3', '4'}, {3, '2', '3', '5'}, {3, '2', '3', '6'}, {3, '2', '3', '7'}, {3, '2', '3', '8'}, {3, '2', '3', '9'}, |
39 | {3, '2', '4', '0'}, {3, '2', '4', '1'}, {3, '2', '4', '2'}, {3, '2', '4', '3'}, {3, '2', '4', '4'}, {3, '2', '4', '5'}, {3, '2', '4', '6'}, {3, '2', '4', '7'}, {3, '2', '4', '8'}, {3, '2', '4', '9'}, |
40 | {3, '2', '5', '0'}, {3, '2', '5', '1'}, {3, '2', '5', '2'}, {3, '2', '5', '3'}, {3, '2', '5', '4'}, {3, '2', '5', '5'}, |
41 | }; |
42 | |
43 | /// integer logarithm, return ceil(log(value, base)) (the smallest integer greater or equal than log(value, base) |
44 | static constexpr UInt32 intLog(const UInt32 value, const UInt32 base, const bool carry) |
45 | { |
46 | return value >= base ? 1 + intLog(value / base, base, value % base || carry) : value % base > 1 || carry; |
47 | } |
48 | |
49 | /// Print integer in desired base, faster than sprintf. |
50 | /// NOTE This is not the best way. See https://github.com/miloyip/itoa-benchmark |
51 | /// But it doesn't matter here. |
52 | template <UInt32 base, typename T> |
53 | static void printInteger(char *& out, T value) |
54 | { |
55 | if (value == 0) |
56 | *out++ = '0'; |
57 | else |
58 | { |
59 | constexpr size_t buffer_size = sizeof(T) * intLog(256, base, false); |
60 | |
61 | char buf[buffer_size]; |
62 | auto ptr = buf; |
63 | |
64 | while (value > 0) |
65 | { |
66 | *ptr = hexDigitLowercase(value % base); |
67 | ++ptr; |
68 | value /= base; |
69 | } |
70 | |
71 | /// Copy to out reversed. |
72 | while (ptr != buf) |
73 | { |
74 | --ptr; |
75 | *out = *ptr; |
76 | ++out; |
77 | } |
78 | } |
79 | } |
80 | |
81 | void formatIPv6(const unsigned char * src, char *& dst, UInt8 zeroed_tail_bytes_count) |
82 | { |
83 | struct { int base, len; } best{-1, 0}, cur{-1, 0}; |
84 | std::array<UInt16, IPV6_BINARY_LENGTH / sizeof(UInt16)> words{}; |
85 | |
86 | /** Preprocess: |
87 | * Copy the input (bytewise) array into a wordwise array. |
88 | * Find the longest run of 0x00's in src[] for :: shorthanding. */ |
89 | for (const auto i : ext::range(0, IPV6_BINARY_LENGTH - zeroed_tail_bytes_count)) |
90 | words[i / 2] |= src[i] << ((1 - (i % 2)) << 3); |
91 | |
92 | for (const auto i : ext::range(0, words.size())) |
93 | { |
94 | if (words[i] == 0) |
95 | { |
96 | if (cur.base == -1) |
97 | { |
98 | cur.base = i; |
99 | cur.len = 1; |
100 | } |
101 | else |
102 | cur.len++; |
103 | } |
104 | else |
105 | { |
106 | if (cur.base != -1) |
107 | { |
108 | if (best.base == -1 || cur.len > best.len) |
109 | best = cur; |
110 | cur.base = -1; |
111 | } |
112 | } |
113 | } |
114 | |
115 | if (cur.base != -1) |
116 | { |
117 | if (best.base == -1 || cur.len > best.len) |
118 | best = cur; |
119 | } |
120 | |
121 | if (best.base != -1 && best.len < 2) |
122 | best.base = -1; |
123 | |
124 | /// Format the result. |
125 | for (const int i : ext::range(0, words.size())) |
126 | { |
127 | /// Are we inside the best run of 0x00's? |
128 | if (best.base != -1 && i >= best.base && i < (best.base + best.len)) |
129 | { |
130 | if (i == best.base) |
131 | *dst++ = ':'; |
132 | continue; |
133 | } |
134 | |
135 | /// Are we following an initial run of 0x00s or any real hex? |
136 | if (i != 0) |
137 | *dst++ = ':'; |
138 | |
139 | /// Is this address an encapsulated IPv4? |
140 | if (i == 6 && best.base == 0 && (best.len == 6 || (best.len == 5 && words[5] == 0xffffu))) |
141 | { |
142 | UInt8 ipv4_buffer[IPV4_BINARY_LENGTH] = {0}; |
143 | memcpy(ipv4_buffer, src + 12, IPV4_BINARY_LENGTH); |
144 | // Due to historical reasons formatIPv4() takes ipv4 in BE format, but inside ipv6 we store it in LE-format. |
145 | std::reverse(std::begin(ipv4_buffer), std::end(ipv4_buffer)); |
146 | |
147 | formatIPv4(ipv4_buffer, dst, std::min(zeroed_tail_bytes_count, static_cast<UInt8>(IPV4_BINARY_LENGTH)), "0" ); |
148 | // formatIPv4 has already added a null-terminator for us. |
149 | return; |
150 | } |
151 | |
152 | printInteger<16>(dst, words[i]); |
153 | } |
154 | |
155 | /// Was it a trailing run of 0x00's? |
156 | if (best.base != -1 && size_t(best.base) + size_t(best.len) == words.size()) |
157 | *dst++ = ':'; |
158 | |
159 | *dst++ = '\0'; |
160 | } |
161 | |
162 | } |
163 | |