maskmap/maskmap.c

   1 /*
   2  */
   3
   4 #include "chiark_tcl_hbytes.h"
   5
   6 /*---------- operations on AddrMap_Entry ----------*/
   7
   8 static void ame_init(AddrMap_Entry *ame) {
   9   ame->prefixlen= -1;
  10   ame->prefix= 0;
  11   ame->data= 0;
  12 }
  13
  14 static unsigned ame_clear_unwanted(AddrMap_Entry *ame, int bytes) {
  15   /* returns non-0 iff some bits were cleared */
  16   int sparebits;
  17   unsigned result, sparemask;
  18   Byte *datap;
  19
  20   sparebits= bytes * 8 - ame->prefixlen;
  21   if (!sparebits) return 0;
  22
  23   sparemask= (1u << sparebits) - 1;
  24   datap= &ame->prefix[bytes-1];
  25
  26   result= *datap & sparemask;
  27   *datap &= ~sparemask;
  28
  29   return result;
  30 }
  31
  32 static int ame_parsekey(Tcl_Interp *ip, AddrMap_Entry *ame,
  33                         Tcl_Obj *prefixo, Tcl_Obj *prefixbitso,
  34                         int inmap) {
  35  /* *ame should be blank entry; after exit (even error exit) it will be valid
  36   * - on errors, it will be blank.  inmap is 1 if we're parsing an existing
  37   * map or 0 if it's an entry to be added or modified. */
  38   HBytes_Value prefix;
  39   int suppliedprefixbytes, prefixbits, wantprefixbytes;
  40   const Byte *data;
  41   int rc;
  42
  43   hbytes_empty(&prefix);
  44
  45   rc= pat_hb(ip,prefixo,&prefix);  if (rc) goto x_rc;
  46   rc= pat_int(ip,prefixbitso,&prefixbits);  if (rc) goto x_rc;
  47
  48   wantprefixbytes= prefix_bytes(prefixbits);
  49   suppliedprefixbytes= hbytes_len(&prefix);
  50
  51   if (suppliedprefixbytes < wantprefixbytes) {
  52     rc= staticerr(ip, "addr-map entry PREFIX too short for PREFIX-LEN",
  53                   "HBYTES ADDRMAP SYNTAX UNDERRUN");
  54     goto x_rc;
  55   }
  56   if (inmap && suppliedprefixbytes > wantprefixbytes) {
  57     rc= staticerr(ip, "addr-map existing entry PREFIX too long for PREFIX-LEN",
  58                   "HBYTES ADDRMAP SYNTAX OVERRUN");
  59     goto x_rc;
  60   }
  61
  62   ame->prefixlen= prefixbits;
  63   ame->prefix= TALLOC(wantprefixbytes);  assert(ame->prefix);
  64   memcpy(ame->prefix, data, wantprefixbytes);
  65
  66   if (ame_clear_unwanted(ame, wantprefixbytes)) {
  67     rc= staticerr(ip, "addr-map entry PREFIX contains bits excluded"
  68                   " by PREFIX-LEN", "HBYTES ADDRMAP SYNTAX EXCLBITS");
  69     goto x_rc;
  70   }
  71
  72   return TCL_OK;
  73
  74  x_rc:
  75   ame_free(ame);
  76   return rc;
  77 }
  78
  79 static int ame_contains(const AddrMap_Entry *ref, const Byte *addr, int len) {
  80   int directbytes, leftoverbits;
  81
  82   assert(len >= ref->prefixlen);
  83
  84   directbytes= ref->prefixlen / 8;
  85   if (memcmp(ref->prefix, addr, directbytes)) return 0;
  86
  87   leftoverbits= ref->prefixlen % 8;
  88   if (leftoverbits)
  89     if ((addr[directbytes] & (0xffu << leftoverbits))
  90         != search->prefix[directbytes])
  91       return 0;
  92
  93   return 1;
  94 }
  95
  96 static int ame_compare(const AddrMap_Entry *a, const AddrMap_Entry *b) {
  97   /*    +2 =    a   covers later range of address space than  b
  98    *    +1 =    a   wholly contains but is not equal to       b
  99    *     0 =    a   is identical to                           b
 100    *    -1 =    b   wholly contains but is not equal to       a
 101    *    -2 =    b   covers later range of address space than  a
 102    */
 103   int al= a->prefixlen;
 104   int bl= b->prefixlen;
 105   int ml, d;
 106
 107   if (al==bl) { ml=al; }
 108   else if (al<bl) { ml=al; if (ame_contains(a,b->prefix,bl)) return +1; }
 109   else if (bl<al) { ml=bl; if (ame_contains(b,a->prefix,al)) return -1; }
 110
 111   d= memcmp(b->prefix, a->prefix, prefix_bytes(ml));
 112   return (d > 0 ? +2 :
 113           d < 0 ? -2 :
 114           0);
 115 }
 116
 117 /*---------- searching maps ----------*/
 118
 119 typedef enum {
 120   sr_notfound,
 121   sr_exact,
 122   sr_inbig,
 123   sr_aroundsmall
 124 } Search_Result;
 125
 126 static int
 127 am_binarychop(AddrMap_Value *am, int low_oreq, int high_strict, void *u,
 128               int (*test)(AddrMap_Entry *am, void *u) /* -ve => look left */,
 129               int *found_r) {
 130   int mid, cmp;
 131
 132   for (;;) {
 133     if (high_strict <= low_oreq) {
 134       assert(high_strict == low_oreq);
 135       *found_r= 0;
 136       return high_strict;
 137     }
 138
 139     mid= (high_strict + low_oreq) / 2;
 140     cmp= test(&am->entries[mid], u);
 141
 142     if (!cmp) {
 143       *found_r= 1;
 144       return mid;
 145     }
 146
 147     if (cmp < 0)
 148       high_strict= mid;
 149     else
 150       low_oreq= mid+1;
 151   }
 152 }
 153
 154 struct am_search_u {
 155   int forbid_aroundsmall;
 156   AddrMap_Entry proposed;
 157   Search_Result sr;
 158 };
 159
 160 static int
 161 am_search_binchoptest(AddrMap_Entry *ame, void *u_v) {
 162   struct am_search_u *u= u_v;
 163   int cmp;
 164
 165   cmp= ame_compare(&u.proposed, ame);
 166   switch (cmp) {
 167   case -1:  u->sr= sr_inbig;        return  0;
 168   case  0:  u->sr= sr_exact;        return  0;
 169   case +1:  u->sr= sr_aroundsmall;  return  0;
 170   default:                          return cmp;
 171   }
 172 }
 173
 174 static Search_Result
 175 am_search(AddrMap_Value *am, const AddrMap_Entry *proposed, int *place_r) {
 176   int place, found;
 177   struct am_search_u u;
 178
 179   u.forbid_aroundsmall= forbid_aroundsmall;
 180   u.proposed= proposed;
 181   u.sr= sr_notfound;
 182
 183   *place_r= am_binarychop(am, 0, am.used, &u, am_search_binchoptest, &found);
 184
 185   assert(!!found == (u.sr != sr_notfound));
 186   return u.sr;
 187 }
 188
 189 /*---------- useful operations on AddrMap_Value etc. ----------*/
 190
 191 /*---------- amendment (complex algorithm) ----------*/
 192
 193 struct am_amend_aroundsmall_u {
 194   AddrMap_Entry *new;
 195   int sign;
 196 };
 197
 198
 199 static int
 200 am_amend_aroundsmall_binchoptest(AddrMap_Entry *search, void *u_v) {
 201   struct am_amend_aroundsmall_u *u= u_v;
 202
 203   cmp= u->sign * ame_compare(search, u->new);
 204
 205   switch (cmp) {
 206   case +2:  return -u->sign;
 207   case +1:  return +u->sign;
 208   default:  abort();
 209   }
 210 }
 211
 212 int do_addrmap_amend(ClientData cd, Tcl_Interp *ip,
 213                      AddrMap_Var map, Tcl_Obj *prefix,
 214                      Tcl_Obj *preflen, Tcl_Obj *data) {
 215   AddrMap_Value *am= map.am;
 216   AddrMap_Entry new, *fragment;
 217   AddrMap_Entry *breaking, *replacements;
 218   int rc, insertat, findend, cmp, nreplacements, new_used;
 219   struct am_amend_aroundsmall_u u;
 220
 221   ame_init(&new);
 222
 223   rc= ame_parsekey(ip,&new,prefix,preflen,0);  if (rc) return rc;
 224
 225   sr= am_search(am, &new, &searched);
 226
 227   replacements= &new;
 228   nreplacements= 1;
 229   replace_start= searched;
 230   replace_end= searched;
 231
 232   switch (sr) {
 233
 234   case sr_notfound:
 235     break;
 236
 237   case sr_exact:
 238     replace_end= searched+1;
 239     break;
 240
 241   case sr_aroundsmall:
 242     u.ame= new;
 243     u.sign= -1;
 244     replace_start= am_binarychop(am, 0, searched, &u,
 245                                  am_amend_aroundsmall_binchoptest, &dummy);
 246     u.sign= +1;
 247     replace_end= am_binarychop(am, searched+1, am.used, &u,
 248                                  am_amend_aroundsmall_binchoptest, &dummy);
 249     break;
 250
 251   case sr_inbig:
 252     /* Urgh, we need to break it up.  This produces
 253      *   - innermost prefix (the new one) as specified
 254      *   - one for each bitlength
 255      *       <= innermost
 256      *        > outermost (the existing one)
 257      *     each one specifying the outermost prefix plus zero, one,
 258      *     two, etc. bits of the innermost followed by one bit
 259      *     opposite to the innermost, with the outermost's data
 260      * Eg, if we have ff/8=>A and want to amend so that ffff/16=>B
 261      * then we replace ff/8 with ff0/9=>A ff8/10=>A ffc/11=>A ...
 262      * ... fff8/14=>A fffc/15=>A fffe/16=>A ffff/16=>B.
 263      */
 264
 265     breaking= &am.entries[searched];
 266     nreplacements= new.prefix - breaking->prefixlen + 1;
 267     replacements= TALLOC(sizeof(*replacements) * nreplacements);
 268
 269     for (fragmentlen= breaking->prefixlen + 1,
 270            left_insert= 0, right_insert= nreplacements;
 271          fragmentlen <= new.prefix;
 272          fragmentlen++) {
 273       int fragmentbytes;
 274
 275       fragmentbytes= prefix_bytes(fragmentlen)
 276       fragment->prefixlen= fragmentlen;
 277       fragment->prefix= TALLOC(fragmentbytes);
 278       memcpy(fragment->prefix, new.prefix, fragmentbytes);
 279       ame_clear_unwanted(fragment, fragmentbytes);
 280
 281       fragment->prefix[fragmentbytes] ^=
 282         0x80u >> ((fragmentlen+7) & 7);
 283
 284       switch (ame_compare(&fragment, &new)) {
 285       case -2:  replacements[left_insert++]=  fragment;  break;
 286       case +2:  replacements[--right_insert]= fragment;  break;
 287       default: abort();
 288       }
 289     }
 290     assert(left_insert == right_insert-1);
 291     replacements[left_insert]= new;
 292     ame_init(&new);
 293
 294     replace_end= searched+1;
 295     break;
 296
 297   }
 298
 299   new_used= am.used - (replace_end - replace_start) + nreplacements;
 300
 301   if (new_used > am.space)
 302     am_reallocentries(am, new_used * 2);
 303
 304   for (scan=replacements, i=0;
 305        i < nreplacements;
 306        scan++, i++) {
 307     scan->data= data;
 308     Tcl_IncrRefCount(scan->data);
 309   }
 310
 311   for (i= replace_start, scan= am.entries+i;
 312        i < replace_end;
 313        i++, scan++) {
 314     ame_free(scan);
 315   }
 316
 317   memmove(am.entries + replace_start + nreplacements,
 318           am.entries + replace_end,
 319           sizeof(*am.entries) * (am.used - replace_end));
 320
 321   memcpy(am.entries + replace_start,
 322          replacements,
 323          sizeof(*am.entries) * nreplacements);
 324
 325   am.used= new_used;
 326   if (replacements != &new)
 327     /* we don't bother freeing the actual array elements because
 328      * if replacements!=&new the array is only full if we're
 329      * committed and have already copied the values into the actual
 330      * AddrMap_Value. */
 331     TFREE(replacements);
 332
 333   return TCL_OK;
 334 }
 335
 336 /*---------- other substantial operations on mask maps ----------*/
 337
 338 int do_addrmap_lookup(ClientData cd, Tcl_Interp *ip,
 339                       Tcl_Obj *mapo, HBytes_Value addrhb, Tcl_Obj *def,
 340                       Tcl_Obj **result) {
 341   AddrMap_Value *am= (void*)&mapo->internalRep;
 342   const Byte *addr= hbytes_data(&addrhb);
 343   int addrbytes= hbytes_len(&addrhb);
 344   int i, addrbits, place;
 345   Search_Result sr;
 346
 347   addrbits= addrbytes * 8;
 348   sr= am_search(am, addr, addrbits, &place);
 349
 350   switch (sr) {
 351
 352   case sr_notfound:
 353     if (!def) return staticerr(ip, "address not found in addr-map",
 354                                "HBYTES ADDRMAP NOMATCH");
 355     *result= def;
 356     break;
 357
 358   case sr_aroundsmall:
 359     return staticerr(ip, "address shorter than mask in map",
 360                      "HBYTES ADDRMAP UNDERRUN");
 361
 362   case sr_exact:
 363   case sr_inbig:
 364     *result= am.entres[place].data;
 365     break;
 366
 367   }
 368
 369   return TCL_OK;
 370 }
 371
 372 /*---------- Tcl type and arg parsing functions ----------*/
 373