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