addrstore.d

   1 /* Written by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   2  * Understanding is not required. Only obedience.
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 3 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  16  */
  17 module addrstore is aliced;
  18
  19
  20 // ////////////////////////////////////////////////////////////////////////// //
  21 enum VType : ubyte {
  22   Byte   = 1<<0, // 8 bits
  23   Word   = 1<<1, // 16 bits
  24   Int    = 1<<2, // 32 bits
  25   Long   = 1<<3, // 64 bits
  26   Float  = 1<<4, // 32 bits
  27   Double = 1<<5, // 64 bits
  28   IMask = 0b00001111,
  29   FMask = 0b00110000,
  30 }
  31
  32
  33 uint maxVTSize (ubyte vt) {
  34   if (vt&VType.Double) return 8;
  35   if (vt&VType.Long) return 8;
  36   if (vt&VType.Float) return 4;
  37   if (vt&VType.Int) return 4;
  38   if (vt&VType.Word) return 2;
  39   return 1;
  40 }
  41
  42
  43 string vtName (ubyte vt) {
  44   if (vt&VType.Double) return "f8";
  45   if (vt&VType.Long) return "i8";
  46   if (vt&VType.Float) return "f4";
  47   if (vt&VType.Int) return "i4";
  48   if (vt&VType.Word) return "i2";
  49   if (vt&VType.Byte) return "i1";
  50   return "b0";
  51 }
  52
  53
  54 // ////////////////////////////////////////////////////////////////////////// //
  55 // pool data format:
  56 // first 4 bytes: base address
  57 // next byte; value type
  58 // data loop:
  59 //  next byte:
  60 //    ==0: 3-byte offset to next address follows
  61 //    ==255: 4-byte next address follows
  62 //    other: this is byte offset to next address
  63 //  next byte: value type
  64
  65
  66 // ////////////////////////////////////////////////////////////////////////// //
  67 static struct AddrVal { uint addr; ubyte vt; }
  68
  69 alias ASRange = ASRangeImpl!false;
  70 alias ASRangeD = ASRangeImpl!true;
  71
  72 struct ASRangeImpl(bool destructive) {
  73 private:
  74   private import core.stdc.stdlib : free;
  75   @disable this (this);
  76   AddrStore.PoolHead* ph;
  77   ubyte* dp; // data pointer in ph
  78   uint dataLeft; // in ph
  79   uint addr; // front element -- address
  80   ubyte vt; // front element -- vtype
  81   uint len; // addresses left (total)
  82
  83 private:
  84   void finish () nothrow @nogc {
  85     static if (destructive) {
  86       // free all remaining pools
  87       import core.stdc.stdlib : free;
  88       while (ph !is null) {
  89         auto np = ph.next;
  90         free(ph);
  91         ph = np;
  92       }
  93     } else {
  94       ph = null;
  95     }
  96     // just in case
  97     dp = null;
  98     dataLeft = 0;
  99     addr = 0;
 100     vt = 0;
 101     len = 0;
 102   }
 103
 104 public:
 105   this (ref AddrStore fv) nothrow @nogc { setup(fv); }
 106   ~this () { finish(); }
 107
 108   void setup (ref AddrStore fv) nothrow @nogc {
 109     finish();
 110     ph = fv.firstPool;
 111     len = fv.addrCount;
 112     static if (destructive) fv.reset(); // reset store, so it can accept new addresses
 113     if (len) {
 114       ++len; // 'cause popFront will dec it
 115       popFront();
 116     }
 117   }
 118
 119   @property bool empty () const pure { pragma(inline, true); return (len == 0); }
 120   @property AddrVal front () const pure { pragma(inline, true); return AddrVal(addr, vt); }
 121   @property uint length () const pure { pragma(inline, true); return len; }
 122
 123   void popFront () {
 124     if (len <= 1) { finish(); return; } // no more
 125     --len; // front item removed
 126     while (ph !is null) {
 127       if (dp is null || dataLeft < 2) {
 128         if (dp !is null) {
 129           // free current block, get next one
 130           static if (destructive) {
 131             import core.stdc.stdlib : free;
 132             auto np = ph.next;
 133             free(ph);
 134             ph = np;
 135           } else {
 136             ph = ph.next;
 137           }
 138           dp = null;
 139           if (ph is null) break;
 140         }
 141         // first entry of new block
 142         dataLeft = ph.used;
 143         if (dataLeft < 5) { dataLeft = 0; continue; } // out of data
 144         dp = ph.data.ptr;
 145         addr = *cast(uint*)dp; dp += 4;
 146         vt = *dp++;
 147         dataLeft -= 5;
 148         return;
 149       }
 150       uint ofs = *dp++;
 151       if (ofs != 0 && ofs != 255) {
 152         // short
 153         addr += ofs;
 154         vt = *dp++;
 155         dataLeft -= 2;
 156       } else if (ofs == 255) {
 157         // new address
 158         if (dataLeft < 6) { dataLeft = 0; continue; } // out of data in this chunk
 159         addr = *dp++;
 160         addr |= (*dp++)<<8;
 161         addr |= (*dp++)<<16;
 162         addr |= (*dp++)<<24;
 163         vt = *dp++;
 164         dataLeft -= 6;
 165       } else if (ofs == 0) {
 166         // long
 167         if (dataLeft < 5) { dataLeft = 0; continue; } // out of data in this chunk
 168         ofs = *dp++;
 169         ofs |= (*dp++)<<8;
 170         ofs |= (*dp++)<<16;
 171         addr += ofs;
 172         vt = *dp++;
 173         dataLeft -= 5;
 174       } else {
 175         assert(0, "wtf?!");
 176       }
 177       return;
 178     }
 179     finish(); // alas
 180   }
 181 }
 182
 183
 184 // ////////////////////////////////////////////////////////////////////////// //
 185 struct AddrStore {
 186 private:
 187   enum PoolSize = 32*1024;
 188
 189   align(1) struct PoolHead {
 190   align(1):
 191     PoolHead* next; // null for last one
 192     uint size; // data size, excluding head
 193     uint used; // data used
 194     // data follows
 195     ubyte[0] data;
 196   nothrow @trusted @nogc:
 197     void putByte (ubyte b) {
 198       if (used >= size || size-used < 1) assert(0, "wtf?!");
 199       *(data.ptr+(used++)) = b;
 200     }
 201   }
 202
 203   PoolHead* firstPool;
 204   PoolHead* lastPool;
 205   uint poolsUsed;
 206   uint lastAddr;
 207   uint addrCount;
 208
 209   void addPool () {
 210     import core.stdc.stdlib : malloc;
 211     PoolHead* ph = cast(PoolHead*)malloc(PoolSize);
 212     if (ph is null) assert(0, "out of memory");
 213     if (lastPool !is null) lastPool.next = ph; else firstPool = ph;
 214     lastPool = ph;
 215     ph.next = null;
 216     ph.size = PoolSize-PoolHead.sizeof;
 217     ph.used = 0;
 218     ++poolsUsed;
 219   }
 220
 221   // reset pools, but don't clear
 222   void reset () nothrow @trusted @nogc {
 223     firstPool = lastPool = null;
 224     poolsUsed = 0;
 225     lastAddr = 0;
 226     addrCount = 0;
 227   }
 228
 229 public:
 230   @disable this (this);
 231   ~this () { clear(); }
 232
 233   uint count () const pure nothrow @safe @nogc { pragma(inline, true); return addrCount; }
 234   uint poolCount () const pure nothrow @safe @nogc { pragma(inline, true); return poolsUsed; }
 235
 236   // not opIndex, 'cause it is slow as hell
 237   AddrVal at (uint idx) {
 238     if (idx >= addrCount) throw new Exception("invalid index");
 239     auto rng = ASRange(this);
 240     while (idx > 0) {
 241       if (rng.empty) assert(0, "wtf?!");
 242       rng.popFront;
 243       --idx;
 244     }
 245     if (rng.empty) assert(0, "wtf?!");
 246     return rng.front;
 247   }
 248
 249   void clear () {
 250     import core.stdc.stdlib : free;
 251     while (firstPool !is null) {
 252       auto cp = firstPool;
 253       firstPool = cp.next;
 254       free(cp);
 255     }
 256     reset();
 257   }
 258
 259   void addAddress (uint addr, ubyte vt) {
 260     // we can waste up to 4 bytes with this; idc
 261     if (lastPool !is null && lastPool.size-lastPool.used >= 6) {
 262       if (lastAddr <= addr && addr-lastAddr <= 0xffffff) {
 263         uint diff = addr-lastAddr;
 264         if (diff == 0 || diff > 254) {
 265           // long form
 266           lastPool.putByte(0);
 267           lastPool.putByte(diff&0xff);
 268           lastPool.putByte((diff>>8)&0xff);
 269           lastPool.putByte((diff>>16)&0xff);
 270         } else {
 271           // short form
 272           lastPool.putByte(cast(ubyte)diff);
 273         }
 274       } else {
 275         // new addr form
 276         lastPool.putByte(255);
 277         lastPool.putByte(addr&0xff);
 278         lastPool.putByte((addr>>8)&0xff);
 279         lastPool.putByte((addr>>16)&0xff);
 280         lastPool.putByte((addr>>24)&0xff);
 281       }
 282     } else {
 283       // new pool
 284       addPool();
 285       *cast(uint*)(lastPool.data.ptr) = addr;
 286       lastPool.used = 4;
 287     }
 288     lastPool.putByte(vt);
 289     lastAddr = addr;
 290     ++addrCount;
 291   }
 292 }