vfs/arc/internal.d

   1 /* Invisible Vector Library
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, version 3 of the License ONLY.
   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 iv.vfs.arc.internal /*is aliced*/;
  18 import iv.alice;
  19
  20 //version = iv_vfs_arcs_debug_hash;
  21 version = iv_vfs_arcs_nomodulo;
  22
  23
  24 // ////////////////////////////////////////////////////////////////////////// //
  25 package mixin template VFSSimpleArchiveDriverMixin() {
  26 protected:
  27   static struct HashTableEntry {
  28     uint hash; // name hash; name is lowercased
  29     uint prev=uint.max; // previous name with the same reduced hash position
  30     uint didx=uint.max; // dir index
  31   }
  32
  33   // returns lowercased string bytes, suitable for hash calculation
  34   static struct LoStringRange {
  35     const(char)[] s;
  36     usize pos;
  37   pure nothrow @trusted @nogc:
  38     this (const(char)[] as) { pragma(inline, true); s = as; pos = 0; }
  39     @property bool empty () const { pragma(inline, true); return (pos >= s.length); }
  40     @property ubyte front () const {
  41       pragma(inline, true);
  42       import iv.vfs.koi8;
  43       if (pos < s.length) {
  44         version(Windows) {
  45           return cast(ubyte)koi8tolowerTable.ptr[cast(ubyte)koi8from1251Table[s.ptr[pos]]];
  46         } else {
  47           return cast(ubyte)koi8tolowerTable.ptr[cast(ubyte)s.ptr[pos]];
  48         }
  49       } else {
  50         return 0;
  51       }
  52       return (pos < s.length ? cast(ubyte)s.ptr[pos] : 0);
  53     }
  54     void popFront () { pragma(inline, true); if (pos < s.length) ++pos; }
  55   }
  56
  57   static uint hashStr (const(char)[] s) {
  58     //pragma(inline, true);
  59     if (auto res = mur3HashOf(LoStringRange(s))) return res; else return 1; // so we can use 0 as sentinel
  60     //return mur3HashOf(LoStringRange(s));
  61   }
  62
  63 protected:
  64   VFile st;
  65   FileInfo[] dir;
  66   HashTableEntry[] htable; // for names, in reverse order; so name lookups will be faster
  67     // the algo is:
  68     //   htable[hashStr(name)%htable.length]: check if hash is ok, and name is ok
  69     //   if not ok, jump to htable[curht.prev], repeat
  70
  71 protected:
  72   // call this after you done building `dir`; never modify `dir` after that (or call `buildNameHashTable()` again)
  73   final void buildNameHashTable () @trusted {
  74     import core.memory : GC;
  75     if (dir.length == 0 || dir.length >= uint.max-8) { delete htable; return; } // just in case
  76     if (htable.length) htable.assumeSafeAppend;
  77     htable.length = dir.length;
  78     if (htable.ptr is GC.addrOf(htable.ptr)) GC.setAttr(htable.ptr, GC.BlkAttr.NO_INTERIOR);
  79     htable[] = HashTableEntry.init;
  80     version(iv_vfs_arcs_debug_hash) {
  81       uint chaincount = 0;
  82       uint maxchainlen = 0;
  83     }
  84     foreach_reverse (immutable idx, const ref FileInfo fi; dir) {
  85       uint nhash = hashStr(fi.name); // never zero
  86       version(iv_vfs_arcs_nomodulo) {
  87         uint hidx = cast(uint)((cast(ulong)nhash*cast(ulong)htable.length)>>32);
  88         assert(hidx < htable.length);
  89       } else {
  90         uint hidx = nhash%cast(uint)htable.length;
  91       }
  92       if (htable.ptr[hidx].didx == uint.max) {
  93         // first item
  94         htable.ptr[hidx].hash = nhash;
  95         htable.ptr[hidx].didx = cast(uint)idx;
  96         assert(htable.ptr[hidx].prev == uint.max);
  97         //version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("H1: [%.*s] nhash=0x%08x; hidx=%u\n", cast(uint)fi.name.length, fi.name.ptr, nhash, hidx); }
  98       } else {
  99         version(iv_vfs_arcs_debug_hash) {
 100           uint chainlen = 0;
 101           ++chaincount;
 102         }
 103         // chain
 104         while (htable.ptr[hidx].prev != uint.max) {
 105           version(iv_vfs_arcs_debug_hash) ++chainlen;
 106           hidx = htable.ptr[hidx].prev;
 107         }
 108         version(iv_vfs_arcs_debug_hash) if (chainlen > maxchainlen) maxchainlen = chainlen;
 109         // find free slot
 110         uint freeslot = hidx;
 111         foreach (immutable uint count; 0..cast(uint)dir.length) {
 112           freeslot = (freeslot+1)%cast(uint)htable.length;
 113           if (htable.ptr[freeslot].hash == 0) break; // i found her!
 114         }
 115         if (htable.ptr[freeslot].hash != 0) assert(0, "wtf?!");
 116         htable.ptr[hidx].prev = freeslot;
 117         htable.ptr[freeslot].hash = nhash;
 118         htable.ptr[freeslot].didx = cast(uint)idx;
 119         assert(htable.ptr[freeslot].prev == uint.max);
 120       }
 121     }
 122     version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("chaincount=%u; maxchainlen=%u; count=%u\n", chaincount, maxchainlen, cast(uint)htable.length); }
 123   }
 124
 125 public:
 126   this (VFile fl, const(char)[] prefixpath) {
 127     open(fl, prefixpath);
 128     st = fl;
 129   }
 130
 131   override VFile tryOpen (const(char)[] fname, bool ignoreCase) {
 132     static bool xequ (const(char)[] s0, const(char)[] s1, bool icase) {
 133       version(Windows) {
 134         import iv.vfs.koi8;
 135         if (s0.length != s1.length) return false;
 136         foreach (immutable idx, char c0; s0) {
 137           char c1 = koi8from1251Table[s1.ptr[idx]];
 138           if (icase) {
 139             c0 = koi8tolowerTable.ptr[cast(ubyte)c0];
 140             c1 = koi8tolowerTable.ptr[cast(ubyte)c1];
 141           }
 142           if (c0 != c1) return false;
 143         }
 144         return true;
 145       } else {
 146         import iv.vfs.koi8 : koi8StrCaseEqu;
 147         return (icase ? koi8StrCaseEqu(s0, s1) : (s0 == s1));
 148       }
 149     }
 150
 151     if (fname.length == 0 || dir.length == 0) return VFile.init;
 152     // try hashtable first
 153     if (htable.length == dir.length) {
 154       uint nhash = hashStr(fname);
 155       version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("HL: [%.*s] nhash=0x%08x\n", cast(uint)fname.length, fname.ptr, nhash); }
 156       version(iv_vfs_arcs_nomodulo) {
 157         uint hidx = cast(uint)((cast(ulong)nhash*cast(ulong)htable.length)>>32);
 158       } else {
 159         uint hidx = nhash%cast(uint)htable.length;
 160       }
 161       while (hidx != uint.max && htable.ptr[hidx].hash != 0) {
 162         if (htable.ptr[hidx].hash == nhash) {
 163           uint didx = htable.ptr[hidx].didx;
 164           FileInfo* fi = dir.ptr+didx;
 165           if (xequ(fi.name, fname, ignoreCase)) {
 166             version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("HH: [%.*s] nhash=0x%08x; hthash=0x%08x; hidx=%u\n", cast(uint)fi.name.length, fi.name.ptr, nhash, htable.ptr[hidx].hash, hidx); }
 167             return wrap(didx);
 168           }
 169         }
 170         version(iv_vfs_arcs_debug_hash) { import core.stdc.stdio; printf("HS: [%.*s] nhash=0x%08x; hthash=0x%08x; hidx=%u\n", cast(uint)dir.ptr[htable.ptr[hidx].didx].name.length, dir.ptr[htable.ptr[hidx].didx].name.ptr, nhash, htable.ptr[hidx].hash, hidx); }
 171         hidx = htable.ptr[hidx].prev;
 172       }
 173       // alas, and it is guaranteed that we have no such file here
 174       return VFile.init;
 175     }
 176     // fallback to linear search
 177     foreach_reverse (immutable idx, ref fi; dir) {
 178       if (xequ(fi.name, fname, ignoreCase)) return wrap(idx);
 179     }
 180     return VFile.init;
 181   }
 182
 183   override @property usize dirLength () { return dir.length; }
 184   override DirEntry dirEntry (usize idx) { return (idx < dir.length ? DirEntry(cast(uint)idx, dir.ptr[idx].name, dir.ptr[idx].size) : DirEntry.init); }
 185 }
 186
 187
 188 // ////////////////////////////////////////////////////////////////////////// //
 189 package enum VFSSimpleArchiveDetectorMixin(string drvname, string mode="normal") =
 190   "shared static this () { vfsRegisterDetector!"~mode.stringof~"(new "~drvname~"Detector()); }\n"~
 191   "private final class "~drvname~"Detector : VFSDriverDetector {\n"~
 192   "  override VFSDriver tryOpen (VFile fl, const(char)[] prefixpath) {\n"~
 193   "    try {\n"~
 194   "      return new VFSDriver"~drvname~"(fl, prefixpath);\n"~
 195   "    } catch (Exception) {}\n"~
 196   "    return null;\n"~
 197   "  }\n"~
 198   "}\n";