1 // store.h
2 // ipdb / ipup / geod
3 //
4 // Created by Dr. Rolf Jansen on 2016-07-10.
5 // Copyright (c) 2016 projectworld.net. All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without modification,
8 // are permitted provided that the following conditions are met:
9 //
10 // 1. Redistributions of source code must retain the above copyright notice,
11 // this list of conditions and the following disclaimer.
12 //
13 // 2. Redistributions in binary form must reproduce the above copyright notice,
14 // this list of conditions and the following disclaimer in the documentation
15 // and/or other materials provided with the distribution.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
18 // OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
19 // AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
20 // OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
23 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
24 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26
27 #pragma mark ••• AVL Tree of IPv4-Ranges •••
28
29 typedef union
30 {
31 uint8_t byte[4];
32 uint32_t number;
33 } IP4Desc;
34
35 typedef uint32_t IP4Set[3]; // [0] -> lo, [1] -> hi, [2] -> cc
36
37 typedef struct IP4Node
38 {
39 uint32_t lo, hi; // IPv4 number range
40 uint32_t cc; // country code
41
42 int32_t B; // house holding
43 struct IP4Node *L, *R;
44 } IP4Node;
45
46 IP4Node *findIP4Node(uint32_t ip, IP4Node *node);
47 IP4Node *findNet4Node(uint32_t lo, uint32_t hi, uint32_t cc, IP4Node *node);
48 int addIP4Node(uint32_t lo, uint32_t hi, uint32_t cc, IP4Node **node);
49 int removeIP4Node(uint32_t ip, IP4Node **node);
50 void serializeIP4Tree(FILE *out, IP4Node *node);
51 void releaseIP4Tree(IP4Node *node);
52
bisectionIP4Search(uint32_t ip4,IP4Set * sortedIP4Sets,int count)53 static inline int bisectionIP4Search(uint32_t ip4, IP4Set *sortedIP4Sets, int count)
54 {
55 uint32_t u;
56 int o, p, q;
57 for (p = 0, q = count-1; p <= q;)
58 {
59 o = (p + q) >> 1;
60 if ((u = sortedIP4Sets[o][0]) <= ip4 && ip4 <= sortedIP4Sets[o][1])
61 return o;
62 else if (ip4 < u)
63 q = o-1;
64 else // (ip4 > sortedIP4Sets[o][1])
65 p = o+1;
66 }
67
68 return -1;
69 }
70
71
72 #pragma mark ••• AVL Tree of IPv6-Ranges •••
73
74 typedef union
75 {
76 uint64_t quad[2];
77 uint16_t word[8];
78 uint128t number;
79 } IP6Desc;
80
81 typedef uint128t IP6Set[3]; // [0] -> lo, [1] -> hi, [2] -> cc
82
83 typedef struct IP6Node
84 {
85 uint128t lo, hi; // IPv4 number range
86 uint32_t cc; // country code
87
88 int32_t B; // house holding
89 struct IP6Node *L, *R;
90 } IP6Node;
91
92 IP6Node *findIP6Node(uint128t ip, IP6Node *node);
93 IP6Node *findNet6Node(uint128t lo, uint128t hi, uint32_t cc, IP6Node *node);
94 int addIP6Node(uint128t lo, uint128t hi, uint32_t cc, IP6Node **node);
95 int removeIP6Node(uint128t ip, IP6Node **node);
96 void serializeIP6Tree(FILE *out, IP6Node *node);
97 void releaseIP6Tree(IP6Node *node);
98
bisectionIP6Search(uint128t ip6,IP6Set * sortedIP6Sets,int count)99 static inline int bisectionIP6Search(uint128t ip6, IP6Set *sortedIP6Sets, int count)
100 {
101 uint128t u;
102 int o, p, q;
103 for (p = 0, q = count-1; p <= q;)
104 {
105 o = (p + q) >> 1;
106 if (le_u128(u = sortedIP6Sets[o][0], ip6) && le_u128(ip6, sortedIP6Sets[o][1]))
107 return o;
108 else if (lt_u128(ip6, u))
109 q = o-1;
110 else // (gt_u128(ip6, sortedIP6Sets[o][1]))
111 p = o+1;
112 }
113
114 return -1;
115 }
116
117
118 #pragma mark ••• AVL Tree of Country Codes •••
119
120 typedef struct CCNode
121 {
122 uint32_t cc; // country code
123 uint32_t ui; // user info
124
125 int32_t B; // house holding
126 struct CCNode *L, *R;
127 } CCNode;
128
129 CCNode *findCCNode(uint32_t cc, CCNode *node);
130 int addCCNode(uint32_t cc, uint32_t ui, CCNode **node);
131 int removeCCNode(uint32_t cc, CCNode **node);
132 void releaseCCTree(CCNode *node);
133
134
135 #pragma mark ••• Pseudo Hash Table of Country Codes •••
136
137 #define ccTableSize 676
138
cce(uint16_t cc)139 static inline uint32_t cce(uint16_t cc)
140 {
141 uint8_t *ca = (uint8_t *)&cc;
142 return (ca[b2_0]-'A')*26 + (ca[b2_1]-'A'); // AA to ZZ ranges from 0 to 675
143 }
144
145 CCNode **createCCTable(void);
146 void releaseCCTable(CCNode *table[]);
147
148 CCNode *findCC(CCNode *table[], uint32_t cc);
149 void storeCC(CCNode *table[], char *ccui);
150 void removeCC(CCNode *table[], uint32_t cc);
151
152
153
154 #pragma mark ••• IP number/string utility functions •••
155
156 #include <sys/socket.h>
157 #include <arpa/inet.h>
158
ipv4_str2bin(char * str)159 static inline uint32_t ipv4_str2bin(char *str)
160 {
161 uint32_t bin;
162 return (inet_pton(AF_INET, str, &bin) > 0)
163 ? swapInt32(bin)
164 : 0;
165 }
166
167 typedef char IP4Str[16];
ipv4_bin2str(uint32_t bin,char * str)168 static inline char *ipv4_bin2str(uint32_t bin, char *str)
169 {
170 IP4Desc ipdsc = {.number = bin};
171 sprintf(str, "%d.%d.%d.%d", ipdsc.byte[b4_3], ipdsc.byte[b4_2], ipdsc.byte[b4_1], ipdsc.byte[b4_0]);
172 return str;
173 }
174
ipv6_str2bin(char * str)175 static inline uint128t ipv6_str2bin(char *str)
176 {
177 uint64_t bin[2];
178 return (inet_pton(AF_INET6, str, &bin) > 0)
179 ? (IP6Desc){swapInt64(bin[b2_1]), swapInt64(bin[b2_0])}.number
180 : u64_to_u128t(0);
181 }
182
183 typedef char IP6Str[40];
ipv6_bin2str(uint128t bin,char * str)184 static inline char *ipv6_bin2str(uint128t bin, char *str)
185 {
186 IP6Desc ipdsc = {.number = bin};
187 sprintf(str, "%x:%x:%x:%x:%x:%x:%x:%x", ipdsc.word[b8_7], ipdsc.word[b8_6], ipdsc.word[b8_5], ipdsc.word[b8_4],
188 ipdsc.word[b8_3], ipdsc.word[b8_2], ipdsc.word[b8_1], ipdsc.word[b8_0]);
189 return str;
190 }
191
192
intlb4_1p(double v)193 static inline int32_t intlb4_1p(double v)
194 {
195 return (int32_t)log2(v+1);
196 }
197
198
199 static const IP6Desc v6[129] =
200 {
201 {0x0, 0x0}, {0x1, 0x0}, {0x3, 0x0}, {0x7, 0x0}, {0xF, 0x0}, {0x1F, 0x0}, {0x3F, 0x0}, {0x7F, 0x0}, {0xFF, 0x0},
202 {0x1FF, 0x0}, {0x3FF, 0x0}, {0x7FF, 0x0}, {0xFFF, 0x0}, {0x1FFF, 0x0}, {0x3FFF, 0x0}, {0x7FFF, 0x0}, {0xFFFF, 0x0},
203 {0x1FFFF, 0x0}, {0x3FFFF, 0x0}, {0x7FFFF, 0x0}, {0xFFFFF, 0x0}, {0x1FFFFF, 0x0}, {0x3FFFFF, 0x0}, {0x7FFFFF, 0x0},
204 {0xFFFFFF, 0x0}, {0x1FFFFFF, 0x0}, {0x3FFFFFF, 0x0}, {0x7FFFFFF, 0x0}, {0xFFFFFFF, 0x0}, {0x1FFFFFFF, 0x0}, {0x3FFFFFFF, 0x0},
205 {0x7FFFFFFF, 0x0}, {0xFFFFFFFF, 0x0}, {0x1FFFFFFFF, 0x0}, {0x3FFFFFFFF, 0x0}, {0x7FFFFFFFF, 0x0}, {0xFFFFFFFFF, 0x0},
206 {0x1FFFFFFFFF, 0x0}, {0x3FFFFFFFFF, 0x0}, {0x7FFFFFFFFF, 0x0}, {0xFFFFFFFFFF, 0x0}, {0x1FFFFFFFFFF, 0x0}, {0x3FFFFFFFFFF, 0x0},
207 {0x7FFFFFFFFFF, 0x0}, {0xFFFFFFFFFFF, 0x0}, {0x1FFFFFFFFFFF, 0x0}, {0x3FFFFFFFFFFF, 0x0}, {0x7FFFFFFFFFFF, 0x0},
208 {0xFFFFFFFFFFFF, 0x0}, {0x1FFFFFFFFFFFF, 0x0}, {0x3FFFFFFFFFFFF, 0x0}, {0x7FFFFFFFFFFFF, 0x0}, {0xFFFFFFFFFFFFF, 0x0},
209 {0x1FFFFFFFFFFFFF, 0x0}, {0x3FFFFFFFFFFFFF, 0x0}, {0x7FFFFFFFFFFFFF, 0x0}, {0xFFFFFFFFFFFFFF, 0x0}, {0x1FFFFFFFFFFFFFF, 0x0},
210 {0x3FFFFFFFFFFFFFF, 0x0}, {0x7FFFFFFFFFFFFFF, 0x0}, {0xFFFFFFFFFFFFFFF, 0x0}, {0x1FFFFFFFFFFFFFFF, 0x0}, {0x3FFFFFFFFFFFFFFF, 0x0},
211 {0x7FFFFFFFFFFFFFFF, 0x0}, {0xFFFFFFFFFFFFFFFF, 0x0}, {0xFFFFFFFFFFFFFFFF, 0x1}, {0xFFFFFFFFFFFFFFFF, 0x3},
212 {0xFFFFFFFFFFFFFFFF, 0x7}, {0xFFFFFFFFFFFFFFFF, 0xF}, {0xFFFFFFFFFFFFFFFF, 0x1F}, {0xFFFFFFFFFFFFFFFF, 0x3F},
213 {0xFFFFFFFFFFFFFFFF, 0x7F}, {0xFFFFFFFFFFFFFFFF, 0xFF}, {0xFFFFFFFFFFFFFFFF, 0x1FF}, {0xFFFFFFFFFFFFFFFF, 0x3FF},
214 {0xFFFFFFFFFFFFFFFF, 0x7FF}, {0xFFFFFFFFFFFFFFFF, 0xFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFF},
215 {0xFFFFFFFFFFFFFFFF, 0x7FFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFF},
216 {0xFFFFFFFFFFFFFFFF, 0x7FFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFF},
217 {0xFFFFFFFFFFFFFFFF, 0x7FFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFF},
218 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFF},
219 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFF},
220 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFF},
221 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFF},
222 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFFF},
223 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFF},
224 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFF},
225 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFFF},
226 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x1FFFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0x3FFFFFFFFFFFFFFF},
227 {0xFFFFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFFF}, {0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF}
228 };
229
inteb6_m1(int32_t e)230 static inline uint128t inteb6_m1(int32_t e)
231 {
232 return (0 <= e && e <= 127) ? v6[e].number : u64_to_u128t(1);
233 }
234
intlb6_1p(uint128t v)235 static inline int32_t intlb6_1p(uint128t v)
236 {
237 uint128t u;
238 int o, p, q;
239 for (p = 0, q = 127; p <= q;)
240 {
241 o = (p + q) >> 1;
242 if (le_u128(u = v6[o].number, v) && lt_u128(v, v6[o+1].number))
243 return o;
244 else if (lt_u128(v, u))
245 q = o-1;
246 else // (ge_u128(v, v6[o+1]))
247 p = o+1;
248 }
249
250 return 0;
251 }
252