2 * maskmap - Tcl extension for address mask map data structures
3 * Copyright 2006 Ian Jackson
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this library; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
21 #include "chiark_tcl_hbytes.h"
23 /*---------- operations on AddrMap_Entry ----------*/
25 static void ame_init(AddrMap_Entry *ame) {
31 static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
32 /* returns non-0 iff some bits were cleared */
34 unsigned result, sparemask;
37 sparebits= bytes * 8 - ame->prefixlen;
38 if (!sparebits) return 0;
40 sparemask= (1u << sparebits) - 1;
41 datap= &ame->prefix[bytes-1];
43 result= *datap & sparemask;
49 static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
50 Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
52 /* *ame should be blank entry; after exit (even error exit) it will be valid
53 * - on errors, it will be blank. inmap is 1 if we're parsing an existing
54 * map or 0 if it's an entry to be added or modified. */
56 int suppliedprefixbytes, prefixbits, wantprefixbytes;
60 hbytes_empty(&prefix);
62 rc= pat_hb(ip,prefixo,&prefix); if (rc) goto x_rc;
63 rc= pat_int(ip,prefixbitso,&prefixbits); if (rc) goto x_rc;
65 wantprefixbytes= prefix_bytes(prefixbits);
66 suppliedprefixbytes= hbytes_len(&prefix);
68 if (suppliedprefixbytes < wantprefixbytes) {
69 rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
70 "HBYTES ADDRMAP SYNTAX UNDERRUN");
73 if (inmap && suppliedprefixbytes > wantprefixbytes) {
74 rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
75 "HBYTES ADDRMAP SYNTAX OVERRUN");
79 ame->prefixlen= prefixbits;
80 ame->prefix= TALLOC(wantprefixbytes); assert(ame->prefix);
81 memcpy(ame->prefix, data, wantprefixbytes);
83 if (ame_clear_unwanted(ame, wantprefixbytes)) {
84 rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
85 " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
96 static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
97 int directbytes, leftoverbits;
99 assert(len >= ref->prefixlen);
101 directbytes= ref->prefixlen / 8;
102 if (memcmp(ref->prefix, addr, directbytes)) return 0;
104 leftoverbits= ref->prefixlen % 8;
106 if ((addr[directbytes] & (0xffu << leftoverbits))
107 != search->prefix[directbytes])
113 static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) {
114 /* +2 = a covers later range of address space than b
115 * +1 = a wholly contains but is not equal to b
116 * 0 = a is identical to b
117 * -1 = b wholly contains but is not equal to a
118 * -2 = b covers later range of address space than a
120 int al= a->prefixlen;
121 int bl= b->prefixlen;
124 if (al==bl) { ml=al; }
125 else if (al<bl) { ml=al; if (ame_contains(a,b->prefix,bl)) return +1; }
126 else if (bl<al) { ml=bl; if (ame_contains(b,a->prefix,al)) return -1; }
128 d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
134 /*---------- searching maps ----------*/
144 am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
145 int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */,
150 if (high_strict <= low_oreq) {
151 assert(high_strict == low_oreq);
156 mid= (high_strict + low_oreq) / 2;
157 cmp= test(&am->entries[mid], u);
172 int forbid_aroundsmall;
173 AddrMap_Entry proposed;
178 am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
179 struct am_search_u *u= u_v;
182 cmp= ame_compare(&u.proposed, ame);
184 case -1: u->sr= sr_inbig; return 0;
185 case 0: u->sr= sr_exact; return 0;
186 case +1: u->sr= sr_aroundsmall; return 0;
192 am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
194 struct am_search_u u;
196 u.forbid_aroundsmall= forbid_aroundsmall;
197 u.proposed= proposed;
200 *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
202 assert(!!found == (u.sr != sr_notfound));
206 /*---------- useful operations on AddrMap_Value etc. ----------*/
208 /*---------- amendment (complex algorithm) ----------*/
210 struct am_amend_aroundsmall_u {
217 am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
218 struct am_amend_aroundsmall_u *u= u_v;
220 cmp= u->sign * ame_compare(search, u->new);
223 case +2: return -u->sign;
224 case +1: return +u->sign;
229 int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
230 AddrMap_Var map, Tcl_Obj *prefix,
231 Tcl_Obj *preflen, Tcl_Obj *data) {
232 AddrMap_Value *am= map.am;
233 AddrMap_Entry new, *fragment;
234 AddrMap_Entry *breaking, *replacements;
235 int rc, insertat, findend, cmp, nreplacements, new_used;
236 struct am_amend_aroundsmall_u u;
240 rc= ame_parsekey(ip,&new,prefix,preflen,0); if (rc) return rc;
242 sr= am_search(am, &new, &searched);
246 replace_start= searched;
247 replace_end= searched;
255 replace_end= searched+1;
261 replace_start= am_binarychop(am, 0, searched, &u,
262 am_amend_aroundsmall_binchoptest, &dummy);
264 replace_end= am_binarychop(am, searched+1, am.used, &u,
265 am_amend_aroundsmall_binchoptest, &dummy);
269 /* Urgh, we need to break it up. This produces
270 * - innermost prefix (the new one) as specified
271 * - one for each bitlength
273 * > outermost (the existing one)
274 * each one specifying the outermost prefix plus zero, one,
275 * two, etc. bits of the innermost followed by one bit
276 * opposite to the innermost, with the outermost's data
277 * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
278 * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
279 * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
282 breaking= &am.entries[searched];
283 nreplacements= new.prefix - breaking->prefixlen + 1;
284 fixme check integer overflow ^
285 replacements= TALLOC(sizeof(*replacements) * nreplacements);
287 for (fragmentlen= breaking->prefixlen + 1,
288 left_insert= 0, right_insert= nreplacements;
289 fragmentlen <= new.prefix;
293 fragmentbytes= prefix_bytes(fragmentlen)
294 fragment->prefixlen= fragmentlen;
295 fragment->prefix= TALLOC(fragmentbytes);
296 memcpy(fragment->prefix, new.prefix, fragmentbytes);
297 ame_clear_unwanted(fragment, fragmentbytes);
299 fragment->prefix[fragmentbytes] ^=
300 0x80u >> ((fragmentlen+7) & 7);
302 switch (ame_compare(&fragment, &new)) {
303 case -2: replacements[left_insert++]= fragment; break;
304 case +2: replacements[--right_insert]= fragment; break;
308 assert(left_insert == right_insert-1);
309 replacements[left_insert]= new;
312 replace_end= searched+1;
317 new_used= am.used - (replace_end - replace_start) + nreplacements;
319 if (new_used > am.space)
320 am_reallocentries(am, new_used * 2);
322 for (scan=replacements, i=0;
326 Tcl_IncrRefCount(scan->data);
329 for (i= replace_start, scan= am.entries+i;
335 memmove(am.entries + replace_start + nreplacements,
336 am.entries + replace_end,
337 sizeof(*am.entries) * (am.used - replace_end));
339 memcpy(am.entries + replace_start,
341 sizeof(*am.entries) * nreplacements);
344 if (replacements != &new)
345 /* we don't bother freeing the actual array elements because
346 * if replacements!=&new the array is only full if we're
347 * committed and have already copied the values into the actual
354 /*---------- other substantial operations on mask maps ----------*/
356 int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
357 Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
359 AddrMap_Value *am= (void*)&mapo->internalRep;
360 const Byte *addr= hbytes_data(&addrhb);
361 int addrbytes= hbytes_len(&addrhb);
362 int i, addrbits, place;
365 addrbits= addrbytes * 8;
366 sr= am_search(am, addr, addrbits, &place);
371 if (!def) return staticerr(ip, "address not found in addr-map",
372 "HBYTES ADDRMAP NOMATCH");
377 return staticerr(ip, "address shorter than mask in map",
378 "HBYTES ADDRMAP UNDERRUN");
382 *result= am.entres[place].data;
390 /*---------- Tcl type and arg parsing functions ----------*/