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
9namespace DB
10{
11
12// To be used in formatIPv4, maps a byte to it's string form prefixed with length (so save strlen call).
13extern 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)
44static 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.
52template <UInt32 base, typename T>
53static 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
81void 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