maskmap/addrmap.c

   1 /*
   2  * maskmap - Tcl extension for address mask map data structures
   3  * Copyright 2006 Ian Jackson
   4  *
   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.
   9  *
  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.
  14  *
  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
  18  * 02110-1301, USA.
  19  */
  20
  21
  22 #include "chiark_tcl_hbytes.h"
  23
  24 /*---------- operations on AddrMap_Entry ----------*/
  25
  26 static void ame_free(AddrMap_Entry *ame) {
  27   TFREE(ame->start);  ame->start=0;
  28   if (ame->data) { Tcl_DecrRefCount(ame->data); ame->data=0; }
  29 }
  30
  31 static const Byte *ame_parsecheck_addr(Tcl_Interp *ip, const AddrMap_Value *am,
  32                                        const HBytes_Value *hb) {
  33   int hbl= cht_hb_len(hb);
  34   if (hbl < am->byl) {
  35     cht_staticerr(ip,"addr-map address too short","HBYTES ADDRMAP UNDERRUN");
  36     return 0;
  37   }
  38   if (hbl > am->byl) {
  39     cht_staticerr(ip,"addr-map address too long","HBYTES ADDRMAP OVERRUN");
  40     return 0;
  41   }
  42   return cht_hb_data(hb);
  43 }
  44
  45 static int ame_parsecheck_range(Tcl_Interp *ip, const AddrMap_Value *am,
  46                                 const HBytes_Value *starthb,
  47                                 const HBytes_Value *endhb,
  48                                 const Byte *p_r[2]) {
  49   p_r[0]= ame_parsecheck_addr(ip,am,starthb);  if (!p_r[0]) return TCL_ERROR;
  50   p_r[1]= ame_parsecheck_addr(ip,am,endhb);    if (!p_r[0]) return TCL_ERROR;
  51   if (memcmp(p_r[0],p_r[1],am->byl) > 0)
  52     return cht_staticerr(ip, "addr-map range start is after end",
  53                      "HBYTES ADDRMAP BADRANGE");
  54   return TCL_OK;
  55 }
  56
  57 static int ame_ba_addsubtractone(Byte *out, const Byte *in, int byl,
  58                                  unsigned signum, unsigned onoverflow) {
  59   /* On entry:
  60    *   *in is an array of byl bytes
  61    *   signum is 0xff or 0x01
  62    *   onoverflow is what counts as overflowed value,
  63    *     ie (for unsigned arith) 0x00 for add and 0xff for subtract
  64    * On exit:
  65    *   *out is the resulting value (subject to overflow truncation)
  66    *   return value is TCL_OK, or TCL_ERROR if overflow happened
  67    *   (but interpreter result is not set on overflow)
  68    */
  69   int j;
  70
  71   for (j= byl, in += byl, out += byl;
  72        in--, out--, j>0;
  73        j--) {
  74     *out = (*out) + signum;
  75     if (*out != onoverflow)
  76       return TCL_OK;
  77   }
  78   return TCL_ERROR;
  79 }
  80
  81 /*---------- useful operations on AddrMap_Value etc. ----------*/
  82
  83 static void am_init0(AddrMap_Value *am, int byl) {
  84   am->byl= byl;
  85   am->used= 0;
  86   am->space= 0;
  87   am->entries= 0;
  88 }
  89
  90 static void am_reallocentries(AddrMap_Value *am, int len) {
  91   AddrMap_Entry *newentries;
  92
  93   assert(len >= am->space);
  94   if (!len) return;
  95
  96   assert(len < INT_MAX/sizeof(*newentries));
  97   newentries= TREALLOC(am->entries, sizeof(*newentries)*len);
  98   assert(newentries);
  99
 100   am->space= len;
 101   am->entries= newentries;
 102 }
 103
 104 static void am_free(AddrMap_Value *am) {
 105   AddrMap_Entry *ame;
 106   int i;
 107
 108   if (!am) return;
 109
 110   for (i=0, ame=am->entries; i<am->used; i++, ame++)
 111     ame_free(ame);
 112
 113   TFREE(am->entries);
 114   TFREE(am);
 115 }
 116
 117 /*---------- Tcl type and arg parsing functions ----------*/
 118
 119 int cht_pat_addrmapv(Tcl_Interp *ip, Tcl_Obj *var, AddrMap_Var *agg) {
 120   int rc;
 121   rc= cht_pat_somethingv(ip,var,&agg->sth,&cht_addrmap_type);
 122   if (rc) return rc;
 123   agg->am= agg->sth.obj->internalRep.otherValuePtr;
 124   return TCL_OK;
 125 }
 126
 127 static void addrmap_t_free(Tcl_Obj *o) {
 128   AddrMap_Value *am= o->internalRep.otherValuePtr;
 129   am_free(am);
 130 }
 131
 132 static void addrmap_t_dup(Tcl_Obj *sob, Tcl_Obj *dob) {
 133   AddrMap_Value *sm= sob->internalRep.otherValuePtr;
 134   AddrMap_Value *dm;
 135   AddrMap_Entry *sme, *dme;
 136   int i;
 137
 138   assert(sob->typePtr == &cht_addrmap_type);
 139   cht_objfreeir(dob);
 140   dm= TALLOC(sizeof(*dm));
 141
 142   am_init0(dm,sm->byl);
 143   am_reallocentries(dm,sm->used);
 144   dm->used= sm->used;
 145   for (i=0, sme=sm->entries, dme=dm->entries;
 146        i < dm->used;
 147        i++, sme++, dme++) {
 148     *dme= *sme;
 149     dme->start= TALLOC(sm->byl);  assert(dme->start);
 150     memcpy(dme->start, sme->start, sm->byl);
 151     Tcl_IncrRefCount(dme->data);
 152   }
 153   dob->internalRep.otherValuePtr= dm;
 154   dob->typePtr= &cht_addrmap_type;
 155 }
 156
 157 static void addrmap_t_ustr(Tcl_Obj *so) {
 158   AddrMap_Value *sm= so->internalRep.otherValuePtr;
 159   Tcl_Obj **mainlobjsl, *surrogate;
 160   AddrMap_Entry *sme;
 161   int entnum, listlength;
 162
 163   assert(so->typePtr == &cht_addrmap_type);
 164   mainlobjsl= TALLOC(sizeof(*mainlobjsl) * (sm->used+1));  assert(mainlobjsl);
 165   mainlobjsl[0]= Tcl_NewIntObj(sm->byl * 8);
 166   listlength= 1;
 167
 168   for (entnum=0, sme=sm->entries; entnum<sm->used; entnum++, sme++) {
 169     HBytes_Value hb;
 170     Tcl_Obj *subl[3], *sublo;
 171
 172     if (!sme->data) continue;
 173
 174     cht_hb_array(&hb, sme->start, sm->byl);
 175     subl[0]= cht_ret_hb(0, hb);  assert(subl[0]);
 176
 177     if (entnum+1 < sm->used) {
 178       ame_ba_addsubtractone(cht_hb_arrayspace(&hb, sm->byl),
 179                             (sme+1)->start, sm->byl,
 180                             /*subtract:*/ 0x0ffu, 0x0ffu);
 181     } else {
 182       memset(cht_hb_arrayspace(&hb, sm->byl),
 183              0x0ffu, sm->byl);
 184     }
 185
 186     subl[1]= cht_ret_hb(0, hb);  assert(subl[1]);
 187     subl[2]= sme->data;
 188
 189     sublo= Tcl_NewListObj(3,subl);  assert(sublo);
 190     mainlobjsl[listlength++]= sublo;
 191   }
 192   assert(listlength <= sm->used+1);
 193   surrogate= Tcl_NewListObj(listlength,mainlobjsl);  assert(surrogate);
 194   assert(surrogate);
 195
 196   so->bytes= Tcl_GetStringFromObj(surrogate, &so->length);  assert(so->bytes);
 197   surrogate->bytes= 0; surrogate->length= 0; /* we stole it */
 198 }
 199
 200 static AddrMap_Entry *ame_sfa_alloc(AddrMap_Value *am) {
 201   AddrMap_Entry *ame;
 202
 203   ame= am->entries + am->used;
 204
 205   am->used++;
 206   assert(am->used <= am->space);
 207
 208   ame->start= TALLOC(am->byl);  assert(ame->start);
 209   ame->data= 0;
 210   return ame;
 211 }
 212
 213 static int addrmap_t_sfa(Tcl_Interp *ip, Tcl_Obj *o) {
 214   int rc, inlen, eol, innum, bitlen, cmp;
 215   Tcl_Obj *eo, *starto, *endo;
 216   HBytes_Value starthb, endhb;
 217   const Byte *rangeptrs[2];
 218   AddrMap_Value *am;
 219   AddrMap_Entry *ame;
 220
 221   am= TALLOC(sizeof(*am));  assert(am);
 222   am_init0(am,0);
 223
 224   rc= Tcl_ListObjLength(ip,o,&inlen);  if (rc) goto x_badvalue_rc;
 225
 226   if (inlen<0) {
 227     rc= cht_staticerr(ip, "addr-map overall length < 1", 0);
 228     goto x_badvalue_rc;
 229   }
 230
 231   rc= Tcl_ListObjIndex(ip,o,0,&eo);  if (rc) goto x_badvalue_rc;
 232   rc= Tcl_GetIntFromObj(ip,eo,&bitlen);  if (rc) goto x_badvalue_rc;
 233
 234   if (bitlen<0 || bitlen % 8) {
 235     rc= cht_staticerr(ip, "addr-map overall length < 1", 0);
 236     goto x_badvalue_rc;
 237   }
 238
 239   am->byl= bitlen/8;
 240   assert(inlen < INT_MAX/2);
 241   am_reallocentries(am, (inlen-1)*2+1);
 242
 243   ame= ame_sfa_alloc(am);
 244   memset(ame->start,0,am->byl);
 245
 246   for (innum=1; innum < inlen; innum++) {
 247     rc= Tcl_ListObjIndex(ip,o,innum,&eo);  if (rc) goto x_badvalue_rc;
 248     rc= Tcl_ListObjLength(ip,eo,&eol);  if (rc) goto x_badvalue_rc;
 249
 250     if (eol != 3) {
 251       rc= cht_staticerr(ip, "addr-map entry length != 3", 0);
 252       goto x_badvalue_rc;
 253     }
 254     rc= Tcl_ListObjIndex(ip,eo,0,&starto);  if (rc) goto x_badvalue_rc;
 255     rc= Tcl_ListObjIndex(ip,eo,1,&endo);    if (rc) goto x_badvalue_rc;
 256
 257     rc= cht_pat_hb(ip,starto,&starthb);  if (rc) goto x_badvalue_rc;
 258     rc= cht_pat_hb(ip,endo,&endhb);  if (rc) goto x_badvalue_rc;
 259
 260     rc= ame_parsecheck_range(ip,am,&starthb,&endhb,rangeptrs);
 261     if (rc) goto x_badvalue_rc;
 262
 263     cmp= memcmp(ame->start, rangeptrs[0], am->byl);
 264     if (cmp < 0) {
 265       rc= cht_staticerr(ip, "addr-map entries out of order", 0);
 266       goto x_badvalue_rc;
 267     }
 268     if (cmp > 0) {
 269       ame= ame_sfa_alloc(am);
 270       memcpy(ame->start, rangeptrs[0], am->byl);
 271     }
 272
 273     assert(!ame->data);
 274     rc= Tcl_ListObjIndex(ip,eo,2,&ame->data);  if (rc) goto x_badvalue_rc;
 275     Tcl_IncrRefCount(ame->data);
 276
 277     ame= ame_sfa_alloc(am);
 278     rc= ame_ba_addsubtractone(ame->start, rangeptrs[1], am->byl,
 279                               /*add:*/ 0x01u, 0x00u);
 280     if (rc) {
 281       /* we've overflowed.  it must have been ffffffff.... */
 282       if (innum != inlen-1) {
 283         rc= cht_staticerr(ip, "addr-map non-last entry end is all-bits-1", 0);
 284         goto x_badvalue_rc;
 285       }
 286       TFREE(ame->start);
 287       am->used--;
 288       break;
 289     }
 290   }
 291
 292   /* we commit now */
 293   cht_objfreeir(o);
 294   o->internalRep.otherValuePtr= am;
 295   o->typePtr= &cht_addrmap_type;
 296   return TCL_OK;
 297
 298  x_badvalue_rc:
 299   if (rc == TCL_ERROR)
 300     Tcl_SetObjErrorCode(ip, Tcl_NewStringObj("HBYTES ADDRMAP VALUE", -1));
 301
 302   am_free(am);
 303   return rc;
 304 }
 305
 306 Tcl_ObjType cht_addrmap_type = {
 307   "addr-map",
 308   addrmap_t_free, addrmap_t_dup, addrmap_t_ustr, addrmap_t_sfa
 309 };