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